Linear Bandits under Exact Sliding-Window Constraints

תקציר מקורי באנגליתarXiv:2610.08745v1 Announce Type: new Abstract: 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 $\tau$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+\tau d+w)$ against the offline-optimal feasible trajectory. Finally, we remove cyclic invariance and consi