This paper studies a sequential decision-making problem in a constrained Markov decision process (MDP) that maximizes expected total reward while satisfying constraints on expected total utility. To solve the infinite horizontal discounting optimal control problem using the natural policy gradient method, we propose the Natural Policy Gradient Primal-Dual (NPG-PD) method. This method updates the primal variable via natural policy gradient ascent and the dual variable via projected subgradient descent. We demonstrate that the proposed method converges globally at a sublinear rate under softmax policy parameterization, despite the non-objective function and nonconvex constraint set for the maximization problem. This convergence is independent of the size of the state-action space, and for log-linear and general smooth policy parameterizations, the sublinear convergence rate is established even when considering the function approximation error due to the restricted policy parameterization. Additionally, we provide convergence and finite sample complexity guarantees for two sample-based NPG-PD algorithms, and demonstrate the effectiveness of our approach through computational experiments.
