# Towards Minimax Optimality of Model-based Robust Reinforcement Learning

arXiv: https://arxiv.org/abs/2302.05372 · HTML: https://mlsanity.com/paper/2302.05372/

## Key facts

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

## Builds on (most cited first, 19 of 19)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Robust Adversarial Reinforcement Learning](https://mlsanity.com/paper/1703.02702/) (2017)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [Assessing Generalization in Deep Reinforcement Learning](https://mlsanity.com/paper/1810.12282/) (2018)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2005.12900/) (2020)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [Twice regularized MDPs and the equivalence between robustness and regularization](https://mlsanity.com/paper/2110.06267/) (2021)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [Leverage the Average: an Analysis of KL Regularization in RL](https://mlsanity.com/paper/2003.14089/) (2020)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Efficient Policy Iteration for Robust Markov Decision Processes via Regularization](https://mlsanity.com/paper/2205.14327/) (2022)
- [Investigating Generalisation in Continuous Deep Reinforcement Learning](https://mlsanity.com/paper/1902.07015/) (2019)
- [KL-Entropy-Regularized RL with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/2205.14211/) (2022)
- [Max-Min Off-Policy Actor-Critic Method Focusing on Worst-Case Robustness to Model Misspecification](https://mlsanity.com/paper/2211.03413/) (2022)
- [Robust Reinforcement Learning with Distributional Risk-averse formulation](https://mlsanity.com/paper/2206.06841/) (2022)

## Built on by (most cited first, 22 of 22)

- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlation](https://mlsanity.com/paper/2307.07907/) (2023)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Distributionally Robust Model-based Reinforcement Learning with Large State Spaces](https://mlsanity.com/paper/2309.02236/) (2023)
- [Distributionally Robust Constrained Reinforcement Learning under Strong Duality](https://mlsanity.com/paper/2406.15788/) (2024)
- [Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption](https://mlsanity.com/paper/2402.08991/) (2024)
- [Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Form](https://mlsanity.com/paper/2408.16286/) (2024)
- [Model-Free Robust Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2406.17096/) (2024)
- [Wolfpack Adversarial Attack for Robust Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.02844/) (2025)
- [Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guarantees](https://mlsanity.com/paper/2505.19238/) (2025)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertainty](https://mlsanity.com/paper/2506.12622/) (2025)
- [RRLS : Robust Reinforcement Learning Suite](https://mlsanity.com/paper/2406.08406/) (2024)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Bootstrapping Expectiles in Reinforcement Learning](https://mlsanity.com/paper/2406.04081/) (2024)
- [Provably Efficient Sample Complexity for Robust CMDP](https://mlsanity.com/paper/2511.07486/) (2025)
- [Distributionally Robust Online Markov Game with Linear Function Approximation](https://mlsanity.com/paper/2511.07831/) (2025)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)
- [Data-driven robust Markov decision processes on Borel spaces: performance guarantees via an axiomatic approach](https://mlsanity.com/paper/2603.08979/) (2026)
- [Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation](https://mlsanity.com/paper/2609.32048/) (2026)

## 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.