  We study online learning in episodic constrained Markov decision processes
(CMDPs), where the goal of the learner is to collect as much reward as possible
over the episodes, while guaranteeing that some long-term constraints are
satisfied during the learning process. Rewards and constraints can be selected
either stochastically or adversarially, and the transition function is not
known to the learner. While online learning in classical unconstrained MDPs has
received considerable attention over the last years, the setting of CMDPs is
still largely unexplored. This is surprising, since in real-world applications,
such as, e.g., autonomous driving, automated bidding, and recommender systems,
there are usually additional constraints and specifications that an agent has
to obey during the learning process. In this paper, we provide the first
best-of-both-worlds algorithm for CMDPs with long-term constraints. Our
algorithm is capable of handling settings in which rewards and constraints are
selected either stochastically or adversarially, without requiring any
knowledge of the underling process. Moreover, our algorithm matches
state-of-the-art regret and constraint violation bounds for settings in which
constraints are selected stochastically, while it is the first to provide
guarantees in the case in which they are chosen adversarially.
