acceptodds
Under review as a conference paper at ICLR 2027

Finding Epsilon-Best Arms in Structured Bandits via Fused Feedback

Abstract

To model real-world scenarios where a learner receives diverse, potentially biased feedback signals, we introduce a structured multi-armed bandit framework with unaligned fused feedback. In this setting, at each round, the learner can either select a single arm to observe its standard reward feedback or select a pair of arms to observe the corresponding dueling feedback. Crucially, each feedback modality has its own latent parameter: the expected feedback associated with an arm is the inner product of its feature vector and the corresponding modality-specific parameter. We propose Wit-BotElim, an algorithm tailored for -best arm identification under fused feedback, which leverages a novel fused-elimination rule to efficiently aggregate disparate feedback modalities. By proving a generic sample complexity lower bound, we demonstrate that Wit-BotElim achieves near-optimal performance in key practical regimes. Finally, numerical experiments indicate the superiority of Wit-BotElim over shared-parameter methods under latent-parameter mismatch, which is attributed to the delicately-designed fused-elimination.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, Bandits, Fused Feedback

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_BVYcOpenReview ↗
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
AuthorsOpenReview ↗

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−δ=951-\delta=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 ε\varepsilon-optimal arms, whereas Wit-BotElim(one) denotes the variant required to identify any single ε\varepsilon-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 ε\varepsilon-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 ε\varepsilon-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−δ=951-\delta=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×1081.22 \times 10^8 than around 6.85×1056.85 \times 10^5 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×1053.41\times 10^5 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.

AuthorsOpenReview ↗

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 LallL^\text{all} stays within [2.83,3.13][2.83, 3.13]; meanwhile, for WIT-BOTELIM(one), the ratio of WIT-BOTELIM(one) against LoneL^\text{one} lies in [12.57,28.94][12.57, 28.94], and the ratio against the refined bound LcolL^\text{col} is tightened to [5.62,13.12][5.62, 13.12]. Across all settings, sample complexity increases monotonically as problem instances become harder---as indicated by a smaller ι\iota---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 ε\varepsilon 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 ε\varepsilon is fixed and specified in advance, introduce the modality-wise best arms and the joint ε\varepsilon-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.''

Reviewer_yotFOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces a structured bandit setting it calls unaligned fused feedback: at each round the learner either queries a single arm for linear reward feedback or a pair of arms for logistic dueling feedback, and the two modalities are governed by separate latent parameters, so their rankings and even their optimal arms may disagree. The goal is fixed-confidence identification of arms whose fused gap, the maximum of the two modality gaps, falls below ε, either by returning one such arm or by recovering the full set. The authors provide a sample-complexity lower bound, propose WIT-BOTELIM, a phased elimination algorithm that combines separate modality estimators with a cross-modal witness and bottleneck elimination rule, prove a PAC guarantee with near-optimality in a specialized regime, and report robustness and scaling experiments against an aligned-feedback baseline and several ablations.

Critical strengths
  1. Prior fused bandit work forces the two feedback sources to share a latent parameter, so allowing reward and dueling parameters to disagree is a real generalization that models settings, such as LLM post-training with ratings versus pairwise preferences, where the two modalities encode different notions of quality. The framing motivates the whole paper and is worth reading for this alone.

  2. Witness elimination drops competitors that no longer determine any modality gap, and bottleneck elimination stops refining a modality once the other provably controls the fused gap; both concentrate sampling on directions that can still change the decision. The lower bound, the phase-wise guarantees, and the explicit near-optimality comparison give the approach a solid foundation even though that comparison is narrow.

Critical weaknesses
  1. The near-optimality claim holds only when the joint answer set is a single arm closest to both modality boundaries, under an additional geometric dominance condition, up to constants and logarithmic factors, and with an explicit caveat tying high-probability and expected stopping times together. That is a slim basis for the headline claim of near-optimal performance, and no experiment measures how close WIT-BOTELIM's query cost actually gets to the lower bound.

  2. The only external baseline is a shared-parameter method whose failure under parameter mismatch mostly restates the motivation, so the robustness demonstration confirms the concept but not its value. The scaling study verifies monotonicity rather than predicted rates, and the fusion ablation shows modest gains concentrated in the exact-set task, leaving the efficiency story to rest on theory rather than evidence.

