mlsanityData to 7 Oct 2026

RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluation

arXiv 2406.01389 ↗First posted 3 Jun 2024cs.LG cs.AI cs.SYcited by 5

Not on the map. Why?

Abstract (arXiv)

In many real-world decision problems there is partially observed, hidden or latent information that remains fixed throughout an interaction. Such decision problems can be modeled as Latent Markov Decision Processes (LMDPs), where a latent variable is selected at the beginning of an interaction and is not disclosed to the agent. In the last decade, there has been significant progress in solving LMDPs under different structural assumptions. However, for general LMDPs, there is no known learning algorithm that provably matches the existing lower bound (Kwon et al., 2021). We introduce the first sample-efficient algorithm for LMDPs without any additional structural assumptions. Our result builds off a new perspective on the role of off-policy evaluation guarantees and coverage coefficients in LMDPs, a perspective, that has been overlooked in the context of exploration in partially observed environments. Specifically, we establish a novel off-policy evaluation lemma and introduce a new coverage coefficient for LMDPs. Then, we show how these can be used to derive near-optimal guarantees of an optimistic exploration algorithm. These results, we believe, can be valuable for a wide range of interactive learning problems beyond LMDPs, and especially, for partially observed environments.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 47 of its 68 references that are in the map. First posted on arXiv 3 Jun 2024.

Builds on

47 of 68 references.

References · 47

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
  3. 2023Efficient Online Reinforcement Learning with Offline Datacited by 332
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  6. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  7. 2015Contextual Markov Decision Processescited by 213
  8. 2019VariBAD: A Very Good Method for Bayes-Adaptive Deep RL via Meta-Learningcited by 210
  9. 2021The Statistical Complexity of Interactive Decision Makingcited by 208
  10. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  11. 2019Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Samplingcited by 118
  12. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
35 more
  1. 2022A Review of Off-Policy Evaluation in Reinforcement Learningcited by 92
  2. 2022The Role of Coverage in Online Reinforcement Learningcited by 82
  3. 2020Adaptive Reward-Free Explorationcited by 77
  4. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  5. 2021RL for Latent MDPs: Regret Guarantees and a Lower Boundcited by 69
  6. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  7. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 65
  8. 2020Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confoundingcited by 60
  9. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  10. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  11. 2016On Context-Dependent Clustering of Banditscited by 43
  12. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  13. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 40
  14. 2022Provable Reinforcement Learning with a Short-Term Memorycited by 40
  15. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  16. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  17. 2021A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable Markov Decision Processescited by 34
  18. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  19. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  20. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  21. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  22. 2024Harnessing Density Ratios for Online Reinforcement Learningcited by 15
  23. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  24. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  25. 2024Scalable Online Exploration via Coverabilitycited by 10
  26. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  27. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  28. 2023When is Agnostic Reinforcement Learning Statistically Tractable?cited by 8
  29. 2022Meta Reinforcement Learning with Finite Training Tasks -- a Density Estimation Approachcited by 6
  30. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  31. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  32. 2024A Natural Extension To Online Algorithms For Hybrid RL With Limited Coveragecited by 5
  33. 2023Prospective Side Information for Latent MDPscited by 4
  34. 2022Tractable Optimality in Episodic Latent MABscited by 3
  35. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 4; 2026: 1.

5 papers.

  1. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  2. 2025To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learningcited by 3
  3. 2025A Classification View on Meta Learning Banditscited by 1
  4. 2025Near-Optimal Clustering in Mixture of Markov Chainscited by 1
  5. 2026Adaptive Exploration for Latent-State Banditscited by 0