We study the exploration problem in episodic MDPs with rich observations generated from a small number of latent states. Under certain identifiability assumptions, we demonstrate how to estimate a mapping from the observations to latent states inductively through a sequence of regression and clustering steps -- where previously decoded latent states provide labels for later regression problems -- and use it to construct good exploration policies. We provide finite-sample guarantees on the quality of the learned state decoding function and exploration policies, and complement our theory with an empirical evaluation on a class of hard exploration problems. Our method exponentially improves over $Q$-learning with na\"ive exploration, even when $Q$-learning has cheating access to latent states.
翻译:我们用从少数潜伏状态产生的丰富观测数据来研究偶发型磁盘的探索问题。根据某些可识别性假设,我们展示了如何通过一系列回归和集群步骤 — — 以前解码的潜伏状态为后来的回归问题提供标签 — — 来估算从观测到潜伏状态的映射,并利用它来构建良好的探索政策。我们为学到的国家解码功能和勘探政策的质量提供了有限样本保证,并以对一类硬质勘探问题的实证评估来补充我们的理论。我们的方法极大地改进了对“纳基”探索的超过$Q的学习,即使“纳基”探索也欺骗了“Q”学习对潜在状态的接触。