Linear Contextual Bandits

Follow this topic Ask about this topic

Linear contextual bandits study how to choose actions using observed context features when rewards are unknown and feedback arrives only for selected actions. Methods such as LinUCB and optimism-based elimination, Thompson sampling, and adversarial online learning estimate linear reward models while trading off exploration and cumulative regret. Current work extends these methods to non-stationary, noisy, corrupted, resource-constrained, and offline-to-online settings, while also reducing computation and communication costs. A central tension is how to gain stronger guarantees or exploit structure without relying on restrictive assumptions about context coverage, drift, noise, or action availability.

Latest papers

33 papers8 papers in the last four weeks, up 100% on the four weeks before. 0.0% of all new papers.

Mixing Makes Markovian Contexts Cheap for Linear Bandits
Mar 13, 2026Kaan Buyukkalayci, Osama Hanna, Christina FragouliMarkovian Bandits Contextual Bandits
University of California, Los Angeles · Meta, Superintelligence Lab
Invariance-Based Dynamic Regret Minimization
Mar 4, 2026Margherita Lazzaretto, Jonas Peters, Niklas PfisterNon-Stationary Bandits Linear Contextual Bandits
University of Copenhagen · ETH Zürich · Lakera Zürich
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford

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

Mixing Makes Markovian Contexts Cheap for Linear Bandits

Kaan Buyukkalayci, Osama Hanna, Christina Fragouli

University of California, Los Angeles · Meta, Superintelligence Lab

Markovian Bandits Contextual Bandits Linear Contextual Bandits

Open paper AskPDF 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.

Latest papers

Mixing Makes Markovian Contexts Cheap for Linear Bandits

Invariance-Based Dynamic Regret Minimization

Best-of-Both Worlds for linear contextual bandits with paid observations