  While learning in an unknown Markov Decision Process (MDP), an agent should
trade off exploration to discover new information about the MDP, and
exploitation of the current knowledge to maximize the reward. Although the
agent will eventually learn a good or optimal policy, there is no guarantee on
the quality of the intermediate policies. This lack of control is undesired in
real-world applications where a minimum requirement is that the executed
policies are guaranteed to perform at least as well as an existing baseline. In
this paper, we introduce the notion of conservative exploration for average
reward and finite horizon problems. We present two optimistic algorithms that
guarantee (w.h.p.) that the conservative constraint is never violated during
learning. We derive regret bounds showing that being conservative does not
hinder the learning ability of these algorithms.
