acceptodds
Under review as a conference paper at ICLR 2027

Tangent Stein Bandits under Predictable Common Shifts

Abstract

Common shifts in candidate features leave action rankings unchanged but can bias raw moment estimates of the reward direction. We study this problem in single-index contextual bandits with an unknown monotone link and Gaussian candidates, allowing the common shift to depend on past observations. Within-set centering removes the shift from action comparisons but correlates the candidates, invalidating the independent-winner score. We show that the selected centered action retains an exact Gaussian moment in the tangent space of the current direction. This identity enables learning without evaluating the link or its derivative for candidate sets containing at least two actions, including candidate counts where the full centered score has a boundary or second-moment obstruction. With finite conditional noise variance, certified scale bounds, and sufficient initialization, a coordinate-clipped tangent epoch algorithm achieves polylogarithmic-in-horizon high-probability pseudo-regret under fixed positive derivative-information and schedule constants. The sharper guarantee follows from a quadratic conditional-mean regret relation specific to Gaussian candidates. In 18 held-out simulation settings, continual updates improve mean pseudo-regret over an independently tuned, valid centered explore-then-commit learner; shared initialization comparisons isolate the benefit of subsequent updates. Six long-horizon comparisons also favor tangent updates over a tuned persistent uniform-exploration policy. Matched perturbations distinguish the distributional conditions for the tangent identity from the derivative information required for effective learning.

Primary area:
learning theory
Keywords:
contextual bandits, single-index models, Stein's identity, online learning, regret analysis, nuisance shifts

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_S1P2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies single-index contextual bandits with an unknown monotone link, where every candidate in a round shares a common shift: Xt,a=St+Zt,aX_{t,a} = S_t + Z_{t,a} with Zt,a∼iidN(0,Id)Z_{t,a} \overset{iid}{\sim} N(0, I_d), and StS_t is predictable from the past but never observed. This shift biases raw Stein moments. Centering each candidate set removes it, but it also makes the arms dependent, which breaks the independent-winner score behind ESTOR (Kang et al., 2026). The authors' key observation is that greedy selection only touches the coordinate along the current direction uu, so the orthogonal part of the chosen centered action stays Gaussian. Stein's lemma then gives the tangent moment E[PuHt,AtYt/σK2∣Ft−1]=μt(u)Puθ⋆\mathbb E[P_u H_{t,A_t} Y_t/\sigma_K^2 \mid \mathcal F_{t-1}] = \mu_t(u) P_u\theta_\star for every K≥2K \ge 2, without evaluating the link or its derivative. On top of this identity they build an epoch algorithm: a uniform warm start, then greedy epochs of growing length that use clipped tangent averages and a normalized step on the sphere. They prove an O~(dT)\tilde O(d\sqrt T) high-probability regret bound, which sharpens to O(log⁡Tlog⁡log⁡T)O(\log T \log\log T) by exploiting the quadratic regret geometry of Gaussian candidates. Both results assume known upper bounds on the reward variance and the Lipschitz constant, a positive lower bound on derivative information, and a long enough warm start. The experiments are synthetic, with d≤24d \le 24 and K≤4K \le 4 in the policy comparisons. The method beats a centered explore-then-commit baseline in 18 settings and a persistent uniform-exploration baseline in 6. It performs on par with the exact full centered score at K=4K = 4 and gives mixed results against ESTOR when there is no shift. Additional controls show where the identity breaks down.

Critical strengths

Polylogarithmic high-probability regret without estimating the link. Corollary 2 shows that the algorithm's realized pseudo-regret is O(log⁡Tlog⁡log⁡T)O(\log T \log\log T) with probability at least 1−δ1-\delta. This holds for a monotone link with positive derivative information and fixed instance constants. It also holds when the common shift is chosen adaptively from past observations. The algorithm never fits ff: the link enters the bound only through BfB_f, Lˉf\bar L_f and μlow\mu_{\text{low}}. Existing guarantees for unknown-link single-index bandits are of order T\sqrt T or worse, so a polylogarithmic, high-probability rate is a meaningful theoretical result.

Critical weaknesses

