Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors
Abstract
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 Õ(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.
Related
- Elicitation and Decision Geometry in Single-Index Bandits
- Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers
- Quantum 6j-symbols arising from a subfactor of finite index and finite depth and the zipper condition for 4-tensors in two-dimensional topological order
- Pointwise minimax lower bounds under a multi-index constraint: the price of an unknown orientation
- Fast Rates for Offline Contextual Bandits with Forward-KL Regularization under Single-Policy Concentrability
BibTeX
@misc{liu2026lowrank,
title = {{Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors}},
author = {Zhongxuan Liu and Yue Kang and Thomas C. M. Lee},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33025},
eprint = {2609.33025},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33025},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors
AU - Zhongxuan Liu
AU - Yue Kang
AU - Thomas C. M. Lee
PY - 2026
DA - 2026/09/26
PB - arXiv
DO - 10.48550/arxiv.2609.33025
UR - https://arxiv.org/abs/2609.33025
AB - 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 Õ(T^2/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.
ER -