Research map / Reinforcement learning / MDPs and planning
Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient 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 policy gradient algorithm for infinite-horizon average-reward ergodic CMDPs with general policy parameterization, achieving Õ(T^{4/5}) regret and constraint violation.
Problem
Regret and constraint violation analysis for infinite-horizon average-reward constrained MDPs under general (neural) policy parameterization, where prior work covered only tabular or linear MDPs.
Approach
A model-free primal-dual policy gradient method that estimates advantages from sub-trajectories within epochs of length H ~ T^xi, updates the policy parameters by gradient ascent on the Lagrangian and the multiplier by projected descent using a biased cost estimate that drops the first N samples of each epoch; the analysis handles the lack of strong duality under general parameterization.
Key results
- Achieves Õ(T^{4/5}) expected regret for average-reward CMDPs with general parameterization, improving the Õ(T^{5/6}) model-free tabular bound.
- Achieves Õ(T^{4/5}) expected constraint violation under the same setting.
- Convergence rates of Õ(T^{-1/5}) for both the objective optimality gap and the constraint violation averages (theorem with beta = T^{-2/5}, xi = 2/5).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Primal-Dual Parameterized Policy Gradient instead of Triple-QA | Average reward CMDP · Average reward CMDP, tabular vs. general parameterization | regret: \tilde{\mathcal{O}}(T^{5/6}) -> \tilde{\mathcal{O}}(T^{4/5}) | Helped |
Surprising findings
- Strong duality does not hold under general parameterization, so dual convergence does not directly transfer to primal convergence; the paper introduces a separate constraint violation analysis to handle this.
Limitations
- Regret bound (T^{4/5}) is worse than the T^{3/4} unconstrained general-parameterization result gap, and the paper notes this gap remains open.
- Requires knowledge of the mixing time and the horizon T.
- Assumes ergodicity, and relies on a bounded compatible function approximation error (epsilon_bias) that is nonzero for restricted policy classes.
Experimental setup
Metrics: regret constraint violation
Baselines: Triple-QA UC-CURL PS-CURL model-based CMDP algorithms for average reward
Builds on: policy gradient theorem primal-dual CMDP methods model-free advantage estimation for average reward MDPs
Closest papers by meaning
- Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm (NeurIPS 2025 · similarity 0.95)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.95)
- Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret (NeurIPS 2026 · similarity 0.91)
- Efficient Exploration in Average-Reward Constrained Reinforcement Learning: Achieving Near-Optimal Regret With Posterior Sampling (ICML 2024 · similarity 0.91)
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation (ICLR 2024 · similarity 0.91)
- Achieving Tractable Minimax Optimal Regret in Average Reward MDPs (NeurIPS 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.