# Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 26 Sep 2026.

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

- [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)
- [Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems](https://mlsanity.com/paper/2401.07298/) (2024)
- [Sub-Gaussian estimators of the mean of a random matrix with heavy-tailed entries](https://mlsanity.com/paper/1605.07129/) (2016)
- [Understanding Implicit Regularization in Over-Parameterized Single Index Model](https://mlsanity.com/paper/2007.08322/) (2020)
- [Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making](https://mlsanity.com/paper/2007.15788/) (2020)
- [Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Bandits](https://mlsanity.com/paper/2402.11156/) (2024)
- [Low-rank Matrix Bandits with Heavy-tailed Rewards](https://mlsanity.com/paper/2404.17709/) (2024)
- [Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions](https://mlsanity.com/paper/2506.12751/) (2025)
- [On High-dimensional and Low-rank Tensor Bandits](https://mlsanity.com/paper/2305.03884/) (2023)
- [Batched Single-Index Global Multi-Armed Bandits with Covariates](https://mlsanity.com/paper/2503.00565/) (2025)
- [On Stein's Identity and Near-Optimal Estimation in High-dimensional Index Models](https://mlsanity.com/paper/1709.08795/) (2017)
- [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)
- [Optimal Regret for Single Index Bandits](https://mlsanity.com/paper/2605.09454/) (2026)

## Abstract (arXiv)

Low-rank matrix and tensor bandits exploit structured interactions but typically assume a known reward link. Recent single-index bandit methods accommodate unknown links without directly exploiting matrix or tensor rank. We address this gap by studying stochastic matrix and tensor bandits with an unknown shared Lipschitz link and a low-rank index parameter under known regular candidate distributions and finite-variance noise. For monotone links, T-ESTOR combines robust, rank-adaptive Stein estimation with epoch-based greedy selection. Under exact selected-score access and a uniformly positive selected-design Stein signal, it achieves square-root regret with dimension dependence determined by the low-rank structure. For every admissible design, the monotone lower bound matches the rank, dimension, and horizon dependence up to logarithmic factors at large horizons, for fixed menu size and model/design constants. For nonmonotone links under a nonzero base-law Stein signal, T-BSTOR combines structured estimation with robust bin-based learning and attains the optimal widetildeO(T2/3) horizon rate for fixed dimensions, menu size, and model/design constants. Synthetic and CCLE-based experiments illustrate the benefits of structured estimation relative to vectorized and competing single-index baseline methods.