mlsanityData to 7 Oct 2026

First-order Policy Optimization for Robust Markov Decision Process

arXiv 2209.10579 ↗First posted 21 Sep 2022cs.LG cs.AI math.OCcited by 31

Not on the map. Why?

Abstract (arXiv)

We consider the problem of solving robust Markov decision process (MDP), which involves a set of discounted, finite state, finite action space MDPs with uncertain transition kernels. The goal of planning is to find a robust policy that optimizes the worst-case values against the transition uncertainties, and thus encompasses the standard MDP planning as a special case. For (s,a)-rectangular uncertainty sets, we establish several structural observations on the robust objective, which facilitates the development of a policy-based first-order method, namely the robust policy mirror descent (RPMD). An O(log(1/ε)) iteration complexity for finding an ε-optimal policy is established with linearly increasing stepsizes. We further develop a stochastic variant of the robust policy mirror descent method, named SRPMD, when the first-order information is only available through online interactions with the nominal environment. We show that the optimality gap converges linearly up to the noise level, and consequently establish an tildeO(1/ε2) sample complexity by developing a temporal difference learning method for policy evaluation. Both iteration and sample complexities are also discussed for RPMD with a constant stepsize. To the best of our knowledge, all the aforementioned results appear to be new for policy-based first-order methods applied to the robust MDP problem.

Key facts. Cited by 31 papers in the map (data through 7 Oct 2026). Builds on 23 of its 55 references that are in the map. First posted on arXiv 21 Sep 2022.

Builds on

23 of 55 references.

References · 23

  1. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,173
  2. 2018Robustness May Be at Odds with Accuracycited by 873
  3. 2017Overcoming Exploration in Reinforcement Learning with Demonstrationscited by 322
  4. 2020Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularizationcited by 170
  5. 2021Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classescited by 149
  6. 2022On the Convergence Rates of Policy Gradient Methodscited by 115
  7. 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
  8. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 95
  9. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
  10. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 82
  11. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 67
  12. 2021A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variantscited by 57
11 more
  1. 2017Reinforcement Learning under Model Mismatchcited by 52
  2. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 49
  3. 2021On the Linear convergence of Natural Policy Gradient Algorithmcited by 48
  4. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
  5. 2022Distributionally Robust Offline Reinforcement Learning with Linear Function Approximationcited by 31
  6. 2020Scalable First-Order Methods for Robust MDPscited by 22
  7. 2022Efficient Policy Iteration for Robust Markov Decision Processes via Regularizationcited by 19
  8. 2019A First-Order Approach To Accelerated Value Iterationcited by 16
  9. 2020Improving Sample Complexity Bounds for (Natural) Actor-Critic Algorithmscited by 14
  10. 2022Homotopic Policy Mirror Descent: Policy Convergence, Implicit Regularization, and Improved Sample Complexitycited by 14
  11. 2020Risk-Averse Learning by Temporal Difference Methodscited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 2; 2023: 11; 2024: 6; 2025: 8; 2026: 4.

31 papers.

Sort:

By area:

  1. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 50
  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. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 29
  5. 2023Robust Multi-Agent Reinforcement Learning via Adversarial Regularization: Theoretical Foundation and Stable Algorithmscited by 25
  6. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 24
  7. 2022Policy Optimization over General State and Action Spacescited by 21
  8. 2023Policy Gradient Algorithms for Robust MDPs with Non-Rectangular Uncertainty Setscited by 15
  9. 2024Distributionally Robust Constrained Reinforcement Learning under Strong Dualitycited by 15
  10. 2023Provably Fast Convergence of Independent Natural Policy Gradient for Markov Potential Gamescited by 12
  11. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  12. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 12
19 more
  1. 2023Policy Mirror Descent Inherently Explores Action Spacecited by 11
  2. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  3. 2023Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularizationcited by 8
  4. 2023First-order Policy Optimization for Robust Policy Evaluationcited by 6
  5. 2025Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learningcited by 6
  6. 2024Tiny Multi-Agent DRL for Twins Migration in UAV Metaverses: A Multi-Leader Multi-Follower Stackelberg Game Approachcited by 4
  7. 2025Rectified Robust Policy Optimization for Model-Uncertain Constrained Reinforcement Learning without Strong Dualitycited by 4
  8. 2023Connected Superlevel Set in (Deep) Reinforcement Learning and its Application to Minimax Theoremscited by 3
  9. 2024Policy Gradient for Robust Markov Decision Processescited by 3
  10. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learningcited by 2
  11. 2025Primal-Only Actor Critic Algorithm for Robust Constrained Average Cost MDPscited by 1
  12. 2025Online Robust Reinforcement Learning with General Function Approximationcited by 1
  13. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  14. 2026Value Mirror Descent for Reinforcement Learningcited by 1
  15. 2026Non-Asymptotic Convergence of Stochastic Iterative Algorithms: A Lyapunov Frameworkcited by 1
  16. 2025Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximationcited by 0
  17. 2025ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertaintycited by 0
  18. 2025Robust Reinforcement Learning in Finance: Modeling Market Impact with Elliptic Uncertainty Setscited by 0
  19. 2026Natural Policy Gradient as Doubly Smoothed Policy Iteration: A Bellman-Operator Frameworkcited by 0