mlsanityData to 13 Oct 2026

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

arXiv 2607.28390 ↗First posted 30 Jul 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (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 tildeO(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.

Key facts. No citing papers in the map yet (data through 13 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 22 of its 39 references that are in the map. First posted on arXiv 30 Jul 2026.

Builds on

22 of 39 references.

Closest ancestors · 4

Same direction, newest first

  1. 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach26 Jul
  2. 2024Sample-Efficient Constrained Reinforcement Learning with General Parameterization17 May
  3. 2024Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite-Horizon Average Reward MDPs2 Apr
  4. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles18 Mar

Other references · 18

  1. 2016Gaussian Error Linear Units (GELUs)cited by 3,472
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,610
  3. 2015Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUs)cited by 1,061
  4. 2019Constrained Reinforcement Learning Has Zero Duality Gapcited by 144
  5. 2020CRPO: A New Approach for Safe Reinforcement Learning with Convergence Guaranteecited by 128
  6. 2018Stochastic Variance-Reduced Policy Gradientcited by 104
  7. 2022An Improved Analysis of (Variance-Reduced) Policy Gradient and Natural Policy Gradient Methodscited by 64
  8. 2019Sample Efficient Policy Gradient Methods with Recursive Variance Reductioncited by 59
  9. 2023Stochastic Policy Gradient Methods: Improved Sample Complexity for Fisher-non-degenerate Policiescited by 54
  10. 2022Adapting to Mixing Time in Stochastic Optimization with Markovian Datacited by 36
  11. 2020Single-Timescale Actor-Critic Provably Finds Globally Optimal Policycited by 34
  12. 2021Towards Tight Bounds on the Sample Complexity of Average-reward MDPscited by 32
6 more
  1. 2022Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPscited by 27
  2. 2021Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithmcited by 26
  3. 2020A Distributed Model-Free Ride-Sharing Approach for Joint Matching, Pricing, and Dispatching using Deep Reinforcement Learningcited by 17
  4. 2022Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Controlcited by 16
  5. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  6. 2024Reinforced Sequential Decision-Making for Sepsis Treatment: The POSNEGDM Framework with Mortality Classifier and Transformercited by 6

Built on by

Not cited yet.