Global Convergence for Average Reward Constrained MDPs with Primal-Dual Actor Critic Algorithm

This paper investigates infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) with general parametrization. We propose a Primal-Dual Natural Actor-Critic algorithm that adeptly manages constraints while ensuring a high convergence rate. In particular, our algorithm achieves global convergence and constraint violation rates of Õ(1/√T) over a horizon of length T when the mixing time, τₘᵢₓ, is known to the learner. In absence of knowledge of τₘᵢₓ, the achievable rates change to Õ(1/T0.5-ε) provided that T ≥ Õ(τₘᵢₓ2/ε). Our results match the theoretical lower bound for Markov Decision Processes and establish a new benchmark in the theoretical exploration of average reward CMDPs.