# Learning Good State and Action Representations via Tensor Decomposition

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 65 references that are in the map.
- First posted on arXiv 3 May 2021.

## Builds on (most cited first, 26 of 26)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?](https://mlsanity.com/paper/1910.03016/) (2019)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Model-free Representation Learning and Exploration in Low-rank MDPs](https://mlsanity.com/paper/2102.07035/) (2021)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [Tensor SVD: Statistical and Computational Limits](https://mlsanity.com/paper/1703.02724/) (2017)
- [Eigendecompositions of Transfer Operators in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/1712.01572/) (2017)
- [Rate-Optimal Perturbation Bounds for Singular Subspaces with Applications to High-Dimensional Statistics](https://mlsanity.com/paper/1605.00353/) (2016)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [On Online Learning in Kernelized Markov Decision Processes](https://mlsanity.com/paper/1911.01871/) (2019)
- [Generalized Canonical Polyadic Tensor Decomposition](https://mlsanity.com/paper/1808.07452/) (2018)
- [Guaranteed Non-Orthogonal Tensor Decomposition via Alternating Rank-1 Updates](https://mlsanity.com/paper/1402.5180/) (2014)
- [Spectral State Compression of Markov Processes](https://mlsanity.com/paper/1802.02920/) (2018)
- [Provable Sparse Tensor Decomposition](https://mlsanity.com/paper/1502.01425/) (2015)
- [Spectral Learning on Matrices and Tensors](https://mlsanity.com/paper/2004.07984/) (2020)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [Learning Markov models via low-rank optimization](https://mlsanity.com/paper/1907.00113/) (2019)
- [Cross: Efficient Low-rank Tensor Completion](https://mlsanity.com/paper/1611.01129/) (2016)
- [Optimal Sparse Singular Value Decomposition for High-dimensional High-order Data](https://mlsanity.com/paper/1809.01796/) (2018)
- [Learning low-dimensional state embeddings and metastable clusters from time series data](https://mlsanity.com/paper/1906.00302/) (2019)
- [Spectral thresholding for the estimation of Markov chain transition operators](https://mlsanity.com/paper/1808.08153/) (2018)

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

- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Learning Bellman Complete Representations for Offline Policy Evaluation](https://mlsanity.com/paper/2207.05837/) (2022)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Off-policy Evaluation with Deeply-abstracted States](https://mlsanity.com/paper/2406.19531/) (2024)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [Realistic Curriculum Reinforcement Learning for Autonomous and Sustainable Marine Vessel Navigation](https://mlsanity.com/paper/2601.10911/) (2026)
- [Safe Reinforcement Learning in Tensor Reproducing Kernel Hilbert Space](https://mlsanity.com/paper/2312.00727/) (2023)

## Abstract (arXiv)

The transition kernel of a continuous-state-action Markov decision process (MDP) admits a natural tensor structure. This paper proposes a tensor-inspired unsupervised learning method to identify meaningful low-dimensional state and action representations from empirical trajectories. The method exploits the MDP's tensor structure by kernelization, importance sampling and low-Tucker-rank approximation. This method can be further used to cluster states and actions respectively and find the best discrete MDP abstraction. We provide sharp statistical error bounds for tensor concentration and the preservation of diffusion distance after embedding. We further prove that the learned state/action abstractions provide accurate approximations to latent block structures if they exist, enabling function approximation in downstream tasks such as policy evaluation.