Research map / Reinforcement learning / MDPs and planning
A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes SRPG, a single-loop primal-dual policy gradient method with Moreau-Yosida smoothing for s-rectangular robust MDPs, achieving O(1/ε^4) complexity under a new gradient dominance property.
Problem
Solving s-rectangular robust MDPs with policy gradient methods efficiently; existing policy gradient approaches for general s-rectangular RMDPs use nested loops with high computational cost.
Approach
Single-loop primal-dual gradient method on a Moreau-Yosida regularized minimax formulation, where auxiliary variables are exponentially averaged; uses a gradient dominance property of the dual (transition) function to handle nonconvex-nonconcave saddle structure, plus a regional exponential growth analysis.
Key results
- SRPG converges consistently and significantly faster than DRPG across all 8 GARNET tasks in average worst-case return.
- On the inventory problem with policy and transition parameterization, SRPG reaches DRPG's objective in substantially less runtime (e.g., 1,518 vs 9,377 for S=200, A=20).
- Theoretical complexity O(1/ε^4) for global convergence, versus DRPG's nested-loop cost.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use single-loop SRPG instead of double-loop DRPG | Inventory management with policy and transition-kernel parameterization · Inventory management | runtime: 9,377.126 -> 1,517.999; 12,758.126 -> 4,719.497; 35,108.616 -> 3,737.307; 7,605.747 -> 1,764.330; 16,725.184 -> 5,852.93 | Helped |
| use single-loop SRPG instead of double-loop DRPG | GARNET MDPs · GARNET MDPs, eight tasks | worst-case expected return | Helped |
| use single-loop SRPG instead of double-loop DRPG | Inventory management with transition-kernel parameterization · Inventory management | worst-case expected return | Helped |
| use single-loop SRPG instead of double-loop DRPG | Inventory management with policy and transition-kernel parameterization · Inventory management | runtime | Helped |
| update the policy within the loop rather than leaving it unchanged during the inner loop | Robust policy gradient on GARNET MDPs · GARNET MDPs | convergence stability | Helped |
Surprising findings
- DRPG oscillates in the last GARNET figure because the policy is not updated during its inner loop, causing large dual changes.
Limitations
- Analysis is for exact gradients; noisy gradients and function approximation not covered.
- Convergence rate O(1/ε^4) does not improve in ε over DRPG; improvement is in per-iteration cost.
- Requires tuning of stepsizes and extrapolation parameters.
Experimental setup
Datasets: GARNET MDPs (synthetic) inventory management problem (synthetic)
Benchmarks: GARNET(5,6,3) GARNET(10,5,10) inventory management problem
Metrics: worst-case expected return phi(pi_k) runtime to reach same objective
Baselines: DRPG
Builds on: DRPG Moreau-Yosida smoothing primal-dual method Lyapunov analysis of GDA-type methods
Closest papers by meaning
- Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces (ICML 2024 · similarity 0.93)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.93)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.91)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.91)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.91)
- On the Complexity of Discounted Robust MDPs with $L_p$ Uncertainty Sets (NeurIPS 2026 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.