mlsanityData to 14 Oct 2026

Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits

arXiv 2309.00814 ↗First posted 2 Sep 2023cs.LG cs.AI stat.MLcited by 19

Not on the map. Why?

Abstract (arXiv)

We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from a fixed distribution. Existing methods for this problem either require access to a simulator to generate free i.i.d. contexts, achieve a sub-optimal regret no better than widetildeO(T^frac56), or are computationally inefficient. We greatly improve these results by achieving a regret of widetildeO(√T) without a simulator, while maintaining computational efficiency when the action set in each round is small. In the special case of sleeping bandits with adversarial loss and stochastic arm availability, our result answers affirmatively the open question by Saha et al. [2020] on whether there exists a polynomial-time algorithm with poly(d)√T regret. Our approach naturally handles the case where the loss is linear up to an additive misspecification error, and our regret shows near-optimal dependence on the magnitude of the error.

Key facts. Cited by 19 papers in the map (data through 14 Oct 2026). Builds on 38 of its 67 references that are in the map. First posted on arXiv 2 Sep 2023.

Builds on

38 of 67 references.

References · 38

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  2. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  3. 2020Bypassing the Monster: A Faster and Simpler Optimal Algorithm for Contextual Bandits under Realizabilitycited by 115
  4. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  5. 2016Corralling a Band of Bandit Algorithmscited by 100
  6. 2018Practical Contextual Bandits with Regression Oraclescited by 93
  7. 2021Adapting to Misspecification in Contextual Banditscited by 81
  8. 2020Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspectivecited by 78
  9. 2019A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-freecited by 71
  10. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 66
  11. 2017Efficient Contextual Bandits in Non-stationary Worldscited by 62
  12. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
26 more
  1. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  2. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  3. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  4. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  5. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 43
  6. 2020Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Banditscited by 40
  7. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  8. 2015The Computational Power of Optimization in Online Learningcited by 39
  9. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  10. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  11. 2020Online learning in MDPs with linear function approximation and bandit feedbackcited by 30
  12. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  13. 2022Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Banditscited by 22
  14. 2016BISTRO: An Efficient Relaxation-Based Method for Contextual Banditscited by 20
  15. 2021Understanding the Eluder Dimensioncited by 19
  16. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  17. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 19
  18. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  19. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 17
  20. 2023Best of Both Worlds Policy Optimizationcited by 17
  21. 2022Pushing the Efficiency-Regret Pareto Frontier for Online Learning of Portfolios and Quantum Statescited by 15
  22. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 15
  23. 2016Improved Regret Bounds for Oracle-Based Adversarial Contextual Banditscited by 13
  24. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  25. 2020Improved Sleeping Bandits with Stochastic Actions Sets and Adversarial Rewardscited by 12
  26. 2020Adversarial Online Learning with Changing Action Sets: Efficient Algorithms with Approximate Regret Boundscited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 5; 2025: 3; 2026: 7.

19 papers.

Sort:

By area:

  1. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 13
  2. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  3. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  4. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  5. 2025Nearly-Optimal Bandit Learning in Stackelberg Games with Side Informationcited by 6
  6. 2024Strategic Linear Contextual Banditscited by 5
  7. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  8. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 4
  9. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  10. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  11. 2024Indexed Minimum Empirical Divergence-Based Algorithms for Linear Banditscited by 2
  12. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
7 more
  1. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  2. 2026Mixing Makes Markovian Contexts Cheap for Linear Banditscited by 0
  3. 2026Calibration-Gated LLM Pseudo-Observations for Online Contextual Banditscited by 0
  4. 2026Near-Optimal Regret in Adversarial Kernel Banditscited by 0
  5. 2026Set Membership Estimation for Stochastic Linear Contextual Banditscited by 0
  6. 2026Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Banditscited by 0
  7. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0