  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 guarantees an $\epsilon$ global optimality gap and $\epsilon$ constraint
violation with $\tilde{\mathcal{O}}(\epsilon^{-2})$ sample complexity for
general parameterized policies. This improves the state-of-the-art sample
complexity in general parameterized CMDPs by a factor of
$\mathcal{O}(\epsilon^{-2})$ and achieves the theoretical lower bound.
