Linear Bandits under Exact Sliding-Window Constraints

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

cs.LGOct 6, 2026

Linear Bandits under Exact Sliding-Window Constraints

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

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 $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 $τ$ 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. 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.

Figures & tables

Setting	Action-wise constraints	Horizon-wide constraints	History dependence	Exact-window constraints
Safe/constrained bandits	✓
Long-term constrained learning		✓
Online learning with memory			✓
Switching-constrained bandits		✓	✓
This work	✓ †	✓ ‡	✓	✓

Table 1: Comparison with related sequential-learning frameworks.

$T$	Method	Avg. Reward	Norm. Pseudo-Regret	Violations	Updates
500	Rare-Update Planning	$0.4618\pm 0.0343$	$0.0540\pm 0.0033$	$0.0$	$31.8$
	Myopic Feasible OFUL	$0.4638\pm 0.0344$	$0.0520\pm 0.0031$	$0.0$	$500.0$
	Primal-Dual OFUL	$0.4639\pm 0.0344$	$0.0518\pm 0.0031$	$160.6$	$500.0$
	Unconstrained OFUL	$0.4643\pm 0.0344$	$0.0515\pm 0.0031$	$177.6$	$500.0$
2500	Rare-Update Planning	$0.4772\pm 0.0350$	$0.0386\pm 0.0019$	$0.0$	$49.5$
	Myopic Feasible OFUL	$0.4801\pm 0.0352$	$0.0356\pm 0.0017$	$0.0$	$2500.0$

Table 2: Recommendation results on KuaiRand-1K over 100 users, with 10 independent simulations per user and horizon. Average reward and normalized pseudo-regret are reported as mean

\pm

95% confidence interval.

$T$	Method	Avg. Reward	Norm. Pseudo-Regret	Violations	Updates
500	Rare-Update Optimistic Planning	$0.7655\pm 0.0145$	$0.1645\pm 0.0134$	$0.0$	$250.2$
	Myopic Feasible OFUL	$0.7701\pm 0.0138$	$0.1599\pm 0.0130$	$0.0$	$500.0$
	Unconstrained OFUL	$0.7713\pm 0.0167$	$0.1587\pm 0.0160$	$4.7$	$500.0$
	Primal-Dual OFUL	$0.7713\pm 0.0167$	$0.1587\pm 0.0160$	$4.7$	$500.0$
2500	Rare-Update Optimistic Planning	$0.7775\pm 0.0049$	$0.1549\pm 0.0040$	$0.0$	$789.8$
	Myopic Feasible OFUL	$0.7768\pm 0.0048$	$0.1556\pm 0.0048$	$0.0$	$2500.0$

Table 3: LLM routing results with sliding-window length

w=5

and budget

B=0.40

over 10 independent simulations for each horizon. Average reward and normalized pseudo-regret are reported as mean

\pm

95% confidence interval.

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Constraint class	Window condition	Transition diameter
Aggregate budget	$\displaystyle\sum_{i=1}^{w}c^{\top}x_{i}\leq B$	$\tau\leq w-1$
Maximum	$\displaystyle\max_{1\leq i\leq w}\phi(x_{i})\leq\rho$	$\tau\leq w-1$
Box	$\displaystyle\ell\leq x_{i}\leq u,\quad i=1,\ldots,w$	$\tau\leq w-1$
Exponential	$\displaystyle\sum_{i=1}^{w}\exp(a^{\top}x_{i}-b)\leq\rho$	$\tau\leq w-1$
$\ell_{p}$ -norm	$\displaystyle\left(\sum_{i=1}^{w}\\|Ax_{i}-b\\|_{p}^{p}\right)^{1/p}\leq\rho$	$\tau\leq w-1$
Convex risk	$\displaystyle\frac{1}{w}\sum_{i=1}^{w}\ell(x_{i})\leq\rho$	$\tau\leq w-1$

Appendix

Table 4: Transition-diameter for convex and cyclically invariant sliding-window constraints.

Constraint class	Window condition	History diameter
State-independent	$\displaystyle\mathcal{C}=\mathcal{A}^{w}$	$\displaystyle D=w-1$
Box	$\displaystyle\ell\leq x_{i}\leq u$	$\displaystyle D=w-1$
Maximum	$\displaystyle\max_{i}\phi(x_{i})\leq\rho$	$\displaystyle D=w-1$
Aggregate budget	$\displaystyle\sum_{i=1}^{w}c^{\top}x_{i}\leq B$	$\displaystyle D\leq 2(w-1)$
Exponential	$\displaystyle\sum_{i=1}^{w}e^{a^{\top}x_{i}-b}\leq\rho$	$\displaystyle D\leq 2(w-1)$
Aggregate $\ell_{p}$	$\displaystyle\sum_{i=1}^{w}\\|Ax_{i}-b\\|_{p}^{p}\leq\rho^{p}$	$\displaystyle D\leq 2(w-1)$

Appendix

Table 5: History-state diameter for representative sliding-window constraints.

Figure 1: Offline geometry and horizon misalignment. Left: stationary approximation gap versus horizon remainder for $w=32$ . Right: maximum gap versus window length; markers show the LP solutions and the dashed line shows the tight value $w/4$ .

Figure 2: Rare switching under cyclic ramping constraints. (a) Pseudo-regret, (b) stationary-target switches, (c) transition rounds, and (d) constraint violations for Rare-switching OFUL, Frequent-update feasible OFUL, and Unconstrained OFUL across $\rho$ . Curves show means over 30 runs with 95% confidence intervals.

