{"id":"a4ef5a66-358f-4c17-ad58-63896fe20b33","arxiv_id":"2504.15812","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"In stochastic multi-armed bandits with both reward and dueling feedback, the authors prove a regret lower bound and give an algorithm whose regret matches it up to a constant under a common dueling assumption.","lead":"The paper introduces a bandit model in which each round the learner receives both a numerical score for one option and a pairwise comparison between two options. It proves a lower bound and gives algorithms that split suboptimal options between the two feedback types, reducing the larger regret cost per option.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The matching to the simplified lower bound relies on the ell*_k = 1 assumption; instances satisfying the model's ordering assumptions can violate it with arbitrarily large regret gaps, so the near-optimality claim is not general.","rationale":"The reader's weakest assumption identifies the same condition I consider most load-bearing: the simplified lower bound and DecoFusion's matching upper bound both hinge on ell*_k = 1. The paper states this assumption explicitly and discusses the limitation in Section 4.3, so the concern is a substantive scope restriction rather than a hidden logical flaw. My constructed example shows the restriction is not mild: the ratio between the simplified and general lower bounds can be made arbitrarily large within the model's own ordering assumptions. The other issues noted by the reader (missing 1/2 factor, undefined event U_t in Appendix D.2, malformed pseudocode in Algorithm 2, arithmetic typos) are presentation or constant-factor problems that do not change the asymptotic matching under the stated assumption. I therefore support the CONDITIONAL verdict: the central claim is plausible and likely correct under ell*_k = 1, but the paper's advertised generality is limited, and the proof needs cleanup before the conditional claim can be fully verified.","tokens_in":1250,"tokens_out":2576,"duration_ms":247416,"concrete_test":"Construct the one-parameter family with K=3, mu = (0.9, 0.8, 0.7), nu_{1,2} = 0.51, nu_{2,3} = 0.9, and nu_{1,3} = 0.5+epsilon for epsilon tending to 0 (with nu_{3,1}=0.5-epsilon, etc.). For k=3, compute the ratio of the simplified lower-bound term 1/max{Delta_3^(R)/alpha, Delta_3^(D)/(1-alpha)} to the general lower-bound term min_{ell<3} (1-alpha)(Delta_3^(D)+Delta_ell^(D))/kl(nu_{3,ell},1/2) and show it diverges as epsilon goes to 0. Then run DecoFusion (Algorithm 2) with alpha=0.5 on a fixed epsilon, e.g., epsilon=0.01, for T=10^6, measure the per-arm regret for arm 3, and check whether it scales as log T/kl(nu_{3,1},1/2), exceeding the general lower bound by the predicted factor. If it does, the concern that the simplified matching is not general is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that DecoFusion matches the simplified lower bound up to a constant requires Corollary 2.4's assumption that for every suboptimal arm k, the most effective dueling competitor is arm 1, i.e., ell*_k = 1. The general lower bound in Theorem 2.3 has the dueling term min_{ell<k} (1-alpha)(Delta_k^(D)+Delta_ell^(D))/kl(nu_{k,ell},1/2), while the simplified bound (3) and DecoFusion's upper bound (5)-(6) only use the pair (k,1). When ell*_k != 1, the true lower bound can be much smaller than the simplified expression, and the algorithm can be arbitrarily suboptimal. Concretely, take K=3 with mu = (0.9, 0.8, 0.7), nu_{1,2} = nu_{1,3} = 0.51, nu_{2,3} = 0.9 (and symmetric complements). Then for k=3, Delta_3^(D) = 0.01, kl(nu_{3,1},1/2) is approximately 0.0002, and kl(nu_{3,2},1/2) is approximately 0.51, so ell*_3 = 2 != 1. The simplified lower-bound term for arm 3 is about 0.5*0.01/0.0002 = 25, while the general lower-bound term is about 0.5*(0.01+0.01)/0.51, about 0.0196, a ratio over 1000 that can be made arbitrarily large by letting nu_{3,1} approach 0.5. Under the good event A_t, DecoFusion duels k against 1 (because hat_nu_{1,k} >= 1/2 implies hat_nu_{k,1} <= 1/2), so it pays the large log T/kl(nu_{k,1},1/2) cost. The paper honestly acknowledges this in Section 4.3, but it means the abstract's claim of achieving the smaller regret for each arm is conditional on a substantive structural restriction, not a mild regularity condition.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the dueling-reward multi-armed bandit (DR-MAB), in which each round the learner obtains both a reward for one arm and the outcome of a duel between two arms, and regret is a weighted combination of reward regret and dueling regret. It derives an information-theoretic lower bound (Theorem 2.3) and a simplified lower bound (Corollary 2.4) under the assumption that the most effective dueling competitor of every suboptimal arm is the optimal arm. It then proposes two fusion algorithms: ElimFusion, an elimination method that shares a candidate arm set across feedback types, and DecoFusion, a decomposition method that randomly assigns each arm to reward or dueling exploration. The main theoretical claim is that DecoFusion matches the simplified lower bound up to a constant factor, with additional constant-regret behavior at α=0 and α=1. Experiments compare the algorithms against no-fusion baselines.","tokens_in":24881,"tokens_out":13497,"duration_ms":123258,"significance":"If the results hold, the paper contributes a new model that combines absolute and relative feedback, a lower bound showing the potential of fusion, and algorithms with logarithmic regret that improve over using either feedback alone. The algorithmic idea behind DecoFusion, especially the randomized decision-making that separates exploration and exploitation while balancing two feedback types, is novel and likely to be useful in similar hybrid-feedback settings. The paper is also careful to acknowledge in Section 4.3 that the near-optimality guarantee is conditional on the structural assumption ℓ*_k=1 for all suboptimal arms. The experimental study supports the qualitative claims, although it is limited to synthetic instances. The central caveat is that the matching-to-lower-bound claim is not established for general DR-MAB instances, and the manuscript should make this scope restriction more prominent.","major_comments":[{"comment":"The regret bound in Eq. (5) is not well-defined at α=0 and α=1 because it divides by α^2 and (1−α)^2, and the randomization threshold β=α^2/(α^2+(1−α)^2) degenerates at these endpoints. The paper advertises constant (T-independent) regret for α=0 and α=1 as a distinctive feature of DecoFusion, but the stated theorem does not rigorously cover these cases. The authors should either state Theorem 4.1 for α∈(0,1) and provide a separate argument for the endpoints, or adapt the proof with a limiting/separate analysis so that the endpoint claim is formally supported.","section":"Theorem 4.1 and Eq. (5), Section 4.3"}],"minor_comments":[{"comment":"The pseudo-code for dueling exploration has a dangling else: the 'if' on line 17 is closed by 'end if' on line 19, leaving the 'else' on line 20 syntactically unattached. The intended logic should be written as an if-else block with a single end if.","section":"Algorithm 2, lines 16-20"},{"comment":"The notation E[R_T | A_t] and E[R_T | A_t^c] in the regret decomposition is imprecise, since R_T is the cumulative regret over all T rounds and A_t is a per-round event. The intended expressions are sums over t of E[R_t 1{A_t}] and E[R_t 1{A_t^c}], where R_t is the per-round regret; this should be clarified to make the proof easier to follow.","section":"Appendix D.2, Step 3"},{"comment":"The phrase 'only the smaller among the reward and dueling-based regret for each individual arm' is informal and could be misread as applying without the min over dueling competitors. It would be helpful to state in the abstract that the dueling side of the lower bound is the best over competing arms ℓ<k, or to refer the reader to Theorem 2.3.","section":"Abstract and Section 1"},{"comment":"There is a typo on line 4 of the algorithm description: 'warm-up phase (detained in Algorithm 3)' should read 'detailed in Algorithm 3'.","section":"Section 3.1"},{"comment":"In a few places the text writes 'LLM' or 'LLN' where the intended phrase is 'law of large numbers'; for instance, 'maximal LLM' appears in the proof of Lemma 2.2 and should be 'maximal LLN'.","section":"Appendix D.1 and D.2"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is generally honest: Section 4.3 explicitly acknowledges the ℓ*_k=1 restriction, and the lower-bound and upper-bound derivations are independent. However, the framing in the abstract and Section 1 overstates the generality of the near-optimality result, and a referee who skims those parts could reasonably believe the algorithm matches the general lower bound. The concrete counterexample in my major comment shows the assumption is not a mild regularity condition but a substantive structural restriction. The endpoint α=0,1 issue in Theorem 4.1 is also worth fixing because the constant-regret phenomenon is advertised as a highlight. With a revised presentation and a corrected Eq. (11), the paper would be a solid contribution."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth a serious look. The paper defines a new bandit model (DR-MAB) in which each round the learner receives both an absolute reward and a pairwise comparison, and it proves the first lower bound for that model. That lower bound is the genuine contribution. The algorithms are more derivative: ElimFusion is a clean but suboptimal elimination marriage; DecoFusion uses a clever randomized decomposition to match the simplified lower bound up to constants.\n\nThe modeling and math are mostly solid. The change-of-measure lower bound is standard, the LP step that reduces the bound to a min over reward vs. dueling terms is correct in spirit, and the paper is honest about the fact that DecoFusion only matches the simplified bound. The central claim is nevertheless narrower than the abstract suggests. The 'efficient algorithm incurs only the smaller regret for each arm' statement is true for the simplified bound under the ell*_k = 1 assumption, not for the general lower bound. The stress-test example is valid: with K=3 you can make nu_{3,1} close to 0.5 and nu_{3,2} close to 0.9; then the best dueling competitor for arm 3 is arm 2, not arm 1, and the lower-bound ratio is arbitrarily large. DecoFusion, because it always duels against the estimated best arm, pays the larger log T / kl(nu_{k,1}, 1/2) cost. This is not a hidden flaw—Section 4.3 says it openly—but it means the abstract's phrasing overstates the scope. The revised version should put the assumption in the abstract and stop saying 'matching the lower bound' without the qualifier.\n\nThe proof defects are real but minor: Eq. (11) drops the factor 1/2 in the dueling regret, Appendix D.2 bounds an event E_t that was never defined, Algorithm 2's pseudocode has a dangling else/end-if, and there is a small arithmetic slip in the ElimFusion bound. All are fixable in revision. I did not find a fatal gap in the main arguments.\n\nWho is this for? People working on dueling bandits, stochastic bandits, and theory of RLHF/preference feedback. It deserves a serious referee. My recommendation: accept for review, require a careful pass that corrects the proof-presentation errors and recalibrates the abstract so the ell*_k = 1 condition is visible up front.","headline":"New model plus a solid lower bound; the algorithm's near-optimality is real only under an assumption the paper acknowledges but the abstract underplays.","tokens_in":25475,"tokens_out":6363,"would_cite":true,"duration_ms":58837,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62L05","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"In a bandit that gets both rewards and pairwise comparisons, the regret of each suboptimal arm can shrink to the smaller of the two feedback costs, and a decomposition algorithm attains this up to a constant factor.","keywords":["multi-armed bandits","dueling bandits","relative feedback","reward feedback","regret lower bound","feedback fusion","elimination algorithm","randomized exploration"],"falsifier":"Build a three-arm Bernoulli instance where arm 1 beats arm 2 only slightly ($\\Delta_2^{(D)}$ tiny) while arm 3 beats arm 2 overwhelmingly, so that $\\ell_2^* = 3$ rather than 1. Run DecoFusion with $\\alpha=0.5$ for increasing $T$, estimate $E[R_T]/\\log T$, and compare it to the simplified bound $C/\\max\\{\\Delta_2^{(R)}/\\alpha, \\Delta_2^{(D)}/(1-\\alpha)\\}$ summed over arms; exceeding the bound by a gap that grows with the advantage of arm 3 would falsify the matching claim.","tokens_in":24197,"feed_emoji":"🎰","tokens_out":9084,"duration_ms":70377,"temperature":0.7,"pith_summary":"This paper asks what happens when an online learner receives both absolute scores and relative comparisons at every round, a setting it calls the dueling-reward multi-armed bandit. It claims that for each arm that is worse than the best arm, the learner need only pay the cheaper of the two learning costs: roughly $\\log T / \\max\\{\\Delta_k^{(R)}/\\alpha, \\Delta_k^{(D)}/(1-\\alpha)\\}$, where the gaps measure reward and dueling disadvantage and $\\alpha$ weights feedback costs. The paper proves a matching lower bound, gives a simple elimination-based fusion algorithm, and then a decomposition-based algorithm whose regret matches the simplified lower bound up to a constant. A sympathetic reader would care because real systems such as LLM alignment collect both scalar ratings and pairwise preferences, and the result says fusing them can be strictly better than using either alone.","feed_headline":"Fusing rewards and duels cuts regret to the cheaper signal per arm","feed_subtitle":"Decomposition fusion matches the lower bound when the optimal arm is key comparator; free signals give constant regret.","key_machinery":"The carrying mechanism is an arm decomposition plus randomized exploration assignment. DecoFusion maintains two approximately decomposed sets $\\hat{K}^{(R)}_t$ and $\\hat{K}^{(D)}_t$ built from revised empirical log-likelihoods $\\hat{I}^{(R)}_{k,t}$ and $\\hat{I}^{(D)}_{k,t}$, which measure how much reward and dueling information has distinguished each arm. Each round the algorithm picks one exploration arm, then flips a coin with threshold $\\alpha^2/(\\alpha^2+(1-\\alpha)^2)$ to decide whether to explore it via reward while exploiting the dueling-optimal arm, or explore it via dueling while exploiting the reward-optimal arm. This split compensates for the mismatch between the estimated decomposition and the true one, and it is what converts the lower bound's per-arm minimization into a matching upper bound.","core_discovery":"The central discovery is that reward feedback (a numerical score for one arm) and dueling feedback (a winner between two arms) are not redundant in regret terms: their contributions to identifying a suboptimal arm add up, while the regret they incur does not. This leads to a regret lower bound in which each suboptimal arm contributes the minimum of a reward-based cost and a dueling-based cost. The paper's DecoFusion algorithm realizes this bound by partitioning suboptimal arms into a reward-explored group and a dueling-explored group, estimating these groups from empirical log-likelihoods, and randomly assigning one feedback type to exploration and the other to exploitation in each round. When each suboptimal arm is most effectively compared against the optimal arm, DecoFusion achieves $E[R_T] = O(\\sum_{k\\neq 1} \\log T / \\max\\{\\Delta_k^{(R)}/\\alpha, \\Delta_k^{(D)}/(1-\\alpha)\\})$, matching the simplified lower bound up to a constant. It also shows that for $\\alpha=0$ or $\\alpha=1$, where one feedback type is free, regret becomes constant in $T$.","pith_inferences":["The decomposition-and-randomize scheme is likely transferable to contextual or linear bandits where a scalar reward model and a preference oracle coexist: the same threshold logic could decide which signal explores which candidate, though the paper does not analyze that setting.","The lower-bound structure suggests an information-accounting view: reward and dueling samples are additive evidence for identifying an arm, so a learner should allocate each arm's exploration budget to whichever signal has the better regret-per-information ratio; this is an editorial rephrasing, not a formal theorem of the paper.","A concrete testable extension is to modify DecoFusion to duel against the empirically most informative comparator rather than the estimated optimal arm; on instances where $\\ell_k^*\\neq 1$ such a variant should close the gap to the general lower bound.","The constant-regret phenomenon at $\\alpha=0$ or $\\alpha=1$ suggests that adding a free comparison channel to a purely reward-based bandit can eliminate the logarithmic factor altogether, which is an implication the paper states for its model and that invites experiments in reward-plus-preference systems."],"forward_implications":["If both rewards and comparisons are available, systems like RLHF can be designed to pay only the smaller regret cost for each bad item, rather than the sum or a fixed blend of both costs.","When one feedback channel is free ($\\alpha=0$ or $\\alpha=1$), DecoFusion achieves $T$-independent regret, so exploration can be offloaded entirely to the free channel and exploitation to the other.","ElimFusion, which shares one candidate arm set between two elimination routines, still improves over no fusion but pays an extra factor of the number of arms from dueling elimination.","The near-optimal constant-factor guarantee requires that the optimal arm be the most effective dueling comparator for every suboptimal arm; outside that case the paper's simplified matching statement is not valid.","The regret formula gives a principled way to set the cost weight $\\alpha$: it trades off the reward gap and the dueling gap for each arm through the maximum in the denominator."],"supporting_citations":[{"why":"Supplies the classical consistent-algorithm definition and information-theoretic lower-bound technique that Lemma 2.2 and Theorem 2.3 adapt to the fused-feedback setting.","marker":"Lai & Robbins (1985)"},{"why":"Provides the dueling-bandit lower bound and the RMED algorithm whose empirical log-likelihood and comparison-arm selection DecoFusion reuses for the dueling side.","marker":"Komiyama et al. (2015)"},{"why":"Gives the empirical log-likelihood exploration rule and concentration lemmas that DecoFusion's revised information measures $\\hat{I}^{(R)}_{k,t}$ build on.","marker":"Honda & Takemura (2010)"},{"why":"Supplies the dueling elimination approach whose intrinsic $1/K$ suboptimality appears in ElimFusion's bound and motivates the more careful DecoFusion design.","marker":"Saha & Gaillard (2022)"},{"why":"Provides the reward-side elimination algorithm with confidence bounds that ElimFusion combines with dueling elimination through a shared candidate set.","marker":"Auer & Ortner (2010)"},{"why":"Defines the Condorcet-winner structure used to identify arm 1 as the unique optimal arm and to set the dueling gaps $\\Delta_k^{(D)}$.","marker":"Urvoy et al. (2013)"}],"fun_headline_variants":["Bandits fuse rewards and duels to pay only the cheaper cost","DecoFusion matches regret lower bound with mixed feedback","Reward and duel feedback: sum contributions, minimize regret","Fusing reward and dueling feedback achieves optimal regret","Stochastic bandits: choose cheaper feedback per arm"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The near-optimal guarantee assumes that for every losing arm, the cheapest way to learn about it by comparison is to duel it against the single best arm; if comparing it against some other arm gives better information per unit of regret, the claimed simplified matching can fail.","fun_headline_variants_meta":{"raw":{"variants":["Bandits fuse rewards and duels to pay only the cheaper cost","DecoFusion matches regret lower bound with mixed feedback","Reward and duel feedback: sum contributions, minimize regret","Fusing reward and dueling feedback achieves optimal regret","Stochastic bandits: choose cheaper feedback per arm"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000632,"raw_usage":{"total_tokens":2917,"prompt_tokens":945,"completion_tokens":1972,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":561,"completion_tokens_details":{"reasoning_tokens":1891}},"tokens_in":561,"tokens_out":1972,"duration_ms":12113,"temperature":1.0,"reasoning_tokens":1891,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:17:31.909030+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a three-arm Bernoulli instance where arm 1 beats arm 2 only slightly ($\\Delta_2^{(D)}$ tiny) while arm 3 beats arm 2 overwhelmingly, so that $\\ell_2^* = 3$ rather than 1. Run DecoFusion with $\\alpha=0.5$ for increasing $T$, estimate $E[R_T]/\\log T$, and compare it to the simplified bound $C/\\max\\{\\Delta_2^{(R)}/\\alpha, \\Delta_2^{(D)}/(1-\\alpha)\\}$ summed over arms; exceeding the bound by a gap that grows with the advantage of arm 3 would falsify the matching claim.","supporting_citations":[{"cited_title":"Regret lower bound and optimal algorithm in dueling bandit problem","cited_arxiv_id":null,"evidence_quote":"Provides the dueling-bandit lower bound and the RMED algorithm whose empirical log-likelihood and comparison-arm selection DecoFusion reuses for the dueling side."},{"cited_title":"and Gaillard, P","cited_arxiv_id":null,"evidence_quote":"Supplies the dueling elimination approach whose intrinsic $1/K$ suboptimality appears in ElimFusion's bound and motivates the more careful DecoFusion design."},{"cited_title":"and Ortner, R","cited_arxiv_id":null,"evidence_quote":"Provides the reward-side elimination algorithm with confidence bounds that ElimFusion combines with dueling elimination through a shared candidate set."},{"cited_title":"Generic exploration and k-armed voting bandits","cited_arxiv_id":null,"evidence_quote":"Defines the Condorcet-winner structure used to identify arm 1 as the unique optimal arm and to set the dueling gaps $\\Delta_k^{(D)}$."}],"review_version":1}