# Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 41 references that are in the map.
- First posted on arXiv 14 Oct 2025.

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

- [Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Survey](https://mlsanity.com/paper/2009.13303/) (2020)
- [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)
- [Fighting Bandits with a New Kind of Smoothness](https://mlsanity.com/paper/1512.04152/) (2015)
- [On Explore-Then-Commit Strategies](https://mlsanity.com/paper/1605.08988/) (2016)
- [Multi-armed Bandits with Application to 5G Small Cells](https://mlsanity.com/paper/1510.00627/) (2015)
- [A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit](https://mlsanity.com/paper/1510.00757/) (2015)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [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)
- [Low-Rank Bandit Methods for High-Dimensional Dynamic Pricing](https://mlsanity.com/paper/1801.10242/) (2018)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worlds](https://mlsanity.com/paper/2305.17301/) (2023)
- [On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems](https://mlsanity.com/paper/1902.00610/) (2019)
- [Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.00715/) (2024)
- [Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games](https://mlsanity.com/paper/2006.07541/) (2020)
- [Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worlds](https://mlsanity.com/paper/2403.05134/) (2024)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [Optimization of Epsilon-Greedy Exploration](https://mlsanity.com/paper/2506.03324/) (2025)

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

- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)

## Abstract (arXiv)

We study the decoupled multi-armed bandit problem, where the learner separately selects one arm for exploration and one, possibly different, arm for exploitation at each round. In this setting, the loss of the explored arm is observed but not incurred, whereas the loss of the exploited arm is incurred without being observed. We propose an efficient Follow-the-Perturbed-Leader (FTPL) policy that achieves Best-of-Both-Worlds (BOBW) guarantee with constant regret in the stochastic regime and optimal O(√KT) regret in the adversarial regime. A key feature of our method is that it completely avoids both the convex optimization required by prior BOBW policies and the resampling procedures typically used in FTPL bandit policies. This allows FTPL to fully realize its computational efficiency advantages, leading to substantial reductions in computational cost. We empirically confirm that our policy not only improves the runtime but also demonstrates superior regret performance in both regimes.