On Optimal Robustness to Adversarial Corruption in Online Decision Problems

Abstract

This paper considers two fundamental sequential decision-making problems: the problem of prediction with expert advice and the multi-armed bandit problem. We focus on stochastic regimes in which an adversary may corrupt losses, and we investigate what level of robustness can be achieved against adversarial corruptions. The main contribution of this paper is to show that optimal robustness can be expressed by a square-root dependency on the amount of corruption. More precisely, we show that two classes of algorithms, anytime Hedge with decreasing learning rate and algorithms with second-order regret bounds, achieve $O(\frac{\log N}{\Delta }+\sqrt{\frac{C\log N}{\Delta }})$-regret, where $N,\Delta$, and $C$ represent the number of experts, the gap parameter, and the corruption level, respectively. We further provide a matching lower bound, which means that this regret bound is tight up to a constant factor. For the multi-armed bandit problem, we also provide a nearly tight lower bound up to a logarithmic factor.

References in corpus (10)

• The best of both worlds: stochastic and adversarial bandits
• More Adaptive Algorithms for Adversarial Bandits
• Adversarial Attacks on Stochastic Bandits
• Data Poisoning Attacks on Stochastic Bandits
• Stochastic Linear Optimization with Adversarial Corruption
• Following the Leader and Fast Rates in Linear Prediction: Curved Constraint Sets and Other Regularities
• On the optimality of the Hedge algorithm in the stochastic regime
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Prediction with Corrupted Expert Advice
• Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions