Robust Lipschitz Bandits to Adversarial Corruptions
This work addresses robustness in continuous bandit problems for applications like online learning and recommendation systems, but it is incremental as it extends existing Lipschitz bandit frameworks to adversarial settings.
The paper tackles the problem of Lipschitz bandits with adversarial corruptions, where an adversary corrupts stochastic rewards up to a total budget C, and presents the first robust algorithms that achieve sub-linear regret under both weak and strong adversaries, with optimality shown in the strong case.
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.