  We study Concave Constrained Markov Decision Processes (Concave CMDPs) where
both the objective and constraints are defined as concave functions of the
state-action occupancy measure. We propose the Variance-Reduced Primal-Dual
Policy Gradient Algorithm (VR-PDPG), which updates the primal variable via
policy gradient ascent and the dual variable via projected sub-gradient
descent. Despite the challenges posed by the loss of additivity structure and
the nonconcave nature of the problem, we establish the global convergence of
VR-PDPG by exploiting a form of hidden concavity. In the exact setting, we
prove an $O(T^{-1/3})$ convergence rate for both the average optimality gap and
constraint violation, which further improves to $O(T^{-1/2})$ under strong
concavity of the objective in the occupancy measure. In the sample-based
setting, we demonstrate that VR-PDPG achieves an $\widetilde{O}(\epsilon^{-4})$
sample complexity for $\epsilon$-global optimality. Moreover, by incorporating
a diminishing pessimistic term into the constraint, we show that VR-PDPG can
attain a zero constraint violation without compromising the convergence rate of
the optimality gap. Finally, we validate the effectiveness of our methods
through numerical experiments.
