{"id":"6166d44d-efaf-4e83-abb1-7849939421bd","arxiv_id":"2506.13125","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A new two-part regret metric and an explore-then-set-cover algorithm for stochastic multi-objective bandits are proposed, with sublinear regret bounds for Pareto-optimal and convex-supported arms.","lead":"The paper proposes a new regret metric for multi-objective multi-armed bandits that requires an algorithm to stay close to every Pareto-optimal arm in every objective, plus a set-based adjustment penalty. It also defines efficient Pareto-optimal arms as those on the convex hull of the Pareto front and gives an explore-then-cover algorithm with sublinear regret.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The polynomial-time greedy set-cover variant's cumulative adjustment-regret bound is unsupported: Theorem 3 bounds each selected arm's adjustment only via exact-cover minimality, and the final size-ratio argument does not control per-arm adjustments.","rationale":"The reader's weakest-assumption analysis correctly identifies the proof gap: Theorem 3's per-arm adjustment bound relies on the exact minimum set cover, and the greedy variant loses that premise. My independent reading confirms that the final paragraph's |B| <= O(log n)|A*| statement bounds only the cardinality of B, not the adjustment epsilon(b) of each selected arm. Since the cumulative adjustment-regret sums epsilon(b) over every b in B at every exploitation round, an unchecked large epsilon(b) would turn the claimed sublinear regret into linear regret. This is therefore a load-bearing concern about the polynomial-time variant, which is part of the paper's central contribution. I did not find an independent fatal flaw in the exact-cover analysis: the coverage-regret proof and the union-of-Pareto-arms covering argument appear coherent under the stated clean event, and the definitional framework is a reasonable contribution even though the EPO treatment remains conditional. The appropriate verdict is the reader's CONDITIONAL: the paper should be accepted only after the greedy-variant adjustment bound is either proven without minimality or the claim is weakened. Since my concern matches the reader's identified weakest assumption rather than introducing a new one, no change to the reader's verdict is needed.","tokens_in":14207,"tokens_out":28764,"duration_ms":329985,"concrete_test":"Run a targeted search over small constructed instances: take D=2, choose Pareto arms p1=(1,0.4), p2=(0.4,1), and add a dominated arm b=(0.99,0.1) together with several dominated arms clustered around b so that the greedy set-cover routine selects Dom(b) early. For each clean-event realization (empirical means within r of true means), run Algorithm 1 with the greedy cover and record whether b is in B and epsilon(b)=min_{a* in A*} max_d(mu_d(a*)-mu_d(b)). If any such realization has epsilon(b)>4r and b remains in B, then Term 2 of Theorem 3 is at least (T-T')epsilon(b), which is linear in T; dividing by |A*| T^{2/3} (n log T)^{1/3} will diverge as T grows. This would settle that the claimed polynomial-time regret bound fails for the stated algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3 proves the per-arm adjustment bound epsilon(b) <= 4r by arguing that if a non-PO arm b in B had a larger gap to every Pareto arm, then b's Dom set would be redundant in the minimum set cover, contradicting minimality of B. This argument is available only because B is the exact minimum set cover in Step 9. For the polynomial-time variant, Step 9 is replaced by an O(log n)-approximate greedy cover. Greedy covers need not be minimal: they can retain an arm selected early even after the arm becomes redundant, and the proof gives no epsilon(b) <= 4r guarantee for such an arm. The paper's final paragraph merely recalls |B| <= O(log n)|A*|, which bounds the number of terms in Term 2 but not their magnitudes. This is not a minor cosmetic gap: an arm b with epsilon(b) >> 4r contributes epsilon(b)(T-T') to Term 2, which is linear in T and would violate the claimed O(T^{2/3}) cumulative adjustment-regret bound. Step 5 does not automatically remove such an arm: it removes a only if some other empirical mean dominates a+2r in every coordinate. An arm b dominated by a PO arm p can survive the clean event when p exceeds b by less than 2r in one coordinate and by much more than 4r in another, because the empirical comparison is coordinatewise and the small-gap coordinate may flip. Thus the polynomial-time variant's central regret guarantee is not established as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a new regret measure for multi-objective multi-armed bandits (MO-MAB), consisting of a coverage-regret component and a cumulative adjustment-regret component, together with the notion of Efficient Pareto-Optimal (EPO) arms. It presents a two-phase algorithm (Algorithm 1): explore each arm for T' rounds, compute a confidence radius r, discard arms clearly dominated by others, build a set cover B of arms whose inflated empirical reward vectors dominate all remaining arms, and then pull the arms in B for the remaining rounds. The paper claims sublinear regret O(T^{2/3}(n log T)^{1/3}) when the exact minimum set cover is used and O(log n · T^{2/3}(n log T)^{1/3}) for a polynomial-time greedy set-cover variant, as well as an extension of the guarantees to EPO arms.","tokens_in":14477,"tokens_out":13909,"duration_ms":160195,"significance":"If the central claims hold, the paper makes a useful contribution by proposing a regret notion that penalizes poor performance in every objective rather than only the scalarized distance to the Pareto front, and by connecting multi-objective bandit exploration to set cover. The exact-cover analysis is coherent and rests on a standard concentration argument: the coverage-regret bound follows immediately from the clean-event analysis, and the cumulative adjustment-regret bound for exact minimum set covers is justified by the minimality-based redundancy argument. The paper is also honest in its experiments, comparing exact and greedy cover sizes on synthetic data. However, the polynomial-time variant's regret guarantee and the EPO extension are not adequately proven as written, so the paper needs revision before the main claims can be accepted.","major_comments":[{"comment":"The claimed cumulative adjustment-regret bound for the polynomial-time greedy variant is unsupported. The proof of the per-arm bound epsilon(b) <= 4r for b in B relies on B being the exact minimum set cover: if a Pareto-optimal arm a* dominates b with gap greater than 4r, then Dom(b) is contained in Dom(a*), making b redundant, which contradicts minimality. An O(log n)-approximate greedy set cover need not be inclusion-wise minimal; it can retain an arm b even after Dom(b) is covered by other selected arms, and for such b the contradiction argument does not apply. The final sentence of the proof only states |B| <= log n · |A*|, which bounds the number of terms in Term 2, not their magnitudes. An arm with epsilon(b) much larger than 4r would contribute (T - T') * epsilon(b) to Term 2, which is linear in T and would violate the claimed O(log n · T^{2/3}(n log T)^{1/3}) bound. A local repair would be to add a post-processing step that prunes B to an inclusion-wise minimal cover, which restores the redundancy argument (a redundant arm can be removed) while preserving |B| <= O(log n) · |A*|; alternatively, a different argument for the greedy variant must be supplied.","section":"Section 5, Theorem 3 and the concluding paragraph of its proof"},{"comment":"The extension of the regret guarantees to EPO arms is not rigorously established. The proof argues that a removed non-efficient arm a can be replaced by an artificial arm b_alpha = sum_i alpha_i a_i, because the rewards of b_alpha can be 'approximated for sufficiently large T by selecting a_i with probability alpha_i'. However, Algorithm 1 as written does not randomize in the exploitation phase; it pulls the remaining arms in B. The coverage-regret definition (Eq. (2)) requires, for each EPO arm a*, the existence of an actual arm a_t in the selected set A_t whose cumulative reward vector is within R of a*. A convex combination of arms is not an element of A_t, and in general no single arm in the convex combination dominates a* even when the combination does (for example, a* = (0.4, 0.4) is dominated by 0.5(1,0) + 0.5(0,1), but by neither (1,0) nor (0,1)). Thus, removing non-efficient arms can destroy coverage. The proof must either modify the algorithm to randomize and prove the regret bound for the resulting randomized process, or prove that some remaining arm in B covers each EPO arm within the claimed radius.","section":"Section 5, Theorem 4"}],"minor_comments":[{"comment":"The fourth contribution bullet duplicates the third bullet verbatim; one of them should be removed.","section":"Section 1"},{"comment":"The keyword 'sochastic' is a typo; it should read 'stochastic'.","section":"Keywords"},{"comment":"The definition of the EPO set uses sequences S and an asymptotic threshold T0, but the notation is not made precise: the length of the sequences, the quantifier order, and the meaning of 'for sufficiently large T' for a fixed sequence should be clarified, and the two displayed definitions of set-wise domination should be aligned.","section":"Section 4.1"},{"comment":"The proof of convergence is informal; it should be made rigorous by using the minimum positive gap between the mean rewards of PO and non-PO arms and showing that for r below half that gap, B must equal A*.","section":"Section 5, Theorem 2"},{"comment":"The regret bounds implicitly assume bounded rewards (e.g., rewards in [0,1]) since the proofs bound per-round regret by constants and Term 1 of Theorem 3 bounds the adjustment by 1 per pulled arm; this assumption should be stated explicitly in the model.","section":"Section 4 / Section 5"},{"comment":"The term 'DPO' is used before its definition as 'diverse set of Pareto Optimal arms', and the proof of Theorem 5 is terse: the claim that uniform random selection from B yields expected per-round difference at most O(2r) requires a more detailed derivation.","section":"Section 5, Theorem 5 and the diversity paragraph"}],"recommendation":"major_revision","confidential_remarks":"The exact-cover version of the algorithm and its analysis appear sound and publishable after revision. The greedy variant can likely be repaired by post-processing the cover to be inclusion-wise minimal, and Theorem 4 needs either a modified algorithm or a more careful argument. I therefore see this as a major revision rather than a rejection. The paper's scope fits the journal, though the novelty of the regret metric may need a stronger positioning relative to existing vector-valued regret notions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper's main contribution is a two-part regret definition for MO-MAB: coverage-regret (each optimal arm is approximated across all objectives) and cumulative adjustment-regret (penalizing redundant or dominated pulls). That is a genuine improvement over the Drugan-Nowe Pareto regret, which as they correctly note can be gamed by single-objective algorithms. The EPO set is a bandit-flavored repackaging of supported Pareto solutions, but the formalization is clean and the LP characterization is useful.\n\nThe exact set-cover version of the analysis is mostly sound. Theorem 1's concentration argument is standard; Theorem 3's per-arm adjustment bound uses a transitivity-plus-minimality argument that checks out when B is exactly the minimum cover. The coverage-regret proof correctly exploits the fact that exploration pulls all arms.\n\nThe soft spots are real, though concentrated. The polynomial-time variant using an O(log n)-approximate greedy set cover does not inherit Theorem 3's bound. That proof relies on every arm in B being irredundant: if a selected arm had a large gap to all Pareto arms, it would be covered by another selected arm and could be removed. Greedy covers are not minimal, so an arm selected early can remain even once redundant, and the per-arm epsilon(b) <= 4r guarantee is simply not established. Since the final paragraph only bounds |B|, not the per-arm gaps, the claimed O(log n T^(2/3)(n log T)^(1/3)) cumulative adjustment regret is unsupported. The stress-test note is right: such an arm would contribute linearly in T. This is not a cosmetic gap; the polynomial-time claim is the headline engineering result.\n\nThere are smaller issues. Theorem 4's argument that non-efficient arms can be replaced by randomized mixtures of other arms is hand-wavy, and Algorithm 1 does not actually perform the mixing. Theorem 5's 'average best arm' bound is asserted more than proven. The experiments recalibrate r below the theoretical value, so they don't validate the guarantees.\n\nThe exact-cover theory and the metric itself deserve serious refereeing. I'd send it to review, but the authors should be told the greedy bound needs either a new proof or a weakened claim, and the EPO mixing needs to be made actual or dropped.","headline":"New two-part regret metric is a real contribution, but the polynomial-time greedy variant's cumulative adjustment-regret bound is not proven.","tokens_in":15031,"tokens_out":4979,"would_cite":true,"duration_ms":49063,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","90C29","62L05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proposes a two-part regret metric and a set-cover algorithm that reaches every Pareto-optimal arm with sublinear regret.","keywords":["stochastic multi-armed bandits","multi-objective optimization","Pareto regret","coverage regret","efficient Pareto-optimal arms","set cover","regret minimization"],"falsifier":"Run Algorithm 1 with the greedy set cover on small instances and record, for every arm $b\\in B$, the largest coordinate gap to a Pareto-optimal arm that dominates it; if any gap exceeds $4r=\\sqrt{8\\log T/T'}$, the contradiction argument in Theorem 3 fails. Alternatively, enumerate the exact and greedy covers on the same instance and check whether the empirical cumulative adjustment-regret scales with $|B_{\\text{greedy}}|$ rather than with $|A^*|$.","tokens_in":13969,"feed_emoji":"🎰","tokens_out":10444,"duration_ms":104837,"temperature":0.7,"pith_summary":"This paper argues that the standard Pareto-regret metric for multi-objective multi-armed bandits is too weak: it measures only the distance to the Pareto front in one direction, so an algorithm that optimizes a single objective can look good while ignoring the others. It proposes a two-part regret definition that holds across all objectives at once: coverage-regret, which requires every Pareto-optimal arm to be within regret $R$ of some arm the algorithm selects, and cumulative adjustment-regret, which bounds the total adjustments needed for selected arms to weakly dominate the optimal set. It also introduces the class of efficient Pareto-optimal (EPO) arms, the subset of Pareto-optimal arms that lie on the convex hull of the front. The paper's algorithm explores each arm $T'$ times, builds a minimum set cover of arms whose inflated empirical means dominate all arms, and then pulls only that cover; for both regret parts it claims $O(T^{2/3}(n\\log T)^{1/3})$ regret, with an extra $\\log n$ factor when the set cover is computed by a polynomial-time approximation.","feed_headline":"Algorithm covers every Pareto-optimal arm with sublinear regret","feed_subtitle":"A new regret metric checks all objectives at once, and a set-cover bandit achieves sublinear regret.","key_machinery":"The load-bearing object is the minimum set cover $B$ of arms whose inflated empirical reward vectors $b+2r$ weakly dominate every arm, where $r=\\sqrt{2\\log T/T'}$ is the confidence radius after $T'$ pulls. Each arm carries a domination list $\\mathrm{Dom}(a)=\\{a': a+2r \\succeq a'\\}$, and the algorithm pulls only the cover $B$. The proofs rest on two covering facts: every Pareto-optimal arm is within $4r$ of some cover arm in every objective, and the minimality of $B$ forces every non-optimal cover arm to be within $4r$ of a Pareto-optimal arm that dominates it. Efficient Pareto-optimal arms are defined separately as PO arms that no convex combination of other PO arms weakly dominates, i.e., the arms on the convex hull of the Pareto front, and they are identified by a linear program once $A^*$ is known.","core_discovery":"The central claim is that a multi-objective bandit algorithm should be evaluated against every Pareto-optimal arm simultaneously, not merely by its minimum distance to the Pareto front. Formally, coverage-regret is the minimum over the selected arms of the worst-objective gap to each Pareto-optimal arm, while cumulative adjustment-regret is the total minimal $\\epsilon$ such that each pulled arm plus $\\epsilon$ in every coordinate weakly dominates some Pareto-optimal arm. On this footing, Algorithm 1 solves the problem: it pulls every arm $T'=(T/n)^{2/3}(2\\log T)^{1/3}$ times, estimates each mean within radius $r=\\sqrt{2\\log T/T'}$, deletes arms dominated by an improved competitor, and computes a minimum set cover $B$ such that every arm is weakly dominated by $b+2r$ for some $b\\in B$; it then pulls only the arms in $B$. Theorems 1 and 3 give coverage-regret and cumulative adjustment-regret of $O(T^{2/3}(n\\log T)^{1/3})$; Theorem 4 extends the same guarantees when $B$ is pruned to the efficient Pareto-optimal arms; and Theorem 5 gives the same rate for a single-arm-pulling version compared with the average of a diverse Pareto-optimal set.","pith_inferences":["The minimum set cover in Algorithm 1 is essentially an $\\epsilon$-net of the Pareto front with radius $2r$; viewing it that way connects the regret rate to classical covering numbers of the front.","The EPO definition identifies the convex hull of the Pareto front, which suggests that pure-exploration variants could identify EPO arms with linear-programming separability tests rather than exhaustive searches.","The $T^{2/3}$ rate is characteristic of explore-then-commit designs; an adaptive UCB-style exploration could plausibly push the regret to $\\tilde{O}(\\sqrt{T})$ while keeping the same metric, but that is not shown here.","The two-part regret metric could be adapted to constrained or adversarial MO-MAB settings, since it only requires per-objective gaps and set-cover structure."],"forward_implications":["If the regret bounds hold, any algorithm evaluated under the new metric must balance all objectives, so single-objective shortcuts that pass the old Pareto-regret test would no longer pass.","Both coverage-regret and cumulative adjustment-regret are sublinear, so Algorithm 1 can run for long horizons and still provably approach the Pareto front.","The polynomial-time variant with the $O(\\log n)$-approximate set cover makes the sublinear guarantee available without exponential computation, at a factor $\\log n$ in regret.","Theorem 5 gives the same $O(T^{2/3}(n\\log T)^{1/3})$ rate when only one cover arm is pulled per round against the average of a diverse Pareto-optimal set, extending the result to a single-arm online setting.","As $T\\to\\infty$, the confidence radius shrinks to zero and the returned cover set converges to the full Pareto-optimal set, or to the efficient Pareto-optimal set after pruning, so the algorithm is asymptotically consistent."],"supporting_citations":[{"why":"Defines the original Pareto-regret metric and a Pareto-aware UCB algorithm that this paper argues is inadequate and builds its critique against.","marker":"[1]"},{"why":"Supplies the standard multi-armed bandit framework, the clean-event definition, and the concentration and union-bound tools used in the regret proofs.","marker":"[2]"},{"why":"Provides the example of an algorithm that looks good under Pareto regret while optimizing a single objective, motivating the balanced regret metric.","marker":"[4]"},{"why":"Supplies the diversity notion in multi-objective optimization that underlies the efficient Pareto-optimal arms and the average-best-arm discussion.","marker":"[19]"},{"why":"Gives the set-cover approximation algorithm with an $O(\\log n)$ ratio used for the polynomial-time variant of Algorithm 1.","marker":"[20]"},{"why":"Bounds the expected number of Pareto-optimal maxima as polylogarithmic in $n$, used for the expected-case complexity of the exact set cover.","marker":"[21]"}],"fun_headline_variants":["New regret metric for multi-objective bandits covers all Pareto-optimal arms","Sublinear regret for every Pareto-optimal arm in MO-MAB","Set-cover bandit achieves sublinear regret on all objectives","MO-MAB algorithm: sublinear regret with full Pareto coverage","Efficient Pareto-optimal arms get sublinear regret in bandits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof of the cumulative adjustment-regret bound (Theorem 3) assumes the set-cover step returns the exact minimum set cover $B$; the polynomial-time greedy variant only approximates the cover, so the stated $O(\\log n\\,T^{2/3}(n\\log T)^{1/3})$ regret bound is not supported by the proof as written.","fun_headline_variants_meta":{"raw":{"variants":["New regret metric for multi-objective bandits covers all Pareto-optimal arms","Sublinear regret for every Pareto-optimal arm in MO-MAB","Set-cover bandit achieves sublinear regret on all objectives","MO-MAB algorithm: sublinear regret with full Pareto coverage","Efficient Pareto-optimal arms get sublinear regret in bandits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000602,"raw_usage":{"total_tokens":2820,"prompt_tokens":965,"completion_tokens":1855,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":581,"completion_tokens_details":{"reasoning_tokens":1764}},"tokens_in":581,"tokens_out":1855,"duration_ms":13197,"temperature":1.0,"reasoning_tokens":1764,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T00:38:10.980418+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with the greedy set cover on small instances and record, for every arm $b\\in B$, the largest coordinate gap to a Pareto-optimal arm that dominates it; if any gap exceeds $4r=\\sqrt{8\\log T/T'}$, the contradiction argument in Theorem 3 fails. Alternatively, enumerate the exact and greedy covers on the same instance and check whether the empirical cumulative adjustment-regret scales with $|B_{\\text{greedy}}|$ rather than with $|A^*|$.","supporting_citations":[{"cited_title":"In: The 2013 International Joint Conference on Neural Networks (IJCNN), pp","cited_arxiv_id":null,"evidence_quote":"Defines the original Pareto-regret metric and a Pareto-aware UCB algorithm that this paper argues is inadequate and builds its critique against."},{"cited_title":"Foundations and Trends®in Machine Learning12(1-2), 1–286 (2019)","cited_arxiv_id":null,"evidence_quote":"Supplies the standard multi-armed bandit framework, the clean-event definition, and the concentration and union-bound tools used in the regret proofs."},{"cited_title":"In: International Conference on Machine Learning, pp","cited_arxiv_id":null,"evidence_quote":"Provides the example of an algorithm that looks good under Pareto regret while optimizing a single objective, motivating the balanced regret metric."},{"cited_title":"Springer, New York (2007)","cited_arxiv_id":null,"evidence_quote":"Supplies the diversity notion in multi-objective optimization that underlies the efficient Pareto-optimal arms and the average-best-arm discussion."},{"cited_title":"Journal of the ACM (JACM)25(4), 536–543 (1978) 21","cited_arxiv_id":null,"evidence_quote":"Bounds the expected number of Pareto-optimal maxima as polylogarithmic in $n$, used for the expected-case complexity of the exact set cover."}],"review_version":1}