Near-Optimal Learning and Planning in Separated Latent MDPs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911914259382272 |
|---|---|
| author | Chen, Fan Daskalakis, Constantinos Golowich, Noah Rakhlin, Alexander |
| author_facet | Chen, Fan Daskalakis, Constantinos Golowich, Noah Rakhlin, Alexander |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_07920 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Learning and Planning in Separated Latent MDPs Chen, Fan Daskalakis, Constantinos Golowich, Noah Rakhlin, Alexander Machine Learning Artificial Intelligence Computational Complexity Statistics Theory 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. |
| title | Near-Optimal Learning and Planning in Separated Latent MDPs |
| topic | Machine Learning Artificial Intelligence Computational Complexity Statistics Theory |
| url | https://arxiv.org/abs/2406.07920 |