Linear Bandits under Exact Sliding-Window Constraints

Key points

• 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.1
• In the online setting, we show that geometric structure alone is insufficient for learning, and sublinear regret can be impossible.1
• We introduce a transition diameter $τ$ that quantifies feasible reachability and develop a rare-switching OFUL algorithm with regret $\widetilde{O}(d\sqrt{T}+τd+w)$ against the offline-optimal feasible trajectory.1
• 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.1

Sources (1)

• [1]Linear Bandits under Exact Sliding-Window Constraints
  arXiv (AI, ML, NLP, CV, robotics, multi-agent) · Oct 6, 05:41 PM

  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.

Extractive summary: sentences quoted from the sources.