  We consider discounted infinite horizon constrained Markov decision processes
(CMDPs) where the goal is to find an optimal policy that maximizes the expected
cumulative reward subject to expected cumulative constraints. Motivated by the
application of CMDPs in online learning of safety-critical systems, we focus on
developing an algorithm that ensures constraint satisfaction during learning.
To this end, we develop a zeroth-order interior point approach based on the log
barrier function of the CMDP. Under the commonly assumed conditions of Fisher
non-degeneracy and bounded transfer error of the policy parameterization, we
establish the theoretical properties of the algorithm. In particular, in
contrast to existing CMDP approaches that ensure policy feasibility only upon
convergence, our algorithm guarantees feasibility of the policies during the
learning process and converges to the optimal policy with a sample complexity
of $O(\varepsilon^{-6})$. In comparison to the state-of-the-art policy
gradient-based algorithm, C-NPG-PDA, our algorithm requires an additional
$O(\varepsilon^{-2})$ samples to ensure policy feasibility during learning with
same Fisher-non-degenerate parameterization.

Machine Learning;Optimization and Control