# Follow the Perturbed Leader: Optimism and Fast Parallel Algorithms for Smooth Minimax Games

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Jun 2020.

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

- [Training for the Future: A Simple Gradient Interpolation Loss to Generalize Along Time](https://mlsanity.com/paper/2108.06721/) (2021)
- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [An Improved Relaxation for Oracle-Efficient Adversarial Contextual Bandits](https://mlsanity.com/paper/2310.19025/) (2023)
- [Some performance considerations when using multi-armed bandit algorithms in the presence of missing data](https://mlsanity.com/paper/2205.03820/) (2022)
- [QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewriting](https://mlsanity.com/paper/2508.16697/) (2025)
- [Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality](https://mlsanity.com/paper/2510.12152/) (2025)
- [Towards Optimal Randomized Strategies in Adversarial Example Game](https://mlsanity.com/paper/2306.16738/) (2023)
- [Optimistic Learning for Communication Networks](https://mlsanity.com/paper/2504.03499/) (2025)
- [No One Size Fits All: QueryBandits for Hallucination Mitigation](https://mlsanity.com/paper/2602.20332/) (2026)

## Abstract (arXiv)

We consider the problem of online learning and its application to solving minimax games. For the online learning problem, Follow the Perturbed Leader (FTPL) is a widely studied algorithm which enjoys the optimal O(T1/2) worst-case regret guarantee for both convex and nonconvex losses. In this work, we show that when the sequence of loss functions is predictable, a simple modification of FTPL which incorporates optimism can achieve better regret guarantees, while retaining the optimal worst-case regret guarantee for unpredictable sequences. A key challenge in obtaining these tighter regret bounds is the stochasticity and optimism in the algorithm, which requires different analysis techniques than those commonly used in the analysis of FTPL. The key ingredient we utilize in our analysis is the dual view of perturbation as regularization. While our algorithm has several applications, we consider the specific application of minimax games. For solving smooth convex-concave games, our algorithm only requires access to a linear optimization oracle. For Lipschitz and smooth nonconvex-nonconcave games, our algorithm requires access to an optimization oracle which computes the perturbed best response. In both these settings, our algorithm solves the game up to an accuracy of O(T-1/2) using T calls to the optimization oracle. An important feature of our algorithm is that it is highly parallelizable and requires only O(T1/2) iterations, with each iteration making O(T1/2) parallel calls to the optimization oracle.