Kernel Single-Index Bandits: Estimation, Inference, and Learning

Sakshi Arya; Satarupa Bhattacharjee; Bharath K. Sriperumbudur

stat.MLMar 19, 2026

Kernel Single-Index Bandits: Estimation, Inference, and Learning

Authors: Sakshi Arya, Satarupa Bhattacharjee, Bharath K. Sriperumbudur

Organizations: Department of Mathematics, Applied Mathematics, and Statistics, Case Western Reserve University · Department of Statistics, University of Florida · Department of Statistics, The Pennsylvania State University

Abstract

We study contextual bandits with finitely many actions in which the reward of each arm follows a single-index model with an arm-specific index parameter and an unknown nonparametric link function. We consider a regime in which arms correspond to stable decision options and covariates evolve adaptively under the bandit policy. This setting creates significant statistical challenges: the sampling distribution depends on the allocation rule, observations are dependent over time, and inverse-propensity weighting induces variance inflation. We propose a kernelized $\varepsilon$ -greedy algorithm that combines Stein-based estimation of the index parameters with inverse-propensity-weighted kernel ridge regression for the reward functions. This approach enables flexible semiparametric learning while retaining interpretability. Our analysis develops new tools for inference with adaptively collected data. We establish asymptotic normality for the single-index estimator under adaptive sampling, yielding valid confidence regions, and derive a directional functional central limit theorem for the RKHS estimator, which provides asymptotically valid pointwise confidence intervals. The analysis relies on concentration bounds for inverse-weighted Gram matrices together with martingale central limit theorems. We further obtain finite-time regret guarantees, including $\tilde{O}(\sqrt{T})$ rates under common-link Lipschitz conditions, showing that semiparametric structure can be exploited without sacrificing statistical efficiency. These results provide a unified framework for simultaneous learning and inference in single-index contextual bandits.

Figures & tables

\hat{a}_{t}=\begin{cases}A_{t}\ \text{with probability}1-\epsilon_{t},\\ \mathcal{A}\setminus A_{t}\ \text{with probability}\frac{\epsilon_{t}}{L-1}\end{cases}

Algorithm 1 K-SIEGE (Kernelized Single-Index Epsilon-Greedy Exploration) Strategy

\hat{\beta}_{i,t}=A_{i,t}^{-1}b_{i,t},\quad\text{where}\quad A_{i,t}=\frac{1}{t}\sum_{s=1}^{t}w_{s,i}W_{s}W_{s}^{\top}+\lambda_{t}I,\quad b_{i,t}=\frac{1}{t}\sum_{s=1}^{t}w_{s,i}W_{s}Y_{s}.

Algorithm 2 Parametric Directional Inference for Single-Index Bandits

Panel of Figure 1 — Figure 1: Empirical joint $95\%$ coverage for the single-index direction for both arms.

Figure 2: Nonparametric pointwise inference for

(d,\sigma)=(2,0.05)

. Left: empirical

95\%

coverage of K-SIEGE and A&S intervals at the selected inference times. Right: corresponding average interval lengths for each arm.

Panel of Figure 3 — Figure 3: Directional inference summary on the Rice Classification dataset.

Panel of Figure 4 — Figure 4: Nonparametric inference summary on the Rice Classification dataset. (a) Estimated success curves with pointwise $95\%$ confidence intervals at $t=900$ for a representative run. (b) Distribution of pointwise CI widths across replications, by arm and time.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Description
$T$ , $\mathcal{T}=\{1,\dots,T\}$	Time horizon and index set of rounds
$L$ , $\mathcal{A}=\{1,\dots,L\}$	Number of arms and action set
$d$	Covariate dimension
$X_{t}\in\mathcal{X}\subset\mathbb{R}^{d}$	Context observed at time $t$ ; $X_{t}\sim P_{X}$ i.i.d.
$a_{t}\in\mathcal{A}$	Arm pulled at time $t$ (random under the policy)
$p_{t,i}$	Propensity: $\mathbb{P}(a_{t}=i\mid\mathcal{F}_{t-1},X_{t})$

