{"id":"89f7197a-5246-48d7-86fe-7a6be529b110","arxiv_id":"2506.15856","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"A decentralized UCB variant learns unknown coordination thresholds and avoids decoy arms, reportedly approaching oracle-level cumulative reward in a small simulated environment.","lead":"This paper studies a team of agents that must learn, through trial and error, how many teammates are needed to activate each task, while some tasks are decoys that never pay off. The authors propose a decentralized bandit algorithm, T-Coop-UCB, and report that it approaches the reward of an omniscient Oracle in simulations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Stochastic failure streaks trigger an unbounded threshold increase that permanently abandons the optimal arm; with m unspecified, the near-Oracle claim cannot hold for Algorithm 1 as written.","rationale":"The reader's weakest assumption targets the threshold estimator: m is unspecified and the increase rule has no upper bound. My stress-test sharpens this into a concrete failure mode: after a finite streak of stochastic failures, the algorithm increments ĥ_2 beyond the team size M, after which the arm is never pulled again and the threshold can never be corrected downward. Since the decrease branch requires a success with fewer agents, and no coalition can satisfy an estimate of 4, the error is permanent. This directly undermines the strongest claim that T-Coop-UCB 'achieves near-Oracle performance': in the base environment, near-Oracle performance requires persistently pulling Arm 2, but the described update rule will eliminate that arm with high probability for any realistically small m. The paper offers no value for m, no clamping of ĥ_i to [1,M], and no tie-breaking rule for the initially all-infinite UCB values, so the reported results are not reproducible from the manuscript. The concern is addressable by specifying these parameters and providing sensitivity analysis, consistent with the reader's conditional verdict; hence no verdict change is needed.","tokens_in":9949,"tokens_out":5926,"duration_ms":64409,"concrete_test":"Implement Algorithm 1 exactly as specified with m as a free parameter and no upper bound on ĥ_i, using the base environment in Table 1 (M=3, Arm 2: p=0.6, h=3). For m = 1,3,5,10,20, compute across 30 seeds the mean per-round reward over T=10,000 and the fraction of runs in which ĥ_2 exceeds 3 and never returns. If this fraction is non-negligible or mean reward falls materially below the Oracle's 12 per round for any m ≤ 20, the close-to-Oracle claim fails under the specified update rule and requires the missing parameter/bound to be disclosed and justified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1's threshold update (lines 14-17) increases ĥ_i(t) after m consecutive failures at the current coalition size. Because rewards are Bernoulli with p_i < 1 even when the threshold is met, a failure does not imply h_i > N. On the optimal Arm 2 (p_2=0.6, h_2=3), m consecutive failures occur with probability (0.4)^m per attempt; e.g., m=3 gives 6.4% per block, so abandonment within T=10,000 is virtually certain. Once ĥ_2 is incremented to 4, no coalition of M=3 can satisfy it, the arm receives no pulls, and the estimate never decreases because the decrease rule only fires on success with fewer agents. Thus the algorithm permanently foregoes the only near-Oracle arm. The paper never specifies m, bounds on ĥ_i, or a reset mechanism, making Algorithm 1 undefined and the reported near-Oracle performance unreproducible. The central claim therefore rests on an implicit choice of m (and of tie-breaking/initial allocation) that is absent from the manuscript.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Threshold-Coop-UCB (T-Coop-UCB), a decentralized multi-agent bandit algorithm for a setting in which each arm yields a reward only when a minimum (unknown) number of agents pull it simultaneously, and where some 'decoy' arms require coordination but give zero reward. Agents maintain synchronized estimates of activation thresholds and reward means, form coalitions greedily using UCB scores, and update threshold estimates on the basis of observed successes and failures. The authors evaluate T-Coop-UCB in one base environment (M=3 agents, K=5 arms) over T=10,000 rounds and compare it with Random, Independent UCB1, Cooperative UCB1 (known thresholds), and an Oracle policy. The reported results show that T-Coop-UCB approaches the Oracle in cumulative reward and regret, outperforming the baselines in cumulative reward, regret, and valid allocations. The paper includes no formal regret analysis; the claims are empirical and based on 30 averaged runs with 95% confidence intervals.","tokens_in":10141,"tokens_out":2979,"duration_ms":32615,"significance":"If the claimed empirical performance were backed by a fully specified, reproducible algorithm, the paper would address a genuinely interesting and underexplored MA-MAB variant: coordination requirements and decoy arms create ambiguous zero-reward feedback that standard decentralized bandit algorithms do not handle. The problem formulation is clean, and the comparison against an Oracle and several baselines is a sensible first evaluation. The strengths are the clearly stated setting, the use of averaged runs with confidence intervals, and the introduction of decoy arms as a structural challenge. However, the paper's contribution is entirely empirical, the experiments are limited to one small environment (M=3, K=5), no code is provided, and, most importantly, Algorithm 1 as written is incomplete. The central 'near-Oracle' claim therefore cannot currently be reproduced or trusted; these issues are fixable within the scope of the manuscript, which is why I am not recommending rejection, but they are load-bearing and require a major revision.","major_comments":[{"comment":"The threshold update rule is not well-defined: the parameter m is declared in Algorithm 1 but never given a value in Section 5 or anywhere else, and the 'Increase ĥ_i(t)' branch has no upper bound and no reset or decrement mechanism other than the success-with-fewer-agents rule. In the base environment, Arm 2 has p_2=0.6 and h_2=3, so at the estimated threshold ĥ_2=3 each pull by the full team fails with probability 0.4; a run of m consecutive failures occurs with probability (0.4)^m per block, which for any reasonable m (e.g., m=3 gives 6.4% per block) is virtually certain over T=10,000 rounds. Once ĥ_2 is increased to 4, no coalition of M=3 agents can satisfy it, so Arm 2 is never pulled again and the estimate never decreases because the decrease rule fires only on a success with fewer agents. The near-Oracle results in Figures 2-4 therefore depend on an implicit choice of m or on an unstated safeguard. Please specify m, any cap on ĥ_i, and a complete reset/decrement rule, and report results across a range of m.","section":"Section 4, Algorithm 1"},{"comment":"The greedy assignment procedure is underspecified. The text says agents are 'assigned greedily to arms based on ĥ_i(t)' and that remaining unassigned agents are allocated 'to the next-best available arms, if feasible, or remain idle,' but there is no formal algorithm: no tie-breaking rule, no order in which arms are considered, no definition of feasibility, and no proof that all agents independently arrive at the same allocation. Because the paper claims decentralized coordination without centralized control, the mechanism by which synchronized estimates produce identical joint actions needs to be specified precisely. As written, the experiment is not reproducible from Algorithm 1 alone.","section":"Section 4, Coalition Formation"},{"comment":"The central empirical claims ('consistently outperforms,' 'near-Oracle performance') are supported only by visual inspection of plotted curves. There are no numerical tables of cumulative reward, regret, or valid allocations, and no statistical tests or per-run distributions beyond shaded 95% confidence intervals. Given that the entire contribution is empirical, the paper should report the numerical values underlying the figures, including confidence intervals, and state explicitly how 'near-Oracle' is measured (e.g., fraction of Oracle reward at the end of the horizon). This is necessary for the reader to assess whether the differences among T-Coop-UCB, Cooperative UCB1, and the Oracle are meaningful.","section":"Section 6"}],"minor_comments":[{"comment":"There are several typographical and formatting errors: 'UA V' should be 'UAV', 'M USICAL CHAIRS' should be 'MUSICAL CHAIRS', and 'GAMEOF THRONES' should be 'GAME OF THRONES'. Please proofread the manuscript.","section":"Section 2"},{"comment":"In the text discussing Cooperative UCB1, the phrase 'its unable to tell' should be 'it is unable to tell'. Also, the claim that T-Coop-UCB 'mirrors the O(log T) regret bounds established in cooperative multi-agent bandits' is misleading because the paper provides no regret bound for T-Coop-UCB; the text should clearly distinguish an empirical analogy from a theoretical result.","section":"Section 6"},{"comment":"The experimental setup does not state the value of the failure threshold m used in the simulations, nor whether any cap was placed on ĥ_i(t). Please include these details in the experimental parameters.","section":"Section 5"},{"comment":"The paper does not mention code availability or a supplementary implementation. Given that the contribution is empirical and the algorithm has several free parameters, providing code or at least a detailed pseudocode version with all tie-breaking rules would substantially improve reproducibility.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The paper reads more like a workshop-style empirical study than a complete journal article. The central issue is not the novelty of the setting or the quality of the writing, but that Algorithm 1 as printed is not a well-defined algorithm: the failure-count parameter m is absent, the threshold increase is unbounded, and the greedy assignment is informal. The skeptical objection about stochastic failure streaks permanently abandoning the optimal arm is a genuine correctness concern for the reported near-Oracle performance. I would recommend major revision with a request for a fully specified algorithm, a sensitivity analysis over m, and numerical results tables; without these, the empirical claim is not reproducible."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this paper is worth a look for the problem, not for the algorithm as written. The new setting — cooperative bandits where an arm yields reward only if an unknown number of agents pull it, with decoy arms that waste coordinated effort — is a real gap in the MA-MAB literature. The authors position it carefully against collision-avoidance, capacity-limited, and known-threshold models, and the related work is honest.\n\nThe soft spot is load-bearing, not cosmetic. In Algorithm 1, the threshold estimate increases after m consecutive failures at the current coalition size and only decreases on success with fewer agents than the estimate. In the test environment, Arm 2 has p=0.6 and h=3, with M=3. Once the team commits to all-on-Arm-2, a streak of m zero-reward rounds is inevitable for any finite m over T=10,000 (for m=3 the expected wait is small; for m=10 it is still on the order of 10^4 rounds). When the estimate increments to 4, no coalition of 3 can satisfy it, the arm is never pulled again, and the estimate never falls. T-Coop-UCB permanently abandons the arm it needs for near-Oracle performance. The manuscript never specifies m, never bounds the estimate, and gives no reset mechanism, so Algorithm 1 is undefined and the central claim is unreproducible.\n\nSmaller issues: the greedy assignment rule is underspecified; the 'decentralized' claim leans on free, instantaneous global synchronization every round (acknowledged, but it severely weakens the framing); and there are no code or tables, only plots. Baselines are reasonable, though the known-threshold Cooperative UCB1 baseline deserves more analysis. The citation pattern is fair. Credit where due: the problem formulation is clear, the zero-reward ambiguity is well articulated, and the paper does not pretend to have theory.\n\nBottom line: the setting deserves a venue and the algorithm is probably repairable — bound the threshold at M, use a statistically sound test before increasing, and report m with sensitivity analysis. But this manuscript's headline claim does not survive a close reading. It should go to peer review with the expectation of major revision.","headline":"The problem setting is genuinely new and worth knowing about, but Algorithm 1 as written has a load-bearing specification gap: for any finite failure-count parameter m, stochastic zero-reward streaks will push the estimated threshold of the optimal arm above M and permanently abandon it, so the near-Oracle claim cannot hold as stated.","tokens_in":10639,"tokens_out":5071,"would_cite":true,"duration_ms":51626,"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":"A decentralized team of agents can learn each arm's hidden activation threshold and reward distribution well enough to nearly match a centralized Oracle, despite decoy arms that mimic ordinary failures.","keywords":["cooperative multi-agent bandits","threshold-activated rewards","decentralized coordination","decoy arms","coalition formation","UCB","unknown thresholds","multi-agent learning"],"falsifier":"Run an arm whose true threshold is 1 and whose success probability is small, say $p=0.05$, with $m$ set to any finite value. With one agent pulling, runs of $m$ failures occur with probability at least $(0.95)^m$, so the update rule 'if failure after $m$ attempts at coalition size, increase $\\hat{h}_i(t)$' will push the threshold estimate above the true value even though the coalition size already satisfies the threshold; observing this in simulation would show that the threshold estimator cannot distinguish stochastic failure from insufficient coordination.","tokens_in":9751,"feed_emoji":"🤝","tokens_out":4668,"duration_ms":44108,"temperature":0.7,"pith_summary":"This paper introduces a cooperative multi-agent bandit setting in which an arm pays out only when at least an unknown number of agents pull it simultaneously, and some arms are decoys that never pay. The authors propose T-Coop-UCB, a decentralized algorithm that maintains upper-confidence reward estimates together with learned estimates of each arm's activation threshold, and show empirically in a three-agent, five-arm environment that it approaches the reward of a centralized Oracle that knows everything. The claim matters because standard multi-agent bandit work either assumes rewards are individually attainable or that coordination requirements are known in advance; this setting removes both assumptions. The paper's central assertion is that joint threshold learning plus decoy avoidance is what closes most of the gap to the Oracle.","feed_headline":"Team learns hidden coalition sizes, near-matches Oracle","feed_subtitle":"A UCB variant jointly infers each task's minimum agent count and reward odds from zero-reward feedback alone.","key_machinery":"T-Coop-UCB is a decentralized UCB algorithm in which each agent computes $\\mathrm{UCB}_i(t)=\\hat{\\mu}_i(t)+\\sqrt{2\\log t / n_i(t)}$ from shared observations, sorts arms by UCB, and greedily assigns agents to arms according to the current threshold estimates $\\hat{h}_i(t)$. The two coupled estimators do the work: the reward estimator is the standard sample mean updated only on successful activations, and the threshold estimator is a conservative rule that decreases $\\hat{h}_i(t)$ when an arm succeeds with fewer agents than estimated and increases it only after $m$ consecutive failures at the current coalition size. This pair turns zero-reward feedback—ambiguous between stochastic failure, insufficient coalition size, and decoy arms—into a signal for both what to pull and how many agents to send.","core_discovery":"The central claim is stated in the results: T-Coop-UCB 'consistently outperforms baseline methods in cumulative reward, regret, and coordination metrics, achieving near-Oracle performance.' Concretely, the paper argues that a team of decentralized agents, communicating freely but with no centralized action assignment and no prior knowledge of activation thresholds, can learn both the minimum coalition size and the reward distribution of every arm, and that this joint learning outperforms a cooperative UCB baseline that is told the true thresholds in advance. The environment that supports the claim is small (M=3 agents, K=5 arms, one decoy arm with zero reward, horizon 10,000 rounds, 30 runs), and the Oracle is a centralized policy with full knowledge of thresholds and success probabilities. The paper does not claim a formal regret bound; it reports empirical regret that tracks below an O(log T) reference in the tested setting.","pith_inferences":["The threshold-update rule is under-specified in Algorithm 1: $m$ is listed as a parameter but never assigned, and no cap prevents $\\hat{h}_i(t)$ from exceeding the number of agents $M$, so the pseudocode alone does not pin down a reproducible algorithm.","The ambiguity between stochastic failure and insufficient coalition size is structural: any algorithm that only sees aggregated zero reward must either accept false threshold increases or spend extra exploration on repeated trials, so the near-Oracle results may depend on the specific arm configuration used in the paper.","A natural testable extension is to compare T-Coop-UCB against a variant that tracks success probability at each coalition size separately, which would directly separate stochastic failure from threshold violation and likely improve sample efficiency.","In settings where the best strategy requires splitting agents across several valuable arms rather than sending the whole team to one arm, the greedy assignment step would need a load-balancing mechanism; that regime is not covered by the paper's experiments."],"forward_implications":["A decentralized team with free communication can jointly infer both which arms pay and how many agents each arm needs, without a central planner assigning actions.","Knowing the true thresholds in advance is not enough: Cooperative UCB1, which has the thresholds but cannot disambiguate ambiguous failures, underperforms T-Coop-UCB, so adaptive threshold learning carries the performance gain.","Decoy arms can be identified and avoided through shared reward feedback, even though they produce the same zero payoff as ordinary failures.","Empirical regret tracks below an O(log T) reference in the tested environment, indicating efficient structural learning, although no formal regret bound is claimed.","Because the best arm in the base environment requires all three agents, overcommitment is not an issue there; the framework's value in larger teams would require allocation across several worthwhile arms simultaneously."],"supporting_citations":[{"why":"Supplies the UCB1 finite-time analysis and exploration bonus that T-Coop-UCB builds its reward estimates on.","marker":"[Auer et al., 2002]"},{"why":"Defines the closest prior threshold-bandit setting, with a known threshold, which the paper contrasts against its unknown multi-agent thresholds.","marker":"[Abernethy et al., 2016]"},{"why":"Models arms with finite shareable resources and per-load rewards, the capacity-based setting the paper contrasts with all-or-nothing threshold activation.","marker":"[Wang et al., 2022]"},{"why":"Establishes the collision-avoidance line of multi-agent bandits, where overlap is a failure mode rather than a required coordination mechanism.","marker":"[Liu and Zhao, 2010]"},{"why":"Provides the O(log T) regret benchmark for cooperative multi-agent bandits with known structure that the paper uses as a reference curve.","marker":"[Landgren et al., 2016]"},{"why":"Introduces a decentralized algorithm designed to avoid simultaneous pulls, representing the opposite coordination goal from the paper's coalition requirement.","marker":"[Rosenski et al., 2016]"}],"fun_headline_variants":["T-Coop-UCB learns hidden thresholds, near-Oracle results","Decentralized bandits crack unknown coalition sizes","Multi-agent bandits: infer thresholds, dodge decoys","Cooperative agents beat baseline told true thresholds","Unknown cutoff? Decentralized bandits still near-Oracle"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that $m$ consecutive failures with a given coalition size reliably mean the estimated threshold is too low; in the paper's own environment, the same zero-reward observation can come from a low success probability or from a decoy arm, and the paper does not specify a value for $m$ or an upper bound on the threshold estimate, so the estimator is not well-defined as written.","fun_headline_variants_meta":{"raw":{"variants":["T-Coop-UCB learns hidden thresholds, near-Oracle results","Decentralized bandits crack unknown coalition sizes","Multi-agent bandits: infer thresholds, dodge decoys","Cooperative agents beat baseline told true thresholds","Unknown cutoff? Decentralized bandits still near-Oracle"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000891,"raw_usage":{"total_tokens":3819,"prompt_tokens":899,"completion_tokens":2920,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":515,"completion_tokens_details":{"reasoning_tokens":2839}},"tokens_in":515,"tokens_out":2920,"duration_ms":20399,"temperature":1.0,"reasoning_tokens":2839,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:30:35.521834+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run an arm whose true threshold is 1 and whose success probability is small, say $p=0.05$, with $m$ set to any finite value. With one agent pulling, runs of $m$ failures occur with probability at least $(0.95)^m$, so the update rule 'if failure after $m$ attempts at coalition size, increase $\\hat{h}_i(t)$' will push the threshold estimate above the true value even though the coalition size already satisfies the threshold; observing this in simulation would show that the threshold estimator cannot distinguish stochastic failure from insufficient coordination.","supporting_citations":[{"cited_title":"Finite-time analysis of the multiarmed bandit problem","cited_arxiv_id":null,"evidence_quote":"Supplies the UCB1 finite-time analysis and exploration bonus that T-Coop-UCB builds its reward estimates on."},{"cited_title":"Threshold bandits, with and without cen- sored feedback","cited_arxiv_id":null,"evidence_quote":"Defines the closest prior threshold-bandit setting, with a known threshold, which the paper contrasts against its unknown multi-agent thresholds."},{"cited_title":"Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications","cited_arxiv_id":"2204.13502","evidence_quote":"Models arms with finite shareable resources and per-load rewards, the capacity-based setting the paper contrasts with all-or-nothing threshold activation."},{"cited_title":"Distributed learning in multi-armed bandit with multiple players","cited_arxiv_id":null,"evidence_quote":"Establishes the collision-avoidance line of multi-agent bandits, where overlap is a failure mode rather than a required coordination mechanism."},{"cited_title":"On distributed cooperative decision-making in multiarmed bandits","cited_arxiv_id":null,"evidence_quote":"Provides the O(log T) regret benchmark for cooperative multi-agent bandits with known structure that the paper uses as a reference curve."},{"cited_title":"Multi-player bandits–a musical chairs approach","cited_arxiv_id":null,"evidence_quote":"Introduces a decentralized algorithm designed to avoid simultaneous pulls, representing the opposite coordination goal from the paper's coalition requirement."}],"review_version":1}