mlsanityData to 14 Oct 2026

Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously

arXiv 2102.05858 ↗First posted 11 Feb 2021cs.LGcited by 48

Not on the map. Why?

Abstract (arXiv)

In this work, we develop linear bandit algorithms that automatically adapt to different environments. By plugging a novel loss estimator into the optimization problem that characterizes the instance-optimal strategy, our first algorithm not only achieves nearly instance-optimal regret in stochastic environments, but also works in corrupted environments with additional regret being the amount of corruption, while the state-of-the-art (Li et al., 2019) achieves neither instance-optimality nor the optimal dependence on the corruption amount. Moreover, by equipping this algorithm with an adversarial component and carefully-designed testings, our second algorithm additionally enjoys minimax-optimal regret in completely adversarial environments, which is the first of this kind to our knowledge. Finally, all our guarantees hold with high probability, while existing instance-optimal guarantees only hold in expectation.

Key facts. Cited by 48 papers in the map (data through 14 Oct 2026). Builds on 21 of its 41 references that are in the map. First posted on arXiv 11 Feb 2021.

Builds on

21 of 41 references.

References · 21

  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  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. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 92
  6. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  7. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  8. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  9. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 51
  10. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 49
  11. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  12. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
9 more
  1. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  2. 2019Adaptive Exploration in Linear Contextual Banditcited by 43
  3. 2017Minimal Exploration in Structured Stochastic Banditscited by 41
  4. 2020An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Banditscited by 26
  5. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  6. 2016Refined Lower Bounds for Adversarial Banditscited by 20
  7. 2020Taking a hint: How to leverage loss predictors in contextual bandits?cited by 20
  8. 2015Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoringcited by 10
  9. 2020Crush Optimism with Pessimism: Structured Bandits Beyond Asymptotic Optimalitycited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 10; 2022: 11; 2023: 12; 2024: 7; 2025: 6; 2026: 2.

48 papers.

Sort:

By area:

  1. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  2. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  3. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  4. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  5. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  6. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  7. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  8. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
  9. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  10. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 21
  11. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  12. 2021Improved Corruption Robust Algorithms for Episodic Reinforcement Learningcited by 20
36 more
  1. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  2. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  3. 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
  4. 2022An Optimization-based Algorithm for Non-stationary Kernel Bandits without Prior Knowledgecited by 17
  5. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  6. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  7. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  8. 2022Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Boundscited by 12
  9. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 12
  10. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  11. 2022Best of Both Worlds Model Selectioncited by 11
  12. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  13. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
  14. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  15. 2023Accelerated Rates between Stochastic and Adversarial Online Convex Optimizationcited by 7
  16. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  17. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  18. 2021Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptionscited by 5
  19. 2024Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learningcited by 5
  20. 2021Best-of-All-Worlds Bounds for Online Learning with Feedback Graphscited by 4
  21. 2023Near-Optimal Adversarial Reinforcement Learning with Switching Costscited by 4
  22. 2023Robust Causal Bandits for Linear Modelscited by 4
  23. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  24. 2021Corruption Robust Active Learningcited by 3
  25. 2025Parameter-free Algorithms for the Stochastically Extended Adversarial Modelcited by 3
  26. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  27. 2023A/B Testing and Best-arm Identification for Linear Bandits with Robustness to Non-stationaritycited by 2
  28. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  29. 2024Improved Bound for Robust Causal Bandits with Linear Modelscited by 2
  30. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  31. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  32. 2025Achieving adaptivity and optimality for multi-armed bandits using Exponential-Kullback Leibler Maillard Samplingcited by 1
  33. 2026Nearly-Optimal Algorithm for Adversarial Kernelized Banditscited by 1
  34. 2025Robust In-Context Reinforcement Learning Under Reward Poisoning Attackscited by 0
  35. 2025Multi-Play Combinatorial Semi-Bandit Problemcited by 0
  36. 2026Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectivescited by 0