mlsanityData to 14 Oct 2026

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

arXiv 2205.13476 ↗First posted 26 May 2022cs.LG cs.AI cs.SYcited by 16

Not on the map. Why?

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.

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

19 of 39 references.

References · 19

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Deep Recurrent Q-Learning for Partially Observable MDPscited by 465
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  4. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  7. 2016Learning to Navigate in Complex Environmentscited by 198
  8. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  9. 2020Dynamical Variational Autoencoders: A Comprehensive Reviewcited by 128
  10. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  11. 2019A Short Note on Concentration Inequalities for Random Vectors with SubGaussian Normcited by 106
  12. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
7 more
  1. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  2. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  3. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  4. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  5. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  6. 2015Recurrent Reinforcement Learning: A Hybrid Approachcited by 13
  7. 2015Learning to Filter with Predictive State Inference Machinescited by 8

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 8; 2024: 2; 2025: 3.

16 papers.

Sort:

By area:

  1. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  2. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  3. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  4. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  5. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 18
  6. 2023Lower Bounds for Learning in Revealing POMDPscited by 15
  7. 2023Improved Sample Complexity for Reward-free Reinforcement Learning under Low-rank MDPscited by 14
  8. 2023Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDPcited by 8
  9. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 8
  10. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  11. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 4
  12. 2025Scalable Policy-Based RL Algorithms for POMDPscited by 4
4 more
  1. 2024Near-Optimal Learning and Planning in Separated Latent MDPscited by 3
  2. 2023Representations and Exploration for Deep Reinforcement Learning using Singular Value Decompositioncited by 2
  3. 2024Generalizing Multi-Step Inverse Models for Representation Learning to Finite-Memory POMDPscited by 2
  4. 2025Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Modelscited by 1