acceptodds
Under review as a conference paper at ICLR 2027

Semiparametric Generalized Linear Bandits

Abstract

We study finite-armed semiparametric generalized linear bandits (SGLBs), where each arm's mean reward follows a generalized linear model with an unknown common shift that may vary arbitrarily over time. This model extends semiparametric linear bandits to nonlinear links, where standard feature centering no longer removes the common shift exactly. We propose Localized Elimination for Semiparametric GLBs (**LE-SGLB**), which progressively localizes the active arms and uses centered experimental design to eliminate suboptimal arms. **LE-SGLB** achieves a leading round-dependent regret of , up to initialization and lower-order terms, where is the feature dimension, is the number of arms, and is the horizon. Importantly, this leading term is free of the global inverse-curvature parameter and is independent of the magnitude and variation of the common shifts. For logistic SGLBs, we further prove an lower bound for , equivalently in this regime, matching the leading term of our upper bound up to logarithmic factors. Moreover, the lower bound remains even as grows to order , where denotes the inverse average slope of the logistic link at the optimal arm. Thus, the favorable local-curvature dependence of ordinary logistic bandits does not extend to SGLBs.

Primary area:
learning theory
Keywords:
Bandit, Generalized Linear Bandit, Semiparametric Bandit

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_9fBUOpenReview ↗
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 O(KTlog⁡K)O(\sqrt{KT\log K}) expected regret bound [3], and there are also works providing high-probability guarantees [4] or O(KT)O(\sqrt{KT}) 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
AuthorsOpenReview ↗

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)\theta^{(1)}=(a,b) and θ(2)=(b,a)\theta^{(2)}=(b,a), where a=log⁡3a=\log3 and b=log⁡2b=\log2. Let e1=(1,0)e_1=(1,0) and e2=(0,1)e_2=(0,1) be the standard basis vectors, and suppose the previously observed contexts offer either e1,−e1\\{e_1,-e_1\\} or e2,−e2\\{e_2,-e_2\\}. These features span R2\mathbb R^2. In context ei,−ei\\{e_i,-e_i\\}, i∈1,2i\in\\{1,2\\}, set the hidden shift to zero if the parameter’s iith coordinate equals bb; if it equals aa, independently choose the shift uniformly from −c,c\\{-c,c\\} before drawing the current action, where c=arcosh⁡(7/3)c=\operatorname{arcosh}(7/3). Since 12[σ(a+c)+σ(a−c)]=σ(b)=2/3\frac12[\sigma(a+c)+\sigma(a-c)]=\sigma(b)=2/3, the two environments with parameters θ(1)\theta^{(1)} and θ(2)\theta^{(2)} induce exactly the same observable feedback distribution: in either context, choosing +ei+e_i yields a Bernoulli reward with mean 2/32/3, while choosing −ei-e_i yields mean 1/31/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\\{v,-v\\}, where v=(e1−e2)/2v=(e_1-e_2)/\sqrt2, with zero hidden shift. Since v⊤θ(1)=(a−b)/2>0v^\top\theta^{(1)}=(a-b)/\sqrt2>0 and v⊤θ(2)=−(a−b)/2<0v^\top\theta^{(2)}=-(a-b)/\sqrt2<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⊤θ⋆+εtY_t=\nu_t+x_{t,A_t}^\top\theta^\star+\varepsilon_t, with conditionally mean-zero noise. In context ei,−ei\\{e_i,-e_i\\}, choose xt,At=Bteix_{t,A_t}=B_te_i using an independent uniform sign Bt∈−1,1B_t\in\\{-1,1\\} after the shift is selected. Under this uniform randomization, the mean feature is xˉt=12ei+12(−ei)=0\bar x_t=\frac12e_i+\frac12(-e_i)=0, so the centered feature is xt,At−xˉt=Bteix_{t,A_t}-\bar x_t=B_te_i. Thus, BtYtB_tY_t is precisely the iith 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[Bt E[εt∣Ft,Bt]∣Ft]=θi⋆\mathbb E[B_tY_t\mid\mathcal F_t]=\mathbb E[B_t\nu_t+B_t^2\theta_i^\star+B_t\varepsilon_t\mid\mathcal F_t]=\nu_t\mathbb E[B_t\mid\mathcal F_t]+\theta_i^\star+\mathbb E[B_t\,\mathbb E[\varepsilon_t\mid\mathcal F_t,B_t]\mid\mathcal F_t]=\theta_i^\star, where Ft\mathcal F_t 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)(a,b) from (b,a)(b,a) and determining the sign of (e1−e2)⊤θ⋆(e_1-e_2)^\top\theta^\star before the new context appears. In the logistic construction, by contrast, averaging over the hidden shift gives E[BtYt∣history, current context]=1/6\mathbb E[B_tY_t\mid\text{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.

AuthorsOpenReview ↗

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 Σθ⋆\Sigma\theta^\star, where Σ\Sigma is the centered feature covariance. In an SGLB, the corresponding moment is generally Htθ⋆H_t\theta^\star, where Ht:=∑ap(a)αt,azaza⊤H_t:=\sum_a p(a)\alpha_{t,a}z_az_a^\top 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 αt,a\alpha_{t,a}. 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 Σm\Sigma_m fixed. The first-order signal then accumulates as (∑tαt)Σmθ⋆(\sum_t\alpha_t)\Sigma_m\theta^\star, where αt\alpha_t 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 max⁡a∣zm,a∣Σm†2≤d\max_a\\|z_{m,a}\\|_{\Sigma_m^\dagger}^2\le d, controlling both stochastic estimation error and the amplification of the Taylor remainder under covariance inversion. When the score width satisfies W(Am)≤ρmW(\mathcal A_m)\le\rho_m, the nonlinear error in each comparison is bounded by ηmW(Am)∑s=1nαs\eta_m W(\mathcal A_m)\sum_{s=1}^n\alpha_s, where ηm:=2d (eRρm−1)\eta_m:=2\sqrt d\,(e^{R\rho_m}-1) and RR is the link's self-concordance constant. Localization makes ηm\eta_m small, so this error is only a small fraction of the comparison signal width W(Am)∑s=1nαsW(\mathcal A_m)\sum_{s=1}^n\alpha_s, enabling safe elimination.

  • Observable stopping through the information–regret coupling. We replace confidence bounds involving the unknown accumulated slope ∑s=1nαs\sum_{s=1}^n\alpha_s with the observable radius q^m(n):=(βm(n)+ηmG^m(n))/(1−ηm)\widehat q_m(n):=(\beta_m(n)+\eta_m\widehat G_m(n))/(1-\eta_m), where G^m(n)\widehat G_m(n) is the estimated comparison width and βm(n)\beta_m(n) is the stochastic confidence radius. The stopping condition G^m(n)≥64βm(n)\widehat G_m(n)\ge64\beta_m(n) certifies sufficient accuracy for elimination. Small slopes αs\alpha_s delay this condition but also shrink instantaneous reward gaps, which are bounded by a constant times αsW(Am)\alpha_s W(\mathcal A_m). Thus, the same quantity W(Am)∑s=1nαsW(\mathcal A_m)\sum_{s=1}^n\alpha_s 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.

AuthorsOpenReview ↗

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 KK. Our experiments also show substantially higher cumulative regret for EXP3 when KK is large.

  • Theoretical comparison. EXP3 [1] guarantees expected regret of O(KTlog⁡K)\mathcal O(\sqrt{KT\log K}), while EXP3-IX [2] provides a high-probability regret guarantee of O~(KT)\widetilde{\mathcal O}(\sqrt{KT}). 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 O~(dTmin⁡d,log⁡K)\widetilde{\mathcal O}(\sqrt{dT\min\\{d,\log K\\}}). Thus, the leading regret term depends primarily on the feature dimension, which is particularly advantageous when KK is large relative to dd. Although our bound includes a curvature-dependent initialization cost, this cost grows at most logarithmically with TT 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 KK in the leading term.

  • Empirical comparison. We have added experiments comparing EXP3 with both LE-SGLB and a practical variant that requires neither κinit\kappa_{\mathrm{init}} nor an upper bound on it. Remark 4 and Appendix J provide a formal procedure with a fixed initialization budget of at most ⌊T⌋\lfloor\sqrt T\rfloor 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 κinit\kappa_{\mathrm{init}}” below. Both versions achieve lower mean cumulative regret than EXP3 in all three configurations, with the gap widening as KK increases. The unknown-κinit\kappa_{\mathrm{init}} variant achieves the lowest mean regret throughout.

Table 1. Cumulative regret in the fixed-period logistic environment at T=30,000T=30{,}000 (d=5d=5, S=3S=3, B=5B=5). Values show mean (standard deviation). The lowest mean in each row is bold.

KKEXP3LE-SGLB (Ours)LE-SGLB, unknown κinit\kappa_{\mathrm{init}} (Ours)
201673.0 (270.7)731.0 (193.1)640.0 (219.6)
1004097.7 (714.6)1455.3 (228.4)826.8 (245.5)
5007060.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.

Reviewer_QrW2OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies finite-armed generalized linear bandits with an unobserved, time-varying common shift inside the link function. The shift can depend on the learner's sampling distribution, but is chosen before the sampled action. Since the link is increasing, the optimal arm remains fixed. LE-SGLB first localizes the latent arm scores under an initialization curvature condition, then uses centered experimental design and adaptive elimination to obtain a curvature-independent leading regret term. A logistic lower bound shows that hidden shifts can eliminate the favorable local-curvature dependence of ordinary logistic bandits. My main concerns are about the theoretical contribution.

Critical strengths
  1. The nonlinear nuisance creates a real obstacle to the centered-design approach: centering no longer removes the baseline. Controlling the relative linearization error and using the same accumulated slope to bound both information and regret are meaningful additions.
  2. Theorem 2 gives a concrete distinction from ordinary logistic bandits. Averaging over the hidden shift sign preserves a small mean sensitivity while making observable reward variance constant-order. The resulting lower bound holds at prescribed local-curvature levels. This is more informative than simply recovering a standard lower bound through a linear special case.
Critical weaknesses
  1. The upper-bound contribution is limited by an unresolved initialization bottleneck. The method builds on centered G-optimal design and local linearization. Its additions are the control of relative nonlinear error and an observable stopping rule that works with an unknown common scale. These are valid technical steps, but their applicability depends on Assumption 4: a known positive slope bound throughout initialization over the entire score interval. The algorithm does construct the localized set; it does not assume that set is supplied. Nevertheless, the information needed to reach the local regime is imposed, and the complete guarantee retains an initialization term of

    O~ ⁣(min⁡{κinit2Kd,  κinit4d9/2}).\widetilde O\!\left(\min\{\kappa_{\rm init}^{2}K\sqrt d,\;\kappa_{\rm init}^{4}d^{9/2}\}\right).

    This is consequential in the regime emphasized by the lower bound. In the Appendix G family, any valid initialization constant satisfies κinit≥κ0\kappa_{\rm init}\ge\kappa_0. At κ0≍T/d\kappa_0\asymp\sqrt T/d and K=2dK=2^d, the displayed full upper bound does not certify sublinear regret. This does not imply linear actual regret, but it limits the claimed optimality to the leading term, as the authors acknowledge. I find the resulting conditional extension insufficiently significant without a better understanding of the necessity or cost of the initial information condition.

  2. The lower bound establishes a narrow separation, whose significance is insufficient to carry the paper. Appendix G averages over hidden signs to obtain the observable Bernoulli mean

    qB(u)=12[σ(B+u)+σ(−B+u)],qB(0)=12,qB′(0)=α=1/κ0.q_B(u)=\tfrac12[\sigma(B+u)+\sigma(-B+u)],\qquad q_B(0)=\tfrac12,\quad q_B'(0)=\alpha=1/\kappa_0.

    In the small score interval used by the construction, this is locally a weak linear signal with constant-order observation variance. Rescaling the score by α\alpha exposes the familiar linear-bandit difficulty; the proof makes this precise through uniform derivative bounds and a hypercube KL argument. The additional result is that this difficulty can be embedded in a conditional logistic model at prescribed values of κ∗\kappa^*. I acknowledge that this disproves a direct transfer of the ordinary logistic curvature benefit. However, it does not establish a tight joint dependence on the curvature and initialization parameters, justify the necessity of the initialization condition, or identify a boundary between nuisance models that retain and lose that benefit. My concern is the limited conclusion, not the use of a constructed hard instance: such constructions are standard, and this one even yields an oblivious deterministic shift sequence. Taken together with the conditional upper bound, I do not find the theoretical increment sufficient for acceptance.

References

Questions for authors
  1. Is an initialization information condition necessary for a regret guarantee with favorable dimension dependence, or is it a limitation of first certifying latent-score localization? In which joint parameter regimes is the complete guarantee, including initialization, known to be optimal or materially stronger than existing baselines?
  2. Beyond showing that the conditional-curvature parameter κ∗\kappa^* is insufficient under unrestricted hidden shifts, what broader structural conclusion should be drawn from Theorem 2? Can its significance be connected to a principled boundary involving the observability or temporal structure of the nuisance?
5 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/4]

We thank the reviewer for the thoughtful comments on initialization and the structural implications of our lower bound. To address these concerns, we have sharpened the initialization bounds, introduced a new initialization procedure that requires no prior curvature knowledge, and strengthened our lower bound to establish an unavoidable curvature cost and characterize the transition between curvature-improved and variation-dominated regimes. The reviewer’s feedback has helped us substantially strengthen the paper.


Improved curvature dependence in initialization with known κinit\kappa_\text{init}

To address the reviewer's concerns about the high powers of κinit\kappa_{\mathrm{init}} in the initialization regret, we have replaced the previous refinements with sequential elimination and revised geometric localization in Remark 3 and Appendix I. These procedures change the respective regret bounds from O~(κinit2Kd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2K\sqrt d) to O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) and from O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) to O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), reducing the curvature dependence from quadratic to linear and from quartic to quadratic, respectively.

  • Sequential elimination: The previous successive-tournament initializer progressively reduced the active score width, but allocated a predetermined sample budget to each pairwise comparison within a stage. Its regret analysis charged every observation the maximum reward gap permitted by that stage's width. The revised initializer samples uniformly from the surviving arms, updates importance-weighted cumulative reward estimates after every observation, and removes arms once their estimated deficits exceed the confidence threshold. By controlling each arm's cumulative reward gap up to its last active round and accounting for the changing sampling probabilities, the new analysis gives regret O~(Kn+K)\widetilde{\mathcal O}(\sqrt{Kn}+K) over nn initialization rounds. Substituting the prescribed localization budget n=O~(κinit2Kd)n=\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2Kd) yields O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) regret. Thus, the worst-case localization budget remains quadratic in κinit\kappa_{\mathrm{init}}, while the initialization regret becomes linear.

  • Geometric initialization: The previous procedure compared fixed representatives of the bins and controlled the discrepancy between each representative and its bin's best arm through a worst-case approximation bound. Protecting the optimal arm therefore required bin widths that shrank inversely with κinit\kappa_{\mathrm{init}}. Since comparison sample complexity grows quadratically with inverse accuracy, this finer partition introduced an additional quadratic curvature factor. We instead run localized learners within the bins and account for their cumulative regret when selecting among bins. This allows bins to be certified at the target localization scale without the additional curvature-dependent refinement, replacing the previous O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) regret bound with O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), still without dependence on KK.

