mlsanityData to 7 Oct 2026

Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes

arXiv 2403.12946 ↗First posted 19 Mar 2024cs.LG math.ST stat.THcited by 12

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

Key facts. Cited by 12 papers in the map (data through 7 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.

Builds on

37 of 60 references.

Closest ancestors · 11

Same direction, newest first

  1. 2024Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning14 Mar
  2. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage16 May
  3. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity11 Aug
  4. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  5. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimism11 Mar
  7. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  8. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  10. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  11. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May

Other references · 26

  1. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  2. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  3. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  4. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  5. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  6. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  7. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  8. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  9. 2022VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximationcited by 44
  10. 2023Improved Sample Complexity Bounds for Distributionally Robust Reinforcement Learningcited by 44
  11. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 41
  12. 2019Distributionally Robust Reinforcement Learningcited by 40
14 more
  1. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 39
  2. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 35
  3. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  4. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  5. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  6. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  7. 2021Reinforcement Learning for IoT Security: A Comprehensive Surveycited by 21
  8. 2022Online Policy Optimization for Robust MDPcited by 19
  9. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  10. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  11. 2019Distributional reinforcement learning with linear function approximationcited by 15
  12. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  13. 2023Adjustable Robust Reinforcement Learning for Online 3D Bin Packingcited by 9
  14. 2023First-order Policy Optimization for Robust Policy Evaluationcited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2024: 5; 2025: 6; 2026: 1.

12 papers.

  1. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  2. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  3. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  4. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  5. 2024Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularizationcited by 8
  6. 2025Linear Mixture Distributionally Robust Markov Decision Processescited by 5
  7. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  8. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  9. 2025Pessimism Principle Can Be Effective: Towards a Framework for Zero-Shot Transfer Reinforcement Learningcited by 2
  10. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  11. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  12. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Robust Offline Reinforcement Learning for Non-Markovian Decision Processes
  2. 2023Achieving the Asymptotically Optimal Sample Complexity of Offline Reinforcement Learning: A DRO-Based Approach
  3. 2023On the Sample Complexity of Vanilla Model-Based Offline Reinforcement Learning with Dependent Samples
  4. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coverage
  5. 2022Offline Reinforcement Learning via Linear-Programming with Error-Bound Induced Constraints
  6. 2024On Sample-Efficient Offline Reinforcement Learning: Data Diversity, Posterior Sampling, and Beyond
  7. 2025Towards Optimal Offline Reinforcement Learning
  8. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximation