# Linear Bandits under Exact Sliding-Window Constraints

arXiv: https://arxiv.org/abs/2610.08745 · HTML: https://mlsanity.com/paper/2610.08745/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 45 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Builds on (most cited first, 3 of 3)

- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [DeepSeek-V3 Technical Report](https://mlsanity.com/paper/2412.19437/) (2024)
- [Bandits with Temporal Stochastic Constraints](https://mlsanity.com/paper/1811.09026/) (2018)

## Abstract (arXiv)

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 wmid 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 widetildeO(d√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 widetildeO(d√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.