mlsanityData to 14 Oct 2026

Model-Free Robust Reinforcement Learning with Sample Complexity Analysis

arXiv 2406.17096 ↗First posted 24 Jun 2024cs.LG cs.AI stat.MLcited by 9

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

Abstract (arXiv)

Distributionally Robust Reinforcement Learning (DR-RL) aims to derive a policy optimizing the worst-case performance within a predefined uncertainty set. Despite extensive research, previous DR-RL algorithms have predominantly favored model-based approaches, with limited availability of model-free methods offering convergence guarantees or sample complexities. This paper proposes a model-free DR-RL algorithm leveraging the Multi-level Monte Carlo (MLMC) technique to close such a gap. Our innovative approach integrates a threshold mechanism that ensures finite sample requirements for algorithmic implementation, a significant improvement than previous model-free algorithms. We develop algorithms for uncertainty sets defined by total variation, Chi-square divergence, and KL divergence, and provide finite sample analyses under all three cases. Remarkably, our algorithms represent the first model-free DR-RL approach featuring finite sample complexity for total variation and Chi-square divergence uncertainty sets, while also offering an improved sample complexity and broader applicability compared to existing model-free DR-RL algorithms for the KL divergence model. The complexities of our method establish the tightest results for all three uncertainty models in model-free DR-RL, underscoring the effectiveness and efficiency of our algorithm, and highlighting its potential for practical applications.

Key facts. Cited by 9 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 15 of its 28 references that are in the map. First posted on arXiv 24 Jun 2024.

Builds on

15 of 28 references.

References · 15

  1. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 413
  2. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  3. 2020Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reductioncited by 95
  4. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  5. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  6. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  7. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  8. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29
  9. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximationcited by 22
  10. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  11. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  12. 2019Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applicationscited by 18
3 more
  1. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 16
  2. 2022Unbiased Multilevel Monte Carlo methods for intractable distributions: MLMC meets MCMCcited by 5
  3. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 6; 2026: 3.

9 papers.

  1. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 7
  2. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
  3. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
  4. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 3
  5. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  6. 2026Online Robust Reinforcement Learning Through Monte-Carlo Planningcited by 2
  7. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  8. 2026Robust Transfer Learning with Side Informationcited by 0
  9. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Online Robust Reinforcement Learning with General Function Approximation
  2. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning
  3. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms
  4. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes
  5. 2025Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
  6. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  7. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Duality
  8. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning