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

Zhongxuan Liu; Yue Kang; Thomas C. M. Lee

cs.LGSep 26, 2026

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

Authors: Zhongxuan Liu, Yue Kang, Thomas C. M. Lee

Organizations: Department of Statistics University of California, Davis Davis, CA 95616 · Microsoft Redmond, WA 98052

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 $\widetilde{O}(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.

Figures & tables

Figure 1: Mean cumulative regret over 50 paired seeds, with pointwise 95% bootstrap bands and endpoint whiskers. Top: monotone links; bottom: nonmonotone. Solid: proposed methods; dashed: external baselines.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$T,\ t,\ K$	Time horizon, round index, and candidates per round.
$\mathcal{X}_{t},\ X_{t,a},\ X_{t}$	Candidate menu, candidate $a$ , and chosen action at round $t$ .
$\Theta_{*},\ \widehat{\Theta}$	True parameter and structured fit targeting $\mu_{}\Theta_{}$ .
$f,\ L_{f}$	Reward link and its Lipschitz bound.
$y_{t},\ \eta_{t},\ \sigma^{2}$	Reward, noise, and conditional noise-variance bound.
$R_{T},\ r_{t}$	Cumulative regret and its round- $t$ summand.

Appendix

Table 2

Grid	Queries	Max $\|\Delta g\|$	Max $\|\Delta F\|$	95th $\|\Delta c\|$	Max $\|\Delta c\|$	Floors
4,096	Actual	$3.80\!\times\!10^{-4}$	$1.26\!\times\!10^{-4}$	$1.81\!\times\!10^{-3}$	$5.85\!\times\!10^{-3}$	0/5284
4,096	Tails	$1.66\!\times\!10^{-4}$	$1.17\!\times\!10^{-4}$	$1.16\!\times\!10^{0}$	$1.65\!\times\!10^{0}$	37/459
8,192	Actual	$1.03\!\times\!10^{-4}$	$2.88\!\times\!10^{-5}$	$4.11\!\times\!10^{-4}$	$1.72\!\times\!10^{-3}$	0/5284
8,192	Tails	$4.04\!\times\!10^{-5}$	$2.77\!\times\!10^{-5}$	$2.38\!\times\!10^{-1}$	$3.27\!\times\!10^{-1}$	37/459

Appendix

Table 2: Oracle discrepancies against a 16,384-point numerical reference over all 27 frozen directions. Actual: the first up to 256 chosen projections per selected epoch; tails: 17 points from

-8/\sqrt{11}

8/\sqrt{11}

. Entries are absolute;

g_{v}=F_{v}^{\prime}

and

c=(K-1)g_{v}/\max\{F_{v},10^{-12}\}

. Floor counts refer to the compared grid.

Panel	Policy	Parameter tuple
T-BSTOR: $(\varepsilon,c_{J},c_{\rm conf},c_{\nu},c_{\tau})$
Linear	T-BSTOR-Vec	$(0.1,\,0.5,\,\tfrac{1}{30},\,64,\,0)$
Linear	T-BSTOR-Mat	$(0.1,\,1,\,\tfrac{1}{30},\,16,\,0.001)$
Linear	T-BSTOR-Slice	$(0.1,\,1,\,\tfrac{1}{30},\,16,\,0.001)$
Tanh	T-BSTOR-Vec	$(0.1,\,0.5,\,\tfrac{1}{30},\,256,\,0)$
Tanh	T-BSTOR-Mat	$(0.1,\,1,\,\tfrac{1}{30},\,16,\,0.001)$

Appendix

Table 3: Frozen synthetic configurations. Every tuned field appears in its method’s tuple order.

c_{\nu}

is the influence multiplier;

c_{w}

and

c_{h}

are width and bandwidth multipliers,

\lambda_{\rm reg}

is the GSTOR penalty, and

c_{\rm trunc}

is the truncation multiplier. Nonzero

\lambda_{\rm reg}

denotes regularized GSTOR.

Panel	Versus T-BSTOR-Vec	Versus ZoomSIB-UCB	Versus GSTOR
Linear	$-134.2\,[-137.6,-130.5]$	$-17.9\,[-22.9,-13.4]$	$-109.5\,[-112.9,-106.0]$
Tanh	$-154.5\,[-158.5,-150.5]$	$-6.8\,[-11.9,-2.0]$	$-78.9\,[-84.6,-73.7]$
Convex	$-154.9\,[-159.9,-149.8]$	$-43.4\,[-50.2,-36.8]$	$-126.1\,[-130.9,-121.1]$
Valley	$-181.2\,[-185.0,-177.5]$	$-42.3\,[-47.5,-37.0]$	$-119.1\,[-123.4,-114.8]$
Peak	$-35.2\,[-37.1,-33.4]$	$-7.5\,[-10.0,-5.2]$	$-38.6\,[-40.4,-36.9]$
Wave	$-26.1\,[-27.0,-25.1]$	$-5.2\,[-6.6,-3.7]$	$-40.9\,[-41.8,-39.9]$

Appendix

Table 4: Paired final-regret differences: the predeclared structured reference minus each comparator. Negative values favor the reference. Brackets give unadjusted paired 95% percentile bootstrap intervals. The reference is T-BSTOR-Slice.

Panel	Policy	$n_{0}$	$m_{\rm init}$	$R_{\rm exp}$	$R_{\rm init}$	$R_{\rm later}$	$D_{\rm bin}$
Linear	T-BSTOR-Vec	4138.0	1102.0	67.2	20.6	261.6	145.5
Linear	T-BSTOR-Mat	2062.0	2072.3	33.5	40.4	112.4	53.6
Linear	T-BSTOR-Slice	2972.0	2069.6	48.2	40.0	126.9	56.5
Tanh	T-BSTOR-Vec	4018.0	1102.9	83.4	25.9	315.6	180.3
Tanh	T-BSTOR-Mat	2392.0	2070.5	49.7	50.2	120.0	61.3
Tanh	T-BSTOR-Slice	3134.0	2068.3	65.0	49.7	155.8	69.9

Appendix

Table 5: T-BSTOR diagnostics averaged over evaluation seeds.

n_{0}

is exploration length;

m_{\rm init}

counts scalar-bin initialization rounds. The three regret columns charge exploration, initialization, and later scalar rounds.

D_{\rm bin}

sums loss relative to the best candidate in the selected bin. Overflow is the percentage of binned candidate indices outside the frozen interval. Uniform-fallback rounds are excluded from the later-scalar column and retained separately in the accompanying summary.

Panel	Policy	$s$	$r_{\rm th}$	$r_{\rm pr}$	Bins	Zero	Fallback	$d$ (count)
Linear	T-BSTOR-Vec	0.04509	–	–	12.8	0/50	0/50	0.673 (50)
Linear	T-BSTOR-Mat	0.02027	2.8	2.8	23.7	0/50	0/50	0.444 (50)
Linear	T-BSTOR-Slice	0.02395	17.4	17.4	23.8	0/50	0/50	0.481 (50)
Tanh	T-BSTOR-Vec	0.05618	–	–	12.8	0/50	0/50	0.661 (50)
Tanh	T-BSTOR-Mat	0.03267	6.6	6.6	23.7	0/50	0/50	0.413 (50)
Tanh	T-BSTOR-Slice	0.03615	24.8	24.8	23.8	0/50	0/50	0.483 (50)

Appendix

Table 6: Frozen-fit and bin diagnostics for T-BSTOR policies.

s

is the fitted Frobenius norm before unit normalization.

r_{\rm th}

and

r_{\rm pr}

are the rank after thresholding and after entrywise projection: matrix rank or sum of slice ranks, omitted for vectors. Bins counts occupied scalar bins. Numeric summaries average observed runs; zero and fallback columns count final zero fits and uniform-fallback runs out of all evaluation seeds. Dashes denote unavailable or inapplicable quantities.

d

is sign-invariant direction error averaged over valid nonzero fits; parentheses give their count.

Method	Linear	Wave
T-ESTOR	57.139	—
ESTOR	90.608	—
G-LowTESTR (identity link)	59.173	42.648
T-BSTOR-Slice-DCT	102.385	46.390
T-BSTOR-Slice-DCT †	110.678	49.549
T-BSTOR-Slice-Identity	107.808	50.074

Appendix

Table 7: CCLE-calibrated cumulative pseudo-regret at

T=20{,}000

: means over ten shared trajectory seeds, with every round included (lower is better). T-ESTOR and ESTOR are monotone-only and inapplicable on Wave (—). G-LowTESTR assumes the identity link, correctly specified on Linear and misspecified on Wave. The seed panel was previously inspected; results are conditional on the fixed coefficient and settings.

Figure 2: CCLE-calibrated mean cumulative pseudo-regret over ten shared trajectory seeds on Linear and Wave. Shading gives pointwise 95% paired-seed percentile intervals, not simultaneous bands. T-ESTOR and ESTOR are monotone-only; G-LowTESTR assumes identity on both links. Curves connect recorded cumulative-regret values. Results are conditional on the fixed coefficient and settings; intervals do not adjust for the previously inspected seed panel or adaptive configuration selection.

Multi-Armed Bandits

Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.

See all 348 papers

Optimal Regret for Single Index Bandits
May 10, 2026Devdan Dey, Sujoy Bhore, Avishek GhoshMulti-Armed Bandits Single-Index Models
Department of Computer Science and Engineering, Indian Institute of Technology Bombay.
Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits
Aug 5, 2026Bo Xue, Ji Cheng, Haodong Jing +2Multi-Armed Bandits Combinatorial Multi-Armed Bandits
City University of Hong Kong. · Xi’an Jiaotong University. · Northwestern Polytechnical University.
Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity
May 18, 2026Hamed Khosravi, Xiaoming HuoMulti-Armed Bandits Non-Stationary Bandits
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta, GA 30332

May 10, 2026J/K move · Enter open · S save

Optimal Regret for Single Index Bandits

Devdan Dey, Sujoy Bhore, Avishek Ghosh

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

Multi-Armed Bandits Single-Index Models Minimax Regret Regret Minimization Contextual Bandits

Open paper AskPDF arXiv

We study the

\textit{single-index bandit}

problem, where rewards depend on an unknown one-dimensional projection of high-dimensional contexts through an unknown reward function. This model extends linear and generalized linear bandits to a nonparametric setting, and is particularly relevant when the reward function is not known in advance. While optimal regret guarantees are known for monotone reward functions, the general non-monotone case remains poorly understood, with the best known bound being

\tilde{\mathcal{O}}(T^{3/4})

(under standard boundedness and Lipschitz assumptions on the reward function [Kang et al., 2025]). We close this gap by establishing the optimal regret for general single-index bandits. We propose a simple two-phase algorithm, namely, Zoomed Single Index Bandit with Upper Confidence Bound (

\texttt{ZoomSIB-UCB}

), that first estimates the projection direction via a normalized Stein estimator, and then reduces the problem to a one-dimensional bandit using discretization and finally use UCB. This approach achieves a regret of

\tilde{\mathcal{O}}(T^{2/3})

, and improves significantly upon prior work without any additional assumptions. We also prove a matching minimax lower bound of

\tildeΩ(T^{2/3})

, showing that the upper bound is essentially tight. Our upper and lower bounds together provide a sharp characterization of the regret in single-index bandits. Moreover, the empirical results further demonstrate the effectiveness and robustness of our approach.

Abstract

Multi-Armed Bandits

Explore similar work

Optimal Regret for Single Index Bandits

Efficient Online Lexicographic Generalized Low-Rank Matrix Bandits

Catching a Moving Subspace: Low-Rank Bandits Beyond Stationarity