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

Jul 3, 2026cs.LG

Dynamic Regret for Non-Stationary Linear Bandits via Misspecification Reductions

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.

Zihao Hu, Yuan Yao, Jiheng Zhang +1

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

Contextual Bandit Framework Regret Feasibility

Ask PDF

Jun 8, 2026cs.LG

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

Motivated by the recency effect in online learning, we study algorithms for single-pass sliding-window streaming multi-armed bandits (MABs) in this paper. In this setting, we are given

n

arms with unknown sub-Gaussian reward distributions and a parameter

W

. The arms arrive in a single-pass stream, and only the most recent

W

arms are considered valid. The algorithm is required to perform pure exploration and regret minimization with limited memory, defined as the number of stored arms. The model is a natural extension of the streaming multi-armed bandits model (without the sliding window) that has been extensively studied in recent years. We provide a comprehensive analysis of both the pure exploration and regret minimization problems with the model. For pure exploration, we prove that finding the best arm is hard with sublinear memory while finding an approximate best arm admits an efficient algorithm. For regret minimization, we explore a new notion of regret and give sharp memory-regret trade-offs for any single-pass algorithm. We complement our theoretical results with experiments, demonstrating the trade-offs between sample, regret, and memory.

Vladimir Braverman, Chen Wang, Liudeng Wang +1

Johns Hopkins University · Rensselaer Polytechnic Institute · Texas A&M University

Stochastic Multi-Armed Bandits Bidirectional Long Short-Term Memory

Ask PDF

Jun 3, 2026cs.LG

Offline-to-Online Learning in Linear Bandits

We study online learning with an additional offline dataset in the stochastic linear bandit setting. Although this problem arises frequently in practice, the offline-to-online tradeoff remains poorly understood in structured environments. We propose a linear bandit algorithm that balances this tradeoff: it relies on offline data during early rounds, and increasingly favors exploration as the horizon grows. We establish regret bounds showing that our method is simultaneously competitive with both purely online and purely offline solutions. In particular, it achieves sublinear regret relative to the optimal action in the number of online interactions, while its regret relative to an offline reference decreases as the number of offline samples grows. Empirical results further demonstrate its effectiveness across various problem parameters.

Kushagra Chandak, Toshinori Kitamura, Xiaoqi Tan

Department of Computing Science, University of Alberta, Canada

Contextual Bandit Framework

Ask PDF