提出新框架BARBAT，让带对抗干扰的随机博弈更高效且接近最优。
A Near-optimal, Scalable and Parallelizable Framework for Stochastic Bandits Robust to Adversarial Corruptions and Beyond
- 设计新算法框架BARBAT，消除原方法中与臂数量相关的冗余开销
- 实现近似最优的后悔值，达到Ω(C)下界，比之前方法提升显著
- 适合多智能体、批量处理等场景，计算更轻量，易于并行
本文研究存在对抗性干扰的各类随机博弈问题。经典算法BARBAR虽具鲁棒性与效率，但其后悔值为O(KC)，未达Ω(C)的理论下界，其中K为臂的数量，C为干扰水平。本文提出新框架BARBAT，通过消除K因子，实现近乎最优的后悔界（仅差对数因子）。该框架可扩展至多智能体、图结构、组合半-博弈及批量博弈等场景。相比基于正则化追随领袖（FTRL）的方法，本方法更易并行，尤其在半-博弈中计算成本更低。数值实验验证了其高效性。
原文摘要 · Abstract (English)
We investigate various stochastic bandit problems in the presence of adversarial corruptions. A seminal work for this problem is the BARBAR~\cite{gupta2019better} algorithm, which achieves both robustness and efficiency. However, it suffers from a regret of $O(KC)$, which does not match the lower bound of $Ω(C)$, where $K$ denotes the number of arms and $C$ denotes the corruption level. In this paper, we first improve the BARBAR algorithm by proposing a novel framework called BARBAT, which eliminates the factor of $K$ to achieve an optimal regret bound up to a logarithmic factor. We also extend BARBAT to various settings, including multi-agent bandits, graph bandits, combinatorial semi-bandits and batched bandits. Compared with the Follow-the-Regularized-Leader framework, our methods are more amenable to parallelization, making them suitable for multi-agent and batched bandit settings, and they incur lower computational costs, particularly in semi-bandit problems. Numerical experiments verify the efficiency of the proposed methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。