Research map / Reinforcement learning / MDPs and planning
Learning a Fast Mixing Exogenous Block MDP using a Single Trajectory
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STEEL, a provably sample-efficient algorithm that learns the controllable latent dynamics and encoder of an Ex-BMDP from a single no-reset trajectory by looping action sequences and using a training oracle for cycle detection and classification.
Problem
Representation learning in Ex-BMDPs (controllable latent state plus time-correlated exogenous noise) when the agent interacts in a single continuous trajectory without resets, where prior methods lacked sample-complexity guarantees.
Approach
Exploit deterministic latent dynamics to repeatedly loop action sequences into latent cycles, use the period and mixing-time-spaced samples to identify latent states via a function-class classifier oracle, then learn the encoder, giving sample complexity polynomial in |S| and log|F| and linear in the exogenous mixing time.
Key results
- STEEL exactly recovered the latent dynamics and optimal encoder in 20/20 runs across combination lock (K=20,30,40) and multi-maze settings.
- Step counts were identical across fixed-environment runs (e.g., 1,886,582 steps for K=20), confirming independence from exogenous noise.
- Multi-maze required about 4.1e7 steps, a few orders of magnitude more than prior practical methods, attributed to conservative guarantees and lack of spatial priors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use STEEL to learn the latent dynamics and encoder | Combination Lock K=20 · Combination Lock K=20 | accuracy: 20/20 | Helped |
| Use STEEL to learn the latent dynamics and encoder | Combination Lock K=30 · Combination Lock K=30 | accuracy: 20/20 | Helped |
| Use STEEL to learn the latent dynamics and encoder | Combination Lock K=40 · Combination Lock K=40 | accuracy: 20/20 | Helped |
| Use STEEL to learn the latent dynamics and encoder | Multi-Maze · Multi-Maze | accuracy: 20/20 | Helped |
| Vary environment randomness and parameters rather than holding them fixed | STEEL · Combination Lock K=20, K=30, K=40 and Multi-Maze | steps: Fixed Env. Steps: 1886582$\pm$0, 4286241$\pm$0, 7914856$\pm$0, 41003875$\pm$0; Variable Env. Steps: 2.00$\cdot 10^6$ $\p | No clear effect |
Surprising findings
- Step counts in the multi-maze experiment are a few orders of magnitude larger than prior practical methods, reflecting the conservative theoretical design.
Limitations
- Requires strict determinism of latent transitions; fragile to rare deviations.
- Requires an optimal training oracle for the encoder function class, which is computationally intractable for complex classes.
- Requires known upper bounds on mixing time and latent state count/diameter, and reachability of all latent states.
Experimental setup
Datasets: combination lock environment (synthetic) multi-maze environment (synthetic)
Benchmarks: combination lock (K=20,30,40) multi-maze
Metrics: success rate (exact recovery of encoder and dynamics) number of environment steps
Baselines: PPE ExoRL multistep inverse methods
Builds on: Ex-BMDP PPE Block MDP
Closest papers by meaning
- Provably Filtering Exogenous Distractors using Multistep Inverse Dynamics (ICLR 2022 · similarity 0.89)
- Towards Principled Representation Learning from Videos for Reinforcement Learning (ICLR 2024 · similarity 0.87)
- Represent to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency (ICLR 2023 · similarity 0.86)
- Optimal Sample Complexity for Average Reward Markov Decision Processes (ICLR 2024 · similarity 0.85)
- Identifying latent state transitions in non-linear dynamical systems (ICLR 2025 · similarity 0.85)
- Diffusion Spectral Representation for Reinforcement Learning (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.