Data to 7 Oct 2026

Provably efficient RL with Rich Observations via Latent State Decoding

arXiv 1901.09018 ↗First posted 25 Jan 2019cs.LG stat.MLcited by 169

Not on the map. Why?

Abstract (arXiv)

We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps -- where previously decoded latent states provide labels for later regression problems -- and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over Q-learning with na"ive exploration, even when Q-learning has cheating access to latent states.

Key facts. Cited by 169 papers in the map (data through 7 Oct 2026). First posted on arXiv 25 Jan 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 37; 2022: 52; 2023: 35; 2024: 21; 2025: 15; 2026: 9.

169 papers.

Sort:

By area:

2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 176
2021Multi-Task Reinforcement Learning with Context-based Representationscited by 169
2021A Survey of Zero-shot Generalisation in Deep Reinforcement Learningcited by 164
2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
2022The Role of Coverage in Online Reinforcement Learningcited by 82
2022Can Foundation Models Perform Zero-Shot Task Specification For Robot Manipulation?cited by 70
2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
2022Denoised MDPs: Learning World Models Better Than the World Itselfcited by 66
2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
2021Learning Task Informed Abstractionscited by 58

38 more

2022Pre-Trained Image Encoder for Generalizable Visual Reinforcement Learningcited by 58
2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
2021Learning Markov State Abstractions for Deep Reinforcement Learningcited by 42
2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
2022Contextualize Me -- The Case for Context in Reinforcement Learningcited by 41
2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
2022Provable Benefits of Representational Transfer in Reinforcement Learningcited by 38
2022On the Power of Foundation Modelscited by 37
2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
2022Spectral Decomposition Representation for Reinforcement Learningcited by 35
2022Offline Reinforcement Learning Under Value and Density-Ratio Realizability: The Power of Gapscited by 34
2021Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvaturecited by 32
2022On the Complexity of Adversarial Decision Makingcited by 32
2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
2022Provable Benefit of Multitask Representation Learning in Reinforcement Learningcited by 29
2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
2023A Novel Framework for Policy Mirror Descent with General Parameterization and Linear Convergencecited by 29
2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
2021Provable RL with Exogenous Distractors via Multistep Inverse Dynamicscited by 28
2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
2022Sample-Efficient Reinforcement Learning in the Presence of Exogenous Informationcited by 26
2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
2024FuRL: Visual-Language Models as Fuzzy Rewards for Reinforcement Learningcited by 26
2021Block Contextual MDPs for Continual Learningcited by 25
2021Learning Representations for Pixel-based Control: What Matters and Why?cited by 24
2021A Free Lunch from the Noise: Provable and Practical Exploration for Representation Learningcited by 24
2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
2022A Comprehensive Survey of Data Augmentation in Visual Reinforcement Learningcited by 23
2023Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RLcited by 22

50 most cited of 169 All 169 (JSON)