Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems
Not on the map. Why?
Abstract (arXiv)
Follow-the-Regularized-Leader (FTRL) policies have achieved Best-of-Both-Worlds (BOBW) results in various settings through hybrid regularizers, whereas analogous results for Follow-the-Perturbed-Leader (FTPL) remain limited due to inherent analytical challenges. To advance the analytical foundations of FTPL, we revisit classical FTRL-FTPL duality for unbounded perturbations and establish BOBW results for FTPL under a broad family of asymmetric unbounded Fr'echet-type perturbations, including hybrid perturbations combining Gumbel-type and Fr'echet-type tails. These results not only extend the BOBW results of FTPL but also offer new insights into designing alternative FTPL policies competitive with hybrid regularization approaches. Motivated by earlier observations in two-armed bandits, we further investigate the connection between the 1/2-Tsallis entropy and a Fr'echet-type perturbation. Our numerical observations suggest that it corresponds to a symmetric Fr'echet-type perturbation, and based on this, we establish the first BOBW guarantee for symmetric unbounded perturbations in the two-armed setting. In contrast, in general multi-armed bandits, we find an instance in which symmetric Fr'echet-type perturbations violate the key condition for standard BOBW analysis, which is a problem not observed with asymmetric or nonnegative Fr'echet-type perturbations. Although this example does not rule out alternative analyses achieving BOBW results, it suggests the limitations of directly applying the relationship observed in two-armed cases to the general case and thus emphasizes the need for further investigation to fully understand the behavior of FTPL in broader settings.
Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 17 of its 53 references that are in the map. First posted on arXiv 26 Aug 2025.
Builds on
17 of 53 references.
References · 17
- 2019Introduction to Online Convex Optimizationcited by 803
- 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 417
- 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
- 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
- 2015Fighting Bandits with a New Kind of Smoothnesscited by 47
- 2016Oracle-Efficient Online Learning and Auction Designcited by 33
- 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 30
- 2014Online Linear Optimization via Smoothingcited by 24
- 2017Sparsity, variance and curvature in multi-armed banditscited by 24
- 2023Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Armscited by 18
- 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 17
- 2015Importance weighting without importance weights: An efficient algorithm for combinatorial semi-banditscited by 16
5 more
- 2019On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problemscited by 11
- 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
- 2020Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Gamescited by 10
- 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
- 2024Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoringcited by 3
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.