  Reinforcement learning (RL) in Markov decision processes (MDPs) with large
state spaces is a challenging problem. The performance of standard RL
algorithms degrades drastically with the dimensionality of state space.
However, in practice, these large MDPs typically incorporate a latent or hidden
low-dimensional structure. In this paper, we study the setting of
rich-observation Markov decision processes (ROMDP), where there are a small
number of hidden states which possess an injective mapping to the observation
states. In other words, every observation state is generated through a single
hidden state, and this mapping is unknown a priori. We introduce a spectral
decomposition method that consistently learns this mapping, and more
importantly, achieves it with low regret. The estimated mapping is integrated
into an optimistic RL algorithm (UCRL), which operates on the estimated hidden
space. We derive finite-time regret bounds for our algorithm with a weak
dependence on the dimensionality of the observed space. In fact, our algorithm
asymptotically achieves the same average regret as the oracle UCRL algorithm,
which has the knowledge of the mapping from hidden to observed spaces. Thus, we
derive an efficient spectral RL algorithm for ROMDPs.
