Stochastic Linear Bandits Robust to Adversarial Attacks

Over the past years, bandit algorithms have found application in computational advertising, recommender systems, clinical trials, and many more. These algorithms make online decisions by balancing between exploiting previously high-reward actions vs. exploring less known ones that could potentially lead to higher rewards. Bandit problems can roughly be categorized [17] into stochastic bandits, in which subsequently played actions yield independent rewards, and adversarial bandits, where the rewards are chosen by an adversary, possibly subject to constraints. A recent line of works has sought to reap the benefits of both approaches by studying bandit problems that are stochastic in nature, but with rewards subject to a limited amount of adversarial corruption. Various works have developed provably robust algorithms [4, 11, 20, 23], and attacks have been designed that cause standard algorithms to fail [9, 11, 12, 21]. While near-optimal theoretical guarantees have been established in the case of independent arms [11], more general settings remain relatively poorly understood or even entirely unexplored; see Section 1.2 for details. Our primary goal is to bridge these gaps via a detailed study of stochastic linear bandits with adversarial corruptions. In the case of a fixed finite (but possibly very large) set of arms, we develop an elimination-based robust algorithm and provide regret bounds with a near-optimal joint dependence on the time horizon and the adversarial attack budget, demonstrating distinct behavior depending on whether the attack budget is known or unknown. In addition, we introduce a novel contextual linear bandit setting under adversarial corruptions, and show that under a context diversity assumption, a simple greedy algorithm attains near-optimal regret under adversarial corruptions, despite having no built-in mechanism that explicitly encourages exploration or robustness.