Reward-Free Exploration for Reinforcement Learning
  Exploration is widely regarded as one of the most challenging aspects of
reinforcement learning (RL), with many naive approaches succumbing to
exponential sample complexity. To isolate the challenges of exploration, we
propose a new "reward-free RL" framework. In the exploration phase, the agent
first collects trajectories from an MDP $\mathcal{M}$ without a pre-specified
reward function. After exploration, it is tasked with computing near-optimal
policies under for $\mathcal{M}$ for a collection of given reward functions.
This framework is particularly suitable when there are many reward functions of
interest, or when the reward function is shaped by an external agent to elicit
desired behavior.
  We give an efficient algorithm that conducts
$\tilde{\mathcal{O}}(S^2A\mathrm{poly}(H)/\epsilon^2)$ episodes of exploration
and returns $\epsilon$-suboptimal policies for an arbitrary number of reward
functions. We achieve this by finding exploratory policies that visit each
"significant" state with probability proportional to its maximum visitation
probability under any possible policy. Moreover, our planning procedure can be
instantiated by any black-box approximate planner, such as value iteration or
natural policy gradient. We also give a nearly-matching
$\Omega(S^2AH^2/\epsilon^2)$ lower bound, demonstrating the near-optimality of
our algorithm in this setting.
