  We study reinforcement learning with function approximation for large-scale
Partially Observable Markov Decision Processes (POMDPs) where the state space
and observation space are large or even continuous. Particularly, we consider
Hilbert space embeddings of POMDP where the feature of latent states and the
feature of observations admit a conditional Hilbert space embedding of the
observation emission process, and the latent state transition is deterministic.
Under the function approximation setup where the optimal latent state-action
$Q$-function is linear in the state feature, and the optimal $Q$-function has a
gap in actions, we provide a \emph{computationally and statistically efficient}
algorithm for finding the \emph{exact optimal} policy. We show our algorithm's
computational and statistical complexities scale polynomially with respect to
the horizon and the intrinsic dimension of the feature on the observation
space. Furthermore, we show both the deterministic latent transitions and gap
assumptions are necessary to avoid statistical complexity exponential in
horizon or dimension. Since our guarantee does not have an explicit dependence
on the size of the state and observation spaces, our algorithm provably scales
to large-scale POMDPs.
