Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization

Anirudh Satheesh; Pankaj Kumar Barman; Washim Uddin Mondal; Vaneet Aggarwal

cs.LGMar 8, 2026

Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization

Authors: Anirudh Satheesh, Pankaj Kumar Barman, Washim Uddin Mondal, Vaneet Aggarwal

Organizations: Department of Computer Science, University of Maryland, College Park, MD 20740, USA · Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India · Department of Electrical Engineering, Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India · Department of Industrial Engineering, Purdue University, West Lafayette, IN 47907, USA

Abstract

We study infinite-horizon Constrained Markov Decision Processes (CMDPs) with general policy parameterizations and multi-layer neural network critics. Existing theoretical analyses for constrained reinforcement learning largely rely on tabular policies or linear critics, which limits their applicability to high-dimensional and continuous control problems. We propose a primal-dual natural actor-critic algorithm that integrates neural critic estimation with natural policy gradient updates and leverages Neural Tangent Kernel (NTK) theory to control function-approximation error under Markovian sampling, without requiring access to mixing-time oracles. We establish global convergence and cumulative constraint violation rates of $\tilde{\mathcal{O}}(T^-1/4)$ up to approximation errors induced by the policy and critic classes. Our results provide the first such guarantees for CMDPs with general policies and multi-layer neural critics, substantially extending the theoretical foundations of actor-critic methods beyond the linear-critic regime.

Figures & tables

References	Global Convergence	Violation	Reward Setting	Infinite State Action Space	Mixing Time Unknown?	Critic Parameterization	Policy Parameterization
( Cayci et al., 2024 )	$\tilde{\mathcal{O}}(T^{-1/5})$	N/A	Discounted	✗	✓	Multi layer NN	Multi layer NN
( Gaur et al., 2024 )	$\tilde{\mathcal{O}}(T^{-1/3})$	N/A	Discounted	✓	✓	Multi layer NN	General
( Ganesh et al., 2025 )	$\tilde{\mathcal{O}}(T^{-1/2})$	N/A	Discounted	✓	✗	Multi layer NN	General
( Mondal and Aggarwal, 2024b )	$\tilde{\mathcal{O}}(T^{-1/2})$	$\tilde{\mathcal{O}}(T^{-1/2})$	Discounted	✓	✓	N/A	General
( Agarwal et al., 2022b ; Agarwal et al., 2022a )	$\tilde{\mathcal{O}}(T^{-1/2})$	0	Average	✗	✗	Tabular	Tabular
( Ghosh et al., 2023 )	$\tilde{\mathcal{O}}(T^{-1/2})$	$\tilde{\mathcal{O}}(T^{-1/2})$	Average	✓	✗	Linear MDP	Tabular

Table 1: Comparison of relevant algorithms for infinite-horizon average-reward Reinforcement Learning in the model-free setting. Our work is the first to provide average reward global convergence and constraint violation results for constrained MDPs with general policy and multi-layer neural network critic parametrization. We provide a more detailed comparison to prior work in Appendix A .

Natural Policy Gradient

See all 13 papers

Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs
Jul 30, 2026Ankur Naskar, Vaneet AggarwalAverage-Reward RL Constrained RL
Indian Institute of Science, India · Purdue University, USA
Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs
May 12, 2026Michael Lu, Max Qiushi Lin, Mo Chen +1Markov Decision Processes Last-Iterate Convergence
Simon Fraser University
Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
Jun 23, 2026Ankur Naskar, Swetha Ganesh, Vaneet AggarwalMulti-Objective Reinforcement Learning Reinforcement Learning
Indian Institute of Science, Bengaluru, India · Purdue University, USA

Jul 30, 2026J/K move · Enter open · S save

Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs

Ankur Naskar, Vaneet Aggarwal

Indian Institute of Science, India · Purdue University, USA

Average-Reward RL Constrained RL Actor-Critic Methods Policy Learning Variance Reduction

Open paper AskPDF arXiv

Constrained Markov Decision Processes (CMDPs) provide a natural framework for reinforcement learning in safety-critical applications, where agents maximize long-term reward while satisfying long-term constraints. Although primal-dual actor-critic methods with linear critics are well understood, extending order-optimal convergence guarantees to neural critics in average-reward CMDPs has remained open. The main challenge is a fundamental bias-cost trade-off in neural critic estimation: under Neural Tangent Kernel (NTK) analysis, reducing critic bias substantially increases critic optimization cost, preventing order-optimal convergence in the primal-dual framework. We resolve this bottleneck by introducing a hierarchical Multilevel Monte Carlo (MLMC) neural critic that performs debiasing simultaneously across trajectory sampling and critic optimization. The resulting estimator attains the bias of a long critic optimization run with only logarithmic expected sample cost. Building on this estimator, we develop a primal-dual Natural Actor-Critic algorithm that achieves both an optimality gap and a constraint violation of order

\tilde{O}(T^{-1/2})

. This establishes the first order-optimal convergence guarantees for infinite-horizon average-reward CMDPs with general policy parameterization and neural critics, while eliminating the need to know the underlying mixing time. Our results are novel even in the unconstrained setting.

Abstract

Natural Policy Gradient

Explore similar work

Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs

Augmented Lagrangian Method for Last-Iterate Convergence for Constrained MDPs

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