Robust Lipschitz Bandits to Adversarial Corruptions
Robust Lipschitz Bandits to Adversarial Corruptions
复制标题
DOI：
10.48550/arxiv.2305.18543
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Yue Kang;Cho-Jui Hsieh;T. C. Lee
中科院分区：
文献类型：
--
作者：
Yue Kang;Cho-Jui Hsieh;T. C. Lee
Lipschitz bandits是随机bandits的一种变体，它处理定义在度量空间上的连续臂集，其中奖励函数受到Lipschitz约束。在本文中，我们引入了一个新的问题，Lipschitz土匪在对抗腐败的存在下，自适应对手腐败的随机奖励的总预算$C$。预算是通过整个时间范围内的腐败程度之和来衡量的。我们认为弱和强的对手，弱对手是不知道当前的行动之前的攻击，而强大的可以观察到it. We的工作提出了第一行强大的Lipschitz强盗算法，可以实现次线性遗憾下两种类型的对手，即使腐败的总预算$C$是未透露的代理。我们提供了一个下界下的每种类型的对手，并表明我们的算法是最佳的情况下，强。最后，我们进行实验来说明我们的算法对两种经典的攻击的有效性。
Lipschitz bandit is a variant of stochastic bandits that deals with a continuous arm set defined on a metric space, where the reward function is subject to a Lipschitz constraint. In this paper, we introduce a new problem of Lipschitz bandits in the presence of adversarial corruptions where an adaptive adversary corrupts the stochastic rewards up to a total budget $C$. The budget is measured by the sum of corruption levels across the time horizon $T$. We consider both weak and strong adversaries, where the weak adversary is unaware of the current action before the attack, while the strong one can observe it. Our work presents the first line of robust Lipschitz bandit algorithms that can achieve sub-linear regret under both types of adversary, even when the total budget of corruption $C$ is unrevealed to the agent. We provide a lower bound under each type of adversary, and show that our algorithm is optimal under the strong case. Finally, we conduct experiments to illustrate the effectiveness of our algorithms against two classic kinds of attacks.