# Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 37 of its 60 references that are in the map.
- First posted on arXiv 19 Mar 2024.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)
- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 37)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Online Robust Reinforcement Learning with Model Uncertainty](https://mlsanity.com/paper/2109.14523/) (2021)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism](https://mlsanity.com/paper/2203.05804/) (2022)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game](https://mlsanity.com/paper/2205.15512/) (2022)
- [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)
- [Partial Policy Iteration for L1-Robust Markov Decision Processes](https://mlsanity.com/paper/2006.09484/) (2020)
- [VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation](https://mlsanity.com/paper/2212.06069/) (2022)
- [Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2303.02783/) (2023)
- [Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/1902.08708/) (2019)
- [The Efficacy of Pessimism in Asynchronous Q-Learning](https://mlsanity.com/paper/2203.07368/) (2022)
- [Distributional Robustness and Regularization in Reinforcement Learning](https://mlsanity.com/paper/2003.02894/) (2020)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [First-order Policy Optimization for Robust Markov Decision Process](https://mlsanity.com/paper/2209.10579/) (2022)
- [Policy Gradient for Rectangular Robust Markov Decision Processes](https://mlsanity.com/paper/2301.13589/) (2023)
- [Sample Complexity of Variance-reduced Distributionally Robust Q-learning](https://mlsanity.com/paper/2305.18420/) (2023)
- [Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlation](https://mlsanity.com/paper/2307.07907/) (2023)
- [Reinforcement Learning for IoT Security: A Comprehensive Survey](https://mlsanity.com/paper/2102.07247/) (2021)
- [Online Policy Optimization for Robust MDP](https://mlsanity.com/paper/2209.13841/) (2022)

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

- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Data](https://mlsanity.com/paper/2411.03810/) (2024)
- [Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization](https://mlsanity.com/paper/2411.18612/) (2024)
- [ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning](https://mlsanity.com/paper/2508.03768/) (2025)
- [Linear Mixture Distributionally Robust Markov Decision Processes](https://mlsanity.com/paper/2505.18044/) (2025)
- [Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysis](https://mlsanity.com/paper/2505.12462/) (2025)
- [Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learning](https://mlsanity.com/paper/2505.18447/) (2025)
- [Online Robust Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2512.18957/) (2025)
- [Provably Efficient Sample Complexity for Robust CMDP](https://mlsanity.com/paper/2511.07486/) (2025)
- [Stationary Robust Mean-Field Games under Model Mismatches](https://mlsanity.com/paper/2606.22579/) (2026)
- [Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2609.28792/) (2026)
- [Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation](https://mlsanity.com/paper/2609.32048/) (2026)

## Abstract (arXiv)

In offline reinforcement learning (RL), the absence of active exploration calls for attention on the model robustness to tackle the sim-to-real gap, where the discrepancy between the simulated and deployed environments can significantly undermine the performance of the learned policy. To endow the learned policy with robustness in a sample-efficient manner in the presence of high-dimensional state-action space, this paper considers the sample complexity of distributionally robust linear Markov decision processes (MDPs) with an uncertainty set characterized by the total variation distance using offline data. We develop a pessimistic model-based algorithm and establish its sample complexity bound under minimal data coverage assumptions, which outperforms prior art by at least widetildeO(d), where d is the feature dimension. We further improve the performance guarantee of the proposed algorithm by incorporating a carefully-designed variance estimator.