Stochastic Linear Optimization with Adversarial Corruption

Abstract

We extend the model of stochastic bandits with adversarial corruption (Lykouriset al., 2018) to the stochastic linear optimization problem (Dani et al., 2008). Our algorithm is agnostic to the amount of corruption chosen by the adaptive adversary. The regret of the algorithm only increases linearly in the amount of corruption. Our algorithm involves using Löwner-John's ellipsoid for exploration and dividing time horizon into epochs with exponentially increasing size to limit the influence of corruption.

References in corpus (4)

• Contextual Bandit Algorithms with Supervised Learning Guarantees
• The best of both worlds: stochastic and adversarial bandits
• Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits

Cited by in corpus (14)

• Adversarial Attacks on Linear Contextual Bandits
• Corruption-robust exploration in episodic reinforcement learning
• Corruption-Tolerant Gaussian Process Bandit Optimization
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization
• Stochastic Linear Bandits Robust to Adversarial Attacks
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Improved Corruption Robust Algorithms for Episodic Reinforcement Learning
• Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks
• Linear Contextual Bandits with Adversarial Corruptions
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
• On Optimal Robustness to Adversarial Corruption in Online Decision Problems
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Bias-Robust Bayesian Optimization via Dueling Bandits