acceptodds
Under review as a conference paper at ICLR 2027

Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors

Abstract

Low-rank matrix and tensor bandits exploit structured interactions but typically assume a known reward link. Recent single-index bandit methods accommodate unknown links without directly exploiting matrix or tensor rank. We address this gap by studying stochastic matrix and tensor bandits with an unknown shared Lipschitz link and a low-rank index parameter under known regular candidate distributions and finite-variance noise. For monotone links, T-ESTOR combines robust, rank-adaptive Stein estimation with epoch-based greedy selection. Under exact selected-score access and a uniformly positive selected-design Stein signal, it achieves square-root regret with dimension dependence determined by the low-rank structure. For every admissible design, the monotone lower bound matches the rank, dimension, and horizon dependence up to logarithmic factors at large horizons, for fixed menu size and model/design constants. For nonmonotone links under a nonzero base-law Stein signal, T-BSTOR combines structured estimation with robust bin-based learning and attains the optimal horizon rate for fixed dimensions, menu size, and model/design constants. Synthetic and CCLE-based experiments illustrate the benefits of structured estimation relative to vectorized and competing single-index baseline methods.

Primary area:
learning theory
Keywords:
contextual bandit, online learning

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_CanCOpenReview ↗
Rating
2
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies single-index contextual bandits with an unknown shared link and a low-rank matrix or tensor parameter. From technical side, it combines paired Stein estimation, spectral robustification, and nuclear-norm regularization. Under known candidate distributions and finite-variance noise, T-ESTOR achieves O~(T)\widetilde O(\sqrt T) regret for monotone links, given selected-score access and a positive-signal assumption. For arbitrary Lipschitz links, T-BSTOR adds scalar binning and achieves O~(T2/3)\widetilde O(T^{2/3}) regret under a nonzero-signal assumption. The lower bounds match the rank dependence for monotone links at large horizons and the T2/3T^{2/3} rate for nonmonotone links. Synthetic and CCLE-derived experiments compare the methods with vectorized and existing bandit baselines.

Critical strengths
  1. Low-rank structure. The paper handles matrix and tensor parameters that are low rank but may be dense, where sparsity-based methods offer little help. Its regret bounds scale with rank and structural dimensions, and the experiments show gains from using that structure.

  2. Theoretical analysis. The proof accounts for the distribution change caused by greedy arm selection. Paired observations remove the reward offset from the estimation bound under finite-variance noise. The lower bounds match the structural dependence in the monotone case and the T2/3T^{2/3} rate in the nonmonotone case under the stated conditions.

Critical weaknesses
  1. The main guarantee relies on strong oracle and signal assumptions. T-ESTOR requires the known joint candidate distribution and exact selected scores, including the projection density-to-CDF ratio for each adaptively chosen direction. Knowing the base distribution does not make this quantity easy to compute for general dependent designs. Moreover, Condition 3.2 requires a uniformly positive selected-design Stein signal, which does not follow from monotonicity alone. The experiments use numerical scores, but Appendix I.3 explicitly states that the accuracy checks do not certify the error conditions needed by the theory. Although the paper provides an estimated-score extension, it does not establish the same guarantee for the implemented algorithm. This limits how directly the advertised generality and regret bounds translate into a practical method.

  2. The experiments do not sufficiently isolate or establish the benefit of the proposed structure. The main synthetic evaluation uses one 16×16×416\times16\times4 construction with rank two and independent beta-distributed entries. It does not systematically vary dimension, rank, menu size, or dependence, despite these being central to the theoretical claims. The structured and vectorized methods also have different exploration lengths and tuned configurations, so the observed regret improvement cannot be attributed to structure alone, as the paper acknowledges. Furthermore, T-BSTOR uses an adaptive stopping heuristic outside the proved exploration schedule, and the CCLE evaluation generates simulated actions and feedback from a data-derived coefficient. Controlled ablations and broader scaling experiments are needed to establish whether the theoretical structural advantage explains the practical gains.

Questions for authors
  1. Guarantees for the implemented algorithms. T-ESTOR uses numerical selected scores, but Appendix C.7 requires error certificates valid for the adaptively chosen directions; the diagnostic in Appendix I.3 does not establish them. Can you provide such certificates or show how regret changes with a finer score grid? The T-BSTOR theorem uses fixed exploration and median-of-means bins, whereas Figure 1 uses adaptive stopping and most Figure 2 variants use sample-mean bins. How does the theorem-specified policy perform on these tasks, and is any regret guarantee available for the plotted variants?

  2. Selected-signal assumption. Condition 3.2 requires a positive signal for every ranking direction. Appendix E.3 shows that, under a symmetric candidate law and a ReLU link, an opposite ranking direction can yield a signal of Lf2−KL_f2^{-K}. What signal lower bounds hold for the reported experiments, and how do regret and the structural comparison change when the signal is weaker? Does the comparison with ESTOR in Kang et al. (2026) use equivalent signal assumptions?

  3. Evidence for the structural gain. Appendix I.4 reports that no T-BSTOR variant had the lowest mean regret in the earlier signed-diagonal design, while the current study changes both the design and implementation. Can you test both implementations on both designs with matched exploration, binning, confidence settings, and tuning budgets? Figure 1 also gives matrix and slice methods the same structural scale of 128; can you test the separating construction in Appendix F.1? The archive can redraw Figures 1 and 2 from saved summaries, but its historical controllers cannot replay the complete experiments from the compact package. Can you provide a standalone numerical rerun procedure using the stated seeds and frozen settings?

10 comments
AuthorsOpenReview ↗

