mlsanityData to 7 Oct 2026

Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits

arXiv 2002.00287 ↗First posted 1 Feb 2020cs.LG stat.MLcited by 42

Not on the map. Why?

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.

Key facts. Cited by 42 papers in the map (data through 7 Oct 2026). First posted on arXiv 1 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 12; 2024: 10; 2025: 5; 2026: 8.

42 papers.

Sort:

By area:

  1. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  3. 2023Breaking the Curse of Multiagents in a Large State Space: RL in Markov Games with Independent Linear Function Approximationcited by 26
  4. 2021Adapting to Misspecification in Contextual Bandits with Offline Regression Oraclescited by 21
  5. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  6. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  7. 2023Refined Regret for Adversarial MDPs with Linear Function Approximationcited by 18
  8. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  9. 2023Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximationcited by 16
  10. 2021Contextual Games: Multi-Agent Learning with Side Informationcited by 11
  11. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  12. 2024Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditscited by 9
30 more
  1. 2024Second Order Bounds for Contextual Bandits with Function Approximationcited by 9
  2. 2021Robust Bandit Learning with Imperfect Contextcited by 8
  3. 2024Optimal cross-learning for contextual bandits with unknown context distributionscited by 7
  4. 2023Incentivizing High-Quality Content in Online Recommender Systemscited by 6
  5. 2023Adversarial Contextual Bandits Go Kernelizedcited by 6
  6. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  7. 2022Reward Imputation with Sketching for Contextual Batched Banditscited by 5
  8. 2022Online Learning with Off-Policy Feedbackcited by 4
  9. 2024LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Banditscited by 4
  10. 2024Strategic Linear Contextual Banditscited by 4
  11. 2024A Parametric Contextual Online Learning Theory of Brokeragecited by 4
  12. 2024Refined Sample Complexity for Markov Games with Independent Linear Function Approximationcited by 3
  13. 2024On Bits and Bandits: Quantifying the Regret-Information Trade-offcited by 3
  14. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  15. 2023No-Regret Linear Bandits beyond Realizabilitycited by 2
  16. 2023Best-of-Both-Worlds Linear Contextual Banditscited by 2
  17. 2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
  18. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  19. 2023Harnessing the Power of Federated Learning in Federated Contextual Banditscited by 1
  20. 2025QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewritingcited by 1
  21. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  22. 2025Differential Privacy in Kernelized Contextual Bandits via Random Projectionscited by 0
  23. 2025Best-of-Both Worlds for linear contextual bandits with paid observationscited by 0
  24. 2026No One Size Fits All: QueryBandits for Hallucination Mitigationcited by 0
  25. 2026A Complete Characterization of Learnability for Adversarial Noisy Banditscited by 0
  26. 2026Stochastic Linear Contextual Bandits with Bounded Noise: A Set-Membership Approachcited by 0
  27. 2026Smart charging of large fleets of Electric Vehicles: Independent Multi-Agent Reinforcement Learning approachescited by 0
  28. 2026Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimizationcited by 0
  29. 2026Correlation-Aware Contextual Bandits with Surrogate Rewards for LLM Routingcited by 0
  30. 2026Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Banditscited by 0