Single Index Bandits: Generalized Linear Contextual Bandits with Unknown Reward Functions
Authors: Yue Kang
Mingshuo Liu
Bongsoo Yi
Jing Lyu
Zhi Zhang
Doudou Zhou
Yao Li
Venue: ICLR 2026 Poster (2026)
Keywords: contextual bandit
online learning
Primary area: learning theory
TL;DR: We study a new problem of generalized linear bandits where reward functions are unknown to the users, also known as single index bandits.

Abstract: Generalized linear bandits have been extensively studied due to their broad applicability in real-world online decision-making problems. However, these methods typically assume that the expected reward function is known to the users, an assumption that is often unrealistic in practice. Misspecification of this link function can lead to the failure of all existing algorithms. In this work, we address this critical limitation by introducing a new problem of generalized linear bandits with unknown reward functions, also known as single index bandits. We first consider the case where the unknown reward function is monotonically increasing, and propose two novel and efficient algorithms, STOR and ESTOR, that achieve decent regrets under standard assumptions. Notably, our ESTOR can obtain the nearly optimal regret bound $\tilde{O}_T(\sqrt{T})$ in terms of the time horizon $T$. We then extend our methods to the high-dimensional sparse setting and show that the same regret rate can be attained with the sparsity index. Next, we introduce GSTOR, an algorithm that is agnostic to general reward functions, and establish regret bounds under a Gaussian design assumption. Finally, we validate the efficiency and effectiveness of our algorithms through experiments on both synthetic and real-world datasets.

Published as a conference paper at ICLR 2026
SINGLE INDEX BANDITS: GENERALIZED LINEAR CON- TEXTUAL BANDITS WITH UNKNOWN REWARD FUNC-
TIONS
Yue Kang"",
Mingshuo Liu', Bongsoo Yiš, Jing Lyu",
Zhi Zhang",
Doudou Zhoull, Yao Lis
i Microsoft University of California, Davis University of North Carolina at Chapel Hill University of California, Los Angeles yuekangemicrosoff.. ccom
National University of Singapore
(mshliu, yu B @ucdavis edu (bongsoo, yaongsoo,yaoli ( @unc. edu z2h2378g.ucla adzhou@nus.edu.c
ABSTRACT
Generalized linear bandits have been extensively studied due their broad appli- cability in real-world online decision-making problems. However, these methods typically assume that the expected reward function is known to the users, an as- sumption that is often unrealistic in practice. Misspecification of this link function can lead the failure of all existing algorithms. In this work, we address this critical limitation by introducing a new problem of generalized linear bandits with unknown reward functions, also known as single index bandits. We first consider the case where the unknown reward function is monotonically increasing, and propose two novel and efficient algorithms, STOR and ESTOR, that achieve decent regrets under standard assumptions. Notably, our ESTOR optimal regret bound Ör(vT) terms of the time horizon T. We then extend our methods to the nigh-dimensional sparse setting and show that the same regret rate be attained with the sparsity index. Next, introduce GSTOR, an algorithm that is agnostic to general reward functions, and establish regret bounds under a Gaussian design assumption. Finally, we validate the efficiency and effectiveness of our algorithms through experiments on both synthetic and real-world datasets.
obtain the nearly
INTRODUCTION
The multi-armed bandit models sequential decision-making with partial feedback and has found broad applicability in areas such as online recommendation (Li et al. 2010). clinical trials (Villar et al.
2015). precision medicine (Lu et al. 2021), and hyperparameter learning (Ding et al.] 2022 Kang ct 2024bb. To incorporate the side information (contexts) of arms, one widely adopted extension is the linear contextual bandit model (Abbasi- Yadkori al.. 2011 2012), which assumes the expected reward is a linear function of the observed feature with some unknown parameter. However, many real-world applications involve inherently non-linear reward structures, such as binary clicks or discrete counts, rendering linear models inadequate. Generalized linear bandits (GLBs) (Filippi al. 2010 Li al. 2017) were then naturally introduced to address this limitation by applying a non-lineas (inverse) link function to the linear predictor, enabling compatibility with a broader range of reward types. While GLBs maintain much of the traceability and theoretical guarantees of linear models, they fundamentally rely on the assumption that the link function is known in advance. In practice, however, this assumption is often unrealistic, as the underlying parametric form typically unknown and impossible to identify. It has been shown that model misspecification severely
Yue Kang is the corresponding author.
!Ô hides polylogarithmic factors. A subscript T on asymptotic notations (e.g., Or) indicates that the bound expressed only in T, with dependence other problem parameters suppressed.

---

Published as a conference paper at ICLR 2026
2021), , and even minor deviations can lead to linear regret for all existing GLB methods (Lattimore & Szepesvári 2020).
degrade the practical performance (Ghosh et al. 2017 Bogunovic & Krause
This fundamental limitation motivates the development of more robust, agnostic approach.
To address this critical limitation, we introduce the single index bandit (SIB) problem, where the expected reward is an unknown function of the linear predictor. To the best of our knowledge, this is the first work to advance GLBs without assuming access to the reward function. Our setting is inspired by single index models (SIMs) from statistical learning (Härdle 2004), which extend generalized linear models (GLMs) by removing the need for known link function. Despite their flexibility and effectiveness in offline settings, SIMs have never been explored in the bandit literature, primarily due to the substantial theoretical challenges they pose in online learning. We propose a family of SIB algorithms that achieve strong theoretical guarantees and demonstrate great empirical performance in this work, all without knowing the form of the reward function. Notably, although GLBS have been extensively studied in recent years, none of the existing results can be applied or
extended to our setting: Both Upper Confidence Bound (UCB)-based methods (Filippi et al. [2010] Li
ct al. 2017) and Thompson Sampling (TS)-based approaches (Agrawal & Goyal| 2013: Kveton et al.
2020) require solving (quasi-)maximum mmaximum likelihood estimator for the unknown parameter, which
essentially relies on explicit knowledge of the reward function. Another class of GLB algorithms
improves computational efficiency via second-order online optimization (Jun et al.) 2017 Xue et al., 2024), while these methods also presume a known link function for online Newton updates at each round. More fundamentally, all existing GLB analyses depend on concentration bounds for some vector-valued martingales involving the noise terms across the time horizon T', whose construction inherently requires the explicit form of the reward function, and these analytical techniques collapse in the agnostic setting. On the other hand, another line of research considers the general contextual bandit problem under the realizability assumption, i.e., the expected reward belongs to some known function class F (Foster et al. 2018:) Foster & Rakhlin, 2020 Simchi-Levi & Xu, (022), and these approaches critically assume access to a powerful square-loss regression oracle with strong non- asymptotic guarantees. However, such oracle is impossible to realize in single index models: most existing SIM estimators are based on maximum likelihood methods and provide only asymptotic guarantees (Han 1987, Carroll et al. 1997| Härdle 2004), while the few results with finite-sample rates require highly restrictive distributional assumptions (e.g., i.i.d. Gaussian covariates) (Neykov) et al. 2016 Plan & Vershynin 2016). These conditions fundamentally incompatible with all contextual bandit algorithms under the realizability assumption, where the full reward function and its parameter must be learned jointly from adaptively collected data rather than from fixed and restrictive sampling strategy. A detailed explanation of this intrinsic incompatibility is provided in Appendix B In conclusion, the single index bandit setting we introduce lies beyond the reach of all existing approaches, and tackling this challenging problem necessitates the development of entirely new algorithmic techniques and theoretical tools.
To overcome the aforementioned challenges, we introduce novel estimator based on Stein's 's method, which offers a fundamentally different approach to estimating the unknown parameter. While Stein's s method has recently been applied in low-rank matrix bandits (Kang et al. 2022), it remains unexplored in the context of linear or generalized linear bandits. We first leverage this tool to study the case where the unknown reward function is continuously differentiable and monotonically increasing, and propose two efficient algorithms that achieve strong performance under mild conditions. Notably, GLMs with the canonical form also induce monotonically increasing reward functions (McCullagh 2019), which indicates that this setting strictly encompasses the classic GLBB framework. Furthermore, we extend our framework to the sparse nigh-dimensional regime and generalize our approach to handle arbitrary (non-monotonic) reward functions. The contributions are summarized as follows:
We propose novel and efficient estimator based on Stein's method that requires only the existence of the second moment of the noise and attains the minimax error rate. Moreover, our estimator is highly efficient: it requires no optimization, and can be computed in O(nd) time and (d) space from n contextual samples in Rd. We further show that this estimator extends naturally to the sparse high-dimensional regime with the same error bound in terms of the sparsity index. These results also constitute notable advancement in the estimation of SIMs as well.
As warm-up, we introduce STOR, an Cieiorre-ten--Comee (EtC) style algorithm, and show that it achieves regret bound of order (T55) Building on this, we propose a new algorithm named
2

---

Published as a conference paper at ICLR 2026
ESTOR that leverages novel epoch- basch-baseddde schedule, and prove that it achieves nearly- regret bound of order (T(+)) under our significantly more challenging problem setting.
Next, we extend our results the high-dimensional setting and show that the same regret bounds hold when the ambient dimension is replaced by the sparsity level of the true parameter, making our approach well-suited for modern applications with sparse high-dimensional feature spaces.
Furthermore, we propose GSTOR, a new method that extends STOR to the general case where the reward functions are not necessarily monotonic. We introduce methodology that combines our Stein's 's method-based estimator with a kernel regression procedure approximate the unknown link function. Under a standard Gaussian design assumption, our GSTOR achieves the regret of order (T
nuuble-epporraiio--tee----
Finally, we validate our theoretical results through extensive experiments on both synthetic and real-world datasets, illustrating the effectiveness of our methods across diverse reward structures.
Due to space constraints, we defer the full related work with discussion to Appendix B There, provide comprehensive overview of prior research on generalized linear bandits, single index models, and contextual bandits under the realizability assumption. We further explain why all existing approaches are fundamentally unable address the single index bandit setting in detail, and illustrate that the SIM/SIB is significantly more challenging than the GLM/GLB.
PRELIMINARIES
We present the setting of single index bandit (SIB) problem and introduce the assumptions used in our analysis. Denote T the time horizon and X; the set available to the agent each round t E [T], where X, = {zz,a E Rd a E [K]} consists of (K 2 3) feature vectors sampled i..d. from some d d-dimensional continuous distribution D with the multivariate density p()). At time I, the agent chooses an arm x, E X, and observes the associated stochastic reward Ve such that y/ f(x,, 0.) + Mi: where 0, Rd is unknown parameter vector and 7) is the zero-mean noise with finite variance o². Note that our analysis only requires bounded variance assumption, which is strictly weaker than the sub-Gaussian noise condition imposed in most GLB literature (Lattimore& & Szepesvári] 2020). Additionally, unlike the GLB setting where the reward function f(-) known to the agent, we consider a more challenging problem in which f(-) is an unknown, continuously differentiable function. This agnostic relaxation significantly increases the difficulty of the problem and invalidates the theoretical guarantees all existing GLB methods, as discussed in Section I and Appendix B Furthermore, we let ||0.1| = I for model identifiability.
Define Ft,+ == arg max x 0a as the feature vector of the optimal arm at round t, and the goal is to minimize the cumulative regret Ry across the time horizon T' defined as,
Rr Σ [(TT.,0) -0x 0.).
Next, we present the following key definition of the score function used in Stein's 's method.
Definition 2.1. Letp: Rd + RR be a probability density function defined on Rd, The score function SP :P:Rd Rdd Rd associated with the density (pdf) p(-) is given by:
(z V. log(p(x)) - -Vp(()//(() &E TER. Rd,
and (x)) i E [d] is defined as the ith entry of the score function vector 5²(x) E Rd.
We will omit the subscript in V and the superscript in S when the underlying distribution is clear from context. With this definition, we then introduce two standard assumptions.
Assumption 2.2. There exists some constant M > 0 such that E(S)(X)²) < M for all j E [d] where X is random variable sampled from the distribution D.
Assumption 2.3. There exists some value L >> 0 such that || L for all i E [d], E [T]. And the unknown reward function f(-) and its derivative f'(-) have constant upper bounds L,. Ly > 0.
L.e. [(xx) [0)=)) S Lp,, for any |or| < T..
3

---

Published as a conference paper at ICLR 2026
Algorithm Stein's Oracle Single Index Bandit (STOR)
Input: T. the probability rate 6, parameters Ti, 7,
1: for t= 1 to Ti do
2: Pull arm 2, Xr uniformly randomly and observe the stochastic reward ye-
3: end for
4: Obtain the estimator 9 with {z,, 8: 3: based on Equ. |I
5: for t= = + to do
6: Choose the arm Te = arg max x TÜ break ties arbitrary.
7: end for
Assumption 2.2 is mild and applies to broad class of distributions, including many non-sub-Gausee or even non-zero-mean cases, which enables us to handle previously intractable cases. Furthermore, it is less restrictive than the conditions in the state-of-the-ar literature Stein's 's method and robust estimation literature (Fan et al. 2019; 2023). which typically require at least a finite fourth moment of the score function. Assumption 2.3 also standard and widely used in existing linear contextual bandit algorithms. While some existing methods assume both the arm vector x and the parameter 6, have an l2 noom bound of S (Abbasi- Yadkori al.) 2011 2012 CCuu al., 2011 Ding et al.) [021 Li et al.] 2017), which may appear different from our Assumption 2.3] both formulations ensure that the inner product 0, bounded by L,, maintaining the same fundamental constraint. Moreover, our main results remain valid under both settings, and we adopt our assumption because it is commonly used sparse linear bandit literature (Hao et al. 2020: Jang et al. 2022), allowing us to maintain consistency in our discussion of both linear and sparse linear bandits. A more detailed discussion on this matter is provided in Appendix ! Additionally, we allow to remain at a constant scale up to logarithmic factors, i.c. L (1). while ensuring our results remain valid. This flcxibility accommodates broad range of distribution D, including any sub-Gaussian sub-Exponential distribution, and more technical details are provided Appendix []
3 METHODS
In this section, we introduce our SIB algorithms, beginning with the case of monotonically increasing reward functions. We then extend approach the high-dimensional regime and ultimately generalize to non-monotonic settings. We first utilize a novel Stein's s--ettodd estimator for the unknown parameter O* under general continuously differentiable reward functions, and show that achieves the optimal етrоr rate under mild assumptions. We further extend this estimator to the sparse high-ddmensional setting by incorporating l regularizer, and demonstrate that the optimal error rate is well preserved in terms of the sparsity level of the true parameter.
3.1 SINGLE INDEX MODEL ESTIMATOR
Suppose we collect n pairs of samples {x,, y where the feature vector x, is i..dd sampled from the d-dimensional distribution D. We propose the following minimization problem in Eqn. (I.
i = arg min I(0) + A|[0|,, where L(0) = |101|
O (ve S(x,)) To 0,
(1)
where we denote (-).) Rd + Rd as the elementwise truncation function such that
Φ, (v) [s;)n(v;) (105) د) Ve =- [w, E Rd
for some parameter > ||0|| is the regularizer designed for sparse high-dimensional set- ting (Plan & Vershynin 201 Notably, instead of directly using the term yı S(x;), we employ careful truncation to control the variance the estimator while managing bias. The truncation is governed by parameter which explicitly balances bias induced by discarding extreme values against variance reduction to achieve optimal statistical guarantee. While this thresholding technique has been widely adopted in statistical and online learning to handle heavy-tailed rewards (Fan et al.) 2021] Bubeck et al., 2013) Kang et al. 2024a), we demonstrate its novel applicability to mitigate the ambiguity from misspecification of the reward function f(-) in this work. Next, we establish the
4

---