W1. The key observation is clean but modest, and dropping the axial component has a cost the paper does not acknowledge. The set mean MtM_t is independent of the centered actions. The problem is therefore a single-index bandit with centered Gaussian candidates and a predictably drifting link f~t(x)=E[f(θ⋆⊤Mt+x)∣Ft−1]\tilde f_t(x) = \mathbb E[f(\theta_\star^\top M_t + x) \mid \mathcal F_{t-1}], a modest step beyond Kang et al. (2026). Within it, the tangent identity follows directly from Stein's lemma, since selection never touches the orthogonal component. Bypassing the axial score is legitimate, but it discards information. The tangent moment μtPuθ⋆\mu_t P_u\theta_\star gives the direction to rotate, yet its length μtsin⁡∠(u,θ⋆)\mu_t \sin\angle(u, \theta_\star) mixes the unknown derivative scale with the angle. The learner therefore cannot recover θ⋆\theta_\star by normalizing, as it does with the full moment at initialization. It must instead take small steps whose admissible size and epoch growth depend on μlow\mu_{\text{low}}, which is the root of the information requirement in W2.

W2. The guarantee rests on an information condition that the learner must know but cannot check. Theorem 2 and Corollary 2 assume that the average link derivative at the selected action stays above μlow\mu_{\text{low}} in every epoch and above μinit\mu_{\text{init}} during the warm start. Because of the step-size issue in W1, the algorithm's schedule must be set from these bounds, and the warm start in (23) depends on them as well. Yet both are properties of the unknown link, evaluated along the learner's own trajectory and moved around by the parallel component of StS_t. The method therefore avoids estimating ff only by assuming a certified lower bound on f′f' over the region it visits, and the paper offers no way to obtain or verify one. This also narrows the adaptive-shift claim. A predictable shift whose parallel component drifts into a flat region of the link drives μt\mu_t toward zero. The guarantee therefore holds only while that component keeps the index where f′f' is bounded away from zero.

Questions for authors
  1. Would the quadratic-regret argument behind Corollary 2 also give polylogarithmic regret for ESTOR in the no-shift Gaussian setting?

  2. Is the derivative-information condition intrinsic to this problem, or an artifact of the tangent approach? A lower bound showing that regret must grow as μlow\mu_{\text{low}} shrinks would make the condition a feature of the problem rather than a limitation of the method, and would weaken my concern in W2.

  3. For K≥4K \ge 4 the full centered score is valid, so the learner could normalize a full estimate of θ⋆\theta_\star instead of taking tangent steps. Would that remove the dependence of the schedule on μlow\mu_{\text{low}}? If so, the tangent score is needed only for K≤3K \le 3.

  4. How would a practitioner obtain μlow\mu_{\text{low}} and μinit\mu_{\text{init}} for an unknown link? Can the step size and epoch growth be chosen adaptively without them, and what condition on the parallel shift keeps the derivative information bounded away from zero under adaptive shifts?

4 comments
AuthorsOpenReview ↗

Response to S1P2 (1/2): reduction, ESTOR, full-score learners, and information dependence

Thank you for a precise review. Your questions led directly to the new results. We have uploaded a revised manuscript; the relevant changes are described below with section and appendix references.

W1 (reduction and the cost of dropping the axial part). We agree with the reduction: averaging over the independent set mean gives a predictably drifting link on centered candidates. The centered winner's law differs from the independent-winner law that ESTOR uses, and Theorem 1 gives an exact, finite-variance moment for that winner at every K≥2K\ge2 without its axial density.

We also agree that dropping the axial component has a cost. The tangent mean μPuθ⋆\mu P_u\theta_\star mixes information with angle, so it supports contraction rather than normalization. A weighted full-direction moment recovers the axial part, and accumulating it across epochs removes the step-size schedule (Appendix K.2 and K.3). Section 6 now states this tradeoff.

Q1 (ESTOR and the quadratic argument). Yes, under conditions. Consider an ESTOR-type clipped epoch learner without shifts whose full-moment estimate is within εn\varepsilon_n of aθ⋆a\theta_\star, where aa is bounded below by a positive constant and εn2\varepsilon_n^2 is of order dℓ/nd\ell/n. Normalizing gives 1−u^⊤θ⋆≤2εn2/a21-\widehat u^\top\theta_\star\le2\varepsilon_n^2/a^2, and equation (26) with geometric epochs then gives high-probability O(log⁡Tlog⁡log⁡T)O(\log T\log\log T) regret for fixed constants (Appendix L.4). This is our analysis under those assumptions, not a claim about ESTOR's published guarantee.

