Linear Bandits under Exact Cyclic Sliding-Window Constraints

We study linear bandits under exact sliding-window constraints, where every block of $w$ consecutive actions must belong to a prescribed convex feasible set. Unlike pointwise or long-term constraints, these constraints strongly couple decisions across time: each action affects both the current reward and what remains feasible in future rounds. When the reward function is known, we show that convexity and cyclic-shift invariance yield a stationary solution up to a tight additive $\mathcal{O}(w)$ gap. This stationary structure, however, is not enough for online learning. We show that, if stationary feasible histories cannot be connected by feasible paths, every admissible policy may suffer linear regret. We therefore introduce a bounded feasible-transition condition with transition diameter $\tau$, measuring the number of rounds needed to move feasibly between stationary actions. Under this condition, we develop a rare-switching OFUL algorithm that preserves every sliding-window constraint and achieves expected regret $\widetilde{\mathcal{O}}(d\sqrt{T}+\tau d+w)$. We also derive explicit transition-diameter bounds for several common aggregate, norm, risk, and cyclic-ramping constraints. Overall, cyclic symmetry provides a useful structural reduction, while feasible reachability quantifies the additional cost of online learning.