pipette
ENEnglish

Linear Bandits under Exact Sliding-Window Constraints

Seyed Mohammad Hadi Hosseini, Yasin Abbasi-Yadkori, Sattar Vakili

Preprint

En palabras de los autores

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 and within an additive 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 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 that measures feasible communication between viable histories. Combining optimistic remaining-horizon planning with rare policy updates, we obtain a regret bound of . 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.

Resultado principalLimitación que admiten los autores

Apareció: miércoles, 7 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 53 pages, including supplementary material; 8 figures and 6 tables