Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs
<|reference_start|>Last-Iterate Convergence of General Parameterized Policies in Constrained MDPs: 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, $\epsilon_{\mathrm{bias}}$, PDR-ANPG achieves a last-iterate $\epsilon$ optimality gap and $\epsilon$ constraint violation (up to some additive factor of $\epsilon_{\mathrm{bias}}$) with a sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2}\min\{\epsilon^{-2},\epsilon_{\mathrm{bias}}^{-\frac{1}{3}}\})$. If the class is incomplete ($\epsilon_{\mathrm{bias}}>0$), then the sample complexity reduces to $\tilde{\mathcal{O}}(\epsilon^{-2})$ for $\epsilon<(\epsilon_{\mathrm{bias}})^{\frac{1}{6}}$. Moreover, for complete policies with $\epsilon_{\mathrm{bias}}=0$, our algorithm achieves a last-iterate $\epsilon$ optimality gap and $\epsilon$ constraint violation with $\tilde{\mathcal{O}}(\epsilon^{-4})$ sample complexity. It is a significant improvement of the state-of-the-art last-iterate guarantees of general parameterized CMDPs.<|reference_end|>
@article{mondal2024last-iterate,
    title={Last-Iterate Convergence of General Parameterized Policies in
  Constrained MDPs},
    author={Washim Uddin Mondal and Vaneet Aggarwal},
    journal={arXiv preprint arXiv:2408.11513},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.11513},
    primaryClass={cs.LG cs.AI}
}