改进了组合半竞争性问题中FTPL算法的性能与效率。
Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems
- 引入几何重采样与条件几何重采样提升算法稳定性。
- 在弗雷切特分布下实现$O( extstyle oot floor{m^2 d^{1/α}T} + oot floor{mdT})$的误差界。
- 计算复杂度从$O(d^2)$降至$O(md( ext{log}(d/m)+1))$，适合大规模场景。
本文研究了组合半竞争性问题中跟随扰动领袖（FTPL）策略的最优性与复杂度。尽管本田等人（2023）和李等人（2024）证明了在标准多臂赌博机问题中，当收益服从弗雷切特型分布时，FTPL可实现最佳双世界（BOBW）最优性，但在组合半竞争性问题中的最优性仍不明确。本文考虑在大小不变的半竞争性设置下，使用几何重采样（GR）的FTPL策略，证明其在弗雷切特分布下达到$Oig( oot floor{m^2 d^{1/α}T} + oot floor{mdT}ig)$的后悔界，并在对抗性设置下对帕累托分布实现最优的$Oig( oot floor{mdT}ig)$后悔界。此外，将条件几何重采样（CGR）扩展至大小不变的半竞争性设置，将计算复杂度从原始的$O(d^2)$降低至$Oig(md( ext{log}(d/m)+1)ig)$，且未牺牲FTPL的后悔性能。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。