mlsanityData to 7 Oct 2026

Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification

arXiv 2410.07533 ↗First posted 10 Oct 2024cs.LG stat.MLcited by 6

Not on the map. Why?

Abstract (arXiv)

In linear bandits, how can a learner effectively learn when facing corrupted rewards? While significant work has explored this question, a holistic understanding across different adversarial models and corruption measures is lacking, as is a full characterization of the minimax regret bounds. In this work, we compare two types of corruptions commonly considered: strong corruption, where the corruption level depends on the action chosen by the learner, and weak corruption, where the corruption level does not depend on the action chosen by the learner. We provide a unified framework to analyze these corruptions. For stochastic linear bandits, we fully characterize the gap between the minimax regret under strong and weak corruptions. We also initiate the study of corrupted adversarial linear bandits, obtaining upper and lower bounds with matching dependencies on the corruption level. Next, we reveal a connection between corruption-robust learning and learning with gap-dependent mis-specification, a setting first studied by Liu et al. (2023a), where the misspecification level of an action or policy is proportional to its suboptimality. We present a general reduction that enables any corruption-robust algorithm to handle gap-dependent misspecification. This allows us to recover the results of Liu et al. (2023a) in a black-box manner and significantly generalize them to settings like linear MDPs, yielding the first results for gap-dependent misspecification in reinforcement learning. However, this general reduction does not attain the optimal rate for gap-dependent misspecification. Motivated by this, we develop a specialized algorithm that achieves optimal bounds for gap-dependent misspecification in linear bandits, thus answering an open question posed by Liu et al. (2023a).

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 32 of its 51 references that are in the map. First posted on arXiv 10 Oct 2024.

Builds on

32 of 51 references.

References · 32

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  4. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  6. 2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
  7. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 124
  8. 2018More Adaptive Algorithms for Adversarial Banditscited by 114
  9. 2021Adapting to Misspecification in Contextual Banditscited by 81
  10. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  11. 2019Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneouslycited by 53
  12. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
20 more
  1. 2020Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPscited by 49
  2. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  3. 2016An algorithm with nearly optimal pseudo-regret for both stochastic and adversarial banditscited by 47
  4. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  5. 2017An Improved Parametrization and Analysis of the EXP3++ Algorithm for Stochastic and Adversarial Banditscited by 43
  6. 2020Efficient and Robust Algorithms for Adversarial Linear Contextual Banditscited by 42
  7. 2020Corruption-Tolerant Gaussian Process Bandit Optimizationcited by 34
  8. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  9. 2023A Blackbox Approach to Best of Both Worlds in Bandits and Beyondcited by 29
  10. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
  11. 2023Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Banditscited by 18
  12. 2023Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Boundscited by 13
  13. 2023No-Regret Online Reinforcement Learning with Adversarial Losses and Transitionscited by 13
  14. 2023Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedbackcited by 12
  15. 2022A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Banditscited by 11
  16. 2023Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithmcited by 11
  17. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  18. 2021The entropic barrier is n-self-concordantcited by 6
  19. 2023On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Banditscited by 6
  20. 2023No-Regret Linear Bandits beyond Realizabilitycited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 1; 2026: 5.

6 papers.

  1. 2025An Improved Algorithm for Adversarial Linear Contextual Bandits via Reductioncited by 3
  2. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  3. 2026Batched Stochastic Linear Bandits with 1-Bit Communication Constraintscited by 1
  4. 2026Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Expertscited by 1
  5. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0
  6. 2026Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivitycited by 0