Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs

Abstract

This paper focuses on learning a Constrained Markov Decision Process (CMDP) via general parameterized policies. We propose a Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm that uses entropy and quadratic regularizers to reach this goal. For parameterized policy classes with a transferred compatibility approximation error, ${ϵ}_{\mathrm{bias}}$, PDR-ANPG achieves a last-iterate $ϵ$ optimality gap and $ϵ$ constraint violation with a sample complexity of $\tilde{\mathcal{O}}({ϵ}^{-2}\min \{{ϵ}^{-2},{ϵ}_{\mathrm{bias}}^{-\frac{1}{3}}\})$. If the class is incomplete (${ϵ}_{\mathrm{bias}}>0$), then the sample complexity reduces to $\tilde{\mathcal{O}}({ϵ}^{-2})$ for $ϵ<({ϵ}_{\mathrm{bias}}{)}^{\frac{1}{6}}$. Moreover, for complete policies with ${ϵ}_{\mathrm{bias}}=0$, our algorithm achieves a last-iterate $ϵ$ optimality gap and $ϵ$ constraint violation with $\tilde{\mathcal{O}}({ϵ}^{-4})$ sample complexity. It is a significant improvement over the state-of-the-art last-iterate guarantees of general parameterized CMDPs.