mlsanityData to 7 Oct 2026

A Finite Sample Complexity Bound for Distributionally Robust Q-learning

arXiv 2302.13203 ↗First posted 26 Feb 2023cs.LG stat.MLcited by 35

Not on the map. Why?

Abstract (arXiv)

We consider a reinforcement learning setting in which the deployment environment is different from the training environment. Applying a robust Markov decision processes formulation, we extend the distributionally robust Q-learning framework studied in Liu et al. [2022]. Further, we improve the design and analysis of their multi-level Monte Carlo estimator. Assuming access to a simulator, we prove that the worst-case expected sample complexity of our algorithm to learn the optimal robust Q-function within an ε error in the sup norm is upper bounded by tilde O(|S||A|(1-γ)-5ε-2pwedge-6δ-4), where γ is the discount rate, pwedge is the non-zero minimal support probability of the transition kernels and δ is the uncertainty size. This is the first sample complexity result for the model-free robust RL problem. Simulation studies further validate our theoretical results.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). Builds on 29 of its 72 references that are in the map. First posted on arXiv 26 Feb 2023.

Builds on

29 of 72 references.

References · 29

  1. 2018Generalizing to Unseen Domains via Adversarial Data Augmentationcited by 451
  2. 2016Deep Reinforcement Learning for Robotic Manipulation with Asynchronous Off-Policy Updatescited by 342
  3. 2018Learning Models with Uniform Performance via Distributionally Robust Optimizationcited by 334
  4. 2015Data-driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulationscited by 285
  5. 2016CAD2RL: Real Single-Image Flight without a Single Real Imagecited by 227
  6. 2016Distributionally Robust Stochastic Optimization with Wasserstein Distancecited by 182
  7. 2016Statistics of Robust Optimization: A Generalized Empirical Likelihood Approachcited by 182
  8. 2015Distributionally Robust Logistic Regressioncited by 124
  9. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  10. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 108
  11. 2021Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysiscited by 89
  12. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
17 more
  1. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  2. 2019Stochastic approximation with cone-contractive operators: Sharp ℓ_∞-bounds for Q-learningcited by 74
  3. 2019Variance-reduced Q-learning is minimax optimalcited by 72
  4. 2016Recovering Best Statistical Guarantees via the Empirical Divergence-based Distributionally Robust Optimizationcited by 33
  5. 2018Robust Hypothesis Testing Using Wasserstein Uncertainty Setscited by 28
  6. 2018Wasserstein Distributionally Robust Stochastic Control: A Data-Driven Approachcited by 27
  7. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  8. 2018Near-Optimal Time and Sample Complexities for Solving Discounted Markov Decision Process with a Generative Modelcited by 22
  9. 2017Learning Policies for Adaptive Tracking with Deep Feature Cascadescited by 19
  10. 2018Wasserstein Distributionally Robust Kalman Filteringcited by 17
  11. 2019Unbiased Multilevel Monte Carlo: Stochastic Optimization, Steady-state Simulation, Quantiles, and Other Applicationscited by 17
  12. 2018Distributionally Robust Inverse Covariance Estimation: The Wasserstein Shrinkage Estimatorcited by 16
  13. 2016The Empirical Likelihood Approach to Quantifying Uncertainty in Sample Average Approximationcited by 12
  14. 2018Data-Driven Chance Constrained Programs over Wasserstein Ballscited by 9
  15. 2022Distributionally Robust Fair Principal Components via Geodesic Descentscited by 9
  16. 2019Distributionally Robust Formulation and Model Selection for the Graphical Lassocited by 7
  17. 2020Distributionally Robust Chance-Constrained Programs with Right-Hand Side Uncertainty under Wasserstein Ambiguitycited by 4

Built on by

Cited by year (2026 to 7 Oct)

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

35 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. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  4. 2023Sample Complexity of Variance-reduced Distributionally Robust Q-learningcited by 28
  5. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  6. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  7. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  8. 2023On the Foundation of Distributionally Robust Reinforcement Learningcited by 18
  9. 2023Distributionally Robust Model-based Reinforcement Learning with Large State Spacescited by 17
  10. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  11. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysiscited by 9
  12. 2025Efficient Policy Optimization in Robust Constrained MDPs with Iteration Complexity Guaranteescited by 6
23 more
  1. 2024Continuous-time Risk-sensitive Reinforcement Learning via Quadratic Variation Penaltycited by 5
  2. 2025ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learningcited by 5
  3. 2025Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlocited by 3
  4. 2025DR-SAC: Distributionally Robust Soft Actor-Critic for Reinforcement Learning under Uncertaintycited by 3
  5. 2024Model-Free Robust φ-Divergence Reinforcement Learning Using Both Offline and Online Datacited by 2
  6. 2024Q-Learning under Finite Model Uncertaintycited by 2
  7. 2024Learning a Single Neuron Robustly to Distributional Shifts and Adversarial Label Noisecited by 2
  8. 2025Planning and Learning in Average Risk-aware MDPscited by 2
  9. 2025Model-Free Robust Average-Reward Reinforcement Learning with Sample Complexity Analysiscited by 2
  10. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 2
  11. 2025Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learningcited by 1
  12. 2025Distributionally Robust Deep Q-Learningcited by 1
  13. 2025Distributionally Robust Optimization with Adversarial Data Contaminationcited by 1
  14. 2025Online Bayesian Risk-Averse Reinforcement Learningcited by 1
  15. 2025Provably Efficient Sample Complexity for Robust CMDPcited by 1
  16. 2025Distributionally Robust Online Markov Game with Linear Function Approximationcited by 1
  17. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  18. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  19. 2026Online Robust Reinforcement Learning Through Monte-Carlo Planningcited by 1
  20. 2025Duality and Policy Evaluation in Distributionally Robust Bayesian Diffusion Controlcited by 0
  21. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  22. 2026Stationary Robust Mean-Field Games under Model Mismatchescited by 0
  23. 2026Robust PAC Learning of Concurrent Stochastic Gamescited by 0