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

Mar 16, 2026

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

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.

Naoto Tani, Futoshi Futami

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

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Ask PDF

May 31, 2026

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

We study linear contextual bandits under rare parameter updates: the learner may incorporate reward feedback into its parameter estimate only at a small number of update times, while still observing contexts online and selecting actions sequentially. This viewpoint clarifies a practical distinction that is often blurred in the literature: many "strictly batched" methods additionally restrict within-interval context adaptivity, meaning that the action rule inside an interval cannot depend on the sequence of realized contexts/actions in that interval (beyond the current round's context). For linear contextual bandits, we propose two practical algorithms with only

O(\log\log T)

parameter updates. Our first algorithm BLCE-G attains minimax-optimal regret (up to polylogarithmic factors in

T

) simultaneously in both the small-

K

and large-

K

regimes under a static schedule. Our second algorithm BLCE removes the near G-optimal design step -- a dominant computational bottleneck in prior strictly batched static-grid methods -- yet preserves minimax-optimal regret and achieves the lowest known runtime complexity among optimal algorithms. We further extend these rare-update and computational principles to generalized linear contextual bandits. Overall, our results yield statistically optimal algorithms under

O(\log\log T)

parameter updates that are also computationally efficient in practice.

Sanghoon Yu, Min-hwan Oh

Seoul National University, Seoul, Republic of Korea

Contextual Bandits Linear Contextual Bandits Generalized Linear Bandits

Ask PDF

Sep 14, 2026

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

We study stochastic linear contextual bandits with arbitrary action menus that may depend on the fixed parameter and the interaction history. We establish matching upper and lower bounds, up to logarithmic factors. Let

d

be the dimension,

K

be the menu size, and

T

the time horizon. For

2\le K\le d

, we prove an upper bound

\widetilde O(K^{1/4}\sqrt{dT})

. When

T\ge d^2

, we further prove a lower bound

Ω(K^{1/4}\sqrt{dT})

. Thus, for

T\ge d^2

and

2\le K\le d

, the upper and lower bounds match up to logarithmic factors, and the polynomial dependence on

K

is optimal. Compared with the previous

\widetilde O(\sqrt{dKT})

bound, our upper bound improves the dependence on

K

by a factor of

K^{1/4}

. For

K\ge d

, we prove an upper bound

\widetilde O_{d,T}\left(\sqrt{dT}\min\{\sqrt d,(d\log K)^{1/4}\}\right)

and a lower bound

Ω\left(\sqrt{dT}\min\left\{\sqrt d,\left(\frac{d\log K}{\log(2d)}\right)^{1/4}\right\}\right)

. Here,

\widetilde O_{d,T}

omits logarithmic factors only in

d

and

T

. In particular, for polynomially large

K\ge d

, the upper and lower bounds both scale as

d^{3/4}\sqrt T

up to logarithmic factors, improving the standard

\widetilde O(d\sqrt T)

rate by a factor of

d^{1/4}

. As

K

grows further, the regret smoothly recovers the

d\sqrt T

scale once

\log K

reaches order

d

Tianyuan Jin

Data Science and Analytics Thrust The Hong Kong University of Science and Technology (Guangzhou)

Multi-Armed Bandits Minimax Regret Contextual Bandits Linear Contextual Bandits

Ask PDF