mlsanityData to 7 Oct 2026

Mixing Makes Markovian Contexts Cheap for Linear Bandits

arXiv 2603.12530 ↗First posted 13 Mar 2026cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

22 of 48 references.

References · 22

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  3. 2021Adapting to Misspecification in Contextual Banditscited by 81
  4. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 81
  5. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  6. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  7. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  8. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  9. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  10. 2018Exploration in Structured Reinforcement Learningcited by 34
  11. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  12. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
10 more
  1. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  2. 2018A Contextual-bandit-based Approach for Informed Decision-making in Clinical Trialscited by 18
  3. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  4. 2020Stochastic Linear Contextual Bandits with Diverse Contextscited by 16
  5. 2024Artificial Intelligence of Things: A Surveycited by 12
  6. 2023Evaluating Online Bandit Exploration In Large-Scale Recommender Systemcited by 7
  7. 2024Partially Observable Contextual Bandits with Linear Payoffscited by 5
  8. 2023Observation-Augmented Contextual Multi-Armed Bandits for Robotic Search and Explorationcited by 3
  9. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  10. 2024Track-MDP: Reinforcement Learning for Target Tracking with Controlled Sensingcited by 1

Built on by

Not cited yet.