- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper studies single index bandits. This is a sequential setting where a learner chooses an action , where is sampled from a nice distribution independently from for . The learner then observes , where is zero-mean subgaussian noise, satisfies , and is an unknown lipschitz function.
The authors provide a new algorithm with regret optimal in and a lower bound that indeed shows that the scaling in is optimal. The authors also provide experiments that show that the algorithm is also empirically better.
Critical strengths
The algorithm and corresponding upper bounds are simple and a nice way to tackle the problem setting. The lower bounds compliment these nicely.
Critical weaknesses
Frustratingly, the paper is difficult to read in too many places. I will list some of the places I had trouble with, but I would like to emphasize that since I am an emergency reviewer I did not take the time to list everything.
- In lines 169 to 172 there seem to be a contradiction around assumptions on . In one sentence there is a lower bound on but in the next there is not a lower bound. At this point I do not understand what is assumption that is used in the paper.
- In the derivation of Stein’s Identity p is used. However, I am not sure what p to use here: the distribution of x changes depending on the learner’s choices. However, it is not clear to me if we use just the distribution that generates or the distribution that depends on the learners choices, for example in which round the learner stops or do we just use the conditional distribution here?
- In line 261 there is the “with high probability ” appears to be unjustified.
- Assumptions 2 and 3 for no clear reason are not part of the setup and setting section (section 2) and are instead introduced only in section 4. This makes several parts of the paper hard to read.
- In lines 261-269 new notation is used but not explained. This is only explained in assumptions 2 and 3.
- And perhaps most frustratingly, big-O notation is used inconsistently. The comparison with prior literature is only in big-O notation. However, the paper ignores several crucial problem parameters when making this comparison in the introduction which do appear in for example Theorem 4.2. This makes it impossible for me to fairly compare to prior literature. I am also curious how the log factors appear in all the bounds.
The assumption on the norm of , i.e. seems is crucial in the derivation of the results and the design of the algorithm. However, the explanation of why this is a reasonable assumption is non-existent. The sentence “to ensure scaling we adopt the standard normalization (see Kang et al. (2025))” is the justification in section 2. However, this does not tell me why this is reasonable. So I went and looked at Kang et al. (2025) and the only explanation I found there was this sentence: “furthermore, we let for model identifiability”. This again does not explain to me why this is a reasonable assumption and consequently I do not believe this is a reasonable assumption.
The introduction motivates the setting by saying that assuming that f is known is a strong assumption and sometimes leads to problems due to misspecification. It is important to know here that for the known setting there are no assumptions on other than boundedness. Then the authors proceed by imposing several assumptions on how is generated. First, it is assumed that is sampled from some distribution. Second, this distribution needs to be nice, which seems to exclude fixed . Thirds, the distribution of needs to be known to the learner. In light of how the paper motivates the SIM bandit setting, I find it sort of problematic to impose all these additional assumptions on the problem to trade away one other assumption. Who is to say that misspecification problems don’t show up in specifying the distribution of . Furthermore, not allowing for fixed seems like a significant limitation.
To summarize, I think that the algorithm, lower bound, and upper bound are technically nice, but the writing can be considerably improved, the assumptions are highly limiting and in practical settings probably highly limiting, and the setting with all these assumptions is poorly motivated.
Questions for authors
I suppose I would like to hear a better motivation for the model and the assumptions that you make.
2 comments
Regret comparison and Model assumptions (Part 2)
Weakness. The comparison suppresses problem parameters, and the logarithmic dependence is unclear.
Our optimality claim concerns the horizon exponent in the stated regime. Kang et al.'s Theorem 3.9 gives expected regret under Gaussian design and . Our Corollary 4.3 gives . Thus, for fixed dimension and nonzero signal, the horizon exponent improves from to . Our displayed bound has a larger exponent of .
The logarithmic factors are stated explicitly alongside the finite-horizon bound in the restatement of Theorem 4.1 in Appendix C. Since our goal is to settle the horizon exponent up to logarithmic factors, we keep the main comparison at that level. Lines 369–375 (in blue) clarify signal dependence and point to the explicit bound.
Question. Why motivate the unknown link while requiring random contexts and a known context distribution? What about fixed contexts and distribution misspecification?
Single-index bandits extend the classical single-index model (SIM) into sequential decision-making. In SIM, both the parameter and the link are unknown. Specifying in advance gives the corresponding generalized linear model (GLM), in which the only unknown component is the parameter. Learning an unknown link introduces an additional nonparametric learning task. Estimators requiring a specified link cannot be applied directly, and their guarantees under general bounded contexts do not automatically extend to our setting.
Existing regret guarantees for single-index bandits also impose assumptions on context generation. Kang et al. (2025), Arya and Song (2025), and Ma and Cai (2025) study stochastic contexts with distributional regularity conditions in their respective formulations. Thus, studying the unknown-link problem under context assumptions follows an established approach. We have added this connection in lines 78–80 of the introduction.
Our work is most closely related to Kang et al. (2025). Their general-link algorithm GSTOR has a upper bound, and they explicitly ask whether a bound might be possible. We study the same stochastic-context formulation and settle its horizon-rate question. Moreover, their general-link theorem assumes Gaussian contexts, whereas ours permits the regular non-Gaussian distributions in Assumptions 2 and 3. We obtain regret for fixed dimension and nonzero signal. Theorem 5.1 shows that this exponent is unavoidable even with signal bounded away from zero, when .
-
Fixed and adversarial contexts. Known-link generalized linear bandit methods can handle contexts beyond our stochastic setting. Filippi et al. (2010) study fixed arm-feature vectors, and Sawarni et al. (2024) (Generalized Linear Bandits with Limited Adaptivity), allow adversarially chosen bounded feature vectors. These guarantees assume a known link. Our unknown-link setting includes an additional nonparametric learning task; our Stein estimator requires the stated stochastic-context assumptions and does not cover arbitrary deterministic or adversarial context sequences.
-
Practical relevance and unknown-distribution experiments. Requiring context assumptions does not make the formulation inherently impractical. Potential applications include recommendation, personalized treatment selection, and hyperparameter tuning, as discussed in our response to Reviewer
G4Wh. We have added the news recommendation example in lines 73–77. Knowing the score is also natural when candidate feature vectors are generated from a chosen distribution. For observational contexts, however, the known-score requirement is a substantive limitation. An incorrect score can bias the direction estimate. Section 2.1, line 232, states that the density must be known. Remark E.1, lines 1274–1278, explains that estimating the score introduces an additional approximation error. Appendix F.7 examines this practical issue using real context vectors from KDD99 and CoverType with synthetic rewards. Lines 1653–1656 explicitly identify this as a practical approximation and a robustness study beyond the exact known-score setting. These experiments provide empirical evidence that the method can be useful on real context data even when the context score is approximated, supporting the practical relevance of the formulation.
We hope these explanations resolve the concerns about the assumptions and their role in the analysis. We would appreciate reconsideration of the score in light of these clarifications.
Presentation, Identifiability, and Sampling Issues (Part 1)
We thank the reviewer for the detailed comments.
We agree that the previous ordering disrupted the reading flow. We have moved Assumptions 2 and 3 to Section 2 (lines 173–182). All critical parameters, including the score-moment condition, context-tail assumption, reward bounds, and Lipschitz bounds, are now fully defined before they are used by the estimator and algorithm.
The bound follows from the coordinatewise sub-Gaussian assumption and is proved in Lemma C.1. Taking a union bound over the d coordinates of all K candidates in all T rounds gives the stated bound with L=4κlog(8dTK/δ). We have added this explanation in lines 289–291, marked in blue, including the probability 1−δ/8.
In our setting, the expected reward is f(x⊤θ⋆). The learner must learn both the unknown weights θ⋆ and the unknown link f. Because both are unknown, their scales cannot be separated using only the observed rewards.
Consider the example where we multiply the true weights by a constant c>0 to obtain β=cθ⋆, and to compensate for this, we define a new link g(u)=f(u/c). If we calculate the expected reward using this new pair. g(x⊤β)=f(cx⊤(cθ⋆))=f(x⊤θ⋆). Both pairs (f,θ⋆) and (g,β) produce exactly the same expected reward for every context x. An algorithm therefore cannot uniquely identify their scales from rewards alone. We fix this ambiguity by requiring the absolute values of the weights to sum to one, namely ∥∣θ⋆∥∣1=1. The link's regularity bounds apply in this normalized representation. We use the ℓ1 norm because it also gives ∣x⊤θ⋆∣≤∥∣x∥∣∞, matching our coordinatewise context bound.
We have added this rescaling explanation in lines 188–194, marked in blue.
The core assumption is simply that the signal is not exactly zero, μ⋆=0. Positivity is a sign convention, not an additional restriction. The statement that μ⋆>0 is just a mathematical convention, not a restriction on the model. For example, if we multiply the weights by −1, we can compensate by reflecting the link, f(u)=f(−u). The expected reward remains unchanged: f(x⊤(−θ⋆))=f(x⊤θ⋆).
Reflecting the link also reverses its average slope, changing the signal from μ⋆ to −μ⋆. Thus, a model with negative signal has an equivalent representation with positive signal. This is why we take μ⋆>0 without loss of generality.
There is no contradiction with allowing arbitrarily small signals. Positivity chooses an orientation; it does not impose a uniform positive lower bound on the magnitude. The algorithm receives neither the signal nor such a lower bound. The revised statement in lines 195–199 makes this distinction explicit.
Here p is the density from which each candidate feature vector is drawn. The reviewer is right that choosing an arm based on its features can change the selected arm's distribution.
During Phase 1, however, we choose uniformly among the candidates, independently of their feature values. Conditional on the past, the selected feature vector therefore still has density p. The decision to continue exploring is also made before observing the next round's candidates.
The stopping time is data-dependent. Lemma B.1 gives an estimation bound simultaneously over all exploration sample sizes, allowing us to use it at the selected stopping time. Phase 2 observations update the bin rewards. We have clarified the density-preserving sampling step in lines 219–220, marked in blue.