mlsanityData to 7 Oct 2026

Towards Minimax Optimality of Model-based Robust Reinforcement Learning

arXiv 2302.05372 ↗First posted 10 Feb 2023cs.LG stat.MLcited by 21

Not on the map. Why?

Abstract (arXiv)

We study the sample complexity of obtaining an ε-optimal policy in Robust discounted Markov Decision Processes (RMDPs), given only access to a generative model of the nominal kernel. This problem is widely studied in the non-robust case, and it is known that any planning approach applied to an empirical MDP estimated with tildeO(fracH3 mid S midmid A midε2) samples provides an ε-optimal policy, which is minimax optimal. Results in the robust case are much more scarce. For sa- (resp s-)rectangular uncertainty sets, the best known sample complexity is tildeO(fracH4 mid S mid2mid A midε2) (resp. tildeO(fracH4 mid S mid2mid A mid2ε2)), for specific algorithms and when the uncertainty set is based on the total variation (TV), the KL or the Chi-square divergences. In this paper, we consider uncertainty sets defined with an Lp-ball (recovering the TV case), and study the sample complexity of any planning algorithm (with high accuracy guarantee on the solution) applied to an empirical RMDP estimated using the generative model. In the general case, we prove a sample complexity of tildeO(fracH4 mid S midmid A midε2) for both the sa- and s-rectangular cases (improvements of mid S mid and mid S midmid A mid respectively). When the size of the uncertainty is small enough, we improve the sample complexity to tildeO(fracH3 mid S midmid A mid ε2), recovering the lower-bound for the non-robust case for the first time and a robust lower-bound when the size of the uncertainty is small enough.

Key facts. Cited by 21 papers in the map (data through 7 Oct 2026). Builds on 19 of its 38 references that are in the map. First posted on arXiv 10 Feb 2023.

Builds on

19 of 38 references.

References · 19

  1. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  2. 2017Robust Adversarial Reinforcement Learningcited by 439
  3. 2019A Theory of Regularized Markov Decision Processescited by 279
  4. 2018Assessing Generalization in Deep Reinforcement Learningcited by 132
  5. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  6. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  7. 2022Robust Reinforcement Learning using Offline Datacited by 95
  8. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  9. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  10. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  11. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  12. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 39
7 more
  1. 2020Leverage the Average: an Analysis of KL Regularization in RLcited by 33
  2. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  3. 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
  4. 2019Investigating Generalisation in Continuous Deep Reinforcement Learningcited by 18
  5. 2022KL-Entropy-Regularized RL with a Generative Model is Minimax Optimalcited by 13
  6. 2022Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecificationcited by 11
  7. 2022Robust Reinforcement Learning with Distributional Risk-averse formulationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 4; 2024: 8; 2025: 8; 2026: 1.

21 papers.

Sort:

By area:

  1. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  2. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  3. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  4. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  5. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  6. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  7. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  8. 2024Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruptioncited by 12
  9. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  10. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  11. 2025Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learningcited by 6
  12. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
9 more
  1. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  2. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  3. 2024RRLS : Robust Reinforcement Learning Suitecited by 2
  4. 2024Bootstrapping Expectiles in Reinforcement Learningcited by 1
  5. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  6. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  7. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  8. 2025ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertaintycited by 0
  9. 2026Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approachcited by 0