Near-Optimal Learning and Planning in Separated Latent MDPs

Autor:	Chen, Fan, Daskalakis, Constantinos, Golowich, Noah, Rakhlin, Alexander
Rok vydání:	2024
Předmět:	Computer Science - Machine Learning Computer Science - Artificial Intelligence Computer Science - Computational Complexity Mathematics - Statistics Theory Statistics - Machine Learning
Druh dokumentu:	Working Paper
Popis:	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. Comment: COLT 2024
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2406.07920 Zobrazit plný text záznamu View this record from Arxiv