  We study the design of sample-efficient algorithms for reinforcement learning
in the presence of rich, high-dimensional observations, formalized via the
Block MDP problem. Existing algorithms suffer from either 1) computational
intractability, 2) strong statistical assumptions that are not necessarily
satisfied in practice, or 3) suboptimal sample complexity. We address these
issues by providing the first computationally efficient algorithm that attains
rate-optimal sample complexity with respect to the desired accuracy level, with
minimal statistical assumptions. Our algorithm, MusIK, combines systematic
exploration with representation learning based on multi-step inverse
kinematics, a learning objective in which the aim is to predict the learner's
own action from the current observation and observations in the (potentially
distant) future. MusIK is simple and flexible, and can efficiently take
advantage of general-purpose function approximation. Our analysis leverages
several new techniques tailored to non-optimistic exploration algorithms, which
we anticipate will find broader use.
