Achieving $\tilde{O}(1/ε)$ Sample Complexity for Constrained
  Markov Decision Process
Jiashuo Jiang Yinyu Ye
We consider the reinforcement learning problem for the constrained Markov
decision process (CMDP), which plays a central role in satisfying safety or
resource constraints in sequential learning and decision-making. In this
problem, we are given finite resources and a MDP with unknown transition
probabilities. At each stage, we take an action, collecting a reward and
consuming some resources, all assumed to be unknown and need to be learned over
time. In this work, we take the first step towards deriving optimal
problem-dependent guarantees for the CMDP problems. We derive a logarithmic
regret bound, which translates into a
$O(\frac{\kappa}{\epsilon}\cdot\log^2(1/\epsilon))$ sample complexity bound,
with $\kappa$ being a problem-dependent parameter, yet independent of
$\epsilon$. Our sample complexity bound improves upon the state-of-art
$O(1/\epsilon^2)$ sample complexity for CMDP problems established in the
previous literature, in terms of the dependency on $\epsilon$. To achieve this
advance, we develop a new framework for analyzing CMDP problems. To be
specific, our algorithm operates in the primal space and we resolve the primal
LP for the CMDP problem at each period in an online manner, with
\textit{adaptive} remaining resource capacities. The key elements of our
algorithm are: i). an eliminating procedure that characterizes one optimal
basis of the primal LP, and; ii) a resolving procedure that is adaptive to the
remaining resources and sticks to the characterized optimal basis.