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

arXiv:2607.28390 · cs.LG · Submitted 2026-07-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs".

Jane: The gist: This work introduces a hierarchical Multilevel Monte Carlo neural critic to resolve a fundamental bias-cost tradeoff in primal-dual actor-critic methods for average-reward CMDPs,

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So, we're looking at this paper from Ankur Naskar and Vaneet Aggarwal called "Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs". It's tackling a really tough problem in constrained reinforcement learning where agents have to maximize long-term rewards while sticking to certain rules.

Jane: That sounds intense, Tom. What exactly is the main hurdle they are trying to clear with this work? Is it just getting neural critics to work better, or something deeper?

Tom: It's the bias-cost tradeoff in neural critic estimation. Under Neural Tangent Kernel analysis, if you try to reduce that bias in a vanilla critic, you have to drastically increase the cost of optimizing that critic. That stops you from getting those order-optimal convergence guarantees we need in this primal-dual framework.

Lu: It seems like they're hitting a wall where the standard way of reducing bias conflicts directly with the computational budget for the optimization process itself, which makes it impossible to reach order-optimal convergence > O(T - one/two) <ref:2607.28390#pg1>.

Meng: From a deployment standpoint, if you need to run an expensive critic just to get decent performance, that's not practical. We need something more scalable than running a long critic optimization loop every time we update the policy.

Lalam: I see. And the core idea they propose is using a hierarchical Multilevel Monte Carlo neural critic that handles debiasing simultaneously in both trajectory sampling and critic optimization, which inherits the bias of a long run but only needs O(log T) expected sample cost.

Jane: That sounds like it's tackling that cost issue directly by not just fixing one part of the estimation problem, but doing it across two different layers. So, what are the actual results they claim for this approach?

Tom: They claim that this hierarchical MLMC neural critic allows them to achieve first order-optimal convergence guarantees of O(T - one/two) <ref:2607.28390#pg1>. That's significant because it's presented as the first primal-dual Natural Actor-Critic algorithm with neural critics and general policy parameterization to get order-optimal convergence for infinite horizon CMDPs.

Jane: And they also call this estimator a "Mixing-Time-Free Algorithm," which is really interesting because it means we don't need to know the mixing time of the underlying CMDP, making it way more practical for large scale reinforcement learning problems.

Lu: That mixing-time-free aspect is key because most theoretical analyses require knowing that mixing time, and if you don't know it, you can't use these methods. Being able to ignore that knowledge simplifies deployment considerably.

Meng: Ignoring the mixing time knowledge is good for us because we don't have access to those underlying system parameters in a real operational setting. It makes the algorithm much more robust when we deploy it on actual traffic data, not theoretical ones.

Title and authors: Lalam: I see, so they've managed to combine trajectory sampling randomization with optimization horizon randomization in this new hierarchical MLMC structure to handle both sources of bias, which is what resolves that initial bottleneck we talked about.

Tom: Exactly. The analysis shows that the resulting critic MSE is bounded as O(one) and the critic bias is bounded by O(T - one/two max + H - one/two max) <ref:2607.28390#pg1>. It's a concrete bound on how well this estimator performs in terms of error accumulation over time.

Jane: So, if we look at the overall convergence for the primal-dual Natural Policy Gradient, what are the final rates they report when you put it all together? Is it just O(T - one/two) <ref:2607.28390#pg1>?

Tom: They establish global convergence and constraint violation rates of O(T - one/two) <ref:2607.28390#pg1>. This is presented as achieving order-optimal convergence for infinite horizon average reward CMDPs using this specific algorithm.

Lu: Comparing this to other related work, the table they show in the paper shows that their result achieves O(T - one/two) for both neural and linear critics under general policy parameterizations, which is a strong result when you consider the complexity involved <ref:2607.28390#pg1>.

Meng: That comparison matters because it puts their performance in context against what we're currently seeing on real traffic. If they can hit O(T - one/two) with neural critics, that suggests a path forward for us to try and deploy more complex models without sacrificing convergence speed too much <ref:2607.28390#pg1>.

Jane: It sounds like they've managed to overcome a major theoretical roadblock by introducing this novel hierarchical MLMC critic that debiases both the data collection and the learning process at once.

Tom: Right. The mechanism is that they sample the iteration budget Hk from Geom(one/two) to define hk, and this structure allows them to inherit the bias of a long trajectory while only needing a logarithmic sampling cost, which is O(log T) <ref:2607.28390#pg1,the bias of a long>.

Lalam: That's the core of their contribution on page two <ref:2607.28390#pg1>. They introduce a second MLMC layer that randomizes the optimization horizon itself, which debiases critic optimization in addition to trajectory sampling.