Figure 3: Planning beyond cyclic symmetry. Left: normalized pseudo-regret relative to the exact offline optimum. Right: number of policy updates. Curves show means over 30 runs with 95% confidence intervals.

Budget	$T$	Method	Avg. Reward	Norm. Pseudo-Regret	Violations	Updates
$0.15$	$500$	Rare-Update Optimistic Planning	$0.7618\pm 0.0116$	$0.1566\pm 0.0132$	0.0	249.8
		Myopic Feasible OFUL	$0.7583\pm 0.0120$	$0.1601\pm 0.0108$	0.0	500.0
		Unconstrained OFUL	$0.7713\pm 0.0167$	$0.1471\pm 0.0156$	104.5	500.0
		Primal-Dual OFUL	$0.7686\pm 0.0161$	$0.1498\pm 0.0136$	112.7	500.0
	$2500$	Rare-Update Optimistic Planning	$0.7699\pm 0.0039$	$0.1509\pm 0.0041$	0.0	789.1
		Myopic Feasible OFUL	$0.7682\pm 0.0048$	$0.1525\pm 0.0049$	0.0	2500.0

Appendix

Table 6: LLM-routing performance across different sliding-window budgets. Average reward and normalized pseudo-regret are reported as mean

\pm

95% confidence interval over 10 independent simulations for each configuration; violations and updates are reported as means.

Figure 4: Ablation on optimistic exploration. Left : normalized pseudo-regret for Rare-Update Optimistic Planning and its non-optimistic variant. Right: paired regret difference, defined as $\mathrm{Regret}_{\mathrm{NoOpt}}-\mathrm{Regret}_{\mathrm{Opt}}$ , so positive values favor optimism. Error bars denote 95% confidence intervals.

Figure 5: Sensitivity to the determinant switching threshold $\alpha$ . (a) Realized pseudo-regret, (b) number of stationary-target switches, and (c) total number of transition rounds. The default choice $\alpha=2$ achieves the lowest pseudo-regret in this experiment. Curves show means over 30 runs with 95% confidence intervals.

Figure 6: Scaling with the action dimension for $d\in\{4,8,16,32\}$ with a fixed reward gap of $0.2$ . (a) Realized pseudo-regret, (b) number of stationary-target switches, and (c) total number of transition rounds. Curves show means over 30 runs with 95% confidence intervals.

Figure 7: Scaling with the window length for $w\in\{2,4,8,16,32\}$ with $T/w=2048$ fixed. (a) Realized pseudo-regret, (b) number of stationary-target switches, (c) total number of transition rounds, and (d) transition rounds per switch. The switch count remains nearly constant, while the cost of each feasible switch grows with $w$ . Curves show means over 30 runs with 95% confidence intervals.

Figure 8: Sensitivity to the planning horizon $H$ for $T=1024$ . Left: normalized pseudo-regret against the offline-optimal feasible trajectory. Right: number of policy updates. The case $H=1$ is myopic and “Full” denotes exact remaining-horizon planning. Curves show means over 30 runs with 95% confidence intervals.

\beta_{k}\leftarrow R\sqrt{2\log\!\left(\frac{\det(W_{k})^{1/2}}{\det(\lambda I_{d})^{1/2}\delta}\right)}+\sqrt{\lambda}S

Appendix

Algorithm 2 Rare-Update Optimistic Planning

Explore similar work

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions
Jul 3, 2026Zihao Hu, Yuan Yao, Jiheng Zhang +1Contextual Bandit Framework Regret
Department of Mathematics, The Hong Kong University of Science and Technology
Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits
Jun 8, 2026Vladimir Braverman, Chen Wang, Liudeng Wang +1Stochastic Multi-Armed Bandits Bidirectional Long Short-Term Memory
Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University
Offline-to-Online Learning in Linear Bandits
Jun 3, 2026Kushagra Chandak, Toshinori Kitamura, Xiaoqi TanContextual Bandit Framework
Department of Computing Science, University of Alberta, Canada

Jul 3, 2026, cs.LGJ/K move · Enter open · S save

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Zihao Hu, Yuan Yao, Jiheng Zhang, Zhengyuan Zhou

Department of Mathematics, The Hong Kong University of Science and Technology

Contextual Bandit Framework Regret Feasibility

Open paper AskPDF arXiv

Many online decision-making problems involve both round-specific feasible actions and drifting reward models: eligible ad impressions, feasible prices, and available treatments can change over time, while user preferences, demand curves, and patient responses may evolve. Motivated by these applications, we study non-stationary linear bandits with round-specific feasible decision sets. Existing methods that obtain the optimal

\widetilde O(T^{2/3}P_T^{1/3})

dependence, where

P_T

is the path length of the reward-parameter sequence, impose an orthogonal-structure assumption on round-specific decision sets, which can be restrictive in contextual applications. We address this gap through a unified misspecification-reduction viewpoint: after partitioning the horizon into blocks, we relate each block's dynamic regret to regret against a fixed-parameter linear bandit benchmark, with the within-block parameter drift entering as bounded misspecification. Restarting algorithms with misspecification-dependent regret guarantees then yields the optimal

T^{2/3}P_T^{1/3}

dynamic-regret dependence for both linear bandits with general compact decision sets and

K

-armed contextual linear bandits.

Abstract

Explore similar work

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

Online Learning with Recency: Algorithms for Sliding-window Streaming Multi-armed Bandits

Offline-to-Online Learning in Linear Bandits