mlsanityData to 14 Oct 2026

Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms

arXiv 2404.03578 ↗First posted 4 Apr 2024cs.LG stat.MLcited by 26

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

The sim-to-real gap, which represents the disparity between training and testing environments, poses a significant challenge in reinforcement learning (RL). A promising approach to addressing this challenge is distributionally robust RL, often framed as a robust Markov decision process (RMDP). In this framework, the objective is to find a robust policy that achieves good performance under the worst-case scenario among all environments within a pre-specified uncertainty set centered around the training environment. Unlike previous work, which relies on a generative model or a pre-collected offline dataset enjoying good coverage of the deployment environment, we tackle robust RL via interactive data collection, where the learner interacts with the training environment only and refines the policy through trial and error. In this robust RL paradigm, two main challenges emerge: managing distributional robustness while striking a balance between exploration and exploitation during data collection. Initially, we establish that sample-efficient learning without additional assumptions is unattainable owing to the curse of support shift; i.e., the potential disjointedness of the distributional supports between the training and testing environments. To circumvent such a hardness result, we introduce the vanishing minimal value assumption to RMDPs with a total-variation (TV) distance robust set, postulating that the minimal value of the optimal robust value function is zero. We prove that such an assumption effectively eliminates support shift pathologies for RMDPs with a TV distance robust set, and present an algorithm with near-optimal sample complexity. To demonstrate the breadth of our framework, we extend our algorithm and theory to new robust set formulations and robust Markov games. To illustrate the operational relevance, we apply our algorithm to data-driven robust inventory control.

Key facts. Cited by 26 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 62 of its 82 references that are in the map. First posted on arXiv 4 Apr 2024.

Builds on

62 of 82 references.

Closest ancestors · 2

Same direction, newest first

  1. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes19 Mar
  2. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation23 Feb

Other references · 60

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2020Deep Reinforcement Learning for Autonomous Driving: A Surveycited by 721
  3. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 672
  4. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  5. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  6. 2018Is Q-learning Provably Efficient?cited by 487
  7. 2017Robust Adversarial Reinforcement Learningcited by 451
  8. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 413
  9. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  10. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  11. 2016CAD2RL: Real Single-Image Flight without a Single Real Imagecited by 233
  12. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
38 more
  1. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  2. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  3. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  4. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  5. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  8. 2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
  9. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  10. 2022Robust Reinforcement Learning using Offline Datacited by 96
  11. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 92
  12. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  13. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  14. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  15. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  16. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  17. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  18. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  19. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  20. 2021UCB Momentum Q-learning: Correcting the bias without forgettingcited by 46
  21. 2022GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondcited by 46
  22. 2021A Model Selection Approach for Corruption Robust Reinforcement Learningcited by 45
  23. 2023Settling the Sample Complexity of Online Reinforcement Learningcited by 45
  24. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  25. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  26. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 38
  27. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  28. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  29. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  30. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 32
  31. 2023Corruption-Robust Offline Reinforcement Learning with General Function Approximationcited by 31
  32. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 29
  33. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  34. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  35. 2023Towards Robust Offline Reinforcement Learning under Diverse Data Corruptioncited by 24
  36. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  37. 2020Distributionally Robust Batch Contextual Banditscited by 20
  38. 2022Online Policy Optimization for Robust MDPcited by 19

50 most cited of 60 All 60 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 14; 2026: 11.

26 papers.

Sort:

By area:

  1. 2026Maximum Likelihood Reinforcement Learningcited by 36
  2. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
  3. 2025MOBODY: Model Based Off-Dynamics Offline Reinforcement Learningcited by 9
  4. 2026Unveiling Implicit Advantage Symmetry: Why GRPO Struggles with Exploration and Difficulty Adaptationcited by 7
  5. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  6. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  7. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  8. 2025Causality-Inspired Robustness for Nonlinear Models via Representation Learningcited by 3
  9. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  10. 2026Distributionally Robust Optimization via Generative Ambiguity Modelingcited by 3
  11. 2025Distributionally Robust Multi-Agent Reinforcement Learning for Dynamic Chute Mappingcited by 2
  12. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
14 more
  1. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 2
  2. 2025Curriculum-Adapted Robust Reinforcement Learning for UAV Deconfliction in Adversarial Environmentscited by 1
  3. 2025Distributionally Robust Self Paced Curriculum Reinforcement Learningcited by 1
  4. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  5. 2025Duality and Policy Evaluation in Distributionally Robust Bayesian Diffusion Controlcited by 0
  6. 2025Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Setscited by 0
  7. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  8. 2026The Price of Paranoia: Robust Risk-Sensitive Cooperation in Non-Stationary Multi-Agent Reinforcement Learningcited by 0
  9. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0
  10. 2026Breaking the Epistemic Trap: Active Perception Under Compound Uncertaintycited by 0
  11. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0
  12. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0
  13. 2026Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processescited by 0
  14. 2026Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysis
  2. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage
  3. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty
  4. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  5. 2025Policy Regularized Distributionally Robust Markov Decision Processes with Linear Function Approximation
  6. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  7. 2025Sample Complexity of Distributionally Robust Off-Dynamics Reinforcement Learning with Online Interaction
  8. 2024Safe and Robust Reinforcement Learning: Principles and Practice