  Reinforcement learning (RL) so far has limited real-world applications. One
key challenge is that typical RL algorithms heavily rely on a reset mechanism
to sample proper initial states; these reset mechanisms, in practice, are
expensive to implement due to the need for human intervention or heavily
engineered environments. To make learning more practical, we propose a generic
no-regret reduction to systematically design reset-free RL algorithms. Our
reduction turns the reset-free RL problem into a two-player game. We show that
achieving sublinear regret in this two-player game would imply learning a
policy that has both sublinear performance regret and sublinear total number of
resets in the original RL problem. This means that the agent eventually learns
to perform optimally and avoid resets. To demonstrate the effectiveness of this
reduction, we design an instantiation for linear Markov decision processes,
which is the first provably correct reset-free RL algorithm.
