# Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds

arXiv: https://arxiv.org/abs/2403.00715 · HTML: https://mlsanity.com/paper/2403.00715/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 50 references that are in the map.
- First posted on arXiv 1 Mar 2024.

## Builds on (most cited first, 30 of 30)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Coin Betting and Parameter-Free Online Learning](https://mlsanity.com/paper/1602.04128/) (2016)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [More Adaptive Algorithms for Adversarial Bandits](https://mlsanity.com/paper/1801.03265/) (2018)
- [A Second-order Bound with Excess Losses](https://mlsanity.com/paper/1402.2044/) (2014)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback](https://mlsanity.com/paper/1409.8428/) (2014)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transition](https://mlsanity.com/paper/2006.05606/) (2020)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [An Optimal Algorithm for Adversarial Bandits with Arbitrary Delays](https://mlsanity.com/paper/1910.06054/) (2019)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Scale-Free Algorithms for Online Linear Optimization](https://mlsanity.com/paper/1502.05744/) (2015)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Connections Between Mirror Descent, Thompson Sampling and the Information Ratio](https://mlsanity.com/paper/1905.11817/) (2019)
- [A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedback](https://mlsanity.com/paper/2206.14906/) (2022)
- [An Algorithm for Stochastic and Adversarial Bandits with Switching Costs](https://mlsanity.com/paper/2102.09864/) (2021)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (2022)
- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Bandits](https://mlsanity.com/paper/2201.11921/) (2022)
- [Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms](https://mlsanity.com/paper/2302.13534/) (2023)
- [Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2103.12487/) (2021)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [Better Best of Both Worlds Bounds for Bandits with Switching Costs](https://mlsanity.com/paper/2206.03098/) (2022)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case](https://mlsanity.com/paper/1511.08405/) (2015)
- [On the Minimax Regret for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2305.15383/) (2023)

## Built on by (most cited first, 11 of 11)

- [Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret](https://mlsanity.com/paper/2602.06348/) (2026)
- [A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worlds](https://mlsanity.com/paper/2405.20028/) (2024)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)
- [How to Set β1, β2 in Adam: An Online Learning Perspective](https://mlsanity.com/paper/2510.03478/) (2025)
- [Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2510.17103/) (2025)
- [Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality](https://mlsanity.com/paper/2510.12152/) (2025)
- [Best-of-Both-Worlds for Heavy-Tailed Markov Decision Processes](https://mlsanity.com/paper/2602.01295/) (2026)
- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)

## Abstract (arXiv)

Follow-The-Regularized-Leader (FTRL) is known as an effective and versatile approach in online learning, where appropriate choice of the learning rate is crucial for smaller regret. To this end, we formulate the problem of adjusting FTRL's learning rate as a sequential decision-making problem and introduce the framework of competitive analysis. We establish a lower bound for the competitive ratio and propose update rules for learning rate that achieves an upper bound within a constant factor of this lower bound. Specifically, we illustrate that the optimal competitive ratio is characterized by the (approximate) monotonicity of components of the penalty term, showing that a constant competitive ratio is achievable if the components of the penalty term form a monotonically non-increasing sequence, and derive a tight competitive ratio when penalty terms are xi-approximately monotone non-increasing. Our proposed update rule, referred to as textitstability-penalty matching, also facilitates constructing the Best-Of-Both-Worlds (BOBW) algorithms for stochastic and adversarial environments. In these environments our result contributes to achieve tighter regret bound and broaden the applicability of algorithms for various settings such as multi-armed bandits, graph bandits, linear bandits, and contextual bandits.