  A major challenge in reinforcement learning is to develop practical,
sample-efficient algorithms for exploration in high-dimensional domains where
generalization and function approximation is required. Low-Rank Markov Decision
Processes -- where transition probabilities admit a low-rank factorization
based on an unknown feature embedding -- offer a simple, yet expressive
framework for RL with function approximation, but existing algorithms are
either (1) computationally intractable, or (2) reliant upon restrictive
statistical assumptions such as latent variable structure, access to
model-based function approximation, or reachability. In this work, we propose
the first provably sample-efficient algorithm for exploration in Low-Rank MDPs
that is both computationally efficient and model-free, allowing for general
function approximation and requiring no additional structural assumptions. Our
algorithm, VoX, uses the notion of a barycentric spanner for the feature
embedding as an efficiently computable basis for exploration, performing
efficient barycentric spanner computation by interleaving representation
learning and policy optimization. Our analysis -- which is appealingly simple
and modular -- carefully combines several techniques, including a new approach
to error-tolerant barycentric spanner computation and an improved analysis of a
certain minimax representation learning objective found in prior work.
