Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

# Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry
Source: [https://arxiv.org/html/2608.10529](https://arxiv.org/html/2608.10529)
###### 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\.

## IIntroduction

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](https://arxiv.org/html/2608.10529#bib.bib25),[13](https://arxiv.org/html/2608.10529#bib.bib26)\]\. 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](https://arxiv.org/html/2608.10529#bib.bib24),[12](https://arxiv.org/html/2608.10529#bib.bib21)\]\. Another has players choose from a common arm set where collisions couple outcomes\[[7](https://arxiv.org/html/2608.10529#bib.bib20),[11](https://arxiv.org/html/2608.10529#bib.bib9)\]\. More recently, cooperative MMAB has been studied under limited or no communication with structured observation asymmetries\[[4](https://arxiv.org/html/2608.10529#bib.bib8),[5](https://arxiv.org/html/2608.10529#bib.bib3)\]; see\[[2](https://arxiv.org/html/2608.10529#bib.bib2)\]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](https://arxiv.org/html/2608.10529#bib.bib23)\]and deterministic exploration–exploitation schedules\[[14](https://arxiv.org/html/2608.10529#bib.bib22)\], with extensions to pure exploration\[[17](https://arxiv.org/html/2608.10529#bib.bib17)\], linear bandits\[[10](https://arxiv.org/html/2608.10529#bib.bib16)\], and minimax\-optimal procedures\[[8](https://arxiv.org/html/2608.10529#bib.bib5)\], while Catoni\-style confidence sequences sharpen what is achievable under weak moment assumptions\[[15](https://arxiv.org/html/2608.10529#bib.bib4)\]\.

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](https://arxiv.org/html/2608.10529#bib.bib11)\]considers delayed message passing and\[[16](https://arxiv.org/html/2608.10529#bib.bib1)\]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, andmHT\-DSEE—and prove regret guarantees summarized in Table[I](https://arxiv.org/html/2608.10529#S1.T1)\. The robust mean estimator and the single\-agent concentration arguments are adapted from\[[3](https://arxiv.org/html/2608.10529#bib.bib23),[14](https://arxiv.org/html/2608.10529#bib.bib22)\]; 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\.
## IIPreliminaries

### II\-AHeavy\-tailed bandits

Consider a stochastic MAB withKKarms\. Each arm𝒂∈𝒜:=\{1,…,K\}\\bm\{a\}\\in\\mathcal\{A\}:=\\\{1,\\dots,K\\\}has an unknown reward distributionν𝒂\\nu\_\{\\bm\{a\}\}with meanμ𝒂\\mu\_\{\\bm\{a\}\}\. At roundtt, the agent selects arm𝒂t\\bm\{a\}\_\{t\}and observes a reward drawn fromν𝒂t\\nu\_\{\\bm\{a\}\_\{t\}\}\. The expected regret at horizonTTis

RT=T​μ⋆−∑t=1T𝔼​\[μ𝒂t\]=∑𝒂∈𝒜Δ𝒂​𝔼​\[n𝒂​\(T\)\],R\_\{T\}=T\\mu^\{\\star\}\-\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[\\mu\_\{\\bm\{a\}\_\{t\}\}\]=\\sum\_\{\\bm\{a\}\\in\\mathcal\{A\}\}\\Delta\_\{\\bm\{a\}\}\\,\\mathbb\{E\}\[n\_\{\\bm\{a\}\}\(T\)\],\(1\)whereμ⋆=max𝒂⁡μ𝒂\\mu^\{\\star\}=\\max\_\{\\bm\{a\}\}\\mu\_\{\\bm\{a\}\},Δ𝒂=μ⋆−μ𝒂\\Delta\_\{\\bm\{a\}\}=\\mu^\{\\star\}\-\\mu\_\{\\bm\{a\}\}is the suboptimality gap, andn𝒂​\(T\)n\_\{\\bm\{a\}\}\(T\)is the number of pulls\. We assume heavy\-tailed rewards: there existε∈\(0,1\]\\varepsilon\\in\(0,1\]andv\>0v\>0such that for all𝒂∈𝒜\\bm\{a\}\\in\\mathcal\{A\},

𝔼​\[\|X𝒂−μ𝒂\|1\+ε\]≤v\.\\mathbb\{E\}\[\|X\_\{\\bm\{a\}\}\-\\mu\_\{\\bm\{a\}\}\|^\{1\+\\varepsilon\}\]\\leq v\.\(2\)This allows distributions with infinite variance \(whenε<1\\varepsilon<1\), capturing Pareto, Student\-tt, and other heavy\-tailed families; smallerε\\varepsiloncorresponds to heavier tails\.

### II\-BMulti\-agent extension

We extend the setting toMMplayers, where playeriihas an individual action set𝒜i\\mathcal\{A\}\_\{i\}of sizeKiK\_\{i\}\. The joint action space is𝒜=𝒜1×⋯×𝒜M\\mathcal\{A\}=\\mathcal\{A\}\_\{1\}\\times\\cdots\\times\\mathcal\{A\}\_\{M\}, containingKM:=∏i=1MKiK^\{M\}:=\\prod\_\{i=1\}^\{M\}K\_\{i\}joint arms\. At each roundtt, each player simultaneously selects an arm, forming joint arm𝒂​\(t\)=\(a1​\(t\),…,aM​\(t\)\)\\bm\{a\}\(t\)=\(a\_\{1\}\(t\),\\dots,a\_\{M\}\(t\)\), and then observes a reward sampled fromν𝒂​\(t\)\\nu\_\{\\bm\{a\}\(t\)\}\. The cumulative regret isRT=T​μ⋆−∑t=1T𝔼​\[X𝒂​\(t\)\]R\_\{T\}=T\\mu^\{\\star\}\-\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\[X\_\{\\bm\{a\}\(t\)\}\], whereμ⋆=max𝒂∈𝒜⁡μ𝒂\\mu^\{\\star\}=\\max\_\{\\bm\{a\}\\in\\mathcal\{A\}\}\\mu\_\{\\bm\{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 realizationX𝒂​\(t\)X\_\{\\bm\{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\)\\bm\{a\}\(t\)but each receives an independent sampleX𝒂​\(t\)i∼ν𝒂​\(t\)X\_\{\\bm\{a\}\(t\)\}^\{i\}\\sim\\nu\_\{\\bm\{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\.

### II\-CRobust upper confidence bounds

Throughout,μ^𝒂​\(t\)\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)is the truncated mean of\[[3](https://arxiv.org/html/2608.10529#bib.bib23)\]: writingX𝒂,1,…,X𝒂,n𝒂​\(t\)X\_\{\\bm\{a\},1\},\\dots,X\_\{\\bm\{a\},n\_\{\\bm\{a\}\}\(t\)\}for the rewards observed from arm𝒂\\bm\{a\},

μ^𝒂​\(t\)=1n𝒂​\(t\)​∑s=1n𝒂​\(t\)X𝒂,s​1​\{\|X𝒂,s\|≤\(v​slog⁡\(Tγ\)\)11\+ε\}\.\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)=\\frac\{1\}\{n\_\{\\bm\{a\}\}\(t\)\}\\sum\_\{s=1\}^\{n\_\{\\bm\{a\}\}\(t\)\}X\_\{\\bm\{a\},s\}\\,\\mathbf\{1\}\\\!\\left\\\{\|X\_\{\\bm\{a\},s\}\|\\leq\\left\(\\tfrac\{vs\}\{\\log\(T^\{\\gamma\}\)\}\\right\)^\{\\frac\{1\}\{1\+\\varepsilon\}\}\\right\\\}\.\(3\)The robust upper confidence bound \(RUCB\) for joint arm𝒂\\bm\{a\}is

RUCB𝒂​\(t\)=\{∞if​n𝒂​\(t\)=0,μ^𝒂​\(t\)\+α𝒂​\(t\)otherwise,\\mathrm\{RUCB\}\_\{\\bm\{a\}\}\(t\)=\\begin\{cases\}\\infty&\\text\{if \}n\_\{\\bm\{a\}\}\(t\)=0,\\\\ \\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)\+\\alpha\_\{\\bm\{a\}\}\(t\)&\\text\{otherwise,\}\\end\{cases\}\(4\)where the first case marks an arm from which nothing has yet been observed, so thatμ^𝒂​\(t\)\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)is undefined; setting the index to∞\\inftyforces every joint arm to be played at least once before any comparison is made\. The confidence radius is

α𝒂​\(t\)=v11\+ε​\(c​log⁡\(Tγ\)n𝒂​\(t\)\)ε1\+ε,\\alpha\_\{\\bm\{a\}\}\(t\)=v^\{\\frac\{1\}\{1\+\\varepsilon\}\}\\\!\\left\(\\frac\{c\\log\(T^\{\\gamma\}\)\}\{n\_\{\\bm\{a\}\}\(t\)\}\\right\)^\{\\\!\\frac\{\\varepsilon\}\{1\+\\varepsilon\}\},\(5\)withc,γ\>0c,\\gamma\>0, and\[[3](https://arxiv.org/html/2608.10529#bib.bib23), Prop\. 1\]givesPr⁡\(\|μ^𝒂​\(t\)−μ𝒂\|\>α𝒂​\(t\)\)≤t−γ\\Pr\(\|\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)\-\\mu\_\{\\bm\{a\}\}\|\>\\alpha\_\{\\bm\{a\}\}\(t\)\)\\leq t^\{\-\\gamma\}\. Only this concentration property is used below, so any estimator obeying a bound of the form \([5](https://arxiv.org/html/2608.10529#S2.E5)\)—median\-of\-means, or the Catoni\-style confidence sequences of\[[15](https://arxiv.org/html/2608.10529#bib.bib4)\]—may be substituted\. Such a substitution changes the constantccand the wayvventers, and hence the constants in all three theorems, but not the rates; Catoni\-style estimators give the sharpest constants asε→1\\varepsilon\\to 1, at the cost of solving an implicit equation at each round\.

## IIIProblem 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𝒜\\mathcal\{A\}for consistent tie\-breaking:𝒂<𝒃\\bm\{a\}<\\bm\{b\}if there existsnnsuch thatai=bia\_\{i\}=b\_\{i\}for alli<ni<nandan<bna\_\{n\}<b\_\{n\}\. Each player then computesRUCB𝒂​\(t\)\\mathrm\{RUCB\}\_\{\\bm\{a\}\}\(t\)for every joint arm and selects the highest, breaking ties lexicographically, yieldingmRUCB\-A\(Algorithm[1](https://arxiv.org/html/2608.10529#alg1)\)\.

Algorithm 1mRUCB\-A1:Players agree on a lexicographic ordering of

𝒜\\mathcal\{A\}\.

2:Init\.

n𝒂​\(0\)←0n\_\{\\bm\{a\}\}\(0\)\\leftarrow 0,

μ^𝒂​\(0\)←0\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(0\)\\leftarrow 0for all

𝒂∈𝒜\\bm\{a\}\\in\\mathcal\{A\}\.

3:for

t=1,…,Tt=1,\\dots,Tdo

4:Compute

RUCB𝒂​\(t\)\\mathrm\{RUCB\}\_\{\\bm\{a\}\}\(t\)for all

𝒂∈𝒜\\bm\{a\}\\in\\mathcal\{A\}via \([4](https://arxiv.org/html/2608.10529#S2.E4)\)\.

5:Select

𝒂​\(t\)←arg⁡max𝒂⁡RUCB𝒂​\(t\)\\bm\{a\}\(t\)\\leftarrow\\arg\\max\_\{\\bm\{a\}\}\\mathrm\{RUCB\}\_\{\\bm\{a\}\}\(t\)\(ties: lexicographic\)\.

6:Pull individual arm; observe common reward; update statistics\.

###### Theorem 1\.

Under condition \([2](https://arxiv.org/html/2608.10529#S2.E2)\), if all players followmRUCB\-A, the expected regret satisfiesRT=O​\(log⁡\(T\)​∑𝐚∈𝒜Δ𝐚−1/ε\)R\_\{T\}=O\\\!\\left\(\\log\(T\)\\sum\_\{\\bm\{a\}\\in\\mathcal\{A\}\}\\Delta\_\{\\bm\{a\}\}^\{\-1/\\varepsilon\}\\right\)\.

###### 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 overKMK^\{M\}arms, and the analysis follows\[[3](https://arxiv.org/html/2608.10529#bib.bib23)\]\. For each suboptimal arm𝒂\\bm\{a\}with gapΔ𝒂\>0\\Delta\_\{\\bm\{a\}\}\>0, define the good event at roundtt:𝒢t:\|μ^𝒂​\(t\)−μ𝒂\|≤α𝒂​\(t\)\\mathcal\{G\}\_\{t\}:\|\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)\-\\mu\_\{\\bm\{a\}\}\|\\leq\\alpha\_\{\\bm\{a\}\}\(t\)for all𝒂\\bm\{a\}\. By the concentration bound of Section[II\-C](https://arxiv.org/html/2608.10529#S2.SS3),Pr⁡\(𝒢tc\)≤KM​t−γ\\Pr\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\leq K^\{M\}t^\{\-\\gamma\}\. Under𝒢t\\mathcal\{G\}\_\{t\}, selection of𝒂\\bm\{a\}requiresμ^𝒂​\(t\)\+α𝒂​\(t\)≥μ^𝒂⋆​\(t\)\+α𝒂⋆​\(t\)\\widehat\{\\mu\}\_\{\\bm\{a\}\}\(t\)\+\\alpha\_\{\\bm\{a\}\}\(t\)\\geq\\widehat\{\\mu\}\_\{\\bm\{a\}^\{\\star\}\}\(t\)\+\\alpha\_\{\\bm\{a\}^\{\\star\}\}\(t\), which implies2​α𝒂​\(t\)≥Δ𝒂2\\alpha\_\{\\bm\{a\}\}\(t\)\\geq\\Delta\_\{\\bm\{a\}\}\. This fails afterτ𝒂=c​γ​log⁡\(T\)​\(2​v1/\(1\+ε\)/Δ𝒂\)\(1\+ε\)/ε\\tau\_\{\\bm\{a\}\}=c\\gamma\\log\(T\)\(2v^\{1/\(1\+\\varepsilon\)\}/\\Delta\_\{\\bm\{a\}\}\)^\{\(1\+\\varepsilon\)/\\varepsilon\}pulls\. Hence𝔼​\[n𝒂​\(T\)\]≤τ𝒂\+∑t=1TPr⁡\(𝒢tc\)\\mathbb\{E\}\[n\_\{\\bm\{a\}\}\(T\)\]\\leq\\tau\_\{\\bm\{a\}\}\+\\sum\_\{t=1\}^\{T\}\\Pr\(\\mathcal\{G\}\_\{t\}^\{c\}\), where the tail sum converges forγ\>1\\gamma\>1\. SummingΔ𝒂⋅𝔼​\[n𝒂​\(T\)\]\\Delta\_\{\\bm\{a\}\}\\cdot\\mathbb\{E\}\[n\_\{\\bm\{a\}\}\(T\)\]over all suboptimal arms gives the result\. ∎

This matches the optimal single\-agent heavy\-tailed rate overKMK^\{M\}arms\. Since theKMK^\{M\}dependence is unavoidable even for a centralized learner, the decentralized agents incur no additional cost from action asymmetry\.

## IVProblem B: Independent Rewards, Observed Actions

In Problem B, players observe the joint action but receive*independent*reward samplesX𝒂​\(t\)1,…,X𝒂​\(t\)M∼i\.i\.d\.ν𝒂​\(t\)X\_\{\\bm\{a\}\(t\)\}^\{1\},\\dots,X\_\{\\bm\{a\}\(t\)\}^\{M\}\\stackrel\{\{\\scriptstyle\\text\{i\.i\.d\.\}\}\}\{\{\\sim\}\}\\nu\_\{\\bm\{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\-Intervalsavoids this by replacing index maximization with*round\-robin elimination*: players cycle through a common active setSS, and an arm leavesSSonly through a signal that every player observes\.

For each joint arm𝒂\\bm\{a\}and playeriithe algorithm maintains

I𝒂i​\(t\)=\[μ^𝒂i​\(t\)−α𝒂​\(t\),μ^𝒂i​\(t\)\+α𝒂​\(t\)\],I\_\{\\bm\{a\}\}^\{i\}\(t\)=\\left\[\\widehat\{\\mu\}\_\{\\bm\{a\}\}^\{i\}\(t\)\-\\alpha\_\{\\bm\{a\}\}\(t\),\\;\\widehat\{\\mu\}\_\{\\bm\{a\}\}^\{i\}\(t\)\+\\alpha\_\{\\bm\{a\}\}\(t\)\\right\],\(6\)whereα𝒂​\(t\)\\alpha\_\{\\bm\{a\}\}\(t\)is common to all players because it depends only on the shared pull countn𝒂​\(t\)n\_\{\\bm\{a\}\}\(t\)\. Elimination proceeds in three stages\.*Detection*: if playeriifinds thatI𝒂i​\(t\)I\_\{\\bm\{a\}\}^\{i\}\(t\)lies strictly below and disjoint from the interval of another active arm, then𝒂\\bm\{a\}is dominated from playerii’s perspective\.*Signaling*: playeriithen 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\)\\bm\{a\}\(t\)and the realized one𝒂′​\(t\)\\bm\{a\}^\{\\prime\}\(t\), and mark𝒂​\(t\)\\bm\{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](https://arxiv.org/html/2608.10529#alg2)gives the procedure\.

Algorithm 2mRUCB\-Intervals1:Players agree on an ordering of

𝒜\\mathcal\{A\}; set

S←𝒜S\\leftarrow\\mathcal\{A\},

P←∅P\\leftarrow\\emptyset\.

2:while

t≤Tt\\leq Tdo

3:foreach

𝒂∈S\\bm\{a\}\\in Sin orderdo

4:ifsome player

iifinds

I𝒂i​\(t\)I\_\{\\bm\{a\}\}^\{i\}\(t\)strictly below the interval of another arm of

SSthen

5:That player pulls a*different*individual arm; all players observe

𝒂′​\(t\)≠𝒂\\bm\{a\}^\{\\prime\}\(t\)\\neq\\bm\{a\}and set

P←P∪\{𝒂\}P\\leftarrow P\\cup\\\{\\bm\{a\}\\\}; the reward of this round is discarded\.

6:else

7:All players pull the components of

𝒂\\bm\{a\}; player

iiobserves

X𝒂iX\_\{\\bm\{a\}\}^\{i\}and updates

I𝒂iI\_\{\\bm\{a\}\}^\{i\}via \([6](https://arxiv.org/html/2608.10529#S4.E6)\);

n𝒂←n𝒂\+1n\_\{\\bm\{a\}\}\\leftarrow n\_\{\\bm\{a\}\}\+1\.

8:

S←S∖PS\\leftarrow S\\setminus P;

P←∅P\\leftarrow\\emptyset\.

###### Lemma 1\.

UndermRUCB\-Intervals, at every round all players hold the same active setS​\(t\)S\(t\)and the same pull countsn𝐚​\(t\)n\_\{\\bm\{a\}\}\(t\)\. Moreover, if𝐚\\bm\{a\}is the arm scheduled at roundtt, thenn𝐛​\(t\)≥n𝐚​\(t\)n\_\{\\bm\{b\}\}\(t\)\\geq n\_\{\\bm\{a\}\}\(t\)for every𝐛∈S​\(t\)\\bm\{b\}\\in S\(t\)\.

###### Proof\.

Both claims follow by induction ontt\. InitiallyS=𝒜S=\\mathcal\{A\}and all counts are zero\. The scheduled arm is a deterministic function ofSSand 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, soSSremains 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 followmRUCB\-Intervalsunder \([2](https://arxiv.org/html/2608.10529#S2.E2)\), then

RT≤c​γ​41\+εε​v1ε​log⁡\(T\)​∑𝒂≠𝒂⋆Δ𝒂−1/ε\+∑𝒂≠𝒂⋆Δ𝒂\+\(KM−1\)​Δmax\+O​\(1\),\\begin\{split\}R\_\{T\}\\leq\\;&c\\gamma\\,4^\{\\frac\{1\+\\varepsilon\}\{\\varepsilon\}\}v^\{\\frac\{1\}\{\\varepsilon\}\}\\log\(T\)\\sum\_\{\\bm\{a\}\\neq\\bm\{a\}^\{\\star\}\}\\Delta\_\{\\bm\{a\}\}^\{\-1/\\varepsilon\}\\\\ &\+\\sum\_\{\\bm\{a\}\\neq\\bm\{a\}^\{\\star\}\}\\Delta\_\{\\bm\{a\}\}\+\(K^\{M\}\-1\)\\Delta\_\{\\max\}\+O\(1\),\\end\{split\}\(7\)where theO​\(1\)O\(1\)term collects the contribution of the failure event and is independent ofTTforγ\>1\\gamma\>1\.

###### Proof\.

Let𝒢t\\mathcal\{G\}\_\{t\}be the event that\|μ^𝒂i​\(t\)−μ𝒂\|≤α𝒂​\(t\)\|\\widehat\{\\mu\}\_\{\\bm\{a\}\}^\{i\}\(t\)\-\\mu\_\{\\bm\{a\}\}\|\\leq\\alpha\_\{\\bm\{a\}\}\(t\)for alliiand all𝒂\\bm\{a\}; by Section[II\-C](https://arxiv.org/html/2608.10529#S2.SS3)and a union bound over theM​KMMK^\{M\}player\-arm pairs,Pr⁡\(𝒢tc\)≤M​KM​t−γ\\Pr\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\leq MK^\{M\}t^\{\-\\gamma\}\.

*Step 1:𝐚⋆\\bm\{a\}^\{\\star\}is never eliminated\.*Under𝒢t\\mathcal\{G\}\_\{t\}, for every playeriiand every active𝒃\\bm\{b\}, the lower end ofI𝒂⋆iI^\{i\}\_\{\\bm\{a\}^\{\\star\}\}satisfiesμ^𝒂⋆i\+α𝒂⋆≥μ⋆≥μ𝒃≥μ^𝒃i−α𝒃\\widehat\{\\mu\}^\{i\}\_\{\\bm\{a\}^\{\\star\}\}\+\\alpha\_\{\\bm\{a\}^\{\\star\}\}\\geq\\mu^\{\\star\}\\geq\\mu\_\{\\bm\{b\}\}\\geq\\widehat\{\\mu\}^\{i\}\_\{\\bm\{b\}\}\-\\alpha\_\{\\bm\{b\}\}, soI𝒂⋆iI^\{i\}\_\{\\bm\{a\}^\{\\star\}\}never lies strictly below the interval of another active arm\. No player signals on𝒂⋆\\bm\{a\}^\{\\star\}, and by Lemma[1](https://arxiv.org/html/2608.10529#Thmlemma1)no player removes it\.

*Step 2: Elimination time\.*Let𝒂≠𝒂⋆\\bm\{a\}\\neq\\bm\{a\}^\{\\star\}be scheduled at roundtt\. By Lemma[1](https://arxiv.org/html/2608.10529#Thmlemma1),n𝒂⋆​\(t\)≥n𝒂​\(t\)n\_\{\\bm\{a\}^\{\\star\}\}\(t\)\\geq n\_\{\\bm\{a\}\}\(t\)and henceα𝒂⋆​\(t\)≤α𝒂​\(t\)\\alpha\_\{\\bm\{a\}^\{\\star\}\}\(t\)\\leq\\alpha\_\{\\bm\{a\}\}\(t\)\. Under𝒢t\\mathcal\{G\}\_\{t\}the upper end ofI𝒂iI^\{i\}\_\{\\bm\{a\}\}is at mostμ𝒂\+2​α𝒂​\(t\)\\mu\_\{\\bm\{a\}\}\+2\\alpha\_\{\\bm\{a\}\}\(t\)and the lower end ofI𝒂⋆iI^\{i\}\_\{\\bm\{a\}^\{\\star\}\}is at leastμ⋆−2​α𝒂​\(t\)\\mu^\{\\star\}\-2\\alpha\_\{\\bm\{a\}\}\(t\), so*every*player detects domination as soon as4​α𝒂​\(t\)<Δ𝒂4\\alpha\_\{\\bm\{a\}\}\(t\)<\\Delta\_\{\\bm\{a\}\}\. By \([5](https://arxiv.org/html/2608.10529#S2.E5)\) this holds oncen𝒂​\(t\)n\_\{\\bm\{a\}\}\(t\)exceeds

τ𝒂=c​γ​log⁡\(T\)​\(4​v1/\(1\+ε\)Δ𝒂\)\(1\+ε\)/ε,\\tau\_\{\\bm\{a\}\}=c\\gamma\\log\(T\)\\left\(\\frac\{4v^\{1/\(1\+\\varepsilon\)\}\}\{\\Delta\_\{\\bm\{a\}\}\}\\right\)^\{\(1\+\\varepsilon\)/\\varepsilon\},\(8\)so thatn𝒂​\(T\)≤τ𝒂\+1n\_\{\\bm\{a\}\}\(T\)\\leq\\tau\_\{\\bm\{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 is4​α𝒂4\\alpha\_\{\\bm\{a\}\}, rather than the2​α𝒂2\\alpha\_\{\\bm\{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](https://arxiv.org/html/2608.10529#Thmlemma1)its removal consumes exactly one round in which the realized joint action is unintended, contributing regret at mostΔmax\\Delta\_\{\\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\)\\Delta\_\{\\max\}, independent of bothTTandMM\.

*Step 4: Summing\.*By Step 2,∑𝒂≠𝒂⋆Δ𝒂​\(τ𝒂\+1\)\\sum\_\{\\bm\{a\}\\neq\\bm\{a\}^\{\\star\}\}\\Delta\_\{\\bm\{a\}\}\(\\tau\_\{\\bm\{a\}\}\+1\)gives the first two terms of \([7](https://arxiv.org/html/2608.10529#S4.E7)\)\. Adding the failure contribution∑t≤TPr⁡\(𝒢tc\)​Δmax≤M​KM​Δmax​∑t≥1t−γ=O​\(1\)\\sum\_\{t\\leq T\}\\Pr\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\Delta\_\{\\max\}\\leq MK^\{M\}\\Delta\_\{\\max\}\\sum\_\{t\\geq 1\}t^\{\-\\gamma\}=O\(1\)forγ\>1\\gamma\>1, together with Step 3, yields the bound\. ∎

The leading term matches Problem A up to the constant4\(1\+ε\)/ε4^\{\(1\+\\varepsilon\)/\\varepsilon\}in place of2\(1\+ε\)/ε2^\{\(1\+\\varepsilon\)/\\varepsilon\}, 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\)\\alpha\_\{\\bm\{a\}\}\(t\)is common across players, so a single detection is enough to eliminate an arm for everyone\.

## VProblem 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](https://arxiv.org/html/2608.10529#alg3)\) follows the DSEE framework\[[14](https://arxiv.org/html/2608.10529#bib.bib22)\]\. Fix an increasingw​\(t\)→∞w\(t\)\\to\\inftyand letD​\(t\)=⌈w​\(t\)​log⁡t⌉D\(t\)=\\lceil w\(t\)\\log t\\rceilbe the target number of samples of each joint arm by roundtt\. If fewer thanKM​D​\(t\)K^\{M\}D\(t\)exploration rounds have been used, roundttis 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 testN​\(t\)<KM​D​\(t\)N\(t\)<K^\{M\}D\(t\)depends only ontt, players stay synchronized without communication\. Two features matter for the analysis: the schedule is*anytime*, requiring neitherTTnor the gaps, and the confidence radius useslog⁡t\\log trather thanlog⁡T\\log T\.

Algorithm 3mHT\-DSEE1:Players agree on an ordering of

𝒜\\mathcal\{A\}and on

w​\(t\)↑∞w\(t\)\\uparrow\\infty;

N←0N\\leftarrow 0\.

2:for

t=1,…,Tt=1,\\dots,Tdo

3:if

N<KM​⌈w​\(t\)​log⁡t⌉N<K^\{M\}\\lceil w\(t\)\\log t\\rceilthen

4:Play the next joint arm in the cyclic order;

N←N\+1N\\leftarrow N\+1; each player stores its own reward\.

5:else

6:Player

iiplays its own component of

arg⁡max𝒂⁡RUCB𝒂i​\(t\)\\arg\\max\_\{\\bm\{a\}\}\\mathrm\{RUCB\}^\{i\}\_\{\\bm\{a\}\}\(t\), computed from exploration samples\.

###### Theorem 3\.

Under \([2](https://arxiv.org/html/2608.10529#S2.E2)\), if all players followmHT\-DSEEwithγ\>1\\gamma\>1, then

RT≤Δmax​KM​D​\(T\)\+Δmax​t0\+O​\(1\),R\_\{T\}\\leq\\Delta\_\{\\max\}K^\{M\}D\(T\)\+\\Delta\_\{\\max\}t\_\{0\}\+O\(1\),\(9\)wheret0=min⁡\{t:w​\(t\)\>c​γ​\(2​v1/\(1\+ε\)/Δmin\)\(1\+ε\)/ε\}t\_\{0\}=\\min\\\{t:w\(t\)\>c\\gamma\(2v^\{1/\(1\+\\varepsilon\)\}/\\Delta\_\{\\min\}\)^\{\(1\+\\varepsilon\)/\\varepsilon\}\\\}depends onε,v\\varepsilon,vand the gaps but*not*onTT\. Withw​\(t\)=⌈log⁡t⌉w\(t\)=\\lceil\\log t\\rceilthis givesRT=O​\(KM​log2⁡T\)R\_\{T\}=O\(K^\{M\}\\log^\{2\}T\)\.

###### Proof\.

*Step 1: Exploration\.*At mostKM​D​\(T\)K^\{M\}D\(T\)rounds are exploration rounds, each contributing regret at mostΔmax\\Delta\_\{\\max\}, which is the first term\.

*Step 2: Good event\.*At an exploitation roundttevery arm hasD​\(t\)D\(t\)samples for each player\. By Section[II\-C](https://arxiv.org/html/2608.10529#S2.SS3)with confidence levelt−γt^\{\-\\gamma\}and a union bound over theM​KMMK^\{M\}player\-arm pairs, the event𝒢t\\mathcal\{G\}\_\{t\}that\|μ^𝒂i−μ𝒂\|≤α​\(D​\(t\)\)\|\\widehat\{\\mu\}^\{i\}\_\{\\bm\{a\}\}\-\\mu\_\{\\bm\{a\}\}\|\\leq\\alpha\(D\(t\)\)for alli,𝒂i,\\bm\{a\}hasPr⁡\(𝒢tc\)≤M​KM​t−γ\\Pr\(\\mathcal\{G\}\_\{t\}^\{c\}\)\\leq MK^\{M\}t^\{\-\\gamma\}, whereα​\(n\)=v1/\(1\+ε\)​\(c​log⁡\(tγ\)/n\)ε/\(1\+ε\)\\alpha\(n\)=v^\{1/\(1\+\\varepsilon\)\}\(c\\log\(t^\{\\gamma\}\)/n\)^\{\\varepsilon/\(1\+\\varepsilon\)\}\.

*Step 3: Coordination\.*On𝒢t\\mathcal\{G\}\_\{t\},RUCB𝒂i≤μ𝒂\+2​α​\(D​\(t\)\)\\mathrm\{RUCB\}^\{i\}\_\{\\bm\{a\}\}\\leq\\mu\_\{\\bm\{a\}\}\+2\\alpha\(D\(t\)\)andRUCB𝒂⋆i≥μ⋆\\mathrm\{RUCB\}^\{i\}\_\{\\bm\{a\}^\{\\star\}\}\\geq\\mu^\{\\star\}for every playerii, so every player selects𝒂⋆\\bm\{a\}^\{\\star\}once2​α​\(D​\(t\)\)<Δmin2\\alpha\(D\(t\)\)<\\Delta\_\{\\min\}, i\.e\. once

D\(t\)\>cγlog\(t\)\(2​v1/\(1\+ε\)Δmin\)\(1\+ε\)/ε=:κlogt\.D\(t\)\>c\\gamma\\log\(t\)\\left\(\\frac\{2v^\{1/\(1\+\\varepsilon\)\}\}\{\\Delta\_\{\\min\}\}\\right\)^\{\(1\+\\varepsilon\)/\\varepsilon\}=:\\kappa\\log t\.\(10\)The threshold does not depend on the player index, so the players agree; and sinceD​\(t\)≥w​\(t\)​log⁡tD\(t\)\\geq w\(t\)\\log t, condition \([10](https://arxiv.org/html/2608.10529#S5.E10)\) holds as soon asw​\(t\)\>κw\(t\)\>\\kappa, that is for everyt≥t0t\\geq t\_\{0\}\. This is the role of the anytime schedule: both sides of \([10](https://arxiv.org/html/2608.10529#S5.E10)\) scale withlog⁡t\\log t, so the crossing timet0t\_\{0\}is determined bywwand the gaps alone and does not grow with the horizon\. Each player then plays its component of𝒂⋆\\bm\{a\}^\{\\star\}, and the realized joint arm is exactly𝒂⋆\\bm\{a\}^\{\\star\}\.

*Step 4: Exploitation regret\.*Exploitation rounds witht<t0t<t\_\{0\}contribute at mostΔmax​t0\\Delta\_\{\\max\}t\_\{0\}\. Fort≥t0t\\geq t\_\{0\}, regret is incurred only on𝒢tc\\mathcal\{G\}\_\{t\}^\{c\}, contributing at mostM​KM​Δmax​∑t≥1t−γ=O​\(1\)MK^\{M\}\\Delta\_\{\\max\}\\sum\_\{t\\geq 1\}t^\{\-\\gamma\}=O\(1\)forγ\>1\\gamma\>1\. Adding Step 1 gives \([9](https://arxiv.org/html/2608.10529#S5.E9)\)\. Takingw​\(t\)=⌈log⁡t⌉w\(t\)=\\lceil\\log t\\rceilgivesD​\(T\)=O​\(log2⁡T\)D\(T\)=O\(\\log^\{2\}T\)\. ∎

## VIExperiments

### VI\-ASetup

We takeM=2M=2players,K=2K=2individual arms \(KM=4K^\{M\}=4joint arms\), and horizonT=106T=10^\{6\}, averaging over1010independent runs on the fixed instance𝝁=\(0\.44,0\.57,0\.91,0\.25\)\\bm\{\\mu\}=\(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 armaayields a Pareto reward with shapea0=2a\_\{0\}=2and scalexm=μa​\(a0−1\)/a0x\_\{m\}=\\mu\_\{a\}\(a\_\{0\}\-1\)/a\_\{0\}, so that𝔼​\[Xa\]=μa\\mathbb\{E\}\[X\_\{a\}\]=\\mu\_\{a\}\. This distribution has finite mean and*infinite variance*: its centered moments of order1\+ε1\+\\varepsilonare finite exactly forε<1\\varepsilon<1\. We therefore setε=0\.5\\varepsilon=0\.5, for which𝔼​\|Xa−μa\|1\.5≤0\.75<1=v\\mathbb\{E\}\|X\_\{a\}\-\\mu\_\{a\}\|^\{1\.5\}\\leq 0\.75<1=vfor everyμa∈\[0,1\]\\mu\_\{a\}\\in\[0,1\], so \([2](https://arxiv.org/html/2608.10529#S2.E2)\) holds; takingε=1\\varepsilon=1would instead require a finite second moment and is not admissible for this reward family\. All three algorithms use the truncated\-mean estimator \([3](https://arxiv.org/html/2608.10529#S2.E3)\) with\(c,γ\)=\(1,2\)\(c,\\gamma\)=\(1,2\), i\.e\. exactly the estimator the analysis assumes, andmHT\-DSEEusesw​\(t\)=⌈log⁡t⌉w\(t\)=\\lceil\\log t\\rceil\.

### VI\-BResults

![Refer to caption](https://arxiv.org/html/2608.10529v1/plot.png)Figure 1:Mean cumulative regret over1010runs under Pareto rewards with infinite variance \(M=2M\{=\}2,K=2K\{=\}2,T=106T\{=\}10^\{6\}\), log–log axes\.Figure[1](https://arxiv.org/html/2608.10529#S6.F1)shows mean cumulative regret\. All three curves are clearly sublinear, confirming that each algorithm identifies𝒂⋆\\bm\{a\}^\{\\star\}under infinite\-variance rewards and with the robust estimator in place\.mRUCB\-Aends at214±24214\\pm 24andmHT\-DSEEat292±21292\\pm 21, both still growing slowly, whilemRUCB\-Intervalsends at4115±2854115\\pm 285but is exactly flat beyond≈7×104\{\\approx\}7\\times 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\\alpha\_\{\\bm\{a\}\}<\\Delta\_\{\\bm\{a\}\}, whereas the index comparisons of Problems A and C need only2​α𝒂<Δ𝒂2\\alpha\_\{\\bm\{a\}\}<\\Delta\_\{\\bm\{a\}\}; by \([5](https://arxiv.org/html/2608.10529#S2.E5)\) this is2\(1\+ε\)/ε=82^\{\(1\+\\varepsilon\)/\\varepsilon\}=8times more samples of each arm whenε=0\.5\\varepsilon=0\.5, which is what the early growth of the orange curve buys\. The payoff is that once the active set collapses,mRUCB\-Intervalsincurs no further regret at all, whereas the other two keep exploring; the curves would therefore cross at larger horizons\. Similarly,mHT\-DSEEis inexpensive here because its exploration budgetKM​⌈log2⁡t⌉K^\{M\}\\lceil\\log^\{2\}t\\rceilis only≈760\{\\approx\}760rounds atT=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](https://arxiv.org/html/2608.10529#S1.T1)is asymptotic: at moderate horizons the constants attached to each coordination mechanism dominate\. A further practical caveat is that the joint action space grows asKMK^\{M\}, so larger instances lengthen the exploration phases ofmHT\-DSEEand slow the elimination cascade ofmRUCB\-Intervals\.

## VIIConclusion

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 alog⁡T\\log Tfactor 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](https://arxiv.org/html/2608.10529#bib.bib23),[14](https://arxiv.org/html/2608.10529#bib.bib22)\], assume that\(ε,v\)\(\\varepsilon,v\)are known: a conservative choice \(smallerε\\varepsilonor largervv\) 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](https://arxiv.org/html/2608.10529#bib.bib4)\]—remains open\. Second, tighter lower bounds for Problem C would clarify whether the extralog⁡T\\log Tfactor 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 exponentialKMK^\{M\}dependence, are also natural directions\.

## References

- \[1\]B\. Awerbuch and R\. Kleinberg\(2008\)Competitive collaborative learning\.Journal of Computer and System Sciences74\(8\),pp\. 1271–1288\.Note:Learning Theory 2005External Links:ISSN 0022\-0000,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.jcss.2007.08.004),[Link](https://www.sciencedirect.com/science/article/pii/S0022000007001250)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[2\]E\. Boursier and V\. Perchet\(2024\)A survey on multi\-player bandits\.External Links:2211\.16275,[Link](https://arxiv.org/abs/2211.16275)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[3\]S\. Bubeck, N\. Cesa\-Bianchi, and G\. Lugosi\(2012\)Bandits with heavy tail\.External Links:1209\.1727,[Link](https://arxiv.org/abs/1209.1727)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1),[§I](https://arxiv.org/html/2608.10529#S1.p5.1),[§II\-C](https://arxiv.org/html/2608.10529#S2.SS3.p1.11),[§II\-C](https://arxiv.org/html/2608.10529#S2.SS3.p1.3),[§III](https://arxiv.org/html/2608.10529#S3.1.p1.15),[§VII](https://arxiv.org/html/2608.10529#S7.p2.5)\.
- \[4\]W\. Chang, M\. Jafarnia\-Jahromi, and R\. Jain\(2021\)Online learning for cooperative multi\-player multi\-armed bandits\.CoRRabs/2109\.03818\.External Links:[Link](https://arxiv.org/abs/2109.03818),2109\.03818Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[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](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[6\]A\. Dubeyet al\.\(2020\)Cooperative multi\-agent bandits with heavy tails\.InInternational conference on machine learning,pp\. 2730–2739\.Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p4.1)\.
- \[7\]D\. Kalathil, N\. Nayyar, and R\. Jain\(2014\)Decentralized learning for multiplayer multiarmed bandits\.IEEE Transactions on Information Theory60\(4\),pp\. 2331–2345\.External Links:[Document](https://dx.doi.org/10.1109/TIT.2014.2302471)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[8\]K\. Lee and S\. Lim\(2024\)Minimax optimal bandits for heavy tail rewards\.IEEE Transactions on Neural Networks and Learning Systems35\(4\),pp\. 5280–5294\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2022.3203035)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1)\.
- \[9\]H\. E\. Robbins\(1952\)Some aspects of the sequential design of experiments\.Bulletin of the American Mathematical Society58,pp\. 527–535\.External Links:[Link](https://api.semanticscholar.org/CorpusID:15556973)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p1.1)\.
- \[10\]H\. Shao, X\. Yu, I\. King, and M\. R\. Lyu\(2018\)Almost optimal algorithms for linear stochastic bandits with heavy\-tailed payoffs\.InAdvances in Neural Information Processing Systems,S\. Bengio, H\. Wallach, H\. Larochelle, K\. Grauman, N\. Cesa\-Bianchi, and R\. Garnett \(Eds\.\),Vol\.31,pp\.\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2018/file/173f0f6bb0ee97cf5098f73ee94029d4-Paper.pdf)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1)\.
- \[11\]C\. Shi and C\. Shen\(2021\)Multi\-player multi\-armed bandits with collision\-dependent reward distributions\.IEEE Transactions on Signal Processing69,pp\. 4385–4402\.External Links:ISSN 1941\-0476,[Link](http://dx.doi.org/10.1109/TSP.2021.3093261),[Document](https://dx.doi.org/10.1109/tsp.2021.3093261)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[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\.InProceedings of the 30th International Conference on Machine Learning,S\. Dasgupta and D\. McAllester \(Eds\.\),Proceedings of Machine Learning Research, Vol\.28,Atlanta, Georgia, USA,pp\. 19–27\.External Links:[Link](https://proceedings.mlr.press/v28/szorenyi13.html)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p2.1)\.
- \[13\]W\. R\. Thompson\(1933\)On the likelihood that one unknown probability exceeds another in view of the evidence of two samples\.Biometrika25\(3/4\),pp\. 285–294\.External Links:ISSN 00063444,[Link](http://www.jstor.org/stable/2332286)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p1.1)\.
- \[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](https://arxiv.org/abs/1106.6104)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1),[§I](https://arxiv.org/html/2608.10529#S1.p5.1),[§V](https://arxiv.org/html/2608.10529#S5.p2.10),[§VII](https://arxiv.org/html/2608.10529#S7.p2.5)\.
- \[15\]H\. Wang and A\. Ramdas\(2023\-09\)Catoni\-style confidence sequences for heavy\-tailed mean estimation\.Stochastic Processes and their Applications163,pp\. 168–202\.External Links:ISSN 0304\-4149,[Link](http://dx.doi.org/10.1016/j.spa.2023.05.007),[Document](https://dx.doi.org/10.1016/j.spa.2023.05.007)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1),[§II\-C](https://arxiv.org/html/2608.10529#S2.SS3.p1.11),[§VII](https://arxiv.org/html/2608.10529#S7.p2.5)\.
- \[16\]X\. Wang and M\. Xu\(2025\)Multi\-agent multi\-armed bandit with fully heavy\-tailed dynamics\.External Links:2501\.19239,[Link](https://arxiv.org/abs/2501.19239)Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p4.1)\.
- \[17\]X\. Yu, H\. Shao, M\. R\. Lyu, and I\. King\(2018\)Pure exploration of multi\-armed bandits with heavy\-tailed payoffs\.\.InUAI,pp\. 937–946\.Cited by:[§I](https://arxiv.org/html/2608.10529#S1.p3.1)\.