# Provable RL with Exogenous Distractors via Multistep Inverse Dynamics

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 33 references that are in the map.
- First posted on arXiv 17 Oct 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Learning Latent Dynamics for Planning from Pixels](https://mlsanity.com/paper/1811.04551/) (2018)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Variational Intrinsic Control](https://mlsanity.com/paper/1611.07507/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits](https://mlsanity.com/paper/1402.0555/) (2014)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning](https://mlsanity.com/paper/1703.07710/) (2017)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPs](https://mlsanity.com/paper/1909.02769/) (2019)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Online Convex Optimization in Adversarial Markov Decision Processes](https://mlsanity.com/paper/1905.07773/) (2019)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Reinforcement Learning with Trajectory Feedback](https://mlsanity.com/paper/2008.06036/) (2020)
- [Planning from Pixels using Inverse Dynamics Models](https://mlsanity.com/paper/2012.02419/) (2020)
- [Discovering and Removing Exogenous State Variables and Rewards for Reinforcement Learning](https://mlsanity.com/paper/1806.01584/) (2018)

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

- [Formal Algorithms for Transformers](https://mlsanity.com/paper/2207.09238/) (2022)
- [Denoised MDPs: Learning World Models Better Than the World Itself](https://mlsanity.com/paper/2206.15477/) (2022)
- [Inverse Dynamics Pretraining Learns Good Representations for Multitask Imitation](https://mlsanity.com/paper/2305.16985/) (2023)
- [Simplifying Model-based RL: Learning Representations, Latent-space Models, and Policies with One Objective](https://mlsanity.com/paper/2209.08466/) (2022)
- [Sample-Efficient Reinforcement Learning in the Presence of Exogenous Information](https://mlsanity.com/paper/2206.04282/) (2022)
- [Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL](https://mlsanity.com/paper/2304.05889/) (2023)
- [Pretraining in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2211.03959/) (2022)
- [Language Models Can Learn from Verbal Feedback Without Scalar Rewards](https://mlsanity.com/paper/2509.22638/) (2025)
- [Mastering Robot Manipulation with Multimodal Prompts through Pretraining and Multi-task Fine-tuning](https://mlsanity.com/paper/2310.09676/) (2023)
- [Representation Learning in Deep RL via Discrete Information Bottleneck](https://mlsanity.com/paper/2212.13835/) (2022)
- [Discrete Factorial Representations as an Abstraction for Goal Conditioned Reinforcement Learning](https://mlsanity.com/paper/2211.00247/) (2022)
- [Ignorance is Bliss: Robust Control via Information Gating](https://mlsanity.com/paper/2303.06121/) (2023)
- [AD3: Implicit Action is the Key for World Models to Distinguish the Diverse Visual Distractors](https://mlsanity.com/paper/2403.09976/) (2024)
- [Object-Centric Latent Action Learning](https://mlsanity.com/paper/2502.09680/) (2025)
- [Provably Efficient CVaR RL in Low-rank MDPs](https://mlsanity.com/paper/2311.11965/) (2023)
- [Elastic Step DQN: A novel multi-step algorithm to alleviate overestimation in Deep QNetworks](https://mlsanity.com/paper/2210.03325/) (2022)
- [A Reinforcement Learning Approach to Estimating Long-term Treatment Effects](https://mlsanity.com/paper/2210.07536/) (2022)
- [DWM: Separating World Effects from Actions in Latent World Models](https://mlsanity.com/paper/2607.18715/) (2026)
- [Exploiting Action Impact Regularity and Exogenous State Variables for Offline Reinforcement Learning](https://mlsanity.com/paper/2111.08066/) (2021)
- [Uniqueness and Complexity of Inverse MDP Models](https://mlsanity.com/paper/2206.01192/) (2022)
- [Disentangled (Un)Controllable Features](https://mlsanity.com/paper/2211.00086/) (2022)
- [Discovering What You Can Control: Interventional Boundary Discovery for Reinforcement Learning](https://mlsanity.com/paper/2603.18257/) (2026)
- [Contrast encodes inductive bias: separating slow noise from dynamics in predictive representation learning](https://mlsanity.com/paper/2606.07770/) (2026)
- [Dueling World Models: Advantage-Style Action Channels for Common-Mode Distractor Rejection](https://mlsanity.com/paper/2608.06706/) (2026)
- [SeMOPO: Learning High-quality Model and Policy from Low-quality Offline Visual Datasets](https://mlsanity.com/paper/2406.09486/) (2024)
- [Rethinking State Disentanglement in Causal Reinforcement Learning](https://mlsanity.com/paper/2408.13498/) (2024)
- [TaskSense: Focusing on What Matters in World Models](https://mlsanity.com/paper/2608.06544/) (2026)
- [CF-JEPA: Improving Robustness of JEPA World Models via Controllability Factorization](https://mlsanity.com/paper/2610.00727/) (2026)

## Abstract (arXiv)

Many real-world applications of reinforcement learning (RL) require the agent to deal with high-dimensional observations such as those generated from a megapixel camera. Prior work has addressed such problems with representation learning, through which the agent can provably extract endogenous, latent state information from raw observations and subsequently plan efficiently. However, such approaches can fail in the presence of temporally correlated noise in the observations, a phenomenon that is common in practice. We initiate the formal study of latent state discovery in the presence of such exogenous noise sources by proposing a new model, the Exogenous Block MDP (EX-BMDP), for rich observation RL. We start by establishing several negative results, by highlighting failure cases of prior representation learning based approaches. Then, we introduce the Predictive Path Elimination (PPE) algorithm, that learns a generalization of inverse dynamics and is provably sample and computationally efficient in EX-BMDPs when the endogenous state dynamics are near deterministic. The sample complexity of PPE depends polynomially on the size of the latent endogenous state space while not directly depending on the size of the observation space, nor the exogenous state space. We provide experiments on challenging exploration problems which show that our approach works empirically.