Both procedures use a known κinit\kappa_{\mathrm{init}}, and the learner selects the one with the smaller deterministic regret bound before interaction. The subsequent localized-elimination procedure and its leading regret guarantee remain unchanged.


New practical initialization with unknown κinit\kappa_{\mathrm{init}} and κinit\kappa_{\mathrm{init}}-independent T\sqrt{T} budget.

To address the reviewer's concerns about prior knowledge of κinit\kappa_{\mathrm{init}} and its role in determining the initialization length, we have added a new initialization procedure in Remark 4 and Appendix J. It takes neither κinit\kappa_{\mathrm{init}} nor an upper bound on it as input and always ends within ⌊T⌋\lfloor\sqrt T\rfloor rounds, making the algorithm more practical.

The procedure works as follows:

  • Tournament and filtering: We allocate at most ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds to fewer than 2K2K pairwise comparisons, each using ⌊T/(4K)⌋\lfloor\sqrt T/(4K)\rfloor observations. The comparisons use confidence thresholds that do not involve κinit\kappa_{\mathrm{init}}, and the resulting filtered set contains an optimal arm with high probability. If the per-comparison budget is zero, this step is skipped and all arms are kept.
  • Budget calculation: Without collecting additional observations, we compute the largest input on a doubling grid whose geometric initialization fits within the remaining ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds. This reserved budget is used only if geometric localization is selected; otherwise, we proceed directly to the main elimination phase.
