Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper addresses the challenge of achieving order-optimal convergence in average-reward Constrained Markov Decision Processes (CMDPs) with neural critics, which has been a significant barrier in reinforcement learning for safety-critical applications. By introducing a hierarchical Multilevel Monte Carlo (MLMC) neural critic that simultaneously reduces bias and optimizes cost, the authors achieve a novel estimator that provides the bias of a long critic optimization run with logarithmic expected sample cost. The resulting primal-dual Natural Actor-Critic algorithm demonstrates an optimality gap and constraint violation of order $\tilde{O}(T^{-1/2})$, marking a breakthrough in convergence guarantees for CMDPs with neural critics.
Achieving order-optimal convergence in average-reward CMDPs with neural critics could redefine the performance benchmarks for safety-critical reinforcement learning applications.
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.