Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems
Not on the map. Why?
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.
Key facts. Cited by 1 paper 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
11 of 22 references.
References · 11
- 2018Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Banditscited by 124
- 2018More Adaptive Algorithms for Adversarial Banditscited by 114
- 2018Thompson Sampling for Combinatorial Semi-Banditscited by 78
- 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
- 2015Fighting Bandits with a New Kind of Smoothnesscited by 47
- 2014Matroid Bandits: Fast Combinatorial Optimization with Learningcited by 30
- 2015First-order regret bounds for combinatorial semi-banditscited by 26
- 2015Importance weighting without importance weights: An efficient algorithm for combinatorial semi-banditscited by 16
- 2020Online Joint Bid/Daily Budget Optimization of Internet Advertising Campaignscited by 16
- 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 10
- 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
Built on by
Citing papers per year: 2026: 1.
1 paper.