Near-Optimal Learning and Planning in Separated Latent MDPs
Not on the map. Why?
Abstract (arXiv)
We study computational and statistical aspects of learning Latent Markov Decision Processes (LMDPs). In this model, the learner interacts with an MDP drawn at the beginning of each epoch from an unknown mixture of MDPs. To sidestep known impossibility results, we consider several notions of separation of the constituent MDPs. The main thrust of this paper is in establishing a nearly-sharp *statistical threshold* for the horizon length necessary for efficient learning. On the computational side, we show that under a weaker assumption of separability under the optimal policy, there is a quasi-polynomial algorithm with time complexity scaling in terms of the statistical threshold. We further show a near-matching time complexity lower bound under the exponential time hypothesis.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 32 of its 64 references that are in the map. First posted on arXiv 12 Jun 2024.
Builds on
32 of 64 references.
References · 32
- 2022Training language models to follow instructions with human feedbackcited by 15,712
- 2017Deep reinforcement learning from human preferencescited by 3,846
- 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
- 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
- 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
- 2015Contextual Markov Decision Processescited by 213
- 2021The Statistical Complexity of Interactive Decision Makingcited by 208
- 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
- 2022The Role of Coverage in Online Reinforcement Learningcited by 82
- 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
- 2013Hidden Parameter Markov Decision Processes: A Semiparametric Regression Approach for Discovering Latent Task Parametrizationscited by 68
- 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
20 more
- 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
- 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
- 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
- 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
- 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
- 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
- 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
- 2022Sample-Efficient Reinforcement Learning of Partially Observable Markov Gamescited by 26
- 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
- 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
- 2021Sublinear Regret for Learning POMDPscited by 19
- 2021Online Learning for Unknown Partially Observable MDPscited by 17
- 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
- 2022Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiencycited by 16
- 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
- 2023Lower Bounds for Learning in Revealing POMDPscited by 14
- 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
- 2022Unified Algorithms for RL with Decision-Estimation Coefficients: PAC, Reward-Free, Preference-Based Learning, and Beyondcited by 10
- 2022Optimistic MLE -- A Generic Model-based Algorithm for Partially Observable Sequential Decision Makingcited by 6
- 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
Built on by
Citing papers per year: 2025: 3.
3 papers.