# Multilinear Tensor Low-Rank Approximation for Policy-Gradient Methods in Reinforcement Learning

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

## 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 32 of its 59 references that are in the map.
- First posted on arXiv 8 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 32)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [High-Dimensional Continuous Control Using Generalized Advantage Estimation](https://mlsanity.com/paper/1506.02438/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [A Brief Survey of Deep Reinforcement Learning](https://mlsanity.com/paper/1708.05866/) (2017)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [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)
- [Stochastic model-based minimization of weakly convex functions](https://mlsanity.com/paper/1803.06523/) (2018)
- [Policy Mirror Descent for Reinforcement Learning: Linear Convergence, New Sampling Complexity, and Generalized Problem Classes](https://mlsanity.com/paper/2102.00135/) (2021)
- [Representation Learning for Online and Offline RL in Low-rank MDPs](https://mlsanity.com/paper/2110.04652/) (2021)
- [Stochastic subgradient method converges on tame functions](https://mlsanity.com/paper/1804.07795/) (2018)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [On the Convergence and Sample Efficiency of Variance-Reduced Policy Gradient Method](https://mlsanity.com/paper/2102.08607/) (2021)
- [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)
- [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)
- [Beyond Exact Gradients: Convergence of Stochastic Soft-Max Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2110.10117/) (2021)
- [Harnessing Structures for Value-Based Planning and Reinforcement Learning](https://mlsanity.com/paper/1909.12255/) (2019)
- [Optimization for Reinforcement Learning: From Single Agent to Cooperative Agents](https://mlsanity.com/paper/1912.00498/) (2019)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Low-rank State-action Value-function Approximation](https://mlsanity.com/paper/2104.08805/) (2021)
- [Stochastic Policy Gradient Ascent in Reproducing Kernel Hilbert Spaces](https://mlsanity.com/paper/1807.11274/) (2018)
- [Learning Online Alignments with Continuous Rewards Policy Gradient](https://mlsanity.com/paper/1608.01281/) (2016)
- [Nonparametric Stochastic Compositional Gradient Descent for Q-Learning in Continuous Markov Decision Problems](https://mlsanity.com/paper/1804.07323/) (2018)
- [Tensor Low-rank Approximation of Finite-horizon Value Functions](https://mlsanity.com/paper/2405.17628/) (2024)
- [DDPG-Driven Deep-Unfolding with Adaptive Depth for Channel Estimation with Sparse Bayesian Learning](https://mlsanity.com/paper/2201.08477/) (2022)

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

- [Addressing Finite-Horizon MDPs via Low-Rank Tensor Value Approximation](https://mlsanity.com/paper/2501.10598/) (2025)
- [From Classical to Quantum Reinforcement Learning and Its Applications in Quantum Control: A Beginner's Tutorial](https://mlsanity.com/paper/2601.08662/) (2026)
- [Factorized Spectral Representations for Reinforcement Learning](https://mlsanity.com/paper/2607.13498/) (2026)

## Abstract (arXiv)

Reinforcement learning (RL) aims to estimate the action to take given a (time-varying) state, with the goal of maximizing a cumulative reward function. Predominantly, there are two families of algorithms to solve RL problems: value-based and policy-based methods, with the latter designed to learn a probabilistic parametric policy from states to actions. Most contemporary approaches implement this policy using a neural network (NN). However, NNs usually face issues related to convergence, architectural suitability, hyper-parameter selection, and underutilization of the redundancies of the state-action representations (e.g. locally similar states). This paper postulates multi-linear mappings to efficiently estimate the parameters of the RL policy. More precisely, we leverage the PARAFAC decomposition to design tensor low-rank policies. The key idea involves collecting the policy parameters into a tensor and leveraging tensor-completion techniques to enforce low rank. We establish theoretical guarantees of the proposed methods for various policy classes and validate their efficacy through numerical experiments. Specifically, we demonstrate that tensor low-rank policy models reduce computational and sample complexities in comparison to NN models while achieving similar rewards.