Paper deep dive
Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
Daphne Feng, Ricardo Parada, Lily Jiang, Sophia Yi, William Chang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 8/16/2026, 2:45:58 AM
Summary
This paper addresses the multi-agent multi-armed bandit (MMAB) problem under heavy-tailed reward distributions and information asymmetry, where agents cannot communicate online. The authors propose three robust decentralized algorithms tailored to specific information structures: mRUCB-A for common rewards with unobserved actions, mRUCB-Intervals for independent rewards with observed actions, and mHT-DSEE for independent rewards with unobserved actions. Theoretical regret bounds are derived for each setting, showing performance that nearly matches centralized heavy-tailed rates, validated by experiments on Pareto-distributed rewards.
Entities (10)
Relation Signals (6)
mRUCB-A → solves → Problem A
confidence 95% · For each we develop a robust decentralized algorithm—mRUCB-A... Problem A (action asymmetry). All players observe the same reward realization... but not each other’s actions.
mRUCB-Intervals → solves → Problem B
confidence 95% · mRUCB-Intervals... Problem B (reward asymmetry). Players observe the joint action... but each receives an independent sample
mHT-DSEE → solves → Problem C
confidence 95% · mHT-DSEE... Problem C (full asymmetry). Players observe neither others’ actions nor a common reward
Heavy-Tailed Rewards → requires → Robust Estimators
confidence 92% · The reward distributions are heavy-tailed, requiring robust estimators to control estimation error under weak moment assumptions.
mRUCB-A → achievesregretbound → O(log(T) * sum(delta_a^(-1/epsilon)))
confidence 90% · Theorem 1... expected regret satisfies R_T = O(log(T) sum_{a in A} delta_a^{-1/epsilon})
mHT-DSEE → achievesregretbound → O(K^M * log^2(T))
confidence 90% · With w(t) = ceil(log t) this gives R_T = O(K^M log^2 T)
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes.
Tags
Links
- Source: https://arxiv.org/abs/2608.10529v1
- Canonical: https://arxiv.org/abs/2608.10529v1
Trouble viewing inline? Open PDF directly →
Full Text
32,673 characters extracted from source content.
Expand or collapse full text
Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry Daphne Feng1, Ricardo Parada2, Lily Jiang1, Sophia Yi1, William Chang1 Abstract The multi-armed bandit problem is a central framework in sequential decision-making, extensively studied under sub-Gaussian reward assumptions. However, real-world applications often involve heavy-tailed reward distributions and decentralized, information-asymmetric interactions. We study multi-agent multi-armed bandits with heavy-tailed rewards under three information-asymmetry regimes: unobserved actions with common rewards, observed actions with independent rewards, and unobserved actions with independent rewards. We develop robust decentralized algorithms for each setting and derive regret guarantees that nearly match centralized heavy-tailed rates. Experiments on a Pareto-distributed reward environment validate our theoretical findings and illustrate the trade-offs between synchronization, coordination, and exploration across the three regimes. I Introduction The multi-armed bandit (MAB) problem is a core model for sequential decision-making under uncertainty, originating in work on adaptive experimentation and Bayesian selection [9, 13]. At each round a learner selects an action and observes a random payoff, balancing exploration of uncertain actions against exploitation of apparently good ones. Bandit models underpin data-driven decision systems—online experimentation, recommendation, resource allocation, spectrum access, multi-robot coordination—which are typically distributed in ways not captured by single-agent abstractions: several agents learn simultaneously while each observes only part of the system state. The multi-player MAB (MMAB) literature spans several information structures. In one line, players share information over communication graphs or gossip protocols [1, 12]. Another has players choose from a common arm set where collisions couple outcomes [7, 11]. More recently, cooperative MMAB has been studied under limited or no communication with structured observation asymmetries [4, 5]; see [2] for a survey. These works show that even without explicit messaging, agents can sometimes coordinate through shared structure or pre-agreed protocols. A largely orthogonal challenge is that many reward signals are heavy-tailed: rare extreme events dominate observations, producing weak concentration and rendering sub-Gaussian analyses inaccurate. Heavy tails arise naturally in financial returns, network traffic bursts, and outlier-prone performance metrics. Robust algorithms for heavy-tailed rewards include robust-UCB methods [3] and deterministic exploration–exploitation schedules [14], with extensions to pure exploration [17], linear bandits [10], and minimax-optimal procedures [8], while Catoni-style confidence sequences sharpen what is achievable under weak moment assumptions [15]. The intersection of cooperative multi-agent bandits, heavy-tailed rewards, and decentralized operation with no online communication remains underexplored. Existing multi-agent heavy-tailed work relies on explicit communication: [6] considers delayed message passing and [16] studies graph-based communication. We ask: what is achievable when agents coordinate implicitly via a pre-agreed protocol? Our contributions. We introduce three problem formulations capturing distinct information asymmetries in multi-agent heavy-tailed bandits: common rewards with unobserved actions (Problem A), independent rewards with observed actions (Problem B), and independent rewards with unobserved actions (Problem C). For each we develop a robust decentralized algorithm—mRUCB-A, mRUCB-Intervals, and mHT-DSEE—and prove regret guarantees summarized in Table I. The robust mean estimator and the single-agent concentration arguments are adapted from [3, 14]; our contribution lies in the multi-agent formulation, in the use of intentional action deviations as an implicit signaling channel, and in a unified comparison of what each information structure costs. TABLE I: Summary of information structures and regret bounds. Prob. A Prob. B Prob. C Actions observed? No Yes No Rewards shared? Yes No (i.i.d.) No (i.i.d.) Algorithm mRUCB-A mRUCB-Int. mHT-DSEE Regret O(logTΔ1/ε)O\! (\! T ^1/ \! ) O(logTΔ1/ε)O\! (\! T ^1/ \! ) O(log2T)O( ^2T) I Preliminaries I-A Heavy-tailed bandits Consider a stochastic MAB with K arms. Each arm ∈:=1,…,K a :=\1,…,K\ has an unknown reward distribution ν _ a with mean μ _ a. At round t, the agent selects arm t a_t and observes a reward drawn from νt _ a_t. The expected regret at horizon T is RT=Tμ⋆−∑t=1T[μt]=∑∈Δ[n(T)],R_T=Tμ - _t=1^TE[ _ a_t]= _ a _ a\,E[n_ a(T)], (1) where μ⋆=maxμ = _ a _ a, Δ=μ⋆−μ _ a=μ - _ a is the suboptimality gap, and n(T)n_ a(T) is the number of pulls. We assume heavy-tailed rewards: there exist ε∈(0,1] ∈(0,1] and v>0v>0 such that for all ∈ a , [|X−μ|1+ε]≤v.E[|X_ a- _ a|^1+ ]≤ v. (2) This allows distributions with infinite variance (when ε<1 <1), capturing Pareto, Student-t, and other heavy-tailed families; smaller ε corresponds to heavier tails. I-B Multi-agent extension We extend the setting to M players, where player i has an individual action set iA_i of size KiK_i. The joint action space is =1×⋯×MA=A_1×·s×A_M, containing KM:=∏i=1MKiK^M:= _i=1^MK_i joint arms. At each round t, each player simultaneously selects an arm, forming joint arm (t)=(a1(t),…,aM(t)) a(t)=(a_1(t),…,a_M(t)), and then observes a reward sampled from ν(t) _ a(t). The cumulative regret is RT=Tμ⋆−∑t=1T[X(t)]R_T=Tμ - _t=1^TE[X_ a(t)], where μ⋆=max∈μ = _ a _ a. Players may agree on a strategy beforehand and know each other’s action spaces, but cannot communicate during learning. We consider three information structures, each matching a distinct class of deployment. Problem A (action asymmetry). All players observe the same reward realization X(t)X_ a(t) but not each other’s actions. This is the situation of a team optimizing a single aggregate metric: transmitters in a shared spectrum band that observe total network throughput, or advertising channels evaluated against one conversion count, where the aggregate is instrumented but attribution to individual actions is not. Problem B (reward asymmetry). Players observe the joint action (t) a(t) but each receives an independent sample X(t)i∼ν(t)X_ a(t)^i _ a(t). This matches federated or multi-site experimentation: a configuration is chosen jointly and logged centrally, so every site knows what was deployed, while each site measures only its own privately held outcomes. Problem C (full asymmetry). Players observe neither others’ actions nor a common reward; each receives an i.i.d. sample. This models fully decentralized deployments such as sensor or robot teams operating with no backhaul, where each unit sees only its own measurements. I-C Robust upper confidence bounds Throughout, μ^(t) μ_ a(t) is the truncated mean of [3]: writing X,1,…,X,n(t)X_ a,1,…,X_ a,n_ a(t) for the rewards observed from arm a, μ^(t)=1n(t)∑s=1n(t)X,s 1|X,s|≤(vslog(Tγ))11+ε. μ_ a(t)= 1n_ a(t) _s=1^n_ a(t)X_ a,s\,1\! \|X_ a,s|≤ ( vs (T^γ) ) 11+ \. (3) The robust upper confidence bound (RUCB) for joint arm a is RUCB(t)=∞if n(t)=0,μ^(t)+α(t)otherwise,RUCB_ a(t)= cases∞&if n_ a(t)=0,\\ μ_ a(t)+ _ a(t)&otherwise, cases (4) where the first case marks an arm from which nothing has yet been observed, so that μ^(t) μ_ a(t) is undefined; setting the index to ∞ forces every joint arm to be played at least once before any comparison is made. The confidence radius is α(t)=v11+ε(clog(Tγ)n(t))ε1+ε, _ a(t)=v 11+ \! ( c (T^γ)n_ a(t) )^\! 1+ , (5) with c,γ>0c,γ>0, and [3, Prop. 1] gives Pr(|μ^(t)−μ|>α(t))≤t−γ (| μ_ a(t)- _ a|> _ a(t))≤ t^-γ. Only this concentration property is used below, so any estimator obeying a bound of the form (5)—median-of-means, or the Catoni-style confidence sequences of [15]—may be substituted. Such a substitution changes the constant c and the way v enters, and hence the constants in all three theorems, but not the rates; Catoni-style estimators give the sharpest constants as ε→1 → 1, at the cost of solving an implicit equation at each round. I Problem A: Common Rewards, Unobserved Actions In Problem A, all players observe the same reward but cannot see others’ actions. Two technical challenges arise. First, since actions are hidden, miscoordination may occur if the players’ internal estimates diverge, and the observed reward is then attributed to the wrong joint action. Second, the reward distributions are heavy-tailed, requiring robust estimators to control estimation error under weak moment assumptions. However, because rewards are shared, all players’ estimates remain identical under the same deterministic update rule—the key simplifying feature. We impose a lexicographic ordering on A for consistent tie-breaking: < a< b if there exists n such that ai=bia_i=b_i for all i<ni<n and an<bna_n<b_n. Each player then computes RUCB(t)RUCB_ a(t) for every joint arm and selects the highest, breaking ties lexicographically, yielding mRUCB-A (Algorithm 1). Algorithm 1 mRUCB-A 1: Players agree on a lexicographic ordering of A. 2: Init. n(0)←0n_ a(0)← 0, μ^(0)←0 μ_ a(0)← 0 for all ∈ a . 3: for t=1,…,Tt=1,…,T do 4: Compute RUCB(t)RUCB_ a(t) for all ∈ a via (4). 5: Select (t)←argmaxRUCB(t) a(t)← _ aRUCB_ a(t) (ties: lexicographic). 6: Pull individual arm; observe common reward; update statistics. Theorem 1. Under condition (2), if all players follow mRUCB-A, the expected regret satisfies RT=O(log(T)∑∈Δ−1/ε)R_T=O\! ( (T) _ a _ a^-1/ ). Proof. Since all players observe the same reward and use the same deterministic update rule with consistent tie-breaking, every player selects the same joint arm at every round. The problem thus reduces to a single-agent heavy-tailed bandit over KMK^M arms, and the analysis follows [3]. For each suboptimal arm a with gap Δ>0 _ a>0, define the good event at round t: t:|μ^(t)−μ|≤α(t)G_t:| μ_ a(t)- _ a|≤ _ a(t) for all a. By the concentration bound of Section I-C, Pr(tc)≤KMt−γ (G_t^c)≤ K^Mt^-γ. Under tG_t, selection of a requires μ^(t)+α(t)≥μ^⋆(t)+α⋆(t) μ_ a(t)+ _ a(t)≥ μ_ a (t)+ _ a (t), which implies 2α(t)≥Δ2 _ a(t)≥ _ a. This fails after τ=cγlog(T)(2v1/(1+ε)/Δ)(1+ε)/ε _ a=cγ (T)(2v^1/(1+ )/ _ a)^(1+ )/ pulls. Hence [n(T)]≤τ+∑t=1TPr(tc)E[n_ a(T)]≤ _ a+ _t=1^T (G_t^c), where the tail sum converges for γ>1γ>1. Summing Δ⋅[n(T)] _ a·E[n_ a(T)] over all suboptimal arms gives the result. ∎ This matches the optimal single-agent heavy-tailed rate over KMK^M arms. Since the KMK^M dependence is unavoidable even for a centralized learner, the decentralized agents incur no additional cost from action asymmetry. IV Problem B: Independent Rewards, Observed Actions In Problem B, players observe the joint action but receive independent reward samples X(t)1,…,X(t)M∼i.i.d.ν(t)X_ a(t)^1,…,X_ a(t)^M .i.d. _ a(t). This reverses Problem A’s structure: players see all actions but their estimates diverge because each empirical mean uses different samples, so one player may conclude that an arm is suboptimal while another player’s interval still overlaps. An index rule applied independently by each player would therefore cause persistent miscoordination. mRUCB-Intervals avoids this by replacing index maximization with round-robin elimination: players cycle through a common active set S, and an arm leaves S only through a signal that every player observes. For each joint arm a and player i the algorithm maintains Ii(t)=[μ^i(t)−α(t),μ^i(t)+α(t)],I_ a^i(t)= [ μ_ a^i(t)- _ a(t),\; μ_ a^i(t)+ _ a(t) ], (6) where α(t) _ a(t) is common to all players because it depends only on the shared pull count n(t)n_ a(t). Elimination proceeds in three stages. Detection: if player i finds that Ii(t)I_ a^i(t) lies strictly below and disjoint from the interval of another active arm, then a is dominated from player i’s perspective. Signaling: player i then deviates from the prescribed action by pulling a different individual arm, the only form of implicit communication available. Propagation: since actions are observable, all players detect the mismatch between the scheduled joint arm (t) a(t) and the realized one ′(t) a (t), and mark (t) a(t) for removal regardless of whether their own intervals support it. Two conventions keep the players’ statistics aligned: the reward of a signaling round is discarded, and removals take effect at the end of the current cycle. Algorithm 2 gives the procedure. Algorithm 2 mRUCB-Intervals 1: Players agree on an ordering of A; set S←S , P←∅P← . 2: while t≤Tt≤ T do 3: for each ∈S a∈ S in order do 4: if some player i finds Ii(t)I_ a^i(t) strictly below the interval of another arm of S then 5: That player pulls a different individual arm; all players observe ′(t)≠ a (t)≠ a and set P←P∪P← P∪\ a\; the reward of this round is discarded. 6: else 7: All players pull the components of a; player i observes XiX_ a^i and updates IiI_ a^i via (6); n←n+1n_ a← n_ a+1. 8: S←S∖PS← S P; P←∅P← . Lemma 1. Under mRUCB-Intervals, at every round all players hold the same active set S(t)S(t) and the same pull counts n(t)n_ a(t). Moreover, if a is the arm scheduled at round t, then n(t)≥n(t)n_ b(t)≥ n_ a(t) for every ∈S(t) b∈ S(t). Proof. Both claims follow by induction on t. Initially S=S=A and all counts are zero. The scheduled arm is a deterministic function of S and the position in the cycle, which are common by hypothesis. Since actions are observed, every player sees the realized joint arm and applies the same count update, and removals are triggered only by observed deviations, so S remains common. Within a cycle each active arm is scheduled exactly once and signaling rounds increment no counts, so all active arms have equal counts at cycle boundaries and, at any point inside a cycle, the arms not yet scheduled—including the scheduled arm itself—have the smallest counts. ∎ Theorem 2. If all players follow mRUCB-Intervals under (2), then RT≤cγ 41+εv1εlog(T)∑≠⋆Δ−1/ε+∑≠⋆Δ+(KM−1)Δmax+O(1), splitR_T≤\;&cγ\,4 1+ v 1 (T) _ a≠ a _ a^-1/ \\ &+ _ a≠ a _ a+(K^M-1) _ +O(1), split (7) where the O(1)O(1) term collects the contribution of the failure event and is independent of T for γ>1γ>1. Proof. Let tG_t be the event that |μ^i(t)−μ|≤α(t)| μ_ a^i(t)- _ a|≤ _ a(t) for all i and all a; by Section I-C and a union bound over the MKMMK^M player-arm pairs, Pr(tc)≤MKMt−γ (G_t^c)≤ MK^Mt^-γ. Step 1: ⋆ a is never eliminated. Under tG_t, for every player i and every active b, the lower end of I⋆iI^i_ a satisfies μ^⋆i+α⋆≥μ⋆≥μ≥μ^i−α μ^i_ a + _ a ≥μ ≥ _ b≥ μ^i_ b- _ b, so I⋆iI^i_ a never lies strictly below the interval of another active arm. No player signals on ⋆ a , and by Lemma 1 no player removes it. Step 2: Elimination time. Let ≠⋆ a≠ a be scheduled at round t. By Lemma 1, n⋆(t)≥n(t)n_ a (t)≥ n_ a(t) and hence α⋆(t)≤α(t) _ a (t)≤ _ a(t). Under tG_t the upper end of IiI^i_ a is at most μ+2α(t) _ a+2 _ a(t) and the lower end of I⋆iI^i_ a is at least μ⋆−2α(t)μ -2 _ a(t), so every player detects domination as soon as 4α(t)<Δ4 _ a(t)< _ a. By (5) this holds once n(t)n_ a(t) exceeds τ=cγlog(T)(4v1/(1+ε)Δ)(1+ε)/ε, _ a=cγ (T) ( 4v^1/(1+ ) _ a )^(1+ )/ , (8) so that n(T)≤τ+1n_ a(T)≤ _ a+1: the arm is signaled the next time it is scheduled and is removed at the end of that cycle. Note that the detection threshold is 4α4 _ a, rather than the 2α2 _ a of an index comparison, because separating two intervals requires both radii to be small. Step 3: Signaling cost. Each arm is removed exactly once, and by Lemma 1 its removal consumes exactly one round in which the realized joint action is unintended, contributing regret at most Δmax _ . Simultaneous deviations by several players still consume a single round, so the total signaling cost is at most (KM−1)Δmax(K^M-1) _ , independent of both T and M. Step 4: Summing. By Step 2, ∑≠⋆Δ(τ+1) _ a≠ a _ a( _ a+1) gives the first two terms of (7). Adding the failure contribution ∑t≤TPr(tc)Δmax≤MKMΔmax∑t≥1t−γ=O(1) _t≤ T (G_t^c) _ ≤ MK^M _ _t≥ 1t^-γ=O(1) for γ>1γ>1, together with Step 3, yields the bound. ∎ The leading term matches Problem A up to the constant 4(1+ε)/ε4^(1+ )/ in place of 2(1+ε)/ε2^(1+ )/ , and the remaining terms are independent of the horizon. The mechanism thus uses action deviations as a 1-bit implicit communication channel; this suffices because α(t) _ a(t) is common across players, so a single detection is enough to eliminate an arm for everyone. V Problem C: Independent Rewards, Unobserved Actions Problem C combines both asymmetries, eliminating the coordination mechanisms of Problems A (shared rewards) and B (observable actions). A player cannot tell whether the realized reward corresponds to the intended joint arm or to a different one caused by another player’s deviation, and independent samples simultaneously prevent synchronized estimates. Adaptive, index-driven coordination is therefore unavailable, and exploration must be scheduled deterministically from the round index alone, which every player can reproduce. mHT-DSEE (Algorithm 3) follows the DSEE framework [14]. Fix an increasing w(t)→∞w(t)→∞ and let D(t)=⌈w(t)logt⌉D(t)= w(t) t be the target number of samples of each joint arm by round t. If fewer than KMD(t)K^MD(t) exploration rounds have been used, round t is an exploration round and the next joint arm in a fixed cyclic order is played; otherwise every player commits to the maximizer of its own RUCB, computed from exploration samples only. Because the test N(t)<KMD(t)N(t)<K^MD(t) depends only on t, players stay synchronized without communication. Two features matter for the analysis: the schedule is anytime, requiring neither T nor the gaps, and the confidence radius uses logt t rather than logT T. Algorithm 3 mHT-DSEE 1: Players agree on an ordering of A and on w(t)↑∞w(t) ∞; N←0N← 0. 2: for t=1,…,Tt=1,…,T do 3: if N<KM⌈w(t)logt⌉N<K^M w(t) t then 4: Play the next joint arm in the cyclic order; N←N+1N← N+1; each player stores its own reward. 5: else 6: Player i plays its own component of argmaxRUCBi(t) _ aRUCB^i_ a(t), computed from exploration samples. Theorem 3. Under (2), if all players follow mHT-DSEE with γ>1γ>1, then RT≤ΔmaxKMD(T)+Δmaxt0+O(1),R_T≤ _ K^MD(T)+ _ t_0+O(1), (9) where t0=mint:w(t)>cγ(2v1/(1+ε)/Δmin)(1+ε)/εt_0= \t:w(t)>cγ(2v^1/(1+ )/ _ )^(1+ )/ \ depends on ε,v ,v and the gaps but not on T. With w(t)=⌈logt⌉w(t)= t this gives RT=O(KMlog2T)R_T=O(K^M ^2T). Proof. Step 1: Exploration. At most KMD(T)K^MD(T) rounds are exploration rounds, each contributing regret at most Δmax _ , which is the first term. Step 2: Good event. At an exploitation round t every arm has D(t)D(t) samples for each player. By Section I-C with confidence level t−γt^-γ and a union bound over the MKMMK^M player-arm pairs, the event tG_t that |μ^i−μ|≤α(D(t))| μ^i_ a- _ a|≤α(D(t)) for all i,i, a has Pr(tc)≤MKMt−γ (G_t^c)≤ MK^Mt^-γ, where α(n)=v1/(1+ε)(clog(tγ)/n)ε/(1+ε)α(n)=v^1/(1+ )(c (t^γ)/n) /(1+ ). Step 3: Coordination. On tG_t, RUCBi≤μ+2α(D(t))RUCB^i_ a≤ _ a+2α(D(t)) and RUCB⋆i≥μ⋆RUCB^i_ a ≥μ for every player i, so every player selects ⋆ a once 2α(D(t))<Δmin2α(D(t))< _ , i.e. once D(t)>cγlog(t)(2v1/(1+ε)Δmin)(1+ε)/ε=:κlogt.D(t)>cγ (t) ( 2v^1/(1+ ) _ )^(1+ )/ =:κ t. (10) The threshold does not depend on the player index, so the players agree; and since D(t)≥w(t)logtD(t)≥ w(t) t, condition (10) holds as soon as w(t)>κw(t)>κ, that is for every t≥t0t≥ t_0. This is the role of the anytime schedule: both sides of (10) scale with logt t, so the crossing time t0t_0 is determined by w and the gaps alone and does not grow with the horizon. Each player then plays its component of ⋆ a , and the realized joint arm is exactly ⋆ a . Step 4: Exploitation regret. Exploitation rounds with t<t0t<t_0 contribute at most Δmaxt0 _ t_0. For t≥t0t≥ t_0, regret is incurred only on tcG_t^c, contributing at most MKMΔmax∑t≥1t−γ=O(1)MK^M _ _t≥ 1t^-γ=O(1) for γ>1γ>1. Adding Step 1 gives (9). Taking w(t)=⌈logt⌉w(t)= t gives D(T)=O(log2T)D(T)=O( ^2T). ∎ Remark 1. The choice of w trades the two terms of (9) against each other: faster growth shortens t0t_0 but enlarges the exploration budget D(T)D(T). Any w↑∞w ∞ yields o(log1+ηT)o( ^1+ηT) regret for the corresponding η, and knowledge of Δmin _ would allow the constant schedule w≡κw≡κ and hence O(logT)O( T); the extra factor is the price of not knowing the gaps. VI Experiments VI-A Setup We take M=2M=2 players, K=2K=2 individual arms (KM=4K^M=4 joint arms), and horizon T=106T=10^6, averaging over 1010 independent runs on the fixed instance =(0.44,0.57,0.91,0.25) μ=(0.44,0.57,0.91,0.25), so that the gaps are (0.46,0.34,−,0.65)(0.46,0.34,-,0.65). Pulling joint arm a yields a Pareto reward with shape a0=2a_0=2 and scale xm=μa(a0−1)/a0x_m= _a(a_0-1)/a_0, so that [Xa]=μaE[X_a]= _a. This distribution has finite mean and infinite variance: its centered moments of order 1+ε1+ are finite exactly for ε<1 <1. We therefore set ε=0.5 =0.5, for which |Xa−μa|1.5≤0.75<1=vE|X_a- _a|^1.5≤ 0.75<1=v for every μa∈[0,1] _a∈[0,1], so (2) holds; taking ε=1 =1 would instead require a finite second moment and is not admissible for this reward family. All three algorithms use the truncated-mean estimator (3) with (c,γ)=(1,2)(c,γ)=(1,2), i.e. exactly the estimator the analysis assumes, and mHT-DSEE uses w(t)=⌈logt⌉w(t)= t . VI-B Results Figure 1: Mean cumulative regret over 1010 runs under Pareto rewards with infinite variance (M=2M=2, K=2K=2, T=106T=10^6), log–log axes. Figure 1 shows mean cumulative regret. All three curves are clearly sublinear, confirming that each algorithm identifies ⋆ a under infinite-variance rewards and with the robust estimator in place. mRUCB-A ends at 214±24214± 24 and mHT-DSEE at 292±21292± 21, both still growing slowly, while mRUCB-Intervals ends at 4115±2854115± 285 but is exactly flat beyond ≈7×104≈7× 10^4 rounds. The ordering at this horizon is governed by constants rather than by rates, and is instructive. Elimination in Problem B requires two intervals to separate, i.e. 4α<Δ4 _ a< _ a, whereas the index comparisons of Problems A and C need only 2α<Δ2 _ a< _ a; by (5) this is 2(1+ε)/ε=82^(1+ )/ =8 times more samples of each arm when ε=0.5 =0.5, which is what the early growth of the orange curve buys. The payoff is that once the active set collapses, mRUCB-Intervals incurs no further regret at all, whereas the other two keep exploring; the curves would therefore cross at larger horizons. Similarly, mHT-DSEE is inexpensive here because its exploration budget KM⌈log2t⌉K^M ^2t is only ≈760≈760 rounds at T=106T=10^6, even though its rate is the worst of the three. The experiments thus support the theory while showing that the hierarchy of Table I is asymptotic: at moderate horizons the constants attached to each coordination mechanism dominate. A further practical caveat is that the joint action space grows as KMK^M, so larger instances lengthen the exploration phases of mHT-DSEE and slow the elimination cascade of mRUCB-Intervals. VII Conclusion We studied multi-agent bandits with heavy-tailed rewards under three information asymmetries. Our algorithms show that effective decentralized learning is achievable even under significant asymmetry and non-sub-Gaussian noise: shared rewards (Problem A) enable costless synchronization; observed actions (Problem B) provide an implicit signaling channel whose cost is independent of the horizon and of the number of players; and the fully asymmetric setting (Problem C) requires a pre-committed anytime schedule at a logT T factor of additional cost. That observable actions compensate for the loss of shared rewards at leading order is a notable positive result, while the barrier between Problems B and C shows the value of even minimal observability. Two limitations point to future work. First, our guarantees, like those of [3, 14], assume that (ε,v)( ,v) are known: a conservative choice (smaller ε or larger v) keeps every bound valid but inflates the confidence radius and hence the regret, so adapting to unknown tail heaviness—plausibly through self-normalized constructions such as [15]—remains open. Second, tighter lower bounds for Problem C would clarify whether the extra logT T factor is necessary without shared information. Extensions to adversarial or non-stationary rewards, and structured reward models such as linear or factored bandits that would mitigate the exponential KMK^M dependence, are also natural directions. References [1] B. Awerbuch and R. Kleinberg (2008) Competitive collaborative learning. Journal of Computer and System Sciences 74 (8), p. 1271–1288. Note: Learning Theory 2005 External Links: ISSN 0022-0000, Document, Link Cited by: §I. [2] E. Boursier and V. Perchet (2024) A survey on multi-player bandits. External Links: 2211.16275, Link Cited by: §I. [3] S. Bubeck, N. Cesa-Bianchi, and G. Lugosi (2012) Bandits with heavy tail. External Links: 1209.1727, Link Cited by: §I, §I, §I-C, §I-C, §I, §VII. [4] W. Chang, M. Jafarnia-Jahromi, and R. Jain (2021) Online learning for cooperative multi-player multi-armed bandits. CoRR abs/2109.03818. External Links: Link, 2109.03818 Cited by: §I. [5] W. Chang and Y. Lu (2023) Optimal cooperative multiplayer learning bandits with noisy rewards and no communication. arXiv preprint arXiv:2311.06210. Cited by: §I. [6] A. Dubey et al. (2020) Cooperative multi-agent bandits with heavy tails. In International conference on machine learning, p. 2730–2739. Cited by: §I. [7] D. Kalathil, N. Nayyar, and R. Jain (2014) Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory 60 (4), p. 2331–2345. External Links: Document Cited by: §I. [8] K. Lee and S. Lim (2024) Minimax optimal bandits for heavy tail rewards. IEEE Transactions on Neural Networks and Learning Systems 35 (4), p. 5280–5294. External Links: Document Cited by: §I. [9] H. E. Robbins (1952) Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society 58, p. 527–535. External Links: Link Cited by: §I. [10] H. Shao, X. Yu, I. King, and M. R. Lyu (2018) Almost optimal algorithms for linear stochastic bandits with heavy-tailed payoffs. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31, p. . External Links: Link Cited by: §I. [11] C. Shi and C. Shen (2021) Multi-player multi-armed bandits with collision-dependent reward distributions. IEEE Transactions on Signal Processing 69, p. 4385–4402. External Links: ISSN 1941-0476, Link, Document Cited by: §I. [12] B. Szorenyi, R. Busa-Fekete, I. Hegedus, R. Ormandi, M. Jelasity, and B. Kegl (2013-17–19 Jun) Gossip-based distributed stochastic bandit algorithms. In Proceedings of the 30th International Conference on Machine Learning, S. Dasgupta and D. McAllester (Eds.), Proceedings of Machine Learning Research, Vol. 28, Atlanta, Georgia, USA, p. 19–27. External Links: Link Cited by: §I. [13] W. R. Thompson (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika 25 (3/4), p. 285–294. External Links: ISSN 00063444, Link Cited by: §I. [14] S. Vakili, K. Liu, and Q. Zhao (2013) Deterministic sequencing of exploration and exploitation for multi-armed bandit problems. External Links: 1106.6104, Link Cited by: §I, §I, §V, §VII. [15] H. Wang and A. Ramdas (2023-09) Catoni-style confidence sequences for heavy-tailed mean estimation. Stochastic Processes and their Applications 163, p. 168–202. External Links: ISSN 0304-4149, Link, Document Cited by: §I, §I-C, §VII. [16] X. Wang and M. Xu (2025) Multi-agent multi-armed bandit with fully heavy-tailed dynamics. External Links: 2501.19239, Link Cited by: §I. [17] X. Yu, H. Shao, M. R. Lyu, and I. King (2018) Pure exploration of multi-armed bandits with heavy-tailed payoffs.. In UAI, p. 937–946. Cited by: §I.