mlsanityData to 14 Oct 2026

Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm

arXiv 2303.06825 ↗First posted 13 Mar 2023cs.LG stat.MLcited by 12

Not on the map. Why?

Abstract (arXiv)

The linear bandit problem has been studied for many years in both stochastic and adversarial settings. Designing an algorithm that can optimize the environment without knowing the loss type attracts lots of interest. citetLeeLWZ021 propose an algorithm that actively detects the loss type and then switches between different algorithms specially designed for specific settings. However, such an approach requires meticulous designs to perform well in all environments. Follow-the-regularized-leader (FTRL) is another type of popular algorithm that can adapt to different environments. This algorithm is of simple design and the regret bounds are shown to be optimal in traditional multi-armed bandit problems compared with the detect-switch type. Designing an FTRL-type algorithm for linear bandits is an important question that has been open for a long time. In this paper, we prove that the FTRL algorithm with a negative entropy regularizer can achieve the best-of-three-world results for the linear bandit problem. Our regret bounds achieve the same or nearly the same order as the previous detect-switch type algorithm but with a much simpler algorithmic design.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 24 of its 44 references that are in the map. First posted on arXiv 13 Mar 2023.

Builds on

24 of 44 references.

References · 24

  1. 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
  2. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  3. 2014A Second-order Bound with Excess Lossescited by 95
  4. 2013Follow the Leader If You Can, Hedge If You Mustcited by 70
  5. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  6. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  7. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  8. 2016The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Banditscited by 49
  9. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  10. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  11. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  12. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
12 more
  1. 2021The best of both worlds: stochastic and adversarial episodic MDPs with unknown transitioncited by 40
  2. 2018On the optimality of the Hedge algorithm in the stochastic regimecited by 33
  3. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  4. 2022Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphscited by 26
  5. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 24
  6. 2021On Optimal Robustness to Adversarial Corruption in Online Decision Problemscited by 21
  7. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  8. 2022Best-of-Both-Worlds Algorithms for Partial Monitoringcited by 19
  9. 2022A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphscited by 17
  10. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 14
  11. 2022Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedbackcited by 6
  12. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2

Built on by

Cited by year (2026 to 14 Oct)

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

12 papers.

  1. 2023Online Clustering of Bandits with Misspecified User Modelscited by 12
  2. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 11
  3. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  4. 2024uniINF: Best-of-Both-Worlds Algorithm for Parameter-Free Heavy-Tailed MABscited by 8
  5. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 7
  6. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  7. 2023Online Corrupted User Detection and Regret Minimizationcited by 3
  8. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  9. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  10. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  11. 2025Last-Iterate Analyses of FTRL with the 1/2-Tsallis Entropy in Stochastic Banditscited by 1
  12. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0