Sample-Efficient Reinforcement Learning of Undercomplete POMDPs
  Partial observability is a common challenge in many reinforcement learning
applications, which requires an agent to maintain memory, infer latent states,
and integrate this past information into exploration. This challenge leads to a
number of computational and statistical hardness results for learning general
Partially Observable Markov Decision Processes (POMDPs). This work shows that
these hardness barriers do not preclude efficient reinforcement learning for
rich and interesting subclasses of POMDPs. In particular, we present a
sample-efficient algorithm, OOM-UCB, for episodic finite undercomplete POMDPs,
where the number of observations is larger than the number of latent states and
where exploration is essential for learning, thus distinguishing our results
from prior works. OOM-UCB achieves an optimal sample complexity of
$\tilde{\mathcal{O}}(1/\varepsilon^2)$ for finding an $\varepsilon$-optimal
policy, along with being polynomial in all other relevant quantities. As an
interesting special case, we also provide a computationally and statistically
efficient algorithm for POMDPs with deterministic state transitions.
