# Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 56 references that are in the map.
- First posted on arXiv 21 Jan 2022.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [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)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [TensorLy: Tensor Learning in Python](https://mlsanity.com/paper/1610.09555/) (2016)
- [Tensor Comprehensions: Framework-Agnostic High-Performance Machine Learning Abstractions](https://mlsanity.com/paper/1802.04730/) (2018)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [Reinforcement Learning of POMDPs using Spectral Methods](https://mlsanity.com/paper/1602.07764/) (2016)
- [Revisiting Normalized Gradient Descent: Fast Evasion of Saddle Points](https://mlsanity.com/paper/1711.05224/) (2017)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Tesseract: Tensorised Actors for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2106.00136/) (2021)
- [Harnessing Structures for Value-Based Planning and Reinforcement Learning](https://mlsanity.com/paper/1909.12255/) (2019)
- [Hybrid Reinforcement Learning with Expert State Sequences](https://mlsanity.com/paper/1903.04110/) (2019)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [Low-rank State-action Value-function Approximation](https://mlsanity.com/paper/2104.08805/) (2021)
- [Value function approximation via low-rank models](https://mlsanity.com/paper/1509.00061/) (2015)
- [Model based Multi-agent Reinforcement Learning with Tensor Decompositions](https://mlsanity.com/paper/2110.14524/) (2021)

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

- [Identifiability of Deep Polynomial Neural Networks](https://mlsanity.com/paper/2506.17093/) (2025)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Tensor Low-rank Approximation of Finite-horizon Value Functions](https://mlsanity.com/paper/2405.17628/) (2024)
- [Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learning](https://mlsanity.com/paper/2501.04879/) (2025)
- [Matrix Low-Rank Trust Region Policy Optimization](https://mlsanity.com/paper/2405.17625/) (2024)
- [Matrix Low-Rank Approximation For Policy Gradient Methods](https://mlsanity.com/paper/2405.17626/) (2024)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)
- [The Limits of Transfer Reinforcement Learning with Latent Low-rank Structure](https://mlsanity.com/paper/2410.21601/) (2024)
- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [A Tensor Low-Rank Approximation for Value Functions in Multi-Task Reinforcement Learning](https://mlsanity.com/paper/2501.10529/) (2025)
- [Unrolling Dynamic Programming via Graph Filters](https://mlsanity.com/paper/2507.21705/) (2025)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)
- [Tensor-Efficient High-Dimensional Q-learning](https://mlsanity.com/paper/2511.03595/) (2025)
- [Factorized Spectral Representations for Reinforcement Learning](https://mlsanity.com/paper/2607.13498/) (2026)
- [A Contraction Framework for Stochastic Operators with Bootstrapping: Application to TD Learning](https://mlsanity.com/paper/2609.29961/) (2026)

## Abstract (arXiv)

Value-function (VF) approximation is a central problem in Reinforcement Learning (RL). Classical non-parametric VF estimation suffers from the curse of dimensionality. As a result, parsimonious parametric models have been adopted to approximate VFs in high-dimensional spaces, with most efforts being focused on linear and neural-network-based approaches. Differently, this paper puts forth a a parsimonious non-parametric approach, where we use stochastic low-rank algorithms to estimate the VF matrix in an online and model-free fashion. Furthermore, as VFs tend to be multi-dimensional, we propose replacing the classical VF matrix representation with a tensor (multi-way array) representation and, then, use the PARAFAC decomposition to design an online model-free tensor low-rank algorithm. Different versions of the algorithms are proposed, their complexity is analyzed, and their performance is assessed numerically using standardized RL environments.