Research map / Reinforcement learning / Policy gradient and actor-critic
ACPO: A Policy Optimization Algorithm for Average MDPs with Constraints
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 ACPO, a trust-region policy optimization algorithm for average-reward constrained MDPs, with new sensitivity-based performance and constraint-violation bounds, evaluated on MuJoCo-based Gather, Circle, Grid and Bottleneck tasks.
Problem
Reinforcement learning for constrained MDPs under the average-reward criterion, where discounted-CMDP methods (e.g., CPO) do not transfer well and scalable policy optimization for average-CMDPs has been lacking.
Approach
Derives average-reward policy improvement and constraint-violation bounds based on the mixing/sensitivity of stationary distributions (sigma-star from eigenvalues of the transition matrix, replacing discounted-style bounds), and uses them to build a CPO-style trust-region update with average-reward advantage estimation (average-reward GAE) and a recovery step with line search.
Key results
- ACPO improves average reward over CPO and PCPO by 52.5% and 36.1% respectively on Point-Gather, per the paper's reported averages.
- On Ant-Gather, ACPO shows 41.1% and 61.5% improvement over CPO and PCPO while satisfying the constraint.
- Lagrangian ATRPO and PPO fail to satisfy constraints on Ant-Circle, Ant-Gather, Bottleneck and Grid, and BVF-PPO fails to satisfy constraints even on Ant-Gather.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ACPO instead of CPO | Point-Gather · Point-Gather | average reward: +52.5% | Helped |
| Use ACPO instead of PCPO | Point-Gather · Point-Gather | average reward: +36.1% | Helped |
| Use ACPO instead of CPO | Ant-Gather · Ant-Gather | average reward: +41.1% | Helped |
| Use ACPO instead of PCPO | Ant-Gather · Ant-Gather | average reward: +61.5% | Helped |
| Use ACPO rather than Lagrangian ATRPO and PPO | average-CMDP policy optimization · Ant-Circle, Ant-Gather, Bottleneck, and Grid | average reward | Helped |
| Use ACPO rather than BVF-PPO | average-CMDP policy optimization · Ant-Gather, Bottleneck, and Grid | constraint satisfaction | Helped |
| Set recovery parameter t to 0.75 instead of using the cost-only recovery scheme (t=1) (ablation) | ACPO · OpenAI Gym tasks | reward and constraint performance | Helped |
| Use the cost-only recovery scheme (t=1) (ablation) | ACPO · OpenAI Gym tasks | reward and constraint performance | Mixed |
Surprising findings
- Setting gamma to 1 in CPO does not perform well on average-CMDPs even with a large discount factor.
- The discounted performance bound trivializes (right-hand side goes to negative infinity) as gamma approaches 1, so it cannot be used in the average setting.
Limitations
- Experiments use only a single constraint in the practical implementation, though the method can in principle handle multiple.
- Constraint violations remain in the high-dimensional Grid and Bottleneck environments.
- Step size is small (1e-4), and the approach may take steps too small, degrading convergence.
Experimental setup
Benchmarks: OpenAI Gym MuJoCo Point-Gather Point-Circle Ant-Gather Ant-Circle Grid Bottleneck
Metrics: average reward average constraint cost
Baselines: CPO ATRPO PCPO BVF-PPO PPO
Builds on: CPO ATRPO TRPO PCPO
Closest papers by meaning
- Confident Natural Policy Gradient for Local Planning in $q_\pi$-realizable Constrained MDPs (NeurIPS 2024 · similarity 0.88)
- Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm (NeurIPS 2024 · similarity 0.88)
- Simple Policy Optimization (ICML 2025 · similarity 0.87)
- Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation (NeurIPS 2025 · similarity 0.87)
- Reflective Policy Optimization (ICML 2024 · similarity 0.87)
- Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL (NeurIPS 2025 · similarity 0.87)
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.