To Reviewer CanC: Summary

Thank you for recognizing the low-rank formulation and theoretical analysis. Our primary contribution is the structural regret guarantees and lower bounds. We address both critical weaknesses: Sections 1–2 below discuss oracle and signal assumptions; Section 3 discusses structural evidence and its remaining limits.

Your concernHow we addressed itRevised location
Selected-score access and guarantees for numerical implementations (Weakness 1; Q1)Added a conditional policy theorem, product-beta certificates, and grid/tuning controls. Calibrated policies remain outside the guarantees.Corollary 3.4; Theorem K.2; Appendices K.1–K.3; Tables 17 and 22
Uniform signal assumption and weaker links (Weakness 1; Q2)Derived an instance-specific all-direction floor and added weak-signal comparisons, retaining transferred-setting failures.Condition 3.2; Lemma K.3; Appendix K.4; Tables 20–21
Practical exploration and binning departures (Weakness 2; Q1)Added matched stopping/bin controls and a conditional bounded-stop theorem. The plotted heuristic is still not covered.Theorem K.4; Appendix K.5; Tables 13 and 16
Structural attribution, historical comparisons, and tensor separation (Weakness 2; Q3)Added matched exploration/shrinkage controls, common-wrapper comparisons, and F.1/unfolding tests; retained unfavorable results.Section 4; Appendix F.1; Tables 1 and 9–15
Breadth of scaling and real-data evidence (Weakness 2)Partly addressed through dimension comparisons and offline moments. Online rank/menu/dependence sweeps remain untested; CCLE remains semi-synthetic.Section 4; Appendices J and L.5; Tables 1, 16 and 23
Standalone reproduction of the original figures (Q3)Documented the full replay audit and commands, separately from summary redraws and the smaller backend check.Appendix M; supplement README
AuthorsOpenReview ↗

To Reviewer CanC: W1 and Q1

1. Weakness 1 and Q1: Oracle access and implementation guarantees

We agree that knowing the candidate law does not itself provide a practical selected-score oracle, and that the original numerical diagnostics did not certify the theorem. The revision adds a conditional regret extension and product-beta certificates; known-law access and a quantitative signal condition remain assumptions of the main guarantees.

The new result is a conditional regret guarantee for the paired policy. Under Theorem 3.3's assumptions, Corollary 3.4 and Theorem K.2 show that T-ESTOR retains square-root horizon regret with a fixed, sufficiently small error in the scalar selected-law correction. Exact base scores are retained; the approximation and its conditional certificate are frozen before collecting each epoch's observations. With valid supplied signal and covariance bounds, it suffices that

εi=(K−1)∣α^i−αi∣L2(Qi)≤μmin⁡4LfK∣ΣX∣op,w^i=(w+εi)2.\displaystyle \varepsilon_i=(K-1)\\|\widehat\alpha_i-\alpha_i\\|_{L^2(Q_i)} \le \frac{\mu_{\min}}{4L_f\sqrt{K\\|\Sigma_X\\|_{\mathrm{op}}}}, \qquad \widehat w_i=(\sqrt{w}+\varepsilon_i)^2.

using Theorem 3.1's tuning with w^i\widehat w_i, where w2=2M(Kd+K−1)w_2=2M(Kd+K-1). The directional error makes the raw paired mean μiΘ∗+βivi\mu_i\Theta_*+\beta_i v_i: its parallel component rescales the structured target, and the perpendicular component gives an epoch contraction. The proof controls robustification around the raw mean and obtains the explicit regret bound (50). It does not require accuracy to improve with TT or assume that nonlinear robustification is unbiased.

Constructive certification. Appendices K.1–K.2 give the product-beta construction, bounding density/CDF truncation and interpolation errors with interval arithmetic and including the floored lower tail in selected-law MSE. All 38 reconstructed functions pass: 27 directions from the dense monotone runs, nine threshold-adjusted d=16d=16 directions, and two reference cases. The maximum scalar-ratio MSE bound is 4.202×10−64.202\times10^{-6}, below 11/116640≈9.431×10−511/116640\approx9.431\times10^{-5} for the original signal floor 1/21/2. Historical grid nodes were not archived; the functions were rebuilt at saved directions.

A separate six-pair guarded study certified all 54 distinct used nonzero directions before their epochs, with identical guarded/unguarded actions (Appendix K.3). These certificates concern real-arithmetic evaluation of the functions. The conditional theorem requires certification at every used direction and valid statistical tuning; it does not validate practical multipliers, the full floating-point pipeline, or new weak-signal directions. The constructive oracle is specific to product-beta laws, although the conditional policy theorem is more general. Resource-limited constructions may fail to certify; the epoch count alone gives no total-work guarantee.

Table 22 reports numerical sensitivity across 1,024–16,384 grid nodes. Endpoint-regret difference intervals lie within prespecified margins of approximately 1.23–1.29, while removing the correction increases regret by 180.94, 197.88, and 202.44 on Linear, Tanh, and Convex. Large pointwise errors persist in floored tails; grid sensitivity and the selected-law certificate answer different questions.

Original theoretical tuning remains conservative. All 20 synthetic and 20 CCLE T-BSTOR controls produce zero fits. At T=32,766T=32{,}766, the synthetic controls exceed practical Slice regret by 375.64 on Linear and 120.49 on Wave (Table 13). Numerical-score T-ESTOR controls exceed practical Slice by 987.93 and 1,178.47 on Linear and Convex at T=65,534T=65{,}534 (Table 17). These controls retain the original submitted formulas, not the sharpened theorem or the new certified policy. The plotted policies use calibrated multipliers and remain outside the current regret guarantees.

