  We study online learning problems in constrained Markov decision processes
(CMDPs) with adversarial losses and stochastic hard constraints. We consider
two different scenarios. In the first one, we address general CMDPs, where we
design an algorithm that attains sublinear regret and cumulative positive
constraints violation. In the second scenario, under the mild assumption that a
policy strictly satisfying the constraints exists and is known to the learner,
we design an algorithm that achieves sublinear regret while ensuring that the
constraints are satisfied at every episode with high probability. To the best
of our knowledge, our work is the first to study CMDPs involving both
adversarial losses and hard constraints. Indeed, previous works either focus on
much weaker soft constraints--allowing for positive violation to cancel out
negative ones--or are restricted to stochastic losses. Thus, our algorithms can
deal with general non-stationary environments subject to requirements much
stricter than those manageable with state-of-the-art algorithms. This enables
their adoption in a much wider range of real-world applications, ranging from
autonomous driving to online advertising and recommender systems.
