Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs

Abstract

We consider the problem of learning a Constrained Markov Decision Process (CMDP) via general parameterization. Our proposed Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) algorithm uses entropy and quadratic regularizers to reach this goal. For a parameterized policy class with transferred compatibility approximation error, $ε_{\mathrm{bias}}$, PDR-ANPG achieves a last-iterate $ε$ optimality gap and $ε$ constraint violation (up to some additive factor of $ε_{\mathrm{bias}}$) 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 of the state-of-the-art last-iterate guarantees of general parameterized CMDPs.