  Reward-free reinforcement learning (RL) is a framework which is suitable for
both the batch RL setting and the setting where there are many reward functions
of interest. During the exploration phase, an agent collects samples without
using a pre-specified reward function. After the exploration phase, a reward
function is given, and the agent uses samples collected during the exploration
phase to compute a near-optimal policy. Jin et al. [2020] showed that in the
tabular setting, the agent only needs to collect polynomial number of samples
(in terms of the number states, the number of actions, and the planning
horizon) for reward-free RL. However, in practice, the number of states and
actions can be large, and thus function approximation schemes are required for
generalization. In this work, we give both positive and negative results for
reward-free RL with linear function approximation. We give an algorithm for
reward-free RL in the linear Markov decision process setting where both the
transition and the reward admit linear representations. The sample complexity
of our algorithm is polynomial in the feature dimension and the planning
horizon, and is completely independent of the number of states and actions. We
further give an exponential lower bound for reward-free RL in the setting where
only the optimal $Q$-function admits a linear representation. Our results imply
several interesting exponential separations on the sample complexity of
reward-free RL.
