# A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for m-Set Semi-Bandit Problem

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Mar 2026.

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

- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (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 m-set semi-bandit problems. FTPL has been studied extensively as a promising candidate of an efficient algorithm with favorable regret for adversarial combinatorial semi-bandits. Nevertheless, the optimality of FTPL has still been unknown unlike Follow-the-Regularized-Leader (FTRL) whose optimality has been proved for various tasks of online learning. In this paper, we extend the analysis of FTPL with geometric resampling (GR) to m-set semi-bandits, which is a special case of combinatorial semi-bandits, showing that FTPL with Fr'echet and Pareto distributions with certain parameters achieves the best possible regret of O(√mdT) in adversarial setting. We also show that FTPL with Fr'echet and Pareto distributions with a certain parameter achieves a logarithmic regret for stochastic setting, meaning the Best-of-Both-Worlds optimality of FTPL for m-set semi-bandit problems. Furthermore, we extend the conditional geometric resampling to m-set semi-bandits for efficient loss estimation in FTPL, reducing the computational complexity from O(d2) of the original geometric resampling to O(md(log(d/m)+1)) without sacrificing the regret performance.