# Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 22 references that are in the map.
- First posted on arXiv 3 Oct 2024.

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

- [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)
- [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)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Denoised MDPs: Learning World Models Better Than the World Itself](https://mlsanity.com/paper/2206.15477/) (2022)
- [Guaranteed Discovery of Control-Endogenous Latent States with Multi-Step Inverse Models](https://mlsanity.com/paper/2207.08229/) (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)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [The Power of Resets in Online Reinforcement Learning](https://mlsanity.com/paper/2404.15417/) (2024)
- [Multistep Inverse Is Not All You Need](https://mlsanity.com/paper/2403.11940/) (2024)
- [Posterior Sampling for Continuing Environments](https://mlsanity.com/paper/2211.15931/) (2022)
- [Reinforcement Learning with Exogenous States and Rewards](https://mlsanity.com/paper/2303.12957/) (2023)
- [Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPs](https://mlsanity.com/paper/2404.14552/) (2024)

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

- [Discovering What You Can Control: Interventional Boundary Discovery for Reinforcement Learning](https://mlsanity.com/paper/2603.18257/) (2026)
- [Compositional Transduction with Latent Analogies for Offline Goal-Conditioned Reinforcement Learning](https://mlsanity.com/paper/2605.20609/) (2026)
- [Reinforcement Learning and Consumption-Savings Behavior](https://mlsanity.com/paper/2510.20748/) (2025)

## Abstract (arXiv)

In order to train agents that can quickly adapt to new objectives or reward functions, efficient unsupervised representation learning in sequential decision-making environments can be important. Frameworks such as the Exogenous Block Markov Decision Process (Ex-BMDP) have been proposed to formalize this representation-learning problem (Efroni et al., 2022b). In the Ex-BMDP framework, the agent's high-dimensional observations of the environment have two latent factors: a controllable factor, which evolves deterministically within a small state space according to the agent's actions, and an exogenous factor, which represents time-correlated noise, and can be highly complex. The goal of the representation learning problem is to learn an encoder that maps from observations into the controllable latent space, as well as the dynamics of this space. Efroni et al. (2022b) has shown that this is possible with a sample complexity that depends only on the size of the controllable latent space, and not on the size of the noise factor. However, this prior work has focused on the episodic setting, where the controllable latent state resets to a specific start state after a finite horizon. By contrast, if the agent can only interact with the environment in a single continuous trajectory, prior works have not established sample-complexity bounds. We propose STEEL, the first provably sample-efficient algorithm for learning the controllable dynamics of an Ex-BMDP from a single trajectory, in the function approximation setting. STEEL has a sample complexity that depends only on the sizes of the controllable latent space and the encoder function class, and (at worst linearly) on the mixing time of the exogenous noise factor. We prove that STEEL is correct and sample-efficient, and demonstrate STEEL on two toy problems. Code is available at: https://github.com/midi-lab/steel.