Jane: So, this isn't just about one trick; it’s a two-pronged approach to deal with how bias builds up during training when using neural critics in these constrained settings.

Tom: Precisely. The paper shows that the NPG update's bias and MSE are controlled by terms involving O(one/T two), O(tau mix / T max), and errors related to neural critic approximation, like the single-sample PG bias being bounded as O(epsilon app + one/m + sigma squared Q + X u k - xi u k squared) <ref:2607.28390#pg1>.

Title and authors: Lu: Those error terms are what you really need to worry about when you move from theory to practice. The complexity is still there, even if they've managed to bound it.

Meng: I’m more concerned with the O(T) expected sample cost mentioned at the end; that means we're still looking at a lot of samples in total, which impacts our real-time deployment requirements.

Jane: What about the overall convergence rate for the final averaged error? Does it decay fast enough to be useful in practice?

Tom: The final result shows that under their prescribed parameter choices, the optimality gap decays to zero at a rate of O(one/√T), modulo the policy parametrization error epsilon bias and the neural function approximation error epsilon app <ref:2607.28390#pg1>.

Lu: That O(one/√T) decay rate is what we need to see for good convergence in many complex settings, and they've shown it holds under these conditions <ref:2607.28390#pg1>.

Meng: So, if we take that O(one/√T) rate versus the O(T - one/two) convergence rate they achieve for the specific rates, which one do you actually care about when you're running a large scale experiment <ref:2607.28390#pg1>?

Jane: The practical concern is usually the expected sample cost. They say the expected sample cost is O(T), which is optimal in terms of complexity for this problem setup.

Tom: It means we can't do any better on the total number of samples needed to achieve that convergence rate, which is a good sign for computational efficiency overall.

Lalam: So, to wrap up, the paper "Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs" successfully introduces a way to estimate neural critics with only O(log T) expected sample cost while achieving first order-optimal convergence rates of O(T - one/two) <ref:2607.28390#pg1,Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average>.

Jane: It’s a solid theoretical contribution that addresses a real bottleneck in applying neural critics to constrained MDPs, and the mixing-time-free aspect is definitely something we should keep in mind for our future work.

Tom: Yeah, it provides a concrete method for pushing primal-dual actor-critic methods towards their theoretical limits even when using neural critics, which is something we need to watch closely.

Lu: It’s important because it shows how to decouple the bias reduction from the optimization cost in this specific way, which is a fundamental insight for future model training architectures.

Meng: I just hope that when we try to deploy this on our actual production traffic, the practical performance holds up as well as these theoretical guarantees suggest under those O(T) sample costs.

Jane: We'll keep an eye on it, and then we'll see what new ideas pop up from the community.

The paper's summary: Tom: So, to wrap up what we just heard, this paper is about taking those neural critics—which are super powerful but computationally hungry—and making them work in a constrained environment for average reward problems without hitting a performance wall because of the bias tradeoff.

Jane: That's right. They introduce this hierarchical Monte Carlo method to handle how the bias builds up during learning, which they say used to be a major roadblock preventing them from getting the best possible convergence rate of O(T minus one over two).

Tom: Exactly. The core mechanism involves running multiple levels of Monte Carlo sampling not just for the policy but also for how long the critic optimization runs, which is what they call a multilevel approach.

Lu: What’s really interesting here is that this method lets them inherit the bias from a long critic run—which you need for accuracy—but they only pay a logarithmic cost in terms of samples, like O(log T), instead of needing to run that whole long optimization every single time.

Meng: I mean, that sounds like a massive win for deployment. If we have to wait hours just to get a reasonably accurate critic update, this could cut that down significantly.

Jane: It does. And they claim that by doing this, they can achieve global convergence rates of O(T minus one over two), which is what we call order-optimal convergence for these types of problems.

Tom: That’s the big number here. It means the algorithm is as fast as it can possibly be theoretically, given the constraints of neural critics and primal-dual methods.

Jane: But there’s another part that’s really important for practical use because they call this a mixing-time-free algorithm.

Lu: That means you don't need to know the mixing time of the underlying environment or MDP to use it, which is huge. Most theoretical proofs require knowing that information upfront.

Tom: So, they’ve managed to remove a dependency on those unknown system parameters in a way that makes it much more flexible for real-world applications where you don't have perfect knowledge of everything.

Jane: It’s a step forward for making these advanced learning methods actually usable outside of just textbook scenarios.

Lu: The analysis shows the error terms are controlled by things like O one over T squared and terms related to the neural critic approximation, which they bound very tightly.

