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

2026/07/30 by Ankur Naskar, Vaneet Aggarwal
Computer Science · #cs.LG

paper · pdf

arxiv created 2026/07/30 · arxiv updated 2026/07/31

Abstract

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 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.

Citations

• A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
• Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles
• Reinforced Sequential Decision-Making for Sepsis Treatment: The POSNEGDM Framework with Mortality Classifier and Transformer
• Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Control
• Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs
• Adapting to Mixing Time in Stochastic Optimization with Markovian Data
• Towards Tight Bounds on the Sample Complexity of Average-reward MDPs
• Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm
• CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guarantee
• A Distributed Model-Free Ride-Sharing Approach for Joint Matching, Pricing, and Dispatching using Deep Reinforcement Learning
• Single-Timescale Actor-Critic Provably Finds Globally Optimal Policy
• Constrained Reinforcement Learning Has Zero Duality Gap
• Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
• Neural Tangent Kernel: Convergence and Generalization in Neural Networks
• Gaussian Error Linear Units (GELUs)
• Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)

Related

• Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm
• A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
• Beyond Exponentially Fast Mixing in Average-Reward Reinforcement Learning via Multi-Level Monte Carlo Actor-Critic
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles
• Recurrent Natural Policy Gradient for POMDPs