Abstract
Partial observability is a common challenge in many reinforcement learningapplications, which requires an agent to maintain memory, infer latent states,and integrate this past information into exploration. This challenge leads to anumber of computational and statistical hardness results for learning generalPartially Observable Markov Decision Processes (POMDPs). This work shows thatthese hardness barriers do not preclude efficient reinforcement learning forrich and interesting subclasses of POMDPs. In particular, we present asample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs,where the number of observations is larger than the number of latent states andwhere exploration is essential for learning, thus distinguishing our resultsfrom prior works. OOM-UCB achieves an optimal sample complexity of$O(1/\epsilon^2)$ for finding an $\epsilon$-optimal policy, along with beingpolynomial in all other relevant quantities. As an interesting special case, wealso provide a computationally and statistically efficient algorithm for POMDPswith deterministic state transitions.