mlsanityData to 7 Oct 2026

Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics

arXiv 2105.03863 ↗First posted 9 May 2021stat.ML cs.LGcited by 27

Not on the map. Why?

Abstract (arXiv)

In this paper, we study the non-asymptotic and asymptotic performances of the optimal robust policy and value function of robust Markov Decision Processes(MDPs), where the optimal robust policy and value function are solved only from a generative model. While prior work focusing on non-asymptotic performances of robust MDPs is restricted in the setting of the KL uncertainty set and (s,a)-rectangular assumption, we improve their results and also consider other uncertainty sets, including L1 and chi2 balls. Our results show that when we assume (s,a)-rectangular on uncertainty sets, the sample complexity is about widetildeOleft(frac|S|2|A|varepsilon2ρ2(1-γ)4right). In addition, we extend our results from (s,a)-rectangular assumption to s-rectangular assumption. In this scenario, the sample complexity varies with the choice of uncertainty sets and is generally larger than the case under (s,a)-rectangular assumption. Moreover, we also show that the optimal robust value function is asymptotic normal with a typical rate √n under (s,a) and s-rectangular assumptions from both theoretical and empirical perspectives.

Key facts. Cited by 27 papers in the map (data through 7 Oct 2026). Builds on 39 of its 96 references that are in the map. First posted on arXiv 9 May 2021.

Builds on

39 of 96 references.

References · 39

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2015Continuous control with deep reinforcement learningcited by 3,279
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,218
  4. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  5. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 774
  6. 2017Sim-to-Real Transfer of Robotic Control with Dynamics Randomizationcited by 616
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  8. 2018Is Q-learning Provably Efficient?cited by 485
  9. 2020Sim-to-Real Transfer in Deep Reinforcement Learning for Robotics: a Surveycited by 388
  10. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  11. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  12. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
27 more
  1. 2016Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learningcited by 285
  2. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  3. 2019Batch Policy Learning under Constraintscited by 242
  4. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  5. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  6. 2016Statistics of Robust Optimization: A Generalized Empirical Likelihood Approachcited by 182
  7. 2015Doubly Robust Policy Evaluation and Optimizationcited by 158
  8. 2016Variance-based regularization with convex objectivescited by 153
  9. 2018More Robust Doubly Robust Off-policy Evaluationcited by 141
  10. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  11. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  12. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  13. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  14. 2019Double Reinforcement Learning for Efficient Off-Policy Evaluation in Markov Decision Processescited by 118
  15. 2020Batch Value-function Approximation with Only Realizabilitycited by 103
  16. 2013Data-Driven Robust Optimizationcited by 84
  17. 2019Robust Reinforcement Learning for Continuous Control with Model Misspecificationcited by 76
  18. 2020CoinDICE: Off-Policy Confidence Interval Estimationcited by 64
  19. 2020Asymptotically Efficient Off-Policy Evaluation for Tabular Reinforcement Learningcited by 60
  20. 2016Safe Policy Improvement by Minimizing Robust Baseline Regretcited by 51
  21. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  22. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learningcited by 42
  23. 2019Distributionally Robust Reinforcement Learningcited by 40
  24. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 39
  25. 2019Beyond Confidence Regions: Tight Bayesian Ambiguity Sets for Robust MDPscited by 37
  26. 2019A Bayesian Approach to Robust Reinforcement Learningcited by 32
  27. 2021On the Optimality of Batch Policy Optimization Algorithmscited by 28

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 6; 2023: 12; 2024: 4; 2025: 1; 2026: 2.

27 papers.

Sort:

By area:

  1. 2022Robust Reinforcement Learning using Offline Datacited by 95
  2. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  3. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
  4. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  5. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  6. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  7. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  8. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  9. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  10. 2021A Statistical Analysis of Polyak-Ruppert Averaged Q-learningcited by 29
  11. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  12. 2023Robust Average-Reward Markov Decision Processescited by 22
15 more
  1. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
  2. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  3. 2022Online Policy Optimization for Robust MDPcited by 19
  4. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  5. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  6. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  7. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  8. 2024Constrained Reinforcement Learning Under Model Mismatchcited by 6
  9. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approachcited by 3
  10. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  11. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  12. 2024Bootstrapping Expectiles in Reinforcement Learningcited by 1
  13. 2024Learning Optimal Distributionally Robust Stochastic Control in Continuous State Spacescited by 0
  14. 2026Robust Transfer Learning with Side Informationcited by 0
  15. 2026Robust PAC Learning of Concurrent Stochastic Gamescited by 0