mlsanityData to 7 Oct 2026

Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processes

arXiv 2212.05949 ↗First posted 12 Dec 2022stat.ML cs.LGcited by 33

Not on the map. Why?

Abstract (arXiv)

Despite the significant interest and progress in reinforcement learning (RL) problems with adversarial corruption, current works are either confined to the linear setting or lead to an undesired tildeO(√Tzeta) regret bound, where T is the number of rounds and zeta is the total amount of corruption. In this paper, we consider the contextual bandit with general function approximation and propose a computationally efficient algorithm to achieve a regret of tildeO(√T+zeta). The proposed algorithm relies on the recently developed uncertainty-weighted least-squares regression from linear contextual bandit and a new weighted estimator of uncertainty for the general function class. In contrast to the existing analysis that heavily relies on the linear structure, we develop a novel technique to control the sum of weighted uncertainty, thus establishing the final regret bounds. We then generalize our algorithm to the episodic MDP setting and first achieve an additive dependence on the corruption level zeta in the scenario of general function approximation. Notably, our algorithms achieve regret bounds either nearly match the performance lower bound or improve the existing methods for all the corruption levels and in both known and unknown zeta cases.

Key facts. Cited by 33 papers in the map (data through 7 Oct 2026). Builds on 23 of its 52 references that are in the map. First posted on arXiv 12 Dec 2022.

Builds on

23 of 52 references.

References · 23

  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. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2020Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oraclescited by 195
  5. 2018Stochastic bandits robust to adversarial corruptionscited by 118
  6. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  7. 2019Better Algorithms for Stochastic Bandits with Adversarial Corruptionscited by 91
  8. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 84
  9. 2021Adapting to Misspecification in Contextual Banditscited by 81
  10. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  11. 2020Stochastic Linear Bandits Robust to Adversarial Attackscited by 65
  12. 2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
11 more
  1. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
  2. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  3. 2020Simultaneously Learning Stochastic and Adversarial Episodic MDPs with Known Transitioncited by 48
  4. 2021Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneouslycited by 48
  5. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  6. 2021Robust Stochastic Linear Contextual Bandits Under Adversarial Attackscited by 33
  7. 2020Stochastic Shortest Path with Adversarially Changing Costscited by 28
  8. 2021Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Casecited by 28
  9. 2019Stochastic Linear Optimization with Adversarial Corruptioncited by 23
  10. 2013Linear Bandits in High Dimension and Recommendation Systemscited by 22
  11. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 9; 2024: 12; 2025: 9; 2026: 3.

33 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2024Online Iterative Reinforcement Learning from Human Feedback with General Preference Modelcited by 52
  3. 2024Sharp Analysis for KL-Regularized Contextual Bandits and RLHFcited by 32
  4. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 30
  5. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  6. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  7. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  8. 2025Logarithmic Regret for Online KL-Regularized Reinforcement Learningcited by 20
  9. 2025RobustVLA: Robustness-Aware Reinforcement Post-Training for Vision-Language-Action Modelscited by 16
  10. 2023Robust Lipschitz Bandits to Adversarial Corruptionscited by 15
  11. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  12. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
21 more
  1. 2023Best-of-Both-Worlds Algorithms for Linear Contextual Banditscited by 10
  2. 2025Greedy Sampling Is Provably Efficient for RLHFcited by 10
  3. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  4. 2024Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedbackcited by 9
  5. 2024How Does Variance Shape the Regret in Contextual Bandits?cited by 9
  6. 2024Uncertainty-based Offline Variational Bayesian Reinforcement Learning for Robustness under Diverse Data Corruptionscited by 8
  7. 2023On the Model-Misspecification in Reinforcement Learningcited by 7
  8. 2024Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecificationcited by 6
  9. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  10. 2023Optimal Sample Selection Through Uncertainty Estimation and Its Application in Deep Learningcited by 4
  11. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  12. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  13. 2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
  14. 2025Offline and Online KL-Regularized RLHF under Differential Privacycited by 3
  15. 2024Learning from Imperfect Human Feedback: a Tale from Corruption-Robust Duelingcited by 2
  16. 2025Daunce: Data Attribution through Uncertainty Estimationcited by 1
  17. 2025Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Ratescited by 1
  18. 2026A Jointly Efficient and Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptionscited by 1
  19. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferencescited by 1
  20. 2025Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Modelscited by 0
  21. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0