For the practical stopping rule, the matched adaptive-minus-fixed contrasts are −2.19-2.19 [−3.58,−0.89-3.58,-0.89] on Linear and −1.38-1.38 [−2.63,−0.28-2.63,-0.28] on Wave, relative to n0=4096n_0=4096 (Table 13). Replacing sample-mean bins with median-of-means bins on CCLE costs 8.26 [4.81,10.21] and 4.04 [3.49,4.47] (Table 16). These controls measure implementation choices; they do not prove their validity.

Theorem K.4 separately preserves the T2/3T^{2/3} horizon rate for bounded checkpoints within a T2/3T^{2/3}-order exploration budget, normalized bins, and sample-mean UCB under sub-Gaussian noise with full confidence radii. It does not justify the plotted stability heuristic or reduced multipliers. Gaussian CCLE noise satisfies the noise premise; Student-t3t_3 noise does not. The original finite-variance MOM theorem remains distinct.

AuthorsOpenReview ↗

To Reviewer CanC: W1 and Q2

2. Weakness 1 and Q2: Selected-signal assumptions and weaker signals

The signal condition has a useful instance-specific interpretation. For 0≤f′≤Lf0\le f'\le L_f, fixed Θ∗≠0\Theta_*\ne0, and base signal μ0>0\mu_0>0, every rule selecting one of KK iid candidates satisfies

\ge\mu_0^K/L_f^{K-1}.$$ Lemma K.3 proves this by layer cake and Jensen; the opposite-ranking ReLU example attains it. Thus positive base signal gives an all-direction floor on each fixed instance, but that floor can deteriorate exponentially in $K$. Monotonicity alone supplies no useful class-uniform floor, and a policy requiring its value still needs a valid supplied bound. The original Linear, Tanh, and Convex links have selected-signal floors 1, 1, and $1/2$. The nonmonotone links have base multiplier $1/2$ under the symmetric design, which is the signal used by T-BSTOR (Appendix K.4). For weaker signals we use $$g_a'(u)=a+\frac{1-a}{1+\exp(8u/s_0)},\qquad g_a(0)=0,$$ at $a\in\\{0.3,0.03,0\\}$ with the same dense design, normalization, Student-$t_3$ noise, $K=10$, and $T=32{,}766$. The all-direction floors $a+(1-a)2^{-K}$ are 0.300684, 0.030947, and 0.000977. In particular, $a=0$ is not a zero-signal instance. Transferred settings fail in all three conditions. A post-hoc recalibration evaluated nine configurations per method/condition on five development seeds, froze the winners, and evaluated them with transferred controls on ten fresh paired seeds. Table 20 reports: | $a$ | Transferred Slice minus Vec [95%] | Recalibrated Slice minus Vec [family-adjusted] | |---|---:|---:| | 0.3 | $+16.12$ [8.55,24.20] | $-21.55$ [$-24.18,-19.46$] | | 0.03 | $+41.91$ [26.93,57.55] | $-11.05$ [$-13.42,-8.13$] | | 0 | $+38.28$ [23.84,53.25] | $-8.37$ [$-10.86,-5.67$] | For $a=0.03$ and $a=0$, Slice changes only its threshold, from 0.0003 to 0.000075, retaining influence multiplier 16. Its own regret falls by 53.11 [36.76,70.03] and 47.67 [32.66,63.19], while uniform fallback falls from about 52% of rounds to below 0.01%. At $a=0.3$, both multipliers change. These interventions identify threshold transfer as a contributor to failure. They do not establish better parameter recovery: late fitted ranks increase and direction-error changes are mixed (Table 21). Five development seeds, finite grids, and boundary winners limit calibration conclusions. This is not a tuning rule for unknown links, and the smaller signal floors require stricter oracle tolerances. **Our unrestricted assumptions are not identical to ESTOR's.** Kang et al. (2026, Assumptions 2.2–2.3 and 3.3) do not state the same all-direction floor. The reported monotone comparisons lie in the common derivative-floor subclass $f'\ge c>0$, with $c=1,1,1/2$, so every selected law has signal at least $c$ for either method. This does not equate the full assumption sets or transfer Theorem K.2 to unpaired ESTOR (Appendix K.4).
Reviewer_RoT8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a low-rank single-index bandit problem over TT rounds. At round tt, the learner observes K≥3K \ge 3 candidates Xt=Xt,aa=1K⊂Rd1×⋯×dh\mathcal X_t=\\{X_{t,a}\\}_{a=1}^K\subset\mathbb R^{d_1 \times \cdots \times d_h}, picks Xt∈XtX_t \in \mathcal X_t, and observes a reward yt=f(⟨Xt,Θ⋆⟩)+ηty_t=f(\langle X_t,\Theta^\star\rangle)+\eta_t, where both the low-rank parameter Θ⋆\Theta^\star and the link function ff are unknown. The authors propose T-ESTOR, an adaptation of ESTOR [1] that estimates the low-rank parameter through Stein estimation and SVD with soft thresholding, and selects actions greedily over doubling epochs. When the link function is monotone and the selected-law scores can be computed exactly, they provide a regret guarantee which, when e.g. Θ⋆∈Rd1×d2\Theta^\star\in\mathbb R^{d_1\times d_2} is a rank-rr matrix, scales as O~(Kr(d+K)T)\widetilde O(K\sqrt{r(d+K)T}), where d=max⁡(d1,d2)d=\max(d_1,d_2). The authors also provide lower bounds and extend the method to non monotone link functions, yielding T-BSTOR, whose regret guarantee has a T2/3T^{2/3} dependence on the horizon rather than T\sqrt T, up to logarithmic factors. The authors additionally evaluate their methods on synthetic data and simulated bandit problems constructed from drug-response data.

