# 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

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 64 references that are in the map.
- First posted on arXiv 30 May 2024.

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

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (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)
- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Follow the Leader If You Can, Hedge If You Must](https://mlsanity.com/paper/1301.0534/) (2013)
- [Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously](https://mlsanity.com/paper/1901.08779/) (2019)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [An Information-Theoretic Approach to Minimax Regret in Partial Monitoring](https://mlsanity.com/paper/1902.00470/) (2019)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Bandits with Switching Costs: T^{2/3} Regret](https://mlsanity.com/paper/1310.2997/) (2013)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [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)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [Efficient Online Portfolio with Logarithmic Regret](https://mlsanity.com/paper/1805.07430/) (2018)
- [Best-of-Both-Worlds Algorithms for Partial Monitoring](https://mlsanity.com/paper/2207.14550/) (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)
- [A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00557/) (2022)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [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)
- [Understanding Bandits with Graph Feedback](https://mlsanity.com/paper/2105.14260/) (2021)
- [Best of Both Worlds Model Selection](https://mlsanity.com/paper/2206.14912/) (2022)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring](https://mlsanity.com/paper/1509.09011/) (2015)
- [Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case](https://mlsanity.com/paper/1511.08405/) (2015)

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

- [Reinforcement Learning from Adversarial Preferences in Tabular MDPs](https://mlsanity.com/paper/2507.11706/) (2025)
- [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 a powerful framework for various online learning problems. By designing its regularizer and learning rate to be adaptive to past observations, FTRL is known to work adaptively to various properties of an underlying environment. However, most existing adaptive learning rates are for online learning problems with a minimax regret of Theta(√T) for the number of rounds T, and there are only a few studies on adaptive learning rates for problems with a minimax regret of Theta(T2/3), which include several important problems dealing with indirect feedback. To address this limitation, we establish a new adaptive learning rate framework for problems with a minimax regret of Theta(T2/3). Our learning rate is designed by matching the stability, penalty, and bias terms that naturally appear in regret upper bounds for problems with a minimax regret of Theta(T2/3). As applications of this framework, we consider three major problems with a minimax regret of Theta(T2/3): partial monitoring, graph bandits, and multi-armed bandits with paid observations. We show that FTRL with our learning rate and the Tsallis entropy regularizer improves existing Best-of-Both-Worlds (BOBW) regret upper bounds, which achieve simultaneous optimality in the stochastic and adversarial regimes. The resulting learning rate is surprisingly simple compared to the existing learning rates for BOBW algorithms for problems with a minimax regret of Theta(T2/3).