# Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 55 references that are in the map.
- First posted on arXiv 26 May 2023.

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

- [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)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Tracking the Best Expert in Non-stationary Stochastic Environments](https://mlsanity.com/paper/1712.00578/) (2017)
- [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)
- [Sparsity, variance and curvature in multi-armed bandits](https://mlsanity.com/paper/1711.01037/) (2017)
- [Improved Path-length Regret Bounds for Bandits](https://mlsanity.com/paper/1901.10604/) (2019)
- [Exploration by Optimisation in Partial Monitoring](https://mlsanity.com/paper/1907.05772/) (2019)
- [A Closer Look at Small-loss Bounds for Bandits with Graph Feedback](https://mlsanity.com/paper/2002.00315/) (2020)
- [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)
- [Cleaning up the neighborhood: A full classification for adversarial partial monitoring](https://mlsanity.com/paper/1805.09247/) (2018)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [Regret Lower Bound and Optimal Algorithm in Finite Stochastic Partial Monitoring](https://mlsanity.com/paper/1509.09011/) (2015)
- [Equipping Experts/Bandits with Long-term Memory](https://mlsanity.com/paper/1905.12950/) (2019)
- [Gains and Losses are Fundamentally Different in Regret Minimization: The Sparse Case](https://mlsanity.com/paper/1511.08405/) (2015)
- [Analysis and Design of Thompson Sampling for Stochastic Partial Monitoring](https://mlsanity.com/paper/2006.09668/) (2020)
- [Sparse Stochastic Bandits](https://mlsanity.com/paper/1706.01383/) (2017)

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

- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Muon with Finite Newton-Schulz: The Smoothing Benefit in Nonsmooth Nonconvex Optimization](https://mlsanity.com/paper/2608.26288/) (2026)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Sublogarithmic Swap Regret in Multiplayer General-Sum Games via Hybrid Regularization](https://mlsanity.com/paper/2608.04149/) (2026)
- [Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring](https://mlsanity.com/paper/2402.08321/) (2024)
- [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)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [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)
- [Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring](https://mlsanity.com/paper/2510.19158/) (2025)
- [Stochastic Shortest Path with Sparse Adversarial Costs](https://mlsanity.com/paper/2511.00637/) (2025)
- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)
- [A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond](https://mlsanity.com/paper/2502.07514/) (2025)
- [From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model](https://mlsanity.com/paper/2602.09457/) (2026)

## Abstract (arXiv)

Adaptivity to the difficulties of a problem is a key property in sequential decision-making problems to broaden the applicability of algorithms. Follow-the-regularized-leader (FTRL) has recently emerged as one of the most promising approaches for obtaining various types of adaptivity in bandit problems. Aiming to further generalize this adaptivity, we develop a generic adaptive learning rate, called stability-penalty-adaptive (SPA) learning rate for FTRL. This learning rate yields a regret bound jointly depending on stability and penalty of the algorithm, into which the regret of FTRL is typically decomposed. With this result, we establish several algorithms with three types of adaptivity: sparsity, game-dependency, and best-of-both-worlds (BOBW). Despite the fact that sparsity appears frequently in real problems, existing sparse multi-armed bandit algorithms with k-arms assume that the sparsity level s ≤ k is known in advance, which is often not the case in real-world scenarios. To address this issue, we first establish s-agnostic algorithms with regret bounds of tildeO(√sT) in the adversarial regime for T rounds, which matches the existing lower bound up to a logarithmic factor. Meanwhile, BOBW algorithms aim to achieve a near-optimal regret in both the stochastic and adversarial regimes. Leveraging the SPA learning rate and the technique for s-agnostic algorithms combined with a new analysis to bound the variation in FTRL output in response to changes in a regularizer, we establish the first BOBW algorithm with a sparsity-dependent bound. Additionally, we explore partial monitoring and demonstrate that the proposed SPA learning rate framework allows us to achieve a game-dependent bound and the BOBW simultaneously.