# Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL

arXiv: https://arxiv.org/abs/2606.25012 · HTML: https://mlsanity.com/paper/2606.25012/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 25 of its 38 references that are in the map.
- First posted on arXiv 23 Jun 2026.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 25 of 25)

- [A Practical Guide to Multi-Objective Reinforcement Learning and Planning](https://mlsanity.com/paper/2103.09568/) (2021)
- [A Finite Time Analysis of Two Time-Scale Actor Critic Methods](https://mlsanity.com/paper/2005.01350/) (2020)
- [Stochastic Variance-Reduced Policy Gradient](https://mlsanity.com/paper/1806.05618/) (2018)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methods](https://mlsanity.com/paper/2211.07937/) (2022)
- [Sample Efficient Policy Gradient Methods with Recursive Variance Reduction](https://mlsanity.com/paper/1909.08610/) (2019)
- [Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policies](https://mlsanity.com/paper/2302.01734/) (2023)
- [Finite-time analysis of single-timescale actor-critic](https://mlsanity.com/paper/2210.09921/) (2022)
- [Learning Infinite-Horizon Average-Reward Markov Decision Processes with Constraints](https://mlsanity.com/paper/2202.00150/) (2022)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes](https://mlsanity.com/paper/2309.01922/) (2023)
- [Concave Utility Reinforcement Learning with Zero-Constraint Violations](https://mlsanity.com/paper/2109.05439/) (2021)
- [Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic](https://mlsanity.com/paper/2301.12083/) (2023)
- [Reinforcement Learning for Joint Optimization of Multiple Rewards](https://mlsanity.com/paper/1909.02940/) (2019)
- [Anchor-Changing Regularized Natural Policy Gradient for Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2206.05357/) (2022)
- [A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach](https://mlsanity.com/paper/2407.18878/) (2024)
- [A Survey of Safe Reinforcement Learning and Constrained MDPs: A Technical Survey on Single-Agent and Multi-Agent Safety](https://mlsanity.com/paper/2505.17342/) (2025)
- [Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm](https://mlsanity.com/paper/2105.14125/) (2021)
- [Non-Asymptotic Analysis for Single-Loop (Natural) Actor-Critic with Compatible Function Approximation](https://mlsanity.com/paper/2406.01762/) (2024)
- [Learning General Parameterized Policies for Infinite Horizon Average Reward Constrained MDPs via Primal-Dual Policy Gradient Algorithm](https://mlsanity.com/paper/2402.02042/) (2024)
- [Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm](https://mlsanity.com/paper/2505.15138/) (2025)
- [Two-Timescale Critic-Actor for Average Reward MDPs with Function Approximation](https://mlsanity.com/paper/2402.01371/) (2024)
- [RL-MPCA: A Reinforcement Learning Based Multi-Phase Computation Allocation Approach for Recommender Systems](https://mlsanity.com/paper/2401.01369/) (2023)
- [Breaking the Bias Barrier in Concave Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2603.08518/) (2026)

## Abstract (arXiv)

Many reinforcement learning (RL) problems in the infinite-horizon average-reward setting require optimizing multiple conflicting objectives while satisfying multiple safety constraints. A common approach is concave scalarization, where the agent maximizes a utility  f(Jπr1, ldots, JπrM)  subject to a scalarized constraint  g(Jπc1, ldots, JπcN) ≥ 0 , where Jπrm and Jπcn denote the average-reward and cost under policy π. However, the nonlinearity of f and g introduces bias in policy-gradient and actor-critic methods, since gradients must be evaluated using noisy estimates of Jπ, and  mathbbE[partial f(Jπ)] neq partial f(mathbbE[Jπ]), and this bias propagates through both primal and dual updates. We propose an MLMC-based primal-dual Natural Actor-Critic algorithm for average-reward MDPs that controls bias in scalarized objectives, constraint evaluation, and actor-critic estimation without requiring mixing-time knowledge. We show that the algorithm achieves optimal global convergence and constraint-violation rates of  tildeO(1/√T) . To our knowledge, this is the first result establishing optimal convergence for concave scalarized multi-objective RL in the average-reward setting, both with and without constraints, and the first to do so without mixing-time information even in the absence of scalarization.