Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency
Reinforcement learning in partially observed Markov decision processes
(POMDPs) faces two challenges. (i) It often takes the full history to predict
the future, which induces a sample complexity that scales exponentially with
the horizon. (ii) The observation and state spaces are often continuous, which
induces a sample complexity that scales exponentially with the extrinsic
dimension. Addressing such challenges requires learning a minimal but
sufficient representation of the observation and state histories by exploiting
the structure of the POMDP.
  To this end, we propose a reinforcement learning algorithm named Embed to
Control (ETC), which learns the representation at two levels while optimizing
the policy.~(i) For each step, ETC learns to represent the state with a
low-dimensional feature, which factorizes the transition kernel. (ii) Across
multiple steps, ETC learns to represent the full history with a low-dimensional
embedding, which assembles the per-step feature. We integrate (i) and (ii) in a
unified framework that allows a variety of estimators (including maximum
likelihood estimators and generative adversarial networks). For a class of
POMDPs with a low-rank structure in the transition kernel, ETC attains an
$O(1/\epsilon^2)$ sample complexity that scales polynomially with the horizon
and the intrinsic dimension (that is, the rank). Here $\epsilon$ is the
optimality gap. To our best knowledge, ETC is the first sample-efficient
algorithm that bridges representation learning and policy optimization in
POMDPs with infinite observation and state spaces.