# Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits

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

## Key facts

- Cited by 43 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Feb 2020.

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

- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2302.03673/) (2023)
- [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)
- [Refined Regret for Adversarial MDPs with Linear Function Approximation](https://mlsanity.com/paper/2301.12942/) (2023)
- [First- and Second-Order Bounds for Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2305.00832/) (2023)
- [Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits](https://mlsanity.com/paper/2309.00814/) (2023)
- [Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2301.13087/) (2023)
- [Contextual Games: Multi-Agent Learning with Side Information](https://mlsanity.com/paper/2107.06327/) (2021)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Second Order Bounds for Contextual Bandits with Function Approximation](https://mlsanity.com/paper/2409.16197/) (2024)
- [Robust Bandit Learning with Imperfect Context](https://mlsanity.com/paper/2102.05018/) (2021)
- [Optimal cross-learning for contextual bandits with unknown context distributions](https://mlsanity.com/paper/2401.01857/) (2024)
- [Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification](https://mlsanity.com/paper/2410.07533/) (2024)
- [Incentivizing High-Quality Content in Online Recommender Systems](https://mlsanity.com/paper/2306.07479/) (2023)
- [Adversarial Contextual Bandits Go Kernelized](https://mlsanity.com/paper/2310.01609/) (2023)
- [Reward Imputation with Sketching for Contextual Batched Bandits](https://mlsanity.com/paper/2210.06719/) (2022)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Online Learning with Off-Policy Feedback](https://mlsanity.com/paper/2207.08956/) (2022)
- [LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2403.03219/) (2024)
- [A Parametric Contextual Online Learning Theory of Brokerage](https://mlsanity.com/paper/2407.01566/) (2024)
- [An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction](https://mlsanity.com/paper/2508.11931/) (2025)
- [Refined Sample Complexity for Markov Games with Independent Linear Function Approximation](https://mlsanity.com/paper/2402.07082/) (2024)
- [On Bits and Bandits: Quantifying the Regret-Information Trade-off](https://mlsanity.com/paper/2405.16581/) (2024)
- [Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routing](https://mlsanity.com/paper/2607.09015/) (2026)
- [No-Regret Linear Bandits beyond Realizability](https://mlsanity.com/paper/2302.13252/) (2023)
- [Best-of-Both-Worlds Linear Contextual Bandits](https://mlsanity.com/paper/2312.16489/) (2023)
- [Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks](https://mlsanity.com/paper/2410.19705/) (2024)

## Abstract (arXiv)

We consider an adversarial variant of the classic K-armed linear contextual bandit problem where the sequence of loss functions associated with each arm are allowed to change without restriction over time. Under the assumption that the d-dimensional contexts are generated i.i.d.~at random from a known distributions, we develop computationally efficient algorithms based on the classic Exp3 algorithm. Our first algorithm, RealLinExp3, is shown to achieve a regret guarantee of widetildeO(√KdT) over T rounds, which matches the best available bound for this problem. Our second algorithm, RobustLinExp3, is shown to be robust to misspecification, in that it achieves a regret bound of widetildeO((Kd)1/3T2/3) + varepsilon √d T if the true reward function is linear up to an additive nonlinear error uniformly bounded in absolute value by varepsilon. To our knowledge, our performance guarantees constitute the very first results on this problem setting.