- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper studies contextual bandits with several rewards ordered by priority. VA-LGLB combines weighted regularized estimation, residual-based variance estimates, and an elimination rule intended to preserve the lexicographic optimum. Under a known trade-off bound , Theorem 2 claims
\qquad \Lambda_i=\sum_{j=0}^{i-1}\lambda^j,$$ with additional dependence on the link and model constants. This expression assumes ordered objective variances; Appendix E replaces $\sigma_t^i$ with $\max_{j\le i}\sigma_t^j$ otherwise. Online-LGLB uses projected online Newton updates and obtains a worst-case $\widetilde O(\Lambda_i d\sqrt T)$ bound. Experiments use a ten-arm synthetic problem and Gaussian rewards calibrated to 16 SW-LLVM compiler configurations, with ten runs per setting.Critical strengths
The elimination argument is the strongest contribution. A later objective may favor an arm that loses on an earlier one, so applying independent elimination rules would be unsafe. Algorithm 2 uses the largest preceding confidence radius and a threshold derived from the trade-off assumption. Lemma 5 explains how this preserves the lexicographic optimum and bounds the gaps of surviving arms. This is a concrete adaptation to hierarchical decisions, and it supports both the variance-adaptive and online algorithms.
Critical weaknesses
-
The residual comparison drops a term that matters precisely at low noise: On p. 19, the bound preceding Eq. (16) contains . The next line absorbs this into , although the stage threshold does not depend on . Regularized estimates can have nonzero residuals even with noiseless observations.
A finite example occurs in the paper’s identity-link special case. Take , , , , , and a singleton arm with deterministic reward . Algorithm 1 first samples at stage , with weight . At , and Eq. (3) gives . The weighted residual is approximately . For the valid noise bound , Lemma 3’s second upper bound is only . The lemma is subsequently used in Eq. (31) to prove Theorem 2.
-
The statistical novelty needs a more precise comparison: Di et al. Sections 4.2–4.3 [1] already use nonlinear regularized estimation, residual-based unknown-variance confidence bounds, and a regret rate. Their feedback and regret are different: a dueling-bandit result does not subsume this numerical, multi-objective problem. Nevertheless, the confidence constructions are close. The current discussion does not explain which steps need new analysis under the feedback model here, beyond transferring the variance machinery and proving the lexicographic elimination result. That distinction affects my assessment of the paper's contribution.
[1] Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits, https://arxiv.org/html/2310.00968. International Conference on Learning Representations (ICLR), 2024.
Questions for authors
- Can Lemma 3 be corrected while retaining regularization bias, and how does the correction propagate through Eq. (31) and Theorem 2? Does it require an additional restriction involving ?
- Which part of the nonlinear variance-estimation analysis goes beyond the construction of Di et al. [1], as distinct from the new lexicographic elimination argument?
- What features and link functions were used for SW-LLVM, and what value of was supplied? These details determine whether the experiment instantiates the model being analyzed.
[1] Qiwei Di, Tao Jin, Yue Wu, Heyang Zhao, Farzad Farnoud, and Quanquan Gu. Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits, https://arxiv.org/html/2310.00968. International Conference on Learning Representations (ICLR), 2024.
2 comments
Response to W2Ts (2/2): Contribution and Answers to Questions
W2. VACDB already has nonlinear regularized estimation, residual-based unknown-variance confidence bounds and the analogous regret order; the paper should distinguish transferred machinery from new analysis.
We clarified the contribution in Section 1 and explicitly credited VACDB (Di et al., 2024) in Table 1 and Appendix A. Its layering and residual-based variance estimation are tools we build on. To the best of our knowledge, VA-LGLB is the first algorithm to provide variance-aware regret guarantees for multi-objective bandits, without requiring prior knowledge of reward variances. The contribution is the resulting multi-objective guarantee and stronger numerical-reward GLB bounds, rather than the invention of the scalar estimation tools.
Model differences. VACDB selects two arms, observes a binary comparison on difference features, and measures average latent-utility regret; its Bernoulli variance is determined by the comparison probability. We select one arm, observe numerical vector rewards with unknown bounded-noise variances not fixed by their means, and measure each objective's mean-reward regret against a lexicographic optimum. VACDB's theorem therefore does not directly establish our result.
Additional analysis and guarantee. Different objectives have different confidence widths, so later-objective elimination must account for uncertainty in earlier priorities. The prefix radius and trade-off threshold yield optimum preservation and surviving-arm gap control in Lemma 5. Theorem 2 and its unordered-variance corollary then give, with probability at least ,
with fixed model constants suppressed. Under variance ordering, this depends on objective 's own cumulative variance. Relative to Zhao et al. (2023b), even the single-objective case removes supplied per-round variance bounds and reduces the variance-independent remainder from to . Using established techniques to obtain these guarantees is the contribution; a new scalar variance-estimation principle is not required for that advance.
Practical value. In Figure 6 (Appendix C.3), disabling only secondary filtering leaves primary-regret trajectories unchanged, but increases secondary regret: VA-LGLB achieves a 43.7% reduction and 100% versus 16.64% final-window lexicographic-optimum selection. Figures 3–5 (Appendices C.1–C.2) add shared-feature tests, matched variance ablations, MTLO and scalarization comparisons. The low-noise gains are demonstrated in the tested settings; high-noise results and the coincident trajectories in the four-arm nonlinear ablation are also reported.
Response to the Questions
Q1. Can Lemma 3 be corrected while retaining regularization bias, and how does the correction propagate through Eq. (31) and Theorem 2? Does it require an additional restriction involving B/R?
Yes. W1(b)–(d) gives the corrected residual bounds, variance proxy and propagation to Theorem 2. The original regret order is preserved for fixed model constants, with revised constants and no additional restriction.
Q2. Which part of the nonlinear variance-estimation analysis goes beyond Di et al., as distinct from the lexicographic elimination argument?
The scalar estimation machinery is inherited; the additional analysis coordinates heterogeneous objective-wise confidence sets and propagates their variances into lexicographic regret guarantees. W2 explains the model differences and resulting contribution.
Q3. What features and link functions were used for SW-LLVM, and what value of lambda was supplied?
Figure 2 (Appendix B) uses 16 configurations with identity features , the identity link , and . The four compiler bits identify the configurations; they are not the learner's features. Rewards are Gaussian draws calibrated to the recorded means and variances.
Figure 6 (Appendix C.3) uses all 1,024 configurations in a memory-first task, also with identity features and the identity link, and . It directly replays recorded rewards without added noise.
Thank you again for your time and thoughtful feedback. We would be happy to answer any further questions during the discussion phase.
Response to W2Ts (1/2): Residual Bias and Regret Proof
We thank the reviewer for recognizing the value of our elimination procedure in coordinating hierarchical decisions and preserving the lexicographic optimum. We appreciate the time and care devoted to reviewing our work and providing constructive comments and suggestions. We respond point by point below.
Responses to the Weaknesses
We verified the counterexample, corrected the regularization-bias terms in Lemma 3, updated the variance proxy in Algorithm 1, and propagated the correction through the confidence bound to Theorem 2.
(a) Confirmation of the counterexample. The reviewer's example is valid: θ=1/65537 gives weighted residual E=1/655372≃2.3282×10−10, exceeding the original bound 7R2γt≃6.2625×10−19 despite zero noise variance. The omitted contribution is regularization bias; constraining the estimator alone does not fix it.
(b) Corrected residual comparison. Let hs=2−s, E be the weighted squared residual sum, v=∑τ∈Ψt,s(wτστi)2, and γt=ln(8t2mS/δ), accounting for the split probability budget. Retaining the B term in the prediction-error bound and applying Lemmas 1–2, the high-layer bounds in Lemma 3 become
E\le4v+7R^2\gamma_t+8h_s^2L^2B^2.$$ **(c) Corrected proxy and confidence bound.** Algorithm 1 now uses $\widehat{\mathrm{Var}}=E+4h_s^2L^2B^2$ in high layers. Consequently, $$v\le8\widehat{\mathrm{Var}}+18R^2\gamma_t,\qquad \widehat{\mathrm{Var}}\le4v+7R^2\gamma_t+12h_s^2L^2B^2.$$ The first inequality turns Lemma 1 into the computable confidence bound in **Theorem 1**; the second controls the radius in the regret proof. Radii are computed at estimator updates and retained between updates, as in Algorithm 1. **(d) Propagation to Theorem 2.** Under the high-layer gate, the additional radius contribution in the argument corresponding to original Eq. (31) satisfies $$\frac{16\sqrt{96}\,h_s^2LB\sqrt{\gamma_t}}{\kappa}\le\sqrt6\,h_sB.$$ Using **Lemma 8** and the layer sample-count bound, this contributes only $\widetilde O(\Lambda_i dLB)$ to high-layer regret. The revised proof uses disjoint layer assignments and uniform upper envelopes for stored radii, accounts for initialization, and bounds the terminal branch using **Lemma 7**. Combining the low-layer, high-layer and terminal terms gives the explicit bound in **Appendix E, Eq. (31)** $$R^i(T)\le\widetilde O\left(\Lambda_i d\left[\frac L\kappa\sqrt{\mathcal V_i}+(U+R+1)\frac{L^2}{\kappa^2}+LB\right]\right), \qquad \mathcal V_i=\sum_t\max_{j\le i}(\sigma_t^j)^2.$$ **No additional $B/R$ restriction is needed, including at zero noise.** For fixed $B,R,U$, this preserves the original regret order and displayed curvature powers, with revised constants. Under variance ordering, $\mathcal V_i$ reduces to $\sum_t(\sigma_t^i)^2$.