Abstract
We study the 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 $L$ MDPs. To sidestep known impossibility results associated with Partially Observable MDPs (POMDPs), we consider several notions of separation between the constituent MDPs. The primary contribution of this work is the establishment of a nearly-sharp statistical threshold for the horizon length ($H$) necessary for efficient learning. On the computational side, we demonstrate that under the assumption of separability under the optimal policy, there exists a quasi-polynomial algorithm with time complexity scaling in terms of this statistical threshold. Furthermore, we provide a near-matching time complexity lower bound conditioned on the Exponential Time Hypothesis (ETH).
Introduction
Standard Reinforcement Learning (RL) assumes the environment follows a Markov Decision Process (MDP), where the current state provides sufficient information for optimal decision-making. However, real-world scenarios often involve latent variables—unobserved factors that change the dynamics of the environment. For example, a robot's physical dynamics might change based on varying weather conditions, or a recommendation system might interact with different user archetypes.
These scenarios are modeled as Latent MDPs (LMDPs). At the start of each episode, a latent index is sampled from a distribution, determining which of $L$ possible MDPs the agent will face. While LMDPs are a subset of POMDPs, they are generally intractable, often requiring exponential sample complexity or being PSPACE-hard to solve. This paper investigates the specific conditions—specifically the relationship between the episode horizon and environment separation—that allow us to break these hardness barriers.
The Statistical Threshold of the Horizon
The central insight of this research is that the horizon length ($H$) acts as a fundamental toggle for complexity. If the episode is too short, the agent cannot gather enough evidence to identify the latent environment, leading to exponential complexity. If the horizon is sufficiently long, the latent nature of the problem can be resolved.
$\delta$-Strong Separation
The authors focus on $\delta$-strongly separated LMDPs. In this setting, for every state-action pair, the transition distributions of any two latent MDPs differ by at least $\delta$ in total variation distance. The paper identifies a sharp threshold:
$$H_* \approx \frac{\log(L/\epsilon)}{\delta^2}$$
- Below the Threshold ($H < H_*$): Learning is exponentially hard. The agent cannot reliably "decode" which latent MDP it is in, necessitating a sample complexity that scales exponentially with the number of latent states.
- Above the Threshold ($H \ge H_*$): The agent can identify the latent state with high probability, making the problem statistically tractable with polynomial sample complexity.
Algorithmic Frameworks
1. Learning: Optimistic Maximum Likelihood Estimation (OMLE)
For the learning setting (where the models are unknown), the authors propose a variant of OMLE. The algorithm maintains a confidence set of possible LMDP models consistent with observed trajectories. By selecting the most optimistic model within this set to guide exploration, the agent can achieve $\epsilon$-optimal performance using a polynomial number of samples, provided the horizon exceeds the statistical threshold.
2. Planning: Short Memory Planning
In the planning setting (where models are known but the latent index is hidden), the authors use a context inference approach. The agent utilizes the initial $W$ steps of an episode to decode the latent MDP index. Once the environment is identified with sufficient confidence, the agent switches to the optimal policy for that specific MDP.
Computational Complexity and Lower Bounds
While the sample complexity becomes polynomial above the threshold, the computational complexity remains a challenge. The paper proves that planning in a known $\delta$-separated LMDP can be achieved in $(SA)^{O(\delta^{-2} \log(L/\epsilon))}$ time.
Crucially, the authors provide a near-matching lower bound using the Exponential Time Hypothesis (ETH). They show that unless ETH is false, a purely polynomial-time algorithm is generally unattainable; quasi-polynomial complexity is the best possible performance for this class of problems. This suggests that while the "statistical" barrier is broken by a long horizon, a "computational" barrier inherent to the latent structure persists.
Conclusion
This work clarifies the boundaries of tractability in Latent MDPs. By identifying the sharp statistical threshold of the horizon length, it provides a roadmap for when complex RL tasks involving hidden contexts become solvable. While the requirement for $\delta$-strong separation is a significant assumption, the transition from exponential to quasi-polynomial complexity marks a major step forward in understanding the limits of reinforcement learning in partially observable environments. Future work remains to extend these findings from tabular settings to large-scale environments using function approximation.
Summary updated