We consider the problem of model estimation in episodic Block MDPs. In these MDPs, the decision maker has access to rich observations or contexts generated from a small number of latent states. We are interested in estimating the latent state decoding function (the mapping from the observations to latent states) based on data generated under a fixed behavior policy. We derive an information-theoretical lower bound on the error rate for estimating this function and present an algorithm approaching this fundamental limit. In turn, our algorithm also provides estimates of all the components of the MDP. We apply our results to the problem of learning near-optimal policies in the reward-free setting. Based on our efficient model estimation algorithm, we show that one can infer a policy converging (as the number of collected samples grows large) to the optimal policy at the best possible asymptotic rate. Our analysis provides necessary and sufficient conditions under which exploiting the block structure yields improvements in the sample complexity for identifying near-optimal policies. When these conditions are met, the sample complexities in the offline reward-free setting are improved by a multiplicative factor $n$, where $n$ is the number of contexts.
이 논문은 블락 마르코프 결정 과정의 모델 추정 문제를 다루었다. 정 과정에서 의사 결정자가 매우 큰 관찰공간에서 샘플들을 관찰할 수 있고, 이 관찰공간은 결정자가 관찰할 수 없는 다소 작은 잠재공간에서 생성된다. 우리의 목적은 주어진 샘플들을 바탕으로, 관찰공간에서 잠재공간으로 가는 디코딩 함수를 추정하는 것이다. 우리는 먼저 정보 이론적 오류율의 하한을 도출하고, 이 하한에 근접하는 알고리즘을 제시한다. 그 다음, 이 결과를 바탕으로 우리는 보상없는 강화학습에서 역시 최적의 정책으로 수렴할 수 있음을 보인다. 특히 우리는, 블락 구조를 활용하였을 때 최적의 정책을 얻는데 필요한 샘플 복잡도이 언제 개선되는지에 대한 필요충분조건을 얻는다. 이 조건이 만족되면, 오프라인 보상없는 강화학습의 샘플 복잡도가 관찰공간의 크기만큼 개선된다.