Published as a conference paper at ICLR 2026
following statistical guarantees for the estimator in Eqn. (.. Notably, our l and Eg error bounds mathh the minimax rates of classical linear regression Wamnwightt (2019) up to logarithmic terms, and since linear regression is a special case of our setting, these bounds are nearly optimal.
Theorem 3.1. (Bound of SIM) For any single index model defined in Section [2 with samples
F Ln drawn from some distribution D. We denote p.. == Eff 0x))), X ~ "D and assume
Me * O. Under Assumption 2.2 2.3 by solving the optimization problem in Eqn. ( with T
V /3 + 11) log (2g(2)/)) 8) and X = 0, with probability at least (1 - 6) it holds that:
|0 - 1-mmell1
2/3
dM + 117 log(2//0/ =0 + V2
=6(1
d
n
2v3 + V2 d.
M(o² + log(d//0) Ō d
- 10-moall 5
n
Vn
We begin by applying Stein's 's identity to show that S(;)] = O.,.,, which motivates our estimator. To analyze its accuracy, we upper bound the optimization gap L(0 L(p.0.) by bounding the gradient norm V [L Il We control the heavy-tailed nature of y: via a truncation function (y))), which limits the influence of extreme values while introducing a controllable bias. We show that the bias term from truncation is small (via Taylor expansion) and the variance is concentrated using Bernstein's 's incquality. Finally, by applying first-order convexity arguments, we obtain high-probability bounds on both ||θ 0x l|2 and ||0 0.112 that match the minimax rate, all without requiring knowledge of the reward function (--).
Proof sketch of Theorem 3.1;
The full proof of Theorem 3.1 is deferred to Appendix D Notably, our estimator is highly computa- tionally efficient. In the low- -iw-dimenioonll regime, the loss in Eqn. ( reduces to a simple quadratic form L(0) with À 0, and the solution admits closed-form expression as Ei (x.)((z))) This solution requires no iterative optimization and is obtained by single averaging operation over the samples, resulting in only ((nd) time and (cd) space complexity. This is remarkably more efficient than solving the MLE used by most GLB algorithms, despite our setting being significantly harder due to the unknown reward function.
While our method assumes that data is sampled from a fixed distribution D, rather than being adversarially chosen, which may appear strong at first glance, we emphasize that this is reasonable condition in the study of SIMs and is still milder than the stronger assumptions commonly imposed in prior work (see Appendix B Note that the SIM/SIB setting is fundamentally more difficult than GLM/GLB, as it involves jointly learning both the parameter and the unknown link function. To make the problem tractable, previous studies on SIMs typically impose additional distributional assumptions, such assuming the context vector is drawn from standard Gaussian and the link function satisfies certain regularity conditions (Neykov et al.; 2016) Thrampoulidis et al., 2015) Plan & Vershynin 2016). In contrast, our approach avoids these assumptions and aligns with prior bandit work that also employs Stein's method (Kang et al. 2022; Wang et al. 2025). Conclusively, we view the assumption on Stein's score as reasonable and necessary compromise for addressing a significantly more realistic and challenging setting than GLBs. A detailed review of existing SIM works is given in Appendix B And we leave studying SIBs with adversarially chosen arms as a challenging future direction.
3.2 WARM-UP: SIMPLE ALGORITHM AGNOSTIC TO INCREASING REWARD FUNCTIONS
We first consider the case where the unknown reward function is continuously differentiable and monotonically increasing, Notably, the reward function of any GLM in the canonical form is also monotonically increasing, implying that our setting still encompasses the existing GLB literature.
As warm-up, we present our efficient STein's ORacle single index bandit (STOR) algorithm, which leverages the Explore-thee theree-the-CCee then-CCmmit (EtC) methodology. EIC has been widely adopted in contextual bandit literature, particularly in the high-dimensional regime (Li et al. 2022 Dang et al.) 2022 Hao ctt al. 2020) due to its simplicity. Our STOR method is shown in Algorithm [ Specifically, STOR begins with exploration phase of length Ti, where randomly selects actions for a fixed number
5

---

Published as a conference paper at ICLR 2026
Algorithm 2 Epoched Stein's Oracle Single Index Bandit (ESTOR)
Input: T, epoch schedule e; = (2' 1)To. the probability rate 6, parameters To, {A,, To T= Initialization: Set the density function p1 corresponding to the distribution D.
for 1 to e1 do
2: Pull an arm 24 Xr uniformly randomly and observe the stochastic reward yt.
3: end for
4: for epoch i 2,3, do
5: Obtain the estimator O, with {rr UJ ) ==e-_2+1 based Eqn. ① where we set d Ais
T= T, and S()) as the score function associated with the density Pi-1-
6:
for ( 6:-1 to min(e;, T) do
7: Choose the arm 22 arg max, 0i break ties arbitrary.
8: end for
9: Update the density function pt(x) K p(x) F1 (loTTO, 0.)K-1, where FF(-) is the cumulative distribution function the random variable XTO, 0, with ~ D.
10: end for
of rounds estimate the direction of the unknown parameter 0.. It then enters the exploitation phase and greedily selects actions that are expected to maximize the estimated reward.
Theorem 3.2. For any single index bandit with an increasing function, we set T
(dT))
In (2d/ 8)
v / In(2d/5) and À 0 in Algorithm following regret bound with probability at least
Then under Assumption
2.2 2.3
we have the
8:
RT = 0 (d T (In (
Although our Algorithm provides the first solution to SIBs with monotonically increasing functions, its regret bound does not match the optimal rate of order ÖT( (vT) for GLBs (Lattimore Szepesvári 2020). This is due to the intrinsic suboptimality of the EtC approach, which incurs additional regret from a fixed
split. Remarkably, we resolve this challenge in the next subsection by proposing improved and novel algorithm, ESTOR, which achieves the minimax- optimal regret bound of order Ör (T) up logarithmic factors.
3.3 IMPROVED ALGORITHM AGNOSTIC TO INCREASING REWARD FUNCTIONS
Our Epoched STein's ' ORacle single index bandit (ESTOR) algorithm is presented in Algorithm 2 employs a carefully designed epoch schedule with epoch-specific hyperparameter configuration. Specifically, ESTOR uses exponentially increasing epoch lengths, and at the beginning of each epoch, leverages data collected from the preceding epoch compute an updated estimate of the unknown parameter (line 5). Actions are selected greedily according to this most recent estimate within each epoch (line 7). At the end of each epoch i, ESTOR updates the distribution p; for arm selection based on the updated estimator Q: (line 9), which serves as the basis for our novel parameter estimator the subsequent epoch. Although epoch scheduling and greedy selection have been studied individually, their integration with a solid theoretical guarantee remains largely unexplored the literature.
Furthermore, while traditional epoch-based techniques like the doubling trick (Auer et al. 1995) focus on adapting to unknown time horizons, our motivation differs fundamentally: we carefully select epoch lengths and utilize epoch-specific hyperparameters that gradually evolve, effectively balancing exploration and exploitation over time. Shorter initial epochs facilitate rapid exploration and coarse estimation, while progressively longer epochs ensure later stages accumulate sufficiently many samples, allowing our parameter estimates to become increasingly precise with diminishing error. By coordinating these components, ESTOR is able to overcome the inherent suboptimality of standard EIC approaches. We now introduce the following mild assumption for our ESTOR to support our regret analysis:
Assumption 3.3. There exists some constant C > 0 such that Epp, (X xT)))) < C for all E TRd with ||||| x where X sampled from the distribution D and (. is the density of X Vo. Remark 3.4. Assumption 3.3 quite mild and applies to broad class of distributions. For example, if the density function p.(.) (+) is bounded, then its second moment is automatically finite and hence

---

Published as a conference paper at ICLR 2026
Assumption 33 holds. This scenario encompasses many standard cases, including X sampled from any multivariate normal distribution. Furthermore, if the entries of X follow the common sub-Gaussian property, then X 'Tv is also sub-Gau Sab-Gaussian with some parameter. This implies its density function exhibits exponentially decaying tails and thus is well-controlled and integrable in tails. Overall, these observations suggest that Assumption (3.3] is easily satisfied in practice, and detailed discussion is deferred to Appendix []] Notably, our Algorithm Aadd its regret analysis (Theorem 3.5) rely only on the validity of this assumption, without requiring knowledge of the value C.
Now we will present the regret bound of our ESTOR shown in Algorihtm 2
Theorem 3.5. For any single index bandit with an increasing function, we set 0,
V /3(e--1-e e;-2) (2-2)
log(2dlogg (T)/8), and To to any value s.t. Ty I dy ToyKKTogl220 (2d (T)/6)
in Algorithm [ Then under Assumption 2.2 2.2
2.3 3.3
our Algorithm Dean attain following regret
bound with probubility at least
RI 0 (dk33 VC. T logg(d (T)/0)) = =Ō Ō (dKká = Ör(VT).
We begin by characterizing the sampling distribution over arms induced by greedy selection within each epoch of ESTOR. Leveraging this structure, we apply Stein's identity relate ((x)) to 0. and bound the estimation error of 0; using samples from the previous epoch, supported by a novel moment analysis of the score function under the induced distribution. We then show that the per-round regret within each epoch is upper bounded by the estimation error of f;, and that due to the exponential growth of epoch lengths, these error terms decay geometrically across epochs. Summing over all epochs yields the final regret bound of 3/d33/2 /T).
Proof sketch of Theorem 3.5
Remark 3.6. The regret bound derived in Theorem 3.5 exhibits worst-case dependency K of order K-3/2 under Assumption 3.3 based on a conservative bounding technique. However, we can show that under many common scenarios, including when the arm Zt,5 is sampled from a d- dimensional normal distribution, i.e. W(ux )x), the dependency on K improves to O ((Vlogg (K)) when Ki is large. It is noteworthy that this order of K matches the lower bound deduced in Li et al. (2019) for the simpler linear contextual bandit problem, despite our study addressing a significantly more challenging setting due to the unknown reward function. detailed discussion is presented in Appendix K
It is essential to highlight that T' is the dominant term the bandit literature primarily focuses on the order of T (Ding et al. 2021| Lattimore & Szepesvári] 2020), and our Algorithm 2 achieves a nearly optimal dependence on T as Or(vT). Furthermore, ESTOR highly efficient in both time and memory complexity. Since the estimator is computed via simple average over each epoch and the algorithm performs greedy action selection at each round, the total time complexity is (dd)). Moreover, ESTOR only maintains the current parameter estimate and another vector containing the sufficient statistics for the truncated mean, yielding total storage complexity of O(d). Beyond its strong theoretical guarantee, ESTOR stands out as one of the most efficient algorithms (Ding et al. (02T)) in terms of both computation and space among GLB methods, despite addressing substantially more difficult setting with unknown reward functions.
3.4 EXTENSION TO SPARSE HIGH-DIMENSIONAL. BANDITS AGNOSTIC TO INCREASING REWARD FUNCTIONS
With high- digeedimnnsional sparse data becoming increasingly prevalent in modern applications. growing body of work has focused on sparse linear bandits, a.k.a. LASSO bandits (Jang et al. 2022 Hao al. 2020), where each arm is represented by high-dimensional feature vector, but the underlying parameter 0_ is assumed to be sparse with at most 8 & nonzero entries. To extend our methods to this sparse tighddimensional regime, incorporate I (-rreuuaarization into our loss function defined in Eqn. ( ie. À > O. By carefully choosing the regularization parameter X, we establish Theorem 3.7 Notably, achieve the same optimal error bound as in the low-dimensional case (Theorem 3.1 with the ambient dimension d replaced by the sparsity index 8, without the knowledge of
Theorem 3.7. (Bound of Sparse SIM) For any sparse single index model where 0, has s nonzero entries, and samples ;1,-..,Tr In are drawn from some distribution D. We denote
7

---

Published as a conference paper at ICLR 2026
Hr = (xTT)))) X ~ D and assume H4, # 0. Under Assumption 2.2
2.3 by solving the
optimization problem in Eqn. with r
13(02 Mn/ log((d/66))) 06, and
M(o² + log(///2//0)) A -=
with probability at least (1 - 5) it holds that:
3 || - 1.bal11 - 1 (
pe-m.o.1. S 3 5 (}²)
Remarkably, our efficient STOR and ESTOR algorithms can be directly applied to the sparse high-dimensional SIB setting by simply replacing the original estimator with the solution to the 4 regularized loss function in Eqn. [T) at each epoch, i.e. line 4 of Algorithm and line 5 of Algorithm 2 Both methods not only retain their optimal computational and memory efficiency, but also inherit the regret bounds established in Theorem 3.2 and Theorem 3.5 with the ambient dimension d replaced by the sparsity index r, all without requiring the value of r. This fact is formalized in Corollary 3.8
Corollary 3.8. For any sparse single index bandit with an increusing function:
1. we sei Ti = (sT) log (2d/5)3, = /3002 L3) log (2d(2) and
11 / + ( (og(2d/8)/n in Algorithm Then under Assumption 2.2 2.3
we have
the following regret bound with probability at least 1 5:
RT = ( (log (d/8))b) = (stT²)
-
2. we sei
33 MK)( l2d log2 (T)/8),
);
11 / (o² + 12MCK + MK) (200g//2/////11--00000 and To any value
To S
d 13 (og((dlog) logz (T)/5) in Algorithm 2 Then under Assumption 2.2 2.3
3.3
our Al-
gorithm 2 can attain following regret bound with probubility least
Ri 0 (K VT log(d (T))))) =Ō (sK (T) Ör(VT).
Notably, both our SIM estimator and the ESTOR algorithm do not rely on the value of the sparsity level s in either theory or implementation under the sparse nigh-dimensional setting. For STOR, the value of is used solely set the exploration phase length Ti. Even if we remove this dependence and set Ti independently of 8, STOR still achieve regret bound of order (sTT2/3). where the exponent of & increases from 2/3 to 1.
3.5 EXTENSION TO ARBITRARY REWARD FUNCTIONS
Finally, we study the SIB problem with arbitrary continuously differentiable reward functions. As this problem is very complicated, and modern offline works general SIMs still rely on restrictive distributional assumptions (Härdle) 2004), we make a similar choice in this initial ex- ploration of the online setting by assuming that each feature vector drawn from Gaussian distribution, i.c. D = . [Px,, )x), for some positive definite matrix Σx. Similar to the iden- tifiability assumption in Section 2 we make slightly modified assumption purely for analyti-
cal convenience with || ll = 1. Additionally, for the general SIBs, we have to assume n4. = ( 0.)) > O.X D to avoid further identifiability issues, e.g., f(x) = f(-x) implies that 0. and -0. are indistinguishable.
We first compute the estimator i based on Eqn. (I) with
in the low-dimensional setting, followed by a normalization step 6, = 0 //|E>// /2/ 01 to scale the estimator onto a fixed and stable manifold. We then propose novel approach to estimate the unknown link function ʃ(-) via kernel
8

---

Published as a conference paper at ICLR 2026
OuryAdiio Rugent Sqarrs Hueder
LCB SUP
STOR 68104
Snce
S00R
Figure 1: Plots of regrets of STOR, ESTOR, and the baseline methods under linear (1) and generalized linear (2)-(4) scenarios. Misspecified models are shown dashed lines in (3) and (4).
regression Härdll 2004): given another independent set of samples {Vx, ) the predictor f(-) is given by,
2 Kr (=-an xT E K1, x
|= -- -===1100l S W, Vz E IR, where Ka(v) 7 h (IMSS) (2)
1
f(:)= =
otherwise,
and W and h are the bandwidth and truncation parameters for the uniform kernel, respectively, We adopt the convention 0/0 = To handle this fully agnostic case with arbitrary reward functions, we propose a new algorithm, General STein's 's ORacle single index bandit (GSTOR), which adopts a double palloratioo-then-comeee Algorithm in Appendix L Specifically, GSTOR uses two separate exploration phases: the first estimates the parameter via Eqn. ①I using Ti samples {Vi, { and the second approximates the reward function based on the kernel regression via Eqn. 2 with an additional Ti independent samples {yi, xz }-) Remarkably, we prove that this design yields prediction error bound
strategy. Due to space limit, the full algorithm is presented in
O(VāT,1//3 as formalized in Appendix L.3 through a novel integration of kernel smoothing analysis and perturbation arguments. Following the double exploration phases, GSTOR selects arms greedily based on the estimated parameter and the approximated reward function. The expected regret bound of GSTOR is given in Theorem 3.9 with its detailed proof deferred to Appendix L
Theorem 3.9. For any SIB problem, set Ti = d T (oT/// W 2 log (Ti), h= T and x in Algorithm 3 Then under the Gaussian design with assumptions (i). (s())) s Ly.1f' S L Vx (part of Assumption (ii). d OT?2, we have E(Rr) OdeTT)
Our GSTOR provides the first solution to SIBs with general reward functions and achieves sublinear regret bound. Importantly, it remains unclear whether a Õ(VT) regret bound is achievable in this general setting. Even in the simpler Lipschitz bandit setting, which optimizes an unknown Lipschitz function without contextual features, the minimax regret bound is known exceed vT. Since our setting introduces further complexity by requiring simultaneous estimation of both the continuously differentiable reward function and the parameter, it suggests that achieving /T regret should be fundamentally unattainable without imposing additional structural assumptions.
EXPERIMENTS
In this section, we empirically validate that our proposed methods, especially ESTOR, perform efficiently across diverse link functions through simulations and real-world experiments.
For the simulation studies, we consider four types of increasing link functions and their corresponding models: (1). f(x) = x with Gaussian noise (0, 0.25) (linear); (2). fxx = exp(x) with outcomes sampled from the Poisson regression model (Poisson); (3). f(x sign(z) x² + 2x with Gaussian noise (0, 0.25) (square); (4). f(r) = 5 with Gaussian noise (0,00. 0.25) (fifth). For the linear case (1), we use LinUCB (Li et al. 2010 and Lin'TS (Agrawal & Goyal 2013) as baselines. For the generalized linear cases (2),(4) we compare our methods against the widely used UCB-GLM (Li (ct al., 2017) and GLM-TSL (Kveton et al. 2020) algorithms. We set the time horizon to T 10, 000, with detailed experimental configurations deferred to Appendix M to space constraints. Average regrets over 20 repetitions are displayed in Figure I Notably, for cases (3) and (4), we further evaluate UCB-GLM, and GLM-TSL by fitting them under one reward model and deploying them under the other to assess robustness under misspecification. Solid lines represent correctly specified models, while dashed lines represent misspecified ones.

---

Published as a conference paper at ICLR 2026
From the results in Figure observe that ESTOR consistently achieves comparable performance to the best baselines across all four types of link functions, demonstrating its high efficiency. In contrast, STOR exhibits clear initially grows and then flattens out. Moreover, when UCB-GLM and GLM-TSI. are fitted under an incorrect underlying reward function, both methods suffer significant performance degradation and slower convergence rates. This observation further highlights the vulnerability of traditional GLB algorithms to model misspecification, underscoring the importance of designing agnostic approaches like ours that can maintain robustness across diverse reward structures. Furthermore, we report the average running time of different methods from Figure I in Table [ MM. Aligned with our time complexity analysis in Subsection 3.3 ESTOR and STOR exhibit substantial computational advantages, performing hundreds of times faster than UCB-GLM and thousands of times faster than GLM-TSI.. This fact demonstrates their practical scalability for real applications. We also include the performance of GSTOR across the four cases in Table 2 in Appendix M While GSTOR is designed for general reward functions and is thus generally less efficient than STOR in these monotone settings, it consistently outperforms GLB-based B-based algorithms under model misspecification, demonstrating its robustness across broader range of reward functions.
perratioonnteee-xpoitttttioooo pattern in its regret curve, which
Due to space constraints, we defer the simulations on the sparse nigh-dimensional case introduced in Subsection 3.4, well two real-world experiments on the Forest Cover Type dataset (Blackard) 1998) and the Yahoo news dataset (Chu et al. 2009) involving the GSTOR method presented in Sub- section 3.5 to Appendix M According to Table 3 all our proposed methods consistently outperform ththe-tf GLB methods. This stems from the fact that the underlying link function is typically unknown in real-world applications. and GLB methods are vulnerable model misspecification. These results firmly underscore the practical value of our agnostic approach in reality.
5 CONCLUSION
In this work, we introduce new problem of generalized linear bandits with unknown reward functions, a.k. single index bandits. We develop family of efficient algorithms, starting with the case of monotonic reward functions and extending sparse nigh-dimensional and non-monotonic settings with solid regret analysis. Central to our approach a novel Stein's -s-method- -based estimator achieving the optimal error rate under mild assumptions. We validate the effectiveness of our algorithms through comprehensive simulations and real experiments. Our work lays the foundation for various promising directions in future research the SIB problem.
Limitation and Future Work: Our analysis assumes the arm set is drawn i.i.d. from some fixed dis- tribution, rather than adversarially selected as in parts of the GLB literature (Lattimore & Szepesvári 2020). Moreover, regret analysis of GSTOR relies on the Gaussian design assumption, which is standard studies of SIMs and kernel regression due the inherent estimation difficulty (Carroll et al. 1997). Extending these results to more general settings remains a challenging open direction, even the offline statistical learning context.
ACKNOWLEDGEMENTS
We appreciate the constructive feedback from the anonymous reviewers and area chair. Bongsoo Yi and Yao Li were supported in part by the National Science Foundation under grants DMS-21 215229 and
Doudou Zhou was supported by the NUS Start-Up Grant and the MOE AcRF Tier I Grant (A (A-8003569-00-00,
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
We strictly adhere to the ICLR Code of Ethics. This study uses only public and simulated data, involves human subjects, and raises no foreseeable ethical concerns.
REPRODUCIBILITY STATEMENT
We have taken necessary steps to ensure the reproducibility of our results. All algorithmic details provided in the main paper, including clear pseudocode for our proposed methods. Complete theoretical proofs of all main results are included in the Appendix. Experimental details such as dataset descriptions and preprocessing steps presented in the Appendix. In addition, submit the source codes as part of the supplementary material for reproducibility.
REFERENCES
Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24, 2011.
Yasin Abbasi-Yadkorf David Pal, and Csaba Szepesvari. Online-to-coffidenc--stt conversions and application sparse stochastic bandits. In Artificial Intelligence and Statistics, pp. 1-9. PMLR, 2012.
Marc Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Artificiaa Intelligence and Statistics, pp. 176-184. PMLR, 2017.
Alekh Agarwal, Miroslav Dudik, Satyen Kale, John Langford, and Robert Schapire. Contextual bandit learning with predictable rewards. Artificial Intelligence and Statistics, pp. 19-26. PMLR, 2012.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoffs. In International conference on machine learning, pp. 127-135. PMLR, 2013.
Sakshi Arya and Hyebin Song. eermmeereetttic batched global multi-armed bandits with covariates. arXiv preprint arXiv:2503.00563 2025.
Peter Auer, Nicolo Cesa-Bianchi Yoav Freund, and Robert E Schapire. Gambling in rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-331. IEEE, 1995.
Fadoua Balabdaoui, Cécile Durot, and Hanna Jankowski. Least squares estimation in the monotone single index model. Bernoulli, (244433337633310 2019a.
Fadoua Balabdaoui, Piet Groeneboom, and Kim Hendrickx. Score estimation in the monotone
single-index model. Scandinavian Journal of Statistics, 46(2):517-544, 2019b.
Jock Blackard.
Covertype.
UCI Machine Learning Repository, 1998.
DOI:
Ilija Bogunovic and Andreas Krause. Misspecified gaussian process bandit optimization. Advances in neural information processing systems, 34:3004-3011 2021.
Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Sébastien Bubeck, Nicolo Cesa-Bianchi, and Gábor Lugosi. Bandits with heavy tail. IEFE Transac- tions on Information Theory, 59(11):7711-7717, 2013.
Raymond J Carroll, Jianqing Fan, Irene Gijbels. and Matt P Wand. Generalized partially linear single-index models. Journal of the American Statistical Association, 92(438):477-489 1997.
Olivier Chapelle and Lihong Li. An empirical evaluation of thompson sampling. Advances in neural information processing systems, 24, 2011.

---

Published as a conference paper at ICLR 2026
Wei Chu, Seung-Tael Tack Park, Todd Beaupre, Nitin Motgi, Amit Phadke, Seinjuti Chakraborty, and Joe Zachariah, case study of behavior-driven conjoint analysis on yahoo! front page today module. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 1097-1104, 2009.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference Artificial Intelligence and Statistics, pp. 208-214, JMLR Workshop and Conference Proceedings, 2011.
Ran Dai, Hyebin Song, Rina Foygel Barber, and Garvesh Raskutti. Convergence guarantee for the
sparse monotone single index model. Electronic Journal of Statistics, 16(2):4449 4496, 2022.
Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In COLT; volume 2, pp. 3, 2008.
Persi Diaconis, Charles Stein, Susan Holmes, and Gesine Reinert. Use of exchangeable pairs in the analysis of simulations. In Stein's 's Method, pp. 1-25. Institute of Mathematical Statistics, 2004.
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1585-1593. PMLR, 2021.
Qin Ding, Yue Kang, Yi-Wei Liu, Thomas Chun Man Lee, Cho-Jui Hsieh, and James Sharpnack. Syndicated bandits: A framework for auto tuning hyper-parameters in contextual bandit algorithms. Advances in Neural Information Processing Systems, 35:1170-1181, 2022.
Jianqing Fan, Weichen Wang, and Yiqiao Zhong. Robust covariance estimation for approximate factor models. Journal of econometrics, 208(1):5-22 2019.
Jianqing Fan, Weichen Wang. and Ziwei Zhu. A shrinkage principle for heavy-tailed data: High- dimensional robust low-rank matrix recovery. Annals of Statistics, 49(3): 2021.
Jianqing Fan, Zhuoran Yang, and Mengxin Yu. Understanding implicit regularization in parameterized single index model. Journal of the American Statistical Association, 118(544): 2315-2328, 2023.
Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári. Parametric bandits: The generalized linear case. In NIPS, volume 23, pp. 586-594, 2010.
Dylan Foster and Alexander Rakhlin. Beyond ueb: Optimal and efficient contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 3199-3210. PMLR, 2020.
Dylan Foster, Alekh Agarwal, Miroslav Dudík, Haipeng Luo, and Robert Schapire. Practical contextual bandits with regression oracles. In International Conference on Machine Learning, pp. 1539-1548. PMLR, 2018.
Dylan J Foster and Akshay Krishnamurthy. Efficient first-order contextual bandits: Prediction, allocation, and triangular discrimination. Advances in Neural Information Processing Systems, 34: 18907-18919, 2021.
Avishek Ghosh, Sayak Ray Chowdhury, and Aditya Gopalan. Misspecified linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
László Györfi, Michael Kohler, Adam Krzyzak, and Harro Walk. distribution-free theory of nonparametric regression. Springer Science & Business Media, 2006.
Aaron K Han. Non-parametric analysis of a generalized regression model: the maximum rank correlation estimator. Journal of Ecomometrics, 35(2-3):303-36,, 1987.
Botao Hao, Tor Lattimore, and Mengdi Wang. High-dimensional sparse linear bandits. Advances in Neural Information Processing Systems, 13:13333- 2020.
Wolfgang Härdle. Nonparametric and semiparametric models. Springer Science & Business Media, 2004.
12

---

Published as a conference paper at ICLR 2026
Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Popart: Efficient sparse regression and experimental design for optimal sparse linear bandits. Advances in Neural Information Processing Systems, 35:2102-2111 14, 2022.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. Advances in Neural Information Processing Systems, 30, 2017.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low-rank matrix bandit problems. Advances in Neural Information Processing Systems, 35:19971-19983, 2022.
Yue Kang, Cho-Jui Hsieh, and Thomas Lee. Low-rank matrix bandits with heavy-tailed re- wards. In The 40th Conference on Uncertainty in Artificial Intelligence, 2024a. URL https?
/openreview net h
Yue Kang, Cho-Jui Hsieh, and Thomas Lee. Online continuous hyperparameter optimization for generalized linear contextual bandits. Transactions on Machine Learning Research, 2024b.
Gi-Soo Kim and Myunghee Cho Paik. Doubly-robust lasso bandit. Advances in Neural Information Processing Systems, 32, 2019.
Branislav Kveton, Manzil Zaheer, Csaba Szepesvari, Lihong Li, Mohammad Ghavamzadeh, and Craig Boutilier. Randomized exploration in generalized linear bandits. In International Conference on Artificial Intelligence and Statistics, pp. 2076-2076. PMLR, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li. Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. In Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Lihong Li, Yu Lu, and Dengyong Zhou. Provably optimal algorithms for generalized linear contextual bandits. In International Conference on Machine Learning, pp. 2071 2071-2080. PMLR, 2017.
Wenjie Li, Adarsh Barik, and Jean Honorio. A simple unified framework for high dimensional bandit problems. In International Conference on Machine Learning, pp. 22619-12655. PMLR, 2022.
Yingkai Li, Yining Wang, and Yuan Zhou. Nearly minimax-optimal regret for linearly parameterized bandits. In Conference on Learning Theory, pp. 2173-2174 PMLR, 2019.
Yangyi Lu, Ziping Xu, and Ambuj Tewari. Bandit algorithms for precision medicine. In Handbook of Statistical Methods for Precision Medicine, pp. 260-294. Chapman and Hall/CRC, 2021.
Peter McCullagh. Generalized linear models. Routledge, 2019.
Sen Na, Zhuoran Yang, Zhaoran Wang, and Mladen Kolar. High- digh-dimmesiionl varying index coefficient models via stein's 's identity. Journal of Machine Learning Research, 20(152): 2019.
Matey Neykov, Jun S Liu, and Tianxi Cai. Ll-regularized least squares for support recovery of high dimensional single index models with gaussian designs. Journal of Machine Learning Research, 17(87):1-37, 2016.
Aldo Pacchiano. Second order bounds for contextual bandits with function approximation. arXiv preprint arXiv:2409.16. 16197, 2024.
Yaniv Plan and Roman Vershynin. The generalized lasso with non-linear observations. IEEE Transactions on information theory, 62(3): 2016.
Nived Rajaraman, Yanjun Han, Jiantao Jiao, and Kannan Ramchandran. Statistical complexity and optimal algorithms for nonlinear ridge bandits. The Annals of Statistics, 52(6):2557-2582 2024.
Daniel Russo and Benjamin Van Roy. Learning to optimize via iiloommatioo-drecttee sampling. Advances in neural information processing systems, 27, 2014.
13

---

Published as a conference paper at ICLR 2026
David Simchi-Levi and Yunzong Xu. Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizabilityy. Mathematics of Operations Research, 47(3):1904-1931. 1931, 2022.
Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi. Lasso with non-linear measurements is equivalent to one with linear measurements. Advances in Neural Information Processing Systems, 28, 2015.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2):199, 2015.
Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48, Cam-
bridge university press, 2019.
Yao Wang, Jiannan Li, Yue Kang, Shanxing Gao, and Zhenxin Xiao. Generalized low-rank matrix contextual bandits with graph information. arXiv preprint arXiv:2507. 17528, 2025.
Bo Xue, Yimu Wang, Yuanyu Wan, Jinfeng Yi, and Lijun Zhang. Efficient algorithms for generalized linear bandits with heavy-tailed rewards. Advances in Neural Information Processing Systems, 36, 2024.
Zhuoran Yang, Krishnakumar Balasubramanian, and Han Liu. High-dimensional non-gaussian single index models via thresholded score function estimation. International conference on machine learning, pp. 3851-38516 PMLR, 2017.
Chenlu Ye. Yujia Jin, Alekh Agarwal, and Tong Zhang. Catoni contextual bandits are robust to heavy-tailed rewards. arXiv preprint arXiv:2502.02486, 2025.
Bongsoo Yi, Yue Kang, and Yao Li. Biased dueling bandits with stochastic delayed feed- back. Transactions Machine Learning Research, 2024. ISSN 2835-8856. URL https
wwwprevieew.nt/forrmne Hd-dddddH---AAWAL..
Bongsoo Yi, Yue Kang, and Yao Li. Quantum lipschitz bandits. In The Fortieth AAAI Conference on wwtppeerreiie..nt/forruueee wtt///tt/oornoo wttp://oorrnn.GBBBCCLBEB Be
Artificial Intelligence, 2025. URL
Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In International Conference Machine Learning, pp. 392-401. PMLR, 2016.
Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou, Haipeng Luo, and Paul Mineiro. Practical contextual bandits with feedback graphs. Advances in Neural Information Processing Systems, 36: 30592-30617, 2023.
Yinglun Zhu and Paul Mineiro. Contextual bandits with smooth regret: Efficient learning in continu- ous action spaces. International Conference on Machine Leurning, pp. 27574-27590. PMLR, 2022.
14

---

Published as a conference paper at ICLR 2026
Appendix
A THE USE OF LARGE LANGUAGE MODELS
We used a large language model (LLM) minimally for minor sentence rewriting and language polishing. The LLM was not used for any research-related tasks, and all scientific contributions were developed solely by the authors.
B RELATED WORK AND DISCUSSION
Generalized L Linear Bandits: Filippi al. (2010) first introduced the GLB problem (I (Lattimore
& Szepesvári 2020) by extending the linear bandit framework (Abbasi- Yadkori et al., 2011 Dani
et al. 2008) and proposed GLM-UCB with a regret bound of order O(dvT), and Li et al. (017) subsequently developed improved UCB-style algorithms with tighter regret bounds. A parallel line of work explores TS approaches for GLBs. Chapelle & Li (2011) proposed Laplace-TSS under the Gaussian design, and then Abeille Lazaric (201)) Russo Van Roy (014)) showed that TS can be analyzed similarly to UCB under general distribution by bounding the information ratio. More recently, Kveton et al. (2020) demonstrated that their randomized TS TS-based methods achieve nearly optimal regret bounds. up logarithmic factors. To improve the scalability of GLBs, Zhang et al.
(2016) and Jun al. (017) proposed algorithms based the online Newton step, achieving O(vT) regret with improved time and space efficiency. Ding et al. (022) introduced another efficient GLB algorithm that combines stochastic gradient descent with the TS framework enhance computational performance. Recently, Rajaraman et al. (2024) briefly examined a closely related GLB problem with an unknown link function as part of broader study. However, they only consider more restrictive assumptions, including fixed action sets, Gaussian noise, and strong structural constraints on the reward function. Their method also computationally intensive and lacks empirical validation. In contrast, our work offers more general and efficient framework that supports non-monotone link functions, handles nigh-dimensional sparsity, and achieves optimal statistical and computational guarantees. The very recent work by Arya & Song (2025) focuses related but different setting, batched multi armed bandit with covariates, using a single index modeling approach combined with dynamic binning and elimination. This work represents concurrent and independent effort. To the best of our knowledge, our work provides the first comprehensive treatment of the single index bandit problem under mild assumptions.
(Rajaaaayn
The single index model (SIM) has been extensively studied in the low- dimensional setting (Han 1987 / Härdle 22004; Carroll et al. 1997). where most approaches estimated the unknown parameter via (quasi- mmaximum likelihood estimation and establish asymptotic guaran- tees using central limit theorems. For non-asymptotic bounds, seminal works such as Thrampoulidis al. (2015); Na al.) (2019); Plan & Vershynin (2016) NNykov et al. (2016) employed traditional regression techniques such as 1 I-regularization. These results show that, under standard Gaussian covariates and certain conditions on the link function, the estimator can achieve the same error rates as our Theorem and Theorem 3.7 However, these guarantees crucially rely on restrictive distributional assumptions such as standard Gaussian covariates. More recently, Yang et al. (0117) relaxed these distributional assumptions by proposing efficient estimator, and Fan et al. 2023 further extended with a regularization-fee approach based on overparameterization that achieves optimal non-asymptotic rates, but still assumes that each entry of the context vector is i.i.d. from a known distribution and that the noise has finite fourth moment. In summary, due to the inherent challenges of SIM estimation, prior statistical literature imposes strong assumptions on the data distribution, whereas our work requires milder conditions.
Single Index Models:
Since part of our work focus on the case where the unknown link function is monotonically increasing, we also examine line of recent work on statistical estimation in monotone SIMs. Balabdaoui et al. (2019a) propose least-squares estimator for monotone SIMs, establishing a convergence rate of 1/3 under a suite of strong assumptions on the noise and covariate distributions (see assumptions A1-A6 therein). To improve upon this, [Balbdaoui et al. (2019b) propose score-based estimator with the same n 1/3 rate under milder assumptions, and achieves the optimal n 1/2 rate when the link function is piecewise constant. More recently. Dai et al. (0022) extend this line to the sparse,
15

---

Published as a conference paper at ICLR 2026
nigh-dimensional setting, but their projection -based estimator still only guarantees n-1/3 rate under nontrivial distributional assumptions. Collectively, these results underscore the statistical and algorithmic challenges of efficient monotone SIM estimation even under nontrivial assumptions, and motivate our pursuit of a computationally cheap and distributionally robust method with optimal convergence guarantees.
Contextual Bandits under the Realizability Assumption: The general contextual bandit problem
under the realizabilitty assumption initiated by AAgawal et al. (2012). A substantial line of work
builds on this assumption by reducing the problem to solving either offline or online square-loss losss
regression oracles (Foster et al. 20118; Foster & Rakhlin 2020 Simchi-Levi & Xu [022]] Foster &
Krishnamurthy 2021] Zhu & Mineiro 2022 Zhang et al. 2023 Pacchiano [024] Ye et al. 2025).. However, as discussed in Section| | such regression oracles are infeasible under STMs due to the
composite and nonparametric structure of the reward function. Beyond this limitation, the regret bounds of modern works (Pacchiano 2024 Ye et al., 2025) rely on some complexity measure of the function class, such as the eluder dimension (Russo & Van Roy 2014). However, in our proposed SIBs with unknown reward functions, the eluder dimension becomes unbounded, making these results inapplicable again.
To illustrate this point, we use FALCON+ (Simchi-Levi & Xu, 2022) as a representative state-of- the-art example to explain why contextual bandit algorithms under the realizability assumption fail under the SIB setting in detail. FALCON+ critically relies on their Assumption 2, which assumes access
offline oracle that can estimate the full reward function, comprising both the unknown parameter vector and the unknown reward function, with a provable error bound, using data collected via randomized sampling only from the previous epoch (i.e., line 6 of the algorithm). To achieve the optimal VT regret bound, this oracle must guarantee estimation rate of the optimal order n-1/2 1/2. However, existing method for single index models comes close to satisfying this requirement. As discussed our review of SIM and monotone SIM literature above, existing estimators rely on restrictive distributional assumptions (e.g., i.i.d. Gaussian features). Moreover, the randomized sampling scheme in FALCON+ produces covariate distributions that lie far outside the regimes where existing estimators have any theoretical guarantee, let alone achieve the optimal rate of n 1/2, As result, although FALCON+ is conceptually insightful, its reliance idealized regression oracle renders it inapplicable to the SIB setting with any provable theoretical guarantees. Furthermore, existing methods are computationally expensive as the least squares solver leads to infinitediimensional and non-convex optimization problems under SIMs Fan et al. (2023). These challenges highlight that existing methods are fundamentally inadequate for the SIB setting, necessitating the development of a completely new solution.
C SUMMARY OF TECHNICAL NOVELTY
In this section, we summarize the technical contributions of our work in detail. We start from utilizing the novel Stein's meedsss-m-o-baaaaa estimator in Eqn. (I). which enables us to estimate the parameter 0g even when the reward function f(-) is unknown. Specifically, Stein's identity implies that (X 0.)- S(x) = p.O., for some scalar u. * O, under mild regularity conditions. Thus, taking (truncated) average of y: S(x;) yields estimator that is directionally aligned with 8, The truncation function o, is essential to control the variance of the estimator in the presence of heavy- tailed rewards, as show through the bias variance trade-off in the proof. Note our estimator is computationally efficient, does not require knowledge of the reward function, and crucially, achieves the optimal estimation rate under mild assumptions. Moreover, we extend this estimator to the high- nigh-dimensional sparse regime with a simple ε regularizer, and it still achieves the minimax-optimal rate without requiring knowledge of the sparsity level s in Theorem 3.7
The proof of Theorem 3.1 follows a classical comparison argument. We first apply Stein's 's identity to show that S(x,)(x;)) p.0... which motivates our estimator. We then analyze the optimization
gap between the empirical loss (() and L(u.0.) ) by bounding the gradient norm [ lxxo. where the bias is controlled by truncation and the concentration is handled via Bernstein's 's inequality. Finally, applying a first-order Taylor expansion and standard convexity arguments yields the lz and l estimation bounds. Notably, the estimator admits closed-form solution in the low-dimensional setting, achieving ((/d/)) rate without requiring knowledge of f(-). For Theorem 3.7
we adapt
16

---

Published as a conference paper at ICLR 2026
this argument the sparse high- digh-dimensional regime by adding an pe-pelly to the loss and leveraging subgradient optimality conditions. While the core Stein's s-method-baat basee structure remains intact, we use support-splitingg analysis to decouple estimation This enables obtain sparsity-adaptivy rates of ((ys/n) in Eg norm and ((svvn) in & norm, again without requiring prior knowledge of the link function.
the true support versus its complement.
Since our estimator, grounded in Stein's 's identity, avoids the need explicitly estimate the unknown reward function, a central advantage of our STOR and ESTOR emerges in the monotonic setting: when the link function is assumed to be monotone increasing. the relative ordering of f( 0) is preserved by x: Ô. This allows the algorithm to perform greedy action selection based solely on æ: 0, without requiring inowledge of the explicit form of f(-). As result, our method achieves substantial gains in sample efficiency by sidestepping the additional exploration cost typically associated with function estimation. Importantly, this setting subsumes the entire class of generalized linear bandits (GLB) with canonical exponential family link functions, which are inherently monotone (McCullagh 2019). In this way, our estimator leverages structural properties of the reward function class to implicitly handle function uncertainty, enabling principled decision-making without direct function recovery.
In particular, our ESTOR achieves the minimax-optimal regret bound of Ö(VT) without requiring explicit knowledge of the link function. Explore-then-Commii (FrC) algorithms are known to be suboptimal in regret minimization, as parameter estimation is performed exclusively using data from the initial exploration phase, ignoring informative samples collected thereafter. ESTOR is an spoch-based variant of STOR with exponentially growing epoch lengths. In ESTOR, the parameter estimate at the start of each epoch is computed using samples from the preceding epoch, followed by greedy selection in the current epoch. This design ensures continual refinement of the estimate and overcomes the inefficiencies of fixed-sample EIC schemes. Notably, the SIM estimator integrates naturally into this framework: greedy selection induces a tractable sampling distribution within each epoch, allowing Stein's 's identity be applied for efficient parameter estimation. For the proof of Theorem 3.5 we characterize this distribution and bound the estimation error at each epoch. Since epoch lengths grow exponentially, the error terms decay geometrically across epochs. Summing the regret over all epochs yields cumulative regret of ((d33/2VT)
Finally, in the general setting with arbitrary differentiable reward functions, we introduce GSTOR, which employs double exploration strategy. In the first stage, estimate the parameter O. using our Stein-based estimator. In the second stage, we estimate the unknown reward function f(()) via kernel regression over the scalar projections x f. We then apply an Explore-then Seatrrethen-Coommee -ommit (EtC) strategy using the estimated f to identify the best arm. This two-phase design decouples parameter and function estimation, enabling our SIB framework in a more general class of problems.
D PROOF OF THEOREM 3.1
D.1 USEFUL LEMMAS
Lemma D.1. (Generalized Stein's Lemma, Diaconis et al. (2004)) For d-dimensional continuous random variable X Rd with continuously differentiable density function p : RRd - R. and any continuously differentiable function f TRd IR. Denote S(X) TR - Rd the score function associated with X, i.e. S(X)= = f(X) S(X) in terms of the density exist, then it holds that
If the expected values of both V f(X) and
E[((X- S(X) EXV](
Lemma D.2. (Bernstein's Inequality, Wainwright 2019 Proposition 2.14) Let XI,..., ,n, be reul- valued rundom variables such that X S. almost surely for all = I,..., n, then for any > 0 we have that
E(X?) + bt
PP
Σ (x, B(x,)) 1=1
2 V2t.
< -t
17

---

Published as a conference paper at ICLR 2026
Lemma D.3. Assume we have pa (XTf(((T6.)) (.)) where X denotes the random vector drawn from the density pl.). By setting
3n(o² + +
log (2d/6)
in the single index model setting to solve @ according to Eqn. at least 5 (0 < < 1), it holds that,
with À 0. Then with probability
AV3
M(o2 + 57) log (2d/5) + +222
VV( 3
3
Proof. Recall that we have
L(0) (0,0)
> n
2
(0: S(z))) 8).
where (1 S(x;)) Sy. (2;;) )) S(xr)( A and the operation happens the vector elementwisely. According to Lemma D.1 it holds that for any i E [n]
E(y:S(zx)) = (x; 0.)S(a))) = (=; (o.) 0. =1.0..
Therefore, holds that
vl(u0.)) = 2u.0, 2
Σ
Φr (M S(x;))
"1 i=1
= -E(())((1))
be (ys S(x,))
1=1
Based on the above equation, we have that
|VVL(,00)]l>> [BB(I -2 "
Σ or (1 S(x.:))
S (2 ( ((11)))) + 2 S(x))) 2 Σ o (Ui -((i))
on
02
To bound ar, we first note that for each index j [d]. holds that
(()))))(zz)) ( (z) ))) < 2 (1v15,(z1)) (111,)00))))
And then we can easily bound the above value by
i (Iv) (1111) ) _ E (viS, E (1 (1(
< E (v15)(m1))) P ((y)1)) T)
( [ (f(xz 0. 0.) S + E (v)) E (S,(z1)3)) IP ((n)))(( >
(m)
E S, (o² + 1.7)² 72
M
(02 T27) M
where we have the inequality (i) due Holder's inequality, and we can deduce the inequality (ii) based on the fact that the white noise is independent with the arm .1. The inequality (iii) comes from Chebyshev's 's inequality. Since the above result holds for all index j E [d], which indicates that
2(02 + 1,3)
<
18

---

Published as a conference paper at ICLR 2026
On the other hand, since have that (3.5(z;)) are iid. samples, and for any i E [n]. [d] | (yt (x:)) S T, Var (1 Sy(x))) - I. (or(H) S E (u) (x;)))))))))) S (o 1.3) M,
then based on Bernstein's inequality in Lemma D.2 we have that for any j [d].
2(0² 12) log(2/2))
2r log (2/()/6)
P
Φ (y: S,(),) E (0+(11 (,(r1))) 2 21
n
n
3n
S 6.
(4)
Taking union bound over j E [d] in the above Eqn. 4 yields that
2(02 + M. (2d/))
2r log(2d/5)
IP
02
2V
S 6.
(5)
3n
Combining the results in Eqn. 3 and Eqn. (5) with probability least 1
6, it holds that,
2(0² + L7)M
2( + +33) log(2d/6)
2r log((d// (2d/6)
[VL(M,0))llo. 5
+ 21
(6)
n
3n
By taking
3n(o² + +7)
log (2d/8)
into Eqn. (6). we finally have that with probability at least 1- 6,
A/3
M(2 + 53) log (2d/8)
VL(H, 3
2V2
3
D.2 PROOF OF THEOREM 3.1
Proof. The proof is straightforward since our loss function L(O) is quadratic function with À = 0. We have L(0) O.,. due the choice of 0, then based the nature of quadratic functions, it holds that
I(O) L(u-0_)= VL(U)))) (0-N.0,) + =2|00 μ., 0.
Therefore, it holds that
||00 mnO0 1.0.11 VL(HOO.) (0 m=00.)
|VVL( | m.O.l $ ( - Vd,
and the last two inequalities are based on Holder's inequality and Cauchy-Schwarz Schwarz inequality respectively. Then by using the results in Lemma D.3] we have that with probability of least
2 210-
A43 + 2
M(62 + 87) log (2d/6)
||o maB. |||
Vd.
3
which is identical to
0 0, 11, 5
2v3
+
V2
dM + + (2d/6)
3
Finally, deduce the 1 norm bound:
| mmlal 11,.vv <vd. ||0- u.O.
11,
22
+ V2 d. d.V
M(o² + +57 log (2d/8)
n
19

---

Published as a conference paper at ICLR 2026
E PROOF OF THEOREM 3.2
E.I USEFUL LEMMAS
Lemma E.1. Let f be a continuously differentiable and non-decreasing function on an interval IC R. Let X be continuous random variable whose support is (or at least covers) the entire interval I. If
Bi)( = 0,
then f is constant on 1.
Proof. First, because f is non-decreasing, we have (x) is nonnegative function on I. Next, by hypothesis,
[[f = 0.
In terms of integration against the density of X, this means
J, (.(()apx())) 0.
Since ('(x) 2 for all x I, the integral (or expectation) of nonnegative function being zero forces
(x(x)= =0 for almost every x E T.
Because f is continuously differentiable. (x) is actually a continuous function on I. A continuous function that zero almost everywhere on an interval must be zero everywhere on that interval. (Otherwise, if f'(xo) * O for some Fu, continuity would force f'(x) to be nonzero on an entire neighborhood around zig, contradicting the fact that (z(x) = a.e.) Consequently,
(x) =0 0 for all x E I.
Finally, function whose derivative is identically zero on an interval is necessarily a constant function on that interval. Therefore, f must be constant on I.
E.2 PROOF OF THEOREM
Proof. On the hand, if we have (X O, then based Lemma F.1 know that f((-) is constant on the support of X T 0.. Therefore. the expected reward for all possible arms are constant, which indicates that cumulative regret Ry 0, and Theorem 3.2 naturally holds.
On the other hand, if we have (X 0, 1) o O, then we can utilize the results from Theorem 3.1
Denote μ² Ef (X (XT0_)) as in Theorem 3.1 Then for any Ti, we have that
0
0
0.) - f(xT0.) = flxT,0.)
21,0
+
f
f(xTO.)
1
θ
S 51(TT,
11, 10*
+
f
)(xT0.)
1
θ
0
Up 12e
0,
L9 xt
0.
11a
4
0
Lp
|| 11
+ Lg ||
0,
14
14a
Lg
| 11
bo
0
p00
Lr.
||
0
120
1r
1
M log (2d/8)
Ti
20

---

Published as a conference paper at ICLR 2026
with probability at least 8 where the last inequality comes from the 4 n-orr error bound proved in Theorem
3.1 Therefore, based on the choice of T1 we have that:
T
Rr (x, fxxT
Σ T=+++
[f(x) fxx
log (2d/5) T
T= 0 (dăT' (log (2d/0)) = (d8TT)
2 2L + +dv
Remark E.2. Our final regret bound includes additional multiplicative factor of 1/4.- according to Eqn. Zi μt, not zero. For special case where μl, = we have shown in Lemma E. that the regret indeed zero. When μ,, > O, this factor is constant and does not affect the order of the final regret bound. As a special case, when the derivative of the unknown reward function is assumed to be lower bounded by some constant 0, the final regret bound in the worst case inherits additional 1/c multiplier without knowing the value of c. This fact also holds for Theorem 3.5 and Corollary 3.8
PROOF OF THEOREM 3.5
F.1
USEFUL LEMMAS
Lemma F.. For all >> b> 0, the following inequality holds:
Va -- S /2a 2b.
Proof. Dividing both sides by vb > 0 and setting Va 1, the inequality reduces to
x 2( -
Squaring both sides (which is valid since both sides nonnegative for z 1) yields
(x - 1) < 2(x² 1).
Expanding and rearranging gives
x² 2x + 1 < 2x -
x + 2x 3.
Since 1, the inequality x² 2x 2 3 always satisfied. Thus the original inequality holds.
Lemma F.2. Let Zi...., EK be i.i.d. continuous random vectors in Hd drawn from common
distribution Do with probability density function p(z). Fix an arbitrary vector 0 Rd and define
arg max (z]
15I5K
Then the density function of x is
pe( K p(x) (Folx (0)x K-1
where po(.) and Fo(-) are the density and cumulative distribution functions of TO with x ~ Do. i.e.
and po(m) d.
Fo(m) P (x 2 m)
Fo(m).
dm
Furthermore, the score function STe (x:) V log can be written
S (x) (T (K- 1K p0 0.
Fo
Proof. Let .1....,.. be i.i.d. samples from distribution D. For each realization, define
arg max (2, 0). 15i5K
We compute the density x." We have that
P(x" dx) P(""" E dr, x" =x))
Since zn is drawn from continuous distribution, the event for E dar) occurs exactly when:
21

---

Published as a conference paper at ICLR 2026
1. Exactly of the zy 's lies in dr. Since xy p(-) and there are K such vectors, the probability contribution
K p((x) dr.
2. Given 2j E dr, the remaining K - vectors satisfy x. s sr 0. By independence,
P O)
P (xtx 0 0) for all illi +5) (Fo(x' 0)) 0)) K-1
Hence,
(px" E dx) = K p(z) (Fo(x' TO)) (Fo(xTo))**
k-1 dx.
which establishes
po(x) K p(x) (Fo(x (T)T) k
For the score function STe (-), taking logarithms yields
log (z log + logp(x) + (K-1) logFo(x ()).
Then
Vap(x) + 11) Fo(x 0) FxFolx 0).
V log
p(z)
Moreover, by the chain rule, V.Fo(xTg) polx T0) A. Thus,
vep(z)
p(z) + (K - 1) Po ()
V logpa(z)
Fo(x') 0.
and so
Vap(x) p(z)
(K - 1) Po(x T ()
Pu(x T 8)
ST (x)
0 = (p)x)) - -(K - 1)
fo ()
Fo 0)
This completes the proof.
Lemma F.3. Let X be a continuous random variable with probability density function px and cumulative distribution function Fx. For any constant e > O, define the random variable = cX with density py and CDF Fy. Then,
E py (V) E[px(x)²]
Proof. Since = cX has density
1 (y = px "
y
evaluating at cX yields:
(c -
Taking the expectation with respect to on both sides completes the proof:
E E(pr(()) = ((rr())) = 1 - [xx
22

---

Published as a conference paper at ICLR 2026
F.2 PROOF OF THEOREM 3.5
Proof. Based on our epoch schedule e; - (2' 1)To, 2 0. we can easily verify the length of each epoch denoted {ia satisfying that K; 6 6i-1 2T, Therefore, this result indicates that our epoch length follows an exponential growth pattern, specifically doubling each time. We denote #4 = Ex, (f'' 0.)). Since we know that the support of pt(+) is identical to that of the original p()), then if μr = 0 for any i = 1.2..... then based on Lemma E. we know that f()) is contant on the support of X 0, with X ~ p()) Therefore, the expected reward for all arms is fixed and we have the cumulative regret bound Rr = O. This indacates that our Theorem 3.5 simply holds. So for the rest of the proof, we will focus on the case that μ4 + 0 for any = 1, ........
At the beginning, we assume that the time horizon 7 exactly matches the end of some epoch H > 0. i.e. eн T. Hence we have that (2# - 1) To T.
the actually the density TTO, 0; where Vi...... YK are randomly sampled from D. Since we assume the arm set X,, 1 1, ....................... ... consisting of K random samples drawn from D, we can deduce that all the chosen arms at epoch i (1,,) follows the distribution with density function p: pz()), i.e.
Based on Lemma F.2 we have for i 2 2, p;(2) = K p(x)) F(
function of arg max u
{ai) 1-1 ~ Pa: i i= 1.2....
hold, and this indicates that we can use our Stein's ---mte-dd--aaste of 0; at each epoch. For pt, we know IES (X)) < M for all E [d] with X ~ according to Assumption 2.2] To bound the second moment of the score function for pi, i 1. Based on Lemma F2 we know that for i >
Theorem 3.1 to bound the error
5P(x)) - -K- (x(x0)) 0.- pe(x) = K p(x)) F,(x F((TT0)K=1 k1) (S (x)
Fx(x
Therefore, for X pt it holds that
(B(SP - =1/
V vap(x)²
p(r) Ky(x) TT 0. - do.
Vap(z)²
p(x)dx
< KM,
p(r)²
based on Assumption 2.3
On the other hand, we have that for ~ Pi and under K 3.
E
(K 1)2
Px 0,)2
|0.1 1 = (K (K-1)
10x=11/|0..1" K
Bi(TTO,32 p(x) T 0,) 0,) k
F((xT0,)2
K(K-- 1)² (8, 1| p:(x (axx00) 0,) p(x) Fi(x T0
K33
0
/ /pllTT0)) 0,)2 p(æ)dr
(8)
R3
10.1 Ey (pi(YT0.)² 0.)²)
Ey-p (YTT) is invariant to the scale of Ú, and hence based on Assumption 3.3 we know this term is actually bounded by some constant C. Therefore, it holds that
Based on Lemma F33
we can conclude that |0.1(-
(K- - 1)2 Px 0.)2 FX(T 0.)2
|0.1(-
E
C.C.
Consequently, for ~ pr(.), we have that
(K (K-1)2 Ps(x 0.)² F(( 0.)2
< (X)) 1 2E
1
00
KM + K²C = Mo.
23

---

Published as a conference paper at ICLR 2026
Furthermore, at epoch >>> 1, based on Theorem 3.1
we have that
8.11, |6:-011, - av
Mo log (2d/8)
R4-1
with probability at least 8. Taking the union we have that for all epoch 2,..., HI, we have
0. 00.-011, s sa Mo log (2d)og
Ri--
holds simultaneously with probability at least ō. Then at some time step t in epoch i, > 1, we have that
0l) -000)-((((())) - 1(x
Li 1e*
+
f
T t,
[xx
S f (
F
f
1 [
0.)
11
$ Lp 22
0.
+
Dg x2
1e
11
0
θ
$ Lp
|0r,
0.
+ Lgr 11azelox
0,
15
1e*
Le n
1 1000
0.
8
Lrp
|| 20
1e" 0. 0
Mo log (T))/))T)/0)
<dv
Ki-1
Therefore, with probability at least 1 - 5,
H
My log (2d (T)/o)
Rr $ 2L +
d
tim
Km-1
m=2
H
=o +
Σ m=
Fim-1 d / Mo log (2dlog, /Fmm
-LL/To +2 / /M log (2d log, (T)/6) VTo (V2) -
V2-1
s 2L + (2+ 2 / Mo log (2d (2dlog,
(2 -2)
s 2Ly + (2 22 / (MK + CKK log (2d log, (T)/8) VT
= 0 (To log (T)o)
where inequality (i) comes from Lemma F.I Finally, based on the choice of To. we have that
RT 0 (dk (ak'
VC-T log(dlog, (1)/6)) Ô [dk vT)
On the other hand, if the time horizon T does not match the end of an epoch. i.c. have some H such that éØ < T < eH41- Since we have that e, = (2 1)To. 2 O, which indicates that 6 > 20,t1, ' 0. Therefore, it holds that
cH+1 2eH 2T.
Therefore, it holds that
V RT 5 Begis =0 O (dk /EE4I log(dlog, (eH+1)/8)
0 (dk 22 (2T))
=0 (dk't /T log(d (T)
24

---

Published as a conference paper at ICLR 2026
And this concludes our proof.
Note that the final regret bound of order (r(VT) holds as long C' does not scale with T,, which naturally occurs as 7'' grows large. Consequently, Assumption 3.3 is not required to establish this nearly-optimal regret bound, and the final regret bound with C' becomes
Ry S O (Kk VC.T log log, (T)/6) = =O(Kk
However, as we emphasize in the main paper, assuming that C' is of constant scale is a very mild requirement, and in fact is satisfied by most practical distributions. For simplicity, adopt this assumption here, which we consider both natural and reasonable.
G PROOF OF THEOREM 3.7
The proof of Theorem 3.7 builds upon our previous proof of Theorem 3.1 and also relies on Lem- mas D.I D.3 which we introduced in Appendix D Notably, Lemma D.3 naturally extends to the high-dimensional single index model. However, to eliminate the dependency on in the final estima- tion bound, we incorporate an 1 -norm penalization in the loss function (Eqn. (T) and introduce novel technical approach.
Proof. Since minimizes the loss function in Eqn. that
TT. based on the property of sub-gradie babb-graieet it holds
VI(O)) + de = 0, where a {010@
Therefore, based widely known result (Boyd & Vandenberghe 2004) on the l norm, we have for any j E [d].
sign(0,), i E supp(0), E 11,11, i & supp(0).
where we denote supp(o) as the support of 0, i.e. supp = {j E [d] 8, * 0}. For some set V S [d] and vector v E Rd, we use uy to denote a d-dimensional vector whose jth entry is equal to "y if E V and O otherwise. For simplicity, we denote U = supp(0.) and 3 = - m_0 in the following proof, and we know that e = cU + ey= and the cardinality of U is s. Since L( is quadratic function for 0 e Rd. we have that
2 || (V) vL(u0))) 3 (-Xe- VL(H,O.))
S <- - -eeu)) & [+11 1181,
(9)
Due to the fact that ||oulloo I 1, holds that
-XeT = TEE S <A1188 1111Bu111
And based on the definitions above, we have that
-XeJo.B -xE 0-) - -x - - |00- -A
By combining the above results with Eqn. (9. holds that
2 213312 < - 11 || + VVVL(p...) baa 113
If we have A 2 Ills. then holds that
+ A
2 2|181| < A 11 11 + A || 11
||
2
X
< 113y 11 + A
1|
+
(1]
11 + |1 ll:)
A | |l + 3A
< -
11,
(10)
2
31
32
31
< 2
1
<
| ll
V8 <
v 111
2
2
25

---

Published as a conference paper at ICLR 2026
and the inequality (i) is due to Cauchy-Schwarz Schwarz inequality and [0]
Therefore, we have
31
|| - 4
V8
(11)
Moreover, due to the Equ. 10 we have that
1 +
2 |1 1 0,
which indicates that ||3 1 _ || ll Therefore, with Eqn. (TT) it holds that
||3||, 11: + || - 4 || 11 - | 1l2
v $ 4/ S 3As.
(12)
According to Lemma D33 by taking
3n(o² + + log (2d/6)
we have that with probability at least 1 - 8,
AV3
(o² + (7) log (2d/8)
VL(H,..)ll> S
2/2)
3
Therefore, by setting the same value for and taking
==11- M(a2 + 1.7) log(2d/0)
8833
M(a + 1.7) log(2d/)) + 4v2
2
n
3
n
then with probability at least - 5 we have X 2 2 VL( A-) 1l Finally, based on Eqn. we can deduce that
11 and
1 1.B. < - 3xv==0
3
| n.0.1, 33ds 331s= 0 (0)))
vn
H PROOF OF COROLLARY 3.8
consists two parts, where the first part the regret bound of Algorithm and the second part is the regret bound of Algorithm We will omit the detailed proof here since they are a simple combination of our deduced results above. Specifically, the proof of the first part is combination of results in Theorem 3.7 and the proof of Themrem 3.2] and the proof of the second part a combination of the results in Theorem 3.7 and the proof procedure of Theorem 3.5 And compared with the estimation error deduced under the low-dimensional case under Theorem 3.1 the estimation bound under the high-dimensional case under Theorem depends on the sparsity index instead of the dimension d in terms of the non-logarithmic factors. Therefore, the final regret bound will also be adjusted by replacing by s in the noo-looarith terms. In other words, if we ignore the logarithmic factors in the final regret bound, then the regret bounds will simply replace d by 8. And all the proof procedure can be identically reused under the high-dimensional sparse case. Therefore, will omit the detailed proof due to redundancy.
Proof. Corollary 3.8
For STOR, the value of s is used only to set the exploration phase length Ti. Even if we remove this dependence and set Ti free of s, we can still prove a regret bound of order (ss22/3), where the exponent of changes from 2/3 to 1.
I EXPLANATIONS ON ASSUMPTION 2.3
I.1 EQUIVALENCE BETWEEN || < L SETTING AND ||,,, < L SETTING
As we mentioned in Section 2 under Assumption 2.3 our main results hold regardless of the assumption types of the norms. Specifically, we have the following two types of assumptions:
26

---

Published as a conference paper at ICLR 2026
Condition I: ||0-112 |2,,, 1 L, Vt E [ [K] for some L > 0.
Condition II: ||0.1| 1, ||r, I L, At [T] . E [K] for some L > 0.
Note we set the l2 )norm as some constant for 0. due to the identifiability of the single index model. The former one is more commonly used in the contextual linear bandit literature (Abbasi Yadkori et al. 2011 Filippi et al., 2010), while we use the latter one in this work. As we explained, both of these two assumptions I based on Holder's 's inequality, and hence they are identical. And we use the latter one merely to keep consistent with the sparse linear bandit case in Section 3.4 where 1 norm is commonly assumed to be bounded. Furthermore, we will claim here our main Theorem 3.2 Theorem 3.5 and Theorem L.2 remain valid irrespective of the assumptions. In particular, the proof of Theorem 3.1 does not depend on the magnitude of f., ensuring that its bounds hold under both Condition and Condition II. Moreover, the final results of Theorem differ at most by constant factor under these conditions, indicating that the bounds remain valid as well. Second, for the regret bounds established in this work, such as Theorem 3.2 Theorem 3.5 and Theorem L.2 show that the same conclusions hold. As an illustrative example, we examine the proof of Theorem 3.2 in Appendix [.2]] as all regret analyses follow similar way on leveraging the estimation bound of the parameter. In its proof, use the estimation bound from 3.1 with Holder's inequality in Eqn. 7 Under condition II in our work, we have that
mainly used to ensure the inner product 0, can be bounded by
still hold: First, the estimation bounds presented in Theorem 3.1 and Theorem
8
S
2v3 3 +
M(o2 + (og((//))))
|
0,
V2
d
where M can be considered constant since each entry of 24,5 is in constant scale. Specifically, for Gaussian random variable N N(Ho, of), we can calculate that M = 1/06- On the other hand, if we have Condition I, then we should rewrite the above equation with
S
2v3 3
dM + 1.7) log log((d/)))
|| 2
0-
< 1
+ 2
1
Although the bound seems to improve by multiplier of vd explicitly, but here the value of M may not be a constant scale. Specifically, since we have ||ar,,lll is bounded by some constant L, then each entry will be bounded by the order 1/vd in magnitude on average. Assume the entry follows N (Ho, oz) with oî Q(1/vd), then it holds that M (dd). Therefore, with M Mdd), actually obtain the same bound of order Ö(d (d/5)/n) under Condition II. This identical argument can be used in the proof of all other Theorems with regret bounds, and hence we can conclude that the regret bounds the same under Condition I and Condition II.
1.2 DETAILS OF I. = Ō(1)
As we mentioned in the paragraph right after Assumption 2.3 we can actually let be in a constant scale up some logarithmic terms, i.e. L Ö(1) and our main theorems in this work will still hold. This enables us to work with a wider range of distributions such as any sub-Gaussian or Ex-ponennettal distributions, and we will explain why this holds. Since Sabb-aussian distribution is specific case of ExbEexxonettil, we will use the following Lemma I.1 to illustrate that L = Ö(1) with arbitrary high probability under exponnnnll D, and hence it will not contribute to the final regret bound after ignoring all logarithmic terms. We also assume zero mean for simplicity in the following lemma since the final bound will only differ by constant mean shift.
Let XI...., Xn be i..dd. zero-mean sub- sub-Expouue uub-Exponential random variables. Specifcially, suppose there exist positive constants and such that
Lemma L.1.
E[AAX.]
exp 2x²
for all [ 1
Then there is a constant c = ca v) for which, for every 0 < 1,
IP
max
[X,1 2 log < 5.
13i5
27

---

Published as a conference paper at ICLR 2026
Proof. By standard sub-exe uub-exponential tail estimate Vershynin 2018), there exist constants C1
depending only on a and such that for all 2 0,
P( 2 t) S 2eex (-a)
A union bound then shows
X 2t) S 2n exp expp-(E.)
max Isih
Choosing log(3 with sufficiently large absorbs and C1 inside the exponential, making the above probability at most 6. It holds that
IP
max [X,] 2 clog())) s 6,
as claimed.
This result indicates that with assuming D is any sub-Exponential distribution, we will get the same final regret bounds up logarithmic factors with high prohability.
EXPLANATIONS OF REMARK 3.4
In this section, we show that Assumption 3.3 is not restrictive and holds for many common distri- butions. In particular, support Remark we demonstrate that if the random vector X Rd is drawn from some multivariate normal distribution, then Assumption 3.3 is satisfied. Firstly, based on Lemma F33 we know that the value of EE (p.(X || is fixed regardless of the scale of v. In other words, to prove Assumption
3.3 it is equivalent to show that for any v with ||ul| 1, we have
B (X u)
|1
|
/D.(e" D.(xTT)pple v)) de S C.
Lemma J.1. Let X Rdd be random vector sampled from some d-dimensioanl multivariate normal distribution with expected value pxx E Rd and covariance matrix Ex E &Bdxd, And E Rd is arbitrary vector with ||il| O. Then we have Assumption 3.3 hold:
(po(X v)9) 110133 SC for some constant >>0 0,
where po(.) is the density of XTv.
Proof. Since X N(ux, Ex), the univariate random variable Y == T is itself normally distributed: Y ~ Nuxx, Exxx) Denote o² := = Ex > Then the density is
exp [)=)))))))
(t)
V2TT
20²
We must show that [T), (1) is finite. Since for every real t we have
1
(() S V2T
po(1)2 <
2T o²
Hence
(v)(1) < 1
2 o²
Taking expectations on both sides yields
E (Y)
S
2 < oc.
Since have that |/0] S ||l||2 1, take C
2 proving the claim.
28

---

Published as a conference paper at ICLR 2026
further conclude that Assumption 3.3 is satisfied once the density function of X is a bounded function, i.c. P.(.)= I C for some C > 0, then we naturally have that (((p.(X b) I C². Note this finiteness holds for most commonly used distributions, such as Gamma distribution [(k, 0) with
Based the above proof,
1, Laplace distribution, uniform distribution, etc.
Finally, If each entry of X is i..dd Gaossaassian and is unit vector, then Y -x is itself sub-Gaussian with the same tail parameter. In particular, this guarantees tail decay of the form
P(||> > r) I exp(-cr²) for some >
is noteworthy that the square density po(y)² inherits rapid decay (dominated by e- at in- finity ensuring its integrability. Near = O, standard Sub-Gaussian distributions also typically expects
avoid pathological density spikes, [p. remains well controlled. Consequently, E [ u to be finite for broad class of sub-Gaussian families. While exotic sub-Gaussian distributions with unbounded and non-integrable squared densities could theoretically violate this, such cases are very atypical in applied settings.
K K DEPENDENCY OF THBOREM 3.5 IN REMARK 3.6
Note that remove the term ((T= directly in the above proof in Eqn. 8 since it must be less than However, this very conservative step since F; 0,)K-1 is exponentially small and quickly converges to 0 under a large value of K. Therefore, our proof holds under worst cases, whereas the dependence on could be significantly improved under lots of common settings. For example, if Fz, is sampled from some d-dimensional normal distribution, then we can prove that
log K K²
E K p(X)2 F(X)K-3] -
K OC,
and this fact indicates that Mg is in the order of log (K) when K is large. Therefore, the final regret bound of Algorithm 2 exhibits an order of (V)T)) = O( (Tylo (K)), ) as established in our proof in Appendix F.2 by setting To to be any value such that Tu <
K) fog(2dlog, (T)/6).
In Lemma K. we provide a proof sketch under the standard normal assumption for simplicity, while noting that the asymptotic order remains unchanged for any normal distribution, regardless of its specific mean or variance.
Lemma K.1. Let X ~ NO0,,1, 1) be a standard normal random variable with probability density function p(z) - =2 and cunulative distribution function (CDF) F(z) (zz). For K > 3. the expectation
E [K
satisfies the asymptotic relation:
log K K2
E [K- ((X)K-(XXK-))) =
K oo.
Proof. The expectation can be expressed as:
1K K / p(1)) K- dx.
Under the substitution ((x). we transform the integral as:
1k lk= = K S. p ( 2 K-3 du.
To analyze the asymptotic behavior as K + oo, we first note that the dominant contribution the integral arises from values of near 1. For E [0,1- - 8) with fixed 5 E (0, the term u -3 decays exponentially as (1 5) and the squared density p (Φ ( is bounded by 1 2r Thus,
the integral over [0, 1 5] satisfies:
K 1-
(Φ (w))² K-3 du du K3 O 5))
29

---

Published as a conference paper at ICLR 2026
which is exponentially negligible compared any polynomial decay K goes to infinity.
For the dominant region u E [1 - 6, 1], let u = 1 - with t E [0, The inverse CDF satisfies the asymptotic expansion + 0+:
log (4T (1g()))))
i p1 (1 22ev22llgge (1og(1/t)
+ 0 log(1/t)
2 2 log((1/t
The density this point is:
v 4t (1/t) 1+0 (1og(1/1)) ))
( (1-)) 1))
nm
2m
which simplifies to:
p ( (1-t)) t)) tv 2 1++ (10g(1/)))
Squaring this gives:
-)))² (1=)))) 2t (1+0 (1Os(1/H))
1
Substituting (1 K3 33 x (K--3 and extending the upper limit co (with exponentially small error), we have:
Ik 2K / lolog(1/t)e -K- -K-3)r dt,
where ~ denotes asymptotic equivalence (exact leading term precision including constants). Using the substitution (K 3)t, the integral becomes:
2K
K - ds.
TK (K 3)3
2 llg
Expanding log (-3)) log K log + O(1/K), the dominant term is:
2K log K
000
4K log K
8e ds
(K 3)3
(K - 333
Since 1000 sde = 2, we obtain:
log K
log K
IK
θ
K +
K2
K2
Combining the negligible contribution from [0. 1 - 8) and the dominant term from [] 5, 1]. we conclude:
log K
E K p(x)x F(X)K-3
as K - oc.
K²
L DETAILS AND THEORY OF GSTOR
I.1 DETAILS OF GSTOR
In this part, we present the pseudocode of our proposed GSTOR in Algorithm As mentioned in Section 3.5 our GSTOR adopts double exploration-then-commiii strategy. Specifically, our algorithm uses Ti random samples to estimate the parameter 0, and obtain estimator (line 4). Afterward, we normalize the estimator and obtain 6 (line 5). Furthermore, we choose another independent set Ti samples. We leverage Og and the kernel regression to approximate the unknown function, and obtain the function predictor f (line 9). For the remaining rounds, we select the best arm greedily based the estimates (line 11).
30

---

Published as a conference paper at ICLR 2026
Algorithm 3 General Stein's s Oracle Single Index Bandit (GSTOR)
Input: T. the probability rate 6, parameters Ti, A, W.h
1: for t= 1 to Ti do
2: Pull arm 2, Xr uniformly randomly and observe the stochastic reward ye-
3: end for
4: Obtain the estimator & with {z,, Ui 3 based on Eqn. ①I
5: Get the normalized estimator On as 0 0/1 0||.
6: for /. Ti to 27) do
7: Pull an arm E Xe uniformly randomly and observe the stochastic reward ye.
8: end for
9: Approximate the unknown reward function f(-) with dg based on Eqn.
fo 2T + to T do
Choose the Ia = arg max fxx T 0g), break ties arbitrary.
12: end for
L.2 USEFCI. LEMMAS
We first prove that our normalized estimator 0g holds similar error bound the rate in Theorem 3.1
Lemma L.1. (Bound of SIM) Following the same notation of Theorem 3.1 For any single index Fn
model defined in with samples ,i, drawn from some distribution D with covariance matrix
Σx. Under Assumption 2.2 2.3 and the identifiability assumption that || |
|==²,,,,, 0- = 1, 1 > 0, by /3102 + M log(2d/5) and
solving the optimization problem in Eqn. ① with t
with the probability at least (1 28) it holds that
0
0. 8. 1| = (
d
|2//2
Note this result holds under general distributions D without the need for Gaussian design.
Proof. We start by controlling the difference between ||>> ||> and μua. When the dimension is low, the eigenvalues of Xx are bounded, and we denote Cmin and Cmax are two positive constants such that Cuin & Amiin (Ex) I Aunax (2x))= I Cmaxx Notably, for sufficiently large n, since
| 2,112 1, we have
| 2222 = ||=
E1/2 Σx u.B. + Ex2² MmBal1
μr ||> -H.0.)l1
2 vallE p., 1..0))12
2 p+ Vdv (av//axxl 10 pb 0z |12
(13)
2 p4 VdvCuma 10
0_ 0-11
p4 0 d
holds with probability at least - 8, where the triangle inequality gives the first inequality, the second
inequality comes from Cauchy-Schwarz, the third inequality is because of Amax (Ex) S Cmax- The
last two inequalities holds with the same probability as indicated by Theorem 3.1 Using the similar reason with the triangle inequlity for the other direction, have
E 22 < μ4, + Ō d3
3/c-
(14)
2
hold with probability least 1 8. Combining Eqn.
13
and
(4)
gives us the result that
| 011 n4 < δ
#4
(15)
n
2
31

---

Published as a conference paper at ICLR 2026
holds with probability at least - 28. We proceed with
i
0
|20
0.
|
011
|
0111
100 pe, 1-111
F4+ || 011 ||0-111
20 |
0
10 1r.0
p1. 2001 110
1 0011
||0X2011
10 pe, 1,,0-11
14+ 2211 Iva
2011
Cmiu /
d 2
d3
2vd
δ d² (
Vn tha
+
Cmin/!
where the third inequality comes from the fact that |10.11 S vdll0_12 S Vd.
Cmin
Vd 1 11 0.112
and Caiia
Vd_ and the last inequality is obtained after combining results of Theorem 3.1 and
Eqn.
15
L.3 KERNEL REGRESSION ERROR BOUND
We slightly abuse the notations for easy presentation in this section. Specifically, we use {y:, 24 )- to denote the samples for the kernel regression after the parameter estimation and normalization.
Theorem L.2. (Full Bound of SIM) We use pairs of samples obtain the normalized estimator Go based on Eqn. ( And we use another n pairs of samples {y:, v. 1= for the kernel regression with Op based on Eqn. (2). Assume that do = O(n). With M = 2//og(()) and = n -1/3
X~ D N(ux, Ex), we have
E B) f(X 0.)l 0
where the expectation taken with respect X and {z+, yi
Proof. The core of our analysis relies on decomposing the prediction error into approximation and statistical components. We first bound the deviation between the predicted and true rewards by separating the prediction error into controllable terms using novel indicator- based partitioning. We then apply Gaussian concentration incqualities to control tail events, and innovatively leverage Stein's method and perturbationn-stlee argument to precisely control the relationship between Z and Z*.
For notation simplicity, with E [ri]. we denote
z x 0., Zi x do. Z TO 0o. 2" = x==xxo To.
(16)
Based on Theorem L.1 and the assumption that de O(n), ), it holds that
|10 0.111 = On 1/3).
(17)
Notably, Z 20 (X (X-px)T Too 6o is random variable which follows the Gaussian distribution 0olla / &0
(0, 1) under our settings given in the assumption, then we get a tail bound for Z as
Z 1 0ol
< 2exp (-12/2).
(18)
| 0oll2
1Z-HI Bul
In other words, by letting = 2. 7i in Eqn.
18 with probability 1 1-2) 22/2,, we have
<
2 2vlog n. Since | 1/2 00112 < ||>;}/ 00lla holds almost surely, and ||>: 12/2000111 = 1 in our assumption, continue to have 1 1x 2 with the same high probability.
32

---

Published as a conference paper at ICLR 2026
Next, separate our & prediction error into two parts
B ( = -1((2) 1112-1880
1
[[(()) 1(2))
(12- (()
(19)
(I)
For term (II), by our definition of f()) given in Eqn. holds), and Assumption 2.3 have
2 (it 0 when the event {12 - -1x - W)
E f -12- S 1 (z- M
1 n²
For (I), we further separate it into (III) and (IV), which can be regarded as integrated mean (III) error and approximation error (IV) respectively. After defining the function g(=) EByl 2 2) for E I, we continue have
11) S E f(2) 9(Z) #112-HT0lsww
+ - f 11 - 2 sw]
(
(20)
(II)
(IV)
To handle the term (III), we define go(Z) [Z) as
Σ i= (z - 7z)
Oo(Z)
E Kn(Z Z.)
and we proceed to control (III) by
(mn) & [[(z) - 90 112 112--1z0 [w]
+ [o (Z) - [12
(21)
(VI)
Combining Eqn. 19 Eqn. 20 and Eqn. 21.. we can see that é prediction error can be bounded by the sum of (II), (IV), (V) and (VI). Next, we will bound these terms separately.
Step 1 (bound (IV)): According to the data distribution assumption, Z - follows N 03 O,) and 7' Ox follows NO,, Ex Moreover, for two random variables following normal distributions, there exists the general result that
xx 2/>01//00122///>
(X (X-xx) do
00Lx0. O.
Z" =x00 + 1| 0.112
C
00112112
222112
0,112 22202200012
// 12 201122
+ sin a 5). 7 7- -x
0x + | 12112
|
where a is real number within [0, m/2], and ( ~~ N(O, 1) is independent of Z. In addition, notice the equality that
|| [a||2||b|l2 ||||2||b||
(a,b) -[|aa]1 [1bl|2) l|a b12
2||a||2|b1]
and |||a||2 - |2| s I|a - bll2 for any real vectors a, E Rd. If we let Σ I!/20, 0 and 1 9, play the roles of and respectively, then by Eqn. [7 it holds that
|> 0,
0.13
C2 Chax
110 0.13
sin a <
<
| 00ll2 22 0.112
| 0 2 1 ll2
(22)
dC2 aC2aax100 110 - -0.11?
dC2 max 110u - - = O(dn" 3),
| Bolli //11111////// 1/22
0.
33

---

Published as a conference paper at ICLR 2026
where the third inequality comes from StuuchySchwarz inequality, and the last order equality comes from Eqn. 17 Thus, the single index model can be equivalently written as
- -x + +sina. 5) + 1IO..
f(Z)) tE, x = -112"00,111 0.112 cos
EE ll (o) + +x 2 - cosa.
1E ll2 (Z
For simplicity, we denote (()) = cos a
Ball2
(o) + 1x and according to the definition of g(=), we have
g(z) = Elyl Z = 2) = [((()) + |ス 0m sin a 5)] =
(23)
= = 5(7=)) | 2l2 sin a () Φ(C)dC,
where Φ the density of the standard normal distribution. It obvious that g(z) S T.f by Assumption To bound (IV), we first use
2.3
f( f2) to approximate f(Z*) as well as g()), then (IV) is bounded as
E - 12-
< F[(() 1
(24)
+ - - 2(²) [[2-~I
For the first term on the right side of Eqn. 24 by mean value theorem
= f(2 + | 0, sina f(2)
f + 1 (Z. () 2 0,112 sin a <) ||=X"00, 21 sin a Ç,
where (1, is constant between [0, depending Z and Ç. We continue have
[1(2)) - ((2))
[||z
/
100200,llssnn 1olu
(z 0. sin ()C((() dçdF(Z) (25)
$ ,1 0, sin O(Vdn -bdd
where the inequality is due to Assumption Eqn.
2.3
that f'(-) is bounded, and the last equality comes from //0.1la 1. For the second term the right side of we have
and Eqn. that 1E 0-
(22
Eqn.
24 by the dehmition of ((2) Eqn.
f(2) - -00) - f(2 + ||> 0. sin a <))(C)dC
=| 1/2 222 sin
f(Z + to (2 Ill|ssina C)Co(C)CC
where (2( is constant between [0, depending Z and ç, and this further implies that F(z-nn00lsm)
[()) ((Z))
00.122,ll /
/
12 /2-2-005ww
r(2+ sin s)s (()))(F(() (26)
=O(vdn- #)),
where the last equality is due Assumption 2.3 that f'(x) is bounded, Eqn. 17 that | 1.20.112 112 S | 0, and Eqn. (22).
Combining Eqn. (25) and Eqn. 26 give us that
(IV) O D(Vdn=b))
34

---

Published as a conference paper at ICLR 2026
Step 2 (bound (V)): For term (V), we have
(V) / 12-ug
/ E [1((z) - 20(22)) 21, Zn 2 dF Za)dF(2).
(1((1))-0(2)))
For any fixed Z, we let Bn (2) to be the event (nlPn(B( > 03, where Pr (B(,,)))
Di=1 (((z- then we further have
[f(()) 20( Zi. Zn, z $ E
(f(Z) - (o( Z,,..., Zno Z
im (yi (1.
E
Ii...., Zz, Z
Σ 11 (1Zi-Z|sh)
>
Var Van(Y:|Ze))ll 2. 21-21SM))
n²TP, (B,,,, h))²
nPP (Z,h)) T (z))
For the last inequality, we can further prove that Var(Y;|Z;) S E( $ 1. Specifically, by definition, we know that
V = =) E = 5 ((2(=)+ sin ()o(C) + 20 z 1,
where the last inequality holds since f is bounded and 0² is finite.
When conditional on Z. we have nlP,, nI (B(, = Σ 11, - ~ Binomial q). with q = i E BZZ IZ), and B(Z, h) represents the ball centered Z with the radius Thus,
when conditional on 2, we obtain
BB (2) n.Pr. (B(2, h))
/
(BP.,(((ZA))0)) dF Zn) S ng nP, (B(Z,))
dF(2),.... Zn)
where the last inequality follows from Lemma 4.1 in Györfi et al. (2006). We further get one upper bound for (V)
dF (V) S 1z- nP(Z ((Z,))lZ)
As (| 00 S W} is bounded area, we can choose 01 og such that (I - -1 S W} covered by R B(a,, h/2) with R < eW/h for some constant > Then we finally bound the term (V) as
dF(Z)
I/z)B(a.A/2))d dF())
(V)
17- nP(Z E (Z)
nP(Zi E B(2,h))2)
(27)
L12e dF
R
cW
Vlog(n) n²/3
nP(Zi E B(a,, h/2))
n nh
where the last inequality is due to the set that h x n 1/3
Step 3 (bound (VT)): We first showcase that function g(2) defined in Eqn. (33 is Lipschitz function, with Lipschitz constant bounded by the order of /d: for any 21, 22 E R. by the mean value theorem, we have
121/20.112 || 001lz
(g(3)) 9(22)) <
cos a
(22 21)
|| || 00.20.10 12 (22 21) ((())s
P' ((Z(z)) + / 22/ |12 sin () + ((C) cos
| 2./22/olb 00112
/20220012 22 21 Vdl 22 21 Lg S Vdl 22 =11-
2001200012
35

---

Published as a conference paper at ICLR 2026
where the second inequality uses the boundness of f(-) and f'(... and the third inequality utilizes
the fact that | 0. 222 < |2 0- Il = 1, and vdl x 0o ll2 2 | 20111 = 1. deal with term
(VI), we first bound the difference between go () and g(Z),
Ioo(Z) 9()) = [9b(Z))lBn12) 9 (Z)).
9 (Z))BBiz))
E (Z,)) K(Z)) Zi)
IB) + +Z(
Di=1 Kn(Z Zi)
S dh + ((Z)IB..())+
where the last inequality follows from the Lipschitzness of g()), which yields that & is Lipschitz function with the Lipschitz constant bounded by vd. We proceed to have
E [10((2) - -[( z- 2-1IB.EW
S vdh++ 1
g (2))6(B..22::12))((
< Voh++ + Tos
(1- E B(Z, (11
13 18-uubolSW
nLP(ZI E B(Z,A))Z) dF
s sddh+ Ly
exp(-nIP(2 E B(Z,N)))) nip(ZI B(Z,1))2
J 12-11b6lSW
2 vdh+ + sup {ue "} "E(0.1]
12-H4001SW J/2-0800lsw mP(2z E B(Z,)) dF(Z)
2 OVVvn
where the third inequality due to - x)" Se- for any x E [0.1]. and the last inequality comes from the fact that ( < 1 and the result in Eqn. (27). We finish the proof of the theorem.
L.4 PROOF THEOREM 3.9
First, note that the Gaussian distribution naturally follows Assumption 2.2 with constant M. And the proof of Theorem 3.1 only relies on the boundness of the unknown function f(-). Therefore, based on Theorem 3.1 and Lemma L.I it holds that
[ + L7) log(2d/0) =Ō
p--=0.1 p.O. 1, < 3d
d
00 m. =
Ti
VT.
VTT
Furthermore, we can deduce that d O(fi). Then based on Theorem L.2 for X D "(xxEEx) we have
d
F(x O
T
Since the arm at each round is randomly sampled from D, then we know that for any E [T], [K], it holds that
d
B - -(1
7
Then for any >>> 271, we have that
E (f(x 0x) f(x, f(xTo.)) = 0.) - ( (2T + E (f (IT,0) - f(xx 0.)
< R
((ITT.0.) 0.) - ()T.0)) + E (i(xT) 0)
f 0.)
T
36

---

Published as a conference paper at ICLR 2026
Table 1: Average running time (in seconds) of each method under different link functions in our simulations in Figure and real-data experiments in Table
Dataset
ESTOR
STOR
GSTOR
UCB-GLM
GLM-TSL.
LinUCB
LinTS
(1). Linear
0.69
0.20
0.79
0.39
0.71
(2). Poisson
0.72
0.26
0.81
131.24
364.89
(3). Square
0.76
0.28
0.89
249.01
707.95
(4). Five
0.76
0.29
0.91
1151.08
3276.35
Forest Cover
4.61
1.88
5.01
662.09
1512.92 121.35
3.64
3.39
Yahoo News
0.43
0.16
0.52
57.80
0.28
0.42
Cumulative Regret Sparse Linear
Cumulative Regret
Square
1750
Curulaaivve Regret
Curulaative Regret
2000
1250
1500
1000
LinUCB
1000
LinUCB
LinTS
LinTS
500
Lasso
500
Lasso
250
ESTOR
ESTOR
2000
4000
8000
2000
4000
8000
10000
Figure 2: Plot of regret of STOR, ESTOR, LinUCB, LinTS and DR Lasso under the sparse high- dimensional cases (left: identity reward function, right: square reward function).
Therefore, based on the choice of Ti we have that:
2T,
B(RT) - Σ [x(
S(; +
Σ 1=271+1
[[((x],0..) -((x 0.)]
d
T = 0 (dàTT))
S 2L
+
T
M EXPERIMENTAL DETAILS
M. ADDITIONAL DETAILS OF SIMULATIONS
We first report the hyperparameter configuration used in experiments. We use the false rate 5 = 0.05, the dimension d = 15 and the number of arms at each round K = 20. Each entry of the contextual vector i.i.d. sampled from standard normal distribution. In each of the 20 repetitions, the parameter vector 0_ is generated by independently sampling each entry from a standard normal distribution and then normalizing the vector to have an 4 norm equal to in accordance with our problem setting in Section 2 To ensure a fair comparison, we use the theoretically recommended values for key hyperparameters in each algorithm, such as the exploration rate for UCB-based methods, and parameters To. and Ti for our ESTOR and STOR algorithms. For each method, we conduct two sets of experiments by multiplying the key hyperparameters by and by 2, respectively. Each configuration is run over 20 repetitions, and we report the better regret curve over two different settings for each method. Specifically, for UCB-bare based methods such as Lin LCB and UCB-GLM the key hyperparameter is the exploration rate scaling the confidence bound. For TS-based methods, including LinTS and GLM-TSL, the key parameter is the variance multiplier of the posterior distribution, which plays role analogous the exploration rate in UCB by influencing the spread of the posterior
37

---

Published as a conference paper at ICLR 2026
distribution. For ESTOR, the main hyperparameter is the threshold value T; used in estimating the unknown parameter 0, We adopt the theoretical value T; /3(e4-1 e/-2)/ log(2d log, (2))6) and evaluate two versions of the algorithm using multipliers and 2 on Tú, respectively. We set To 50 since it can be any value less than bound in the theoretical result. For STOR, we consider the exploration phase length Ti as the key hyperparameter. Inspired by our theoretical analysis, we use the formula T1 = (dT))/3 2/3 (2d/))) /3 /8 and apply multipliers of and 2 to this value as well.
We also conducted experiments with GSTOR, but did not include its results in Figure ! that figure focuses on the monotone setting, where GSTOR, designed for general reward functions, is comparably less efficient. Instead, report GSTOR's performance along with all other implemented methods in Table 2 Compared to STOR, GSTOR performs slightly worse in the first three cases, likely because STOR avoids the additional exploration overhead required for reward function estimation, while GSTOR incurs some efficiency loss in that process. However, GSTOR clearly outperforms GLB-based algorithms under model misspecification, demonstrating its robustness across range of reward functions. Moreover, in the final case. GSTOR outperforms STOR, suggesting that when the reward function sufficiently complex, explicit estimation may improve overall approximation accuracy and lead to better performance.
We also report the average running time of different methods across the four cases in Figure I oovr 20 repetitions. All simulations were conducted on a machine equipped with the Apple M3 chip. Consistent with our time complexity analysis in section [.3] our proposed methods are significantly faster than the commonly used GLB algorithms. Specifically, STOR, ESTOR and GSTOR are all hundreds of times faster than their strong practical scalability. This efficiency stems from the fact that our methods avoid solving computationally intensive optimization problems at each iteration. Moreover, our methods exhibit stable running times across all settings. In contrast, the running times of UCB-GLM and GLM-TSL vary depending on the reward functions, which is due to the varying difficulty of solving their respective optimization problems. In summary, our methods are not only robust to unknown reward functions but also substantially more efficient than these state-of-the-art GLB algorithms.
and thousands of times faster than GLM-TSL, demonstrating
Furthermore, we evaluate the sparse high-dimensional setting (Section 3.4p by setting == 30, d = 60, and sparsity level r r= 10, where the indices of non-zero entries are sampled uniformly without replacement. We include the classic sparse linear bandit algorithm, DR Lasso Bandit (Kim & Paik 2 for a fair comparison. In the first plot of Figure 2 we consider the linear case with identity reward function; in the second plot, we adopt the same nonlinear square function f(x) sign(x)- x² + 2z used in our main experiments. Since LinUCB, LinTS, and DR Lasso Bandit are only designed for linear settings and face significant computational challenges under nonlinear rewards, we still fit them with linear reward model to assess their robustness under model misspecification.
All the hyperparameter configurations are the same the former simulations on low-dimensional settings. For the regularizer parameter À in Equ. (T]. we leverage its exact theoretical value deduced from Theorem 3.7 We showease the average cumulative regret over 20 repetitions in Figure 2 Compared to the low-dimensional results in Figure 1), our methods ESTOR and STOR outperform LinUCB and LinTS, and ESTOR in particular performs better than DR Lasso Bandit. Under the nonlinear square reward, all three baselines suffer from misspecification and exhibit linear regret growth, while our methods retain a sublinear regret curve with stronger performance. These results demonstrate that our algorithms are not only agnostic to the reward function and highly efficient, but also extend effectively to the sparse high-dimensional regime, maintaining robust and accurate performance.
M.2 ADDITIONAL. DETAILS OF WOAL- EXPERIMENT
For our real-world experiment, we use the Forest Cover Type dataset (Blackard 1998) from the UCI repository and the benchmark Yahoo Today Module dataset on news article recommendation (Chu et al. 2009). We approximate the arm feature vector distribution by fitting normal distribution using the estimated mean and covariance matrix from a small subset of the data, since our proposed methods further rely on the distribution of the feature vector. We will show that this approximation works effectively, as our methods demonstrate superior and consistent performance, highlighting their ro- bustness and efficiency in real-world applications. However, we do not provide theoretical guarantees
38

---

Published as a conference paper at ICLR 2026
Table 2: Average final cumulative regret of each method under different link functions in our simulations in Figure 1 For entries in the format a/b, the first value corresponds to the case where the model is correctly specified, while the second value represents performance under model misspecification.
Dataset
ESTOR
STOR
GSTOR
UCB-GLM
GLM-TSL
LinUCB
LinTS
Linear 289.37
571.62
604.45
309.35
405.21
Poisson
993.99
2036.94
2199.01
830.68
1148.02
Square
482.92
1331.41
1397.26
713.36/1314.54
875.12/1692.19
Five
198.51
611.11
519.18
136.14/415.05
213.87/648.23
Table 3: Results on the Forest Cover Type and the Yahoo news recommendation dataset.
Dataset
Metric
ESTOR
STOR
GSTOR
UCB-GLM
GLM-TSI.
LinUCB
LinTS
Forest
Regret
844.78
1101,28
1278.91 344.6
1497.39 255.6
2330.80
5506.45
4081.33
Yahoo
Reward
349.8
302.7
248.1
221.0
219.3
under this approximation for real- world applications, as the resulting error would introduce additional terms in the final regret bound. All the algorithmic settings and hyperparameter configurations are identical to the simulations presented above. The Forest Cover Type dataset consists 581,012 samples with 55 features. The label of cach instance denotes specific type of forest cover. Following the setup in Ding et al. (2021), we assign binary reward to each data point: a reward of 1 the point belongs to the first class (Spruce/Fir species), and otherwise. We extract feature vectors from the dataset and partition the data into K 32 clusters, each representing an arm. The reward of a cluster is defined as the proportion of data points within the cluster that have reward of 1. At every round, we sample feature vector randomly from each cluster to represent its observation. Table reports the average cumulative regret the final time step T 10,000, averaged over 10 independent runs. For GLB algorithms UCB-GI GCM and GLM-TSL, we adopt the logistic bandit setting for both, as this is the default and most common modeling assumption in binary reward scenarios. We report the average cumulative regrets of each method over repetitions in Table 3
The Yahoo news recommendation dataset comprises over 40 million user visits the Yahoo Today Module between May I and May 10, 2009. In each visit, the user is presented with a news article and chooses click (reward 1) or not click (reward 0). Both users and articles are represented by feature vectors of dimension 5 with additional constant feature, constructed via conjoint analysis with bilinear model (Chu al. 2009 Yi et al. 2024 2025). For our experiment, we discard article features and use data from May and May 2. 2009. Due to the heavy click response imbalance, we subsample the data by removing a portion of the non-click (reward 0) events. We set the time horizon T = 000, and each round, randomly select K 10 arms without replacement. For each method, we compute the total reward as the number clicks accumulated over the time horizon T' (higher values indicate better performance). Results are averaged over 10 independent runs and reported in Table 3 The average running time of each algorithm on these two real datasets is also displayed in Table
evident that all our proposed algorithms consistently outperform the other methods on both datasets. This strong performance stems from the fact that, in real-world settings, the true underlying link function is unknown and potentially complex. Unlike other methods, our methods do not rely on the explicit knowledge
the link function, again highlighting the advantage of adopting agnostic approaches in practice. In contrast, GLB methods require the reward function to be specified priori. While the logistic model is commonly used under the binary reward case, this choice inappropriate in many real-world applications, making such methods susceptible to model misspecification. It also worth noting that GSTOR demonstrates strong performance on both real-world datasets, particularly on the Yahoo News dataset. This suggests that the underlying reward function in the Yahoo setting may not exhibit a monotonic structure, making GSTOR's 's flexibility advantageous. In contrast, on the Forest Cover Type dataset, ESTOR and STOR outperform GSTOR, indicating that
39

---

Published as a conference paper at ICLR 2026
the reward function in this enviromment is likely monotonic. Nonetheless, all three proposed methods consistently outperform the GLB baselines across both datasets.
Moreover, although our methods assume knowledge of the covariate distribution for theoretical analysis, we approximate it using a normal distribution fitted from a small subset of the data in our real data experiments. The strong results obtained under this approximation further demonstrate the robustness and feasibility of our methods in real-world applications.
40


Reviews:
[{"review_id": "531RNQwa07", "reviewer": "Reviewer_2RuZ", "summary": "This paper investigates generalized linear bandits with unknown reward functions. The authors propose three algorithms that progressively handle increasingly general link functions. STOR addresses monotone functions using an ETC strategy, ESTOR achieves near-optimal regret through an epoch-based framework, and GSTOR extends the approach to arbitrary functions under Gaussian design. The paper explores sparse high-dimensional settings and leverages Stein’s identity to estimate model parameters without prior knowledge of the reward function. Extensive experiments validate the effectiveness of the proposed methods.", "questions": "1) How critical is the Gaussian design assumption in GSTOR? Could the analysis extend to sub-Gaussian or other distributions, or does it rely on properties unique to the Gaussian setting?\n2) Are the dependencies on $T, d, K$ optimal?\n3) Can the sparse variants adapt to unknown sparsity levels? How sensitive are the algorithms to misspecification of the sparsity parameter?\n4) Are there specific settings where realizability-based contextual bandits can outperform the single-index bandits?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1) This paper tackles a challenging and relatively unexplored generalized linear bandit setting in which the link function is unknown. \n2) It offers a hierarchical perspective on assumptions and algorithms, distinguishing between monotone and general link functions, to illustrate the trade-off between assumptions and regret. \n3) The proposed Stein’s estimator is new and conceptually clear, enabling efficient estimation of the underlying parameter without explicitly modeling the link function.", "weaknesses": "1) The monotonicity assumption is key to achieving near-optimal regret but remains restrictive. It would be helpful to discuss whether weaker conditions, e.g., local monotonicity or Lipschitz continuity, could still lead to meaningful results.\n2) The non-monotone case achieves $O(T^{3/4})$ rate is suboptimal. The dependence on the number of arms $K$ might be suboptimal.\n3) The analysis of sparsity is good but assumes knowledge of the true sparsity level.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XzBkS6RLhd", "reviewer": "Reviewer_Fk6c", "summary": "This paper introduces Single Index Bandits (SIB), extending generalized linear bandits (GLBs) to settings where the reward function $f$ is unknown. Note that GLBs require the link function, and misspecification in the link function can lead to linear regret. To address this, the authors propose a novel Stein's method-based estimator that achieves minimax-optimal error rates $O\\sqrt{d/n}$ without knowing $f$,  requiring only $O(nd)$ time complexity. For monotonically increasing $f$, they develop STOR (explore-then-commit), achieving $O(T^{2/3})$ regret and ESTOR (epoch-based), achieving near-optimal $O(\\sqrt{T})$ regret. The framework extends to sparse high-dimensional settings, replacing $d$ with sparsity $s$ in regret bounds. For general non-monotonic $f$, GSTOR employs kernel regression under Gaussian design, achieving $O(T^{3/4})$ regret. The Stein's estimator cleverly exploits $E[f(X^\\intercal \\theta^{\\star})S(X)] = E[f'(X^\\intercal \\theta^{\\star})]\\theta^{\\star}$ through integration by parts, using truncation to control variance. Experiments on synthetic and real datasets (Forest Cover, Yahoo News) demonstrate substantial improvements over GLB methods, with ESTOR/STOR running 100-1000x faster than UCB-GLM/GLM-TSL.", "questions": "1. The technical novelty is not clear to me. I actually went over the proof of Theorem 3.1 in the appendix. It uses the standard Holder's and Cauchy-Schwarz inequality. Relies on Lemma C.3, which follows directly from Steim's inequality and Bernstein's inequality. Where is the key technical challenge in this?\n2. One thing I am slightly confused about is that, to get rid of the knowledge of the link function, the authors mainly rely on the estimator and the quadratic loss function in eq (1), and that data is sampled from a fixed distribution D. Is this enough? Or are there some hidden assumptions I am missing?\n3. While theoretically sound, the STOR algorithm (which is an Explore-then-Commit algorithm) is quite impractical. Observe that, combined with Theorem 3.1, the first stage requires $O(dT^{2/3}$ samples. which is very large. Basically, to build the estimator itself, it takes two-thirds of the samples. Now, if you look into a stochastic bandit setting with no structure, the ETC algorithm takes $O\\sqrt{T}$ samples. Check Chapter 6 of https://tor-lattimore.com/downloads/book/book.pdf.\n4. The sparse high-dimensional setting only tests linear rewards; as such, testing against a synthetic complex f will enhance the paper.", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper tackles a fundamental limitation of GLBs - the known reward function (link function) assumption. By using an the Stein's method approach, they address this issue. The resulting estimator is both theoretically optimal (achieving minimax rates) and computationally efficient (closed-form solution requiring no optimization).\n2. The paper provides two algorithms, STOR, a simpler variant with uniform exploration, and ESTOR which is an epoch-based algorithm that balances exploration-exploitation. Finally, GSTOR, stated in the Appendix for non-monotonic functions, is the algorithm that tackles non-monotonic reward functions.\n3. Synthetic experimentation shows good performance against baselines.", "weaknesses": "1. To me, one of the main weaknesses of the paper is that it tries to pack too much stuff into the paper without going deep into one section.\n2. Following the previous comment, none of the theorems, technical novelty has been explained in detail.\n3. The sparse high-dimensional experiments only test linear rewards (not truly testing the unknown f capability), GSTOR evaluation is limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lpBARjPKWC", "reviewer": "Reviewer_vpkp", "summary": "This paper introduces and addresses the Single Index Bandit problem, a generalization of the Generalized Linear Bandit (GLB) framework. In a SIB, the expected reward is an unknown, potentially non-linear function $f$ of a linear predictor $x^\\top \\theta_*$, in contrast to GLBs which assume $f$ is known.  The authors propose a family of efficient algorithms based on a novel estimator derived from Stein's method, which avoids the need for complex optimization or a known link function.", "questions": "see the weaknesses.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The work directly addresses a critical and often unrealistic limitation (known link function) in the extensive GLB literature, making bandit algorithms significantly more robust to model misspecification.\n2. The paper is generally well-written and structured. The motivation is compelling, and the challenges of the problem are clearly explained, especially in contrasting with existing GLB and general contextual bandit approaches.", "weaknesses": "1. The analysis crucially relies on the assumption that the context vectors (arms) are i.i.d. from a fixed distribution. This is a significant limitation, as a large body of bandit literature deals with adversarially chosen arm sets. Why this assumption is needed?\n2. The worst-case regret bound of ESTOR exhibits a $K^{3/2}$ dependence on the number of arms, a limitation not present in prior work on heavy-tailed GLBs. Why this term exists? Is there any lower bound?\n3. This paper assumes $||\\theta_*||=1$, which is less common in contextual linear bandits. Why the norm bound on the parameter is needed?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "QnVIIy0HiY", "reviewer": "Reviewer_pAj9", "summary": "The paper studies generalized linear bandits (GLBs) with unknown reward functions, referred to as single index bandits (SIBs). This setting is analogous to single index models which generalize generalized linear models by allowing an unknown link function. The presence of an unknown reward function poses substantial theoretical challenges. The authors proposed a family of algorithms for the single index bandits, based on the Stein’s method: STOR and ESTOR for the case where the unknown reward function is monotonically increasing, and GSTOR for the case of general reward functions. The paper provides regret bounds for all proposed algorithms within this new problem setting.", "questions": "1.What is the fundamental difficulty in the arbitrary reward function setting that prevents the exponential epoch scheduling technique (used in ESTOR) from being effective?  \n2.Does the presented upper bound match any known lower bound in this setting? And what about the dependency on K?   \n3.Could the authors also include the performance of GSTOR in Figure 1 for a more complete empirical comparison across all proposed algorithms?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper makes a clear and original contribution by being the first to extend generalized linear bandits to the setting where the reward function is unknown. The authors carefully discuss the theoretical challenges that arise in this new formulation and emphasize that most of the popular GLB algorithms such as UCB-based methods cannot be directly applied.  To tackle with the challenges, the authors introduce new algorithms based on Stein’s method, which jointly estimate both the underlying parameter and the unknown link function. Notably, Among these, ESTOR achieves a near-optimal regret bound (optimal up to logarithmic factors) under the assumption of a monotone reward function. The paper further extends this approach to the sparse high-dimensional regime and to the general reward function setting. For the latter, the authors propose GSTOR, and prove regret guarantees under a Gaussian design assumption.", "weaknesses": "The presentation of the paper could be improved for clarity and intuition. Theorem 3.1 plays a central role across all three proposed algorithms, as the joint learning of both the parameter and the unknown link function is the core challenge of the new problem setup. However, little intuition is given for the minimization problem. It is hard to see how the bound in Theorem 3.1 contributes to the regret analysis that follows. It would be helpful if the authors highlighted where and how the unknown function is estimated within the algorithmic framework. Including a brief proof sketch for Theorem 3.1 and Theorem 3.5 would also improve understanding, especially regarding why the regret bound improves substantially in Theorem 3.5 through epoch scheduling.\n\nIn contrast, the sections on STOR and the sparse high-dimensional extension could be presented more concisely, as they are relatively straightforward once ESTOR is clear. The last section on arbitrary reward function is an exciting direction to expand on, but it is presented shortly. The regret bound for the general case is relatively weak, given it is formulated under Gaussian assumptions - It would strengthen the paper to elaborate on the notion of “fundamental unattainability” and to explain more clearly the need/necessity behind the double Etc strategy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)