# Adaptive Exploration in Linear Contextual Bandit

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Oct 2019.

## Built on by (most cited first, 30 of 43)

- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature](https://mlsanity.com/paper/2102.04168/) (2021)
- [Leveraging Good Representations in Linear Contextual Bandits](https://mlsanity.com/paper/2104.03781/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Information Directed Sampling for Sparse Linear Bandits](https://mlsanity.com/paper/2105.14267/) (2021)
- [Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selection](https://mlsanity.com/paper/2110.14798/) (2021)
- [An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledge](https://mlsanity.com/paper/2205.14775/) (2022)
- [Instance-optimal PAC Algorithms for Contextual Bandits](https://mlsanity.com/paper/2207.02357/) (2022)
- [A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs](https://mlsanity.com/paper/2106.13013/) (2021)
- [Sequential Learning of the Pareto Front for Multi-objective Bandits](https://mlsanity.com/paper/2501.17513/) (2025)
- [Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applications](https://mlsanity.com/paper/2302.03683/) (2023)
- [Federated Linear Contextual Bandits with User-level Differential Privacy](https://mlsanity.com/paper/2306.05275/) (2023)
- [Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference](https://mlsanity.com/paper/2207.11597/) (2022)
- [Residual Bootstrap Exploration for Stochastic Linear Bandit](https://mlsanity.com/paper/2202.11474/) (2022)
- [Asymptotic Instance-Optimal Algorithms for Interactive Decision Making](https://mlsanity.com/paper/2206.02326/) (2022)
- [Optimal Batched Linear Bandits](https://mlsanity.com/paper/2406.04137/) (2024)
- [On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits](https://mlsanity.com/paper/2303.09390/) (2023)
- [Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guarantees](https://mlsanity.com/paper/2210.13083/) (2022)
- [On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structure](https://mlsanity.com/paper/2211.15129/) (2022)
- [A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimization](https://mlsanity.com/paper/2405.10815/) (2024)
- [Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits](https://mlsanity.com/paper/2306.14872/) (2023)
- [Achieving Constant Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2404.10745/) (2024)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [On the Complexity of Representation Learning in Contextual Linear Bandits](https://mlsanity.com/paper/2212.09429/) (2022)
- [Provable and Practical In-Context Policy Optimization for Self-Improvement](https://mlsanity.com/paper/2603.01335/) (2026)
- [Sequential Estimation under Multiple Resources: a Bandit Point of View](https://mlsanity.com/paper/2109.14703/) (2021)
- [Truncated LinUCB for Stochastic Linear Bandits](https://mlsanity.com/paper/2202.11735/) (2022)
- [Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach](https://mlsanity.com/paper/2312.12731/) (2023)
- [ε-Policy Gradient for Online Pricing](https://mlsanity.com/paper/2405.03624/) (2024)

## Abstract (arXiv)

Contextual bandits serve as a fundamental model for many sequential decision making tasks. The most popular theoretically justified approaches are based on the optimism principle. While these algorithms can be practical, they are known to be suboptimal asymptotically. On the other hand, existing asymptotically optimal algorithms for this problem do not exploit the linear structure in an optimal way and suffer from lower-order terms that dominate the regret in all practically interesting regimes. We start to bridge the gap by designing an algorithm that is asymptotically optimal and has good finite-time empirical performance. At the same time, we make connections to the recent literature on when exploration-free methods are effective. Indeed, if the distribution of contexts is well behaved, then our algorithm acts mostly greedily and enjoys sub-logarithmic regret. Furthermore, our approach is adaptive in the sense that it automatically detects the nice case. Numerical results demonstrate significant regret reductions by our method relative to several baselines.