  Partially Observable Markov Decision Processes (POMDPs) are a natural and
general model in reinforcement learning that take into account the agent's
uncertainty about its current state. In the literature on POMDPs, it is
customary to assume access to a planning oracle that computes an optimal policy
when the parameters are known, even though the problem is known to be
computationally hard. Almost all existing planning algorithms either run in
exponential time, lack provable performance guarantees, or require placing
strong assumptions on the transition dynamics under every possible policy. In
this work, we revisit the planning problem and ask: are there natural and
well-motivated assumptions that make planning easy?
  Our main result is a quasipolynomial-time algorithm for planning in
(one-step) observable POMDPs. Specifically, we assume that well-separated
distributions on states lead to well-separated distributions on observations,
and thus the observations are at least somewhat informative in each step.
Crucially, this assumption places no restrictions on the transition dynamics of
the POMDP; nevertheless, it implies that near-optimal policies admit
quasi-succinct descriptions, which is not true in general (under standard
hardness assumptions). Our analysis is based on new quantitative bounds for
filter stability -- i.e. the rate at which an optimal filter for the latent
state forgets its initialization. Furthermore, we prove matching hardness for
planning in observable POMDPs under the Exponential Time Hypothesis.