[1] Yue Kang, Mingshuo Liu, Bongsoo Yi, Jing Lyu, Zhi Zhang, Doudou Zhou, and Yao Li. Single index bandits: Generalized linear contextual bandits with unknown reward functions. In The Fourteenth International Conference on Learning Representations, 2026. \url{https://arxiv.org/abs/2506.12751v3}.

Critical strengths

The low-rank single-index bandit problem considered is relevant, and the ability to exploit low-rank structure without knowing the link function is interesting. It is also notable that the rank does not need to be known by T-ESTOR. In my understanding, the low-rank Stein estimator is adapted from [1], and the main technical contribution of the paper is to make it compatible with the greedy epochs of ESTOR.

I found the regret analysis thorough. For T-ESTOR, the upper bound of Theorem 3.3 matches the lower bound of Theorem 3.4 in its dependence on the rank, dimension, and horizon. The upper and lower regret bounds for T-BSTOR (Theorems 3.5 and H.6) also match in their dependence on the horizon.

[2] Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low-rank matrix bandit problems. In Advances in Neural Information Processing Systems, volume 35, pp. 19971–19983. Curran Associates, Inc., 2022. doi:10.52202/068431-1452. URL https: //doi.org/10.52202/068431-1452.

Critical weaknesses

The main algorithm needs to compute the scores in (6), which seems potentially difficult even when the candidate distribution is known. Appendix C provides useful results on approximate scores and a construction for unknown product laws, but it gives worsened regret guarantees. It remains unclear to me whether the T\sqrt{T} regret dependence could be retained with a computationally practical approximation.

Questions for authors
  1. In Appendix I.3 it is said that the numerical diagnostics do not establish the conditions of Appendix C.7. Do you expect these conditions to be achievable with a computationally practical refinement of your numerical approximation?

  2. Why is ESTOR not included in the synthetic experiments of the main text? The comparison in Appendix J is useful, but I would have liked to see this baseline for the synthetic experiments with monotone links, since T-ESTOR is an adaptation of ESTOR and the other baselines do not appear to exploit monotonicity.

  3. In the matrix setting, Theorem 3.4 gives a lower bound of order K−1drTK^{-1}\sqrt{drT}, compared with the upper bound O~(Kr(d+K)T)\widetilde O(K\sqrt{r(d+K)T}) in Theorem 3.3, so there is a factor K21+K/dK^2\sqrt{1+K/d} between the two (as mentioned in Appendix F.1). Under stronger assumptions, Appendix F improves the upper bound to O~(Kr(d+K)T)\widetilde O(\sqrt{Kr(d+K)T}), but there is still a gap in the dependence on KK. Do you expect the K(d+K)\sqrt{K(d+K)} dependence to be necessary for T-ESTOR, or could a sharper analysis reduce it? More generally, what dependence on KK do you conjecture to be minimax optimal?

4 comments
AuthorsOpenReview ↗

To Reviewer RoT8: W1 and Q1 (1/2)

We sincerely thank you for the careful review and the constructive questions. We have carefully considered your concerns and provided a detailed explanation below. Please feel free to let us know if you have any additional concerns or questions.

Your concernHow we addressed itRevised location
Practical score approximation retaining square-root regret (Critical weakness; Q1)Proved a fixed-accuracy conditional policy guarantee and constructed product-beta certificates; reported their cost and the remaining implementation limits.Corollary 3.4; Theorem K.2; Appendices K.1–K.3 and L.5
Missing synthetic ESTOR baseline (Q2)Added a comparison on 20 fresh paired seeds, with all methods' outcomes and paired intervals.Figure 3; Table 8; Appendix L.1
Loose menu-size dependence and the minimax gap (Q3)Sharpened the selected-score moment and regret bounds; stated the remaining gap and qualified the conjecture.Theorem 3.3; Lemma E.1; Appendices F and F.1

The spectral estimator builds on Kang et al. (2022), your reference [2]. The additional analysis uses pairing to remove the unrestricted reward offset, controls selected-score spectral moments uniformly over ranking directions under dependent candidate laws, and transfers structured estimation error into regret. Sections 1 and 3 and Appendices E–H now make these steps explicit.

Critical weakness and Q1. Practical selected scores with T\sqrt T regret

Response to the weakness. Under Theorem 3.3's assumptions, Corollary 3.4 and Theorem K.2 retain the paired policy's square-root rate with fixed conditional scalar-correction accuracy, exact base scores, and valid tuning. Appendices K.1–K.2 give a product-beta certificate construction. This addresses the approximation-error question; computationally practical score access for general dependent laws remains unresolved.

For the frozen ranking direction viv_i, write αi=Fi′/Fi\alpha_i=F_i'/F_i. The score error is

=-(K-1)(\widehat\alpha_i-\alpha_i)(\langle v_i,X\rangle)v_i.$$ Consequently, the **raw paired statistic** has mean $\mu_i\Theta_*+\beta_i v_i$. Its component along $\Theta_*$ rescales the target, while its orthogonal component contracts with the preceding direction error. Pairing expresses the mean as a covariance, so a nonzero approximate-score mean introduces no additional reward-offset term. The proof controls nonlinear robustification around this raw mean; it does not assume that robustification preserves expectation. It suffices to freeze and certify the correction before collecting each epoch's observations, conditional on its start history, with $\displaystyle \varepsilon_i:=(K-1)\\|\widehat\alpha_i-\alpha_i\\|_{L^2(Q_i)} \le \frac{\mu_{\min}}{4L_f\sqrt{K\\|\Sigma_X\\|_{\mathrm{op}}}},$ where $Q_i$ is the conditional law of $\langle v_i,X\rangle$ under the selected law $p_i$, with CDF $F_i^K$. Valid signal and covariance bounds are supplied. The rescaled target multiplier is at least $3\mu_{\min}/4$, and the relative errors satisfy $\displaystyle \widehat w_i=(\sqrt{w}+\varepsilon_i)^2, \qquad w=2M(Kd+K-1).$ With doubling epochs, the statistical term has inverse-square-root sample-size order up to logarithms, and the convolution ratio is $\sqrt2/3<1$. Thus the policy retains square-root horizon regret, with the explicit bound in Theorem K.2, equation (50). Theorem 3.1's tuning must use a valid approximate-score moment bound, for example $$\widehat w_i=(\sqrt{w}+\varepsilon_i)^2, \qquad w=2M(Kd+K-1).$$ The tolerance is independent of $T$ and has no explicit dimension or rank factor when signal and covariance bounds are fixed. Appendix C.7's decreasing-error requirement is therefore unnecessary for this directional approximation with exact base scores. Generic learned-score errors need not have this form, and the result does not establish unpaired ESTOR's guarantee. **Certification and cost.** Appendices K.1–K.2 bound selected-law MSE from certified density/CDF errors, including the floored tail. For product-beta candidates, explicit Fourier coefficients and truncation bounds permit interval-arithmetic certification of the stored interpolation functions. At $K=10$, $L_f=3/2$, $\mu_{\min}=1/2$, and $\Sigma_X=I/11$, the sufficient scalar-ratio MSE is $11/116640\approx9.431\times10^{-5}$.
AuthorsOpenReview ↗

To Reviewer RoT8: W1 and Q1 (2/2); Q2

All 38 checked functions pass, with maximum bound 4.202×10−64.202\times10^{-6}: 27 directions from the dense monotone runs, nine from threshold-adjusted d=16d=16 runs, and two reference cases. Historical grid nodes were not archived, so these are reconstructed functions at saved directions. Separately, six guarded/unguarded trajectory pairs at T=8,190T=8{,}190 certified all 54 distinct nonzero directions before use and produced identical action sequences. Total policy times increased from 16.4–20.5 s to 56.5–75.8 s (Appendices K.3 and L.5). Certification is invoked O(log⁡T)O(\log T) times; this is not a bound on construction time or a guarantee that every resource-limited construction succeeds.

These certificates cover real-arithmetic evaluation of the declared functions. The policy guarantee additionally requires valid certificates at every used direction and the stated statistical tuning; it does not cover the practical multipliers or full floating-point pipeline. With submitted theorem-prescribed tuning, T-ESTOR incurs 987.93 and 1,178.47 more regret than tuned T-ESTOR-Slice on Linear and Convex (Table 13). These controls use the submitted moment bound, which exceeds the sharpened bound by less than 10% at the tested dimensions and still satisfies the moment requirement; they do not execute the new certified policy (Appendices K.3 and L.3). The original signal-floor certificates also do not certify the weak-signal recalibration runs, which require stricter tolerances.

Q2. Why was ESTOR missing from the synthetic comparison?

We agree that ESTOR should have been included. Figure 3 presents the separate matched monotone comparison, and Table 8 reports the paired contrasts and intervals. Figure 1 retains the original six-link, 50-seed comparison. ESTOR, T-ESTOR-Vec, Mat, and Slice receive the same evaluation streams. The three T-ESTOR variants share the paired epoch framework; ESTOR retains its published estimator and schedule. Settings were selected on separate development data before evaluation on 20 fresh paired seeds at T=65,534T=65{,}534.

Mean final-regret differences are below; negative values favor Slice.

LinkSlice minus ESTORSlice minus VecSlice minus Mat
Linear−78.09-78.09−60.38-60.38+20.59+20.59
Tanh perturbation−122.60-122.60−80.86-80.86+16.60+16.60
Smooth convex−117.15-117.15−89.21-89.21+14.59+14.59

All six ESTOR/Vec individual paired-bootstrap 95% intervals favor Slice; all three Mat comparisons favor Mat (Table 8). Slice–Vec examines structured estimation within the paired framework. The ESTOR comparison additionally changes pairing, robustification, and update conventions, so it does not attribute the full improvement to structure alone. The dense design gives Mat and Slice the same structural scale 128 but rank-constrained parameter counts 156 and 240; it does not demonstrate a tensor-specific advantage. Appendix F.1 and Table 9 give the separating construction and its comparison.

On the fresh 20-seed CCLE-derived Linear task, Slice minus ESTOR is −32.30-32.30 [−33.18,−31.45-33.18,-31.45] (Table 12). Table 14 separately reports weak-signal failures with settings selected on Linear and fresh evaluation after post hoc recalibration; this supplies no general tuning rule for unknown links.

AuthorsOpenReview ↗

To Reviewer RoT8: Q3

Q3. Is the dependence on KK necessary, and what is minimax optimal?

The extra +K+K inside the original (d+K)(d+K) factor is an artifact of the moment bound. A sharper analysis removes it; the remaining minimax dependence on KK is unresolved.

Sharper upper bound. Under Assumption 2.1, splitting the projected Fisher information on both sides of a point gives, for every unit ranking direction, (Fv′)2≤MFv(1−Fv).(F_v')^2\le M F_v(1-F_v). Under maximum selection, Fv(⟨v,X⟩)F_v(\langle v,X\rangle) has density KzK−1Kz^{K-1} on (0,1)(0,1), yielding Epi[(Fi′/Fi)2]≤MK−1.\mathbb E_{p_i}\left[(F_i'/F_i)^2\right]\le \frac{M}{K-1}. The resulting selected-score moment bound is w=2M(Kd+K−1),w=2M(Kd+K-1), replacing MGK(d)≍MK(d+K)MG_K(d)\asymp MK(d+K). Substitution into the regret analysis gives

