Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems
This work addresses the performance and efficiency of FTPL for researchers in bandit algorithms, providing incremental improvements in regret bounds and computational complexity for combinatorial semi-bandit problems.
This paper tackles the optimality and complexity of Follow-the-Perturbed-Leader (FTPL) in combinatorial semi-bandit problems, showing that FTPL achieves regret bounds of O(√(m²d^(1/α)T) + √(mdT)) with Fréchet distributions and O(√(mdT)) with Pareto distributions in adversarial settings, and reduces computational complexity from O(d²) to O(md(log(d/m)+1)) using conditional geometric resampling.
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échet-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 $O\left(\sqrt{m^2 d^\frac{1}αT}+\sqrt{mdT}\right)$ regret with Fréchet distributions, and the best possible regret bound of $O\left(\sqrt{mdT}\right)$ 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(d^2)$ of original GR to $O\left(md\left(\log(d/m)+1\right)\right)$ without sacrificing the regret performance of FTPL.