Provably Filtering Exogenous Distractors using Multistep Inverse Dynamics

Yonathan Efroni, Dipendra Misra, Akshay Krishnamurthy, Alekh Agarwal, John Langford

Introduction

Standard representation learning in Reinforcement Learning (RL) often fails when observations contain "exogenous noise"—complex, temporally correlated distractors like moving clouds, background traffic, or other elements that the agent cannot control. In "rich-observation" RL, agents must map high-dimensional inputs (like megapixel camera images) to a small latent state (like the agent's coordinates) to plan effectively.

However, the real world is full of these exogenous distractors. Existing methods often fall into two traps:

  1. Under-abstraction: Treating every unique combination of agent position and distractor state as a different state, leading to an exponential explosion in the data needed to explore.
  2. Over-abstraction: Ignoring the agent's position entirely if it's "smaller" than the noise, failing to learn a useful policy.

To address this, the authors introduce the Exogenous Block MDP (EX-BMDP) framework and a novel algorithm, Predictive Path Elimination (PPE), which uses multistep inverse dynamics to provably filter out these distractors and learn sample-efficiently based only on relevant state information.

The EX-BMDP Model and Predictive Path Elimination

The authors propose a new model to formalize the environment by splitting the latent state into two components: an endogenous state (affected by actions and rewards) and an exogenous state (independent dynamics).

EX-BMDP and Generalized Inverse Dynamics

To solve this, they introduce Predictive Path Elimination (PPE). Instead of trying to predict the next observation (which would require modeling the distractors), PPE learns a multistep inverse dynamics model.

  • It asks: "Given this current observation, which sequence of actions (path) did I take to get here?"
  • If the algorithm cannot statistically distinguish between two different paths based on the resulting observations, it concludes those paths lead to the same endogenous state.
  • It iteratively builds a "policy cover"—a set of action sequences that reach every reachable endogenous state—while eliminating redundant paths.

Key Insights

  • The Power of Multistep Inverse Dynamics: Standard inverse dynamics (predicting the last action) can fail if the starting state is random. By predicting the entire path from the start, the agent isolates endogenous changes from exogenous noise.
  • Factorization is the Filter: Because the exogenous state is independent of the agent's actions, the probability of reaching a specific exogenous state is the same regardless of the path taken. This mathematical symmetry allows the classifier to "cancel out" the noise.
  • Provable Efficiency: The number of samples needed scales polynomially with the size of the endogenous state space, regardless of how large or complex the exogenous distractors are.

Experiments and Results

The authors evaluated PPE on simulated environments designed to highlight the distractor problem: a Combination Lock with Noise (a difficult exploration task with 100-dimensional temporally correlated noise) and a Visual Grid World (a navigation task with moving, random ellipses as distractors).

Experimental Results on Combination Lock and Decoding Accuracy
  • Superior Exploration: In the Combination Lock task, PPE successfully solved the problem for horizons up to $H=40$. Baselines like PPO, RND (Random Network Distillation), and HOMER failed even at much shorter horizons ($H=5$ or $10$) because they were distracted by the noise.
  • Robust State Decoding: In the Visual Grid World, PPE maintained high accuracy in decoding the agent's true position from the image, even as distractor complexity increased. Contrastive methods like HOMER saw their accuracy plummet.
  • Computational Efficiency: PPE reduces the complex RL problem to a series of standard multi-class classification problems, making it highly practical compared to previous theoretical algorithms.

Limitations and Future Work

  • Determinism: The current theoretical proof for PPE assumes that the endogenous dynamics are "near-deterministic." Extending this to highly stochastic environments remains an open challenge.
  • Discrete Latent States: The model assumes the endogenous state space is discrete. Adapting path elimination to continuous state spaces is a direction for future work.
  • Function Class Realizability: The theory assumes the chosen function class (e.g., neural network architecture) is powerful enough to represent the "true" path predictor, which is a common but strong assumption in RL theory.

Summary updated

Abstract

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.
BibTeX
@inproceedings{efroni2022provably,
  author = {Yonathan Efroni and Dipendra Misra and Akshay Krishnamurthy and Alekh Agarwal and John Langford},
  title = {{Provably Filtering Exogenous Distractors using Multistep Inverse Dynamics}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=RQLLzMCefQu},
}
Figure