提出新型扰动策略，让半盲博弈算法在对抗与随机场景下都表现优异。
Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems
- 用弗雷歇扰动改进FTPL，无需每步优化即可选最优组合
- 对抗场景下达到近优后悔界，随机场景下实现对数级后悔
- 适合追求稳定性能的在线决策研究者
我们研究组合半盲问题中的m-集半盲场景，即从d个动作中精确选择m个。在对抗设置下，已有最优后悔界为O(√(nmd))，由著名的正则化追随领先者（FTRL）策略实现，但其需在每步求解优化问题并采样。而追随扰动领先者（FTPL）通过给损失估计加随机扰动，直接选取扰动后排名前m的臂，避免了优化开销。本文证明，采用弗雷歇扰动的FTPL在对抗设置下可实现近优后悔界O(√(nm)(√(d log d) + m^(5/6)))，且在随机设置下接近对数后悔，达到“双场景最优”效果。我们的下界表明，当前额外因子无法避免；任何改进都需要根本性新方法。
原文摘要 · Abstract (English)
We consider a common case of the combinatorial semi-bandit problem, the $m$-set semi-bandit, where the learner exactly selects $m$ arms from the total $d$ arms. In the adversarial setting, the best regret bound, known to be $\mathcal{O}(\sqrt{nmd})$ for time horizon $n$, is achieved by the well-known Follow-the-Regularized-Leader (FTRL) policy. However, this requires to explicitly compute the arm-selection probabilities via optimizing problems at each time step and sample according to them. This problem can be avoided by the Follow-the-Perturbed-Leader (FTPL) policy, which simply pulls the $m$ arms that rank among the $m$ smallest (estimated) loss with random perturbation. In this paper, we show that FTPL with a Fréchet perturbation also enjoys the near optimal regret bound $\mathcal{O}(\sqrt{nm}(\sqrt{d\log(d)}+m^{5/6}))$ in the adversarial setting and approaches best-of-both-world regret bounds, i.e., achieves a logarithmic regret for the stochastic setting. Moreover, our lower bounds show that the extra factors are unavoidable with our approach; any improvement would require a fundamentally different and more challenging method.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。