Research map / Reinforcement learning / MDPs and planning
Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
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 a primal-dual natural actor-critic with MLMC-based gradient estimates for infinite-horizon average-reward CMDPs under general parametrization, achieving O~(1/sqrt(T)) global optimality gap and constraint violation (known mixing time) and O~(T^{-(0.5-eps)}) without mixing-time knowledge.
Problem
Global convergence and constraint violation for infinite-horizon average-reward constrained MDPs with general parametrized policies, where prior best rate was O~(T^{-1/5}).
Approach
Combines a primal-dual natural actor-critic with nested inner loops for critic and NPG estimation, using geometric-length MLMC trajectory estimators so that mixing time need not be known and the inner loop length H can be kept small (near-single-timescale with K ~ T), yielding O(1/sqrt(T)) rates.</multeridea>
Key results
- Achieves O~(1/sqrt(T)) global convergence and constraint violation when mixing time is known (Theorem with H~tau_mix^2, K=T/H).
- Without mixing-time knowledge, achieves O~(T^{-(0.5-eps)}) provided T >= O~(tau_mix^{2/eps}).
- Improves on prior general-parameterization average-reward CMDP rate of O~(1/T^{1/5}).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use PDNAC with known mixing time instead of Algorithm 1 in [cite] | Average-reward CMDP with general parameterization · Average-reward CMDP, general parameterization, known mixing time | global convergence rate: $\tilde{\mathcal{O}}\bigg(1/T^{1/5}\bigg)$ -> $\tilde{\mathcal{O}}\bigg(1/\sqrt{T}\bigg)$ | Helped |
| Use PDNAC with known mixing time instead of Algorithm 1 in [cite] | Average-reward CMDP with general parameterization · Average-reward CMDP, general parameterization, known mixing time | constraint violation rate: $\tilde{\mathcal{O}}\bigg(1/T^{1/5}\bigg)$ -> $\tilde{\mathcal{O}}\bigg(1/\sqrt{T}\bigg)$ | Helped |
| Use PDNAC without assuming mixing time is known instead of Algorithm 1 in [cite] | Average-reward CMDP with general parameterization · Average-reward CMDP, general parameterization, unknown mixing time | global convergence rate: $\tilde{\mathcal{O}}\bigg(1/T^{1/5}\bigg)$ -> $\tilde{\mathcal{O}}\bigg(1/T^{0.5-\epsilon}\bigg)$ | Helped |
| Use PDNAC without assuming mixing time is known instead of Algorithm 1 in [cite] | Average-reward CMDP with general parameterization · Average-reward CMDP, general parameterization, unknown mixing time | constraint violation rate: $\tilde{\mathcal{O}}\bigg(1/T^{1/5}\bigg)$ -> $\tilde{\mathcal{O}}\bigg(1/T^{0.5-\epsilon}\bigg)$ | Helped |
Limitations
- Ergodicity assumption required for all policies.
- Without known mixing time, the horizon requirement T >= tau_mix^{2/eps} can be large and the rate is slightly suboptimal.
- Residual approximation errors epsilon_bias and epsilon_app prevent zero gap even for large T.
Experimental setup
Metrics: global optimality gap average constraint violation
Baselines: Algorithm 1 in prior general-parameterization average-reward CMDP work (O(1/T^{1 tabular model-based CMDP methods (UC-CURL, PS-CURL) Triple-QA
Builds on: natural policy gradient MLMC-based actor-critic for average reward MDPs Lagrangian primal-dual CMDP methods
Closest papers by meaning
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.95)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.92)
- On the Convergence of Single-Timescale Actor-Critic (NeurIPS 2025 · similarity 0.91)
- Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach (NeurIPS 2025 · similarity 0.91)
- Sample-Efficient Constrained Reinforcement Learning with General Parameterization (NeurIPS 2024 · similarity 0.90)
- Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs (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.