mlsanityData to 14 Oct 2026

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

arXiv 2304.05889 ↗First posted 12 Apr 2023cs.LG cs.AIcited by 22

Not on the map. Why?

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.

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

23 of 39 references.

References · 23

  1. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  2. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  3. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  4. 2018Is Q-learning Provably Efficient?cited by 487
  5. 2022Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videoscited by 345
  6. 2020Agent57: Outperforming the Atari Human Benchmarkcited by 303
  7. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  8. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  9. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  10. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  11. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  12. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
11 more
  1. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  2. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  3. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  4. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  5. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  6. 2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
  7. 2022INFOrmation Prioritization through EmPOWERment in Visual Model-Based RLcited by 27
  8. 2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
  9. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  10. 2020Learning the Linear Quadratic Regulator from Nonlinear Observationscited by 21
  11. 2022Latent Variable Representation for Reinforcement Learningcited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 4; 2024: 12; 2025: 1; 2026: 5.

22 papers.

Sort:

By area:

  1. 2026Sensorimotor World Models: Perception for Action via Inverse Dynamicscited by 20
  2. 2023Efficient Model-Free Exploration in Low-Rank MDPscited by 16
  3. 2023Offline Data Enhanced On-Policy Policy Gradient with Provable Guaranteescited by 11
  4. 2024Multistep Inverse Is Not All You Needcited by 11
  5. 2024Offline Reinforcement Learning: Role of State Aggregation and Trajectory Datacited by 11
  6. 2024Towards Principled Representation Learning from Videos for Reinforcement Learningcited by 10
  7. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 9
  8. 2024A Note on Loss Functions and Error Compounding in Model-based Reinforcement Learningcited by 8
  9. 2024Offline Oracle-Efficient Learning for Contextual MDPs via Layerwise Exploration-Exploitation Tradeoffcited by 8
  10. 2024Oracle-Efficient Differentially Private Learning with Public Datacited by 6
  11. 2024Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learningcited by 6
  12. 2024Hybrid Reinforcement Learning from Offline Observation Alonecited by 5
10 more
  1. 2023PcLast: Discovering Plannable Continuous Latent Statescited by 4
  2. 2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
  3. 2024Is Efficient PAC Learning Possible with an Oracle That Responds 'Yes' or 'No'?cited by 3
  4. 2024Learning a Fast Mixing Exogenous Block MDP using a Single Trajectorycited by 3
  5. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  6. 2026When Does Predictive Inverse Dynamics Outperform Behavior Cloning?cited by 3
  7. 2024Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPscited by 2
  8. 2026Decoupling Exploration and Policy Optimization: Uncertainty Guided Tree Search for Hard Explorationcited by 1
  9. 2026End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitionscited by 0
  10. 2026Minimal Recurrent Behavioral Memory for Imitation under Partial Observabilitycited by 0