PDR-ANPG Algorithm Achieves Last-Iterate Convergence in Constrained MDPs

A novel algorithm named Primal-Dual based Regularized Accelerated Natural Policy Gradient (PDR-ANPG) has been introduced for the learning of Constrained Markov Decision Processes (CMDPs) utilizing general parameterized policies. This algorithm employs both entropy and quadratic regularizers to ensure convergence at the last iterate. For parameterized policy classes that exhibit a transferred compatibility approximation error, ε_bias, PDR-ANPG achieves an ε optimality gap and ε constraint violation with a sample complexity of Õ(ε⁻² min{ε⁻², ε_bias⁻¹/³}). In scenarios where the class is incomplete (ε_bias > 0), the complexity simplifies to Õ(ε⁻²) for ε < (ε_bias)^(1/6). For complete policies with ε_bias = 0, the algorithm secures last-iterate ε optimality gap and ε constraint violation with sample complexity Õ(ε⁻² min{ε⁻², 1}). This development enhances reinforcement learning in safety-critical contexts where constraints must be adhered to throughout the learning process.