평균 보상 제약 마르코프 결정 프로세스(CMDP)를 위한 최적 순서 기반 신경망 액터-크리틱 알고리즘: 계층적 다단계 몬테카를로 방법

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

제약 마르코프 결정 프로세스(CMDP)는 안전이 중요한 응용 분야에서 강화 학습을 위한 자연스러운 프레임워크를 제공하며, 여기서 에이전트는 장기적인 제약을 만족시키면서 장기적인 보상을 최대화합니다. 선형 크리틱을 사용하는 원-듀얼 액터-크리틱 방법은 잘 이해되고 있지만, 평균 보상 CMDP에서 신경망 크리틱에 대한 최적 순서 기반 수렴 보장을 확장하는 것은 해결되지 않은 과제로 남아 있었습니다. 주된 문제는 신경망 크리틱 추정에서 근본적인 편향-비용 절충 관계입니다. 신경 텐저 커널(NTK) 분석 하에서, 크리틱의 편향을 크게 줄이면 크리틱 최적화 비용이 증가하여 원-듀얼 프레임워크에서 최적 순서 기반 수렴을 방해합니다. 우리는 이 병목 현상을 해결하기 위해 계층적 다단계 몬테카를로(MLMC) 신경망 크리틱을 도입하여 경로 샘플링 및 크리틱 최적화에 동시에 편향을 제거합니다. 결과적으로 얻어지는 추정기는 로그 스케일의 예상 샘플 비용으로만 장기간의 크리틱 최적화를 수행하는 것과 동일한 수준의 편향을 달성합니다. 이 추정기를 기반으로, 우리는 최적 간극과 제약 위반이 모두 $ ilde{O}(T^{-1/2})$의 순서를 갖는 원-듀얼 내추럴 액터-크리틱 알고리즘을 개발했습니다. 이는 일반적인 정책 파라미터화 및 신경망 크리틱을 사용하는 무한 지평 평균 보상 CMDP에 대한 최초의 최적 순서 기반 수렴 보장을 제시하며, 기본 혼합 시간을 알아야 하는 필요성을 없앱니다. 우리의 결과는 제약이 없는 설정에서도 새롭습니다.

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.