提出高效解耦强化学习算法，兼顾随机与对抗场景最优表现。
Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality
- 基于扰动领导者策略，无需凸优化或重采样
- 随机环境下常数级后悔，对抗下达最优根号KT后悔
- 计算成本大幅降低，适合实际部署
我们研究解耦多臂赌博机问题，即学习者每轮独立选择一个用于探索的臂和一个用于利用的臂（可不同）。探索臂的损失被观测但不产生，而利用臂的损失产生但不可观测。我们提出一种高效的跟随扰动领导者（FTPL）策略，在随机环境下实现常数后悔，在对抗环境下达到最优 $O(\sqrt{KT})$ 后悔，具备最佳之世界（BOBW）性质。该方法完全避免了先前BOBW策略所需的凸优化以及传统FTPL策略中常见的重采样过程，充分释放了其计算效率优势，显著降低计算开销。实验验证，该策略不仅提升运行速度，还在两种场景下均表现出更优的后悔性能。
原文摘要 · Abstract (English)
We study the decoupled multi-armed bandit problem, where the learner separately selects one arm for exploration and one, possibly different, arm for exploitation at each round. In this setting, the loss of the explored arm is observed but not incurred, whereas the loss of the exploited arm is incurred without being observed. We propose an efficient Follow-the-Perturbed-Leader (FTPL) policy that achieves Best-of-Both-Worlds (BOBW) guarantee with constant regret in the stochastic regime and optimal $O(\sqrt{KT})$ regret in the adversarial regime. A key feature of our method is that it completely avoids both the convex optimization required by prior BOBW policies and the resampling procedures typically used in FTPL bandit policies. This allows FTPL to fully realize its computational efficiency advantages, leading to substantial reductions in computational cost. We empirically confirm that our policy not only improves the runtime but also demonstrates superior regret performance in both regimes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。