AuthorsOpenReview ↗

Official Comment by Authors [2/4]

  • Optional geometric localization: To obtain a regret guarantee without polynomial dependence on KK, we optionally apply geometric localization using at most the reserved ⌊T/2⌋\lfloor\sqrt T/2\rfloor additional rounds, keeping the total initialization budget within ⌊T⌋\lfloor\sqrt T\rfloor.

Thus, the total warm-up budget is at most ⌊T⌋\lfloor\sqrt T\rfloor, with no additional factor involving KK, dd, or κinit\kappa_{\mathrm{init}}. The analysis also covers the case where this budget is insufficient to reach the target localization width: subsequent actions remain within the first filtered set, whose score width allows us to control the remaining regret.

With probability at least 1−δ1-\delta, the resulting algorithm satisfies RT=O~(dTmin⁡d,log⁡K+dmin⁡d,log⁡K+min⁡κinit4K2d3/2,κinit4d10)R_T=\tilde{\mathcal O}(\sqrt{dT\min\\{d,\log K\\}}+d\min\\{d,\log K\\}+\min\\{\kappa_{\mathrm{init}}^4K^2d^{3/2},\kappa_{\mathrm{init}}^4d^{10}\\}). The larger initialization cost term (the third term) accounts for the possibility that the T\sqrt T initialization budget is insufficient to guarantee localization. For example, geometric localization has a prescribed sample budget of NG=O~(κinit2d5)N_G=\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5). When curvature is known, the learner can allocate this budget to certify localization. The unknown-curvature procedure must instead end initialization within the prescribed cap T\sqrt{T}, potentially leaving an active set too wide for the usual localized-regret analysis to apply. In this case, the analysis must also control the regret incurred after initialization. We use the tirivial bound RT=O(T)R_T=\mathcal O(T), together with the fact that an insufficient budget implies T≲NG\sqrt T\lesssim N_G, and hence T≲NG2T\lesssim N_G^2, up to logarithmic factors. This gives the additive cost O~(κinit4d10)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{10}). Thus, the squared scale comes from controlling regret when localization is insufficient, rather than from spending more rounds on initialization; the initialization cap and the leading regret order remain unchanged.

More importantaly, our new practical unknown-curvature implementation using this budget achieves the lowest mean regret in all six settings reported below at d=5d=5 and K=20K=20, outperforming the original capped implementation.

Table 1. Cumulative regret at T=30,000T=30{,}000 (d=5d=5, K=20K=20, S=3S=3, B=5B=5). Values are reported as mean (standard deviation). The lowest mean regret is shown in bold.

LinkEnvironmentGLM-UCBGLOCRS-GLinCBOFU-ECOLogOFULog+BOSESemiparametric TSSBEGLB-OMDEXP3LE-SGLB (Ours)LE-SGLB, unknown κinit\kappa_{\mathrm{init}} (Ours)
LogisticFixed-period5170.7 (2158.1)4997.7 (2079.2)4813.5 (2224.1)5038.1 (1923.8)3899.0 (2929.1)4921.8 (2189.0)4351.5 (1738.5)4405.3 (2562.9)3242.8 (1457.3)1673.0 (270.7)731.0 (193.1)640.0 (219.6)
LogisticVariable-period5184.5 (2156.0)5012.2 (2076.9)4748.3 (2071.8)5077.3 (1924.3)3510.7 (3468.6)4939.0 (2186.3)4378.4 (1738.7)4415.2 (2552.2)3242.3 (1494.2)1660.1 (263.7)796.3 (237.7)690.0 (215.7)
LogisticAdversarial10258.0 (1746.7)10257.5 (1746.8)10278.5 (1881.5)10265.4 (1711.2)9455.1 (5409.7)10813.6 (1692.7)6899.0 (1354.9)8452.1 (2376.5)9776.8 (2176.7)2028.9 (165.9)1289.0 (429.5)682.9 (558.4)
ProbitFixed-period4296.2 (2297.9)4296.4 (2298.1)4083.5 (2373.9)——4106.1 (2313.0)3848.2 (2019.4)3719.0 (2526.8)1832.9 (1542.8)1586.8 (328.7)912.6 (449.1)697.4 (343.3)
ProbitVariable-period4316.1 (2296.5)4316.3 (2296.2)4125.1 (2330.5)——4129.1 (2308.8)3875.2 (2004.1)3734.7 (2515.4)1869.5 (1604.7)1589.7 (325.6)936.4 (471.9)714.1 (331.2)
ProbitAdversarial12119.9 (1542.3)12119.9 (1542.3)11955.3 (1715.8)——13042.5 (1709.8)7985.2 (1366.8)10545.2 (2396.4)12764.6 (2934.6)2197.0 (139.9)1292.9 (771.9)1259.9 (1527.9)

Improved Lower Bound

To address the reviewer’s concerns about the necessity of the initialization cost and the broader structural implications of Theorem 2, we have strengthened the lower bound to establish (1) an unavoidable nuisance-dependent (or κinit\kappa_{\mathrm{init}}-dependent) regret cost and (2) a boundary between curvature-improved and variation-dominated regimes in the lower bound, determined by the variation of the hidden shifts.

