On Optimal Robustness to Adversarial Corruption in Online Decision Problems

2021/09/22 by Shinji Ito, Ito, Shinji · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Adversarial system #Artificial intelligence #Binary logarithm #Combinatorics #Computer science #FOS: Computer and information sciences #Logarithm #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematical optimization #Mathematics #Optimization and Search Problems #Regret #Robustness (evolution) #Statistics #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2109.10963

openalex publication_date 2021/09/22 · openalex created_date 2021/09/27 · openalex updated_date 2026/07/28

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( \fraclog NΔ + √ \fracC log N Δ )-regret, where N, Δ, 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.

Citations

• A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
• The Nonstochastic Multiarmed Bandit Problem
• A Second-order Bound with Excess Losses
• The best of both worlds: stochastic and adversarial bandits
• An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits
• Adversarial Attacks on Stochastic Bandits
• Data Poisoning Attacks on Stochastic Bandits
• Stochastic Linear Optimization with Adversarial Corruption
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously

Cited by

• Parameter-free Algorithms for the Stochastically Extended Adversarial Model

Related

• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions
• Stochastic Bandits Robust to Adversarial Attacks
• Stochastic bandits robust to adversarial corruptions
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs