Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs

arXiv:2408.11513v2 Announce Type: replace 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, epsilon_{bias}, PDR-ANPG achieves a last-iterate epsilon optimality gap and epsilon constraint violation with a sample complexity of ilde{O}(epsilon^{-2}min{epsilon^{-2},epsilon_{bias}^{-frac{1}{3}}}). If the class is incomplete (epsilon_{bias}>0), then the sample complexity reduces to ilde{O}(epsilon^{-2}) for epsilon<(epsilon_{bias})^{frac{1}{6}}. Moreover, for complete policies with epsilon_{bias}=0, our algorithm achieves a last-iterate epsilon optimality gap and epsilon constraint violation with ilde{O}(epsilon^{-4}) sample complexity. It is a significant improvement over the state-of-the-art last-iterate guarantees of general parameterized CMDPs.

Source: arXiv cs.LG | 2026-05-04