For the logistic link σ\sigma, define κS:=1/σ′(S)\kappa_S:=1/\sigma'(S) and κinit:=1/σ′(S+B)\kappa_{\mathrm{init}}:=1/\sigma'(S+B), where ∣xa⊤θ⋆∣≤S|x_a^\top\theta^\star|\le S and ∣νt∣≤B|\nu_t|\le B. The former captures nuisance-free curvature, whereas the latter also accounts for the nuisance magnitude. Define κ⋆:=(1T∑t=1Tσ′(νt+xa⋆⊤θ⋆))−1\kappa^\star:=(\frac1T\sum_{t=1}^T\sigma'(\nu_t+x_{a^\star}^{\top}\theta^\star))^{-1} as the reciprocal of the average optimal-arm slope, including the hidden shifts, and QT:=∑t=2T[σ(νt+xa⋆⊤θ⋆)−σ(νt−1+xa⋆⊤θ⋆)]2Q_T:=\sum_{t=2}^T[\sigma(\nu_t+x_{a^\star}^{\top}\theta^\star)-\sigma(\nu_{t-1}+x_{a^\star}^{\top}\theta^\star)]^2 as the temporal variation in the optimal arm’s mean reward.

AuthorsOpenReview ↗

Official Comment by Authors [3/4]

Under the conditions of the revised Theorem 2, with log⁡K=Θ(d)\log K=\Theta(d) and variation budget 4≤Qˉ≤T4\le\bar Q\le T, every policy incurs worst-case expected regret over the specified family with QT≤QˉQ_T\le\bar Q of at least Ω(max⁡min⁡Tκ⋆,κSQˉ,κinit,min⁡Tκ⋆,dTκ⋆+Qˉ)\Omega(\max\\{\min\\{\frac{T}{\kappa^\star},\kappa_S\sqrt{\bar Q},\kappa_{\mathrm{init}}\\},\min\\{\frac{T}{\kappa^\star},d\sqrt{\frac{T}{\kappa^\star}+\bar Q}\\}\\}).

This yields the following two corollaries.

1. Necessity of κinit\kappa_{\mathrm{init}}-dependent regret.

With unrestricted variation, Qˉ=T\bar Q=T, and a sufficiently large horizon T≳max⁡{κ⋆κinit,d2(κ⋆)2}T\gtrsim\max\{\kappa^\star\kappa_{\mathrm{init}},d^2(\kappa^\star)^2\}, the bound becomes E[RT]=Ω(max⁡{κinit,dT})\mathbb E[R_T]=\Omega(\max\{\kappa_{\mathrm{init}},d\sqrt T\}). Thus, a regret cost of order κinit\kappa_{\mathrm{init}} is unavoidable even for policies without an initialization phase. Here, κinit\kappa_{\mathrm{init}} is the smallest valid initialization-curvature bound, and it grows with the nuisance magnitude even when the nuisance-free curvature is fixed. This differs from conventional logistic bandit results (Abeille et al., 2021), where curvature-dependent costs involve nuisance-free quantities such as κS\kappa_S, which do not depend on the nuisance scale. This lower bound applies to every policy, including policies without an explicit initialization phase. Appendix G further identifies regimes where this cost dominates the dTd\sqrt T term. This directly addresses whether the initialization dependence reflects an inherent difficulty of the problem, while leaving the optimal joint dependence on κinit\kappa_{\mathrm{init}}, dd, and KK open.

2. Boundary between curvature-improved and variation-dominated regimes.

Our revised lower bound identifies a boundary between curvature-improved and variation-dominated regimes, clarifying when hidden nuisance variation can erase the curvature benefit familiar from standard logistic bandits. Specifically, Abeille et al. (2021) establish an instance-wise minimax lower bound of order Ω(dT/κGLB⋆)\Omega(d\sqrt{T/\kappa^\star_{\mathrm{GLB}}}), where κGLB⋆:=1/σ′(xa⋆⊤θ⋆)\kappa^\star_{\mathrm{GLB}}:=1/\sigma'(x_{a^\star}^{\top}\theta^\star). With κ⋆\kappa^\star now incorporating the hidden shifts, our result shows that, for sufficiently large horizons, the term dT/κ⋆+Qˉd\sqrt{T/\kappa^\star+\bar Q} in our lower bound transitions from the dT/κ⋆d\sqrt{T/\kappa^\star} scale to the dQˉd\sqrt{\bar Q} scale as the allowed nuisance variation increases, reaching dTd\sqrt T under unrestricted variation.

Whenever the horizon is large enough that T/κ⋆≳dT/κ⋆+QˉT/\kappa^\star\gtrsim d\sqrt{T/\kappa^\star+\bar Q}, this term exhibits two regimes:

  • Small variation: If Qˉ≲T/κ⋆\bar Q\lesssim T/\kappa^\star, its scale is dT/κ⋆d\sqrt{T/\kappa^\star}, matching the curvature-sensitive regret scale in standard logistic bandits.
  • Large variation: If Qˉ≳T/κ⋆\bar Q\gtrsim T/\kappa^\star, its scale is dQˉd\sqrt{\bar Q}. In particular, Qˉ=T\bar Q=T gives an Ω(dT)\Omega(d\sqrt T) lower bound when T≳d2(κ⋆)2T\gtrsim d^2(\kappa^\star)^2, precluding a uniform curvature improvement of the dTd\sqrt T term.

The boundary Qˉ≍T/κ⋆\bar Q\asymp T/\kappa^\star provides a quantitative connection between the lower bound and the temporal structure of the nuisance: even at the same average optimal-arm curvature, allowing greater hidden variation permits harder instances. We do not claim that QTQ_T is the unique or necessary measure of this structure. Rather, it provides a concrete way to quantify how nuisance variation can limit the curvature benefit. The broader conclusion is that optimal-arm curvature alone does not fully characterize the difficulty of the problem; the temporal structure of the hidden shifts also matters.


Sufficient condition for Assumption 4.

A simple sufficient condition is that the common shifts satisfy a finite bound ∣νt∣≤B|\nu_t|\le B during initialization. Since ∣xa⊤θ⋆∣≤S|x_a^\top\theta^\star|\le S, the argument of the link then lies in [−S−B,S+B][-S-B,S+B], and we can take κinit=(inf⁡∣z∣≤S+Bμ′(z))−1\kappa_{\mathrm{init}}=(\inf_{|z|\le S+B}\mu'(z))^{-1} whenever the infimum is positive. For the logistic link, this becomes κinit=1/σ′(S+B)\kappa_{\mathrm{init}}=1/\sigma'(S+B). Neither BB nor κinit\kappa_{\mathrm{init}} needs to be known under the revised assumption; a valid curvature value is supplied only to the known-curvature initializers. We have added this explanation immediately below Assumption 4.

Such bounded-range conditions are common in the standard GLB literature. For example, Faury et al. (2020) and Abeille et al. (2021) assume bounded action features and a known bound on the parameter norm. Our sufficient condition is analogous to these standard bounded-range assumptions, while being required only during initialization. It allows arbitrary temporal variation within the specified range; after initialization, neither a nuisance bound nor a uniform positive lower bound on the derivative is required. In this sense, we view it as a mild condition for obtaining the initial localization.

Reviewer_cKLhOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies finite-armed semiparametric generalized linear bandits (SGLBs) with time-varying common shift. Unlike in semiparametric linear bandits, ordinary feature centering does not remove the nuisance exactly because it appears inside a nonlinear link.

The authors introduce Localized Elimination for Semiparametric GLBs (LE-SGLB). They show the leading horizon-dependent term is independent of global inverse curvature, although initialization requires a curvature condition.

Critical strengths
  1. Meaningful theoretical novelty

  2. interesting information-regret coupling: After localization, a fixed design permits unknown per-round link slopes to accumulate as a common positive scale, preserving arm rankings.

  3. lower-bound construction: Theorem 2 shows that unobserved shifts can preserve order-one Bernoulli reward variance while attenuating differences between nearby parameter instances. This explains why favorable local-curvature dependence from ordinary logistic bandits need not extend to SGLBs.

Critical weaknesses
  1. Curvature-independent learning still requires potentially very expensive initialization. Assumption 4 is not properly motivated and is rather strong. Need comparison with GLB literature about the necessity of such an initialization assumption. It turns out that the analysis and the curvature independent result depends on this assumption. The kappa_init^2 Kd initialization term can be enormous (in the instances where the authors run experiments, this term is not small). The authors should discuss whether weaker initialization assumptions or fully adaptive alternatives are possible.

  2. Is it possible to compare with standard adversarial multi-armed bandit algorithms like EXP3. Comment on this.

  3. Role of G optiml design is not clear.

  4. Theorem 2 proves a tight leading d,T dependence in the special K=2^d hypercube regime. It does not establish tightness of the full upper bound for all K,d, nor of the initialization term. Statements about a 'matching lower bound' should retain this qualification.

Questions for authors

See weaknesses.

How does the 2,500-round capped initializer used experimentally relate to the formal localization guarantee?

How do cumulative regret and computation scale with K and d? How do the theory-prescribed, successive-tournament, and geometric initializers compare?

8 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/6]

We thank the reviewer for the insightful and constructive feedback. To address the main concerns, we have sharpened the initialization regret bounds, introduced a new procedure requiring no prior knowledge of κinit\kappa_{\mathrm{init}} and using at most ⌊T⌋\lfloor\sqrt T\rfloor initialization rounds, and expanded the experiments to include EXP3, the unknown-κinit\kappa_{\mathrm{init}} variant, and comparisons across different KK and dd. These revisions strengthen both the theoretical guarantees and the evidence for practical performance.


Regarding Assumption 4

Assumption 4 is a natural positive-slope condition for initialization, analogous to the regularity conditions used in the standard logistic and GLB literature (Faury et al., 2020; Abeille et al., 2021; Lee et al., 2024; Sawarni et al., 2024). Crucially, our new initialization procedure in Appendix J does not require knowing κinit\kappa_{\mathrm{init}}, while our revised lower bound (Theorem 2) shows that some regret dependence on the nuisance-dependent curvature parameter κinit\kappa_{\mathrm{init}} is unavoidable.

1. Prior knowledge of κinit\kappa_{\mathrm{init}} is unnecessary.

Our new initialization procedure in Remark 4 and Appendix J requires neither κinit\kappa_{\mathrm{init}} nor an upper bound on it as input and always terminates within ⌊T⌋\lfloor\sqrt T\rfloor rounds. Thus, the algorithm can operate without knowing the initialization-curvature bound, and its initialization budget is independent of that bound.

The procedure consists of three steps:

  • Tournament and filtering: We use at most ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds for pairwise comparisons with confidence thresholds independent of κinit\kappa_{\mathrm{init}}. The resulting candidate set contains an optimal arm with high probability; if the per-comparison budget is zero, this step is skipped and all arms are kept.
  • Budget calculation: Without collecting additional observations, we compute the largest candidate curvature bound on a doubling grid for which geometric localization fits within the remaining ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds.
  • Optional geometric localization: Based on the available localization guarantees, we either proceed directly to elimination or first perform geometric localization using the reserved budget. This geometric option provides a guarantee without polynomial dependence on KK.

The total initialization length is at most ⌊T⌋\lfloor\sqrt T\rfloor, and the regret bound preserves the original leading regret term at the expense of a larger additive term.

2. A positive-slope condition is natural and standard.

Standard logistic and GLB analyses also use a positive lower bound on the derivative over the relevant score range, either explicitly or through bounded features and parameters (Faury et al., 2020; Abeille et al., 2021; Sawarni et al., 2024). Assumption 4 applies the same type of condition to the score including the hidden common shift, and requires it only during initialization.

For example, if ∣νt∣≤B|\nu_t|\le B during initialization, then ∣xa⊤θ⋆∣≤S|x_a^\top\theta^\star|\le S implies that the link argument lies in [−S−B,S+B][-S-B,S+B]. We can therefore take κinit=(inf⁡∣z∣≤S+Bμ′(z))−1\kappa_{\mathrm{init}}=(\inf_{|z|\le S+B}\mu'(z))^{-1} whenever this infimum is positive. For the logistic link, positivity follows automatically on this bounded interval, giving κinit=1/σ′(S+B)\kappa_{\mathrm{init}}=1/\sigma'(S+B). We have added this explanation immediately below Assumption 4.

The role of this condition is to prevent arbitrarily weak comparison signals during localization: when the link is nearly flat, distinct latent scores can generate nearly indistinguishable observations, making their differences difficult to identify. The condition allows arbitrary variation of the shifts within the specified range. After initialization, our elimination analysis requires neither a nuisance bound nor a uniform positive lower bound on the derivative.

3. Our revised lower bound establishes an unavoidable nuisance-dependent cost.

Our revised Theorem 2 shows that our setting requires a regret cost of order κinit=1/σ′(S+B)\kappa_{\mathrm{init}}=1/\sigma'(S+B), which cannot be characterized solely by the nuisance-free curvature κS=1/σ′(S)\kappa_S=1/\sigma'(S) used in standard logistic and GLB analyses. Specifically, it establishes an Ω(κinit)\Omega(\kappa_{\mathrm{init}}) regret lower bound under its stated parameter and horizon conditions. Here, κinit\kappa_{\mathrm{init}} is the smallest valid initialization-curvature bound in the construction. It grows with the nuisance magnitude BB even when κS\kappa_S is fixed, demonstrating an additional statistical difficulty introduced by the hidden shifts.

This lower bound applies to every policy, including policies without an explicit initialization phase. Thus, some regret dependence on κinit\kappa_{\mathrm{init}} is unavoidable, although our new initialization procedure removes the need to know it in advance.

AuthorsOpenReview ↗

Official Comment by Authors [2/6]

Regarding initialization cost

We address the reviewer’s concerns about the large initialization term by providing an improved theoretical bound, a practical initialization procedure, and a new lower bound identifying the unavoidable curvature dependence. We also explain how curvature-dependent additive costs arise in standard logistic bandit and GLB guarantees.

1. Improved curvature dependence in initialization with known κinit\kappa_\text{init}

To address the reviewer's concerns about the high powers of κinit\kappa_{\mathrm{init}} in the initialization regret, we have replaced the previous refinements with sequential elimination and revised geometric localization in Remark 3 and Appendix I. These procedures change the respective regret bounds from O~(κinit2Kd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2K\sqrt d) to O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) and from O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) to O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), reducing the curvature dependence from quadratic to linear and from quartic to quadratic, respectively.

  • Sequential elimination: The previous successive-tournament initializer progressively reduced the active score width, but allocated a predetermined sample budget to each pairwise comparison within a stage. Its regret analysis charged every observation the maximum reward gap permitted by that stage's width. The revised initializer samples uniformly from the surviving arms, updates importance-weighted cumulative reward estimates after every observation, and removes arms once their estimated deficits exceed the confidence threshold. By controlling each arm's cumulative reward gap up to its last active round and accounting for the changing sampling probabilities, the new analysis gives regret O~(Kn+K)\widetilde{\mathcal O}(\sqrt{Kn}+K) over nn initialization rounds. Substituting the prescribed localization budget n=O~(κinit2Kd)n=\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2Kd) yields O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) regret. Thus, the worst-case localization budget remains quadratic in κinit\kappa_{\mathrm{init}}, while the initialization regret becomes linear.

  • Geometric initialization: The previous procedure compared fixed representatives of the bins and controlled the discrepancy between each representative and its bin's best arm through a worst-case approximation bound. Protecting the optimal arm therefore required bin widths that shrank inversely with κinit\kappa_{\mathrm{init}}. Since comparison sample complexity grows quadratically with inverse accuracy, this finer partition introduced an additional quadratic curvature factor. We instead run localized learners within the bins and account for their cumulative regret when selecting among bins. This allows bins to be certified at the target localization scale without the additional curvature-dependent refinement, replacing the previous O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) regret bound with O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), still without dependence on KK.

