# Low-rank State-action Value-function Approximation

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 21 references that are in the map.
- First posted on arXiv 18 Apr 2021.

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

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Generalized Low Rank Models](https://mlsanity.com/paper/1410.0342/) (2014)
- [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)
- [Harnessing Structures for Value-Based Planning and Reinforcement Learning](https://mlsanity.com/paper/1909.12255/) (2019)
- [Factorized Q-Learning for Large-Scale Multi-Agent Systems](https://mlsanity.com/paper/1809.03738/) (2018)
- [Value function approximation via low-rank models](https://mlsanity.com/paper/1509.00061/) (2015)

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

- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Towards Global Optimality in Cooperative MARL with the Transformation And Distillation Framework](https://mlsanity.com/paper/2207.11143/) (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)
- [Applications of Reinforcement Learning in Finance -- Trading with a Double Deep Q-Network](https://mlsanity.com/paper/2206.14267/) (2022)
- [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)
- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [ADARL: Adaptive Low-Rank Structures for Robust Policy Learning under Uncertainty](https://mlsanity.com/paper/2510.11899/) (2025)

## Abstract (arXiv)

Value functions are central to Dynamic Programming and Reinforcement Learning but their exact estimation suffers from the curse of dimensionality, challenging the development of practical value-function (VF) estimation algorithms. Several approaches have been proposed to overcome this issue, from non-parametric schemes that aggregate states or actions to parametric approximations of state and action VFs via, e.g., linear estimators or deep neural networks. Relevantly, several high-dimensional state problems can be well-approximated by an intrinsic low-rank structure. Motivated by this and leveraging results from low-rank optimization, this paper proposes different stochastic algorithms to estimate a low-rank factorization of the Q(s, a) matrix. This is a non-parametric alternative to VF approximation that dramatically reduces the computational and sample complexities relative to classical Q-learning methods that estimate Q(s,a) separately for each state-action pair.