# Mixing Makes Markovian Contexts Cheap for Linear Bandits

arXiv: https://arxiv.org/abs/2603.12530 · HTML: https://mlsanity.com/paper/2603.12530/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 22 of its 48 references that are in the map.
- First posted on arXiv 13 Mar 2026.

## Builds on (most cited first, 22 of 22)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Efficient Contextual Bandits in Non-stationary Worlds](https://mlsanity.com/paper/1708.01799/) (2017)
- [Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2205.06811/) (2022)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [Adaptive Exploration in Linear Contextual Bandit](https://mlsanity.com/paper/1910.06996/) (2019)
- [Exploration in Structured Reinforcement Learning](https://mlsanity.com/paper/1806.00775/) (2018)
- [An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits](https://mlsanity.com/paper/2010.12247/) (2020)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [A Contextual-bandit-based Approach for Informed Decision-making in Clinical Trials](https://mlsanity.com/paper/1809.00258/) (2018)
- [Stochastic Linear Contextual Bandits with Diverse Contexts](https://mlsanity.com/paper/2003.02681/) (2020)
- [Artificial Intelligence of Things: A Survey](https://mlsanity.com/paper/2410.19998/) (2024)
- [Evaluating Online Bandit Exploration In Large-Scale Recommender System](https://mlsanity.com/paper/2304.02572/) (2023)
- [Partially Observable Contextual Bandits with Linear Payoffs](https://mlsanity.com/paper/2409.11521/) (2024)
- [An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction](https://mlsanity.com/paper/2508.11931/) (2025)
- [Observation-Augmented Contextual Multi-Armed Bandits for Robotic Search and Exploration](https://mlsanity.com/paper/2312.12583/) (2023)
- [Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensing](https://mlsanity.com/paper/2407.13995/) (2024)

## Abstract (arXiv)

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.