mlsanityData to 7 Oct 2026

Scalable First-Order Methods for Robust MDPs

arXiv 2005.05434 ↗First posted 11 May 2020math.OC cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

Robust Markov Decision Processes (MDPs) are a powerful framework for modeling sequential decision-making problems with model uncertainty. This paper proposes the first first-order framework for solving robust MDPs. Our algorithm interleaves primal-dual first-order updates with approximate Value Iteration updates. By carefully controlling the tradeoff between the accuracy and cost of Value Iteration updates, we achieve an ergodic convergence rate of O left( A2 S3log(S)log(ε-1) ε-1 right) for the best choice of parameters on ellipsoidal and Kullback-Leibler s-rectangular uncertainty sets, where S and A is the number of states and actions, respectively. Our dependence on the number of states and actions is significantly better (by a factor of O(A1.5S1.5)) than that of pure Value Iteration algorithms. In numerical experiments on ellipsoidal uncertainty sets we show that our algorithm is significantly more scalable than state-of-the-art approaches. Our framework is also the first one to solve robust MDPs with s-rectangular KL uncertainty sets.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 May 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 7; 2023: 4; 2024: 3; 2025: 4; 2026: 2.

22 papers.

Sort:

By area:

  1. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  2. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  3. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 35
  4. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  5. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  6. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  7. 2022Robust Reinforcement Learning with Distributional Risk-averse formulationcited by 9
  8. 2022On the convex formulations of robust Markov decision processescited by 8
  9. 2022Robust Reinforcement Learning in Continuous Control Tasks with Uncertainty Set Regularizationcited by 7
  10. 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 6
  11. 2025Robust Finite-Memory Policy Gradients for Hidden-Model POMDPscited by 5
  12. 2021Conic Blackwell Algorithm: Parameter-Free Convex-Concave Saddle-Point Solvingcited by 4
10 more
  1. 2022Solving optimization problems with Blackwell approachabilitycited by 4
  2. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  3. 2024RRLS : Robust Reinforcement Learning Suitecited by 2
  4. 2022Robust Phi-Divergence MDPscited by 1
  5. 2023Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularizationcited by 1
  6. 2024Solving robust MDPs as a sequence of static RL problemscited by 1
  7. 2026Robust General Utility for Reinforcement Learningcited by 1
  8. 2025ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertaintycited by 0
  9. 2025A Theoretical Analysis of State Similarity Between Markov Decision Processescited by 0
  10. 2026Entropy Regularization Improves Policy Robustness in Continuous-Time Reinforcement Learningcited by 0