Research map / Reinforcement learning / MDPs and planning

Deterministic Policy Gradient Primal-Dual Methods for Continuous-Space Constrained MDPs

AAAI 2025 · Reinforcement learning › MDPs and planning · approach: Average-reward and regularized MDPs · 2 citations (OpenAlex)

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 D-PGPD, a quadratic-regularized deterministic policy gradient primal-dual method (plus function-approximation and sample-based variants) for continuous-state-action constrained MDPs, with linear convergence to a neighborhood of regularized saddle points, validated on navigation and fluid control.

Problem

Finding optimal deterministic policies for constrained MDPs with continuous state and action spaces, where the lack of enumerable state-action pairs and deterministic policies hinder standard policy gradient methods.

Approach

Regularize the Lagrangian with a quadratic action penalty and quadratic dual penalty, then run a proximal-point-type deterministic primal ascent step and a gradient-descent dual step; under non-atomicity the deterministic value image is convex, giving zero duality gap for deterministic policies.

Key results

• On the navigation problem, AD-PGPD converges to a feasible solution with low variance over 40,000 iterations, while PGDual shows large variance and violates the constraint in the last iterate.
• On fluid velocity control over 10,000 iterations, AD-PGPD damps oscillations and converges to a feasible solution with low return variance, whereas PGDual does not dampen oscillations.
• Theory: the primal-dual potential function converges linearly up to an O(epsilon) neighborhood; epsilon-optimality after Omega(epsilon^-6) iterations, and sample complexity Omega(epsilon^-18) rollouts.

Measured effects reported in the paper

Surprising findings

• PGDual achieves final primal return similar to AD-PGPD on average, yet its iterates violate the constraint due to high variance.

Limitations

• Relies on concavity and Lipschitz assumptions on regularized action-value functions, which may not hold in general.
• Convergence is only to a neighborhood whose size depends on regularization and step size; the near-optimality bounds scale with the regularization.
• Sample-based convergence requires very large numbers of rollouts (Omega(epsilon^-18)).

Experimental setup

Benchmarks: constrained robot navigation (simulated) fluid velocity control (Burgers' equation)

Metrics: average reward value function average utility value function variance of iterates / constraint satisfaction

Baselines: PGDual

Builds on: PGDual performance difference lemma occupancy measure LP formulation of constrained MDPs

Closest papers by meaning

• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.90)
• Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (NeurIPS 2026 · similarity 0.90)
• Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.90)
• Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.89)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients (ICML 2024 · similarity 0.89)
• Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · similarity 0.89)