Sample-Efficient Constrained Reinforcement Learning with General Parameterization

Abstract

We consider a constrained Markov Decision Problem (CMDP) where the goal of an agent is to maximize the expected discounted sum of rewards over an infinite horizon while ensuring that the expected discounted sum of costs exceeds a certain threshold. Building on the idea of momentum-based acceleration, we develop the Primal-Dual Accelerated Natural Policy Gradient (PD-ANPG) algorithm that ensures an $ϵ$ global optimality gap and $ϵ$ constraint violation with $\tilde{\mathcal{O}}((1-\gamma {)}^{-7}{ϵ}^{-2})$ sample complexity for general parameterized policies where $\gamma$ denotes the discount factor. This improves the state-of-the-art sample complexity in general parameterized CMDPs by a factor of $\mathcal{O}((1-\gamma {)}^{-1}{ϵ}^{-2})$ and achieves the theoretical lower bound in ${ϵ}^{-1}$.