Both procedures use a known κinit\kappa_{\mathrm{init}}, and the learner selects the one with the smaller deterministic regret bound before interaction. The subsequent localized-elimination procedure and its leading regret guarantee remain unchanged.

2. Strong empirical performance of the practical initialization procedure without prior curvature knowledge.

Our new procedure in Remark 4 and Appendix J requires neither κinit\kappa_{\mathrm{init}} nor an upper bound on it and always terminates within ⌊T⌋\lfloor\sqrt T\rfloor rounds. It uses curvature-independent pairwise comparisons to filter the arms, followed by optional geometric localization within the remaining budget.

This addresses the practical concerns about prior knowledge and excessive initialization length. It preserves the original leading regret term, but has a larger additive term in its regret guarantee: capping initialization does not eliminate the cost of potentially incomplete localization. The practical unknown-curvature implementation achieves the lowest mean regret across all six settings reported below at d=5d=5 and K=20K=20, supporting its practical effectiveness.

AuthorsOpenReview ↗

Official Comment by Authors [3/6]

Table 1. Cumulative regret at T=30,000T=30{,}000 (d=5d=5, K=20K=20, S=3S=3, B=5B=5). Values are reported as mean (standard deviation). The lowest mean regret in each row is shown in bold.

LinkEnvironmentGLM-UCBGLOCRS-GLinCBOFU-ECOLogOFULog+BOSESemiparametric TSSBEGLB-OMDEXP3LE-SGLB (Ours)LE-SGLB, unknown κinit\kappa_{\mathrm{init}} (Ours)
LogisticFixed-period5170.7 (2158.1)4997.7 (2079.2)4813.5 (2224.1)5038.1 (1923.8)3899.0 (2929.1)4921.8 (2189.0)4351.5 (1738.5)4405.3 (2562.9)3242.8 (1457.3)1673.0 (270.7)731.0 (193.1)640.0 (219.6)
LogisticVariable-period5184.5 (2156.0)5012.2 (2076.9)4748.3 (2071.8)5077.3 (1924.3)3510.7 (3468.6)4939.0 (2186.3)4378.4 (1738.7)4415.2 (2552.2)3242.3 (1494.2)1660.1 (263.7)796.3 (237.7)690.0 (215.7)
LogisticAdversarial10258.0 (1746.7)10257.5 (1746.8)10278.5 (1881.5)10265.4 (1711.2)9455.1 (5409.7)10813.6 (1692.7)6899.0 (1354.9)8452.1 (2376.5)9776.8 (2176.7)2028.9 (165.9)1289.0 (429.5)682.9 (558.4)
ProbitFixed-period4296.2 (2297.9)4296.4 (2298.1)4083.5 (2373.9)——4106.1 (2313.0)3848.2 (2019.4)3719.0 (2526.8)1832.9 (1542.8)1586.8 (328.7)912.6 (449.1)697.4 (343.3)
ProbitVariable-period4316.1 (2296.5)4316.3 (2296.2)4125.1 (2330.5)——4129.1 (2308.8)3875.2 (2004.1)3734.7 (2515.4)1869.5 (1604.7)1589.7 (325.6)936.4 (471.9)714.1 (331.2)
ProbitAdversarial12119.9 (1542.3)12119.9 (1542.3)11955.3 (1715.8)——13042.5 (1709.8)7985.2 (1366.8)10545.2 (2396.4)12764.6 (2934.6)2197.0 (139.9)1292.9 (771.9)1259.9 (1527.9)

3. Curvature-dependent additive costs also arise in standard GLB results.

