  POMDPs capture a broad class of decision making problems, but hardness
results suggest that learning is intractable even in simple settings due to the
inherent partial observability. However, in many realistic problems, more
information is either revealed or can be computed during some point of the
learning process. Motivated by diverse applications ranging from robotics to
data center scheduling, we formulate a Hindsight Observable Markov Decision
Process (HOMDP) as a POMDP where the latent states are revealed to the learner
in hindsight and only during training. We introduce new algorithms for the
tabular and function approximation settings that are provably sample-efficient
with hindsight observability, even in POMDPs that would otherwise be
statistically intractable. We give a lower bound showing that the tabular
algorithm is optimal in its dependence on latent state and observation
cardinalities.