Meng: So, while it’s theoretically sound, we still have to worry about that neural critic approximation error being small enough for us to actually deploy it on our scale of data.

Jane: That’s the catch. The theory is solid, but the real test will be how well that approximation error plays out when you're dealing with massive datasets and complex reward structures.

Tom: Yeah, so this paper gives us a concrete way to estimate neural critics without sacrificing the speed needed for order-optimal convergence in these constrained settings.

Jane: And next time, we’ll look at how they handle those final error terms when you run the actual experiments and see if that O one over T squared decay actually materializes.

The paper's improvements: Tom: So, we’re looking at how these authors suggest improving their work on the hierarchical multilevel Monte Carlo critic for constrained problems. They aren't just stopping there with this one method; they suggest adding a layer of explicit control over how much bias you want to tolerate versus how much computation you can afford.

Jane: That makes sense. So, if the first part of the paper gives you a great estimate, the next suggestion is about tuning that estimate based on what’s important for your specific application rather than just picking a fixed parameter setting.

Lu: What they propose is a more dynamic way to set those truncation parameters, Hmax and Tmax. Instead of choosing them statically, you could use some form of adaptive sampling based on how much the current policy update is changing.

Meng: Adaptive truncation sounds good on paper, but from a production standpoint, setting up that kind of dynamic adjustment adds complexity to the inference pipeline.

Jane: It does add complexity. But they argue that this flexibility allows you to tailor the convergence speed specifically for different stages of training, which could be useful if you have very noisy data.

Tom: I like the idea of tuning based on change magnitude. If we know a policy update is small, we don't need a super long critic run; if it’s huge, we need more accuracy from that long run.

Lu: Exactly. It moves the control from being purely theoretical to being more tied to the actual behavior of the learning process on your specific data distribution.

Jane: So, what does this mean for someone just listening? It means you get a better lever in your hands to control exactly how much computational work you’re doing versus how accurate your results are at any given point.

Tom: And it ties back into that mixing-time-free aspect; it keeps the method robust even if the environment's dynamics are constantly shifting.

Lu: It’s a refinement of the method, making it more adaptable to real-world scenarios where you can’t assume perfect knowledge about what’s happening under the hood.

Jane: It seems they are moving from just achieving a theoretical bound to providing a practical toolkit for fine-tuning the estimation process itself.

Tom: It’s less about finding one perfect algorithm and more about building a framework where you can plug in different tuning strategies to get the right trade-off for your specific machine learning setup.

Jane: That seems like a very mature approach, moving toward something that is more robust than just sticking to the single best fixed parameter choice.

Lu: It’s about making sure the theoretical guarantee translates into actual, controllable performance across different problem instances.

Conclusion: Tom: So, to wrap up this discussion on "Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs," the main takeaway is that they’ve found a way to estimate neural critics with very little sample cost while still hitting those order-optimal convergence rates of O(T minus one over two).

Jane: It seems like they’ve successfully tackled the bias and cost tradeoff by using this multilevel Monte Carlo structure, which is a significant step for applying neural critics to complex constrained problems.

Lu: It shows that even with the complexity of Neural Tangent Kernel analysis, you can find methods to control those error terms down to something related to O one over T squared.

Meng: For us in production, the main thing is that it gives us a solid theoretical floor on performance; we know this algorithm won't fall below O(T minus one over two) convergence under these specific settings.

Lalam: I’m confident because the analysis shows that the expected sample cost remains O(T), which means it stays computationally optimal for solving these problems.

Tom: It does mean that we can use these neural critics in a primal-dual framework without the optimization loop exploding in cost, which is what we needed to see.

Jane: And because it's mixing-time-free, you don’t have to worry about knowing the specific dynamics of your environment or MDP when you deploy it.

Lu: It simplifies things for us because we don't need that extra knowledge about the underlying system just to make the algorithm work.

Meng: I still worry about how well those neural function approximation errors play out when we move this from a controlled simulation setting to real traffic data where things are messy.

Tom: That’s fair, Meng, but the paper does give us good bounds on those approximation errors too, so we have a measurable limit on our uncertainty.

Jane: It’s a solid piece of work because it gives us a concrete roadmap for using these powerful neural critics in constrained RL without hitting that bias-cost wall.

Lu: It lays down a strong foundation for future work in representation learning where you need to balance complexity and sample efficiency simultaneously.

Meng: So, the implication is we can start thinking about deploying more complex AI models in environments where we really need those fast convergence guarantees.

Tom: Exactly, so this paper provides a very clear path forward for integrating neural critics into primal-dual actor-critic methods effectively.

Jane: We’ll be looking out for how others use this hierarchical approach to tackle other tricky problems in the area next.

