- 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 regret for monotone links, given selected-score access and a positive-signal assumption. For arbitrary Lipschitz links, T-BSTOR adds scalar binning and achieves regret under a nonzero-signal assumption. The lower bounds match the rank dependence for monotone links at large horizons and the rate for nonmonotone links. Synthetic and CCLE-derived experiments compare the methods with vectorized and existing bandit baselines.
Critical strengths
-
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.
-
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 rate in the nonmonotone case under the stated conditions.
Critical weaknesses
-
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.
-
The experiments do not sufficiently isolate or establish the benefit of the proposed structure. The main synthetic evaluation uses one 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
-
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?
-
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 . 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?
-
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
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
using Theorem 3.1's tuning with , where . The directional error makes the raw paired mean : 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 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 directions, and two reference cases. The maximum scalar-ratio MSE bound is , below for the original signal floor . 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 , 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 (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 [] on Linear and [] on Wave, relative to (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 horizon rate for bounded checkpoints within a -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- noise does not. The original finite-variance MOM theorem remains distinct.
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 , fixed , and base signal , every rule selecting one of 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).
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.