  The key assumption underlying linear Markov Decision Processes (MDPs) is that
the learner has access to a known feature map $\phi(x, a)$ that maps
state-action pairs to $d$-dimensional vectors, and that the rewards and
transitions are linear functions in this representation. But where do these
features come from? In the absence of expert domain knowledge, a tempting
strategy is to use the ``kitchen sink" approach and hope that the true features
are included in a much larger set of potential features. In this paper we
revisit linear MDPs from the perspective of feature selection. In a $k$-sparse
linear MDP, there is an unknown subset $S \subset [d]$ of size $k$ containing
all the relevant features, and the goal is to learn a near-optimal policy in
only poly$(k,\log d)$ interactions with the environment. Our main result is the
first polynomial-time algorithm for this problem. In contrast, earlier works
either made prohibitively strong assumptions that obviated the need for
exploration, or required solving computationally intractable optimization
problems.
  Along the way we introduce the notion of an emulator: a succinct approximate
representation of the transitions that suffices for computing certain Bellman
backups. Since linear MDPs are a non-parametric model, it is not even obvious
whether polynomial-sized emulators exist. We show that they do exist and can be
computed efficiently via convex programming.
  As a corollary of our main result, we give an algorithm for learning a
near-optimal policy in block MDPs whose decoding function is a low-depth
decision tree; the algorithm runs in quasi-polynomial time and takes a
polynomial number of samples. This can be seen as a reinforcement learning
analogue of classic results in computational learning theory. Furthermore, it
gives a natural model where improving the sample complexity via representation
learning is computationally feasible.