\qquad \widetilde O\left(\sqrt{Kdr_UT}\right) \quad\text{under the sub-Gaussian projection condition (9)},$$ with signal and design constants, including $\kappa_X$ for the refined rate, fixed. In the matrix case $r_U=r$. Relative to the existing lower bound in Theorem 3.5, the respective gaps are $K^2$ and $K^{3/2}$ up to logarithms. Theorem 3.3, Lemma E.1, and Appendix F now incorporate this refinement. The moment inequality itself holds for $K>1$. It also makes the order-$\sqrt d$ separation between the slice and unfolding upper-bound factors in Appendix F.1 uniform over admissible $K$; this remains a comparison of upper bounds. *What remains.* The leading dimensional term uses the worst-case domination $p_i\le Kp$ to control the base score. The correction bound also grows with $K$, and the general regret conversion contributes an additional $\sqrt K$, replaced by a logarithmic factor under (9). Thus improving the remaining dependence requires more than the refinement above. On the product-beta design, offline diagnostics at $d=16$ give median empirical slice-score moments of 237.75 and 252.54 at $K=3$ and $K=100$, respectively, while $w$ grows from 1,200 to 40,776. The full correction moment increases from 11.80 to 113.00, against bounds of 24 and 1,188 (Appendix L.5, Table 17). These measurements use the true-coefficient ranking direction and characterize moments, rather than online regret or all adaptive directions. Our tentative conjecture is that, for the product-beta subclass with a $K$-uniform positive signal floor and fixed model constants, the minimax dependence beyond the $\sqrt{drT}$ factor is at most polylogarithmic in $K$. The present bounds do not establish this, and sub-Gaussian projections alone do not control score moments sufficiently to justify the same conjecture for the entire class in (9). We leave the sharp dependence under Assumption 2.1 open. Holding the signal floor fixed is essential: in the opposite-ranking ReLU example of Appendix E.3, it can decay as $2^{-K}$.

