提出高效算法，同时在对抗和随机场景下达到最优后悔界。
A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$-Set Semi-Bandit Problem
- 用特定分布的扰动领导者策略解决m-集合半贝叶斯问题。
- 对抗场景下后悔界为O(√mdT)，随机场景下为对数级。
- 新方法计算复杂度降至O(md(log(d/m)+1))，适合大规模应用。
本文研究了在m-集合半贝叶斯问题中，扰动领导者（FTPL）策略的最优性与复杂度。尽管FTPL被视为对抗性组合半贝叶斯问题中具有潜力的高效算法，其最优性尚未被证实，而同类方法FTRL已在多种在线学习任务中证明最优。本文将几何重采样（GR）分析扩展至m-集合半贝叶斯问题，表明使用Fréchet与Pareto分布且参数适当时，FTPL可实现对抗环境下最优的后悔界O(√mdT)。同时，在随机设置下，该方法可达到对数级后悔，即实现了“双优”最优性。此外，本文还将条件几何重采样拓展至m-集合半贝叶斯问题，显著降低损失估计的计算复杂度：从原始方法的O(d²)降至O(md(log(d/m)+1))，且不牺牲后悔性能。
原文摘要 · Abstract (English)
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échet and Pareto distributions with certain parameters achieves the best possible regret of $O(\sqrt{mdT})$ in adversarial setting. We also show that FTPL with Fréchet 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(d^2)$ of the original geometric resampling to $O(md(\log(d/m)+1))$ without sacrificing the regret performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。