Data to 14 Oct 2026

Sample Complexity of Robust Reinforcement Learning with a Generative Model

arXiv 2112.01506 ↗First posted 2 Dec 2021cs.LG stat.MLcited by 83

Not on the map. Why?

Cited by 33 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

The Robust Markov Decision Process (RMDP) framework focuses on designing control policies that are robust against the parameter uncertainties due to the mismatches between the simulator model and real-world settings. An RMDP problem is typically formulated as a max-min problem, where the objective is to find the policy that maximizes the value function for the worst possible model that lies in an uncertainty set around a nominal model. The standard robust dynamic programming approach requires the knowledge of the nominal model for computing the optimal robust policy. In this work, we propose a model-based reinforcement learning (RL) algorithm for learning an ε-optimal robust policy when the nominal model is unknown. We consider three different forms of uncertainty sets, characterized by the total variation distance, chi-square divergence, and KL divergence. For each of these uncertainty sets, we give a precise characterization of the sample complexity of our proposed algorithm. In addition to the sample complexity results, we also present a formal analytical argument on the benefit of using robust policies. Finally, we demonstrate the performance of our algorithm on two benchmark problems.

Key facts. Cited by 83 papers in the map (data through 14 Oct 2026). Builds on 15 of its 39 references that are in the map. First posted on arXiv 2 Dec 2021.

Builds on

15 of 39 references.

References · 15

2016OpenAI Gymcited by 1,736
2017Robust Adversarial Reinforcement Learningcited by 451
2020Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observationscited by 238
2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
2019Robust Reinforcement Learning for Continuous Control with Model Misspecificationcited by 78
2017Reinforcement Learning under Model Mismatchcited by 52
2019Policy Optimization for H2 Linear Control with H_∞ Robustness Guarantee: Implicit Regularization and Global Convergencecited by 46
2019Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPscited by 40
2018Soft-Robust Actor-Critic Policy-Gradientcited by 37
2019A Bayesian Approach to Robust Reinforcement Learningcited by 34
2015Distributionally Robust Counterpart in Markov Decision Processescited by 33

3 more

2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
2014Empirical Q-Value Iterationcited by 7
2013Empirical Dynamic Programmingcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 9; 2023: 25; 2024: 20; 2025: 17; 2026: 12.

83 papers.

Sort:

By area:

2022Robust Reinforcement Learning using Offline Datacited by 96
2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 38
2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
2022Doubly Robust Distributionally Robust Off-Policy Evaluation and Learningcited by 34
2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 29

38 more

2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 26
2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximationcited by 25
2023Robust Average-Reward Markov Decision Processescited by 22
2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
2023Replicable Reinforcement Learningcited by 21
2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
2022Online Policy Optimization for Robust MDPcited by 19
2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learningcited by 18
2025Robust LLM Alignment via Distributionally Robust Direct Preference Optimizationcited by 18
2023Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexitycited by 17
2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 16
2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 16
2022Robust Constrained Reinforcement Learningcited by 15
2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
2023Robust Markov Decision Processes without Model Estimationcited by 11
2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 8
2024Constrained Reinforcement Learning Under Model Mismatchcited by 8
2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
2024Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstractioncited by 6
2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 6
2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Modelcited by 5
2023Bayesian Risk-Averse Q-Learning with Streaming Observationscited by 4
2024Tractable Equilibrium Computation in Markov Games through Risk Aversioncited by 4
2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
2023Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theoremscited by 3
2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
2024Policy Gradient for Robust Markov Decision Processescited by 3

50 most cited of 83 All 83 (JSON)