mlsanityData to 7 Oct 2026

Partial Policy Iteration for L1-Robust Markov Decision Processes

arXiv 2006.09484 ↗First posted 16 Jun 2020cs.LG math.OC stat.MLcited by 49

Not on the map. Why?

Abstract (arXiv)

Robust Markov decision processes (MDPs) allow to compute reliable solutions for dynamic decision problems whose evolution is modeled by rewards and partially-known transition probabilities. Unfortunately, accounting for uncertainty in the transition probabilities significantly increases the computational complexity of solving robust MDPs, which severely limits their scalability. This paper describes new efficient algorithms for solving the common class of robust MDPs with s- and sa-rectangular ambiguity sets defined by weighted L1 norms. We propose partial policy iteration, a new, efficient, flexible, and general policy iteration scheme for robust MDPs. We also propose fast methods for computing the robust Bellman operator in quasi-linear time, nearly matching the linear complexity the non-robust Bellman operator. Our experimental results indicate that the proposed methods are many orders of magnitude faster than the state-of-the-art approach which uses linear programming solvers combined with a robust value iteration.

Key facts. Cited by 49 papers in the map (data through 7 Oct 2026). First posted on arXiv 16 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 1; 2022: 12; 2023: 14; 2024: 9; 2025: 5; 2026: 7.

49 papers.

Sort:

By area:

  1. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 85
  2. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  3. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  4. 2022Policy Gradient in Robust MDPs with Global Convergence Guaranteecited by 35
  5. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  6. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 31
  7. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  8. 2020Bayesian Robust Optimization for Imitation Learningcited by 28
  9. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  10. 2023Seeing is not Believing: Robust Reinforcement Learning against Spurious Correlationcited by 25
  11. 2023Robust Average-Reward Markov Decision Processescited by 22
  12. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 21
37 more
  1. 2023Model-Free Robust Average-Reward Reinforcement Learningcited by 20
  2. 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
  3. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  4. 2023Single-Trajectory Distributionally Robust Reinforcement Learningcited by 15
  5. 2022Robust Constrained Reinforcement Learningcited by 14
  6. 2023Reducing Blackwell and Average Optimality to Discounted MDPs via the Blackwell Discount Factorcited by 13
  7. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
  8. 2025Robust Gymnasium: A Unified Modular Benchmark for Robust Reinforcement Learningcited by 12
  9. 2023Robust Markov Decision Processes without Model Estimationcited by 11
  10. 2023Solving Long-run Average Reward Robust MDPs via Stochastic Gamescited by 10
  11. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  12. 2022On the convex formulations of robust Markov decision processescited by 8
  13. 2023Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularizationcited by 8
  14. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  15. 2024Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPscited by 7
  16. 2022The Geometry of Robust Value Functionscited by 6
  17. 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 6
  18. 2024Q-learning for Quantile MDPs: A Decomposition, Performance, and Convergence Analysiscited by 6
  19. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 6
  20. 2023An Efficient Solution to s-Rectangular Robust Markov Decision Processescited by 5
  21. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  22. 2022RASR: Risk-Averse Soft-Robust MDPs with EVaR and Entropic Riskcited by 4
  23. 2025Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processescited by 3
  24. 2024Solving Multi-Model MDPs by Coordinate Ascent and Dynamic Programmingcited by 2
  25. 2025Qualitative Analysis of ω-Regular Objectives on Robust MDPscited by 2
  26. 2022Robust Phi-Divergence MDPscited by 1
  27. 2023Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularizationcited by 1
  28. 2024Bootstrapping Expectiles in Reinforcement Learningcited by 1
  29. 2026Robust General Utility for Reinforcement Learningcited by 1
  30. 2026Robust Data-Collection Policy Learning for Low-Variance Online Policy Evaluationcited by 1
  31. 2022Gradient Optimization for Single-State RMDPscited by 0
  32. 2024Efficient Duple Perturbation Robustness in Low-rank MDPscited by 0
  33. 2026Distributionally Robust Cooperative Multi-Agent Reinforcement Learning via Robust Value Factorizationcited by 0
  34. 2026Robust Transfer Learning with Side Informationcited by 0
  35. 2026Solving Robust POMDPs with Omega-regular Objectives via Partially Observable Stochastic Gamescited by 0
  36. 2026Quantitative Analysis of ω-Regular Robust MDPscited by 0
  37. 2026Linear Programming Representations and Strongly Polynomial Algorithms for Robust Markov Decision Processescited by 0