# Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation

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

## Key facts

- Cited by 1 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 30 of its 64 references that are in the map.
- First posted on arXiv 17 Jan 2025.

## 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, 30 of 30)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Revisiting Fundamentals of Experience Replay](https://mlsanity.com/paper/2007.06700/) (2020)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning](https://mlsanity.com/paper/1510.08906/) (2015)
- [A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with Constraints](https://mlsanity.com/paper/2009.11348/) (2020)
- [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)
- [Block stochastic gradient iteration for convex and nonconvex optimization](https://mlsanity.com/paper/1408.2597/) (2014)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [TD Convergence: An Optimization Perspective](https://mlsanity.com/paper/2306.17750/) (2023)
- [Reinforcement Learning in Rich-Observation MDPs using Spectral Methods](https://mlsanity.com/paper/1611.03907/) (2016)
- [High-Dimensional Stochastic Optimal Control using Continuous Tensor Decompositions](https://mlsanity.com/paper/1611.04706/) (2016)
- [Fixed-Horizon Temporal Difference Methods for Stable Reinforcement Learning](https://mlsanity.com/paper/1909.03906/) (2019)
- [Provably Efficient Representation Selection in Low-rank Markov Decision Processes: From Online to Offline RL](https://mlsanity.com/paper/2106.11935/) (2021)
- [Low-rank State-action Value-function Approximation](https://mlsanity.com/paper/2104.08805/) (2021)
- [Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning](https://mlsanity.com/paper/2310.06793/) (2023)
- [Learning Good State and Action Representations via Tensor Decomposition](https://mlsanity.com/paper/2105.01136/) (2021)
- [Overcoming the Long Horizon Barrier for Sample-Efficient Reinforcement Learning with Latent Low-Rank Structure](https://mlsanity.com/paper/2206.03569/) (2022)
- [Multi-task Reinforcement Learning in Reproducing Kernel Hilbert Spaces via Cross-learning](https://mlsanity.com/paper/2008.11895/) (2020)
- [Approximating optimal feedback controllers of finite horizon control problems using hierarchical tensor formats](https://mlsanity.com/paper/2104.06108/) (2021)
- [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)
- [e-COP : Episodic Constrained Optimization of Policies](https://mlsanity.com/paper/2406.09563/) (2024)
- [Low-Rank Tensors for Multi-Dimensional Markov Models](https://mlsanity.com/paper/2411.02098/) (2024)

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

- [Unrolling Dynamic Programming via Graph Filters](https://mlsanity.com/paper/2507.21705/) (2025)

## Abstract (arXiv)

We study the problem of learning optimal policies in finite-horizon Markov Decision Processes (MDPs) using low-rank reinforcement learning (RL) methods. In finite-horizon MDPs, the policies, and therefore the value functions (VFs) are not stationary. This aggravates the challenges of high-dimensional MDPs, as they suffer from the curse of dimensionality and high sample complexity. To address these issues, we propose modeling the VFs of finite-horizon MDPs as low-rank tensors, enabling a scalable representation that renders the problem of learning optimal policies tractable. Our approach focuses on VF approximation within a policy iteration framework, where low-rank policy evaluation is combined with greedy policy improvement to compute near-optimal policies. We introduce an optimization-based framework for solving the Bellman equations with low-rank constraints, along with block-coordinate descent (BCD) and block-coordinate gradient descent (BCGD) algorithms, both with theoretical convergence guarantees. We further establish that bounded low-rank policy evaluation error translates into bounded policy improvement in the finite-horizon setting. For scenarios where the system dynamics are unknown, we adapt the proposed BCGD method to estimate the VFs using sampled trajectories. Numerical experiments further demonstrate that the proposed framework reduces computational demands in controlled synthetic scenarios and more realistic resource allocation problems, while achieving competitive policy performance in terms of attained returns.