acceptodds
Under review as a conference paper at ICLR 2027

Variance-Aware Lexicographic Generalized Linear Bandits: Unknown Variance and Tighter Bounds

Abstract

This paper investigates the Lexicographic Multi-Objective Generalized Linear Bandit problem, in which a learner optimizes hierarchically ordered objectives by sequentially selecting arms and observing their corresponding reward vectors. While multi-objective bandits have been widely studied, existing work largely overlooks the exploitation of reward variance. Furthermore, current variance-aware approaches for generalized linear bandits typically require prior knowledge of the variance and suffer from a suboptimal variance-independent regret term of . To address these limitations, we propose a novel variance-aware algorithm that achieves a regret bound of for any objective , where , , and represent the reward variance, arm dimension, and time horizon, respectively. Crucially, our algorithm eliminates the need for prior variance knowledge and significantly reduces the variance-independent term to . While this method relies on maximum likelihood estimation, which can be computationally intensive, we further propose a computationally efficient online alternative that achieves a regret bound of . Finally, we validate our theoretical findings through both numerical simulations and real-world experiments.

Primary area:
learning theory
Keywords:
bandits, multi-objective, variance-aware, regret bounds

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 4 reviews, above 68% of the others.
Reviewer_W2TsOpenReview ↗
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 λ\lambda, 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
  1. The residual comparison drops a term that matters precisely at low noise: On p. 19, the bound preceding Eq. (16) contains 2(6Rγt+κB)22(6R\gamma_t+\kappa B)^2. The next line absorbs this into R2γtR^2\gamma_t, although the stage threshold does not depend on B/RB/R. Regularized estimates can have nonzero residuals even with noiseless observations.

    A finite example occurs in the paper’s identity-link special case. Take d=m=B=κ=L=U=1d=m=B=\kappa=L=U=1, θ∗=1\theta^*=1, T=65536T=65536, S=24S=24, δ=0.05\delta=0.05, and a singleton arm x=2−15x=2^{-15} with deterministic reward y=xy=x. Algorithm 1 first samples at stage s=8s=8, with weight w=1/2w=1/2. At t=2t=2, sˉt=8\bar s_t=8 and Eq. (3) gives θ^=1/65537\hat\theta=1/65537. The weighted residual is approximately 2.33×10−102.33\times10^{-10}. For the valid noise bound R=10−10R=10^{-10}, Lemma 3’s second upper bound is only 7R2γt≈6.26×10−197R^2\gamma_t\approx6.26\times10^{-19}. The lemma is subsequently used in Eq. (31) to prove Theorem 2.

  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 d∑tσt2+dd\sqrt{\sum_t\sigma_t^2}+d 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
  1. 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/RB/R?
  2. 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?
  3. What features and link functions were used for SW-LLVM, and what value of λ\lambda 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
AuthorsOpenReview ↗

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

