Research map / Reinforcement learning / MDPs and planning
Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity
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 RP2G, a projected policy gradient method with decreasing inner tolerance for robust average-reward MDPs under general convex compact ambiguity sets, plus projected gradient and projected Langevin inner solvers for worst-case transition evaluation, with convergence guarantees.
Problem
Robust average-reward MDPs (RAMDPs) are hard to solve with policy gradients because the robust objective is non-differentiable and non-convex, and prior robust average-reward methods are restricted to rectangular ambiguity sets and need exact inner solves.
Approach
A nested gradient-descent-ascent scheme (RP2G) that alternates an inner worst-case transition solve with a decreasing tolerance and a projected policy gradient step; convergence is analyzed via weak convexity and Moreau envelope gradient dominance, and the inner problem is solved by projected gradient ascent (rectangular) or projected Langevin dynamics (general sets).
Key results
- On GARNET MDPs with (s,a)-rectangular ambiguity, RP2G's relative error to the optimum decreases to near zero over ~250 iterations across three problem sizes.
- RP2G runtime is 0.63s vs 13.99s for RPMD on G(5,3,3), and 12.54s vs 2711.79s on G(15,10,6) with 30 instances each.
- With ellipsoidal general ambiguity sets, RP2G achieves lower worst-case objective than non-robust policy gradient across 20 sample problems.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RP2G with a decreasing tolerance sequence instead of RPMD's fixed tolerance | Robust policy optimization · G(5, 3, 3) | runtime (seconds): 13.99(13.05) -> 0.63(0.35) | Helped |
| Use RP2G with a decreasing tolerance sequence instead of RPMD's fixed tolerance | Robust policy optimization · G(10, 5, 5) | runtime (seconds): 532.64(356.84) -> 2.48(0.90) | Helped |
| Use RP2G with a decreasing tolerance sequence instead of RPMD's fixed tolerance | Robust policy optimization · G(15, 10, 6) | runtime (seconds): 2711.79(849.00) -> 12.54(3.85) | Helped |
Limitations
- Analysis restricted to ergodic tabular MDPs
- General-ambiguity inner solver (Langevin) needs exponentially many iterations in AS^2 dimension
- Global convergence relies on an oracle for the inner problem with theoretical O(eps^-4) iteration complexity
Experimental setup
Datasets: GARNET MDPs
Benchmarks: GARNET MDPs
Metrics: relative error of objective average runtime worst-case objective Psi(pi)
Baselines: RPMD (robust policy mirror descent) robust value iteration non-robust policy gradient
Builds on: Kumar et al. 2024 average-reward policy gradient Agarwal et al. 2021 policy gradient for MDPs Cheng et al. 2024 sensitivity analysis Sun et al. 2024 robust policy mirror descent Li et al. 2023 Langevin for general ambiguity sets
Closest papers by meaning
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.93)
- Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.92)
- Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces (ICML 2024 · similarity 0.92)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.92)
- 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)
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.