Provable RL with Exogenous Distractors via Multistep Inverse Dynamics

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

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 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.

Introduction: The Challenge of Exogenous Noise

In real-world RL, agents often face high-dimensional observations cluttered with "exogenous distractors"—complex background noise that the agent cannot control. For example, a robot navigating a park sees its own position (endogenous state) but also ducks in a pond or swaying trees (exogenous noise). While the ducks' movement is temporally correlated, it is independent of the robot's actions.

Standard representation learning often fails in these scenarios:

  • Autoencoders waste capacity reconstructing high-entropy noise.
  • Contrastive methods (e.g., HOMER) may fail to abstract, treating every unique noise configuration as a distinct state, leading to an explosion in the state space.
  • Standard Inverse Dynamics (predicting the last action from two frames) can "over-abstract," failing to distinguish important states if the final action alone is insufficient to tell them apart.

The authors formalize this as the Exogenous Block MDP (EX-BMDP), where the latent state is split into a controllable "endogenous" part ($s$) and an uncontrollable "exogenous" part ($\xi$).

Predictive Path Elimination (PPE)

The Predictive Path Elimination (PPE) algorithm addresses these challenges by building a "policy cover"—a set of action sequences (paths) that reach every possible relevant state in the environment.

Overview of the EX-BMDP framework (left) and the Generalized Inverse Dynamics approach used in PPE (right).

The core innovation is Multistep Inverse Dynamics. Instead of guessing a single action from two adjacent frames, PPE:

  1. Data Collection: Follows various action sequences (paths) to collect observations.
  2. Path Prediction: Trains a classifier $f_\theta$ to predict the index of the path (the sequence of actions) that led to a specific observation $x'$.
  3. Path Elimination: If the model cannot statistically distinguish between two different paths based on the resulting observations, PPE concludes those paths lead to the same endogenous state and eliminates the redundant one.

Because exogenous noise is independent of the agent's actions, the path predictor naturally learns to ignore it, focusing only on the endogenous state transitions. This "Independence Principle" allows the algorithm to focus on controllable features.

Experimental Evaluation

The authors evaluated PPE on two primary benchmarks designed to test exploration under heavy noise:

  • Combination Lock: A "needle in a haystack" RL problem with high-dimensional exogenous noise created by projecting random bit-vectors through a Hadamard matrix.
  • Visual Grid World: A navigation task where five colored ellipses (distractors) randomly change position, size, and color, often covering the relevant parts of the image.

Key Results

  • Superior Exploration: In the Combination Lock task, PPE successfully solved the problem up to a horizon of $H=40$. Baselines like PPO, RND, and even state-of-the-art representation learners like HOMER failed completely as the horizon increased or noise was added.
  • Decoding Accuracy: PPE recovered the true latent state with near 100% accuracy, whereas contrastive methods saw their accuracy plummet to near-random levels once exogenous noise was introduced.
  • Robustness: In Visual Grid World, PPE made almost zero "Type 1" errors (accidentally merging different states), allowing it to plan optimal paths despite heavy visual distractors.

Conclusion

PPE demonstrates that multistep inverse dynamics can provably filter out complex exogenous distractors in near-deterministic environments. The sample complexity scales with the size of the latent endogenous state space, making it efficient for high-dimensional tasks. Future work aims to extend these guarantees to stochastic endogenous transitions and more complex, continuous state representations.

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