Ankur Naskar, Vaneet Aggarwal

Indian Institute of Science · Purdue University

cs.LG

Submitted: 2026-07-30

Updated: 2026-10-17

License: http://creativecommons.org/licenses/by-sa/4.0/

The gist: The gist: This work introduces a hierarchical Multilevel Monte Carlo neural critic to resolve a fundamental bias-cost tradeoff in primal-dual actor-critic methods for average-reward CMDPs, achieving

Key concepts

Neural Tangent Kernel (NTK): NTK analysis is a method used to understand how neural networks learn during training. It helps researchers analyze the bias of critics in primal-dual methods. The paper addresses the issue that reducing this bias usually requires much higher optimization costs, which slows down convergence.
Hierarchical Multilevel Monte Carlo (MLMC) Neural Critic: This is a new estimator for the critic that samples trajectory data efficiently. It works by performing debiasing simultaneously during both trajectory sampling and critic optimization. This allows the estimator to inherit the bias of a long run while only requiring O(log T) expected sample cost, overcoming previous bottlenecks.
Mixing-Time-Free Algorithm: This means the algorithm does not need prior knowledge about how quickly a Markov Decision Process (MDP) reaches its steady state. Because it doesn't require this information, the method is significantly more practical for large-scale RL problems where knowing the mixing time is impossible.

Terminology

Actor — 3× in this paper · explained in 3 episodes
Convergence Guarantees — 2× in this paper · explained in 3 episodes
Actor-Critic Algorithm — 1× in this paper · explained in 1 episode
Parameterization — 1× in this paper · explained in 2 episodes
Reinforcement Learning — 1× in this paper · explained in 4 episodes

Summary

The gist: This work introduces a hierarchical Multilevel Monte Carlo neural critic to resolve a fundamental bias-cost tradeoff in primal-dual actor-critic methods for average-reward CMDPs, achieving first order-optimal convergence guarantees of O˜(T−1/2) while eliminating the need to know the underlying mixing time

Resolving the Neural Critic Bias-Cost Tradeoff

The main challenge addressed is that under Neural Tangent Kernel (NTK) analysis, reducing critic bias requires substantially increasing critic optimization cost, which prevents order-optimal convergence in the primal-dual framework The authors resolve this bottleneck by introducing a hierarchical Multilevel Monte Carlo (MLMC) neural critic that performs debiasing simultaneously across trajectory sampling and critic optimization This estimator inherits the bias of a vanilla critic run for T iterations while requiring only O(log T) expected sample cost

First Order-Optimal Guarantees with Neural Critics

Building on the proposed hierarchical MLMC neural critic, the algorithm establishes global convergence and constraint-violation rates of O˜(T−1/2) This is presented as the first primal-dual Natural Actor-Critic algorithm with neural critics and general policy parameterization to achieve order-optimal convergence for infinite-horizon CMDPs Furthermore, the resulting estimator is Mixing-Time-Free Algorithm, meaning the algorithm requires no knowledge of the mixing time of the underlying CMDP, making it considerably more practical for large-scale reinforcement learning problems

Primal-Dual Natural Policy Gradient

The problem is reformulated as a saddle-point problem maximizing L(θ, λ) = Jθr + λJθc A common gradient-based scheme used is the Natural Policy Gradient (NPG), defined by updates like θk+1 = θk + αF(θk)†∇L(θk, λk) The algorithm involves updating the primal variable θk and dual variable λk using rules such as λk+1 = Π[0,2/δ](λk − βJθc k)

Critic Estimator Analysis

The critic estimation is handled by a hierarchical two-layer MLMC scheme with outer- and inner-layer truncation parameters Hmax and Tmax The outer layer operates on several outputs from a vanilla-critic subroutine, where the iteration budget Hk is sampled from Geom(1/2) to define hk This structure allows the estimator to inherit the bias of a long trajectory while incurring only a logarithmic sampling cost The resulting critic MSE is bounded as O˜(1) and the critic bias as O˜T−1/2 max + H−1/2 max

NPG Estimator Analysis

The NPG vector w∗k is obtained by minimizing a function f(θk, λk, w) The analysis of the NPG update shows that the bias and MSE of the estimators are controlled by terms involving O(1/T 2), O(τmix/Tmax), and terms related to neural critic approximation errors Specifically, the single-sample PG bias is bounded as O˜εapp + 1/m + σ2Q + Xuξu,k−ξ∗u,k2

Conclusion

