提出高效算法SAMBA，在坏数据干扰下仍能最优地选择最佳选项。
Efficient and Optimal Policy Gradient Algorithm for Corrupted Multi-armed Bandits
- 用策略梯度方法处理被恶意篡改的多臂老虎机问题。
- 理论证明其误差上限比现有最优算法少一个log T因子。
- 适合关注鲁棒性与效率的强化学习研究者使用。
本文研究对抗性干扰下的随机多臂老虎机问题，即对手部分篡改各选项的奖励以误导算法。我们引入策略梯度算法SAMBA，证明其计算高效，并达到当前最优的上界 $O(K\log T/Δ) + O(C/Δ)$，其中 $K$ 为臂的数量，$C$ 为未知的干扰程度，$Δ$ 为最优臂与其他臂间的最小期望奖励差距，$T$ 为时间范围。相比现有最高效的算法（如CBARBAR）的 $O(K\log^2 T/Δ) + O(C)$，SAMBA在保持干扰项线性于 $C$ 的同时，将第一项中的 $\log^2 T$ 降低为 $\log T$，实现渐近最优。仿真结果表明SAMBA优于现有基线。
原文摘要 · Abstract (English)
In this paper, we consider the stochastic multi-armed bandits problem with adversarial corruptions, where the random rewards of the arms are partially modified by an adversary to fool the algorithm. We apply the policy gradient algorithm SAMBA to this setting, and show that it is computationally efficient, and achieves a state-of-the-art $O(K\log T/Δ) + O(C/Δ)$ regret upper bound, where $K$ is the number of arms, $C$ is the unknown corruption level, $Δ$ is the minimum expected reward gap between the best arm and other ones, and $T$ is the time horizon. Compared with the best existing efficient algorithm (e.g., CBARBAR), whose regret upper bound is $O(K\log^2 T/Δ) + O(C)$, we show that SAMBA reduces one $\log T$ factor in the regret bound, while maintaining the corruption-dependent term to be linear with $C$. This is indeed asymptotically optimal. We also conduct simulations to demonstrate the effectiveness of SAMBA, and the results show that SAMBA outperforms existing baselines.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。