Adversarial Bandits with Corruptions

Lin Yang, Mohammad Hajiesmaili, Sadegh Talebi, John C. S. Lui, Wing Shing WongResearch 2020

Abstract

This paper studies adversarial bandits with corruptions.In the basic adversarial bandit setting, the reward of arms is predetermined by an adversary who is oblivious to the learner's policy.In this paper, we consider an extended setting in which an attacker sits in-between the environment and the learner, and is endowed with a limited budget to corrupt the reward of the selected arm.We have two main results.First, we derive a lower bound on the regret of any bandit algorithm that is aware of the budget of the attacker.Also, for budget-agnostic algorithms, we characterize an impossibility result demonstrating that even when the attacker has a sublinear budget, i.e., a budget growing sublinearly with time horizon T , they fail to achieve a sublinear regret.Second, we propose , a bandit algorithm that incorporates a biased estimator and a robustness parameter to deal with corruption.We characterize the regret of and show that for the case of a known corruption budget, the regret of is tight.
BibTeX
@inproceedings{yang2020adversarial,
  author = {Lin Yang and Mohammad Hajiesmaili and Sadegh Talebi and John C. S. Lui and Wing Shing Wong},
  title = {{Adversarial Bandits with Corruptions}},
  booktitle = {Research},
  year = {2020},
}

Loading related content...

Figure