Search papers, labs, and topics across Lattice.
This paper analyzes linear bandits with exact sliding-window constraints, where consecutive action blocks must satisfy feasibility. For the offline case with known rewards, a stationary solution is optimal under divisibility by window size ($w$), with an $O(w)$ gap otherwise, due to convexity and cyclic-shift invariance. In the online setting, a novel rare-switching OFUL algorithm achieves $\widetilde{O}(d\sqrt{T}+\tau d+w)$ regret by incorporating a transition diameter $\tau$ to quantify feasible reachability, and a more general approach with a history-state diameter $D$ yields $\widetilde{O}(d\sqrt{T}+dD+w)$ regret for non-stationary optimal policies.
Sublinear regret in linear bandits is achievable even with strict sliding-window constraints by leveraging a novel "transition diameter" and a rare-switching algorithm, outperforming naive approaches with significantly fewer policy updates.
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 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.