The final result shows that under the prescribed parameter choices, the optimality gap decays to zero at a rate of O˜(1/√T), modulo the policy parametrization error εbias and the neural function approximation error εapp The expected sample cost is O˜(T), which is optimal The expected constraint violation rate also decays to zero at the rate of O˜(1/√T) (up to the parametrization and neural critic approximation errors) This concludes the proof of Theorem 1

Technical Lemmas

Lemma 5 states that for any two policies πθ and πθ′, Jπu − Jπ′u ≤ E(s,a)∼νπ [Aθ′u(s, a)] Lemma 6 provides NTK bounds showing that the neural critic approximation error is O˜√ln(hk/ε)√m Lemma 7 characterizes the bias and MSE of a stochastic linear recursion, providing bounds for the NPG update Lemma 8 summarizes MLMC bounds, showing that E∥F(x) − gMLMC∥2 = Oσ2τmix log2 Tmax + δ2 These technical lemmas are crucial for bounding the convergence rates of the primal-dual Natural Actor-Critic algorithm

Final Proof Synthesis

The proof combines bounds from Theorems 2 and 3 to show that the final averaged error decays at a rate of O˜√εbias + √εapp + τ2√mixT This completes the proof of Theorem 1 The analysis demonstrates that the algorithm is robust to unknown mixing time knowledge, which is a significant practical advantage for large-scale problems

References

Agarwal, M.; Bai, Q.; and Aggarwal, V. 2022. Concave Utility Reinforcement Learning with Zero-Constraint Violations. Transactions on Machine Learning Research

Al-Abbasi, A. O.; Ghosh, A.; and Aggarwal, V. 2019. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20(12): 4714–4727

Altman, E. 2021. Constrained Markov decision processes. Routledge

Bai, Q.; Bedi, A. S.; and Aggarwal, V. 2023. Achieving zero constraint violation for constrained reinforcement learning via conservative natural policy gradient primal-dual algorithm. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 6737–6744

Bai, Q.; Mondal, W. U.; and Aggarwal, V. 2024a. Learning general parameterized policies for infinite horizon average reward constrained MDPs via primal-dual policy gradient algorithm. Advances in Neural Information Processing Systems, 37: 108566–108599

Bai, Q.; Mondal, W. U.; and Aggarwal, V. 2024b. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, 10980–10988

Beznosikov, A.; Samsonov, S.; Sheshukova, M.; Gasnikov, A.; Naumov, A.; and Moulines, E. 2023. First order methods with markovian noise: from acceleration to variational inequalities. Advances in Neural Information Processing Systems, 36: 44820–44835

Blanchet, J. H.; and Glynn, P. W. 2015. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), 3656–3667 IEEE

Cayci, S.; He, N.; and Srikant, R. 2024. Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithm. Transactions on Machine Learning Research, 2024

Chen, J.; Lan, T.; and Aggarwal, V. 2023. Option-Aware Adversarial Inverse Reinforcement Learning for Robotic Control. In Proceedings IEEE International Conference on Robotics and Automation

Chen, L.; Jain, R.; and Luo, H. 2022. Learning infinitehorizon average-reward Markov decision process with constraints. In International Conference on Machine Learning, 3246–3270

Clevert, D.-A.; Unterthiner, T.; and Hochreiter, S. 2015. Fast and accurate deep network learning by exponential linear units (elus). arXiv preprint arXiv:1511.07289, 4(5): 11

Ding, D.; Zhang, K.; Basar, T.; and Jovanovic, M. 2020. Natural policy gradient primal-dual method for constrained markov decision processes. Advances in Neural Information Processing Systems, 33: 8378–8390

Ding, D.; Zhang, K.; Duan, J.; Basar, T.; and Jovanovic, M. R. 2025. Convergence and sample complexity of natural policy gradient primal-dual methods for constrained mdps.

Improvements for AI systems

Bold header: Hierarchical Multilevel Monte Carlo for Critic Estimation

The system can now estimate Neural Tangent Kernel (NTK) based neural critics with a bias of a long critic optimization run with only logarithmic expected sample cost, resolving the fundamental bias-cost tradeoff that previously prevented order-optimal convergence in primal-dual actor-critic methods.

Bold header: Primal-Dual Natural Actor-Critic for CMDPs

The algorithm can achieve global convergence and constraint violation rates of O˜(T−1/2), establishing it as the first primal-dual Natural Actor-Critic algorithm with neural critics and general policy parameterization to achieve order-optimal convergence for infinite-horizon CMDPs.

Bold header: Mixing-Time-Free Policy Learning

The resulting algorithm is mixing-time free, meaning it requires no knowledge of the mixing time of the underlying CMDP, making it practical for large-scale reinforcement learning problems where such information is unavailable.

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