Similar results appear in the standard logistic and GLB literature, where optimal leading regret terms coexist with curvature-dependent additive costs. For example, in the fixed-arm logistic setting, Faury et al. (2022) and Sawarni et al. (2024) obtain bounds of the form O~(dT/κGLB⋆+κd2)\widetilde{\mathcal O}(d\sqrt{T/\kappa^\star_{\mathrm{GLB}}}+\kappa d^2), with other model-scale parameters fixed, where κGLB⋆=1/σ′(xa⋆⊤θ⋆)\kappa^\star_{\mathrm{GLB}}=1/\sigma'(x_{a^\star}^{\top}\theta^\star) and κ\kappa controls the minimum slope over the relevant domain. These additive costs are absorbed into the leading regret terms when T≳κ2d2κGLB⋆T\gtrsim\kappa^2d^2\kappa^\star_{\mathrm{GLB}}, up to logarithmic factors. Thus, a horizon requirement polynomial in curvature parameters also arises in these established guarantees.

Our revised sequential-elimination bound (in Remark 3 and Appendix I) now has linear curvature dependence, while the KK-independent geometric bound still has higher curvature and dimension dependence. We establish, to our best knowledge, the first complete regret guarantee for this semiparametric GLB setting without polynomial dependence on KK. Under the lower bound's stated conditions with log⁡K=Θ(d)\log K=\Theta(d) and unrestricted variation, the leading dimension and horizon dependence matches up to logarithmic factors; the complete guarantee matches when the improved additive cost is absorbed. We believe that establishing these guarantees under hidden, arbitrarily varying shifts, together with a practical initialization procedure requiring no prior curvature knowledge, constitutes a substantial contribution that merits acceptance. Sharpening the remaining curvature and dimension dependence of the KK-independent additive cost is an interesting direction for future work.


Comparison with adversarial multi-armed bandit algorithms

As suggested by the reviewer, we compare our method with EXP3 [1], which is applicable to our bounded-reward setting and guarantees expected regret O(KTlog⁡K)\mathcal O(\sqrt{KT\log K}). However, it treats the arms as unrelated and does not exploit their shared dd-dimensional feature structure. Our leading regret term is O~(dTmin⁡d,log⁡K)\widetilde{\mathcal O}(\sqrt{dT\min\\{d,\log K\\}}), offering a better dependence on the number of arms, particularly when KK is large relative to dd.

We have also added an empirical comparison with EXP3. As shown below, both versions of our algorithm achieve lower mean regret, and the performance gap widens as KK increases.

Table 2. Cumulative regret in the fixed-period logistic environment at T=30,000T=30{,}000 (d=5d=5, S=3S=3, B=5B=5). Values show mean (standard deviation). The lowest mean in each row is bold.

KKEXP3LE-SGLB (Ours)LE-SGLB, unknown κinit\kappa_{\mathrm{init}} (Ours)
201673.0 (270.7)731.0 (193.1)640.0 (219.6)
1004097.7 (714.6)1455.3 (228.4)826.8 (245.5)
5007060.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.

Reviewer_CiEHOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies stochastic bandits with a known nonlinear link and an unobserved, time-varying shift in the natural parameter. The shift is common across arms and may depend on the announced sampling distribution, but is chosen before the realized action. Monotonicity preserves the optimal arm, while the unknown shift prevents direct application of standard GLB estimation.

The proposed LE-SGLB algorithm first localizes the active arms, then combines a fixed centered experimental design within each phase, local linearization, and elimination based on observable confidence bounds. Its principal horizon-dependent regret term is \widetildeO!(dTmin⁡d,log⁡K)\widetildeO!\left(\sqrt{dT\min{d,\log K}}\right) with additional initialization and lower-order costs. A logistic lower bound establishes an (Ω(dT))(\Omega(d\sqrt T)) obstruction for (K=2^d) in the stated parameter regime, explaining why favorable dependence on optimal-arm curvature cannot generally be retained under hidden shifts. Synthetic logistic and probit experiments provide empirical validation, with probit serving as a robustness test outside the main theoretical assumptions.

Critical strengths
  1. A substantive extension of semiparametric bandit methods to nonlinear confounding. Placing the nuisance inside the link creates a meaningful obstacle: centering the features no longer removes the nuisance through an exact linear moment identity. The combination of localization and a fixed design within each phase addresses this obstacle by producing an approximately linear signal with an unknown positive common scale. The observable stopping and elimination rules then avoid needing to estimate that scale directly. This is a technically meaningful contribution beyond substituting a nonlinear link into an existing semiparametric algorithm.

  2. A lower bound that clarifies what robustness costs statistically. The logistic construction explains why the favorable curvature dependence available in ordinary logistic bandits cannot generally survive hidden shifts. Marginalizing over the hidden shift can leave substantial observation noise while reducing the sensitivity of the observable mean to the arm score. This complements the upper bound and strengthens the paper’s conceptual contribution. For exponentially many arms, the lower bound matches the leading dimension and horizon dependence of the upper bound, up to logarithmic factors and the separate initialization cost.

Critical weaknesses
  1. The initialization requirement limits the scope of the curvature-independent claim and leaves a gap between the theorem and the implementation. The main horizon-dependent term avoids inverse-curvature dependence, but initialization still requires a known lower bound on the link derivative during that stage. The basic initialization cost scales as (O~(κinit2Kd))(\widetilde O(\kappa_{\mathrm{init}}^2 Kd)); the improved appendix result reduces this dependence but can still be substantial. Consequently, the usefulness of the full bound depends on both the available prior information and the horizon needed to amortize initialization. This matters particularly because the experiments cap initialization at 2,500 rounds. Such a cap does not by itself establish the localization condition required by the subsequent proof. The practical modification is understandable, but its reliability should be measured explicitly so that readers can assess how closely the evaluated algorithm follows the theoretically analyzed one.

  2. The experiments demonstrate promising robustness but provide limited evidence about the source and scaling of the gains. The principal experiments use a relatively small fixed problem size, (K=20) and (d=5). They therefore provide limited evidence for the finite-arm and dimension dependence highlighted by the theory. Moreover, several baselines do not model the same nonlinear nuisance, so the observed advantage reflects both model robustness and algorithm design. The current comparisons do not sufficiently separate the effects of initialization, localized estimation, and the stopping/elimination rules. A controlled comparison with the closest centered-design predecessor, together with targeted ablations and variation in (K) and (d), would make the empirical contribution more convincing. This is especially relevant given the capped initialization and environment-specific tuning used in the experiments.

Questions for authors

Initialization assumptions and cost. For the experimental instances, what value of κinit\kappa_{\mathrm{init}} is used, and what information about the unobserved shifts makes that value available to the learner? How does the resulting theoretical initialization budget compare with the 2,500-round cap and the total horizon?

4 comments
AuthorsOpenReview ↗

Official Comment by Authors [1/4]

We sincerely thank the reviewer for the time and care devoted to reviewing our paper and for the constructive feedback. To address the concerns about initialization assumptions and cost, we have sharpened the initialization bounds and introduced a formally analyzed procedure that requires no prior curvature knowledge and uses at most ⌊T⌋\lfloor\sqrt T\rfloor initialization rounds. We have also expanded the experiments across different KK and dd, including comparisons with EXP3 and the new initialization variant. The reviewer’s feedback has helped us strengthen both the theory and the empirical evidence supporting our method.


New practical initialization with unknown κinit\kappa_{\mathrm{init}} and a curvature-independent T\sqrt T budget.

To address the reviewer's concerns about prior knowledge of κinit\kappa_{\mathrm{init}} and its role in determining the initialization length, we have added a new initialization procedure in Remark 4 and Appendix J. It requires neither κinit\kappa_{\mathrm{init}} nor an upper bound on it and always terminates within ⌊T⌋\lfloor\sqrt T\rfloor rounds. Crucially, its analysis also covers cases where this budget is insufficient to achieve the target localization, directly addressing the gap between a prescribed initialization cap and the formal localization guarantee.

