# Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions

arXiv: https://arxiv.org/abs/2205.06811 · HTML: https://mlsanity.com/paper/2205.06811/

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 13 May 2022.

## Builds on (most cited first, 19 of 19)

- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Stochastic bandits robust to adversarial corruptions](https://mlsanity.com/paper/1803.09353/) (2018)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [Better Algorithms for Stochastic Bandits with Adversarial Corruptions](https://mlsanity.com/paper/1902.08647/) (2019)
- [Weighted Linear Bandits for Non-Stationary Environments](https://mlsanity.com/paper/1909.09146/) (2019)
- [Adapting to Misspecification in Contextual Bandits](https://mlsanity.com/paper/2107.05745/) (2021)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Stochastic Linear Bandits Robust to Adversarial Attacks](https://mlsanity.com/paper/2007.03285/) (2020)
- [Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously](https://mlsanity.com/paper/2102.05858/) (2021)
- [An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial bandits](https://mlsanity.com/paper/1605.08722/) (2016)
- [A Model Selection Approach for Corruption Robust Reinforcement Learning](https://mlsanity.com/paper/2110.03580/) (2021)
- [An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1702.06103/) (2017)
- [Misspecified Linear Bandits](https://mlsanity.com/paper/1704.06880/) (2017)
- [Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks](https://mlsanity.com/paper/2106.02978/) (2021)
- [Stochastic Linear Optimization with Adversarial Corruption](https://mlsanity.com/paper/1909.02109/) (2019)
- [Linear Bandits in High Dimension and Recommendation Systems](https://mlsanity.com/paper/1301.1722/) (2013)
- [Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles](https://mlsanity.com/paper/2102.13240/) (2021)
- [Linear Contextual Bandits with Adversarial Corruptions](https://mlsanity.com/paper/2110.12615/) (2021)

## Built on by (most cited first, 30 of 51)

- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Reinforcement Learning from Human Feedback with Active Queries](https://mlsanity.com/paper/2402.09401/) (2024)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes](https://mlsanity.com/paper/2212.05949/) (2022)
- [Corruption-Robust Offline Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2310.14550/) (2023)
- [Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithms](https://mlsanity.com/paper/2211.05632/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Incentivized Learning in Principal-Agent Bandit Games](https://mlsanity.com/paper/2403.03811/) (2024)
- [Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm](https://mlsanity.com/paper/2303.06825/) (2023)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2310.18701/) (2023)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback](https://mlsanity.com/paper/2404.10776/) (2024)
- [How Does Variance Shape the Regret in Contextual Bandits?](https://mlsanity.com/paper/2410.12713/) (2024)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits](https://mlsanity.com/paper/2303.09390/) (2023)
- [Collaborative Linear Bandits with Adversarial Agents: Near-Optimal Regret Bounds](https://mlsanity.com/paper/2206.02834/) (2022)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Provably Efficient Multi-Objective Bandit Algorithms under Preference-Centric Customization](https://mlsanity.com/paper/2502.13457/) (2025)
- [Density-Based Algorithms for Corruption-Robust Contextual Search and Convex Optimization](https://mlsanity.com/paper/2206.07528/) (2022)
- [Near-Optimal Adversarial Reinforcement Learning with Switching Costs](https://mlsanity.com/paper/2302.04374/) (2023)
- [Optimal Sample Selection Through Uncertainty Estimation and Its Application in Deep Learning](https://mlsanity.com/paper/2309.02476/) (2023)
- [Robust Causal Bandits for Linear Models](https://mlsanity.com/paper/2310.19794/) (2023)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [Corruption-Robust Offline Two-Player Zero-Sum Markov Games](https://mlsanity.com/paper/2403.07933/) (2024)
- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Linear Bandits with Partially Observable Features](https://mlsanity.com/paper/2502.06142/) (2025)
- [Online Corrupted User Detection and Regret Minimization](https://mlsanity.com/paper/2310.04768/) (2023)
- [Federated Linear Bandits with Finite Adversarial Actions](https://mlsanity.com/paper/2311.00973/) (2023)

## Abstract (arXiv)

We study the linear contextual bandit problem in the presence of adversarial corruption, where the reward at each round is corrupted by an adversary, and the corruption level (i.e., the sum of corruption magnitudes over the horizon) is C≥ 0. The best-known algorithms in this setting are limited in that they either are computationally inefficient or require a strong assumption on the corruption, or their regret is at least C times worse than the regret without corruption. In this paper, to overcome these limitations, we propose a new algorithm based on the principle of optimism in the face of uncertainty. At the core of our algorithm is a weighted ridge regression where the weight of each chosen action depends on its confidence up to some threshold. We show that for both known C and unknown C cases, our algorithm with proper choice of hyperparameter achieves a regret that nearly matches the lower bounds. Thus, our algorithm is nearly optimal up to logarithmic factors for both cases. Notably, our algorithm achieves the near-optimal regret for both corrupted and uncorrupted cases (C=0) simultaneously.