# Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 39 references that are in the map.
- First posted on arXiv 26 May 2022.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Recurrent Q-Learning for Partially Observable MDPs](https://mlsanity.com/paper/1507.06527/) (2015)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Learning to Navigate in Complex Environments](https://mlsanity.com/paper/1611.03673/) (2016)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Dynamical Variational Autoencoders: A Comprehensive Review](https://mlsanity.com/paper/2008.12595/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Norm](https://mlsanity.com/paper/1902.03736/) (2019)
- [When Is Partially Observable Reinforcement Learning Not Scary?](https://mlsanity.com/paper/2204.08967/) (2022)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [Sample-Efficient Reinforcement Learning of Undercomplete POMDPs](https://mlsanity.com/paper/2006.12484/) (2020)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Provable Reinforcement Learning with a Short-Term Memory](https://mlsanity.com/paper/2202.03983/) (2022)
- [A PAC RL Algorithm for Episodic POMDPs](https://mlsanity.com/paper/1605.08062/) (2016)
- [Recurrent Reinforcement Learning: A Hybrid Approach](https://mlsanity.com/paper/1509.03044/) (2015)
- [Learning to Filter with Predictive State Inference Machines](https://mlsanity.com/paper/1512.08836/) (2015)

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

- [PAC Reinforcement Learning for Predictive State Representations](https://mlsanity.com/paper/2207.05738/) (2022)
- [Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems](https://mlsanity.com/paper/2206.12020/) (2022)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration](https://mlsanity.com/paper/2305.18258/) (2023)
- [Learning in POMDPs is Sample-Efficient with Hindsight Observability](https://mlsanity.com/paper/2301.13857/) (2023)
- [Lower Bounds for Learning in Revealing POMDPs](https://mlsanity.com/paper/2302.01333/) (2023)
- [Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPs](https://mlsanity.com/paper/2303.10859/) (2023)
- [Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP](https://mlsanity.com/paper/2306.12356/) (2023)
- [Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPs](https://mlsanity.com/paper/2503.01134/) (2025)
- [Provably Efficient UCB-type Algorithms For Learning Predictive State Representations](https://mlsanity.com/paper/2307.00405/) (2023)
- [Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight](https://mlsanity.com/paper/2307.02884/) (2023)
- [Scalable Policy-Based RL Algorithms for POMDPs](https://mlsanity.com/paper/2510.06540/) (2025)
- [Near-Optimal Learning and Planning in Separated Latent MDPs](https://mlsanity.com/paper/2406.07920/) (2024)
- [Representations and Exploration for Deep Reinforcement Learning using Singular Value Decomposition](https://mlsanity.com/paper/2305.00654/) (2023)
- [Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPs](https://mlsanity.com/paper/2404.14552/) (2024)
- [Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Models](https://mlsanity.com/paper/2506.01919/) (2025)

## Abstract (arXiv)

Reinforcement learning in partially observed Markov decision processes (POMDPs) faces two challenges. (i) It often takes the full history to predict the future, which induces a sample complexity that scales exponentially with the horizon. (ii) The observation and state spaces are often continuous, which induces a sample complexity that scales exponentially with the extrinsic dimension. Addressing such challenges requires learning a minimal but sufficient representation of the observation and state histories by exploiting the structure of the POMDP. To this end, we propose a reinforcement learning algorithm named Embed to Control (ETC), which learns the representation at two levels while optimizing the policy.~(i) For each step, ETC learns to represent the state with a low-dimensional feature, which factorizes the transition kernel. (ii) Across multiple steps, ETC learns to represent the full history with a low-dimensional embedding, which assembles the per-step feature. We integrate (i) and (ii) in a unified framework that allows a variety of estimators (including maximum likelihood estimators and generative adversarial networks). For a class of POMDPs with a low-rank structure in the transition kernel, ETC attains an O(1/ε2) sample complexity that scales polynomially with the horizon and the intrinsic dimension (that is, the rank). Here ε is the optimality gap. To our best knowledge, ETC is the first sample-efficient algorithm that bridges representation learning and policy optimization in POMDPs with infinite observation and state spaces.