- Rating
- 3(+1)
- Confidence
- 3
- Informativeness
- 2(+1)
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
- This work studies semiparametric generalized linear bandits with unobserved, time-varying common shifts. It proposes a localized elimination algorithm and provides a regret upper bound whose leading term is independent of global curvature, together with a lower bound matching its leading dependence on dimension and horizon.
Critical strengths
- This work extends the previous problem setting of semiparametric linear bandits to generalized linear bandits.
- This work shows that the previous approach in semiparametric linear bandits cannot be directly applied and suggests new technical tools to avoid this problem.
- This work shows matching upper and lower bounds on regret.
Critical weaknesses
- This work only considers a finite, fixed arm set, which seems restrictive. Also, such a setting calls for a comparison with adversarial bandit algorithms as baselines. See the questions below.
Questions for authors
- Previous works [1, 2] allow action features to vary every round. Could you elaborate on why your analysis focuses on the finite, fixed arm setting? Is this assumption essential to the algorithm, or is it just limitation and primarily needed for the current analysis?
- With a fixed, finite arm set, the optimal arm remains fixed across rounds in your setting. Thus, adversarial bandit algorithms such as EXP3 appear applicable to the Bernoulli experiments, and a comparison would be helpful. To my knowledge, classical results provide an expected regret bound [3], and there are also works providing high-probability guarantees [4] or expected regret [5]. Could you discuss how your algorithm compares with these adversarial bandit algorithms, both theoretically and empirically?
References:
[1] Krishnamurthy et al., "Semiparametric Contextual Bandits", ICML, 2018.
[2] Kim and Paik, "Contextual Multi-armed Bandit Algorithm for Semiparametric Reward Model", ICML, 2019.
[3] Auer et al., "The Nonstochastic Multiarmed Bandit Problem", SIAM Journal on Computing, 2002.
[4] Neu, "Explore no more: Improved high-probability regret bounds for non-stochastic bandits", NeurIPS, 2015.
[5] Zimmert and Seldin, "Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits", JMLR, 2021.
7 comments
Official Comment by Authors [2/3]
Why is the fixed-action setting still meaningful?
Even with fixed action features, nonlinear hidden shifts create a fundamental obstacle to directly applying semiparametric linear-bandit techniques (e.g., Krishnamurthy et al., 2018; Kim et al., 2025). In the additive linear model, centering the features yields the conditional moment , where is the centered feature covariance. In an SGLB, the corresponding moment is generally , where is an unknown covariance weighted by arm-dependent local slopes. Although centering removes the common reward level, the hidden shift still affects the unknown slopes . Consequently, applying the usual linear estimator introduces a systematic distortion that cannot generally be removed by collecting more samples or enlarging the confidence radius. Fixed features therefore do not make the nonlinear nuisance problem a direct extension of the linear case.
Our approach addresses this difficulty through a new combination of techniques:
-
Randomized comparisons followed by localization. Pairwise randomization produces comparisons whose signs remain valid despite changing shifts. Under the initialization-curvature condition, we use these comparisons to narrow the latent score range, making the local slopes approximately equal across active arms.
-
Separating unknown slopes from feature geometry. Within each localized phase, we keep the centered design covariance fixed. The first-order signal then accumulates as , where is the unknown local slope. This puts all arm comparisons on a common positive scale, allowing rankings to be learned without estimating the shifts or slopes.
-
Using optimal design to control nonlinear bias as well as noise. Centered optimal design ensures , controlling both stochastic estimation error and the amplification of the Taylor remainder under covariance inversion. When the score width satisfies , the nonlinear error in each comparison is bounded by , where and is the link's self-concordance constant. Localization makes small, so this error is only a small fraction of the comparison signal width , enabling safe elimination.
-
Observable stopping through the information–regret coupling. We replace confidence bounds involving the unknown accumulated slope with the observable radius , where is the estimated comparison width and is the stochastic confidence radius. The stopping condition certifies sufficient accuracy for elimination. Small slopes delay this condition but also shrink instantaneous reward gaps, which are bounded by a constant times . Thus, the same quantity controls both the comparison signal and phase regret; exploiting this coupling removes global inverse-curvature dependence from the leading regret term.
The technical contribution lies in how these ingredients work together: sign-preserving comparisons enable localization, localization and fixed design produce a common comparison scale, and observable stopping turns that structure into a regret guarantee. This combination resolves the nonlinear nuisance difficulty in the fixed-action setting and provides a substantive foundation for studying more general contextual extensions.
Official Comment by Authors [3/3]
Comparison with adversarial bandit algorithms.
Adversarial bandit algorithms such as EXP3 [1] and EXP3-IX [2] apply to our setting, but their regret guarantees scale less favorably with the number of arms . Our experiments also show substantially higher cumulative regret for EXP3 when is large.
-
Theoretical comparison. EXP3 [1] guarantees expected regret of , while EXP3-IX [2] provides a high-probability regret guarantee of . Both accommodate arbitrary reward sequences but do not exploit the shared feature structure. Our method exploits this structure despite the hidden nonlinear nuisance, achieving a high-probability leading regret of . Thus, the leading regret term depends primarily on the feature dimension, which is particularly advantageous when is large relative to . Although our bound includes a curvature-dependent initialization cost, this cost grows at most logarithmically with for fixed problem parameters. For sufficiently large horizons, the improved leading dependence can therefore yield a stronger guarantee. Our contribution is a dimension-dependent leading regret bound under nonlinear common shifts, without polynomial dependence on in the leading term.
-
Empirical comparison. We have added experiments comparing EXP3 with both LE-SGLB and a practical variant that requires neither nor an upper bound on it. Remark 4 and Appendix J provide a formal procedure with a fixed initialization budget of at most rounds and a regret guarantee that also covers insufficient localization. The practical implementation described in Appendix K follows this budget choice and is labeled “unknown ” below. Both versions achieve lower mean cumulative regret than EXP3 in all three configurations, with the gap widening as increases. The unknown- variant achieves the lowest mean regret throughout.
Table 1. Cumulative regret in the fixed-period logistic environment at (, , ). Values show mean (standard deviation). The lowest mean in each row is bold.
| EXP3 | LE-SGLB (Ours) | LE-SGLB, unknown (Ours) | |
|---|---|---|---|
| 20 | 1673.0 (270.7) | 731.0 (193.1) | 640.0 (219.6) |
| 100 | 4097.7 (714.6) | 1455.3 (228.4) | 826.8 (245.5) |
| 500 | 7060.8 (711.1) | 1886.4 (772.1) | 1131.7 (340.7) |
[1] Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. “The Nonstochastic Multiarmed Bandit Problem.” SIAM Journal on Computing, 32(1):48–77, 2002.
[2] Gergely Neu. “Explore no more: Improved high-probability regret bounds for non-stochastic bandits.” Advances in Neural Information Processing Systems, 28, 2015.
Official Comment by Authors [1/3]
We thank the reviewer for the thoughtful questions about the fixed-feature setting and the comparison with adversarial bandit methods. These comments prompted us to better explain the significance of our setting, clarify the challenges posed by varying features, and add theoretical and empirical comparisons with EXP3. This feedback has helped us present our contributions and position the paper more clearly.
Why do we assume fixed action features?
The main reason we assume fixed action features is that nonlinear hidden shifts can obstruct the transfer of information across contexts, even when observations are sufficient to learn comparisons within each previously observed context. Fixed features allow our method to build on persistent arm comparisons without resolving this ambiguity.
1. A nontrivial identifiability obstacle in SGLBs with varying action features.
Consider two possible logistic environments with fixed parameters θ(1)=(a,b) and θ(2)=(b,a), where a=log3 and b=log2. Let e1=(1,0) and e2=(0,1) be the standard basis vectors, and suppose the previously observed contexts offer either e1,−e1 or e2,−e2. These features span R2. In context ei,−ei, i∈1,2, set the hidden shift to zero if the parameter’s ith coordinate equals b; if it equals a, independently choose the shift uniformly from −c,c before drawing the current action, where c=arcosh(7/3). Since 21[σ(a+c)+σ(a−c)]=σ(b)=2/3, the two environments with parameters θ(1) and θ(2) induce exactly the same observable feedback distribution: in either context, choosing +ei yields a Bernoulli reward with mean 2/3, while choosing −ei yields mean 1/3. Consequently, no algorithm can distinguish the two environments using these contexts, regardless of how many samples it collects.
This indistinguishability matters because the two environments can require different optimal actions in a new context. To see this, suppose a new context offers v,−v, where v=(e1−e2)/2, with zero hidden shift. Since v⊤θ(1)=(a−b)/2>0 and v⊤θ(2)=−(a−b)/2<0, the optimal actions are opposite. Thus, even arbitrarily many observations from the previous contexts cannot determine the optimal action when this new context first appears.
2. Why the same ambiguity does not arise in the additive linear model.
In the corresponding additive linear model, observations from the previous contexts can distinguish the two environments and identify the optimal action in the new context. To see this, consider the same feature configurations under Yt=νt+xt,At⊤θ⋆+εt, with conditionally mean-zero noise. In context ei,−ei, choose xt,At=Btei using an independent uniform sign Bt∈−1,1 after the shift is selected. Under this uniform randomization, the mean feature is xˉt=21ei+21(−ei)=0, so the centered feature is xt,At−xˉt=Btei. Thus, BtYt is precisely the ith coordinate of the centered feature–reward product used in orthogonalized estimation for semiparametric contextual linear bandits (Krishnamurthy et al., 2018). Then E[BtYt∣Ft]=E[Btνt+Bt2θi⋆+Btεt∣Ft]=νtE[Bt∣Ft]+θi⋆+E[BtE[εt∣Ft,Bt]∣Ft]=θi⋆, where Ft includes the history, current context, and current shift before action randomization. The conditional mean of the signed reward therefore identifies the coordinate value itself, rather than only its sign. With sufficiently many randomized observations from each context, these coordinates can be estimated under standard bounded-moment conditions, distinguishing (a,b) from (b,a) and determining the sign of (e1−e2)⊤θ⋆ before the new context appears. In the logistic construction, by contrast, averaging over the hidden shift gives E[BtYt∣history, current context]=1/6 in both environments, and the entire observable feedback distribution is identical despite the different coordinate magnitudes.
The distinction is therefore about the information available in the observations, not merely the choice of estimator. Nonlinear hidden shifts can prevent past observations from identifying comparisons needed in a new context. This does not establish that learning with varying features is impossible or necessarily requires a worse regret rate. Fixed features allow our method to build on persistent arm comparisons without resolving this cross-context ambiguity.