Q2 (is the information dependence intrinsic?). The μ−3\mu^{-3} dependence arises from our current estimation and contraction analysis. We do not establish a matching lower bound, so we do not claim that the exponent is intrinsic. Appendix L.2 gives the decomposition: a μ−2\mu^{-2} estimation factor and a μ−1\mu^{-1} factor from the epoch count of our contraction-based schedule. The accumulated learner does not use that schedule.

Q3 (full scores for K ≥ 4). We tested this directly. At K=4K=4, d=6d=6 and horizon 128,000, we accumulated the clipped unweighted full score across epochs and normalized it, with no step size and no information bound as input. Relative to retuned Tangent Stein Bandits (TSB), this lowered regret by 48.0 for logistic rewards (95% interval 37.9 to 58.0) and by 24.5 for signed rewards (95% interval 10.2 to 38.8). The intervals are paired over 48 held-out replicates, and the run used the frozen settings of the accumulated learner (Appendix K.4).

The full-score control in Table 12 normalizes each epoch separately, which is a different update. With weighting, full-direction moments also become valid at K=2K=2 and K=3K=3 (Appendix K.2). The tangent construction remains the version that needs no axial density.

AuthorsOpenReview ↗

Response to S1P2 (2/2): obtaining information bounds, avoiding them as inputs, adaptive shifts

W2 and Q4 (what can be certified). Lemma 3 in Appendix B gives a class-based certificate. Suppose ∣θ⋆⊤St∣≤B|\theta_\star^\top S_t|\le B and f′≥mr>0f'\ge m_r>0 on [−B−r,B+r][-B-r,B+r], and let pr=2Φ(r)−1p_r=2\Phi(r)-1. Then μlow≥mrprK\mu_{\rm low}\ge m_rp_r^K and μinit≥mrpr\mu_{\rm init}\ge m_rp_r, with orthogonal shifts unrestricted. This requires prior knowledge of the link class; it is not an online certificate for an arbitrary monotone link. Section 5 now says so next to Algorithm 1.

Avoiding the bounds as inputs: theory. Proposition 3 in Appendix L.3 gives a horizon-dependent schedule. With L=log⁡TL=\log T, set γ=1/Lˉf\gamma=1/\bar L_f, bT=1+1/L\sqrt{b_T}=1+1/L and n0=⌈CF2dℓˉTL2⌉n_0=\lceil C_F^2d\bar\ell_TL^2\rceil, where ℓˉT\bar\ell_T is the logarithmic confidence term, and play uniformly if n0>Tn_0>T. The schedule uses the variance and Lipschitz bounds but neither information bound.

Suppose the instance has uniform positive information, and let x=γc0μlowx=\gamma c_0\mu_{\rm low}. Once n0≤Tn_0\le T and L≥max⁡2/x,VˉKmax⁡(3/μinit,4/(c0μlow))L\ge\max\\{2/x,\\ \sqrt{\bar V_K}\max(3/\mu_{\rm init},4/(c_0\mu_{\rm low}))\\}, the contraction margin is at least x/2x/2, the number of stages is O(L2)O(L^2), and the initialization condition (23) holds. The result is high-probability O(log⁡2Tlog⁡log⁡T)O(\log^2T\log\log T) regret. Information then determines when the guarantee takes effect rather than being an input. That onset can be large, and the schedule does not estimate information online.

Avoiding the bounds as inputs: practice. The completed accumulated learner (CA, Appendix K.3) needs none of γ\gamma, μlow\mu_{\rm low}, μinit\mu_{\rm init} and Lˉf\bar L_f. Its inputs are the variance bound, used for clipping, and the known Gaussian axial density. Against Tangent Stein Bandits (TSB) it had three wins, two inconclusive comparisons and one loss (Appendix K.4). We present it as an empirical extension; its regret analysis is future work.

Adaptive shifts. The identity holds for any predictable common shift. Learning additionally needs derivative information, and a parallel shift that drifts into a flat region of the link reduces it. A bounded parallel shift together with the derivative envelope above is one sufficient condition. Section 3 now states the identity's validity and the learning conditions separately.

