# Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL

arXiv: https://arxiv.org/abs/2304.05889 · HTML: https://mlsanity.com/paper/2304.05889/

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 39 references that are in the map.
- First posted on arXiv 12 Apr 2023.

## Builds on (most cited first, 23 of 23)

- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videos](https://mlsanity.com/paper/2206.11795/) (2022)
- [Agent57: Outperforming the Atari Human Benchmark](https://mlsanity.com/paper/2003.13350/) (2020)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Bilinear Classes: A Structural Framework for Provable Generalization in RL](https://mlsanity.com/paper/2103.10897/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Making Linear MDPs Practical via Contrastive Representation Learning](https://mlsanity.com/paper/2207.07150/) (2022)
- [Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach](https://mlsanity.com/paper/2202.00063/) (2022)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)
- [INFOrmation Prioritization through EmPOWERment in Visual Model-Based RL](https://mlsanity.com/paper/2204.08585/) (2022)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Learning the Linear Quadratic Regulator from Nonlinear Observations](https://mlsanity.com/paper/2010.03799/) (2020)
- [Latent Variable Representation for Reinforcement Learning](https://mlsanity.com/paper/2212.08765/) (2022)

## Built on by (most cited first, 22 of 22)

- [Sensorimotor World Models: Perception for Action via Inverse Dynamics](https://mlsanity.com/paper/2606.20104/) (2026)
- [Efficient Model-Free Exploration in Low-Rank MDPs](https://mlsanity.com/paper/2307.03997/) (2023)
- [Offline Data Enhanced On-Policy Policy Gradient with Provable Guarantees](https://mlsanity.com/paper/2311.08384/) (2023)
- [Multistep Inverse Is Not All You Need](https://mlsanity.com/paper/2403.11940/) (2024)
- [Offline Reinforcement Learning: Role of State Aggregation and Trajectory Data](https://mlsanity.com/paper/2403.17091/) (2024)
- [Towards Principled Representation Learning from Videos for Reinforcement Learning](https://mlsanity.com/paper/2403.13765/) (2024)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [A Note on Loss Functions and Error Compounding in Model-based Reinforcement Learning](https://mlsanity.com/paper/2404.09946/) (2024)
- [Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoff](https://mlsanity.com/paper/2405.17796/) (2024)
- [Oracle-Efficient Differentially Private Learning with Public Data](https://mlsanity.com/paper/2402.09483/) (2024)
- [Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning](https://mlsanity.com/paper/2404.03774/) (2024)
- [Hybrid Reinforcement Learning from Offline Observation Alone](https://mlsanity.com/paper/2406.07253/) (2024)
- [PcLast: Discovering Plannable Continuous Latent States](https://mlsanity.com/paper/2311.03534/) (2023)
- [Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actions](https://mlsanity.com/paper/2406.11640/) (2024)
- [Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?](https://mlsanity.com/paper/2406.11667/) (2024)
- [Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory](https://mlsanity.com/paper/2410.03016/) (2024)
- [To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2510.03207/) (2025)
- [When Does Predictive Inverse Dynamics Outperform Behavior Cloning?](https://mlsanity.com/paper/2601.21718/) (2026)
- [Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPs](https://mlsanity.com/paper/2404.14552/) (2024)
- [Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Exploration](https://mlsanity.com/paper/2603.22273/) (2026)
- [End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions](https://mlsanity.com/paper/2603.23461/) (2026)
- [Minimal Recurrent Behavioral Memory for Imitation under Partial Observability](https://mlsanity.com/paper/2609.25757/) (2026)

## Abstract (arXiv)

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.