Questions for authors
  1. In the main lower-bound result, the bound with a min over the answer set and the kl((1−δ)/s,δ)\mathrm{kl}((1-\delta)/s,\delta) factor reads like the one-arm guarantee, while the bound with a max reads like the exact-set guarantee, yet each carries a different, seemingly wrong name, and the appendix repeats the confusion. Could you confirm which bound corresponds to εone\varepsilon_{\mathrm{one}} and which to εall\varepsilon_{\mathrm{all}}, and fix the labels?
  2. For εone\varepsilon_{\mathrm{one}} identification with several arms in the answer set, does the upper-bound analysis really track the min-inside hardness, or only the single-answer regime where min and max coincide?
  3. As future work, a tightness study comparing WIT-BOTELIM's empirical query cost with the lower-bound quantity across ε values and gap profiles would materially change my assessment.
2 comments
AuthorsOpenReview ↗

Response to Reviewer yotf (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: Clarifying near-optimality of the Wit-BotElim algorithm.

Theoretical comparison. We admit that our theoretical comparison applies only to the stated specialized regime which should not be interpreted as a general instance-optimality result. We also clarify this point before Remark 1 in Page 8.

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 implemented an improved lower bound under certain regimes to track near-optimality, and added Proposition 41 with its proof, as well as the following discussion in Section D.11:

  • ''We next strengthen the lower bound for εone\varepsilon^{\mathrm{one}}-BAI when several recommendations are jointly acceptable under specified assumptions. The original lower bound can focus on the easiest acceptable arm because the algorithm needs to return only one of them. The construction below instead identifies perturbations that invalidate every answer in the original acceptable set simultaneously.''

  • ''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.''

Empirical comparison. 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 LallL^\text{all} stays within [2.83,3.13][2.83, 3.13]; meanwhile, for WIT-BOTELIM(one), the ratio of WIT-BOTELIM(one) against LoneL^\text{one} lies in [12.57,28.94][12.57, 28.94], and the ratio against the refined bound LcolL^\text{col} is tightened to [5.62,13.12][5.62, 13.12]. Across all settings, sample complexity increases monotonically as problem instances become harder---as indicated by a smaller ι\iota---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 ε\varepsilon 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."

AuthorsOpenReview ↗

Response to Reviewer yotf (Part 2/2)

Weakness 2: Clarifying the effectiveness of Wit-BotElim.

First, as in our response to W1, ''Figures [placeholder] and [placeholder] compare the empirical performance of Wit-BotElim against the theoretical lower bound to investigate its optimality beyond the specific regimes analyzed in Sections 3.2 and D.11.''

Moreover, to evaluate the value of WIT-BOTELIM independently of external comparisons, we now perform more ablation study isolating the witness elimination and bottleneck elimination mechanisms, as shown in Table 3 and 4 of the revised manuscript. We compare four variants using direction sets C×ZC\times Z (no compression), C×WC\times W (witness only), G×ZG\times Z (bottleneck only), and G×WG\times W (the complete method) on settings of ∣Sε∣∈{2,3,4}|\mathcal S_\varepsilon|\in\{2,3,4\}.

We also add the following discussion to the revised manuscript:

''Across all the instances, the no-compression variant requires 62.062.0–75.175.1 times as many queries on average as the complete method, corresponding to a 98.39%98.39\%–98.67%98.67\% reduction in mean query cost.

As presented in Table 4, the paired factorial analysis further separates the two mechanisms. With witness elimination active, bottleneck elimination provides a 21.7221.72–25.72×25.72\times reduction factor; with bottleneck elimination active, witness elimination provides an additional 1.871.87–2.40×2.40\times reduction factor. All factorial contrasts remain significant after global Holm correction, while the variants retain comparable identification accuracy. These results show that both mechanisms make distinct and substantial contributions and that their benefits extend across both identification objectives. Together with the HyTS-GLB robustness experiment, the new ablation distinguishes the value of modeling unaligned feedback from the efficiency gains produced by the proposed algorithmic mechanisms.''

Question 1: Correction of typos in Theorem 1.

Thank you for catching this. This is a typographical error in the task labels. The bound containing

\min_{i\in\mathcal S_\varepsilon}(H_i^R+4H_i^D)$$ corresponds to $\varepsilon^{\mathrm{one}}$-BAI, whereas the bound containing $$2\operatorname{kl}(1-\delta,\delta) \left(\max_{i\in\mathcal S_\varepsilon}H_i^R+ 4\max_{i\in\mathcal S_\varepsilon}H_i^D\right)$$ corresponds to $\varepsilon^{\mathrm{all}}$-BAI. We correct the labels in both this main theorem (Theorem 1) and the appendix. The bounds and their proofs are unchanged. ### **Question 2: Clarifying the theoretical optimality of Wit-BotElim** Our current upper-bound analysis does not generally track the minimum over $i\in\mathcal S_\varepsilon$ when the answer set contains multiple arms. For $\varepsilon^{\mathrm{one}}$-BAI, the discussed upper–lower-bound matching applies to the singleton-answer regime, where the minimum and maximum over $\mathcal S_\varepsilon$ coincide. We additionally investigate specialized regimes in which the dominant terms in the sample-complexity upper bound of Wit-BotElim align more closely with the refined lower-bound quantities. we add these results to Appendix C.11.2 of the revised manuscript. You may refer to our **response to W1** for more details. ### **Question 3: Clarifying the numerical optimality of Wit-BotElim.** Please refer to our **response to W1**.
Reviewer_3rphOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies an interesting scenario in MAB in which the learner can choose the feedback channel, e.g., choosing a single arm or a dual arm pair to evaluate. The key difference from prior studies is that the optimal arm from the two channels can be different, so that a global optimal arm does not exist. As a result, the paper tries to develop an ϵ\epsilon-best arm algorithm that has estimators for different channels. A lower bound and an upper bound for the algorithm were provided. Preliminary results show in certain scenarios, the algorithm outperforms existing parameter-sharing baselines.

Critical strengths
  • The problem is well motivated and quite interesting to the reviewer. The main paper is well written.

  • The algorithm is easy to understand, though Algorithm 1 could be made cleaner to read. The ablation about the two components in Table 3 looks promising.

Critical weaknesses
  • There have been existing studies on fused feedback, as the authors cited, e.g., Wang et al. 2025a and Zeng et al 2026. While the difference to theirs is the misalignment of latent parameters, the reviewer is wondering whether the two channels are in fact decoupled, and by that I mean if their parameters can be estimated on their own. If so, the contributions of this paper would lean towards the incremental side. Can the authors provide a detailed explanation on this point?

  • Following the previous comment, it would be nice to have a table summarizing existing approaches for fused feedback, and providing a comparative analysis regarding their assumptions, lower/upper bounds. Also, a theoretically interesting question is whether fused feedback in light of misaligned parameters leads to better lower/upper bounds than single channel feedback. Could the authors provide a discussion or proof sketch to this?

  • The appendix is ill organized. Currently they read a plain list of math lemmas without a clear map to the key theorems. As a result it is very difficult to assess fully the technical correctness of this paper. Also, throughout the paper, only Eq. 1 is numbered while all other math results are not numbered. This makes it more difficult to track the correlations between different math derivations. There are also some writing issues that need proofreading. For example, line 336 should merge into line 335.

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer 3rph (Part 1/3)

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: Clarifying the prevalence of modality misalignment in practical fused bandit settings and why existing alignment-dependent algorithms fail to apply.

The key point is that the two feedback modalities are not merely two types of noisy observations from the same underlying utility. As stated in lines 49-51 of the revised manuscript (lines 47-49 of the original manuscript), “absolute ratings and pairwise preferences are often elicited through distinct procedures and may therefore convey complementary or discrepant information about the same candidate.” Thus, it is necessary and natural for the two modalities to be governed by genuinely different latent parameters and to induce different arm rankings.

This difference fundamentally changes the identification problem. Under the alignment assumption adopted by Wang et al. (2025a) and Zeng et al. (2026), both modalities share the same optimal arm, so fused feedback can be used to identify a single common optimum. Under parameter misalignment, however, the reward-optimal arm and the dueling-optimal arm may differ, and a common optimal arm may not exist at all. Therefore, the standard best-arm target established in existing fused-feedback work is no longer well-defined for our setting.

This motivates the two identification targets introduced in our paper. The ε\varepsilon-one objective asks for any arm whose gaps under both modalities are below ε\varepsilon, whereas the ε\varepsilon-all objective asks for the complete set of such arms. These targets are not addressed by existing work, particularly existing fused-bandit methods, and our experiments further demonstrate that the baseline algorithm fails when an optimal arm under one modality is no longer ε\varepsilon-optimal under both modalities.

AuthorsOpenReview ↗

Response to Reviewer 3rph (Part 2/3)

Weakness 2: Providing a comparative study against prior works with a summary comparison table.

Thank you for this helpful suggestion. Following your advice, we provide a comparative study against the most relevant methods with fused feedback below; this table and the following discussion is also added to Appendix B in the revision.

AlgorithmSettingQueries per round$^*$TargetUpper bound
ElimFusionStochastic fused bandit with alignment: μk>μℓ⟺νk,ℓ>1/2\mu_k>\mu_\ell\Longleftrightarrow\nu_{k,\ell}>1/22Cumulative weighted regretO(∑k≠1(αΔkR+(1−α)ΔkD)log⁡Tmax⁡{(ΔkR)2,(ΔkD)2/K})O\left(\displaystyle\sum_{k\ne1}\frac{\left(\alpha\Delta_k^R+(1-\alpha)\Delta_k^D\right)\log T}{\max\{(\Delta_k^R)^2,(\Delta_k^D)^2/K\}}\right)
DecoFusionSame aligned stochastic fused-bandit setting2Cumulative weighted regretUnder ℓk⋆=1\ell_k^\star=1, O(∑k≠1log⁡Tmax⁡{ΔkR/α,ΔkD/(1−α)})O\left(\displaystyle\sum_{k\ne1}\frac{\log T}{\max\{\Delta_k^R/\alpha,\Delta_k^D/(1-\alpha)\}}\right)
Lower bound (Wang et al., 2025a)Ω(∑k≠1log⁡Tmax⁡{ΔkR/α,ΔkD/(1−α)})\Omega\left(\displaystyle\sum_{k\ne1}\frac{\log T}{\max\{\Delta_k^R/\alpha,\Delta_k^D/(1-\alpha)\}}\right).
HyTS-GLBStructured fused bandit with alignment: θR=θD=θ⋆\theta_R=\theta_D=\theta^\star1Fixed-confidence identification of a unique exact best armO~(T⋆(θ⋆)log⁡1δ)\widetilde O\left(T^\star(\theta^\star)\log\frac{1}{\delta}\right)
Lower bound (Zeng et al., 2026)Eθ⋆[τδ]≥TLB(θ⋆)kl⁡(1−δ,δ)\mathbb E_{\theta^\star}[\tau_\delta]\ge T_{\mathrm{LB}}(\theta^\star)\operatorname{kl}(1-\delta,\delta).
WIT-BOTELIM (Ours)Structured fused bandit without an alignment requirement: θR\theta_R and θD\theta_D may differ1εone\varepsilon^{\mathrm{one}}- and εall\varepsilon^{\mathrm{all}}-BAI over SεS_\varepsilonO~(Rqd2ζ+(1+ζ)κ0−1d2+(1+ζ)∑r=1Rq[4rPˉR,rγ2+PˉD,r])\widetilde O\left(R_q\frac{d^2}{\zeta}+(1+\zeta)\kappa_0^{-1}d^2+(1+\zeta)\displaystyle\sum_{r=1}^{R_q}\left[\frac{4^r\bar P_{R,r}}{\gamma^2}+\bar P_{D,r}\right]\right)
Lower boundεone-BAI:2kl⁡(1−δs,δ)min⁡i∈Sε(HiR+4HiD);εall-BAI:2kl⁡(1−δ,δ)(max⁡i∈SεHiR+4max⁡i∈SεHiD).\varepsilon^{\mathrm{one}}\text{-BAI}: 2\operatorname{kl}\left(\frac{1-\delta}{s},\delta\right)\displaystyle\min_{i\in S_\varepsilon}\left(H_i^R+4H_i^D\right);\quad \varepsilon^{\mathrm{all}}\text{-BAI}: 2\operatorname{kl}(1-\delta,\delta)\left(\displaystyle\max_{i\in S_\varepsilon}H_i^R+4\displaystyle\max_{i\in S_\varepsilon}H_i^D\right).

∗^* The number of queries per round describes how feedback is acquired during sampling. A value of 22 means that the algorithm obtains both one reward observation and one dueling observation in each round, whereas a value of 11 means that it chooses either a reward query or a dueling query in each round. Here, s=∣Sε∣s=|S_\varepsilon|. The O~\widetilde O notation suppresses logarithmic factors in the problem parameters and confidence level.

''Among existing works on fused bandits, ElimFusion and DecoFusion address regret minimization, whereas only HyTS-GLB is designed for best-arm identification (BAI). However, HyTS-GLB aims to identify a common best arm, which may not exist in fused bandits with unaligned feedback, rendering HyTS-GLB inapplicable in this setting. Moreover, single-channel feedback algorithms can only identify either a reward-optimal or a dueling-optimal arm, whereas our Wit-BotElim algorithm is designed to identify an ε\varepsilon-optimal arm tailored to this unaligned environment. Because these methods pursue fundamentally different objectives, a direct theoretical comparison between their sample-complexity upper and lower bounds is not meaningful.''

Nevertheless, our numerical experiments comparing WIT-BOTELIM and HyTS-GLB in Section 4 demonstrate that HyTS-GLB fails to identify a satisfactory arm under unaligned feedback, underscoring the necessity of Wit-BotElim.

Furthermore, in the original manuscript, immediately following Theorem 3—which establishes the sample-complexity upper bound of Wit-BotElim—we provide a comparative analysis against RAGE (Fiez et al., 2019) and RAGE-GLM (Jun et al., 2021), as they serve as the most relevant modality-specific foundations for our analysis. Specifically, RAGE provides the phased transductive experimental-design framework utilized for the linear reward channel, whereas RAGE-GLM supplies the corresponding confidence bounds and allocation routine for the logistic dueling channel.

AuthorsOpenReview ↗

Response to Reviewer 3rph (Part 3/3)

Weakness 3: Improving Paper Organization and Presentation.

Thank you for pointing out these presentation issues. We have added two roadmap paragraphs among the beginning of Appendix C and D that connect each technical lemma to its corresponding main theorem.

Appendix C: The proof has four ingredients. Lemma 5 converts correctness into a lower bound on the information collected before stopping. Lemma 6 identifies the least-informative perturbation that moves an arm to the decision boundary. Lemma 7 makes that perturbation available even when the algorithm's expected sampling design is singular. Finally, Lemma 9 combines these ingredients and directly connects the resulting information constraints to HiRH_i^R and HiDH_i^D.

Appendix D: "This appendix gives the complete proof of the high-probability correctness and sample-complexity guarantee in Theorem 2. The proof follows a four-layer dependency chain. First, Appendix D.1 records the three external tools used throughout: effective rounding (Lemma 7), G-optimal design (Lemma 8), and fixed-design logistic confidence (Lemma 9). Second, Appendices D.2--D.4 turn these tools into the burn-in guarantee of Lemma 10, the phase allocations in equation 9 and equation 10, and the reward and dueling confidence statements in Lemmas 12 and 14. Third, those confidence statements feed into the phase-wise elimination guarantee (Lemma 1); a union bound then produces the simultaneous good event of Lemma 15, on which Lemma 16 validates every modality-wise and fused interval used by the algorithm. Fourth, Lemma 17 replaces the adaptive direction sets by deterministic envelopes, Lemmas 18 and 19 convert those envelopes into phase costs, and Lemma 20 supplies the stopping and correctness statement. Appendix D.10 then sums the phase costs to prove Theorem 2.

The last subsection, Appendix D.12, is not needed for the logical proof of Theorem 2; it separately explains how witness and bottleneck compression reduce the phase-wise experimental-design problems. The deterministic rate obtained here is subsequently compared with the expected lower bounds in Appendix D.11. To make these dependencies traceable, displays that define quantities used later are numbered and cross-referenced---beginning with the phase schedule and total risk budget in equation 5--equation 6."

We also number all equations and mathematical statements that are referenced elsewhere, and update the cross-references throughout the manuscript accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

For AC and Reviewers

Dear AC and Reviewers,

Thank you for your time, effort, and insightful feedback; below, we provide our detailed responses to each reviewer. While we sincerely apologize for submitting our rebuttal nearing the deadline of the author-reviewer-discussion period, we would be deeply grateful if you could take our responses into account during your discussions and final evaluations.

Sincerely, The Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.