{"id":"5d48a2a3-2fdc-400a-b4c9-01438db24aef","arxiv_id":"2505.17869","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors formalize Best Group Identification in multi-objective bandits and give elimination algorithms with upper and lower sample-complexity bounds for Pareto and linear objectives.","lead":"This paper introduces a new bandit problem in which the task is to identify the best group of arms when rewards are multi-dimensional, using either Pareto optimality or a known weighted sum. It presents two elimination algorithms with sample-complexity guarantees and tests them in simulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GPSI lower-bound proof does not guarantee the perturbed optimal-group arm raises every coordinate of the group efficiency vector, so the optimal-group term in Theorem 3.5 is unsupported as written.","rationale":"The paper's main deliverables are two elimination algorithms with upper bounds and two lower bounds. Reading in good faith, the upper-bound arguments for Triple Elimination and EECB are coherent: the confidence-bound events are standard, the elimination lemmas are internally consistent, and the sample-complexity accounting follows from the maintained active sets. The apparent issue in EECB's count synchronization is not a real flaw, because n_d is maintained as a lower bound on the number of pulls of active arms in dimension d, so using beta(n_d) is conservative and valid. The genuine soft spot is the GPSI lower bound in Theorem 3.5. The proof's hard instance perturbs a single arm in an optimal group and claims the group's entire efficiency vector rises above the competing optimal group. That claim requires the perturbed arm to be the maximizer in every coordinate of the efficiency vector, or at least in every coordinate d >= 3 where the two optimal groups tie at a3. The stated condition (13) constrains only the first two coordinates, so the asserted domination can fail. This concern is load-bearing because Theorem 3.5 is the only support for the near-optimality claim, and the lower-bound sum over optimal-group arms contributes materially to that result. However, the gap is localized to the construction, not to the algorithm's logic; a strengthened instance (e.g., all arms in groups 1 and 2 equal to their efficiency vectors) appears capable of restoring the argument. Thus the concern warrants a proof repair before publication but does not overturn the main algorithmic contributions, so the reader's conditional verdict is appropriate.","tokens_in":23414,"tokens_out":25675,"duration_ms":211191,"concrete_test":"Construct a counterexample satisfying all stated conditions: take a1=0.9, a2=0.7, a3=0.7, a4=0.3, a5=0.1, and let group 1 contain an arm l with mu_{1,l} = (0.8, 0.51, 0.1) while another arm in group 1 has mu^3 = 0.7. After the prescribed shift s, R'_1 in dimension 3 remains 0.7, so G1 does not dominate G2 with gap epsilon+alpha, invalidating the proof step. Then check whether the theorem is repaired by setting every arm in groups 1 and 2 equal to the group efficiency vector (fully-dependent); if the change-of-measure argument goes through for that explicit instance, the lower bound may still be true but needs a strengthened construction.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing gap is in the proof of Theorem 3.5 (Appendix B.2), specifically the change-of-measure argument for arms in the Pareto-optimal groups 1 and 2. For each arm (1,l), the proof defines the alternative instance by adding s = a1 - min(mu^1_{1,l}, mu^2_{1,l}) + epsilon + alpha to all coordinates of arm (1,l), and asserts that in V(1,l) group G2 is dominated by G1 with gap epsilon+alpha. This would require R'_1 > R_2 + epsilon in every coordinate. For coordinates d >= 3, where R_1 and R_2 both equal a3, the shifted arm contributes mu^d_{1,l} + s, and the new efficiency in dimension d is max(a3, mu^d_{1,l} + s). Unless arm (1,l) is a coordinate-wise maximizer for every d >= 3 (or mu^d_{1,l} + s exceeds a3 + epsilon), R'_1 remains a3 in that coordinate, so the domination gap is zero, not epsilon+alpha. Condition (13) only lower-bounds coordinates 1 and 2 in each arm; it does not ensure that any arm attains all the maxima that define R1. Consequently the claimed per-arm lower bound for optimal groups does not follow from the stated construction. The same issue applies to arms (2,l). Since Theorem 3.5 is the basis for the claim that Triple Elimination is near-optimal for GPSI, this proof gap is load-bearing, though it does not affect the correctness or upper-bound proofs for the TE algorithm.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the Best Group Identification (BGI) problem in multi-objective multi-armed bandits, where arms are partitioned into groups and each group is summarized by an efficiency vector whose entries are the per-dimension best mean rewards among the group's arms. Two settings are studied: Group Pareto Set Identification (GPSI), where the goal is to output the set of Pareto-optimal groups up to an epsilon-approximation, and Linear Best Group Identification (LBGI), where a known weight vector makes the objective linear. For GPSI the paper proposes the Triple Elimination (TE) algorithm and proves an (epsilon, delta)-PAC guarantee with an instance-dependent sample-complexity upper bound of order sum_{i,j} 1/Delta_tilde_{i,j}^2 log(NKD/(delta Delta_tilde_{i,j})). For LBGI it proposes the Equal Effect Confidence Bound (EECB) algorithm and proves delta-correctness with an upper bound of order sum_{i,j} 1/(Delta_{i,j}/D)^2 log(NKD/(delta Delta_{i,j})). Lower bounds are claimed for both problems. Numerical experiments compare TE with ablations and a uniform-sampling baseline, and EECB with a TE-based baseline.","tokens_in":23783,"tokens_out":13534,"duration_ms":112988,"significance":"If the upper-bound results are correct, the paper provides the first fixed-confidence algorithms for best group identification in multi-objective bandits, a natural and previously under-explored problem. The TE and EECB algorithms are clean elimination schemes, and the upper-bound proofs are detailed and appear internally consistent under the stated concentration event. The numerical experiments, while limited, support the practical value of dimension and arm elimination. The main caveat is the GPSI lower bound: as written, the proof for arms in the Pareto-optimal groups does not establish the claimed per-arm lower bound, and hence the near-optimality statement for TE is not fully supported. This gap is local to the lower-bound construction and does not affect the correctness or sample-complexity upper bound of TE, so the paper merits a major revision rather than rejection.","major_comments":[{"comment":"The lower-bound proof for arms in the optimal groups is not valid as written. For each arm (1,l), the alternative instance V(1,l) adds s = a1 - min(mu^1_{1,l}, mu^2_{1,l}) + epsilon + alpha to all coordinates of arm (1,l), and the proof asserts that G2 is dominated by G1 with gap epsilon+alpha. This requires R'_1 > R_2 + epsilon in every coordinate. For d >= 3, both R_1 and R_2 equal a3, and the shifted arm contributes mu^d_{1,l} + s, so the new efficiency in coordinate d is max(a3, mu^d_{1,l} + s). Condition (13) lower-bounds only the first two coordinates of the arm means; it does not ensure that mu^d_{1,l} + s exceeds a3 + epsilon for d >= 3. If it does not, R'_1^d remains a3, G2 is not dominated by G1, and G2 is still in G*_epsilon, so the event E2 is not forced to have small probability under V(1,l). The same issue applies to arms (2,l). Consequently the per-arm lower bound for optimal-group arms, and hence the full sum in Theorem 3.5, does not follow from the stated construction. This does not affect the TE upper bound, but it is load-bearing for the claimed near-optimality of TE for GPSI. The gap could be repaired by strengthening the hard-instance construction, for example by ensuring that the perturbed arm saturates all coordinates of the group efficiency vector, and then re-verifying the alternative instance.","section":"Appendix B.2 / Theorem 3.5"}],"minor_comments":[{"comment":"The proof concludes that the final inequality holds 'because N≥2', but the displayed inequality involves (NKD)^{12}; since K,D≥1 the conclusion still holds, but the justification should cite NKD≥2 rather than N≥2.","section":"Appendix B, Lemma B.2"},{"comment":"The chain of inequalities in the proof would be easier to follow if it explicitly invoked the arm-elimination rule at line 12 of Algorithm 1; as written, the middle inequality is easy to misread.","section":"Appendix B, Lemma B.13"},{"comment":"The Uniform Sampling baseline is described as outputting 'all optimal arms along with non-optimal arms whose gap is less than ε'; this should refer to groups, not arms.","section":"Section 5.1"},{"comment":"There are several small typos: 'as most' in Theorem 4.1 should be 'at most', 'Appendix 3' in Remark 3.4 should be 'Appendix B', and the description of Δ_min in Section 5 is missing the quantity being minimized.","section":"Throughout"},{"comment":"The statement says 'for small ε > 0' but does not quantify how small ε must be relative to the parameters a1,...,a5; providing explicit inequalities would make the hard-instance class easier to verify.","section":"Theorem 3.5"}],"recommendation":"major_revision","confidential_remarks":"The main obstacle is the GPSI lower-bound gap in Appendix B.2, which is specific and load-bearing but appears repairable by modifying the hard-instance construction. The upper-bound contributions are solid and the paper is a reasonable fit for the journal. If the authors can fix the construction and re-verify Theorem 3.5, I would be willing to accept the paper after a further round of review."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper's new formulation—best group identification with component-wise max efficiency vectors—is genuinely new and worth knowing about. It cleanly generalizes Pareto set identification to grouped arms, and the two variants (GPSI and LBGI) are natural. The TE and EECB algorithms are sensible elimination designs, and the finite-time upper-bound proofs under the stated good event appear internally consistent. The LBGI lower bound also looks sound. Credit where due: the problem setup is crisp, the related work is covered fairly, and this is a reasonable contribution to pure-exploration multi-objective bandits.\n\nThe soft spot is the GPSI lower bound, Theorem 3.5. In the alternative instance V(1,l), the proof adds s = a1 - min(mu^1_{1,l}, mu^2_{1,l}) + epsilon + alpha to every coordinate of arm (1,l) and asserts that G2 is then dominated by G1 with gap epsilon+alpha. That requires R'_1 >= R2 + epsilon in every coordinate. For coordinates d >= 3, both R1 and R2 equal a3, so R'_1^d = max(a3, mu^d_{1,l} + s). Condition (13) only controls the first two coordinates of each arm; mu^d_{1,l} for d >= 3 is unconstrained. So the new efficiency in those coordinates can remain a3, and the claimed domination gap collapses. The per-arm lower bound for arms in the optimal groups therefore does not follow as written. This is a significant gap because Theorem 3.5 is the basis for the claim that TE is near-optimal for GPSI; the upper-bound proofs, however, do not depend on it.\n\nThe experiments are thinner than the text suggests: the GPSI baselines are mostly ablations of the same algorithm, and the LBGI comparison is a single random instance. That is minor relative to the lower-bound issue, but the \"strong empirical performance\" claim is overstated.\n\nWho should read this: anyone working on multi-objective pure exploration or structured bandit identification will find the formulation and the TE/EECB designs useful. It deserves a serious referee, but the authors should be asked to repair the lower-bound proof or soften the near-optimality claim. I would not desk-reject it.","headline":"New problem formulation and solid upper-bound work, but the GPSI lower-bound proof has a genuine gap that undercuts the near-optimality claim for Pareto-optimal groups.","tokens_in":24238,"tokens_out":3921,"would_cite":true,"duration_ms":37444,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper introduces fixed-confidence algorithms that identify Pareto-optimal groups and weighted-best groups from vector-valued bandit rewards, with sample-complexity upper bounds and lower bounds matching up to constants and log factors.","keywords":["multi-objective bandits","best group identification","Pareto set identification","linear best group identification","fixed-confidence pure exploration","sample complexity","elimination algorithms"],"falsifier":"Build a two-group instance with efficiency vectors $R_1=(0.9,0.7)$ and $R_2=(0.7,0.9)$, but arrange that the arm reaching $0.9$ in dimension 1 of group 1 is different from the arm reaching $0.7$ in dimension 2, then apply the paper's perturbation to one non-maximal arm and check numerically whether $R_1$ changes; if it does not, the change-of-measure lower bound for arms in optimal groups fails on that instance.","tokens_in":23237,"feed_emoji":"🎯","tokens_out":16027,"duration_ms":122155,"temperature":0.7,"pith_summary":"This paper introduces Best Group Identification (BGI), a fixed-confidence pure-exploration problem in multi-objective multi-armed bandits. Arms are split into groups, and each group is summarized by its efficiency vector, the coordinate-wise best mean reward attainable inside the group; in the Pareto version the optimal groups are those not uniformly outperformed by any other group, while in the linear version a known weight vector selects the group maximizing the weighted sum of its efficiency vector. For the Pareto version (GPSI), the paper proposes Triple Elimination (TE), which maintains active sets of groups, dimensions, and arms and eliminates only what must still be resolved; for the linear version (LBGI), it proposes Equal Effect Confidence Bound (EECB), which focuses sampling on the dimension whose weighted confidence radius is largest. The paper proves both algorithms are correct with probability at least $1-\\delta$ and gives instance-dependent sample-complexity upper bounds, together with lower bounds that match up to constants and logarithmic factors on constructed hard instances. If these bounds are right, BGI is the multi-objective group analogue of classic best-arm identification: difficulty is governed by inverse squared gaps, and the group structure does not add an exponential price.","feed_headline":"Two algorithms find optimal groups in multi-objective bandits","feed_subtitle":"Elimination-based TE and EECB make Pareto and weighted best-group problems tractable with near-matching sample bounds.","key_machinery":"The load-bearing object is the efficiency vector $R_i = (\\max_{j} \\mu^d_{i,j})_{d=1}^D$, built from the tensor of arm means; every group comparison is a comparison of these vectors. Around it the paper defines the group sub-optimality gap $\\Delta_i$ and the in-group arm gap $\\Delta_{i,j} = m(\\mu_{i,j}, R_i)$, where $m(u,v)$ is the smallest per-coordinate add-on that keeps $v$ from strictly dominating $u$, with combined gap $\\tilde{\\Delta}_{i,j} = \\max(\\Delta_i, \\Delta_{i,j}, \\epsilon)$ for GPSI. Both algorithms are driven by the confidence radius $\\beta(r,\\delta) = \\sqrt{2\\log(4NKDr^2/\\delta)/r}$, which shrinks as samples accumulate; TE eliminates a group when a competitor's estimated efficiency vector is $2\\beta$ ahead, freezes a dimension once all pairwise differences are separated by $4\\beta+\\epsilon$, and eliminates an arm when its estimated mean trails its group's efficiency by $2\\beta$. EECB's distinctive mechanism is its dimension-selection rule: at each round it samples the dimension $d$ whose $w_d \\beta(n_d,\\delta)$ is largest, so weighted uncertainty is equalized and every gap has a per-dimension projection of at least $\\Delta_{i,j}/D$.","core_discovery":"The central claim is that GPSI can be solved by Triple Elimination with sample complexity $O(\\sum_{i,j} \\tilde{\\Delta}_{i,j}^{-2} \\log(NKD/(\\delta \\tilde{\\Delta}_{i,j})))$, and LBGI can be solved by EECB with complexity $O(\\sum_{i,j} (\\Delta_{i,j}/D)^{-2} \\log(NKD/(\\delta \\Delta_{i,j})))$, while any correct algorithm needs $\\Omega(\\sum_{i,j} \\tilde{\\Delta}_{i,j}^{-2} \\log(1/\\delta))$ samples on the hard instances. TE achieves this by running three nested elimination phases: reject groups whose estimated efficiency vector is dominated by another active group, freeze resolved dimensions once pairwise order is statistically clear, and drop arms whose mean is far below their group's efficiency. EECB achieves its bound by pulling, in each round, all active arms in the dimension $d$ with maximal $w_d \\beta(n_d,\\delta)$, which keeps weighted confidence widths balanced across dimensions; this equal-effect rule converts the $D$-dimensional problem into per-arm gap problems with an effective $D$-way slack. The lower bounds are proven by perturbing one arm's reward distribution on fully-dependent Gaussian instances and applying a change-of-measure identity, so the claimed near-optimality is for those instance classes rather than for every environment.","pith_inferences":["Editorial: an implicit next step is the fixed-budget version of BGI, where the stopping rule is replaced by a fixed round budget while the same elimination and equal-effect sampling rules are kept; the paper does not analyze this regime.","Editorial: because EECB's sampling weights are read only through $w_d \\beta(n_d,\\delta)$, a natural extension replaces known weights by estimated dimension importances, but the correctness argument would need new concentration bounds and is not in the paper.","Editorial: the lower-bound hard instances use fully-dependent Gaussian reward vectors, a worst-case dependence structure; on independent or negatively correlated dimensions the practical sample counts may be lower than the worst-case bound, which the paper leaves open."],"forward_implications":["If TE's upper bound is correct, a learner can identify the Pareto-optimal groups without estimating every arm to the same accuracy; arms with large in-group gaps or groups far from the Pareto front are discarded after few pulls.","If EECB's upper bound is correct, the known-weight linear problem has the same inverse-squared-gap scaling as single-objective best-arm identification, with the number of dimensions entering only through the effective gap $\\Delta_{i,j}/D$.","The lower bounds imply that on the constructed fully-dependent Gaussian instances, no $(\\epsilon,\\delta)$-PAC or $\\delta$-correct algorithm can beat these rates, so the algorithms are near-optimal there up to constants and logarithmic factors.","The experiments show TE beating uniform sampling and simplified eliminations, and EECB beating a Pareto-first baseline by an order of magnitude, so the theoretical savings appear in practice on the tested instances."],"supporting_citations":[{"why":"Supplies the change-of-measure lemma used to turn event probabilities into per-arm sample lower bounds in both Theorem 3.5 and Theorem 4.2.","marker":"[KCG16]"},{"why":"Introduces Pareto front identification in multi-objective bandits and the accept/reject elimination structure that Triple Elimination generalizes to groups and dimensions.","marker":"[ACOD16]"},{"why":"Provides the active-set action-elimination template whose confidence-radius shrinking both algorithms use for group, dimension, and arm elimination.","marker":"[EDMMM06]"},{"why":"Defines the fixed-confidence bandit Pareto set identification problem and gap notions that GPSI builds on; TE is positioned as a group-level extension of this line.","marker":"[KKR24c]"},{"why":"An elimination-based almost-optimal exploration algorithm cited together with EDMMM06 as the source of the per-round elimination logic in TE.","marker":"[KKS13]"}],"fun_headline_variants":["Best group identification solved in multi-objective bandits","Pareto and weighted best groups found with near-optimal bounds","Two elimination algorithms identify optimal groups in bandits","New algorithms achieve matching sample bounds for best groups"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The GPSI lower-bound proof needs the perturbation of a single arm in an optimal group to shift that group's efficiency vector in every coordinate; the paper does not guarantee that each arm attains its group's maximum in every dimension, and if one does not, the alternative instance leaves the old efficiency vector intact and the lower bound for optimal-group arms is not established.","fun_headline_variants_meta":{"raw":{"variants":["Best group identification solved in multi-objective bandits","Pareto and weighted best groups found with near-optimal bounds","Two elimination algorithms identify optimal groups in bandits","New algorithms achieve matching sample bounds for best groups"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001089,"raw_usage":{"total_tokens":4560,"prompt_tokens":963,"completion_tokens":3597,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":3533}},"tokens_in":579,"tokens_out":3597,"duration_ms":19048,"temperature":1.0,"reasoning_tokens":3533,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:39:40.202844+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build a two-group instance with efficiency vectors $R_1=(0.9,0.7)$ and $R_2=(0.7,0.9)$, but arrange that the arm reaching $0.9$ in dimension 1 of group 1 is different from the arm reaching $0.7$ in dimension 2, then apply the paper's perturbation to one non-maximal arm and check numerically whether $R_1$ changes; if it does not, the change-of-measure lower bound for arms in optimal groups fails on that instance.","supporting_citations":[],"review_version":1}