arXiv 论文：精确滑动窗口约束下的线性 Bandit 算法与遗憾界分析
Linear Bandits under Exact Sliding-Window Constraints
推荐给做在线决策或推荐排序的读者：这篇论文处理了“连续动作组合必须合规”这种常见但少有人形式化的问题，给出了可用的 OFUL 算法和遗憾界证明。
arXiv 论文 2610.08745 研究线性 bandit 在精确滑动窗口约束下的表现，即每段连续动作序列都必须属于给定可行集。论文证明当窗口长度 w 整除总时长 T 时，凸性与循环平移不变性使平稳解最优，否则差距不超过 O(w)。作者提出过渡直径 τ 刻画可达性，并设计 rare-switching OFUL 算法，遗憾界为 O(d√T+τd+w)。在去除循环不变性的一般设定下，论文进一步用历史状态直径 D 得到 O(d√T+dD+w) 的遗憾界，并在真实与合成基准上验证了算法在保持精确可行性的同时大幅减少策略切换次数。
Linear Bandits under Exact Sliding-Window Constraints
We study linear bandits under exact sliding-window constraints, where every consecutive block of actions must belong to a prescribed feasible set. In the offline setting, where the reward function is known, we show that convexity and cyclic-shift invariance make a stationary solution optimal when $w\mid T$ and within an additive $O(w)$ gap otherwise. In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible. We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consider general sliding-window constraints, where optimal behavior may be non-stationary. We represent recent action history as the state of a finite-memory control problem and introduce a history-state diameter $D$ that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of $\widetilde{O}(d\sqrt{T}+dD+w)$. We evaluate our approach on real-world and synthetic benchmarks, showing that it maintains exact feasibility while achieving reward and regret comparable to baselines with substantially fewer policy updates.