I thank the authors for the detailed response and the revision. Section 6 and Appendix L now state the tradeoffs clearly. However, the revision shows that the paper's main strengths do not depend on the tangent construction. Proposition 2 gives a weighted full-direction moment that is valid for every K≥2K \ge 2, and Appendix L.4 shows that the polylogarithmic rate comes from Gaussian geometry shared by any full-moment learner whose estimate concentrates. The tangent route also seems to be the costlier one. It needs μlow\mu_{\text{low}} to set the schedule and pays an extra μ−1\mu^{-1}, while in L.4 the coefficient aa affects only the initialization length and an a−2a^{-2} constant.

Overall, I am keeping my scores unchanged. I believe the paper would be stronger as a resubmission built around the full-moment learner and its regret analysis.

AuthorsOpenReview ↗

Response to S1P2: full-moment learners and the tangent construction

Thank you for the further assessment, and for the suggestion that led to the weighted full-direction moments in Appendix K. We agree with both observations: the Gaussian quadratic-regret argument extends to any full-moment learner whose estimate concentrates, and our contraction-based tangent analysis pays an extra μ−1\mu^{-1} factor through its schedule.

The methodological result we retain is an exact, finite-variance moment for the correlated centered winner at every K≥2K\ge2 that does not require the selected axial density. The weighted moments are a valid alternative that retains axial information but needs that density.

Two points may help complete the comparison. First, the full-moment route also requires an information condition: Appendix L.4 assumes a uniform positive coefficient E[wf′]≥a‾\mathbb E[wf']\ge\underline a, a weighted analogue of μlow\mu_{\rm low}, which enters through the initialization length and an a‾−2\underline a^{-2} factor in the regret bound. Second, L.4 is a transfer argument conditional on concentration and that coefficient bound; it is not yet a complete regret theorem for the accumulated learner. Proposition 3 removes the information bounds from the inputs of the tangent schedule, although information still sets the onset horizon and the contraction cost remains.

We agree that a complete regret analysis of the accumulated full-moment learner is a natural next step. The revision states the current tradeoffs in Section 6 and Appendix L.

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

The paper studies contextual bandits with an unknown monotone reward function and Gaussian actions sharing a predictable common shift.

The algorithm centers the actions, estimates a reward direction through initial exploration, then selects greedily and updates this direction after each epoch using clipped tangent estimates.

These estimates exploit the Gaussian component perpendicular to the current direction, allowing learning from greedy choices without evaluating the reward function or its derivative.

With sufficient initialization and derivative information, the method achieves polylogarithmic high-probability pseudo-regret. Synthetic experiments compare it with exploration-based and other Stein-based methods.

Critical strengths

i) The tangent moment provides a simple way to learn from greedy selections despite the dependence introduced by centering. The arguments I examined appear sound.

ii) The experiments are carefully controlled, with separate tuning and evaluation, paired comparisons, shared-initialization tests, and comparisons with ESTOR.

Critical weaknesses

i) The distinct novelty needs clearer justification. The central identity follows relatively directly from Gaussian independence and classical Stein integration by parts. The improved regret rate also relies on a sharper Gaussian regret analysis that could benefit other valid estimators. The exact centered full score performs similarly, and comparisons with ESTOR are mixed.

ii) The guarantee has limited quantitative relevance to the experiments. The supplied sufficient initialization bound reaches approximately 18.5 million samples for a 128,000-round horizon, while experiments often initialize with 128 samples. This does not invalidate the theorem, but leaves a substantial gap between theory and practice.

iii) The scope is too specialized and restrictive. Monotonicity removes the unknown function from the optimal ranking rule, while exact Gaussian structure and positive derivative-information bounds enable the analysis. The significance of the advance should be assessed within this restricted setting. Why would it be monotonous?

Questions for authors
  1. Which part of the improved regret rate specifically requires tangent estimation, rather than the sharper Gaussian regret analysis?

  2. Can you provide a meaningful finite-horizon guarantee for an evaluated setting?

  3. How does the tangent estimator compare with weighted full-direction moments that avoid the standard score’s small-K difficulties?

5 comments
AuthorsOpenReview ↗

Response to Wtoi (1/2): novelty, what needs tangent estimation, and weighted full moments

Thank you for checking the arguments and for the weighted-moment suggestion, which we followed. We have uploaded a revised manuscript; the relevant changes are described below with section and appendix references.

W1 and Q1 (what requires tangent estimation). The quadratic regret conversion does not; it applies to any valid estimator (comparison table in Section 1, Appendix L.1). Tangent estimation supplies a moment that stays valid on greedy rounds for the correlated centered winner at every K≥2K\ge2, with finite variance and without the axial density. For explore-then-commit, which uses only uniform exploration rounds, the tradeoff between exploration and commitment gives T\sqrt T even with Lemma 2. The introduction now states the two contributions separately.

