mlsanityData to 7 Oct 2026

Adaptive Exploration in Linear Contextual Bandit

arXiv 1910.06996 ↗First posted 15 Oct 2019cs.LG math.ST stat.MLcited by 43

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 10; 2023: 6; 2024: 6; 2025: 8; 2026: 5.

43 papers.

Sort:

By area:

  1. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  2. 2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
  3. 2021Leveraging Good Representations in Linear Contextual Banditscited by 29
  4. 2021Fair Exploration via Axiomatic Bargainingcited by 21
  5. 2021Information Directed Sampling for Sparse Linear Banditscited by 20
  6. 2021Reinforcement Learning in Linear MDPs: Constant Regret and Representation Selectioncited by 17
  7. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  8. 2022Instance-optimal PAC Algorithms for Contextual Banditscited by 16
  9. 2021A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPscited by 15
  10. 2025Sequential Learning of the Pareto Front for Multi-objective Banditscited by 13
  11. 2023Federated Linear Contextual Bandits with User-level Differential Privacycited by 12
  12. 2023Linear Partial Monitoring for Sequential Decision-Making: Algorithms, Regret Bounds and Applicationscited by 11
31 more
  1. 2022Exploration in Linear Bandits with Rich Action Sets and its Implications for Inferencecited by 9
  2. 2022Residual Bootstrap Exploration for Stochastic Linear Banditcited by 7
  3. 2022Asymptotic Instance-Optimal Algorithms for Interactive Decision Makingcited by 7
  4. 2024Optimal Batched Linear Banditscited by 7
  5. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  6. 2022Scalable Representation Learning in Linear Contextual Bandits with Constant Regret Guaranteescited by 5
  7. 2022On the Sample Complexity of Representation Learning in Multi-task Bandits with Global and Local structurecited by 5
  8. 2023Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Banditscited by 3
  9. 2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
  10. 2024A Functional Model Method for Nonconvex Nonsmooth Conditional Stochastic Optimizationcited by 3
  11. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  12. 2025Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contextscited by 3
  13. 2022On the Complexity of Representation Learning in Contextual Linear Banditscited by 2
  14. 2021Sequential Estimation under Multiple Resources: a Bandit Point of Viewcited by 1
  15. 2023Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approachcited by 1
  16. 2024ε-Policy Gradient for Online Pricingcited by 1
  17. 2025A Classification View on Meta Learning Banditscited by 1
  18. 2025High-dimensional Nonparametric Contextual Bandit Problemcited by 1
  19. 2026Provable and Practical In-Context Policy Optimization for Self-Improvementcited by 1
  20. 2022Learning Optimal Antenna Tilt Control Policies: A Contextual Linear Bandit Approachcited by 0
  21. 2022Truncated LinUCB for Stochastic Linear Banditscited by 0
  22. 2023Bounded (O(1)) Regret Recommendation Learning via Synthetic Controls Oraclecited by 0
  23. 2024Differentially Private High Dimensional Banditscited by 0
  24. 2025Information maximization for a broad variety of multi-armed bandit gamescited by 0
  25. 2025Sparse Nonparametric Contextual Banditscited by 0
  26. 2025An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical Systemcited by 0
  27. 2025Beyond ATE: Multi-Criteria Design for A/B Testingcited by 0
  28. 2026Mixing Makes Markovian Contexts Cheap for Linear Banditscited by 0
  29. 2026Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversitycited by 0
  30. 2026Adaptive Bandit Algorithms for Contextual Matching Marketscited by 0
  31. 2026Annealed Softmax Greedy in Many-Armed Bayesian Banditscited by 0