The procedure works as follows:

  • Tournament and filtering: We allocate at most ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds to fewer than 2K2K pairwise comparisons, each using ⌊T/(4K)⌋\lfloor\sqrt T/(4K)\rfloor observations. The confidence thresholds do not involve κinit\kappa_{\mathrm{init}}, and the resulting filtered set contains an optimal arm with high probability. If the per-comparison budget is zero, this step is skipped and all arms are kept.
  • Budget calculation: Without collecting additional observations, we compute the largest candidate curvature parameter on a doubling grid for which geometric initialization fits within the reserved ⌊T/2⌋\lfloor\sqrt T/2\rfloor rounds.
  • Optional geometric localization: When selected, geometric localization uses at most this reserved budget, providing an alternative regret guarantee without polynomial dependence on KK. Otherwise, the algorithm proceeds directly to the main elimination phase.

Thus, the total initialization budget is at most ⌊T⌋\lfloor\sqrt T\rfloor, with no additional factor involving KK, dd, or κinit\kappa_{\mathrm{init}}. If this budget is insufficient for the target localization, subsequent actions still remain within the first filtered set, whose score width allows us to control the remaining regret.

Under the stated assumptions, with probability at least 1−δ1-\delta, the resulting algorithm satisfies RT=O~(dTmin⁡d,log⁡K+dmin⁡d,log⁡K+min⁡κinit4K2d3/2,κinit4d10)R_T=\widetilde{\mathcal O}(\sqrt{dT\min\\{d,\log K\\}}+d\min\\{d,\log K\\}+\min\\{\kappa_{\mathrm{init}}^4K^2d^{3/2},\kappa_{\mathrm{init}}^4d^{10}\\}). The initialization-curvature condition remains part of the analysis, but its value is no longer an algorithm input. The larger additive term accounts for regret incurred after initialization when the short budget does not guarantee localization. For example, the prescribed geometric localization budget is NG=O~(κinit2d5)N_G=\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5). With known curvature, the learner can allocate this budget to certify localization; under the T\sqrt T cap, initialization may end before this guarantee is available. In the insufficient-budget regime, T≲NG\sqrt T\lesssim N_G implies T≲NG2T\lesssim N_G^2, up to logarithmic factors. Here, TT is the total horizon, so the trivial bound RT=O(T)R_T=\mathcal O(T) controls the entire interaction, including the rounds after initialization, and yields the additive cost O~(κinit4d10)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{10}). Thus, this larger term covers the consequences of insufficient localization, while the actual initialization remains capped at ⌊T⌋\lfloor\sqrt T\rfloor rounds and the leading regret order is unchanged.

We also evaluate the practical unknown-κinit\kappa_{\mathrm{init}} implementation using this budget, as described in Appendix K. As shown below, it achieves the lowest mean cumulative regret among the compared methods in all six settings at d=5d=5 and K=20K=20, improving on the original initialization. At our experimental horizon T=30,000T=30{,}000, its initialization budget is at most ⌊30,000⌋=173\lfloor\sqrt{30{,}000}\rfloor=173 rounds, substantially below the original 2,500-round cap.

AuthorsOpenReview ↗

Official Comment by Authors [2/4]

Table 1. Cumulative regret at T=30,000T=30{,}000 (d=5d=5, K=20K=20, S=3S=3, B=5B=5). Values are reported as mean (standard deviation). The lowest mean regret in each row is shown in bold.

LinkEnvironmentGLM-UCBGLOCRS-GLinCBOFU-ECOLogOFULog+BOSESemiparametric TSSBEGLB-OMDEXP3LE-SGLB (Ours)LE-SGLB, unknown κinit\kappa_{\mathrm{init}} (Ours)
LogisticFixed-period5170.7 (2158.1)4997.7 (2079.2)4813.5 (2224.1)5038.1 (1923.8)3899.0 (2929.1)4921.8 (2189.0)4351.5 (1738.5)4405.3 (2562.9)3242.8 (1457.3)1673.0 (270.7)731.0 (193.1)640.0 (219.6)
LogisticVariable-period5184.5 (2156.0)5012.2 (2076.9)4748.3 (2071.8)5077.3 (1924.3)3510.7 (3468.6)4939.0 (2186.3)4378.4 (1738.7)4415.2 (2552.2)3242.3 (1494.2)1660.1 (263.7)796.3 (237.7)690.0 (215.7)
LogisticAdversarial10258.0 (1746.7)10257.5 (1746.8)10278.5 (1881.5)10265.4 (1711.2)9455.1 (5409.7)10813.6 (1692.7)6899.0 (1354.9)8452.1 (2376.5)9776.8 (2176.7)2028.9 (165.9)1289.0 (429.5)682.9 (558.4)
ProbitFixed-period4296.2 (2297.9)4296.4 (2298.1)4083.5 (2373.9)——4106.1 (2313.0)3848.2 (2019.4)3719.0 (2526.8)1832.9 (1542.8)1586.8 (328.7)912.6 (449.1)697.4 (343.3)
ProbitVariable-period4316.1 (2296.5)4316.3 (2296.2)4125.1 (2330.5)——4129.1 (2308.8)3875.2 (2004.1)3734.7 (2515.4)1869.5 (1604.7)1589.7 (325.6)936.4 (471.9)714.1 (331.2)
ProbitAdversarial12119.9 (1542.3)12119.9 (1542.3)11955.3 (1715.8)——13042.5 (1709.8)7985.2 (1366.8)10545.2 (2396.4)12764.6 (2934.6)2197.0 (139.9)1292.9 (771.9)1259.9 (1527.9)

We hope that this new procedure and its empirical evaluation help address the reviewer’s concerns about initialization. Developing initialization methods that combine further practical improvements with tighter curvature-dependent regret guarantees remains an important direction for future work.


Improved curvature dependence in initialization with known κinit\kappa_\text{init}

To address the reviewer's concerns about the high powers of κinit\kappa_{\mathrm{init}} in the initialization regret, we have replaced the previous refinements with sequential elimination and revised geometric localization in Remark 3 and Appendix I. These procedures change the respective regret bounds from O~(κinit2Kd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2K\sqrt d) to O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) and from O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) to O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), reducing the curvature dependence from quadratic to linear and from quartic to quadratic, respectively.

  • Sequential elimination: The previous successive-tournament initializer progressively reduced the active score width, but allocated a predetermined sample budget to each pairwise comparison within a stage. Its regret analysis charged every observation the maximum reward gap permitted by that stage's width. The revised initializer samples uniformly from the surviving arms, updates importance-weighted cumulative reward estimates after every observation, and removes arms once their estimated deficits exceed the confidence threshold. By controlling each arm's cumulative reward gap up to its last active round and accounting for the changing sampling probabilities, the new analysis gives regret O~(Kn+K)\widetilde{\mathcal O}(\sqrt{Kn}+K) over nn initialization rounds. Substituting the prescribed localization budget n=O~(κinit2Kd)n=\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2Kd) yields O~(κinitKd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}K\sqrt d) regret. Thus, the worst-case localization budget remains quadratic in κinit\kappa_{\mathrm{init}}, while the initialization regret becomes linear.

  • Geometric initialization: The previous procedure compared fixed representatives of the bins and controlled the discrepancy between each representative and its bin's best arm through a worst-case approximation bound. Protecting the optimal arm therefore required bin widths that shrank inversely with κinit\kappa_{\mathrm{init}}. Since comparison sample complexity grows quadratically with inverse accuracy, this finer partition introduced an additional quadratic curvature factor. We instead run localized learners within the bins and account for their cumulative regret when selecting among bins. This allows bins to be certified at the target localization scale without the additional curvature-dependent refinement, replacing the previous O~(κinit4d9/2)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^4d^{9/2}) regret bound with O~(κinit2d5+κinitSd4)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4), still without dependence on KK.

Both procedures use a known κinit\kappa_{\mathrm{init}}, and the learner selects the one with the smaller deterministic regret bound before interaction. The subsequent localized-elimination procedure and its leading regret guarantee remain unchanged.

AuthorsOpenReview ↗

Official Comment by Authors [3/4]

Expanded experiments and clarification of the empirical comparisons.

We have expanded the experiments across different action-set sizes KK and feature dimensions dd, added an adversarial bandit baseline (EXP3) that accommodates our reward process, and evaluated a new unknown κinit\kappa_{\mathrm{init}} initialization procedure. We clarify below both the additional evidence and the scope of the component comparisons.