Q3 (weighted full moments). Condition on the past and the set mean, and write the winner as H=su+vH=su+v, where ss has the axial winner density qKq_K and v⊥uv\perp u is Gaussian. For a weight with w(0)qK(0)=0w(0)q_K(0)=0, Gw=aw(s)u+w(s)vσK2,aw=−w′−wqK′qK,E[YGw]=E[wf′],θ⋆.G_w=a_w(s)u+\frac{w(s)v}{\sigma_K^2},\qquad a_w=-w'-w\frac{q_K'}{q_K},\qquad \mathbb E[YG_w]=\mathbb E[wf']\\,\theta_\star. The weight w(s)=sw(s)=s gives finite variance for every K≥2K\ge2, while w≡1w\equiv1 does so only for K≥4K\ge4. The axial density follows a one-dimensional recursion in KK (Proposition 1, Appendix K.1). At K=2K=2, Gs=(s2/σK2−1)u+sv/σK2G_s=(s^2/\sigma_K^2-1)u+sv/\sigma_K^2 and E∣Gs∣2=d+1\mathbb E\\|G_s\\|^2=d+1. Monte Carlo checks agree with the identity for every weight and candidate count we tested, with cosine at least 0.999.

Online comparison. Since the mean of YGwYG_w is a positive multiple of θ⋆\theta_\star for every uu, we accumulate its clipped observations across epochs and normalize. We call this the completed accumulated learner (CA) and use w(s)=sw(s)=s. In the Table 7 environments (d=6d=6, horizon 128,000), CA and Tangent Stein Bandits (TSB) were tuned on the same 14-configuration grid with 12 tuning replicates, and all choices were frozen before evaluation on 48 held-out paired replicates. CA minus TSB, with paired 95% intervals:

K = 2K = 3K = 4
Logistic+17.1 (3.0, 31.3)−1.8 (−10.5, 7.0)−4.7 (−18.0, 8.7)
Signed−32.6 (−43.0, −22.1)−27.2 (−36.2, −18.2)−30.5 (−43.3, −17.6)

Ablations at CA's frozen settings:

  • Resetting the completed moment every epoch is worse than CA in all six cells, so accumulation substantially improves these learners under the matched settings.
  • Accumulating the unweighted full score at K=4K=4 beats TSB (Appendix K.4).
  • The weight tanh⁡(2s)\tanh(2s) beats w(s)=sw(s)=s in the logistic cells and is slightly worse in the signed cells, so the weight shape matters.

The weighted identity extends full-direction estimation to K=2K=2 and K=3K=3. The tangent construction is the route that needs no axial density and has an established high-probability analysis. It also remains valid under any selection rule that depends only on the axial coordinates and independent randomization, without re-deriving the selected axial density. Appendix K contains the derivations and results, and Sections 6 and 7 summarize them.

AuthorsOpenReview ↗

Response to Wtoi (2/2): finite-horizon relevance, monotonicity, and scope

W2 and Q2 (a meaningful finite-horizon guarantee). The figure of 18,486,784 is correct, and we do not have a non-vacuous certificate for the evaluated short initializations. Plugging numerically evaluated information values into (25) still gives about 1.96 million rounds for logistic and 185,000 for signed rewards at horizon 128,000. These are quadrature values, not certified lower bounds. A meaningful certificate would need a sharper concentration and initialization analysis, and the revision says so explicitly (Section 5, Appendix L.5).

What we can offer is evidence on the shape of growth that Corollary 2 predicts. We ran 48 paired replicates to 2232^{23} = 8,388,608 rounds, comparing Tangent Stein Bandits (TSB) at the paper's settings (n0=128n_0=128, b=1.5b=1.5) with the centered explore-then-commit (ETC) baseline. The table gives the regret added by each horizon doubling from 2142^{14} to 2232^{23}, and the final regret as mean ± one standard error.

SettingTSB, added per doublingTSB at 2232^{23}ETC at 2232^{23}
Logistic, K = 214.1 to 17.0224.7 ± 4.416,833 ± 1,490
Logistic, K = 419.9 to 25.7326.6 ± 6.032,520 ± 4,240
Signed, K = 22.4 to 2.869.8 ± 4.816,594 ± 1,420
Signed, K = 41.9 to 2.6100.7 ± 6.738,770 ± 2,948

Approximately constant increments per doubling are consistent with logarithmic growth over the tested range. We fit R=a+c,hβ(T/216)R=a+c\\,h_\beta(T/2^{16}) to the checkpoints from 2162^{16} on, with hβ(x)=(xβ−1)/βh_\beta(x)=(x^\beta-1)/\beta and h0(x)=log⁡xh_0(x)=\log x, so that β=0\beta=0 is logarithmic growth. The bootstrap intervals for β\beta contain 0 for TSB and for the completed accumulated learner in every setting, for example −0.045-0.045 to 0.0520.052 for logistic K=2K=2. ETC, which stops learning, gives β≈1\beta\approx1. This supports the predicted shape over a 512-fold range of horizons, but it does not certify the constants (Appendix K.5).

W3 (why monotone?). Monotonicity makes ranking by the index optimal, so the learner can act without knowing the link. For general, possibly non-monotone links, Dey et al. (2026) show that worst-case regret of order T2/3T^{2/3} is unavoidable in their setting. We work in the monotone regime, where the learning problem reduces to the direction. That problem is still non-trivial, because the direction must be learned from rewards of greedily chosen, correlated centered actions.

A concrete instance is acceptance of an offered option against a fixed outside option, Y=1θ⋆⊤X+ϵ>0Y=\mathbf 1\\{\theta_\star^\top X+\epsilon>0\\}, where ϵ\epsilon has an unknown fixed distribution. Then f(z)=1−Fϵ(−z)f(z)=1-F_\epsilon(-z) is monotone, and a bounded continuous density gives our regularity conditions. A history-dependent common state StS_t shifts acceptance levels without changing the ranking of options. Gaussian residuals are a substantive design assumption, discussed in Appendix L.6.

Reviewer_WtoiOpenReview ↗

reply

Thank you for the detailed responses and additional results.

  • Novelty: The authors confirm that the improved regret rate also applies to ESTOR in the Gaussian no-shift setting. Moreover, the new weighted full-direction estimators are competitive with, and sometimes outperform, tangent estimation. This further raises the question of what substantial methodological advantage the tangent construction provides beyond a simpler estimating equation for a particular Gaussian setting.

  • Theoretical guarantees: The authors acknowledge that the sufficient initialization requirements remain larger than the experimental horizons. The long-horizon experiments are useful, but do not resolve the lack of quantitatively informative finite-horizon guarantees.

  • Scope: The response explains why monotonicity simplifies the decision problem, but this is precisely the concern: the unknown link does not affect the optimal action ranking under this assumption. The acceptance-model example provides some motivation, but does not substantially establish the relevance of the restrictive combination of monotonicity, Gaussian candidates, predictable common shifts, and positive derivative information.

Overall, the rebuttal clarifies the contributions and adds useful results, but does not sufficiently resolve my concerns about their novelty and significance.

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

This paper studies single-index contextual bandits with an unknown monotone link, predictable common shifts, and Gaussian residuals. It proposes an epoch-based greedy algorithm that learns the parameter direction using centered contexts and tangent Stein moments. Under the stated assumptions, the authors prove a high-probability polylogarithmic regret bound.

Critical strengths
  1. I think a key strength of this work is their simple estimation method that remains valid under both centering and greedy selection. Theorem 1 gives an exact tangent moment for estimating the unknown parameter from centered contexts. This moment remains valid after greedy selection, even though centering makes the candidates dependent. I checked the proof in Appendix A.1 and did not find any major issues.

  2. The paper combines tangent-based direction estimation with regret analysis to obtain a strong high-probability guarantee with an unknown link, common shifts and Gaussian residuals. Under the stated assumptions, Corollary 2 proves a regret bound of O(log⁡Tlog⁡log⁡T)O(\log T\log\log T).

Critical weaknesses
  1. My main concern is the strong dependence on derivative information hidden in the polylogarithmic regret rate. When both information bounds are of order μ\mu, the bound can have roughly a 1/μ31/\mu^3 factor. Could the authors make this dependence explicit and compare it with earlier single-index bandit results? Also, (as mentioned in Appendix J) Logistic-bandit results, such as Abeille et al. (2021), show that curvature dependence can be substantially improved. I understand that these results use a known link and do not directly apply here. However, it remains unclear whether the stronger information dependence comes from an unavoidable difficulty of this model, or whether it could be reduced through a sharper analysis.
Questions for authors

Question

  1. I appreciate the analysis under the proposed model. As I am not an expert in single-index bandits, I find it difficult to judge how much the assumptions on the Gaussian residuals and the link function limit the significance of the results. It would help if the authors provided concrete examples of important real-world problems captured by this setting and explained why the assumptions are reasonable in those examples.

  2. If there is no common shift and the candidates are Gaussian, could ESTOR also achieve polylogarithmic regret by using Equation (26)?


Clarification request

  1. (Line 40-44) I initially read “We extend the fixed-distribution model” as suggesting that this paper covers ESTOR’s full setting. My understanding is that the paper allows predictable common translations but restricts the residuals to standard Gaussian, whereas ESTOR allows a broader class of fixed candidate distributions. So the setting is broader in one respect and narrower in another. The preceding sentence does mention Gaussian candidates, but making this tradeoff explicit would help clarify the comparison.

  2. Since (\hat g_i) plays a central role in the analysis, it would help to define it explicitly with an equation in the main text before Lemma 1. The lemma describes its construction in words, but a single equation showing the clipping, averaging, and projection steps would make it easier to follow.

7 comments
AuthorsOpenReview ↗

Response to Q7Dd: information dependence, ESTOR, model relevance, and clarifications

Thank you for checking Appendix A.1 and for the precise questions. We have uploaded a revised manuscript; the relevant changes are described below with section and appendix references.

W1 (information dependence). Your reading is correct. In (21), let μinit≍μlow≍μ\mu_{\rm init}\asymp\mu_{\rm low}\asymp\mu, fix γ\gamma, set x=γc0μlowx=\gamma c_0\mu_{\rm low}, and choose b=(1−αx)/(1−x)\sqrt b=(1-\alpha x)/(1-x) for a fixed α∈(0,1)\alpha\in(0,1). Then (ATceil)2=O(VˉKdℓT/μ2)(A_T^{\rm ceil})^2=O(\bar V_Kd\ell_T/\mu^2) and the number of epochs is JT=O(log⁡T/(γμ))J_T=O(\log T/(\gamma\mu)), so the greedy term in (27) scales as LˉfVˉKdℓTlog⁡T/(γμ3)\bar L_f\bar V_Kd\ell_T\log T/(\gamma\mu^3).

The dependence has two sources: a μ−2\mu^{-2} estimation factor and a μ−1\mu^{-1} factor from the epoch count of our contraction-based schedule. Section 5 now displays this, with the derivation in Appendix L.2. We do not establish a matching lower bound and do not claim that the exponent is intrinsic.

Empirically, when we scaled the logistic slope f(κx)f(\kappa x) over an 8-fold range, the regret of Tangent Stein Bandits (TSB) stayed between 260 and 386. Because κ\kappa also changes gaps and initialization cost, we do not read an exponent from this. Abeille et al. (2021) improve curvature dependence for known-link logistic bandits; whether a similar improvement holds with an unknown link is an interesting open question.

Q1 (applications). A concrete instance is binary acceptance against a fixed outside option, where an unknown monotone response maps an option's index to its acceptance probability. A common user or session state enters every candidate's features and shifts acceptance levels without changing their ranking.

Gaussian candidates are most natural when the system itself generates them, for example by Gaussian perturbations around a context embedding; the assumption then holds by design. When candidates are observational, the learner sees all KK candidates every round. This allows distributional diagnostics and covariance estimation of the centered residuals without rewards, although finite samples cannot certify exact Gaussianity. If the residuals are Gaussian with known covariance Σ\Sigma, whitening reduces the problem to ours (Appendix L.6).

Q2 (ESTOR without shifts). Yes, under a uniform positive full-moment coefficient and the matching concentration bound. Normalizing an estimate with error εn\varepsilon_n gives squared angular error of order εn2\varepsilon_n^2, and (26) with geometric epochs gives polylogarithmic high-probability regret (Appendix L.4). This separates the Gaussian geometry, which both methods share, from the tangent construction for centered candidates.

Clarification 1. We replaced the sentence in the introduction with: "We allow predictable common translations while assuming independent standard Gaussian residuals. Kang et al. (2026) allow broader fixed candidate distributions without translations, so the two settings differ along both dimensions."

Clarification 2. Before Lemma 1 we added the explicit estimator, with coordinatewise clipping over the rounds Ei\mathcal E_i of epoch ii: g^i=Pui[1ni∑t∈Eiclip⁡τi(YtPuiHt,AtσK2)],τi=VˉKni/ℓT.\widehat g_i=P_{u_i}\Big[\frac1{n_i}\sum_{t\in\mathcal E_i}\operatorname{clip}_{\tau_i}\Big(\frac{Y_tP_{u_i}H_{t,A_t}}{\sigma_K^2}\Big)\Big],\qquad\tau_i=\sqrt{\bar V_Kn_i/\ell_T}.

Thank you for the clarification in Appendix L.4. I appreciate the simple tangent construction and would like to clarify its contribution relative to ESTOR.

I still have 2 more questions.

Noise assumptions. Would your conditional zero-mean and second-moment assumptions also suffice for ESTOR’s estimation analysis, using an appropriate martingale argument? If so, the absence of a feature–noise independence requirement appears to follow from directly imposing conditional moment conditions, rather than from the tangent construction. Is this understanding correct?

Scope of the contribution. If the above understanding is correct, would it be fair to regard handling predictable common shifts as the primary contribution? Appendix L.4 indicates that an ESTOR-type learner already achieves the same polylogarithmic horizon dependence in the Gaussian no-shift setting. Your setting additionally imposes global boundedness and Lipschitz conditions on the link. Thus, is the main advance a simpler tangent-based method that retains polylogarithmic regret when predictable common shifts are introduced, under these additional global link restrictions, rather than a stronger regret guarantee by ESTOR in the comparable no-shift setting?

AuthorsOpenReview ↗

Follow-up to Q7Dd: conditional noise assumptions and the contribution relative to ESTOR

Thank you for the precise follow-up. Your reading of the noise assumptions is correct, and we separate that shared estimation step from the contribution of the tangent construction.

Noise assumptions. Yes. The conditional moment conditions also support an ESTOR-type clipped full-moment estimator, provided it uses the correct selected-action score. Let Gt=σ(Ft−1,Xt,1:K,At)\mathcal G_t=\sigma(\mathcal F_{t-1},X_{t,1:K},A_t), let sts_t be a Gt\mathcal G_t-measurable score with E[st,j2∣Ft−1]≤Vs\mathbb E[s_{t,j}^2\mid\mathcal F_{t-1}]\le V_s for every coordinate jj, and write V=(Bf2+ση2)VsV=(B_f^2+\sigma_\eta^2)V_s. Iterated conditioning gives E[ηtst∣Ft−1]=0,E[Yt2st,j2∣Ft−1]≤V.\mathbb E[\eta_ts_t\mid\mathcal F_{t-1}]=0,\qquad \mathbb E[Y_t^2s_{t,j}^2\mid\mathcal F_{t-1}]\le V. Clipping controls the bias, and Freedman's inequality bounds the deviation from the epoch's average conditional moment by a term of order dVℓ/n\sqrt{dV\ell/n}, where ℓ\ell is the logarithmic confidence term. With a correct full-direction moment and a uniform positive coefficient, this supplies the estimation and normalization steps of Appendix L.4. Feature-dependent noise is therefore permitted by the conditional moment assumptions, not by a property specific to tangent estimation. We will add this argument to Appendix L.4.

Scope of the contribution. Largely yes. Handling predictable common translations is the primary model extension, and the tangent construction is our route to it: it gives an exact, finite-variance greedy-round moment for the correlated centered winner at every K≥2K\ge2 without the axial winner density. The unweighted full centered score has a boundary term at K=2K=2 and an infinite axial second moment at K=3K=3. The weighted full-direction moments in Appendix K are valid alternatives; they retain axial information but require the axial density.

The Gaussian quadratic-regret conversion is a separate analytical contribution. Under the corresponding concentration and positive-coefficient conditions, it also sharpens the analysis of an ESTOR-type learner in the Gaussian no-shift setting, so we do not claim a tangent-specific improvement in horizon dependence there. Our guarantee also uses a globally bounded, Lipschitz link and positive derivative information, whereas ESTOR allows broader fixed candidate distributions. The two settings therefore differ both in the nuisance structure and in the distributional and regularity conditions.

We will revise the contribution statement and the related-work comparison to make this separation explicit.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.