# On High-dimensional and Low-rank Tensor Bandits

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 26 references that are in the map.
- First posted on arXiv 6 May 2023.

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

- [Tensor Decomposition for Signal Processing and Machine Learning](https://mlsanity.com/paper/1607.01668/) (2016)
- [Bilinear Bandits with Low-rank Structure](https://mlsanity.com/paper/1901.02470/) (2019)
- [Low-Rank Generalized Linear Bandit Problems](https://mlsanity.com/paper/2006.02948/) (2020)
- [An Optimal Statistical and Computational Framework for Generalized Tensor Estimation](https://mlsanity.com/paper/2002.11255/) (2020)
- [Provable Tensor Factorization with Missing Data](https://mlsanity.com/paper/1406.2784/) (2014)
- [Tucker Tensor Regression and Neuroimaging Analysis](https://mlsanity.com/paper/1304.5637/) (2013)
- [Tensor Methods and Recommender Systems](https://mlsanity.com/paper/1603.06038/) (2016)
- [Statistically Optimal and Computationally Efficient Low Rank Tensor Completion from Noisy Entries](https://mlsanity.com/paper/1711.04934/) (2017)
- [ISLET: Fast and Optimal Low-rank Tensor Regression via Importance Sketching](https://mlsanity.com/paper/1911.03804/) (2019)
- [Tensor Regression Using Low-rank and Sparse Tucker Decompositions](https://mlsanity.com/paper/1911.03725/) (2019)
- [Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making](https://mlsanity.com/paper/2007.15788/) (2020)
- [Tensor Completion from Regular Sub-Nyquist Samples](https://mlsanity.com/paper/1903.00435/) (2019)

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

- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)
- [Efficient Generalized Low-Rank Tensor Contextual Bandits](https://mlsanity.com/paper/2311.01771/) (2023)
- [A Unified Regularization Approach to High-Dimensional Generalized Tensor Bandits](https://mlsanity.com/paper/2501.10722/) (2025)
- [Navigating Sparsities in High-Dimensional Linear Contextual Bandits](https://mlsanity.com/paper/2510.08435/) (2025)
- [Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors](https://mlsanity.com/paper/2609.33025/) (2026)

## Abstract (arXiv)

Most existing studies on linear bandits focus on the one-dimensional characterization of the overall system. While being representative, this formulation may fail to model applications with high-dimensional but favorable structures, such as the low-rank tensor representation for recommender systems. To address this limitation, this work studies a general tensor bandits model, where actions and system parameters are represented by tensors as opposed to vectors, and we particularly focus on the case that the unknown system tensor is low-rank. A novel bandit algorithm, coined TOFU (Tensor Optimism in the Face of Uncertainty), is developed. TOFU first leverages flexible tensor regression techniques to estimate low-dimensional subspaces associated with the system tensor. These estimates are then utilized to convert the original problem to a new one with norm constraints on its system parameters. Lastly, a norm-constrained bandit subroutine is adopted by TOFU, which utilizes these constraints to avoid exploring the entire high-dimensional parameter space. Theoretical analyses show that TOFU improves the best-known regret upper bound by a multiplicative factor that grows exponentially in the system order. A novel performance lower bound is also established, which further corroborates the efficiency of TOFU.