1. Performance across different numbers of arms and feature dimensions. We now evaluate d∈{3,5,10}d\in\{3,5,10\} and K∈{20,100,500}K\in\{20,100,500\}, with T=30,000T=30{,}000, S=3S=3, and B=5B=5. The table below presents "Logistic · Fixed" as a representative setting; Appendix K includes the complete comparisons across all six settings. Our algorithms achieve the lowest mean cumulative regret in all nine configurations, with the unknown-κinit\kappa_{\mathrm{init}} variant performing best in eight of them. These experiments extend the evaluation beyond the original d=5d=5, K=20K=20 configuration and demonstrate strong performance across the tested dimensions and action-set sizes.

Table 2. Reported cumulative regret in Logistic · Fixed at T=30,000T=30{,}000, with S=3S=3 and B=5B=5. Values are mean (standard deviation); the lowest mean in each row is bold.

ddKKGLM-UCBGLB-OMDGLOCRS-GLinCBOFU-ECOLogOFULog+BOSESemiparametric TSSBEEXP3LE-SGLBLE-SGLB, unknown κinit\kappa_{\mathrm{init}}
3205777.7 (1911.4)3649.5 (963.6)5463.6 (1625.6)5760.2 (1395.0)4881.6 (1326.9)3392.3 (3771.2)6003.7 (1874.8)4223.5 (869.2)5983.7 (1624.6)1902.7 (160.3)548.7 (246.1)459.1 (331.9)
31006869.3 (899.6)5345.5 (645.6)6333.0 (617.0)6897.6 (658.9)6072.5 (613.9)5760.8 (3737.2)7522.4 (811.4)5057.7 (491.7)7195.6 (930.6)4001.9 (258.3)1149.0 (257.1)666.6 (201.6)
35007927.2 (840.7)6156.9 (548.9)7278.5 (551.7)8223.5 (749.3)7008.3 (544.8)6583.9 (4006.5)8663.4 (779.4)5659.3 (357.0)8243.0 (879.9)7328.0 (430.7)1367.1 (376.1)807.6 (376.8)
5205170.7 (2158.1)3242.8 (1457.3)4997.7 (2079.2)4813.5 (2224.1)5038.1 (1923.8)3899.0 (2929.1)4921.8 (2189.0)4351.5 (1738.5)4405.3 (2562.9)1673.0 (270.7)731.0 (193.1)640.0 (219.6)
51006823.7 (1354.0)5152.7 (911.4)6421.8 (1256.7)6754.3 (1524.5)6282.9 (1275.4)4682.0 (3173.5)7051.7 (1221.7)5974.2 (1138.4)6534.9 (2021.5)4097.7 (714.6)1455.3 (228.4)826.8 (245.5)
55007912.4 (908.1)6334.8 (756.1)7472.8 (815.6)7896.5 (891.6)7424.7 (760.0)5604.0 (2637.0)8219.6 (688.8)6977.3 (724.3)7734.6 (1605.3)7060.8 (711.1)1886.4 (772.1)1131.7 (340.7)
10203975.8 (1255.4)2999.7 (968.2)3962.9 (1252.9)3852.0 (1068.8)3930.8 (1325.7)1912.1 (1574.2)3927.6 (1196.7)3864.3 (1153.8)3929.4 (1611.7)1595.3 (282.7)1268.0 (485.1)1163.2 (362.1)
101005823.4 (1360.4)4812.4 (1057.9)5745.6 (1330.5)5758.0 (1274.1)5764.3 (1331.0)5244.7 (2033.6)5850.3 (1329.9)5574.4 (1225.0)5752.4 (1612.9)4024.6 (607.8)2026.7 (779.6)1575.8 (558.2)
105006524.7 (916.4)5584.1 (888.5)6389.5 (953.8)6493.1 (1084.4)6520.5 (984.9)4824.0 (2788.5)6594.4 (1031.8)6342.0 (952.3)6537.2 (1345.7)6015.4 (961.7)1746.6 (386.5)1758.5 (515.4)

2. Comparison with a baseline that accommodates nonlinear hidden shifts. Robustness to nonlinear hidden shifts is a central objective of our work. Standard GLB methods and semiparametric linear-bandit methods capture different parts of this structure, making them informative comparisons, although their assumptions do not fully cover our model. To complement these comparisons, we added EXP3 [1], whose adversarial reward formulation directly accommodates our bounded-reward setting without imposing a linear or generalized linear reward model.

Both versions of LE-SGLB achieve lower mean cumulative regret than EXP3 in all nine configurations, and the gap widens with KK at every tested dimension. For example, at d=3d=3, increasing KK from 2020 to 500500 increases EXP3’s mean regret from 1902.71902.7 to 7328.07328.0, whereas the unknown-κinit\kappa_{\mathrm{init}} variant increases from 459.1459.1 to 807.6807.6. At K=500K=500, the latter achieves approximately 89%89\% lower mean regret; the corresponding reduction at d=5d=5 is approximately 84%84\%. Thus, the empirical advantage extends to a baseline that is valid for our reward process, supporting the practical benefit of exploiting feature structure under nonlinear nuisance.

AuthorsOpenReview ↗

Official Comment by Authors [4/4]

3. Comparison with the closest centered-design predecessor. The centered-design method of Kim et al. [2] is already included as SBE, and we will make this connection explicit in the experimental discussion. Both versions of LE-SGLB achieve lower mean regret than SBE throughout the tested grid. This is consistent with the distinction between their modeling assumptions: SBE is designed for additive semiparametric linear rewards, while LE-SGLB explicitly addresses the interaction between hidden shifts and a nonlinear link.

4. Initialization comparison and component ablations. The comparison with the unknown-κinit\kappa_{\mathrm{init}} variant described above allows us to examine the effect of changing initialization while using the same subsequent localized-elimination procedure.

The remaining components are structurally connected: localization controls the nonlinear approximation error, the confidence analysis accounts for this error, and the stopping rule determines when comparisons are reliable enough for elimination. Removing one component can therefore invalidate the conditions supporting the others, making component-wise ablations difficult without redesigning the algorithm. We would welcome suggestions for informative ablations that preserve a coherent learning procedure and would be happy to evaluate them.

[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] Seok-Jin Kim, Gi-Soo Kim, and Min-hwan Oh. “Experimental Design for Semiparametric Bandits.” Proceedings of the 38th Conference on Learning Theory, PMLR 291:3215–3252, 2025.


Questions

Q1. For the experimental instances, what value of κinit\kappa_{\text{init}} is used, and what information about the unobserved shifts makes that value available to the learner? How does the resulting theoretical initialization budget compare with the 2,500-round cap and the total horizon?

With S=3S=3 and B=5B=5, the interval-based choice is κinit=(inf⁡∣z∣≤8μ′(z))−1\kappa_{\mathrm{init}}=(\inf_{|z|\le8}\mu'(z))^{-1}, approximately 2.98×1032.98\times10^3 for the logistic link and 1.98×10141.98\times10^{14} for the probit link. This requires prior knowledge of the bound ∣νt∣≤B|\nu_t|\le B during initialization, but not of the individual shifts.

The revised Appendix I selects between sequential elimination and geometric initialization using their deterministic regret bounds, giving initialization regret O~(min⁡κinitKd,κinit2d5+κinitSd4)\widetilde{\mathcal O}(\min\\{\kappa_{\mathrm{init}}K\sqrt d,\kappa_{\mathrm{init}}^2d^5+\kappa_{\mathrm{init}}Sd^4\\}). Importantly, the sequential initializer's improved regret does not imply a linear-curvature sample budget: its localization budget remains O~(κinit2Kd)\widetilde{\mathcal O}(\kappa_{\mathrm{init}}^2Kd). For the logistic instance with d=5d=5 and K=20K=20, this polynomial factor is approximately 8.9×1088.9\times10^8, before constants and logarithmic factors. Thus, the prescribed worst-case localization budget remains much larger than both 2,500 rounds and T=30,000T=30{,}000. As described in Appendix K, the reported known-curvature implementation uses a practical 2,500-round cap, which does not itself certify localization.

To address these concerns, we developed the unknown-κinit\kappa_{\mathrm{init}} initialization in Appendix J. It requires neither κinit\kappa_{\mathrm{init}} nor an upper bound on it, uses at most ⌊T⌋=173\lfloor\sqrt T\rfloor=173 rounds at our experimental horizon, and provides a regret guarantee that also covers insufficient localization. The practical variant using this budget also achieves the lowest mean cumulative regret in most of the evaluated configurations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.