# Learning Markov State Abstractions for Deep Reinforcement Learning

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

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 64 references that are in the map.
- First posted on arXiv 8 Jun 2021.

## Builds on (most cited first, 30 of 35)

- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Dream to Control: Learning Behaviors by Latent Imagination](https://mlsanity.com/paper/1912.01603/) (2019)
- [World Models](https://mlsanity.com/paper/1803.10122/) (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)
- [Model-Based Reinforcement Learning for Atari](https://mlsanity.com/paper/1903.00374/) (2019)
- [Reinforcement Learning with Augmented Data](https://mlsanity.com/paper/2004.14990/) (2020)
- [Learning Invariant Representations for Reinforcement Learning without Reconstruction](https://mlsanity.com/paper/2006.10742/) (2020)
- [dm_control: Software and Tasks for Continuous Control](https://mlsanity.com/paper/2006.12983/) (2020)
- [Embed to Control: A Locally Linear Latent Dynamics Model for Control from Raw Images](https://mlsanity.com/paper/1506.07365/) (2015)
- [Improving Sample Efficiency in Model-Free Reinforcement Learning from Images](https://mlsanity.com/paper/1910.01741/) (2019)
- [Decoupling Representation Learning from Reinforcement Learning](https://mlsanity.com/paper/2009.08319/) (2020)
- [Stochastic Latent Actor-Critic: Deep Reinforcement Learning with a Latent Variable Model](https://mlsanity.com/paper/1907.00953/) (2019)
- [DeepMDP: Learning Continuous Latent Space Models for Representation Learning](https://mlsanity.com/paper/1906.02736/) (2019)
- [Reinforcement Learning with Prototypical Representations](https://mlsanity.com/paper/2102.11271/) (2021)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Learning to Poke by Poking: Experiential Learning of Intuitive Physics](https://mlsanity.com/paper/1606.07419/) (2016)
- [Deep Spatial Autoencoders for Visuomotor Learning](https://mlsanity.com/paper/1509.06113/) (2015)
- [DARLA: Improving Zero-Shot Transfer in Reinforcement Learning](https://mlsanity.com/paper/1707.08475/) (2017)
- [Unsupervised State Representation Learning in Atari](https://mlsanity.com/paper/1906.08226/) (2019)
- [Scalable methods for computing state similarity in deterministic Markov Decision Processes](https://mlsanity.com/paper/1911.09291/) (2019)
- [When to use parametric models in reinforcement learning?](https://mlsanity.com/paper/1906.05243/) (2019)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Lipschitz Continuity in Model-based Reinforcement Learning](https://mlsanity.com/paper/1804.07193/) (2018)
- [Loss is its own Reward: Self-Supervision for Reinforcement Learning](https://mlsanity.com/paper/1612.07307/) (2016)
- [Near Optimal Behavior via Approximate State Abstraction](https://mlsanity.com/paper/1701.04113/) (2017)
- [Plannable Approximations to MDP Homomorphisms: Equivariance under Actions](https://mlsanity.com/paper/2002.11963/) (2020)
- [Learning Plannable Representations with Causal InfoGAN](https://mlsanity.com/paper/1807.09341/) (2018)

## Built on by (most cited first, 30 of 44)

- [Bridging State and History Representations: Understanding Self-Predictive RL](https://mlsanity.com/paper/2401.08898/) (2024)
- [Flipping Coins to Estimate Pseudocounts for Exploration in Reinforcement Learning](https://mlsanity.com/paper/2306.03186/) (2023)
- [Conditional Mutual Information for Disentangled Representations in Reinforcement Learning](https://mlsanity.com/paper/2305.14133/) (2023)
- [Unsupervised Representation Learning in Deep Reinforcement Learning: A Review](https://mlsanity.com/paper/2208.14226/) (2022)
- [Pretraining in Deep Reinforcement Learning: A Survey](https://mlsanity.com/paper/2211.03959/) (2022)
- [Inference via Interpolation: Contrastive Representations Provably Enable Planning and Inference](https://mlsanity.com/paper/2403.04082/) (2024)
- [A Survey of State Representation Learning for Deep Reinforcement Learning](https://mlsanity.com/paper/2506.17518/) (2025)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [SimSR: Simple Distance-based State Representation for Deep Reinforcement Learning](https://mlsanity.com/paper/2112.15303/) (2021)
- [Hierarchical State Abstraction Based on Structural Information Principles](https://mlsanity.com/paper/2304.12000/) (2023)
- [Studying the Interplay Between the Actor and Critic Representations in Reinforcement Learning](https://mlsanity.com/paper/2503.06343/) (2025)
- [One Subgoal at a Time: Zero-Shot Generalization to Arbitrary Linear Temporal Logic Requirements in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2508.01561/) (2025)
- [Meta-Learning Parameterized Skills](https://mlsanity.com/paper/2206.03597/) (2022)
- [Sequential Knockoffs for Variable Selection in Reinforcement Learning](https://mlsanity.com/paper/2303.14281/) (2023)
- [Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy](https://mlsanity.com/paper/2407.07333/) (2024)
- [Temporal Distance-aware Transition Augmentation for Offline Model-based Reinforcement Learning](https://mlsanity.com/paper/2505.13144/) (2025)
- [Learning Abstract World Model for Value-preserving Planning with Options](https://mlsanity.com/paper/2406.15850/) (2024)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [BAMDP Shaping: a Unified Framework for Intrinsic Motivation and Reward Shaping](https://mlsanity.com/paper/2409.05358/) (2024)
- [Improving Policy Exploitation in Online Reinforcement Learning with Instant Retrospect Action](https://mlsanity.com/paper/2601.19720/) (2026)
- [Abstract Reward Processes: Leveraging State Abstraction for Consistent Off-Policy Evaluation](https://mlsanity.com/paper/2410.02172/) (2024)
- [From Pixels to Factors: Learning Independently Controllable State Variables for Reinforcement Learning](https://mlsanity.com/paper/2510.02484/) (2025)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Representations and Exploration for Deep Reinforcement Learning using Singular Value Decomposition](https://mlsanity.com/paper/2305.00654/) (2023)
- [Beyond Non-Expert Demonstrations: Outcome-Driven Action Constraint for Offline Reinforcement Learning](https://mlsanity.com/paper/2504.01719/) (2025)
- [Contextual Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2301.01298/) (2023)
- [On shallow planning under partial observability](https://mlsanity.com/paper/2407.15820/) (2024)
- [The Synergy of LLMs & RL Unlocks Offline Learning of Generalizable Language-Conditioned Policies with Low-fidelity Data](https://mlsanity.com/paper/2412.06877/) (2024)
- [Inversely Learning Transferable Rewards via Abstracted States](https://mlsanity.com/paper/2501.01669/) (2025)
- [Multi-Agent Conditional Diffusion Model with Mean Field Communication as Wireless Resource Allocation Planner](https://mlsanity.com/paper/2510.22969/) (2025)

## Abstract (arXiv)

A fundamental assumption of reinforcement learning in Markov decision processes (MDPs) is that the relevant decision process is, in fact, Markov. However, when MDPs have rich observations, agents typically learn by way of an abstract state representation, and such representations are not guaranteed to preserve the Markov property. We introduce a novel set of conditions and prove that they are sufficient for learning a Markov abstract state representation. We then describe a practical training procedure that combines inverse model estimation and temporal contrastive learning to learn an abstraction that approximately satisfies these conditions. Our novel training objective is compatible with both online and offline training: it does not require a reward signal, but agents can capitalize on reward information when available. We empirically evaluate our approach on a visual gridworld domain and a set of continuous control benchmarks. Our approach learns representations that capture the underlying structure of the domain and lead to improved sample efficiency over state-of-the-art deep reinforcement learning with visual features -- often matching or exceeding the performance achieved with hand-designed compact state information.