Mixing Makes Markovian Contexts Cheap for Linear Bandits

Kaan Buyukkalayci; Osama Hanna; Christina Fragouli

cs.LGMar 13, 2026

Mixing Makes Markovian Contexts Cheap for Linear Bandits

Authors: Kaan Buyukkalayci, Osama Hanna, Christina Fragouli

Organizations: University of California, Los Angeles · Meta, Superintelligence Lab

Abstract

Recent work shows that when contexts are drawn i.i.d., linear contextual bandits can be reduced to single-context linear bandits. This ``contexts are cheap'' perspective is highly advantageous, as it allows for sharper finite-time analyses and leverages mature techniques from the linear bandit literature, such as those for misspecification and adversarial corruption. However, this reduction crucially relies on the independence of contexts and does not extend to settings with temporally correlated (e.g., Markovian) contexts, which arise frequently in practice. Motivated by applications with temporally correlated availability, we extend this perspective to linear bandits with Markovian context processes, where the action set evolves via an exogenous Markov chain. Our main contribution is a reduction that applies under uniform geometric ergodicity. We construct a stationary surrogate action set to solve the problem using a standard linear bandit oracle, employing a delayed-update scheme to control the bias induced by the nonstationary conditional context distributions. We further provide a phased algorithm for unknown stationary distributions that learns the surrogate mapping online. In both settings, we obtain a high-probability worst-case regret bound matching that of the underlying linear bandit oracle in sufficiently fast mixing regimes. We then validate our results on a real-world instance, where we show practical gains over a LinUCB baseline.

Figures & tables

Figure 1: Sketch of the outdoor experiment site and vehicle trajectory.

Panel of Figure 2 — Figure 2: Performance of Algorithm 2 on the bandit instance with linearized rewards. Shaded regions show $\pm$ one standard error around the mean across runs.

Panel of Figure 3 — Figure 3: Performance of Algorithms 1 and 2 on the bandit instance with rewards equal to the utility function.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Variant	Bound	Type	Bound	Type
	Known best bound		Our Markovian reduction
Base	$O(d\sqrt{T}\log T)$ [ Abbasi-Yadkori et al., 2011 ]	w.h.p.	$O(d\sqrt{T\log T})$	w.h.p.
Misspecified	$O(d\sqrt{T}\log T+\varepsilon\sqrt{dT})$ [ Foster et al., 2020 ]	exp.	$O(d\sqrt{T\log T}+\varepsilon\sqrt{dT}\log T)$	w.h.p.
Adv. corrupt.	$\tilde{O}(d^{4.5}\sqrt{T}+d^{4}C)$ [ Wei et al., 2022 ]	w.h.p.	$\tilde{O}(d\sqrt{T}+d^{1.5}C)$	w.h.p.

Appendix

Table 1: Comparison between the known best guarantees for representative contextual linear bandit variants and the guarantees obtained by applying our Markovian reduction. Here, “w.h.p.” denotes high-probability bounds and “exp.” denotes bounds in expectation.

Object	Symbol	Definition	Value
Nodes	$N$	sensing nodes	$9$
Actions	$\|S\|$	selected subset size	$1,2,3$
Actions	$\|\mathcal{A}_{t}\|$	$\sum_{k=1}^{3}\binom{N}{k}=\binom{9}{1}+\binom{9}{2}+\binom{9}{3}$	$129$
Utility	$\rho$	distance scale in $u_{t}(S)$	$10$
Utility	$(w_{1},w_{2},w_{3})$	weights on sorted selected-node distances	$(1,0.45,0.20)$
Context $c_{t}$	$d_{\mathrm{node}}$	features per node	$9$

Appendix

Table 2: Core numerical parameters and feature dimensions for the bandit instance construction.

Tower	Input	Hidden widths	Nonlinear layers	Output
Context tower	$c_{t}\in\mathbb{R}^{85}$	$512,256$	LayerNorm after the first hidden layer; ReLU after both hidden layers	$z_{c}(c_{t})\in\mathbb{R}^{8}$
Action tower	$\psi_{t}(S)\in\mathbb{R}^{42}$	$512,256$	LayerNorm after the first hidden layer; ReLU after both hidden layers	$z_{a}(\psi_{t}(S))\in\mathbb{R}^{8}$

Appendix

Table 3: Two-tower embedding architecture.

Object	Symbol	Construction	Value
Replay	$T_{\mathrm{orig}}$	original real-data contexts	$7208$
	$T_{\mathrm{replay}}$	replay horizon	$10^{6}$
	$\Delta_{\mathrm{replay}}$	effective time step between replayed contexts	$5$ sec.
State proxy	$d_{\mathrm{PCA}}$	PCA dimension before clustering	$10$
State proxy	$K_{\mathrm{state}}$	number of $K$ -means clusters after PCA	$20$
Mixing proxy	$\widehat{C}_{\mathrm{mix}}$	fitted prefactor in ( 1 )	$1.29$

Appendix

Table 4: Environment characteristics for the bandit instance

Panel of Figure 4 — Figure 4: Diagnostics for the Markovian bandit instance over one replay period. (a) demonstrates ergodicity, (b) shows the visitation frequency of context groups and (c) demonstrates the rewards obtained from the model and model misspecification

Object	Symbol	Role	Value
Instance	$\|\mathcal{A}_{t}\|$	number of available actions per context	$129$
Instance	$\|\Theta\|$	finite bank size of surrogate directions	$256$
Delay	$c_{\tau}$	delayed-feedback setting	$1$
Delay	$c_{\tau}$	no-delay ablation	$0$
Algorithm 2	$\mathrm{radix}$	epoch growth factor	$100$
LinUCB	$\lambda$	regularization, used by baseline and reduced subroutines	$1.0$

Appendix

Table 5: Practical implementation parameters for the tested algorithms.

Panel of Figure 5 — Figure 5: Performance of Algorithm 1 on the bandit instance with linearized rewards. Shaded regions show $\pm$ one standard error around the mean across runs.

Explore similar work

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
Mar 16, 2026Naoto Tani, Futoshi FutamiContextual Bandits Linear Contextual Bandits
The University of Osaka · RIKEN AIP · The University of Tokyo
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
May 31, 2026Sanghoon Yu, Min-hwan OhContextual Bandits Linear Contextual Bandits
Seoul National University, Seoul, Republic of Korea
Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets
Sep 14, 2026Tianyuan JinMulti-Armed Bandits Minimax Regret
Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)

Mar 16, 2026J/K move · Enter open · S save

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

Naoto Tani, Futoshi Futami

The University of Osaka · RIKEN AIP · The University of Tokyo

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Open paper AskPDF arXiv

We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite

(1+ε)

-th moments for some

ε\in (0,1]

. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs

\mathcal{O}(t\log T)

computational cost, our algorithm reduces this to

\mathcal{O}(1)

per round. We establish an additive regret bound consisting of a term depending on the

(1+ε)

-moment bound of the noise and a term depending on the total amount of corruption. In particular, when

ε= 1

, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.

Abstract

Explore similar work

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates

Nearly Minimax-Optimal Regret for Linear Contextual Bandits with Arbitrary Adaptive Action Sets