# Tensor-Efficient High-Dimensional Q-learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 14 of its 46 references that are in the map.
- First posted on arXiv 5 Nov 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, 14 of 14)

- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Challenges of Real-World Reinforcement Learning](https://mlsanity.com/paper/1904.12901/) (2019)
- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Deep Exploration via Randomized Value Functions](https://mlsanity.com/paper/1703.07608/) (2017)
- [The Uncertainty Bellman Equation and Exploration](https://mlsanity.com/paper/1709.05380/) (2017)
- [Q-learning with UCB Exploration is Sample Efficient for Infinite-Horizon MDP](https://mlsanity.com/paper/1901.09311/) (2019)
- [Sample Efficient Reinforcement Learning via Low-Rank Matrix Estimation](https://mlsanity.com/paper/2006.06135/) (2020)
- [Tensor and Matrix Low-Rank Value-Function Approximation in Reinforcement Learning](https://mlsanity.com/paper/2201.09736/) (2022)
- [Overcoming the Curse of Dimensionality in Reinforcement Learning Through Approximate Factorization](https://mlsanity.com/paper/2411.07591/) (2024)
- [How Informative is the Approximation Error from Tensor Decomposition for Neural Network Compression?](https://mlsanity.com/paper/2305.05318/) (2023)

## Abstract (arXiv)

High-dimensional reinforcement learning(RL) faces challenges with complex calculations and low sample efficiency in large state-action spaces. Q-learning algorithms struggle particularly with the curse of dimensionality, where the number of state-action pairs grows exponentially with problem size. While neural network-based approaches like Deep Q-Networks have shown success, they do not explicitly exploit problem structure. Many high-dimensional control tasks exhibit low-rank structure in their value functions, and tensor-based methods using low-rank decomposition offer parameter-efficient representations. However, existing tensor-based Q-learning methods focus on representation fidelity without leveraging this structure for exploration. We propose Tensor-Efficient Q-Learning (TEQL), which represents the Q-function as a low-rank CP tensor over discretized state-action spaces and exploits the tensor structure for uncertainty-aware exploration. TEQL incorporates Error-Uncertainty Guided Exploration (EUGE), which combines tensor approximation error with visit counts to guide action selection, along with frequency-aware regularization to stabilize updates. Under matched parameter budgets, experiments on classic control tasks demonstrate that TEQL outperforms both matrix-based low-rank methods and deep RL baselines in sample efficiency, making it suitable for resource-constrained applications where sampling costs are high.