Thank you for your answer and the additional clarifications, particularly regarding Q2 and Q3. I intend to keep my score.

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

The paper studies stochastic matrix and tensor bandits whose rewards depend on a low-rank parameter through an unknown shared Lipschitz link.

To my understanding the operational chain is: i) collect observations through uniform exploration; ii) estimate the parameter direction using paired reward–score statistics, robust averaging, and singular-value shrinkage; iii) for increasing links, select actions greedily and periodically re-estimate the direction while correcting for selection bias; iv) for nonmonotone links, freeze the estimated direction and learn rewards over scalar bins using robust confidence bounds. The tensor version applies structured estimation to transformed matrix slices.

Under the stated distributional and signal assumptions, the paper establishes square-root regret with structural dimension dependence for monotone links and a T^{2/3} horizon rate for nonmonotone links, together with lower bounds and synthetic and semisynthetic experiments.

Critical strengths

i) The guarantees show a useful benefit from exploiting low-rank structure. A low-rank parameter can be dense, so methods exploiting coordinate sparsity do not automatically capture its structure. The paper obtains regret bounds with reduced dimension dependence while allowing an unknown reward function. For nonmonotone links, the improvement concerns structural dependence and robustness, while retaining the established (T^{2/3}) horizon rate. This is a meaningful extension of existing single-index bandit methods.

ii) The lower bounds help establish the significance of these guarantees. For monotone links, the lower bound matches the rank, dimension, and horizon dependence up to logarithmic factors at sufficiently large horizons, with other parameters fixed. For nonmonotone links, the paper establishes (T^{2/3}) difficulty with a fixed menu size and a signal bounded away from zero, even when the parameter is known. This strengthens the construction of Dey et al. (2026) and shows that learning the unknown reward curve remains intrinsically difficult under these conditions.

Critical weaknesses

i) The methodological novelty is limited, making the significance depend mainly on the new analysis. The estimation and decision procedures build substantially on existing low-rank Stein estimators, ESTOR, and ZoomSIB-UCB. These connections are acknowledged. While the structured guarantees and strengthened lower bounds appear useful, my limited examination leaves some uncertainty about how substantial the additional technical contribution is. A concise explanation of the main obstacle that prevents the results from following through existing arguments would help clarify this. I remain open to update my score with this regard.

ii) The practical scope and the distinctive benefit of the tensor extension remain insufficiently established. The main guarantees require a known regular candidate distribution and, for T-ESTOR, access to selected-distribution scores. These requirements may be difficult to satisfy outside controlled settings. The experiments support gains from exploiting structure, but the main synthetic setup gives the matrix and tensor representations the same structural complexity. It therefore provides limited evidence about when the tensor extension offers an advantage over matrix unfolding.

Questions for authors
  1. What is the main technical obstacle beyond combining existing low-rank estimators with ESTOR or ZoomSIB-UCB?

  2. Can you demonstrate gains over matrix unfolding and report the computational cost of selected-distribution scores?

6 comments
AuthorsOpenReview ↗

