{"id":"645adf02-d910-41c3-9e41-285c7fa279ac","arxiv_id":"2608.10529","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Three decentralized multi-agent bandit algorithms achieve near-centralized regret under heavy-tailed rewards across different information asymmetry regimes.","lead":"The paper designs three decentralized algorithms for teams of learning agents that face heavy-tailed rewards and limited information about each other's actions or outcomes. It proves regret bounds for each setup and shows that observing teammates' actions is enough to nearly recover the performance of a centralized learner.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Problem C's anytime proof is inconsistent with the paper's confidence radius: Eq. (5) uses log(T^γ), while Theorem 3's Step 2 uses log(t^γ); with Eq. (5) the coordination time t0 depends on T and the O(log^2 T) regret bound does not follow.","rationale":"The paper's main results are credible: Problems A and B reduce to standard single-agent or interval-elimination arguments, and the heavy-tailed concentration framework is standard. The reader's stated concern about the per-sample truncation threshold in Eq. (3) is probably not load-bearing, since [10] uses exactly that per-sample-index threshold to obtain anytime concentration. However, the manuscript has a genuine internal inconsistency that affects the central Problem C claim: the preliminary definitions in Eqs. (3) and (5) use log(T^γ), while Theorem 3's proof switches to log(t^γ). Because mHT-DSEE is designed to be anytime and to avoid knowing T, the proof must use a confidence radius based on log t; otherwise the coordination time t0 grows with T and the claimed O(K^M log^2 T) bound fails. This is fixable by explicitly specifying the log-t variant for Problem C, so the appropriate verdict remains CONDITIONAL rather than ACCEPT or REJECT. The reader's verdict is unchanged, but the reason for the condition should be updated to this T/t mismatch.","tokens_in":7994,"tokens_out":29749,"duration_ms":284125,"concrete_test":"Re-derive Theorem 3 with the radius actually defined in Eq. (5). Set w(t)=⌈log t⌉ and compute t0 = min{ t : w(t) log t > cγ log(T^γ) (2v^{1/(1+ε)}/Δ_min)^{(1+ε)/ε} }. If t0 is T-dependent and the Δ_max t0 term is not O(1), the proof fails for the algorithm as written. Separately, check [10, Prop. 1] to confirm that its truncation threshold uses the per-sample index s, i.e. (v s / log(1/δ))^{1/(1+ε)}; if so, remove the s-index objection and require instead that the authors explicitly state that mHT-DSEE uses log(t^γ) in equations (3) and (5).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim for Problem C rests on a T/t mismatch in the confidence radius. Section II-C defines α_a(t) in Eq. (5) using log(T^γ), and the estimator in Eq. (3) also truncates using log(T^γ). But Theorem 3's Step 2 defines α(n) = v^{1/(1+ε)}(c log(t^γ)/n)^{ε/(1+ε)}, and the crossing condition (10) cancels log t so that t0 is independent of T. This cancellation is the only reason R_T = O(K^M log^2 T) holds. If mHT-DSEE actually uses the RUCB defined in Section II-C — Algorithm 3 says 'arg max_a RUCB_i^a(t)' without modification — then the correct condition is D(t) > cγ log(T^γ) (2v^{1/(1+ε)}/Δ_min)^{(1+ε)/ε}. With w(t)=⌈log t⌉ this requires log t ≥ γ sqrt(cK log T), so the miscoordination interval t0 is exp(O(sqrt(log T))) = T^{o(1)}, and the Δ_max t0 term dominates O(log^2 T). The proof is consistent only with a log-t version of (3)/(5) that is never formally stated in the algorithm. The per-sample index s in Eq. (3) is standard in [10] and is not the weak point; the T/t inconsistency is the concrete gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies multi-agent stochastic bandits with heavy-tailed rewards satisfying a (1+ε)-moment condition, under three information-asymmetry regimes: common rewards with unobserved actions (Problem A), independent rewards with observed actions (Problem B), and independent rewards with unobserved actions (Problem C). For each regime it proposes a decentralized algorithm (mRUCB-A, mRUCB-Intervals, mHT-DSEE) and proves regret bounds: O(log T Σ_a Δ_a^{-1/ε}) for Problems A and B and O(K^M log^2 T) for Problem C, based on the truncated-mean robust UCB estimator of [10] and a deterministic exploration schedule in the style of [11]. The paper also reports experiments on an infinite-variance Pareto reward instance with M=2 players and K=2 arms per player.","tokens_in":8237,"tokens_out":20850,"duration_ms":192094,"significance":"If the bounds are established, the paper gives a useful separation among information structures for heavy-tailed multi-agent bandits: shared rewards give costless synchronization, observed actions provide an implicit signaling channel whose cost is independent of the horizon, and full asymmetry costs an extra log factor. The strengths include a clean exact reduction in Problem A, a natural deviation-based elimination protocol in Problem B, explicit constants in the regret bounds, and experiments run with the same estimator as the analysis on a genuinely infinite-variance reward family. The principal weakness is that the Problem C analysis as written relies on a confidence radius that uses log t, while the preliminaries and Algorithm 3 define the radius with log T; this inconsistency is load-bearing for the O(log^2 T) claim. With that issue resolved and the concentration statements restated in terms of pull counts, the paper would be a solid contribution.","major_comments":[{"comment":"The central O(K^M log^2 T) bound for Problem C is not supported by the algorithm as written. Section II-C defines the robust estimator (3) and the confidence radius (5) with log(T^γ) in the truncation threshold and in α_a(t), and Algorithm 3 (line 6) computes RUCB_i^a(t) without any modification. The proof of Theorem 3, however, uses α(n) = v^{1/(1+ε)}(c log(t^γ)/n)^{ε/(1+ε)} and derives the crossing condition (10) with log t on both sides, so that t0 is independent of T. With the log T radius of (5), the crossing condition is D(t) > cγ log T (2v^{1/(1+ε)}/Δ_min)^{(1+ε)/ε}; since D(t) = ⌈w(t) log t⌉ and w(t)=⌈log t⌉, this requires log t = Ω(sqrt(log T)), giving t0 = exp(Ω(sqrt(log T))). The term Δ_max t0 in (9) then dominates O(log^2 T). The paper must either specify that mHT-DSEE uses a separately defined anytime version of (3)/(5) with log t and prove or cite the corresponding concentration bound, or revise the claimed Problem C rate.","section":"Section V, Theorem 3, Eq. (10), Algorithm 3"},{"comment":"The stated concentration inequality Pr(|bµ_a(t) − μ_a| > α_a(t)) ≤ t^{-γ} uses the global round index t, while α_a(t) in Eq. (5) depends on the pull count n_a(t). If t is the global round, the assertion is false when n_a(t) is small: for n_a(t)=1 the available moment inequality cannot give a t^{-γ}-type tail for large t. The bound from [10, Prop. 1] is in terms of the number of samples s. Consequently the lines 'Pr(G_t^c) ≤ K^M t^{-γ}' and 'the tail sum converges for γ>1' appearing in the proofs of Theorems 1, 2, and 3 should be restated with sums over pull counts s of s^{-γ} (or D(t)^{-γ} in Theorem 3). The final rates are unchanged under this standard correction, but the proofs as written rely on an invalid probability bound.","section":"Section II-C, Eq. (5); proofs of Theorems 1–3"}],"minor_comments":[{"comment":"The signaling step 'That player pulls a different individual arm' is undefined if the detecting player has an action set of size 1; the paper should either assume K_i ≥ 2 for all players or describe how a singleton player can participate in the signaling protocol.","section":"Algorithm 2, Problem B"},{"comment":"The sentence 'the confidence radius uses log t rather than log T' contradicts the formal definitions in Eqs. (3) and (5) and Algorithm 3; this ambiguity is part of Major Comment 1 and should be resolved by giving a single consistent definition.","section":"Section V, first paragraph"},{"comment":"The text refers to Figure 1, but no figure appears in the manuscript; please verify that the figure is included in the submitted version.","section":"Section VI-A"},{"comment":"The remark that any estimator obeying a bound of the form (5) may be substituted is helpful, but the constants in the regret bounds should be made explicitly dependent on the substituted estimator's concentration constants rather than left implicit through c.","section":"Section II-C"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth a look. It gives the first systematic treatment of three information-asymmetry regimes for heavy-tailed multi-agent bandits, and the comparison between them is genuinely useful. Problems A and B are clean: shared rewards make coordination free, and observable actions support the signaling-by-deviation mechanism in mRUCB-Intervals. The proofs there are standard union-bound arguments, and they check out. The authors also credit the single-agent machinery in [10] and [11] properly, and no fitted parameters or circular reasoning appear. That part earns its place.\n\nThe soft spot is Problem C. The stress-test concern lands. The confidence radius in Section II-C, Eq. (5), uses log(T^γ), and the estimator in Eq. (3) truncates with log(T^γ). But Theorem 3's Step 2 uses α(n) with log(t^γ), and the crossing condition in Eq. (10) cancels log t to make t0 independent of T. Algorithm 3 points back to the RUCB defined in Section II-C, which uses log T. So the paper is running two different confidence radii. With the stated log T version, t0 becomes exp(O(sqrt(log T))) at best, and the claimed O(log^2 T) bound does not follow. This is a load-bearing flaw for the central claim of Problem C, not a cosmetic typo.\n\nThat said, it looks fixable. The anytime concentration result from [10] holds with log t, so the authors can restate the estimator and RUCB for Algorithm 3 with log(t^γ), or define the general α(t) with log t and treat log T as a special case for the fixed-horizon algorithms. They should also double-check that the exact truncation threshold in Eq. (3) is covered by [10, Prop. 1] as written, since the per-sample s with log(T^γ) is a nonstandard variant. Those are minor-to-moderate gaps in presentation, but Problem C's theorem is the one that needs the fix.\n\nExperiments are illustrative only, no code shipped, so they add little beyond confirming sublinear behavior. The paper's value is the framework and the A/B results.\n\nFor the field: anyone working on multi-agent bandits with limited communication will find the problem formulations and the signaling mechanism useful. I would send this to peer review, but I would require the authors to fix the anytime inconsistency before publication. As it stands, the claims outrun the proof for the hardest regime.","headline":"Solid multi-agent heavy-tailed bandit paper with a real but fixable anytime-consistency gap in Problem C.","tokens_in":8785,"tokens_out":2605,"would_cite":false,"duration_ms":25855,"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":"Three decentralized multi-agent bandit algorithms match centralized heavy-tailed regret rates under information asymmetry.","keywords":["multi-armed bandits","heavy-tailed rewards","multi-agent learning","information asymmetry","decentralized algorithms","regret bounds","truncated-mean estimator","coordination without communication"],"falsifier":"Run the truncated-mean estimator (3) on a Pareto distribution with $\\varepsilon=0.5$, $v=1$, and the exact truncation threshold $(v s/\\log(T^\\gamma))^{1/(1+\\varepsilon)}$, and estimate $\\Pr(|\\hat\\mu_a(t)-\\mu_a|>\\alpha_a(t))$ over many independent runs; if the empirical tail probability exceeds $t^{-\\gamma}$ at any $t$ by a non-negligible margin, the concentration step used in Theorems 1–3 fails for this estimator and the bounds would need re-derivation.","tokens_in":7747,"feed_emoji":"🎰","tokens_out":9961,"duration_ms":81955,"temperature":0.7,"pith_summary":"The paper studies a multi-armed bandit problem in which several agents act simultaneously, agree on a strategy beforehand, and cannot communicate once learning begins, while reward distributions have heavy tails. Its central claim is that each of three information-asymmetry regimes admits a decentralized algorithm whose regret matches the best centralized heavy-tailed rate up to constants and, in one case, a single log factor. The three mechanisms are shared rewards with hidden actions, observable actions with independent rewards, and full asymmetry; the corresponding algorithms are named mRUCB-A, mRUCB-Intervals, and mHT-DSEE. Under the moment condition $E|X-\\mu|^{1+\\varepsilon}\\le v$, the regret bounds are $O(\\log T\\sum_{a\\neq a^*}\\Delta_a^{-1/\\varepsilon})$ for the first two regimes and $O(K^M\\log^2 T)$ for the third. The result matters because real deployments such as spectrum sharing, federated experiments, and sensor teams without backhaul often combine heavy-tailed observations with limited attribution and no online communication; the paper argues that this combination need not degrade the asymptotic learning rate.","feed_headline":"Decentralized bandits match centralized heavy-tailed regret rates","feed_subtitle":"With shared rewards, visible actions, or a preset schedule, agents keep single-agent regret rates despite heavy tails.","key_machinery":"The load-bearing object is the robust upper confidence bound built on the truncated-mean estimator $\\hat\\mu_a(t)$ with confidence radius $\\alpha_a(t)=v^{1/(1+\\varepsilon)}(c\\log(T^\\gamma)/n_a(t))^{\\varepsilon/(1+\\varepsilon)}$, for which the paper imports the concentration guarantee $\\Pr(|\\hat\\mu_a(t)-\\mu_a|>\\alpha_a(t))\\le t^{-\\gamma}$. Everything else is designed so that this radius is common knowledge among the players: in Problem A the shared reward synchronizes all estimates; in Problem B the shared pull count $n_a(t)$ makes $\\alpha_a(t)$ identical across players, so a single observed deviation can signal arm elimination through a 1-bit implicit channel (intervals that separate once $4\\alpha_a(t)<\\Delta_a$); in Problem C the deterministic anytime schedule $D(t)=\\lceil w(t)\\log t\\rceil$ lets every player reproduce the exploration sequence from the round index alone. The same concentration bound is the only probabilistic input to all three theorems, so any estimator satisfying it can replace the truncated mean.","core_discovery":"On its own terms, the paper establishes that decentralization and information asymmetry are asymptotically almost free in heavy-tailed multi-agent bandits. Under the moment condition $E|X-\\mu|^{1+\\varepsilon}\\le v$, the algorithm mRUCB-A (common reward, hidden actions) attains $R_T=O(\\log T\\sum_{a\\neq a^*}\\Delta_a^{-1/\\varepsilon})$, the same rate a single-agent heavy-tailed learner achieves over the joint action space; mRUCB-Intervals (visible actions, independent rewards) attains the same leading rate with a larger constant; and mHT-DSEE (full asymmetry) attains $O(K^M\\log^2 T)$. The only unavoidable cost is the $K^M$ dependence on the joint action space, which a centralized learner also pays, and the extra log factor in the fully asymmetric regime is the price of not knowing the gaps and having no shared observations. The paper argues that observable actions compensate for the loss of shared rewards at leading order, while the full-asymmetry regime shows the value of even minimal observability.","pith_inferences":["The paper does not pursue this, but the formal role played by the common confidence radius suggests a general design rule: any information structure that keeps active-set statistics common knowledge across agents should support elimination at centralized rates, while structures that privatize them will likely pay at least a log factor; testing this on other asymmetry patterns would be a natural ex","Beyond the paper, the anytime schedule in mHT-DSEE can be viewed as a tunable knob rather than a fixed choice: choosing $w(t)=t^{\\eta}$ trades exploration cost against the time until agents first agree on the optimal arm, yielding intermediate rates of $O(K^M\\log^{1+\\eta}T)$ for any $\\eta>0$; the paper's Remark 1 gestures at this but does not develop it.","A testable extension is to replace the truncated mean in Problem B with a Catoni-style estimator, since the protocol already supports one-bit communication; the paper predicts only constant improvements, but sharper constants would shrink Problem B's moderate-horizon disadvantage relative to the other two regimes."],"forward_implications":["When all agents observe the same reward, hiding their individual actions costs nothing in the regret rate: the team matches a centralized learner over the joint action space.","When actions are observable but rewards are independent, a deliberate deviation works as a one-bit implicit signal, and the total cost of all such signaling rounds is at most $(K^M-1)\\Delta_{\\max}$, independent of the horizon and of the number of players.","In the fully asymmetric regime a pre-committed anytime schedule with $w(t)=\\lceil\\log t\\rceil$ gives $O(K^M\\log^2 T)$ regret; knowing $\\Delta_{\\min}$ would allow a constant schedule and recover $O(K^M\\log T)$.","Because only the concentration bound is used, the algorithms can run with any robust estimator, such as median-of-means or Catoni-style confidence sequences, without changing the rates; only the constants change.","The rate hierarchy is asymptotic; at moderate horizons the constants dominate, and in the experiments Problem B's elimination threshold $4\\alpha_a<\\Delta_a$ costs $2^{(1+\\varepsilon)/\\varepsilon}$ more samples per arm than the index-based methods."],"supporting_citations":[{"why":"Supplies the truncated-mean estimator and the concentration bound $\\Pr(|\\hat\\mu_a(t)-\\mu_a|>\\alpha_a(t))\\le t^{-\\gamma}$ that all three theorems rely on.","marker":"[10]"},{"why":"Supplies the deterministic sequencing of exploration and exploitation (DSEE) schedule that mHT-DSEE adapts for the fully asymmetric regime.","marker":"[11]"},{"why":"Provides Catoni-style confidence sequences offered as a substitute estimator that preserves the rates with sharper constants.","marker":"[15]"},{"why":"Establishes the prior multi-agent heavy-tailed bandit setting with communication that this paper extends to no-communication regimes.","marker":"[16]"},{"why":"Treats multi-agent bandits with fully heavy-tailed dynamics, the closest prior problem for the fully asymmetric case.","marker":"[17]"},{"why":"Shows cooperative multiplayer bandit learning with noisy rewards and no communication, supplying the pre-agreed protocol idea.","marker":"[8]"}],"fun_headline_variants":["Decentralized heavy-tailed bandits nearly match centralized regret","Information asymmetry is almost free in heavy-tailed multi-agent bandits","Heavy-tailed rewards: decentralized agents keep single-agent regret rates","Three regimes show decentralization costs little in heavy-tailed bandits","Robust algorithms match centralized rates despite heavy tails and asymmetry"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All three regret bounds rest on the imported concentration inequality for the truncated-mean estimator: the estimate must stay within its confidence radius with probability at least $1-t^{-\\gamma}$ at every round, and the paper uses a truncation threshold for which that inequality is borrowed rather than proved.","fun_headline_variants_meta":{"raw":{"variants":["Decentralized heavy-tailed bandits nearly match centralized regret","Information asymmetry is almost free in heavy-tailed multi-agent bandits","Heavy-tailed rewards: decentralized agents keep single-agent regret rates","Three regimes show decentralization costs little in heavy-tailed bandits","Robust algorithms match centralized rates despite heavy tails and asymmetry"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000192,"raw_usage":{"total_tokens":1311,"prompt_tokens":877,"completion_tokens":434,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":493,"completion_tokens_details":{"reasoning_tokens":351}},"tokens_in":493,"tokens_out":434,"duration_ms":4069,"temperature":1.0,"reasoning_tokens":351,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T14:18:56.579871+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the truncated-mean estimator (3) on a Pareto distribution with $\\varepsilon=0.5$, $v=1$, and the exact truncation threshold $(v s/\\log(T^\\gamma))^{1/(1+\\varepsilon)}$, and estimate $\\Pr(|\\hat\\mu_a(t)-\\mu_a|>\\alpha_a(t))$ over many independent runs; if the empirical tail probability exceeds $t^{-\\gamma}$ at any $t$ by a non-negligible margin, the concentration step used in Theorems 1–3 fails for this estimator and the bounds would need re-derivation.","supporting_citations":[{"cited_title":"Bandits with heavy tail,","cited_arxiv_id":null,"evidence_quote":"Supplies the truncated-mean estimator and the concentration bound $\\Pr(|\\hat\\mu_a(t)-\\mu_a|>\\alpha_a(t))\\le t^{-\\gamma}$ that all three theorems rely on."},{"cited_title":"Deterministic sequencing of exploration and exploitation for multi-armed bandit problems,","cited_arxiv_id":null,"evidence_quote":"Supplies the deterministic sequencing of exploration and exploitation (DSEE) schedule that mHT-DSEE adapts for the fully asymmetric regime."},{"cited_title":"Catoni-style confidence sequences for heavy- tailed mean estimation,","cited_arxiv_id":null,"evidence_quote":"Provides Catoni-style confidence sequences offered as a substitute estimator that preserves the rates with sharper constants."},{"cited_title":"Cooperative multi-agent bandits with heavy tails,","cited_arxiv_id":null,"evidence_quote":"Establishes the prior multi-agent heavy-tailed bandit setting with communication that this paper extends to no-communication regimes."},{"cited_title":"Multi-agent multi-armed bandit with fully heavy- tailed dynamics,","cited_arxiv_id":null,"evidence_quote":"Treats multi-agent bandits with fully heavy-tailed dynamics, the closest prior problem for the fully asymmetric case."},{"cited_title":"Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication","cited_arxiv_id":"2311.06210","evidence_quote":"Shows cooperative multiplayer bandit learning with noisy rewards and no communication, supplying the pre-agreed protocol idea."}],"review_version":1}