mlsanityData to 14 Oct 2026

Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP

arXiv 2306.12356 ↗First posted 21 Jun 2023cs.LGcited by 8

Not on the map. Why?

Abstract (arXiv)

In this paper, we study representation learning in partially observable Markov Decision Processes (POMDPs), where the agent learns a decoder function that maps a series of high-dimensional raw observations to a compact representation and uses it for more efficient exploration and planning. We focus our attention on the sub-classes of textitγ-observable and textitdecodable POMDPs, for which it has been shown that statistically tractable learning is possible, but there has not been any computationally efficient algorithm. We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) to perform representation learning and achieve efficient sample complexity, while only calling supervised learning computational oracles. We then show how to adapt this algorithm to also work in the broader class of γ-observable POMDPs.

Key facts. Cited by 8 papers in the map (data through 14 Oct 2026). Builds on 28 of its 46 references that are in the map. First posted on arXiv 21 Jun 2023.

Builds on

28 of 46 references.

References · 28

  1. 2020Decoupling Representation Learning from Reinforcement Learningcited by 269
  2. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  3. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  4. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  5. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  6. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  7. 2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 129
  8. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  9. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  10. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  11. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  12. 2022BYOL-Explore: Exploration by Bootstrapped Predictioncited by 73
16 more
  1. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  2. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  3. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 52
  4. 2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 52
  5. 2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
  6. 2022PAC Reinforcement Learning for Predictive State Representationscited by 43
  7. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  8. 2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
  9. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  10. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  11. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  12. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  13. 2021Online Learning for Unknown Partially Observable MDPscited by 17
  14. 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
  15. 2018Bayesian Reinforcement Learning in Factored POMDPscited by 15
  16. 2016POMDP-lite for Robust Robot Planning under Uncertaintycited by 12

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 2; 2024: 2; 2025: 3; 2026: 1.

8 papers.

  1. 2024Diffusion Spectral Representation for Reinforcement Learningcited by 15
  2. 2023Provable Representation with Efficient Planning for Partial Observable Reinforcement Learningcited by 10
  3. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 8
  4. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  5. 2025Spectral Representation-based Reinforcement Learningcited by 3
  6. 2024Learning Interpretable Policies in Hindsight-Observable POMDPs through Partially Supervised Reinforcement Learningcited by 2
  7. 2025Transformers as Multi-task Learners: Decoupling Features in Hidden Markov Modelscited by 1
  8. 2026A Decentralized Partially Observable Team Decision Methodology with Delayed Information Sharingcited by 0