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

arXiv:2606.25012v1 Announce Type: new Abstract: 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^pi_{r_1}, ldots, J^pi_{r_M}) subject to a scalarized constraint g(J^pi_{c_1}, ldots, J^pi_{c_N}) ge 0 , where J^pi_{r_m} and J^pi_{c_n} denote the average-reward and cost under policy pi. 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^pi, and E[partial f(J^pi)] neq partial f(E[J^pi]), 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 ilde{O}(1/sqrt{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.

Source: arXiv cs.LG | 2026-06-25