Learning in POMDPs is Sample-Efficient with Hindsight Observability
This addresses a fundamental challenge in decision-making for applications like robotics and data center scheduling, offering a novel framework to bypass statistical intractability in POMDPs.
The paper tackles the intractability of learning in partially observable Markov decision processes (POMDPs) by introducing Hindsight Observable MDPs (HOMDPs), where latent states are revealed during training, and provides sample-efficient algorithms with optimality guarantees for tabular and function approximation settings.
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.