Research map / Optimization / Nonconvex and smooth optimization
Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces
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 an accelerated policy gradient method for s-rectangular robust MDPs via entropy regularization, achieving O(ϵ^-3 ln ϵ^-1) iteration complexity in the deterministic setting and extending to stochastic and large-state-space settings with O(ϵ^-7 ln ϵ^-1) sample complexity.
Problem
Global convergence of policy gradient for s-rectangular robust MDPs is slow (O(ϵ^-4) iteration complexity) and existing methods are limited to deterministic exact-gradient settings with small state spaces.
Approach
Apply entropy regularization to the robust MDP so the dual objective max_p min_π J_{ρ,τ} is smooth (Lipschitz gradient and gradient dominance), then run projected gradient ascent on the transition kernel with inner NPG policy updates; extend to stochastic TD/sample-average estimates and to large state spaces via linear kernel parameterization and linear Q approximation.
Key results
- Deterministic Algorithm 1 achieves O(ϵ^-3 ln ϵ^-1) iteration complexity versus prior O(ϵ^-4) (Guha and Lee 2023) for s-rectangular robust MDPs.
- Stochastic Algorithm 2 achieves O(ϵ^-7 ln ϵ^-1) sample complexity, the first sample complexity result for policy gradient on s-rectangular robust MDPs.
- Large-state-space Algorithm 3 retains O(ϵ^-7 ln ϵ^-1) sample complexity up to a linear Q approximation error term ζ.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use entropy regularization and accelerated policy gradient instead of directly optimizing the non-differentiable objective | s-rectangular robust MDP · s-rectangular robust MDP, deterministic | iteration complexity: O(ϵ−4) -> O(ϵ−3 ln ϵ−1) | Helped |
| Extend the algorithm to stochastic gradients and sample-based updates | Algorithm 1 · s-rectangular robust MDP, stochastic | sample complexity | Mixed |
| Add linear transition-kernel parameterization and linear Q-function approximation | Algorithm 2 · s-rectangular robust MDP, stochastic, large state space | sample complexity: O(ϵ−7 ln ϵ−1) | Mixed |
| Use linear Q-function approximation | Algorithm 3 · s-rectangular robust MDP, large state space | convergence error: O(√ζ + ζ + ϵ) | Hurt |
Limitations
- Smoothness constant scales as O(τ^-1), forcing small stepsize and yielding iteration/sample complexities that are not minimax optimal.
- Large-state results carry an additional linear Q function approximation error ζ.
- Assumes s-rectangular, compact, convex ambiguity set and an inf transition lower bound p_min for the large-space analysis.
Experimental setup
Metrics: iteration complexity sample complexity
Baselines: Wang et al. 2023 Li et al. 2023b Kumar et al. 2023c Guha and Lee 2023
Builds on: Wang et al. 2023 double-loop robust policy gradient Cen et al. 2022 entropy-regularized NPG Mai and Jaillet 2021 entropy regularized robust MDP duality Li et al. 2023a TD convergence
Closest papers by meaning
- A Single-Loop Robust Policy Gradient Method for Robust Markov Decision Processes (ICML 2024 · similarity 0.93)
- Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity (ICML 2025 · similarity 0.92)
- Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity (ICLR 2024 · similarity 0.91)
- Efficient Value Iteration for s-rectangular Robust Markov Decision Processes (ICML 2024 · similarity 0.91)
- Policy Optimization for Robust Average Reward MDPs (NeurIPS 2024 · similarity 0.89)
- Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization (AAAI 2024 · similarity 0.89)
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.