To Reviewer epYn: W1 and Q1

We sincerely thank you for the careful review and the constructive questions. We have carefully considered your concerns and provided a detailed explanation below. Please feel free to let us know if you have any additional concerns or questions.

Your concernHow we addressed itRevised location
Limited novelty and unclear additional technical work (Weakness 1; Q1)Explained the selected-law spectral bounds and fresh-menu regret transfer, and clarified the strengthened lower bounds.Section 1; Lemma E.1; Appendix F; Theorems 3.3, 3.5 and H.6
Distinct tensor benefit over unfolding (Weakness 2; Q2)Added separating-design comparisons; retained Mat's advantage on the dense design and the threshold-transfer failures.Section 4; Appendix F.1; Tables 8–9; Appendices L.1–L.2
Practical score access and computational cost (Weakness 2; Q2)Added conditional numerical-score guarantees and measured costs. Known-law access and general-law oracle construction remain limitations.Corollary 3.4; Appendices K.1–K.3 and L.5; Section 5

Weakness 1 and Q1. Technical contribution beyond existing methods

We agree that spectral shrinkage, ESTOR's epochs, and its selected-density identity build on prior work. The contribution is the analysis needed to preserve rank dependence when greedy selection changes the observation law, together with the strengthened lower bounds. For monotone links, existing arguments do not directly give the structural T\sqrt T guarantee:

  • Low-rank Stein estimation from uniform exploration followed by commitment uses base-law data; the usual exploration/estimation-error balance gives O~((drU)1/3T2/3)\widetilde O((d r_U)^{1/3}T^{2/3}) for fixed menu size and model constants.
  • ESTOR learns from selected observations, but its stated vector analysis gives O~(NK3/2T)\widetilde O(NK^{3/2}\sqrt T), with ambient dimension NN.