Appendix

Table 1: Notation for the problem setup.

Symbol	Description
$p$	Differentiable density of $X_{t}\sim P_{X}$ on $\mathbb{R}^{d}$
$\mathcal{S}(x)$	Score (w.r.t. covariates): $\mathcal{S}(x)=-\nabla_{x}\log p(x)$
$W_{s}$	Score feature: $W_{s}:=\mathcal{S}(X_{s})\in\mathbb{R}^{d}$
$\beta_{i}$	Arm- $i$ index parameter in the KSIB model
$b_{i}$	Unit direction: $b_{i}:=\beta_{i}/\\|\beta_{i}\\|_{2}$
$f_{i}$	Unknown link; $f_{i}^{\prime}:=\frac{d}{dz}f_{i}(z)$

Appendix

Table 2: Notation for parametric (index-direction) estimation and inference in Section 4 .

Symbol	Description
$U_{s,i}$	Projected covariate: $U_{s,i}:=X_{s}^{\top}\beta_{i}\in\mathcal{U}$
$p_{s,i}(u)$	Propensity: $\mathbb{P}(\hat{a}_{s}=i\mid\mathcal{F}_{s-1},\,U_{s,i}=u)\in(0,1]$
$\tilde{r}_{t}$	Average exploration: $\tilde{r}_{t}:=t^{-2}\sum_{s=1}^{t}\text{E}[\,1/p_{s,i}(U_{s,i})\,]$
$K$	Reproducing kernel on $\mathcal{U}\times\mathcal{U}$ (bounded)
$\mathcal{H}_{K}$	RKHS induced by $K$ on $\mathcal{U}$
$\langle\cdot,\cdot\rangle_{K},\ \\|\cdot\\|_{K}$	Inner product and norm in $\mathcal{H}_{K}$

Appendix

Table 3: Notation for RKHS estimation and inference of the link function in Section 5 .

Figure 5: Link functions

g_{1}

and

g_{2}

as functions of the single-index

z

Figure 6: Nonparametric pointwise

95\%

confidence intervals for a single Monte Carlo replication in the

(d,\sigma)=(2,0.20)

scenario. The dashed curve shows the true mean reward, points show fitted values, and vertical bars give the K-SIEGE and A&S intervals.

Figure 7: Time-averaged regret

\bar{R}_{t}=R_{t}/t

across simulation scenarios. Curves show the mean over replications with pointwise

95\%

confidence bands.

Variable	Center	CI ${}_{\text{lo}}$	CI ${}_{\text{hi}}$
Perimeter	0.47405	0.47016	0.47794
MajorAxisLength	0.46718	0.45704	0.47731
ConvexArea	0.44804	0.43794	0.45813
Area	0.44534	0.43628	0.45440
Eccentricity	0.28564	0.23618	0.33510
MinorAxisLength	0.26861	0.23365	0.30356

Appendix

Table 4: Directional parametric inference (95% confidence intervals) at

t=900

for a representative run (Arm 1). Variables are ordered by

\lvert\widehat{\theta}_{i,t}\rvert

Figure 8: Distribution of coordinate-wise directional CI widths across 40 replications at

t=900

, shown separately by arm.

Panel of Figure 9 — Figure 9: Sequential performance of K-SIEGE on the Rice Classification dataset. (a) Time-averaged regret $\bar{R}_{t}$ (mean $\pm$ 95% CI). (b) Excess error relative to the cross-fitted logistic oracle (mean $\pm$ 95% CI).

Variable	$t=300$	$t=600$	$t=900$
Perimeter	0.4728 (0.4631, 0.4826)	0.4768 (0.4714, 0.4823)	0.4741 (0.4702, 0.4779)
MajorAxisLength	0.4733 (0.4627, 0.4839)	0.4668 (0.4545, 0.4790)	0.4672 (0.4570, 0.4773)
ConvexArea	0.4469 (0.4364, 0.4575)	0.4511 (0.4394, 0.4628)	0.4480 (0.4379, 0.4581)
Area	0.4456 (0.4342, 0.4571)	0.4471 (0.4368, 0.4575)	0.4453 (0.4363, 0.4544)
Eccentricity	0.2941 (0.2500, 0.3382)	0.2716 (0.2135, 0.3296)	0.2856 (0.2362, 0.3351)
MinorAxisLength	0.2568 (0.2211, 0.2926)	0.2739 (0.2336, 0.3141)	0.2686 (0.2337, 0.3036)

