- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
The paper studies near-optimal arm identification in structured bandits when two feedback modalities - numerical reward feedback and pairwise preference feedback - are based on DIFFERENT latent parameters. This extends prior approaches that assume a shared latent model with aligned preferences across both feedback modalities. The authors propose the algorithm WIT-BOTELIM, which mantains modality-specific estimators while exploiting cross-modal information through the two mechanisms witness elimination and bottleneck elimination. The paper provides a lower bound for the identification problem, a high-probability upper bound for WIT-BOTELIM and states near-optimality in a particular regime. Experiments demonstrate the robustness of WIT-BOTELIM to increasing mismatch between the reward and preference parameters and investigate scaling with the number of arms and feature dimension.
Critical strengths
- Interesting and practically relevant problem: allowing reward and preference feedback to have different latent parameters in a meaningful generalization that is much more realistic than shared-parameter approaches
- Strong theory: paper provides both: a lower bound and an upper bound (in a PAC guarantee style)
- clear algorithmic idea: a easy understandable and interpretable separation between modality-specific estimation and decision-making. The witness and bottleneck elimination provide a clear way of exploiting information in each modality without assuming that the modalities are aligned
Critical weaknesses
- Experimental comparison somewhat limited: no surprise at all that HYTS-GLB which is designed for shared latent parameters cannot handle a misalignment in the latent parameters. To be fair, not only the accuracy of WIT-BOTELIM and HYTS-GLB should be compared, but also the sample complexity (which will be better for HYTS-GLB, but for the cost of lower accuracy)
- the near-optimality claim is quite restricted: the matching-order result requires a fairly specialized closest-challenger condition and boundedness assumptions, while the general upper bound contains additional rounding, burn-in and Fisher-leverage terms
Minor:
- \epsilon is not introduced properly: a statement that \epsilon is fixed and specified in advance is missing throughout the paper
- in the introduction you already mention 'the best arm' and 'arm whose gaps under both modalities are less than \epsilon', but at that point it is not clear what a best arm is and that an \epsilon-best arm for both modalities exists (and also not discussed that is does not necessarily exist)
- same for the defiinition of set S_{\epsilon}: no discussion that this set might be empty
- after the definition of the best arms for each feedback modality, an explanation why this coincides with the usual definition of best arms in a dueling setting where i_D^* = argmax_{j \in [K]} \sum_{i \neq j} (x_j - x_i)\theta_D
- gamma_r in Lemma 2 was not introduced and explained in the text, only in the pseudocode I think
Questions for authors
- Not sure whether the comparison of the lower and upper bound is valid. You mentioned something like this yourselves in your paper and I would appreciate more justification why you can compare a lower bound in expectation with a high-probability upper bound
2 comments
Response to Reviewer bvyc (Part 2/2)
Weakness 2: Clarifying near-optimality of the Wit-BotElim algorithm.
Thank you for pointing this out. We agree that our near-optimality result applies only to the specialized regime characterized by the closest-challenger condition and the stated boundedness assumptions. However, beyond the theoretical results, we also add an empirical comparison of Wit-BotElim's performance against the sample-complexity lower bound in Figure 1(c) of Section 4, accompanied by the following discussion:
"Figure 1c first demonstrates that the empirical sample complexities of WIT-BOTELIM(all) and WIT-BOTELIM(one) co-vary closely with their corresponding lower-bound quantities and remain on the same scale. Specifically, the ratio between the empirical sample complexity of WIT-BOTELIM(all) and stays within ; meanwhile, for WIT-BOTELIM(one), the ratio of WIT-BOTELIM(one) against lies in , and the ratio against the refined bound is tightened to . Across all settings, sample complexity increases monotonically as problem instances become harder---as indicated by a smaller ---and as hardness parameters grow, corroborating our theoretical bounds. Notably, the gap between the empirical sample complexity of WIT-BOTELIM(one) and its corresponding lower bounds narrows further as decreases. Overall, Figure 1c implies that our theoretical bounds are satisfactory and that WIT-BOTELIM achieves high sample efficiency, particularly in more challenging problem regimes."
Minor Weaknesses
Thank you for these careful comments. These points mainly concern exposition and notation, and we incorporate all of the requested clarifications in the revision. Specifically, we state explicitly that is fixed and specified in advance, introduce the modality-wise best arms and the joint -optimality criterion before using them, and etc. As these changes are presentational and do not affect our technical results, we do not elaborate further here.
Question: Clarifying the tightness study
Thanks for your comment. Our original comparison followed the convention of Fiez et al. (2019), which compares an expected lower bound against a high-probability upper bound. Furthermore, we have added Proposition 6 and its proof, as well as the following discussion in Appendix D.11.3:
''In Proposition 6, we derive an expected sample-complexity upper bound for WIT-BOTELIM in specific regimes and show that it matches the high-probability upper bound in order. Accordingly, comparing our high-probability upper bound with the expected lower bound provides a reasonable basis for assessing the optimality of WIT-BOTELIM in these regimes, while establishing its optimality in the general case remains an open direction for future work.''
Response to Reviewer bvyc (Part 1/2)
We thank you for your time, effort, and valuable comments, and we provide our point-by-point responses below. We sincerely apologize for submitting our rebuttal nearing the deadline and hope you will still take these responses into consideration when finalizing your review and discussing with the AC.
Weakness 1: Comparison to baseline algorithm
Thank you for your comments. Accordingly, we add a comparison between Wit-BotElim and HyTS-GLB evaluating both identification accuracy and sample complexity. Figure 1(a), which presents this comparison, along with the following discussion, has been added to Section 4 of the revised manuscript:
"Although Wit-BotElim and HyTS-GLB are designed for distinct objectives under different settings, we compare them in terms of both identification accuracy (Figure 1(a)-i) and sample complexity (Figure 1(a)-ii). Each algorithm is configured to achieve its target with a success probability of at least 1−δ=95%, which we plot as a reference threshold for empirical accuracy in Figure 1(a)-i. In Figure 1(a)-ii, we also plot the sample-complexity lower bound established in Theorem 1. Here, Wit-BotElim(all) denotes the variant tasked with identifying the exact set of all ε-optimal arms, whereas Wit-BotElim(one) denotes the variant required to identify any single ε-optimal arm.
Because these algorithms target different objectives, a completely fair comparison is infeasible; to make the evaluation as fair as possible, we construct a suite of problem instances spanning varying levels of misalignment between the reward and dueling feedback with fixed instance settings as detailed in Appendix E.1, each possessing a unique ε-optimal arm. Under this construction, WIT-BOTELIM(all) and WIT-BOTELIM(one) share the exact fixed identification target arm across unaligned instances as there exists a unique ε-optimal arm, while in the aligned instance with no misspecification, the target output of each algorithm differs.
First, as shown in Figure 1(a)-i, both Wit-BotElim variants empirically identify the optimal arm with an accuracy of 99.4% to 100%—exceeding the required 1−δ=95% threshold—whereas HyTS-GLB succeeds in the aligned setting but fails in unaligned settings. This behavior is expected, as HyTS-GLB is designed exclusively for aligned feedback, thereby demonstrating the necessity of Wit-BotElim. Next, as shown in Figure 1(a)-ii, Wit-BotElim (all) incurs a higher sample complexity of around 1.22×108 than around 6.85×105 of Wit-BotElim (one), corroborating our theoretical result in Theorem 3 as Wit-BotElim (one) terminates earlier. Moreover, HyTS-GLB exhibits a smaller sample complexity of around 3.41×105 for following reasons: (i) in the aligned setting, HyTS-GLB leverages both feedback modalities to estimate a single shared latent vector, whereas Wit-BotElim maintains separate parameter estimates for the two modalities and is therefore less sample-efficient; and (ii) in the unaligned setting, although HyTS-GLB terminates earlier than Wit-BotElim (one), it consistently fails to identify the correct arm."
These results may confirm the prediction you made in the review.