W1. The residual comparison drops a regularization term that remains nonzero at low or zero noise; the singleton example violates Lemma 3's second bound and affects Eq. (31) and Theorem 2.

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\widehat\theta=1/65537 gives weighted residual E=1/655372≃2.3282×10−10E=1/65537^2\simeq2.3282\times10^{-10}, exceeding the original bound 7R2γt≃6.2625×10−197R^2\gamma_t\simeq6.2625\times10^{-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−sh_s=2^{-s}, EE be the weighted squared residual sum, v=∑τ∈Ψt,s(wτστi)2v=\sum_{\tau\in\Psi_{t,s}}(w_\tau\sigma_\tau^i)^2, and γt=ln⁡(8t2mS/δ)\gamma_t=\ln(8t^2mS/\delta), accounting for the split probability budget. Retaining the BB 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$.
AuthorsOpenReview ↗

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 βˉi=max⁡j≤iβ^j\bar\beta^i=\max_{j\le i}\widehat\beta^j 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 1−δ1-\delta,

Ri(T)≤O~(Λid[∑tmax⁡j≤i(σtj)2+1])R^i(T)\le\widetilde O\left(\Lambda_i d\left[\sqrt{\sum_t\max_{j\le i}(\sigma_t^j)^2}+1\right]\right)

with fixed model constants suppressed. Under variance ordering, this depends on objective ii'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 O~(dT)\widetilde O(\sqrt{dT}) to O~(d)\widetilde O(d). 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 B/RB/R 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 xa=ea∈R16x_a=e_a\in\mathbb R^{16}, the identity link μ(z)=z\mu(z)=z, and λ=0.9\lambda=0.9. 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 λ≃0.282523\lambda\simeq0.282523. 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.

Reviewer_TctMOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies generalized linear bandits with mm lexicographically ordered objectives, where each reward coordinate follows μi(x⊤θ⋆i)+ϵti\mu^i(x^\top\theta^i_\star) + \epsilon^i_t with unknown variance (σti)2(\sigma^i_t)^2, regret is measured per objective against the lexicographically optimal arm, and Assumption 4 bounds cross-objective trade-offs by a parameter λ\lambda. The authors propose VA-LGLB, a SupLin-style layered algorithm with weighted MLE per layer, residual-estimated variance in the confidence radius, and a lexicographic elimination routine using the surrogate radius βˉi=max⁡j≤iβ^j\bar\beta^i = \max_{j \le i}\hat\beta^j. They claim objective-wise regret O~(Λid(Lκ∑t(σti)2+L2κ2+L))\tilde O(\Lambda_i d(\tfrac{L}{\kappa}\sqrt{\sum_t(\sigma^i_t)^2} + \tfrac{L^2}{\kappa^2} + L)), Λi=1+λ+⋯+λi−1\Lambda_i = 1 + \lambda + \dots + \lambda^{i-1}, without prior variance knowledge, and present it as improving the variance-independent term of Zhao et al. (2023b) from O~(dT)\tilde O(\sqrt{dT}) to O~(d)\tilde O(d). A second algorithm, Online-LGLB, replaces the MLE by online Newton steps and attains O~(ΛiLκdT)\tilde O(\Lambda_i \tfrac{L}{\kappa} d\sqrt T) without variance adaptivity. Experiments compare both to MOR-UCB and PF-LEX on a 10-armed synthetic instance with basis-vector arms and a 16-arm SW-LLVM instance.

Critical strengths

1. The paper is clearly written and the results are well organized. The problem setting is cleanly formulated, the two algorithms are presented with full pseudocode, and the theorems are stated with explicit constants and complete appendix proofs. The real-world examples used to motivate lexicographic ordering and the trade-off parameter λ\lambda (radiotherapy, energy management, traffic control) make the model easy to follow. This matters for my assessment because it means the paper's limitations are ones of contribution rather than of exposition: a reader can see exactly what is being claimed and check it, which is also what makes the incrementality visible.

2. The analysis is correct under its stated assumptions. I verified the chain Lemma 1 (linearization and the F⪰κVF \succeq \kappa V step), Lemmas 2–3 (Freedman plus Young and the residual-based variance switch at s≥sˉts \ge \bar s_t), Lemma 5 (the induction preserving the lexicographic optimal arm), the two-case regret decomposition in Theorem 2, and the ONS confidence set in Theorem 3. Apart from constant-level slips (the hidden condition κB≲Rγt\kappa B \lesssim R\gamma_t needed for Eq. (16), overlapping index sets ΨT+1,s\Psi_{T+1,s} in the proof of Theorem 4, a dropped dln⁡T\sqrt{d\ln T} factor in Eq. (29), and δ\delta not being re-split across the union of events), the stated bounds follow from Assumptions 1–4 as written. The one substantive gap, that Assumption 2 as stated excludes the logistic link unless the MLE in Eq. (3) is projected onto ∥θ∥2≤B\lVert\theta\rVert_2 \le B (see Weakness 2), is fixable by standard means (Filippi et al. 2010; Li et al. 2017). This is consequential in the sense that nothing in the paper is wrong in a way that cannot be repaired; my recommendation rests on the contribution being a recombination of existing techniques, not on any flaw in the execution.

Critical weaknesses

1. The paper is an assembly of three existing components with no new technique, and it is positioned so that this is not visible. Every piece of VA-LGLB maps one-to-one onto prior work: the layered structure (stages S=⌈32log⁡2T⌉S = \lceil \tfrac32 \log_2 T \rceil, V1,s=2−2sIV_{1,s} = 2^{-2s} I, weights wt=2−s/∥xt∥Vt,s−1w_t = 2^{-s}/\lVert x_t\rVert_{V_{t,s}^{-1}}, the case split on T−3/2T^{-3/2} and 2−s2^{-s}) is the VACDB algorithm of Di et al. (2024); the per-layer weighted MLE and the linearization F(θˉ)⪰κVF(\bar\theta) \succeq \kappa V in Lemma 1 are Filippi et al. (2010) / Li et al. (2017); the Bernstein bound is applied as a black box from Theorem 1 of Zhao et al. (2023a), and Lemmas 2–3 are the variance-estimation lemmas of Zhao et al. (2023a) and Di et al. (2024) with L/κL/\kappa in place of VACDB's Lμ/κμL_\mu/\kappa_\mu; AAE-LGLB is the lexicographic successive elimination of Xue et al. (2024) with each radius replaced by βˉi=max⁡j≤iβ^j\bar\beta^i = \max_{j \le i}\hat\beta^j, after which Lemma 5 follows mechanically from Assumption 4; Online-LGLB is Jun et al. (2017)'s GLOC, with Lemma 11 restating Lemma 3 of Zhang et al. (2016). What remains is a union bound over mm objectives. The paper concedes this in Appendices C and F ("proof framework inspired by ... Zhao et al. (2023a); Di et al. (2024)"; "inspired by ... Xue et al. (2023)"), yet Di et al. is absent from Table 1, the only place a reader would see that an O~(d∑tσt2+d)\tilde O(d\sqrt{\sum_t\sigma_t^2} + d) bound for a nonlinear link without prior variance knowledge already exists; the contribution bullet on "estimating unknown variances from nonlinear residuals" describes what Di et al. already did. The paper also does not cite Xue, Lin, Zhang and Zhang, "Multiple Trade-offs: An Improved Approach for Lexicographic Linear Bandits" (AAAI 2025), which already proposes an arm filter aggregating trade-offs across objectives and obtains O~(dT)\tilde O(d\sqrt{T}), i.e. Online-LGLB's guarantee for the identity link.

The headline comparison compounds this. The claimed improvement of the variance-independent term from O~(dT)\tilde O(\sqrt{dT}) (Zhao et al. 2023b) to O~(d)\tilde O(d) is not like-for-like: Zhao et al.'s dT\sqrt{dT} is the price of a one-pass estimator, VA-LGLB is offline MLE where the O~(d)\tilde O(d) term was already available from Di et al., and the paper's own one-pass algorithm, Online-LGLB, gets O~(dT)\tilde O(d\sqrt T), never better than Zhao et al.'s O~(dVT+dT)\tilde O(d\sqrt{V_T} + \sqrt{dT}) and strictly worse for small variances (the "optimal dependence on dd and TT" claim is also wrong for finite arm sets, where dTlog⁡K\sqrt{dT\log K} is minimax). This is consequential because "unknown variance" and "tighter bounds" are, by the title, the entire contribution; against the right prior work, no technical idea remains that is not already in Di et al. (2024) and Xue et al. (2024, 2025).

2. The bound's variance-independent term carries a d⋅L2/κ2d \cdot L^2/\kappa^2 factor that can dwarf the term it replaces, and the experiments neither exercise the GLB structure nor report what is needed to assess this. The L2/κ2L^2/\kappa^2 term in Theorem 2 comes from the sˉT=⌈log⁡2(64(L/κ)γT)⌉\bar s_T = \lceil \log_2(64 (L/\kappa)\sqrt{\gamma_T}) \rceil crude-radius layers (Eq. 30). For the logistic link used in the experiments, Assumption 2 fails as stated (inf⁡zμ˙(z)=0\inf_z \dot\mu(z) = 0), restricting to ∣z∣≤B|z| \le B does not suffice because Eq. (10) evaluates μ˙\dot\mu between θ⋆i\theta^i_\star and the unconstrained MLE of Eq. (3), and even on the range of x⊤θx^\top\theta the constant is astronomically small: θ⋆3(1)=−60\theta_\star^3(1) = -60 gives μ˙\dot\mu below 10−2510^{-25}. The values of κ\kappa and LL used are never reported, so whether the implemented radii correspond to Theorem 1 is unknown, and the "improvement" over dT\sqrt{dT} holds only in a regime the paper does not characterize. The experiments do not help: the synthetic arms are the standard basis in d=K=10d = K = 10 (a 10-armed bandit, no shared structure); SW-LLVM is 16 arms with unspecified features and link; MOR-UCB is single-objective run on an instance with three arms tied on objective 1, so its linear third-objective regret is by construction; PF-LEX is featureless; no error bars; it is not stated whether MOR-UCB received the true variances; the noise is Gaussian despite Assumption 3; and on SW-LLVM, VA-LGLB's first-objective regret (Fig. 2a) is still increasing at about 0.8 per round at t=2000t = 2000, comparable to the 1.3 gap between arms 14 and 16, so the optimal arm has not been identified. No weighted-scalarization baseline, the obvious comparator under Assumption 4, is included. With the theoretical novelty absent, the empirical section would have to show the assembled algorithm matters in practice, and it does not.

Questions for authors

Please feel free to address any of the points raised above.

5 comments
AuthorsOpenReview ↗

Response to TctM (1/3): Contributions and Prior Work

We thank the reviewer for recognizing the clear presentation, well-organized results and precise problem formulation. We appreciate the time and care devoted to reviewing our work and providing constructive comments and suggestions. We respond point by point below.

W1. The method recombines existing techniques, omits close prior work, compares different computational regimes, and overstates optimality.

(a) Contribution and relationship to VACDB. We clarified the contribution in Section 1 and added VACDB (Di et al., 2024) and MTLO (Xue et al., 2025) to Table 1 and Appendix A. Layering and residual-based estimation are established tools; their adaptation is valuable when it improves guarantees and variance-information requirements for a different decision problem. 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. Building on established variance-estimation techniques, we derive new variance-aware regret guarantees for each objective in lexicographic GLB, without requiring prior knowledge of reward variances.

The models differ in three respects. VACDB (Section 3, Eq. (3.1)) selects two arms, observes a binary comparison with mean pt=μ((xt−yt)⊤θ∗)p_t=\mu((x_t-y_t)^\top\theta_*) and variance pt(1−pt)p_t(1-p_t), and measures average latent-utility regret. We select one arm, observe numerical vector rewards with unknown bounded-noise variances not fixed by their means, and bound each objective's mean-reward regret against the lexicographic optimum. These differences prevent a direct invocation of VACDB's theorem: even subtracting two GLB rewards generally gives mean μ(x⊤θ)−μ(y⊤θ)\mu(x^\top\theta)-\mu(y^\top\theta), rather than the comparison model μ((x−y)⊤θ)\mu((x-y)^\top\theta).

The additional coordination problem is that a later objective's narrow confidence interval must not override unresolved earlier priorities. Using βˉi=max⁡j≤iβ^j\bar\beta^i=\max_{j\le i}\widehat\beta^j, Lemma 5 establishes optimum preservation under Assumption 4. Theorem 2 and its unordered-variance corollary give, with probability at least 1−δ1-\delta and fixed model constants suppressed,

Ri(T)≤O~(Λid[∑tmax⁡j≤i(σtj)2+1]).R^i(T)\le\widetilde O\left(\Lambda_i d\left[\sqrt{\sum_t\max_{j\le i}(\sigma_t^j)^2}+1\right]\right).

Under variance ordering, the prefix variance reduces to objective ii's own variance. The contribution lies in the problem resolved and the resulting guarantee, while the scalar estimation tools are explicitly attributed to prior work.

(b) Comparison with Zhao et al. (2023b). Even for m=1m=1, VA-LGLB removes the need for supplied per-round variance bounds and reduces the variance-independent remainder from O~(dT)\widetilde O(\sqrt{dT}) to O~(d)\widetilde O(d), holding model constants fixed. A noise-magnitude bound RR remains required.

Appendix A describes Zhao et al. (2023b) as using layered FTRL estimation. The characterization of their estimator as one-pass is inaccurate. Their Algorithm 2, line 9 (p. 9) computes

\widehat\theta_{t+1,l}=\arg\min_{\theta\in\mathbb R^d}\left\\{\lambda\|\theta\|_2^2+\sum_{\tau\in\Psi_{t+1,l}}\ell_\tau(\theta)\right\\},

where their λ\lambda is a regularization coefficient. This is FTRL minimization over the layer's historical observations, not a one-pass parameter update. Both methods optimize historical loss, so our statistical improvement cannot be attributed simply to replacing a one-pass estimator with batch re-estimation. The comparison concerns statistical guarantees, not a claim of equal runtime or computational superiority.

(c) Online-LGLB and optimality. We corrected the optimality wording: Online-LGLB provides efficient recursive updates with a worst-case O~(ΛiLκ−1dT)\widetilde O(\Lambda_i L\kappa^{-1}d\sqrt T) guarantee for fixed B,R,UB,R,U, matching the dTd\sqrt T order of classical single-objective upper bounds rather than claiming finite-action minimax optimality or improvement over Zhao's variance-dependent rate. Theorem 4, Remark 3 and the conclusion reflect this scope.

AuthorsOpenReview ↗

Response to TctM (2/3): W2: Curvature and Proof Corrections

W2. Curvature constants and estimator assumptions undermine the claimed improvement, while the experiments do not adequately test GLB structure, practical performance or the relevant baselines.

We clarified the curvature domain, constrained the estimator, corrected the affected proofs, and added shared-feature experiments, matched ablations and stronger baselines. The key changes and results are as follows.

(a) Curvature and estimator consistency. Positive local curvature is standard in classical GLB analysis, including Li et al. (2017) and VACDB. We now impose derivative bounds on [−B,B][-B,B] and minimize the regularized loss over ΘB={θ:∥θ∥2≤B}\Theta_B=\{\theta:\|\theta\|_2\le B\}. The true parameter, estimate and connecting segment then remain in the curvature domain. Lemma 1 (Appendix D) uses constrained optimality and the integral Hessian to retain the estimation-error bound; Online-LGLB's convexity argument is likewise restricted to its parameter ball.

The curvature cost remains explicit in Theorem 2: ignoring logarithms and other constants, its d(L/κ)2d(L/\kappa)^2 remainder is smaller than dT\sqrt{dT} only when T>d(L/κ)4T>d(L/\kappa)^4; this comparison alone does not imply a smaller total regret bound. We therefore added linear tests with L=κ=1L=\kappa=1 and nonlinear tests with valid L=1L=1, κ≃0.420\kappa\simeq0.420 on [−2,2][-2,2]. Appendices B–C disclose the constants and calibration. Figure 1's empirical curvature constants and the Gaussian-noise experiments do not satisfy all theorem conditions; empirical radius scaling is not claimed to provide theoretical confidence coverage.

(b) Proof corrections. Lemma 3 now retains regularization bias: adding 4⋅2−2sL2B24\cdot2^{-2s}L^2B^2 to the residual variance proxy removes the hidden restriction relating BB and RR. We also correct the probability-budget allocation, layer index sets, terminal-branch factors and Online-LGLB's initial radius BαB\sqrt\alpha. The corrected analysis for Theorem 2, together with its unordered-variance extension in Appendices E–F, gives

Ri(T)≤O~(Λid[Lκ∑tmax⁡j≤i(σtj)2+(U+R+1)L2κ2+LB]).R^i(T)\le\widetilde O\left(\Lambda_i d\left[\frac L\kappa\sqrt{\sum_t\max_{j\le i}(\sigma_t^j)^2}+(U+R+1)\frac{L^2}{\kappa^2}+LB\right]\right).

For fixed B,R,UB,R,U, the regret order and displayed curvature powers are preserved. For Online-LGLB, Theorems 3–4 and Appendices G–H use constrained ONS optimality from the first round, initialization β1=Bα\beta_1=B\sqrt\alpha, and a common confidence event for sequential filtering and optimum preservation. With fixed B,R,UB,R,U, the regret remains O~(ΛiLκ−1dT)\widetilde O(\Lambda_i L\kappa^{-1}d\sqrt T).

AuthorsOpenReview ↗

Response to TctM (3/3): W2 Continued: Empirical Evidence

(c) Shared features and meaningful secondary decisions. We expanded to 64 shared-feature arms, up to eight dimensions/objectives, and both linear and nonlinear links. VA-LGLB reaches 100% final-window optimum selection in all four settings (Figure 3, Appendix C.1). Figures 1–2 now include pointwise 95% intervals, and Appendix C reports every objective.

On all 1,024 recorded SW-LLVM configurations, six share the minimum memory but differ in performance. Compared with PrimaryOnly, which disables only secondary filtering, VA-LGLB has identical primary-regret trajectories but 43.7% lower secondary regret and 100% versus 16.64% final-window lexicographic-optimum selection (Figure 6, Appendix C.3). This demonstrates the value of secondary decisions in the recorded-data replay, without asserting ties in population means or improved real measurement efficiency. Appendix B also specifies Figure 2's identity features and linear link; that original task has a unique primary optimum and does not establish stable identification at its horizon.

(d) Baselines and variance adaptation. We added MTLO and WeightedWorst, a matched ablation replacing only the residual variance proxy with a worst-case bound. At low variance, VA-LGLB achieves lower mean regret on all four objectives; fourth-objective regret is 317.2, versus 611.1 for WeightedWorst and 495.8 for MTLO. At high variance, MTLO performs better and the matched methods are close; the four-arm nonlinear ablation yields coincident trajectories (Figure 4, Appendix C.2). MOR-UCB in Figures 1–2 optimizes only the first objective, providing a comparison with single-objective optimization. Our implementation uses a fixed, empirically scaled exploration coefficient, with true variances used only to generate rewards.

(e) Weighted scalarization. We added OFUL with weights ai=qm−i/∑jqm−ja_i=q^{m-i}/\sum_jq^{m-j}, q=2(1+λ)q=2(1+\lambda), preserving the lexicographic optimum under Assumption 4. Both C.2 linear comparisons use T=100000T=100000 and ten paired runs per noise level. Appendix C.2 specifies the settings for each comparison; within each comparison, each method uses the same parameters at both noise levels. At low noise, VA-LGLB improves objectives 2–4, with paired 95% intervals for the regret differences excluding zero; fourth-objective regret is 51.3 versus 299.5, and final-window optimum selection is 100% versus 57.4%. Scalarization has lower primary regret (9.6 versus 37.4). At high noise, this VA-LGLB calibration excludes the optimum in all ten runs; paired intervals favor scalarization on objectives 1–2 and include zero on objectives 3–4. The demonstrated benefit is confined to later objectives in the low-noise regime (Figure 5, Table 3 and Appendix C.2).


Thank you again for your time and thoughtful feedback. We would be happy to answer any further questions during the discussion phase.

Reviewer_GdEXOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies lexicographic multi objective generalized linear bandits with unknown reward variances. It proposes VA-LGLB, which combines residual based variance estimation, maximum likelihood estimation, and adaptive arm elimination. The algorithm achieves variance dependent regret and improves the variance independent term from the square root of the horizon to a term logarithmic in the horizon. It also introduces Online-LGLB, an online Newton based alternative with lower computational cost but a worst case regret bound. Validation includes a synthetic three objective environment and a semi synthetic experiment constructed from SW-LLVM data. The reported results show improvements over MOR-UCB and PF-LEX under several noise settings.

Critical strengths

The main strength is a theoretically meaningful improvement in variance adaptive regret without requiring prior knowledge of reward variances. This result also improves existing guarantees for single objective generalized linear bandits as a special case, making the contribution relevant beyond the specific multi objective setting.

The paper also provides a principled extension of variance aware estimation to lexicographic optimization. Its adaptive elimination procedure propagates uncertainty across objectives while preserving the lexicographically optimal arm with high probability. The analysis is detailed and includes a generalized bound without the variance ordering assumption used in the main text.

Critical weaknesses

The empirical validation is too limited to establish robust practical performance. The experiments use small action sets, only ten repetitions, and no variability or statistical significance analysis. The real world study is semi synthetic and relies on simulated Gaussian rewards. Important comparisons with stronger multi objective baselines, runtime measurements, and ablation studies are also missing.

The practical applicability is further constrained by strong assumptions and computational tradeoffs. The algorithms require a known global tradeoff parameter and several problem dependent constants. VA-LGLB retains historical data and repeatedly solves maximum likelihood problems, while the more efficient Online-LGLB loses variance adaptivity. Thus, the paper does not yet provide an algorithm that is both computationally efficient and variance adaptive.

Questions for authors

Please address the concerns raised in the Weaknesses section. I am willing to reconsider and increase my score.

4 comments
AuthorsOpenReview ↗

Response to GdEX (1/2): Expanded Empirical Evaluation

We thank the reviewer for recognizing the improvement in unknown-variance regret guarantees, including the single-objective GLB case, and the extension to lexicographic optimization. We appreciate the time and care devoted to reviewing our work and providing constructive comments and suggestions. We respond point by point below.

W1. Limited empirical validation: small action sets, ten repetitions without variability analysis, simulated real-data rewards, missing stronger multi-objective comparisons, runtime measurements and ablations.

We expanded the experimental scope, added stronger baselines and matched ablations, and measured computational cost alongside regret. The main additions are summarized below.

(a) Larger action sets and uncertainty. We added 64-arm shared-feature experiments, covering linear (d,m)=(2,2),(4,4),(8,8)(d,m)=(2,2),(4,4),(8,8) and nonlinear (4,4)(4,4) instances, with 30 runs per condition, plus a 32-arm experiment with changing arm availability, where four core arms remain available and each of the other 28 arms is independently available with probability 1/2 each round. VA-LGLB reaches 100% final-window optimum selection in all four shared-feature settings, compared with 68.5%, 13.3%, 2.7% and 13.3% for WeightedWorst (a matched worst-case variance baseline, defined below). With changing availability, mean regrets are (466.7, 715.4) versus (953.8, 1147.3). Figure 3 and Appendix C.1 report every objective. Figures 1–2 now include uncertainty bands, and the supplementary results report pointwise 95% Student-tt intervals; run counts are specified with each experiment.

(b) Recorded real-data rewards and secondary decisions. We added a memory-first replay of all 1,024 SW-LLVM configurations, using recorded rewards without fitted Gaussian noise. Six configurations share the minimum recorded memory but differ in performance, making secondary decisions necessary to distinguish the best configuration; no binning or additional rounding creates these ties. Across 30 paired runs, VA-LGLB and PrimaryOnly (the same method with secondary filtering disabled) have identical primary-regret trajectories, but VA-LGLB reduces secondary regret by 43.7%. Both achieve 100% final-window primary-optimum selection, while lexicographic-optimum selection is 100% versus 16.64%. Figure 6 and Appendix C.3 isolate this benefit on the recorded table, rather than establish ties in population means or gains in real measurement efficiency.

(c) Stronger baseline and variance ablation. We added MTLO (Xue et al., AAAI 2025) on a matching 64-arm, four-objective linear family, retaining its published filtering rules. Appendix C.2 reports ten paired runs per noise level, with the same parameter settings across noise levels for each method. WeightedWorst shares VA-LGLB's estimator, sample weights, stages, filtering and regularization compensation, replacing only the empirical residual sum with a worst-case variance bound.

At low variance, VA-LGLB has lower mean regret on all four objectives than both comparators; fourth-objective regret is 317.2, versus 611.1 for WeightedWorst and 495.8 for MTLO. The matched ablation isolates the variance proxy in this experiment; differences from MTLO also reflect its estimator and terminal rules. At high variance, VA-LGLB and WeightedWorst perform similarly and MTLO performs better; the four-arm nonlinear ablation also yields coincident trajectories. Figure 4 and Appendix C.2 provide the full results, supporting a regime-dependent benefit.

(d) Runtime alongside regret. We added runtime, per-round latency and peak-memory measurements alongside regret on the same instances and runs. At T=2000T=2000, VA-LGLB and Online-LGLB take 3.353 s and 0.263 s, with mean regret vectors (184.77, 179.55, 190.39) and (184.38, 173.96, 183.74), respectively. Online-LGLB is approximately 12.7 times faster with similar regret at this horizon; this measures early learning, not time to convergence. Table 4 and Appendix C.4 report the full measurements.

AuthorsOpenReview ↗

Response to GdEX (2/2): Parameters and Computational Trade-offs

W2. Practical applicability is constrained by a known global trade-off parameter and other constants, historical-data/MLE costs, and the absence of an algorithm that is both computationally efficient and variance adaptive.

We clarified the required parameters, added guidance and a sensitivity test for λ\lambda, and quantified the computational trade-off between the two algorithms.

(a) Parameter choice and sensitivity. The main text discusses justified trade-off bounds, while Appendix C.5 tests sensitivity and illustrates the risk of underestimation. Assumption 4 requires a uniform bound on expected-reward trade-offs in fixed objective units, justified by domain constraints or offline information; the examples in the main text are illustrative rather than certified bounds. In our sensitivity test, the valid bound and its two- and four-fold multiples yield the same mean regret vector, (105.2, 567.0), with 100% final-window optimum selection. Underestimation can nevertheless remove the true optimum, as the counterexample in Table 5's accompanying discussion and Appendix C.5 demonstrates. Appendices B–C specify the remaining model parameters and experimental settings; unknown-variance adaptation does not remove the need for valid parameter, noise and trade-off bounds. The experimental trade-off bounds are computed from known instance means rather than certified online.

(b) Computational efficiency and variance adaptation. VA-LGLB uses historical weighted estimation to obtain variance-adaptive guarantees; Online-LGLB uses recursive updates with a worst-case regret guarantee. Figure 4 and Appendix C.2 demonstrate VA-LGLB's low-noise benefit against the matched variance ablation and MTLO. Table 4 and Appendix C.4 compare cost and regret on the same runs: Online-LGLB is about 12.7 times faster with similar regret at T=2000T=2000. The low-variance advantage over MTLO is demonstrated on linear instances, whereas the computational-cost comparison uses nonlinear instances; they provide complementary evidence rather than a joint demonstration on the same setting. Section 3.2 contrasts historical constrained estimation with recursive ONS updates. For the identity-link SLB special case, Section 3.1 explains that VA-LGLB can update its estimator online without revisiting historical observations; the open problem concerns a computationally efficient variance-aware method for general nonlinear links (Section 5).


Thank you again for your time and thoughtful feedback. We would be happy to answer any further questions during the discussion phase.

Thank you for the detailed response and additional experiments. After considering the clarifications, I maintain my current rating of 3.

AuthorsOpenReview ↗

Thank You for Your Feedback and Positive Assessment

Thank you for following up and for your positive assessment of our work. We appreciate your time in reviewing our clarifications and additional experiments, and your constructive suggestions have helped improve the paper.

Reviewer_14EdOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies generalized linear bandits with multiple lexicographically ordered objectives and unknown reward variances. The authors propose VA-LGLB, which combines variance estimation with a priority-aware active arm elimination procedure. The method provides variance-dependent regret guarantees with an improved variance-independent term compared with the cited single-objective GLB baseline. The paper also introduces Online-LGLB, which replaces repeated maximum likelihood estimation with online Newton updates to reduce computational costs, while sacrificing variance adaptivity. Experiments on synthetic data and a compiler-configuration dataset illustrate the proposed methods.

Critical strengths

The problem is well motivated. Lexicographic priorities capture applications where gains in lower-priority objectives cannot compensate for losses in higher-priority objectives. Adapting exploration to unknown reward variances adds practical relevance to this setting.

The proposed elimination procedure explicitly incorporates uncertainty across higher-priority objectives. This provides a clear connection between the algorithmic design and the hierarchical decision structure, rather than treating the objectives independently.

Introducing Online-LGLB alongside VA-LGLB shows attention to computational practicality. The manuscript clearly explains the differences between the two methods, including their estimation procedures, storage requirements, and variance adaptivity.

The synthetic instance is deliberately constructed so that identifying the lexicographic optimum requires considering all three objectives. This makes it useful for demonstrating the importance of hierarchical decision-making.

Critical weaknesses

The experimental scope is limited. The synthetic evaluation uses a single configuration with ten standard-basis arms and three objectives. This construction provides little opportunity to demonstrate generalization through shared features. Experiments with dense features, varying dimensions, more objectives, and changing contextual arm sets would provide stronger evidence of robustness and scalability.

The baseline comparisons do not fully isolate the proposed contributions. MOR-UCB optimizes a single objective, so its poor performance on lower-priority objectives does not establish the advantage of the proposed elimination mechanism. PF-LEX provides a relevant hierarchical comparison but does not exploit the same generalized linear structure. An ablation that retains the elimination procedure while replacing the variance-adaptive confidence radius with a worst-case radius would help distinguish the sources of improvement.

The SW-LLVM experiment provides limited evidence for the lexicographic component. As the authors acknowledge, the first objective alone determines the optimal arm, making lower-priority objectives unnecessary for identifying the lexicographic optimum. Furthermore, rewards are simulated from Gaussian distributions fitted to aggregated dataset statistics. Additional dataset-based instances requiring decisions across multiple priority levels would strengthen the practical evaluation.

The computational advantage of Online-LGLB is not measured. Although reducing computational costs is its primary motivation, the experiments do not report runtime, memory consumption, or per-round update latency. Comparing VA-LGLB and Online-LGLB on the same instances using both regret and computational cost would make their practical trade-off clearer.

Practical parameter selection requires more discussion. In particular, the trade-off parameter λ\lambda directly affects the elimination thresholds, but the manuscript provides limited guidance on selecting it in an unfamiliar application. Sensitivity experiments, including misspecified values, would help assess how much prior problem knowledge the methods require.

The empirical reporting could be more informative. Results are averaged over ten runs without uncertainty bands, making variability difficult to assess. Reporting all synthetic objectives and the frequency of selecting the lexicographic optimum would also help interpret performance, especially because lower-priority regret can be negative.

Questions for authors

See weakness

4 comments
AuthorsOpenReview ↗

Response to 14Ed (1/2): Expanded Experiments and Ablations

We thank the reviewer for recognizing the motivation of our problem and the connection between our elimination procedure and hierarchical decision-making. We appreciate the time and care devoted to reviewing our work and providing constructive comments and suggestions. We respond point by point below.

W1. Limited scope: shared features, varying dimensions/objectives and changing arm sets.

We expanded the evaluation to 64 arms with dense shared features, covering linear instances with (d,m)=(2,2),(4,4),(8,8)(d,m)=(2,2),(4,4),(8,8) and a nonlinear instance with (d,m)=(4,4)(d,m)=(4,4), with 30 runs per condition. We also added a 32-arm experiment with changing arm availability: four core arms remain available, while each of the other 28 arms is independently available with probability 1/2 each round.

VA-LGLB achieves 100% final-window optimum selection in all four shared-feature settings, compared with 68.5%, 13.3%, 2.7% and 13.3% for WeightedWorst (a matched baseline replacing the empirical residual sum with a worst-case variance bound; see our response to W2 below), respectively. With changing availability, its mean terminal regret vector is (466.7, 715.4), versus (953.8, 1147.3) for WeightedWorst. Figure 3 and Appendix C.1 report the objective-wise results, confidence intervals and experimental settings.

W2. The comparisons do not isolate the contributions.

We added a matched variance-proxy ablation to isolate the contribution of residual-based variance adaptation, together with an MTLO comparison on a matching linear instance family (Figure 4, Appendix C.2). The ablation baseline, WeightedWorst, shares the constrained estimator, sample weights, stages, filtering rules and regularization compensation with VA-LGLB. It replaces only the empirical residual sum with the worst-case bound R2∑wτ2R^2\sum w_\tau^2.

On the 64-arm, four-objective linear instance, VA-LGLB achieves lower mean regret on all four objectives at low variance than both WeightedWorst and MTLO. For example, fourth-objective regret is 317.2, versus 611.1 for WeightedWorst and 495.8 for MTLO. The matched ablation isolates the variance proxy in this experiment; differences from MTLO also reflect its estimator and terminal rules. At high variance, VA-LGLB and WeightedWorst perform similarly, while MTLO performs better; the four-arm nonlinear ablation also yields coincident trajectories. Thus the observed benefit is regime-dependent. Figure 4 and Appendix C.2 provide the full results and settings.

W3. The original SW-LLVM task does not require secondary decisions and uses simulated rewards.

We added a recorded-data replay on all 1,024 SW-LLVM configurations, prioritizing minimum memory and then maximum performance. Six configurations share the minimum recorded memory but have different performance values, so primary-objective optimization alone cannot distinguish the best configuration.

Across 30 paired runs, VA-LGLB and PrimaryOnly (the same method with secondary filtering disabled) have identical primary-regret trajectories, but VA-LGLB reduces secondary regret by 43.7%. Both reach 100% final-window primary-optimum selection, while lexicographic-optimum selection is 100% for VA-LGLB versus 16.64% for PrimaryOnly. This isolates the value of secondary decisions on the recorded table; it does not establish ties in population means or improved real measurement efficiency. Figure 6 and Appendix C.3 provide the results and experimental settings.

AuthorsOpenReview ↗

Response to 14Ed (2/2): Computational Cost, Parameters and Reporting

W4. Computational costs should be measured alongside regret on the same instances.

We added a joint comparison of regret, runtime, per-round latency and peak memory on the same instances, with all measurements taken from the same runs of VA-LGLB and Online-LGLB.

At T=2000T=2000, mean runtime is 3.353 s for VA-LGLB versus 0.263 s for Online-LGLB, while their mean regret vectors are (184.77, 179.55, 190.39) and (184.38, 173.96, 183.74), respectively. Thus Online-LGLB is approximately 12.7 times faster with similar regret at this horizon, an early-learning comparison rather than a time-to-convergence result. Table 4 and Appendix C.4 report the full regret and cost measurements.

W5. Practical choice of λ\lambda and misspecification sensitivity need explanation.

The main-text discussion of practical implications explains the need for a justified upper bound on λ\lambda; Appendix C.5 supplies the sensitivity experiment and underestimation counterexample. As required by Assumption 4, the bound must hold uniformly for expected rewards in fixed objective units and be justified by domain constraints or offline information.

In the sensitivity experiment, using the valid bound or two/four times that bound gives the same mean regret vector, (105.2, 567.0), with 100% final-window optimum selection. Although underestimated values also succeed on this instance, they can invalidate optimum preservation: our counterexample shows that using one quarter of the required bound removes the true optimum even with exact predictions. Table 5 and Appendix C.5 provide the results and details.

W6. Report uncertainty, all objectives and optimum-selection frequencies.

We added pointwise 95% Student-tt confidence intervals for mean performance, objective-wise results and final-window optimum-selection frequencies. Figures 1–2 now include uncertainty bands; Figure 1 retains selected objectives, while Figures 3–6 and Tables 3–5 report all objectives for the supplementary experiments, with selection rates in the accompanying text, Figure 6 and Tables 3 and 5. Table entries with ±\pm give confidence-interval half-widths. Appendix C specifies the interval convention and run counts. Selection frequencies use the final 200 rounds for the shared-feature instances in C.1 and the sensitivity experiment in C.5 and the final 1000 rounds in the scalarization and recorded-data comparisons; Figure 6 intervals reflect policy randomization. Main-text analyses describe the regret trajectories: Figure 1(a) illustrates noise sensitivity, while the matched variance ablation is in Figure 4 and Appendix C.2. Figure 2 does not establish stable optimum identification at the tested horizon.

Negative lower-priority regret does not imply better lexicographic performance: an arm can exceed the lexicographic optimum on a later objective while sacrificing an earlier one. We therefore interpret it jointly with primary regret, as explained alongside Figure 2, and use optimum-selection frequencies in the supplementary evaluation (Appendices B–C).


Thank you again for your time and thoughtful feedback. We would be happy to answer any further questions during the discussion phase.

I agree with Reviewer TctM that the work appears incremental, building on existing techniques without clear fundamental novelty. The contribution would be stronger if the authors established fundamentally new theoretical results, such as a lower bound for the problem under study, to demonstrate that the proposed methods achieve optimal dependence on the relevant problem parameters. Nevertheless, in recognition of the authors’ efforts to add new experiments, I am raising my rating to 3.

AuthorsOpenReview ↗

Thank You for Your Updated Assessment

Thank you for recognizing the additional experiments and raising your rating. We appreciate your careful evaluation and constructive suggestions.

Regarding lower bounds, our model includes single-objective linear bandits as the special case m=1m=1 with an identity link. The classical Ω(dT)\Omega(d\sqrt{T}) minimax lower bound for general linear-bandit action sets (Dani et al., 2008) therefore applies to this subclass. Our bounds specialize to O~(dT)\widetilde O(d\sqrt{T}) in the worst case, matching this dependence on dimension and horizon up to logarithmic factors. Your suggestion motivates a further direction: establishing lower bounds that additionally characterize the dependence on lexicographic trade-offs and objective priorities.

Thank you again for your thoughtful feedback. We would be happy to answer further questions.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.