mlsanityData to 14 Oct 2026

Efficient Policy Iteration for Robust Markov Decision Processes via Regularization

arXiv 2205.14327 ↗First posted 28 May 2022cs.AIcited by 20

Not on the map. Why?

Abstract (arXiv)

Robust Markov decision processes (MDPs) provide a general framework to model decision problems where the system dynamics are changing or only partially known. Efficient methods for some textttsa-rectangular robust MDPs exist, using its equivalence with reward regularized MDPs, generalizable to online settings. In comparison to textttsa-rectangular robust MDPs, texttts-rectangular robust MDPs are less restrictive but much more difficult to deal with. Interestingly, recent works have established the equivalence between texttts-rectangular robust MDPs and policy regularized MDPs. But we don't have a clear understanding to exploit this equivalence, to do policy improvement steps to get the optimal value function or policy. We don't have a clear understanding of greedy/optimal policy except it can be stochastic. There exist no methods that can naturally be generalized to model-free settings. We show a clear and explicit equivalence between texttts-rectangular Lp robust MDPs and policy regularized MDPs that resemble very much policy entropy regularized MDPs widely used in practice. Further, we dig into the policy improvement step and concretely derive optimal robust Bellman operators for texttts-rectangular Lp robust MDPs. We find that the greedy/optimal policies in texttts-rectangular Lp robust MDPs are threshold policies that play top k actions whose Q value is greater than some threshold (value), proportional to the (p-1)th power of its advantage. In addition, we show time complexity of (textttsa and texttts-rectangular) Lp robust MDPs is the same as non-robust MDPs up to some log factors. Our work greatly extends the existing understanding of texttts-rectangular robust MDPs and naturally generalizable to online settings.

Key facts. Cited by 20 papers in the map (data through 14 Oct 2026). Builds on 15 of its 31 references that are in the map. First posted on arXiv 28 May 2022.

Builds on

15 of 31 references.

References · 15

  1. 2017Reinforcement Learning with Deep Energy-Based Policiescited by 669
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2021Maximum Entropy RL (Provably) Solves Some Robust RL Problemscited by 176
  4. 2017Equivalence Between Policy Gradients and Soft Q-Learningcited by 173
  5. 2018Assessing Generalization in Deep Reinforcement Learningcited by 133
  6. 2021Online Robust Reinforcement Learning with Model Uncertaintycited by 96
  7. 2022Policy Gradient Method For Robust Reinforcement Learningcited by 69
  8. 2020Partial Policy Iteration for L1-Robust Markov Decision Processescited by 50
  9. 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 47
  10. 2020Distributional Robustness and Regularization in Reinforcement Learningcited by 40
  11. 2021Regularized Policies are Reward Robustcited by 32
  12. 2018Robust Markov Decision Process: Beyond Rectangularitycited by 24
3 more
  1. 2019Model-Based Reinforcement Learning Exploiting State-Action Equivalencecited by 6
  2. 2017k*-Nearest Neighbors: From Global to Localcited by 4
  3. 2021Robust Entropy-regularized Markov Decision Processescited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 7; 2024: 6; 2025: 3; 2026: 1.

20 papers.

Sort:

By area:

  1. 2023Natural Actor-Critic for Robust Reinforcement Learning with Function Approximationcited by 36
  2. 2022First-order Policy Optimization for Robust Markov Decision Processcited by 32
  3. 2023Policy Gradient for Rectangular Robust Markov Decision Processescited by 31
  4. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  5. 2023Bridging Distributionally Robust Learning and Offline RL: An Approach to Mitigate Distribution Shift and Partial Data Coveragecited by 12
  6. 2022Robust Reinforcement Learning with Distributional Risk-averse formulationcited by 10
  7. 2022On the convex formulations of robust Markov decision processescited by 10
  8. 2024Near-Optimal Policy Identification in Robust Constrained Markov Decision Processes via Epigraph Formcited by 10
  9. 2023Bring Your Own (Non-Robust) Algorithm to Solve Robust MDPs by Estimating The Worst Kernelcited by 8
  10. 2023Solving Non-Rectangular Reward-Robust MDPs via Frequency Regularizationcited by 8
  11. 2024Roping in Uncertainty: Robustness and Regularization in Markov Gamescited by 5
  12. 2025Adversarial Diffusion for Robust Reinforcement Learningcited by 4
8 more
  1. 2024Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processescited by 3
  2. 2024Sequential Decision-Making under Uncertainty: A Robust MDPs reviewcited by 2
  3. 2024RRLS : Robust Reinforcement Learning Suitecited by 2
  4. 2025Session-Level Dynamic Ad Load Optimization using Offline Robust Reinforcement Learningcited by 2
  5. 2023Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularizationcited by 1
  6. 2024Bootstrapping Expectiles in Reinforcement Learningcited by 1
  7. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  8. 2025ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertaintycited by 0