# Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 22 references that are in the map.
- First posted on arXiv 14 Jun 2025.

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

- [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)
- [Thompson Sampling for Combinatorial Semi-Bandits](https://mlsanity.com/paper/1803.04623/) (2018)
- [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)
- [Matroid Bandits: Fast Combinatorial Optimization with Learning](https://mlsanity.com/paper/1403.5045/) (2014)
- [First-order regret bounds for combinatorial semi-bandits](https://mlsanity.com/paper/1502.06354/) (2015)
- [Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits](https://mlsanity.com/paper/1503.05087/) (2015)
- [Online Joint Bid/Daily Budget Optimization of Internet Advertising Campaigns](https://mlsanity.com/paper/2003.01452/) (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)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)

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

- [A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for m-Set Semi-Bandit Problem](https://mlsanity.com/paper/2603.11764/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## Abstract (arXiv)

This paper studies the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) policy in size-invariant combinatorial semi-bandit problems. Recently, Honda et al. (2023) and Lee et al. (2024) showed that FTPL achieves Best-of-Both-Worlds (BOBW) optimality in standard multi-armed bandit problems with Fr'echet-type distributions. However, the optimality of FTPL in combinatorial semi-bandit problems remains unclear. In this paper, we consider the regret bound of FTPL with geometric resampling (GR) in size-invariant semi-bandit setting, showing that FTPL respectively achieves Oleft(√m2 d^frac1αT+√mdTright) regret with Fr'echet distributions, and the best possible regret bound of Oleft(√mdTright) with Pareto distributions in adversarial setting. Furthermore, we extend the conditional geometric resampling (CGR) to size-invariant semi-bandit setting, which reduces the computational complexity from O(d2) of original GR to Oleft(mdleft(log(d/m)+1right)right) without sacrificing the regret performance of FTPL.