mlsanityData to 14 Oct 2026

Best-of-Both-Worlds Algorithms for Linear Contextual Bandits

arXiv 2312.15433 ↗First posted 24 Dec 2023cs.LG stat.MLcited by 11

Not on the map. Why?

Abstract (arXiv)

We study best-of-both-worlds algorithms for K-armed linear contextual bandits. Our algorithms deliver near-optimal regret bounds in both the adversarial and stochastic regimes, without prior knowledge about the environment. In the stochastic regime, we achieve the polylogarithmic rate frac(dK)2polylog(dKT)Deltamin, where Deltamin is the minimum suboptimality gap over the d-dimensional context space. In the adversarial regime, we obtain either the first-order widetildeO(dK√L^*) bound, or the second-order widetildeO(dK√Lambda^*) bound, where L^* is the cumulative loss of the best action and Lambda^* is a notion of the cumulative second moment for the losses incurred by the algorithm. Moreover, we develop an algorithm based on FTRL with Shannon entropy regularizer that does not require the knowledge of the inverse of the covariance matrix, and achieves a polylogarithmic regret in the stochastic regime while obtaining widetildeObig(dK√Tbig) regret bounds in the adversarial regime.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 43 of its 77 references that are in the map. First posted on arXiv 24 Dec 2023.

Builds on

43 of 77 references.

References · 43

  1. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 197
  2. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  3. 2018Stochastic bandits robust to adversarial corruptionscited by 119
  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. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  8. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
  9. 2021Adapting to Misspecification in Contextual Banditscited by 81
  10. 2020Model Selection in Contextual Stochastic Bandit Problemscited by 71
  11. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  12. 2018Adversarial Attacks on Stochastic Banditscited by 57
31 more
  1. 2019Nearly Minimax-Optimal Regret for Linearly Parameterized Banditscited by 54
  2. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  3. 2019Data Poisoning Attacks on Stochastic Banditscited by 53
  4. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  5. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  6. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  7. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  8. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  9. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 43
  10. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  11. 2020Adversarial Attacks on Linear Contextual Banditscited by 34
  12. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  13. 2016Efficient Algorithms for Adversarial Contextual Learningcited by 33
  14. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  15. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  16. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  17. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  18. 2013An efficient algorithm for learning with semi-bandit feedbackcited by 21
  19. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  20. 2016BISTRO: An Efficient Relaxation-Based Method for Contextual Banditscited by 20
  21. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  22. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  23. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 19
  24. 2018Make the Minority Great Again: First-Order Regret Bound for Contextual Banditscited by 17
  25. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  26. 2015Importance weighting without importance weights: An efficient algorithm for combinatorial semi-banditscited by 16
  27. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  28. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  29. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  30. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  31. 2022Best of Both Worlds Model Selectioncited by 11

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 5; 2026: 3.

11 papers.

  1. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  2. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  3. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  4. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  5. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  6. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  7. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  8. 2025An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical Systemcited by 0
  9. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  10. 2026Tighter Regret Bounds for Contextual Action-Set Reinforcement Learningcited by 0
  11. 2026Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairnesscited by 0