mlsanityData to 7 Oct 2026

RL for Latent MDPs: Regret Guarantees and a Lower Bound

arXiv 2102.04939 ↗First posted 9 Feb 2021cs.LGcited by 69

Not on the map. Why?

Abstract (arXiv)

In this work, we consider the regret minimization problem for reinforcement learning in latent Markov Decision Processes (LMDP). In an LMDP, an MDP is randomly drawn from a set of M possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We first show that a general instance of LMDPs requires at least Omega((SA)M) episodes to even approximate the optimal policy. Then, we consider sufficient assumptions under which learning good policies requires polynomial number of episodes. We show that the key link is a notion of separation between the MDP system dynamics. With sufficient separation, we provide an efficient algorithm with local guarantee, it i.e., providing a sublinear regret guarantee when we are given a good initialization. Finally, if we are given standard statistical sufficiency assumptions common in the Predictive State Representation (PSR) literature (e.g., Boots et al.) and a reachability assumption, we show that the need for initialization can be removed.

Key facts. Cited by 69 papers in the map (data through 7 Oct 2026). Builds on 16 of its 49 references that are in the map. First posted on arXiv 9 Feb 2021.

Builds on

16 of 49 references.

References · 16

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2015Contextual Markov Decision Processescited by 213
  4. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  5. 2014Online Clustering of Banditscited by 99
  6. 2016Explore First, Exploit Next: The True Shape of Regret in Bandit Problemscited by 78
  7. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  8. 2020Sample-Efficient Reinforcement Learning of Undercomplete POMDPscited by 66
  9. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  10. 2017Markov Decision Processes with Continuous Side Informationcited by 54
  11. 2016Reinforcement Learning of POMDPs using Spectral Methodscited by 51
  12. 2016On Context-Dependent Clustering of Banditscited by 43
4 more
  1. 2016A PAC RL Algorithm for Episodic POMDPscited by 37
  2. 2019EM Converges for a Mixture of Many Linear Regressionscited by 27
  3. 2020On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regressioncited by 24
  4. 2013PEGASUS: A Policy Search Method for Large MDPs and POMDPscited by 21

Built on by

Cited by year

Citing papers per year: 2021: 4; 2022: 23; 2023: 17; 2024: 14; 2025: 11.

69 papers.

Sort:

By area:

  1. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  2. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  3. 2023POPGym: Benchmarking Partially Observable Reinforcement Learningcited by 59
  4. 2022PAC Reinforcement Learning for Predictive State Representationscited by 42
  5. 2022The Importance of Non-Markovianity in Maximum State Entropy Explorationcited by 35
  6. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  7. 2022On the Complexity of Adversarial Decision Makingcited by 32
  8. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  9. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  10. 2022Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithmscited by 24
  11. 2024Learning to Cooperate with Humans using Generative Agentscited by 23
  12. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 20
38 more
  1. 2022An Instrumental Variable Approach to Confounded Off-Policy Evaluationcited by 20
  2. 2021Sublinear Regret for Learning POMDPscited by 19
  3. 2021Unsupervised Reinforcement Learning in Multiple Environmentscited by 17
  4. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  5. 2023Learning in POMDPs is Sample-Efficient with Hindsight Observabilitycited by 17
  6. 2023Structure in Deep Reinforcement Learning: A Survey and Open Problemscited by 16
  7. 2021Reinforcement Learning in Reward-Mixing MDPscited by 15
  8. 2022Learning Mixtures of Linear Dynamical Systemscited by 15
  9. 2022Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiencycited by 15
  10. 2023Lower Bounds for Learning in Revealing POMDPscited by 14
  11. 2022Model-Free and Model-Based Policy Evaluation when Causality is Uncertaincited by 12
  12. 2022Computationally Efficient PAC RL in POMDPs with Latent Determinism and Conditional Embeddingscited by 12
  13. 2022Learning Mixtures of Markov Chains and MDPscited by 12
  14. 2022Offline Policy Evaluation and Optimization under Confoundingcited by 12
  15. 2024A CMDP-within-online framework for Meta-Safe Reinforcement Learningcited by 12
  16. 2023Reinforcement Learning with History-Dependent Dynamic Contextscited by 11
  17. 2023Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Gamescited by 9
  18. 2024On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluationcited by 9
  19. 2024Hybrid Transfer Reinforcement Learning: Provable Sample Efficiency from Shifted-Dynamics Datacited by 8
  20. 2024Preference Adaptive and Sequential Text-to-Image Generationcited by 8
  21. 2025SPiDR: A Simple Approach for Zero-Shot Safety in Sim-to-Real Transfercited by 8
  22. 2025Statistical Tractability of Off-policy Evaluation of History-dependent Policies in POMDPscited by 7
  23. 2022Group Distributionally Robust Reinforcement Learning with Hierarchical Latent Variablescited by 6
  24. 2023Provably Efficient UCB-type Algorithms For Learning Predictive State Representationscited by 6
  25. 2023Weakly Coupled Deep Q-Networkscited by 6
  26. 2022Reward-Mixing MDPs with a Few Latent Contexts are Learnablecited by 5
  27. 2024RL in Latent MDPs is Tractable: Online Guarantees via Off-Policy Evaluationcited by 5
  28. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  29. 2022Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanismscited by 4
  30. 2023Prospective Side Information for Latent MDPscited by 4
  31. 2025Flow-based Domain Randomization for Learning and Sequencing Robotic Skillscited by 4
  32. 2022Tractable Optimality in Episodic Latent MABscited by 3
  33. 2022Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processescited by 3
  34. 2023Provably Efficient Offline Reinforcement Learning with Perturbed Data Sourcescited by 3
  35. 2023Context-lumpable stochastic banditscited by 3
  36. 2023Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsightcited by 3
  37. 2023Tempo Adaptation in Non-stationary Reinforcement Learningcited by 3
  38. 2024An Empirical Study on the Power of Future Prediction in Partially Observable Environmentscited by 3

50 most cited of 69 All 69 (JSON)