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 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 au that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret widetilde{O}(dsqrt{T}+au 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}(dsqrt{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.

Related

• Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions
• Quantum Multi-Armed Bandits and Linear Bandits: Lower Bounds and Algorithms
• Restless Bandits with Individual Penalty Constraints: A New Near-Optimal Index Policy and How to Learn It
• Optimistic Policy Learning under Pessimistic Adversaries with Regret and Violation Guarantees
• Fast Best-in-Class Regret for Contextual Bandits

Source: arXiv cs.LG | 2026-10-07