Near-Optimal Learning and Planning in Separated Latent MDPs
This work addresses computational and statistical challenges in reinforcement learning for separated latent MDPs, offering theoretical insights with potential applications in domains like robotics or AI planning, though it is incremental in refining existing impossibility results.
The paper tackles the problem of learning Latent Markov Decision Processes (LMDPs) by establishing a nearly-sharp statistical threshold for the horizon length needed for efficient learning, and provides a quasi-polynomial algorithm under a weaker separability assumption with a near-matching lower bound.
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.