Appendix

Table 5: Directional parametric inference (representative run 01, arm 1): entries are center and

95\%

directional CI in parentheses.

Variable	$t=300$	$t=600$	$t=900$
Perimeter	-0.4696 (-0.4746, -0.4645)	-0.4688 (-0.4729, -0.4646)	-0.4663 (-0.4695, -0.4630)
MajorAxisLength	-0.4784 (-0.4894, -0.4675)	-0.4727 (-0.4844, -0.4611)	-0.4646 (-0.4737, -0.4554)
ConvexArea	-0.4463 (-0.4564, -0.4361)	-0.4512 (-0.4602, -0.4422)	-0.4573 (-0.4635, -0.4510)
Area	-0.4443 (-0.4531, -0.4355)	-0.4503 (-0.4587, -0.4419)	-0.4565 (-0.4625, -0.4505)
Eccentricity	-0.3033 (-0.3315, -0.2751)	-0.2941 (-0.3220, -0.2662)	-0.2723 (-0.2937, -0.2508)
MinorAxisLength	-0.2324 (-0.2627, -0.2020)	-0.2488 (-0.2778, -0.2198)	-0.2706 (-0.2924, -0.2487)

Appendix

Table 6: Directional parametric inference (representative run 01, arm 2): entries are center and

95\%

directional CI in parentheses.

Variable	$t=300$	$t=600$	$t=900$
V8 (O2)	0.1707 (-0.0261, 0.3674)	0.3688 (0.1869, 0.5506)	0.3819 (0.2747, 0.4892)
V9 (P8)	0.4968 (0.2792, 0.7145)	0.4337 (0.2490, 0.6184)	0.3681 (0.2609, 0.4753)
V10 (T8)	0.4665 (0.2836, 0.6495)	0.4132 (0.2129, 0.6135)	0.3493 (0.2312, 0.4673)
V7 (O1)	-0.0647 (-0.4643, 0.3348)	0.2504 (-0.1544, 0.6553)	0.3461 (0.1259, 0.5663)
V13 (F8)	0.2368 (-0.0320, 0.5055)	0.3605 (0.0850, 0.6360)	0.3376 (0.1813, 0.4940)
V12 (F4)	0.2983 (0.1458, 0.4509)	0.2996 (0.1234, 0.4758)	0.3150 (0.2184, 0.4116)

Appendix

Table 7: Directional parametric inference (representative run 01, arm 2): entries are center and

95\%

directional CI in parentheses.

Panel of Figure 10 — Figure 10: Directional inference summary on the EEG dataset.

Panel of Figure 11 — Figure 11: Nonparametric inference summary on the EEG dataset. (a) NP success curves with pointwise $95\%$ CIs at $t=900$ (representative run). (b) Distribution of NP pointwise CI widths across replications, by arm and time.

Contextual Bandits

Contextual bandits learn which action to take from features of each situation when only the chosen action’s reward is observed.

See all 152 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.
Statistical Inference for Misspecified Contextual Bandits
Jun 21, 2026Yongyi Guo, Ziping XuInverse Probability Weighting Adaptive Inference
Department of Statistics, University of Wisconsin–Madison · School of Data Science and Society, University of North Carolina at Chapel Hill
Elicitation and Decision Geometry in Single-Index Bandits
Sep 28, 2026Sakshi Arya, Cheng Soon OngMulti-Armed Bandits Single-Index Models
Case Western Reserve University, USA · CSIRO, Australia

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

Contextual Bandits

Explore similar work

Optimal Regret for Single Index Bandits

Statistical Inference for Misspecified Contextual Bandits

Elicitation and Decision Geometry in Single-Index Bandits