# Tensor Low-rank Approximation of Finite-horizon Value Functions

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 27 May 2024.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

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

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis](https://mlsanity.com/paper/1812.04300/) (2018)
- [Harnessing Structures for Value-Based Planning and Reinforcement Learning](https://mlsanity.com/paper/1909.12255/) (2019)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Fixed-Horizon Temporal Difference Methods for Stable Reinforcement Learning](https://mlsanity.com/paper/1909.03906/) (2019)
- [Low-rank State-action Value-function Approximation](https://mlsanity.com/paper/2104.08805/) (2021)
- [Approximating optimal feedback controllers of finite horizon control problems using hierarchical tensor formats](https://mlsanity.com/paper/2104.06108/) (2021)
- [Finite Horizon Q-learning: Stability, Convergence, Simulations and an application on Smart Grids](https://mlsanity.com/paper/2110.15093/) (2021)

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

- [Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learning](https://mlsanity.com/paper/2501.04879/) (2025)
- [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)

## Abstract (arXiv)

The goal of reinforcement learning is estimating a policy that maps states to actions and maximizes the cumulative reward of a Markov Decision Process (MDP). This is oftentimes achieved by estimating first the optimal (reward) value function (VF) associated with each state-action pair. When the MDP has an infinite horizon, the optimal VFs and policies are stationary under mild conditions. However, in finite-horizon MDPs, the VFs (hence, the policies) vary with time. This poses a challenge since the number of VFs to estimate grows not only with the size of the state-action space but also with the time horizon. This paper proposes a non-parametric low-rank stochastic algorithm to approximate the VFs of finite-horizon MDPs. First, we represent the (unknown) VFs as a multi-dimensional array, or tensor, where time is one of the dimensions. Then, we use rewards sampled from the MDP to estimate the optimal VFs. More precisely, we use the (truncated) PARAFAC decomposition to design an online low-rank algorithm that recovers the entries of the tensor of VFs. The size of the low-rank PARAFAC model grows additively with respect to each of its dimensions, rendering our approach efficient, as demonstrated via numerical experiments.