# Reinforcement Learning in Rich-Observation MDPs using Spectral Methods

arXiv: https://arxiv.org/abs/1611.03907 · HTML: https://mlsanity.com/paper/1611.03907/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Nov 2016.

## Built on by (most cited first, 13 of 13)

- [Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00136/) (2021)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Structure in Deep Reinforcement Learning: A Survey and Open Problems](https://mlsanity.com/paper/2306.16021/) (2023)
- [Three Dogmas of Reinforcement Learning](https://mlsanity.com/paper/2407.10583/) (2024)
- [Learning Efficiently Function Approximation for Contextual MDP](https://mlsanity.com/paper/2203.00995/) (2022)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Reinforcement Learning in Factored Action Spaces using Tensor Decompositions](https://mlsanity.com/paper/2110.14538/) (2021)
- [An Analysis of Model-Based Reinforcement Learning From Abstracted Observations](https://mlsanity.com/paper/2208.14407/) (2022)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)
- [Detection and Evaluation of Clusters within Sequential Data](https://mlsanity.com/paper/2210.01679/) (2022)
- [Estimating the number of clusters of a Block Markov Chain](https://mlsanity.com/paper/2407.18287/) (2024)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [Near-Optimal Clustering in Mixture of Markov Chains](https://mlsanity.com/paper/2506.01324/) (2025)

## Abstract (arXiv)

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.