Two steps close this gap.

  1. Selected-law spectral moments (Appendix E.3, Lemma E.1). Greedy selection adds a score correction along the history-dependent direction viv_i, proportional to Fi′/FiF_i'/F_i. This ratio can diverge near the lower end of the projection support, and selection couples coordinates and slices even under a product law. Spectral estimation requires left and right operator second moments. From the joint score certificate we bound both uniformly over ranking directions. The refined projection argument gives

    \mathbb E_{p_i}(F_i'/F_i)^2\le M/(K-1),$$ and hence $w=2M(Kd+K-1)$, where $d=\max(d_1,d_2)$. The same bound holds for every transformed slice, with no extra factor $q$ and no independence assumption across slices.
  2. Fresh-menu transfer (Lemma F.1). For E=Θ^−μΘ∗E=\widehat\Theta-\mu\Theta_*, the worst-case bound ∣⟨X,E⟩∣≤AN∥E∥F|\langle X,E\rangle|\le A\sqrt N\|E\|_F would reintroduce ambient dimension. We instead use the covariance of the fresh menu to obtain conditional regret at most

    2Lfμmin⁡K∥ΣX∥op ∥E∥F.\frac{2L_f}{\mu_{\min}}\sqrt{K\|\Sigma_X\|_{\mathrm{op}}}\,\|E\|_F.

Theorem 3.3 and Appendix F now incorporate the sharper bound, giving O~(KdrUT)\widetilde O(K\sqrt{d r_U T}), or O~(KdrUT)\widetilde O(\sqrt{K d r_U T}) under the sub-Gaussian projection condition (9), with κX\kappa_X and the other model/design constants controlled. Both recover structural O~(drUT)\widetilde O(\sqrt{d r_U T}) regret for fixed KK. Even vectorization gives the refined bound O~(KNT)\widetilde O(K\sqrt{NT}), improving on ESTOR's stated upper bound on the shared product-design subclass with comparable budgets and signal floors (Appendix F.1).

Pairing also removes the unrestricted offset f(0)f(0) from the moments needed for spectral robustification. For arbitrary links, Lemma H.3 supplies finite-variance confidence bounds for adaptively sampled bins with varying conditional means and random observation counts.

The lower bounds are a separate contribution. For every admissible design, Theorem 3.5 matches the monotone rank, dimension, and horizon dependence up to logarithms at sufficiently large horizons, with KK and model/design constants fixed. For nonmonotone links, Theorem H.6 establishes the T2/3T^{2/3} difficulty at fixed menu size and a positive signal floor even when the parameter is known. Dey et al. (2026) instead grow the menu and shrink the signal floor. Our hard links can additionally satisfy the uniform selected-signal condition while remaining nonmonotone. These lower bounds complement the structural upper analysis.

The separate 20-seed matched comparison provides complementary evidence: Slice minus Vec regret is −60.38-60.38, −80.86-80.86, and −89.21-89.21 on Linear, Tanh, and Convex (Figure 3, Table 8); separately, removing the selected-score correction increases regret by 180.94, 197.88, and 202.44 (Table 16). Section 1 now explains the analytical obstacle explicitly.

AuthorsOpenReview ↗

To Reviewer epYn: W2 and Q2 (1/2)

Weakness 2 and Q2. Practical scope, tensor benefit, and score computation

The revision adds separating-design comparisons and computational costs. It does not remove the known-law requirement or construct a practical oracle for general dependent designs.

When tensor structure helps. Low-rank slices may have different row and column spaces, so unfolding can lose the useful rank restriction. In Appendix F.1's dense d×d×dd\times d\times d construction, every slice has rank one, giving structural scale d2d^2, while all three unfoldings have rank dd and shape d×d2d\times d^2, giving scale d3=Nd^3=N. Under the same candidate law and linear link, this yields an order-d\sqrt d separation between the slice and unfolding upper-bound factors, uniformly for admissible KK.

Rank dd imposes no restriction on those unfolded matrices, and Theorem 3.5 gives an Ω(NT)\Omega(\sqrt{NT}) lower bound over the full unfolded parameter class at sufficiently large horizons, with KK and other constants fixed. This class comparison does not assert that every unfolding algorithm incurs that regret on the specific F.1 tensors.

The original 16×16×416\times16\times4 design does not separate these structures: Mat and Slice both have structural scale 128. Their rank-constrained parameter counts are 156 and 240, respectively, and Mat performs better (Table 8). This is consistent with a more economical matrix model, without identifying parameter count as the sole cause. The separating construction supplies the distinct tensor case.

Separating-design experiments. Table 9 compares Slice with all three mode unfoldings within T-ESTOR, sharing menus, noise streams, and epoch schedules. On the exact F.1 construction at d=8d=8 (Linear, K=10K=10, T=32,766T=32{,}766, 20 paired seeds), Slice minus modes 1–3 is −37.04-37.04, −38.17-38.17, and −45.98-45.98, with intervals [−39.29,−34.73][-39.29,-34.73], [−40.50,−35.71][-40.50,-35.71], and [−48.38,−43.72][-48.38,-43.72]. Settings were selected on separate Hadamard d=8d=8 development data, without the later threshold rescaling.

The fresh Hadamard study uses ten paired seeds per dimension and reuses the settings selected at d=8d=8 across dimensions. These settings favor Slice against every unfolding at d=4,8d=4,8, but fail at d=16d=16: the three differences are +58.26+58.26, +58.63+58.63, and +55.44+55.44. Slice's robust singular values fell below its threshold, producing zero fits and essentially uniform play. The earlier Hadamard evaluation cohort has the same dimension-wise signs and is reported separately in Table 9.

Following that failure, a common threshold factor 0.25 was selected offline and applied to every structured comparator, with all other settings unchanged. Both settings were evaluated on the same fresh seeds, disjoint from those used to choose the factor. At d=16d=16, Slice regret falls from 237.72 to 52.82, and the three unfolding contrasts become −54.20-54.20, −53.72-53.72, and −53.86-53.86. At d=4,8d=4,8, the same factor worsens Slice's own regret by 7.24 and 17.12 (Appendix L.2). This is a post-hoc threshold-sensitivity study, not dimension-specific development tuning or a general calibration rule. Each three-mode family in Table 9 has nominal simultaneous 95% intervals excluding zero in the stated direction; there is no adjustment across settings. Appendix L.2 gives the full protocol and adverse findings.

Cost of selected scores. For product-beta candidates, the additional distribution-specific calculation is the one-dimensional law of ⟨vi,X⟩\langle v_i,X\rangle, constructed by Fourier convolution for each frozen nonzero epoch direction. At N=1024N=1024, numerical oracle construction takes a median 1.52 s per construction, accounting for 43.1% of pooled online time on an Intel i7-1065G7 with one thread (Appendices I.3 and L.5). This excludes the separate certification overhead reported below. The 0.344 μ0.344\,\mus correction-query figure is a batched microbenchmark with precomputed projections, not per-round latency.

For three threshold-adjusted d=16d=16 Slice runs (N=4096N=4096, grid 8,192, T=32,766T=32{,}766, one numerical thread), construction totals average 69.99 s per trajectory (66.56–72.86 s). Scalar-ratio evaluation plus directional-score application average 0.717 s per trajectory. These timers exclude projection, base-score evaluation, fitting, and environment generation (Appendix L.5). They are not a controlled scaling benchmark. T-BSTOR uses only base scores.

AuthorsOpenReview ↗

To Reviewer epYn: W2 and Q2 (2/2)

Numerical approximation and scope. Corollary 3.4 and Theorem K.2 establish that fixed, sufficiently small conditional selected-law error in the scalar correction preserves the paired policy's T\sqrt T rate, with exact base scores, supplied valid signal/covariance bounds, and statistical tuning using w^i=(w+εi)2\widehat w_i=(\sqrt{w}+\varepsilon_i)^2. This is a conditional policy guarantee. For our product-beta constants and signal floor 1/21/2, the scalar-ratio MSE tolerance is 11/116640≈9.431×10−511/116640\approx9.431\times10^{-5}; at K=10K=10, the corresponding full directional-score MSE tolerance is 11/1440≈7.639×10−311/1440\approx7.639\times10^{-3}.

All 38 reconstructed functions have scalar-ratio MSE certificates at most 4.202×10−64.202\times10^{-6}. Historical grid nodes were not archived, so the functions were rebuilt at saved directions. A separate six-pair guarded study certified all 54 used nonzero directions before use, with unchanged actions; total policy times rose from 16.4–20.5 s to 56.5–75.8 s at T=8,190T=8{,}190 (Appendices K.3 and L.5). These function certificates do not validate practical statistical multipliers or the full floating-point policy. The plotted calibrated implementations remain outside the stated regret guarantees; Appendix L.3 reports the conservative outcomes with submitted theorem-prescribed tuning.

The known candidate law remains a substantive restriction, natural when menus are generated by a chosen randomization law. The theory permits dependent and noncentered designs, but the constructive oracle is specific to product-beta laws; general laws still require the stated score access. Appendix C studies unknown smooth product laws with a separate, slower-rate policy. A constructive T\sqrt T guarantee for greedy epochs with learned selected scores remains open. Section 2.3 and the conclusion state these limits.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.