Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization

# Multi-Objective Multi-Agent Bandits: From Learning Efficiency to Fairness Optimization
Source: [https://arxiv.org/html/2605.06864](https://arxiv.org/html/2605.06864)
John Wang University of Massachusetts Amherst jawang@umass\.edu &Mengfan Xu University of Massachusetts Amherst mengfanxu@umass\.edu

###### Abstract

We study multi\-objective multi\-agent multi\-armed bandits \(MO\-MA\-MAB\) under stochastic rewards, where agents observe heterogeneous reward vectors and communicate over time\-varying graphs\. We formulate this emerging problem setting to address*efficient learning*, measured by Pareto regret, and incorporate*fair learning*as an additional goal, captured via social welfare\. To measure efficiency, we formulate Pareto regret and developPareto UCB1 Gossip, whose novel exploration radius explicitly separates statistical uncertainty in Pareto\-based inference from consensus error\. To express the fairness constraint, we formulate a Nash Social Welfare objective over preference\-scalarized rewards and proposeSimulated NSW UCB Gossip, which integrates preference\-based reward simulation, gossip\-based utility estimation, and UCB\-style exploration\. We prove thatPareto UCB1 Gossipachieves𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\)regret and an instance\-independent rate of𝒪​\(T\)\\mathcal\{O\}\(\\sqrt\{T\}\), whileSimulated NSW UCB Gossipachieves an instance\-independent regret bound of𝒪​\(T3/4\)\\mathcal\{O\}\(T^\{3/4\}\)\. This separation reveals the cost of imposing the fairness constraint to our efficiency objective: fairness limits information aggregation and slows convergence\. Experiments show that our methods consistently outperform baselines, improving performance by approximately100%100\\%and50%50\\%in the efficiency and fairness settings, respectively\.

## 1Introduction

Sequential decision\-making under uncertainty is commonly modeled using the multi\-armed bandit \(MAB\) framework\. In its classical form, a learner repeatedly selects from a set of actions \(or “arms”\), each associated with an unknown reward distribution, and observes only the reward of the chosen action\. The learner’s objective is to maximize cumulative reward over time, despite two fundamental challenges: uncertainty in the underlying reward distributions and limited feedback, as observations are restricted to the selected actions\. These challenges give rise to the fundamental trade\-off between exploration, gathering information about uncertain arms, and exploitation, leveraging current estimates to select the best\-performing option\.

This combination of uncertainty and partial observability arises naturally in many real\-world applications\. In online recommendation systems a platform must select a single item to display while only observing user feedback for that choice, leaving the outcomes of alternative recommendations unknown\. In adaptive clinical trials, treatments must be sequentially assigned to patients with uncertain efficacy, and only the outcomes of administered treatments are observed\. In networked systems, decisions such as resource allocation or routing must be made under stochastic conditions with feedback limited to realized actions\. Across these domains, the need to learn from noisy, incomplete observations while optimizing performance makes the MAB framework a powerful and widely applicable modeling paradigm\.

Many modern decision\-making systems are inherently multi\-agent, where multiple learners interact with a shared set of actions under uncertainty\. This motivates the study of multi\-agent multi\-armed bandits \(MA\-MAB\) in the stochastic setting, where each agent observes noisy rewards and must learn the underlying reward structure over time\. In contrast to the single\-agent case, agents can leverage information generated by others to accelerate learning, partially mitigating the challenges of uncertainty and limited feedback\. By combining local observations with information shared across agents, MA\-MAB frameworks enable the formation of more accurate and robust reward estimates, improving learning efficiency in the presence of noise\. Such cooperative learning arises naturally in applications including distributed sensor networks aggregating noisy measurements, wireless communication systems where devices learn channel quality through shared experience, and large\-scale recommendation platforms that pool feedback across users\.

While cooperation across agents can significantly improve learning efficiency, it also introduces new challenges when agents experience heterogeneous rewards\. In many settings, different agents may observe systematically different reward distributions for the same action due to variations in preferences, local environments, or contextual factors\. This heterogeneity constitutes an additional source of uncertainty, beyond the inherent stochasticity of rewards\. Unlike the homogeneous setting, where information can be directly aggregated, heterogeneity requires agents to reconcile potentially conflicting observations when forming estimates\.

Another key dimension of multi\-agent systems is the distinction between centralized and decentralized learning\. In centralized settings, a global coordinator can aggregate observations from all agents, enabling full information sharing\. In contrast, decentralized systems lack such coordination, and agents must rely on local communication, introducing an additional layer of limited information\. This challenge is further amplified when communication is time\-varying\. While some works assume stationary networks with fixed connections, many real\-world systems exhibit nonstationary communication, where links between agents evolve over time\. A common approach to modeling such dynamics is through Erdos–Renyi \(ER\) random graphs, in which edges are formed probabilistically at each time step\.

Building on these challenges, an emerging direction of research considers multi\-objective multi\-armed bandits \(MO\-MAB\), where each action yields a vector\-valued reward rather than a single scalar outcome\. This formulation captures settings in which performance is inherently multi\-dimensional, and decisions must account for multiple criteria simultaneously\. By representing rewards as vectors, MO\-MAB provides a more realistic framework for modeling real\-world scenarios, where outcomes cannot be adequately summarized by a single metric\.

Building on the multi\-objective formulation, a more realistic setting arises when different agents assign different utilities to the components of the reward vector\. In such cases, each agent evaluates outcomes according to its own preferences, leading to potentially conflicting objectives across the system\. This introduces the need to balance these preferences in a principled and fair manner, rather than simply determining a globally optimal arm or optimizing cumulative regret\. Instead, it becomes natural to consider social welfare functions that aggregate individual utilities, providing a unified measure of system performance that accounts for both efficiency and fairness\.

These challenges highlight the need for new learning frameworks that account for both multi\-objective structure and fairness constraints, motivating the following research questions: \(1\) Can the multi\-agent multi\-armed bandit \(MA\-MAB\) framework be extended to the multi\-objective setting, incorporating heterogeneous rewards and time\-varying decentralized communication, while still enabling efficient learning? \(2\) How can we formalize fairness in the MO\-MA\-MAB setting through agent\-specific utilities and design algorithms that optimize a principled social welfare objective, such as Nash Social Welfare? We answer these questions affirmatively through the following contributions\.

### 1\.1Contributions

To address efficient learning in MO\-MA\-MAB, we develop a decentralized algorithm by extending thePareto UCB1framework introduced in\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\)to a setting with heterogeneous rewards and time\-varying decentralized communication\. We incorporate a gossip\-based communication protocol over Erdos–Renyi networks, as studied in\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)to enable information sharing across agents\. A key technical contribution is the design of an exploration radius that captures both sampling error and consensus error arising from decentralized estimation under heterogeneity, enabling the construction of reliable confidence sets for learning\.

To enable fairness\-aware efficent learning in MO\-MA\-MAB, we extend the notion of Nash Social Welfare \(NSW\) regret introduced in[hossain2021fair](https://arxiv.org/html/2605.06864#bib.bib10)to the multi\-objective multi\-agent setting\. We model agent\-specific preferences through preference vectors that scalarize vector\-valued rewards, so that each entry of the utility matrix—representing the mean reward of an arm for a given agent—is expressed as a linear combination of reward components weighted by that agent’s preferences\. Building on this formulation, we develop a decentralized algorithm by extending the UCB\-based approach in\([hossain2021fair,](https://arxiv.org/html/2605.06864#bib.bib10)\)and incorporating gossip\-based updates over Erdos–Renyi networks as in\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)\. Our method enables agents to optimize NSW with respect to the global average utility by leveraging consensus information, despite decentralized communication and heterogeneous observations\.

We provide theoretical guarantees for both proposed algorithms through regret analysis\. ForPareto UCB1 Gossip, we establish a logarithmic regret bound of order𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\), which implies an instance\-independent bound of𝒪​\(T\)\\mathcal\{O\}\(\\sqrt\{T\}\), matching the optimal rate for stochastic bandits\. In contrast, forSimulated NSW UCB Gossip, we derive a regret bound of order𝒪​\(T3/4\)\\mathcal\{O\}\(T^\{3/4\}\), reflecting the additional complexity introduced by optimizing the nonlinear Nash Social Welfare objective under heterogeneous rewards\. This gap highlights a fundamental tradeoff between efficiency and fairness, as enforcing fairness prevents the aggregation of observations across agents and slows learning\.

We complement our theoretical results with empirical evaluations against natural baselines\. In the multi\-objective setting, we compare against a multi\-agent extension ofPareto UCB1introduced in\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\)and a multi\-objective extension ofGossip Successive Eliminationdeveloped in\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\), demonstrating faster convergence and improved regret due to more efficient confidence bounds\. In the social choice setting, we compare against variants that remove either gossip communication or reward simulation, showing that both components are essential for achieving sublinear regret\. We review related work in Appendix[A\.1](https://arxiv.org/html/2605.06864#A1.SS1)\.

## 2Problem Formulation

The multi\-objective, multi\-agent, multi\-armed bandit problem featuresNNagents,KKarms,DDdimensional rewards, and a time horizonTT\. At timet∈\[T\]t\\in\[T\], each agenti∈\[N\]i\\in\[N\]pulls an armait∈\[K\]a\_\{i\}^\{t\}\\in\[K\]\. The rewards associated with agentiiarmkk,Xi,k​\(t\)∈\[0,1\]DX\_\{i,k\}\(t\)\\in\[0,1\]^\{D\}are i\.i\.d across timet∈\[T\]t\\in\[T\]and are sub\-Gaussian distributed with meanμi,k\\mu\_\{i,k\}\. We assume a heterogeneous setting whereμi,k≠μj,k\\mu\_\{i,k\}\\neq\\mu\_\{j,k\}fori≠ji\\neq j\. We introduceμk=1N​∑i=1Nμi,k\\mu\_\{k\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mu\_\{i,k\}as the centered mean for armkk\.

Our problem follows an decentralized communication model\. Specifically, we introduce an undirected base graph𝒢=\(V,E\)\\mathcal\{G\}=\(V,E\)whereV=\[N\]V=\[N\], the set of agents and fori,j∈\[N\]i,j\\in\[N\],\(i,j\)∈E\(i,j\)\\in Eif and only if agentiican communicate with agentjj\.𝒢\\mathcal\{G\}is assumed to be connected and may in certain instances be complete\. A random graph𝒢t\\mathcal\{G\}\_\{t\}restricts communication between agents at time stept∈\[T\]t\\in\[T\]\.𝒢t\\mathcal\{G\}\_\{t\}is generated according to the Erdos\-Renyi model by selecting edges from the base graph𝒢\\mathcal\{G\}with probabilitypp, a hyperparameter\. At timett, the graph𝒢t\\mathcal\{G\}\_\{t\}corresponds to a weight matrixWt∈ℝN×NW\_\{t\}\\in\\mathbb\{R\}^\{N\\times N\}\. We defineWtW\_\{t\}by its entries\[Wt\]i​j=\{1/Nif​j∈𝒩i​\(t\)1−\|𝒩i​\(t\)\|/Notherwise\[W\_\{t\}\]\_\{ij\}=\\begin\{cases\}\\nicefrac\{\{1\}\}\{\{N\}\}&\\text\{if \}j\\in\\mathcal\{N\}\_\{i\}\(t\)\\\\ 1\-\\nicefrac\{\{\\left\|\\mathcal\{N\}\_\{i\}\(t\)\\right\|\}\}\{\{N\}\}&\\text\{otherwise\}\\end\{cases\}\. In other words, agentiiassigns each of its neighbors1N\\frac\{1\}\{N\}of the weight and applies the rest of the mass to itself\. Note thatWtW\_\{t\}is row stochastic with spectral gap parameterρ=∑t𝔼​\[‖Wt−1N​𝟙𝟙⊤‖2\]<1\\rho=\\sum\_\{t\}\\mathbb\{E\}\[\\left\\lVert W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\\right\\rVert\_\{2\}\]<1\.

### 2\.1Multi\-Objective Pareto Setting

We extend cumulative expected regret depicted in\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)to MO\-MA\-MAB using Pareto optimality\. As discussed in\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\), for vectorsx,y∈ℝDx,y\\in\\mathbb\{R\}^\{D\},xxdominatesyyand we writex≻yx\\succ yif for alli∈\[D\]i\\in\[D\],xi≥yix\_\{i\}\\geq y\_\{i\}and there exists ani∈\[D\]i\\in\[D\]such thatxi\>yix\_\{i\}\>y\_\{i\}\. Theϵ\\epsilon\-distance between a vectorx∈ℝDx\\in\\mathbb\{R\}^\{D\}and a setSSof vectors with the sample dimensionality is given byDist​\(x,S\)=inf\{ϵ\>0:∄​y∈S​such that​y≻x\+ϵ\}\\text\{Dist\}\(x,S\)=\\inf\\\{\\epsilon\>0:\\nexists y\\in S\\text\{ such that \}y\\succ x\+\\epsilon\\\}\. In other words,ϵ\\epsilonis the smallest relaxation needed so that no vectory∈Sy\\in Sdominatesxx\. Similarly, a vectory∈Sy\\in Sis Pareto optimal if it is not dominated by another vector inSS\. We express global Pareto regret for MO\-MA\-MAB asRT=∑i=1N∑t=1TDist​\(μait,O\)R\_\{T\}=\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{Dist\}\(\\mu\_\{a\_\{i\}^\{t\}\},O\)whereμait\\mu\_\{a\_\{i\}^\{t\}\}is the centered arm mean for the arm selected by agentiiat timettandO=\{μk∗:∄​k∈\[K\]​such that​μk≻μk∗\}O=\\\{\\mu\_\{k^\{\*\}\}:\\nexists k\\in\[K\]\\text\{ such that \}\\mu\_\{k\}\\succ\\mu\_\{k^\{\*\}\}\\\}\. We refer to this set as the Pareto front of the centered arm means because it contains all Pareto optimal vectors\. In other words, the sub\-optimality gap for global Pareto regret is theϵ\\epsilon\-distance between the centered mean of the arm selected and the Pareto front\.

### 2\.2Nash Social Welfare Setting

A constant preference vectorwi∈ΔKw\_\{i\}\\in\\Delta\_\{K\}denotes the utility of agentiiwhereΔk\\Delta\_\{k\}refers to the probability simplex over the arm set\. When agentiipulls armkkat timett, it receives the scalar rewardwi⊤​Xi,k​\(t\)w\_\{i\}^\{\\top\}X\_\{i,k\}\(t\), the dot product between the vector reward and its utility\. We represent the scalar mean for agentiipulling armkkwith agentjj’s preferences,μi,j,k∗=wj⊤​μi,k\\mu\_\{i,j,k\}^\{\*\}=w\_\{j\}^\{\\top\}\\mu\_\{i,k\}\. The centered scalar mean for armkkwith agentjj’s preferences isμ¯j,k=1N​∑i=1Nμi,j,k∗\\bar\{\\mu\}\_\{j,k\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mu\_\{i,j,k\}^\{\*\}\.

Our regret formulation follows from the Nash Social Welfare function to develop fair algorithms for MO\-MA\-MAB\. Given a distribution over the arm setp∈ΔKp\\in\\Delta\_\{K\}and a utility matrixμ∈ℝN×K\\mu\\in\\mathbb\{R\}^\{N\\times K\}, Nash Social Welfare is given byNSW​\(p,μ\)=∏j=1N\(∑k=1Kpk⋅μj,k\)\\text\{NSW\}\(p,\\mu\)=\\prod\_\{j=1\}^\{N\}\\left\(\\sum\_\{k=1\}^\{K\}p\_\{k\}\\cdot\\mu\_\{j,k\}\\right\)Suppose that the optimal distribution under the centered scalar mean matrix isp∗=arg maxp∈ΔK​NSW​\(p,μ¯\)p^\{\*\}=\\text\{arg\\,max\}\_\{p\\in\\Delta\_\{K\}\}\\text\{NSW\}\(p,\\bar\{\\mu\}\)\. Then we define NSW regret asRT=∑t=1T∑i=1NNSW​\(p∗,μ¯\)−NSW​\(pit,μ¯\)R\_\{T\}=\\sum\_\{t=1\}^\{T\}\\sum\_\{i=1\}^\{N\}\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\-\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)The suboptimality gap for agentiiat timettis the difference between the NSW of the optimal distributionp∗p^\{\*\}under the centered scalar mean matrixμ¯\\bar\{\\mu\}and the estimated distributionpitp\_\{i\}^\{t\}under the centered scalar mean matrix\. NSW regret is calculated by summing the suboptimality gaps over agentsiiand timett\. The decision to adopt centered scalar means as the reference utility matrix parallels\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)\. We interpret reward heterogeneity as stochastic noise retaining the representation of conflicting utilities with different preference vectors\. Since communication is restricted, our regret formulation allows agents to settle at different estimated distributions at each time step\.

Our problem setting extends similar works that study MA\-MAB using NSW regret\.\([hossain2021fair,](https://arxiv.org/html/2605.06864#bib.bib10)\)and\([jones2023efficient,](https://arxiv.org/html/2605.06864#bib.bib13)\), considers a utility matrix specifying the rewards for each agent under a homogeneous, centralized setting\.\([zhang2024no,](https://arxiv.org/html/2605.06864#bib.bib30)\)generalizes the problem to non\-stationary utility matrices\. Our work extends the problem by incorporating multi\-dimensional rewards\. Specifically, we build on\([hossain2021fair,](https://arxiv.org/html/2605.06864#bib.bib10)\)to the case where each element in the utility matrix is a linear combination of the dimensions of the reward weighted by a preference vector\. Our work also broadens[hossain2021fair](https://arxiv.org/html/2605.06864#bib.bib10)to the setting where rewards are heterogeneous and communication is decentralized\.

## 3Pareto UCB1 Gossip

To enable efficient learning in the multi\-objective Pareto setting, we propose an algorithm that extendsPareto UCB1\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\)to the multi\-agent regime by integrating gossip\-based sharing, as inSuccessive Gossip Elimination\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)\. To address the challenges introduced by heterogeneous reward vectors and decentralized communication, we develop an exploration term that captures both sampling and consensus errors\.

### 3\.1Methodology

At each time step, every agent maintains local averages of arm rewards together with a set of global averages that are updated through gossip\-based communication\. The algorithm begins with an initialization phase in which each arm is pulled once to obtain initial samples\. After this, each agent constructs upper confidence bounds for all arms using its global averages and a confidence radius which accounts for both sampling uncertainty and consensus error\. Using the upper confidence bounds, each agent identifies the Pareto front and selects an arm uniformly at random from this set\. Upon receiving a reward, the agent updates its local empirical mean for the selected arm and increments the corresponding counter\. Finally, agents perform a gossip update, mixing their current estimates with those of their neighbors according to the time\-varying communication matrix, while incorporating the latest local updates\. This iterative process enables agents to progressively refine their estimates by combining local observations with information propagated through the network, leading to improved identification of Pareto optimal arms over time\. A complete description is presented in Algorithm[1](https://arxiv.org/html/2605.06864#algorithm1)\.

1

2Input:total time horizon

TT, set of agents

\[N\]\[N\], set of arms

\[K\]\[K\], dimensions

\[D\]\[D\], base graph

𝒢\\mathcal\{G\}, link probability

pp;

3

4Initialization:For each agent

i∈\[N\]i\\in\[N\]and arm

k∈\[K\]k\\in\[K\], set

Ti,k​\(0\)=0T\_\{i,k\}\(0\)=0,

μ^i,k​\(0\)=0\\hat\{\\mu\}\_\{i,k\}\(0\)=0, and

zi,k​\(1\)=0z\_\{i,k\}\(1\)=0;

5

6for*t=1,…,Tt=1,\\dots,T*do

7for*i=1,…,Ni=1,\\dots,N*do

8if*t=1,…,Kt=1,\\dots,K*then

9

ait←ta\_\{i\}^\{t\}\\leftarrow t;

10

11else

12

UCBi,k​\(t\)←zi,k​\(t\)\+ci,k​\(t\)\\text\{UCB\}\_\{i,k\}\(t\)\\leftarrow z\_\{i,k\}\(t\)\+c\_\{i,k\}\(t\), where

ci,k​\(t\)=8​log⁡\(t​D​\|𝒜∗\|4\)/Ti,k​\(t\)\+2​n/1−pc\_\{i,k\}\(t\)=\\sqrt\{\\nicefrac\{\{8\\log\\left\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\right\)\}\}\{\{T\_\{i,k\}\(t\)\}\}\}\+\\nicefrac\{\{2\\sqrt\{n\}\}\}\{\{1\-\\sqrt\{p\}\}\};

13

14

Sit=\{k∗∈\[K\]:∄​k∈\[K\]​such thatUCBi,k​\(t\)≻UCBi,k∗​\(t\)\}S\_\{i\}^\{t\}=\\\{k^\{\*\}\\in\[K\]:\\nexists k\\in\[K\]\\text\{ such that \}\\text\{UCB\}\_\{i,k\}\(t\)\\succ\\text\{UCB\}\_\{i,k^\{\*\}\}\(t\)\\\};

15

16Sample

aita\_\{i\}^\{t\}uniformly from

SitS\_\{i\}^\{t\};

17

18Observe

Xi,ait​\(t\)∼μi,aitX\_\{i,a\_\{i\}^\{t\}\}\(t\)\\sim\\mu\_\{i,a\_\{i\}^\{t\}\};

Ti,ait​\(t\)←Ti,ait​\(t−1\)\+1T\_\{i,a\_\{i\}^\{t\}\}\(t\)\\leftarrow T\_\{i,a\_\{i\}^\{t\}\}\(t\-1\)\+1;

19

20

μ^i,ait​\(t\)←Ti,ait​\(t−1\)​μ^i,ait​\(t−1\)\+Xi,ait​\(t\)/Ti,ait​\(t\)\\hat\{\\mu\}\_\{i,a\_\{i\}^\{t\}\}\(t\)\\leftarrow\\nicefrac\{\{T\_\{i,a\_\{i\}^\{t\}\}\(t\-1\)\\hat\{\\mu\}\_\{i,a\_\{i\}^\{t\}\}\(t\-1\)\+X\_\{i,a\_\{i\}^\{t\}\}\(t\)\}\}\{\{T\_\{i,a\_\{i\}^\{t\}\}\(t\)\}\};

21

22for*k=1,…,Kk=1,\\dots,K*do

23

zi,k​\(t\+1\)←∑j=1N\[Wt\]i​j​zj,k​\(t\)\+μ^i,k​\(t\)−μ^i,k​\(t−1\)z\_\{i,k\}\(t\+1\)\\leftarrow\\sum\_\{j=1\}^\{N\}\[W\_\{t\}\]\_\{ij\}z\_\{j,k\}\(t\)\+\\hat\{\\mu\}\_\{i,k\}\(t\)\-\\hat\{\\mu\}\_\{i,k\}\(t\-1\);

24

Algorithm 1Pareto UCB1 Gossip
### 3\.2Analysis

We analyze the regret ofPareto UCB1 Gossipby extending thePareto UCB1framework to a decentralized, heterogeneous setting\. The main challenge is to control how statistical uncertainty and imperfect information mixing jointly affect the confidence bounds used for arm selection\. The comprehensive proof is provided in Appendix[A\.2](https://arxiv.org/html/2605.06864#A1.SS2)\.

#### 3\.2\.1Key Decomposition and Error Bounds

We havezi,k​\(t\)z\_\{i,k\}\(t\)as the global average of agentiifor armkk\. We decompose the deviation between the global average and the centered arm mean aszi,k​\(t\)−μk=\(zi,k​\(t\)−μ~k​\(t\)\)\+\(μ~k​\(t\)−μk\),z\_\{i,k\}\(t\)\-\\mu\_\{k\}=\(z\_\{i,k\}\(t\)\-\\tilde\{\\mu\}\_\{k\}\(t\)\)\+\(\\tilde\{\\mu\}\_\{k\}\(t\)\-\\mu\_\{k\}\),whereμ~k​\(t\)=1N​∑i=1Nμ^i,k\\tilde\{\\mu\}\_\{k\}\(t\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,k\}is the average of local empirical means\. The second term \(sampling error\) concentrates via Chernoff bounds, yielding exponential decay insk​\(t\)=mini⁡Ti,k​\(t\)s\_\{k\}\(t\)=\\min\_\{i\}T\_\{i,k\}\(t\)\. The first term \(consensus error\) is controlled through the contraction of the gossip updates, leading to a uniform bound of orderN1−ρ\\frac\{\\sqrt\{N\}\}\{1\-\\sqrt\{\\rho\}\}with high probability\. Combining both bounds givesℙ​\[zi,k​\(t\)⊀μk\+ϵ​𝟏\]≤D​exp⁡\(−12​sk​\(t\)​ϵ2\)\+N2t\.\\mathbb\{P\}\[z\_\{i,k\}\(t\)\\nprec\\mu\_\{k\}\+\\epsilon\\mathbf\{1\}\]\\leq D\\exp\\left\(\-\\tfrac\{1\}\{2\}s\_\{k\}\(t\)\\epsilon^\{2\}\\right\)\+\\frac\{N^\{2\}\}\{t\}\.

A key novelty is the resulting exploration radius

ci,k​\(t\)=8​log⁡\(t​D​\|𝒜∗\|4\)/Ti,k​\(t\)\+2​N/1−p,c\_\{i,k\}\(t\)=\\sqrt\{\\nicefrac\{\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\}\{\{T\_\{i,k\}\(t\)\}\}\}\+\\nicefrac\{\{2\\sqrt\{N\}\}\}\{\{1\-\\sqrt\{p\}\}\},which cleanly separates sampling and consensus effects\. In contrast to prior gossip\-based approaches where these terms are coupled, the sampling component retains the optimal𝒪​\(log⁡T/Ti,k​\(t\)\)\\mathcal\{O\}\(\\sqrt\{\\log T/T\_\{i,k\}\(t\)\}\)decay, while the consensus error appears only as an additive constant\. This distinction is critical for ensuring that confidence intervals shrink at the correct rate\.

#### 3\.2\.2Regret Bound

We now outline how the regret bound is obtained\. The main objective is to bound the expected number of times a suboptimal armk∉𝒜∗k\\notin\\mathcal\{A\}^\{\*\}is selected by an agentii\. After a warm\-up period, a suboptimal arm can only be selected if its upper confidence bound is not dominated by that of some Pareto optimal armh∈𝒜∗h\\in\\mathcal\{A\}^\{\*\}\. This implies that at least one of the following failure events occurs:

\(i\)zi,h\(t\)⊁μh−ci,h\(t\)𝟏;\(ii\)zi,k\(t\)⊀μk\+ci,k\(t\)𝟏;\(iii\)μh⊁μk\+2ci,k\(t\)𝟏\.\\text\{\(i\)\}\\;z\_\{i,h\}\(t\)\\nsucc\\mu\_\{h\}\-c\_\{i,h\}\(t\)\\mathbf\{1\}\\quad;\\quad\\text\{\(ii\)\}\\;z\_\{i,k\}\(t\)\\nprec\\mu\_\{k\}\+c\_\{i,k\}\(t\)\\mathbf\{1\}\\quad;\\quad\\text\{\(iii\)\}\\;\\mu\_\{h\}\\nsucc\\mu\_\{k\}\+2c\_\{i,k\}\(t\)\\mathbf\{1\}\.
The exploration radius governs these events in two ways\. First, it determines the warm\-up period: onceTi,k​\(t\)T\_\{i,k\}\(t\)is sufficiently large so that2​ci,k​\(t\)≤Δk2c\_\{i,k\}\(t\)\\leq\\Delta\_\{k\}, event \(iii\) cannot occur\. Second, events \(i\) and \(ii\) are precisely the deviation events controlled in the previous subsection, and thus occur with probability at most𝒪​\(t−4\)\+𝒪​\(N2/t\)\\mathcal\{O\}\(t^\{\-4\}\)\+\\mathcal\{O\}\(N^\{2\}/t\)\.

Combining these bounds yields a logarithmic upper bound on the expected number of pulls of each suboptimal arm\. Summing over suboptimal arms and agents gives the global Pareto regret\.

###### Theorem 1\(Global Pareto Regret ofPareto UCB1 Gossip\)\.

Let𝒜∗\\mathcal\{A\}^\{\*\}denote the Pareto optimal set andΔk\\Delta\_\{k\}the Pareto gap of armkk\. ThenRegT​\(π\)≤N​∑k∉𝒜∗32​log⁡\(T​D​\|𝒜∗\|4\)Δk\+N​\(1\+π445\+2​\|𝒜∗\|​N2​\(log⁡T\+1\)\)​∑k∈𝒜∗Δk\.\\mathrm\{Reg\}\_\{T\}\(\\pi\)\\leq N\\sum\_\{k\\notin\\mathcal\{A\}^\{\*\}\}\\frac\{32\\log\(T\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{\\Delta\_\{k\}\}\+N\\left\(1\+\\frac\{\\pi^\{4\}\}\{45\}\+2\\left\|\\mathcal\{A\}^\{\*\}\\right\|N^\{2\}\(\\log T\+1\)\\right\)\\sum\_\{k\\in\\mathcal\{A\}^\{\*\}\}\\Delta\_\{k\}\.

Since the regret admits a logarithmic, gap\-dependent bound of order𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\), standard arguments imply a corresponding gap\-independent bound of order𝒪​\(T\)\\mathcal\{O\}\(\\sqrt\{T\}\)\.

#### 3\.2\.3Discussion and Comparison

The leading term scales as𝒪​\(log⁡T\)\\mathcal\{O\}\(\\log T\)with standard gap dependence, matchingPareto UCB1\. The additional𝒪​\(N3​log⁡T\)\\mathcal\{O\}\(N^\{3\}\\log T\)contribution reflects the cost of decentralized communication through consensus error and diminishes with improved connectivity\.

Compared to\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\), we retain the centralized regret structure while extending it to decentralized, heterogeneous multi\-agent settings\. Compared to gossip\-based bandits such as\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\), the key improvement lies in the exploration radius: by separating sampling and consensus errors, it preserves the optimal𝒪​\(log⁡T/Ti,k​\(t\)\)\\mathcal\{O\}\(\\sqrt\{\\log T/T\_\{i,k\}\(t\)\}\)shrinkage while incorporating consensus effects only additively\. This leads to faster elimination of suboptimal arms, with decentralization affecting only lower\-order terms, consistent with empirical observations\.

## 4Simulated NSW UCB Gossip

To optimize learning under fairness constraints in the Nash Social Welfare setting, we develop an algorithm that builds on the UCB\-based approach in\([hossain2021fair,](https://arxiv.org/html/2605.06864#bib.bib10)\)and incorporates gossip\-based updates as inSuccessive Gossip Elimination\. Our method leverages shared preference vectors among neighboring agents by constructing simulated rewards from the perspective of other agents\.

### 4\.1Methodology

1

2Input:total time horizon

TT, set of agents

\[N\]\[N\], set of arms

\[K\]\[K\], dimensions

\[D\]\[D\], preference vectors

wiw\_\{i\}, base graph

𝒢\\mathcal\{G\}, link probability

pp, explore factor

αt\\alpha^\{t\};

3

4Initialization:For each agent pair

i,j∈\[N\]i,j\\in\[N\]and arm

k∈\[K\]k\\in\[K\], set

Ti,j,k​\(0\)=0T\_\{i,j,k\}\(0\)=0,

μ^i,j,k​\(0\)=0\\hat\{\\mu\}\_\{i,j,k\}\(0\)=0, and

zi,j,k​\(1\)=0z\_\{i,j,k\}\(1\)=0;

5

6for*t=1,…,Tt=1,\\dots,T*do

7for*i=1,…,Ni=1,\\dots,N*do

8if*t=1,…,Kt=1,\\dots,K*then

9

pit←etp\_\{i\}^\{t\}\\leftarrow e\_\{t\};

10

11else

12

pit←arg maxp∈ΔK​NSW​\(p,zi​\(t\)\)\+αt​∑k=1Kpk​rktp\_\{i\}^\{t\}\\leftarrow\\text\{arg\\,max\}\_\{p\\in\\Delta\_\{K\}\}\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\+\\alpha^\{t\}\\sum\_\{k=1\}^\{K\}p\_\{k\}r\_\{k\}^\{t\}, where

rkt=log⁡\(N​K​t\)/Ti,j,k​\(t\)r\_\{k\}^\{t\}=\\sqrt\{\\nicefrac\{\{\\log\(NKt\)\}\}\{\{T\_\{i,j,k\}\(t\)\}\}\};

13

14Sample

ait∼pita\_\{i\}^\{t\}\\sim p\_\{i\}^\{t\}and observe

Xi,ait​\(t\)X\_\{i,a\_\{i\}^\{t\}\}\(t\);

15

16for*j∈𝒩i​\(t\)j\\in\\mathcal\{N\}\_\{i\}\(t\)*do

17

si,j​\(t\)←wj⊤​Xi,ait​\(t\)s\_\{i,j\}\(t\)\\leftarrow w\_\{j\}^\{\\top\}X\_\{i,a\_\{i\}^\{t\}\}\(t\);

Ti,j,ait​\(t\)←Ti,j,ait​\(t\)\+1T\_\{i,j,a\_\{i\}^\{t\}\}\(t\)\\leftarrow T\_\{i,j,a\_\{i\}^\{t\}\}\(t\)\+1;

18

19

μ^i,j,ait​\(t\)←Ti,j,ait​\(t−1\)​μ^i,j,ait​\(t−1\)\+si,j​\(t\)/Ti,j,ait​\(t\)\\hat\{\\mu\}\_\{i,j,a\_\{i\}^\{t\}\}\(t\)\\leftarrow\\nicefrac\{\{T\_\{i,j,a\_\{i\}^\{t\}\}\(t\-1\)\\hat\{\\mu\}\_\{i,j,a\_\{i\}^\{t\}\}\(t\-1\)\+s\_\{i,j\}\(t\)\}\}\{\{T\_\{i,j,a\_\{i\}^\{t\}\}\(t\)\}\};

20

21for*j=1,…,Nj=1,\\dots,N*do

22for*k=1,…,Kk=1,\\dots,K*do

23

zi,j,k​\(t\+1\)←∑l=1N\[Wt\]i​l​zl,j,k​\(t\)\+μ^i,j,k​\(t\)−μ^i,j,k​\(t\)z\_\{i,j,k\}\(t\+1\)\\leftarrow\\sum\_\{l=1\}^\{N\}\[W\_\{t\}\]\_\{il\}z\_\{l,j,k\}\(t\)\+\\hat\{\\mu\}\_\{i,j,k\}\(t\)\-\\hat\{\\mu\}\_\{i,j,k\}\(t\);

24

Algorithm 2Simulated NSW UCB GossipAlgorithm[2](https://arxiv.org/html/2605.06864#algorithm2)can be understood per agentiiat a specific timett\. Each round consists of three stages: choosing an arm, observing a rewards, and updating estimators\. In the arm choosing period, during the firstKKtime steps the agent sets its distribution to thettth standard basis vector\. This conforms to the exploration period in traditional UCB algorithms where every arm is pulled once\. Beyond the firstKKrounds, the agent optimizes the objectivearg maxp∈ΔK​NSW​\(p,zi​\(t\)\)\+αt​∑k=1Kpk⋅rkt​where​rkt=log⁡\(N​K​t\)/Ti,j,k​\(t\)\\text\{arg\\,max\}\_\{p\\in\\Delta\_\{K\}\}\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\+\\alpha^\{t\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\cdot r\_\{k\}^\{t\}\\text\{ where \}r\_\{k\}^\{t\}=\\sqrt\{\\nicefrac\{\{\\log\(NKt\)\}\}\{\{T\_\{i,j,k\}\(t\)\}\}\}with respect to its global averages\. The first term exploits the fairest distribution over the arm set using NSW\. The second term represents an explore term weighted by a exploration factorαt\\alpha^\{t\}\. Each termkkin the sum incentivizes or decentivizes the agent to assign probability mass onpkp\_\{k\}givenrktr\_\{k\}^\{t\}which is inversely proportional to the counterTi,j,k​\(t\)T\_\{i,j,k\}\(t\)\.

When observing a reward, the agent samples an arm from its estimated distribution\. Then, the agent pulls on the arm and obtains a scalar reward given by the dot product of its preference vector and the vector reward\. The agent also receives\|𝒩i​\(t\)\|\\left\|\\mathcal\{N\}\_\{i\}\(t\)\\right\|simulated rewards arising from the dot product between each neighbor’s preference vector and the observed reward\.

During the estimator update phase, agentiistores both a local average matrixμ^i∈ℝN×K\\hat\{\\mu\}\_\{i\}\\in\\mathbb\{R\}^\{N\\times K\}and a global average matrixzi∈ℝN×Kz\_\{i\}\\in\\mathbb\{R\}^\{N\\times K\}for the value of armkkunder agentjj’s preferences\. The local average represents a Monte\-Carlo estimate over the locally observed scalar rewards\. The global average is computed by taking weighted averages of the local averages\. For the local average matrix, the agent updates the Monte\-Carlo estimates for the arm that it selected under its own preferences and its neighbors preferences\. For clarity, consider the local average as aN×N×KN\\times N\\times Ktensor\.

\[\[μ^1,1,1​\(t\)⋯μ^1,1,K​\(t\)⋮⋮μ^1,N,1​\(t\)⋯μ^1,N,K​\(t\)\]\[μ^2,1,1​\(t\)⋯μ^2,1,K​\(t\)⋮⋮μ^2,N,1​\(t\)⋯μ^2,N,K​\(t\)\]⋯\[μ^N,1,1​\(t\)⋯μ^N,1,K​\(t\)⋮⋮μ^N,N,1​\(t\)⋯μ^N,N,K​\(t\)\]\]\\begin\{bmatrix\}\\begin\{bmatrix\}\\hat\{\\mu\}\_\{1,1,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{1,1,K\}\(t\)\\\\ \\vdots&&\\vdots\\\\ \\hat\{\\mu\}\_\{1,N,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{1,N,K\}\(t\)\\end\{bmatrix\}&\\begin\{bmatrix\}\\hat\{\\mu\}\_\{2,1,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{2,1,K\}\(t\)\\\\ \\vdots&&\\vdots\\\\ \\hat\{\\mu\}\_\{2,N,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{2,N,K\}\(t\)\\end\{bmatrix\}&\\cdots&\\begin\{bmatrix\}\\hat\{\\mu\}\_\{N,1,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{N,1,K\}\(t\)\\\\ \\vdots&&\\vdots\\\\ \\hat\{\\mu\}\_\{N,N,1\}\(t\)&\\cdots&\\hat\{\\mu\}\_\{N,N,K\}\(t\)\\end\{bmatrix\}\\end\{bmatrix\}In this way, the agent can only update select entries in the row corresponding to the arm it selected that round\. In the global estimate for armkkunder agentjj’s preferences, agentiiaverages the global averages of all other agents weighted by the theiith row ofWtW\_\{t\}\. Finally, the agent adds in any local update contributions\. Again, it is helpful to view the global average as aN×N×KN\\times N\\times Ktensor\. The resulting global average matrix for agentiiis a linear combination of the sub\-matrices in the tensor weighted by theiith row ofWtW^\{t\}\. In he end, we add local average matrix update at timett\.

### 4\.2Analysis

We analyze the cumulative Nash Social Welfare \(NSW\) regret ofSimulated NSW UCB Gossip\. Our analysis decomposes the sources of error arising from stochastic rewards and decentralized communication, and shows how these propagate through the nonlinear NSW objective\. The comprehensive proof is provided in Appendix[A\.3](https://arxiv.org/html/2605.06864#A1.SS3)\.

#### 4\.2\.1Key Decomposition and Error Bounds

The proof begins by decomposing the deviation between the global estimates and the centered mean aszi,j,k​\(t\)−μ¯j,k=\(zi,j,k​\(t\)−z¯j,k​\(t\)\)\+\(z¯j,k​\(t\)−μ¯j,k\),z\_\{i,j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}=\(z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\)\+\(\\bar\{z\}\_\{j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\),which separates the error into a consensus term induced by decentralized communication and a sampling term arising from stochastic rewards\. A key observation is that the network average tracks the empirical mean,z¯j,k​\(t\)=1N​∑i=1Nμ^i,j,k​\(t−1\),\\bar\{z\}\_\{j,k\}\(t\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\),so thatz¯j,k​\(t\)\\bar\{z\}\_\{j,k\}\(t\)is an unbiased estimator ofμ¯j,k\\bar\{\\mu\}\_\{j,k\}\. The sampling error is controlled via concentration of the local estimators together with a coupling between off\-diagonal and diagonal counts under the Erdos–Renyi communication model, yielding a bound of order1p​log⁡\(N​K​t\)Ti,i,k​\(t\)\\frac\{1\}\{\\sqrt\{p\}\}\\sqrt\{\\frac\{\\log\(NKt\)\}\{T\_\{i,i,k\}\(t\)\}\}\. The consensus error follows from the contraction of the gossip process and accumulates geometrically with rateρ\\rho\.

#### 4\.2\.2Regret Bound

To connect estimation error to regret, we exploit a telescoping argument that converts the multiplicative NSW objective into an additive bound:\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|≤∑j=1N∑k=1Kpk​\|zi,j,k​\(t\)−μ¯j,k\|\.\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|\.This yields a high\-probability event under which the discrepancy between the true and estimated objectives is controlled by a UCB\-style exploration term aligned with the algorithm, together with lower\-order corrections\. Under this event, we compare the optimal distributionp∗p^\{\*\}with the chosen distributionpitp\_\{i\}^\{t\}and reduce regret to the accumulation of sampling and consensus errors over time\.

###### Theorem 2\(NSW Regret ofSimulated NSW UCB Gossip\)\.

With probability at least1−𝒪​\(\(N2​K​T\)−2\)1\-\\mathcal\{O\}\(\(N^\{2\}KT\)^\{\-2\}\), the cumulative NSW regret satisfiesRT≤𝒪​\(N2​Kp​log⁡\(N​K​T\)⋅T3/4\)\+𝒪​\(N2​K​log3/2⁡T\)\+𝒪​\(N31−ρ​log⁡T\)\.R\_\{T\}\\leq\\mathcal\{O\}\\left\(\\frac\{N^\{2\}K\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\cdot T^\{3/4\}\\right\)\+\\mathcal\{O\}\\left\(N^\{2\}K\\log^\{3/2\}T\\right\)\+\\mathcal\{O\}\\left\(\\frac\{N^\{3\}\}\{1\-\\rho\}\\log T\\right\)\.

The leading term scales as𝒪​\(N2​K​T3/4/p\)\\mathcal\{O\}\(N^\{2\}KT^\{3/4\}/\\sqrt\{p\}\), while the remaining terms are lower\-order contributions due to limited exploration and decentralized communication\.

#### 4\.2\.3Discussion and Comparison

The dominant contribution to regret is the sampling term, which scales as𝒪​\(N2​Kp​T3/4\)\\mathcal\{O\}\(\\frac\{N^\{2\}K\}\{\\sqrt\{p\}\}T^\{3/4\}\)\. TheT3/4T^\{3/4\}rate reflects the difficulty of optimizing the nonlinear NSW objective, while the1p\\frac\{1\}\{\\sqrt\{p\}\}dependence captures the reduction in effective sample size due to sparse communication\. The remaining terms are lower order: the𝒪​\(N2​K​log3/2⁡T\)\\mathcal\{O\}\(N^\{2\}K\\log^\{3/2\}T\)term corresponds to a burn\-in phase, and the𝒪​\(N31−ρ​log⁡T\)\\mathcal\{O\}\(\\frac\{N^\{3\}\}\{1\-\\rho\}\\log T\)term reflects the cost of decentralized consensus, improving with faster mixing\.

The𝒪​\(T3/4\)\\mathcal\{O\}\(T^\{3/4\}\)dependence in our regret bound is driven by a fundamental sampling term∑t=1T∑k=1Kpi,kt/Ti,i,k​\(t\),\\sum\_\{t=1\}^\{T\}\\sum\_\{k=1\}^\{K\}\\nicefrac\{\{p\_\{i,k\}^\{t\}\}\}\{\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\},which cannot be improved to yield aT\\sqrt\{T\}rate under heterogeneous rewards\. In contrast, UCB\-based MA\-MAB algorithms\([hossain2021fair,](https://arxiv.org/html/2605.06864#bib.bib10);[jones2023efficient,](https://arxiv.org/html/2605.06864#bib.bib13)\)for NSW regret in homogeneous, centralized settings achieve𝒪​\(T\)\\mathcal\{O\}\(\\sqrt\{T\}\)regret by effectively pooling observations across agents, allowing counters to scale with the total number of samples\. In our setting, however, becauseμi,k≠μj,k\\mu\_\{i,k\}\\neq\\mu\_\{j,k\}, observations cannot be aggregated across agents, and each agent must rely on its own diagonal countersTi,i,k​\(t\)T\_\{i,i,k\}\(t\)to estimate arm values\. This prevents the effective sample size from scaling withNNand slows the growth ofTi,i,k​\(t\)T\_\{i,i,k\}\(t\)along frequently sampled arms\. Consequently, even under optimal allocation, the cumulative contribution of the inverse\-square\-root term scales asT3/4T^\{3/4\}up to logarithmic factors, making this rate unavoidable in our setting\.

This behavior parallels non\-stationary bandit problems, where past observations cannot be fully reused and similarT3/4T^\{3/4\}regret rates arise\. For instance, sliding\-window and restart\-based UCB methods achieve𝒪​\(T3/4\)\\mathcal\{O\}\(T^\{3/4\}\)regret in abruptly changing environments\([garivier2011upper,](https://arxiv.org/html/2605.06864#bib.bib7)\), and variation\-budget approaches yield comparable rates when the amount of non\-stationarity is large or unknown\([besbes2014stochastic,](https://arxiv.org/html/2605.06864#bib.bib1)\)\. In both cases, limited sample reuse constrains learning in much the same way as heterogeneity does here\. Finally, while our problem\-dependent analysis yields a𝒪​\(T3/4\)\\mathcal\{O\}\(T^\{3/4\}\)regret bound, this stands in contrast to the instance\-free𝒪​\(T\)\\mathcal\{O\}\(\\sqrt\{T\}\)guarantee achieved by the algorithm in the previous section; this gap reflects the inherent tradeoff required to enforce fairness through the Nash Social Welfare objective\.

## 5Experiments

The primary hyperparameters for the simulation are the number of agentsNN, armsKK, and the dimensionsdd\. The environment consists of preference vectors for each agent and distributions for each arm\. Each preference vectorwiw\_\{i\}is drawn from a Dirichlet distribution with concentration parameterα=𝟏N\\mathbf\{\\alpha\}=\\mathbf\{1\}\_\{N\}\. It follows thatwiw\_\{i\}is drawn uniformly from the probability simplex over the arm set\. We simulate each arm distribution as a Bernoulli trial\. To generate arm means, we sample base meansμk,dB∼Uniform​\(0\.2,0\.8\)\\mu\_\{k,d\}^\{B\}\\sim\\text\{Uniform\}\(0\.2,0\.8\)for every armkkand dimensiondd\. We add heterogeneity by perturbing these base means for each agent\. For each agentii,μi,k,d=μk,dB\+pi,k,d\\mu\_\{i,k,d\}=\\mu\_\{k,d\}^\{B\}\+p\_\{i,k,d\}wherepi,k,d∼Uniform​\(−het\_scale,het\_scale\)p\_\{i,k,d\}\\sim\\text\{Uniform\}\(\-\\verb\|het\_scale\|,\\verb\|het\_scale\|\)\.`het\_scale`represents an additional hyperparameter in the experiment\. We clipμi,k,d\\mu\_\{i,k,d\}to the range\[0\.05,0\.95\]\[0\.05,0\.95\]so that the arm means lie between0and11\. The base graph𝒢\\mathcal\{G\}is complete and we determine𝒢t\\mathcal\{G\}\_\{t\}using the ER model with parameterpp\.

### 5\.1Pareto UCB1 Gossip

We compare the performance ofPareto UCB1 Gossipagainst two baselines\. The first baseline extendsPareto UCB1described in\([drugan2013designing,](https://arxiv.org/html/2605.06864#bib.bib5)\)to the multi\-agent case by takingNNindependent instances\. The second baseline extendsGossip Successive Eliminationintroduced in\([liu2025distributed,](https://arxiv.org/html/2605.06864#bib.bib16)\)to the multi\-objective setting\. As inGossip Successive Elimination, agentiiselects the arm in the active set with the smallest counter value\. To account for vector rewards, our local and global averages are 3D tensors inℝN×K×D\\mathbb\{R\}^\{N\\times K\\times D\}\. Local updates are made element\-wise and global averages for agentiiarmkkare computed by taking linear combinations of vectors rewards for armkkweighted by theiith row ofWtW\_\{t\}\. In order to eliminate arms from the active set, we compute confidence intervals by calculating half\-widths\. We obtain upper and lower bounds by combining these half\-widths to the global averages element\-wise\. Analogous toGossip Successive Elimination, we eliminate armkkif its upper bound is dominated by the Pareto front constructed by all lower bounds for agentii\.

![[Uncaptioned image]](https://arxiv.org/html/2605.06864v1/figures/pareto_experiment_regret_cropped.png)In the experiment, we setN=8N=8,K=8K=8,D=3D=3, andT=150000T=150000\. We set the graph connectivityp=0\.8p=0\.8and`het\_scale=0\.2`\. We perform1010trials, each corresponding to an independent environment with new arm means and connectivity graphs\. For each trial, the algorithms run in the same environment but use different random number stream during the experiment when selecting an arm or sampling a reward\. We graph the mean global Pareto regret along with confidence intervals set to one quarter of the standard deviation\. In the legend,`pareto\_ucb\_gossip`refers toPareto\-UCB1 Gossip,`pareto\_ucb`corresponds to baseline11, and`pareto\_gossip`refers to baseline22\. Qualitatively, we observe that`pareto\_gossip`experiences a longer burn\-in time due to confidence intervals converging slowly\. On the other hand, we showed that the exploration term inPareto\-UCB1 Gossipconverges on the order of𝒪​\(log⁡T/Ti,k​\(t\)\)\\mathcal\{O\}\(\\sqrt\{\\log T/T\_\{i,k\}\(t\)\}\)\. Finally,`pareto\_ucb`does not grow sub\-linearly as the local averages are not unbiased estimators of the centered arm means\.

### 5\.2Simulated NSW UCB Gossip

We analyze the performance ofSimulated NSW UCB Gossipagainst two baselines\. The first baseline`no\_gossip`follows the proposed algorithm but does not engage in gossip sharing\. Instead, each agent uses its local average matrix to optimize NSW regret for arm selection\. The local average matrix can still be computed as agents retain the ability to share preference vectors and conduct simulations using their own observations\. The second baseline, referred to as`no\_sim`, mirrors the proposed algorithm without simulated rewards\. Agents use the global average matrix to determine the arm distribution for each round\. In the absence of reward simulation, agentiican only compute theiith row of its local average matrix\. Agents can populate their entire global average matrix via gossip\.

In this experiment, we considerN=4N=4agents,K=5K=5arms, feature dimensionD=2D=2, and horizonT=1500T=1500\. The communication graph is generated with connectivity parameterp=0\.5p=0\.5, and`het\_scale=0\.2`\. We run 15 independent trials, each corresponding to a newly sampled environment with fresh arm means\. Within each trial, all algorithms share the same environment but use independent randomness for graph generation, arm selection, and reward sampling\. We report the mean NSW regret with confidence intervals given by one quarter of the standard deviation\.

![[Uncaptioned image]](https://arxiv.org/html/2605.06864v1/figures/fairness_experiment_cropped.png)

We set the time horizon to15001500times steps as the proposed algorithm had already converged for most trials\. Empirical results suggest that`no\_gossip`and`no\_sim`fail to exhibit sublinear growth\. This observation is justified, as neither baseline produces an unbiased estimator of the centered means\. In`no\_gossip`, each agent computes local averages using only samples from its own reward distributions\. In`no\_sim`, agentiireceives global averages for agentjjcomputed with agentjj’s reward distributions\.

## References

- \[1\]O\. Besbes, Y\. Gur, and A\. Zeevi\.Stochastic multi\-armed\-bandit problem with non\-stationary rewards\.Advances in neural information processing systems, 27, 2014\.
- \[2\]C\. Bone and S\. Dragićević\.Gis and intelligent agents for multiobjective natural resource allocation: A reinforcement learning approach\.Transactions in GIS, 13\(3\):253–272, 2009\.
- \[3\]R\. Busa\-Fekete, B\. Szörényi, P\. Weng, and S\. Mannor\.Multi\-objective bandits: Optimizing the generalized gini index\.InInternational Conference on Machine Learning, pages 625–634\. PMLR, 2017\.
- \[4\]F\. M\. Delle Fave, R\. Stranders, A\. Rogers, and N\. Jennings\.Bounded decentralised coordination over multiple objectives\.2011\.
- \[5\]M\. M\. Drugan and A\. Nowe\.Designing multi\-objective multi\-armed bandits algorithms: A study\.InThe 2013 international joint conference on neural networks \(IJCNN\), pages 1–8\. IEEE, 2013\.
- \[6\]M\. M\. Drugan, A\. Nowé, and B\. Manderick\.Pareto upper confidence bounds algorithms: an empirical study\.In2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning \(ADPRL\), pages 1–8\. IEEE, 2014\.
- \[7\]A\. Garivier and E\. Moulines\.On upper\-confidence bound policies for switching bandit problems\.InInternational conference on algorithmic learning theory, pages 174–188\. Springer, 2011\.
- \[8\]F\. Grandoni, P\. Krysta, S\. Leonardi, and C\. Ventre\.Utilitarian mechanism design for multiobjective optimization\.SIAM Journal on Computing, 43\(4\):1263–1290, 2014\.
- \[9\]W\.\-J\. Hong, P\. Yang, and K\. Tang\.Evolutionary computation for large\-scale multi\-objective optimization: A decade of progresses\.International Journal of Automation and Computing, 18\(2\):155–169, 2021\.
- \[10\]S\. Hossain, E\. Micha, and N\. Shah\.Fair algorithms for multi\-agent multi\-armed bandits\.Advances in Neural Information Processing Systems, 34:24005–24017, 2021\.
- \[11\]A\. Hüyük and C\. Tekin\.Multi\-objective multi\-armed bandit with lexicographically ordered and satisficing objectives\.Machine Learning, 110\(6\):1233–1266, 2021\.
- \[12\]M\. Inja, C\. Kooijman, M\. de Waard, D\. M\. Roijers, and S\. Whiteson\.Queued pareto local search for multi\-objective optimization\.InInternational conference on parallel problem solving from nature, pages 589–599\. Springer, 2014\.
- \[13\]M\. Jones, H\. Nguyen, and T\. Nguyen\.An efficient algorithm for fair multi\-agent multi\-armed bandit with low regret\.InProceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 8159–8167, 2023\.
- \[14\]P\. Landgren, V\. Srivastava, and N\. E\. Leonard\.On distributed cooperative decision\-making in multiarmed bandits\.In2016 European Control Conference \(ECC\), pages 243–248\. IEEE, 2016\.
- \[15\]C\.\-S\. Lee\.Multi\-objective game\-theory models for conflict analysis in reservoir watershed management\.Chemosphere, 87\(6\):608–613, 2012\.
- \[16\]J\. Liu, H\. Qiu, L\. Yang, and M\. Xu\.Distributed multi\-agent bandits over erd\\\\backslashh\{\\\{o\}\\\}sr\\\\backslash’enyi random networks\.arXiv preprint arXiv:2510\.22811, 2025\.
- \[17\]S\. Liu, G\. Lever, J\. Merel, S\. Tunyasuvunakool, N\. Heess, and T\. Graepel\.Emergent coordination through competition\.arXiv preprint arXiv:1902\.07151, 2019\.
- \[18\]K\. Madani and J\. R\. Lund\.A monte\-carlo game theoretic approach for multi\-criteria decision making under uncertainty\.Advances in water resources, 34\(5\):607–616, 2011\.
- \[19\]P\. Mannion, J\. Duggan, and E\. Howley\.A theoretical and empirical analysis of reward transformations in multi\-objective stochastic games\.2017\.
- \[20\]A\.\-I\. Mouaddib, M\. Boussard, and M\. Bouzid\.Towards a formal framework for multi\-objective multiagent planning\.InProceedings of the 6th international joint conference on Autonomous agents and multiagent systems, pages 1–8, 2007\.
- \[21\]R\. Rădulescu, P\. Mannion, D\. M\. Roijers, and A\. Nowé\.Multi\-objective multi\-agent decision making: a utility\-based analysis and survey\.Autonomous Agents and Multi\-Agent Systems, 34\(1\):10, 2020\.
- \[22\]G\. D\. O\. Ramos, R\. Radulescu, and A\. Nowé\.A budged\-balanced tolling scheme for efficient equilibria under heterogeneous preferences\.InProceedings of the Adaptive and Learning Agents Workshop 2019 \(ALA\-19\) at AAMAS, 2019\.
- \[23\]A\. Sankararaman, A\. Ganesh, and S\. Shakkottai\.Social learning in multi agent multi armed bandits\.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3\(3\):1–35, 2019\.
- \[24\]M\. Shi\.Communication\-corruption coupling and verification in cooperative multi\-objective bandits\.arXiv preprint arXiv:2601\.11924, 2026\.
- \[25\]A\. Taylor, I\. Dusparic, E\. Galvan\-Lopez, S\. Clarke, and V\. Cahill\.Accelerating learning in multi\-objective systems through transfer learning\.In2014 international joint conference on neural networks \(IJCNN\), pages 2298–2305\. IEEE, 2014\.
- \[26\]X\. Wang, L\. Yang, Y\.\-Z\. J\. Chen, X\. Liu, M\. Hajiesmaili, D\. Towsley, and J\. C\. Lui\.Achieving near\-optimal individual regret & low communications in multi\-agent bandits\.InThe Eleventh International Conference on Learning Representations, 2022\.
- \[27\]M\. Xu and D\. Klabjan\.Decentralized randomly distributed multi\-agent multi\-armed bandit with heterogeneous rewards\.Advances in Neural Information Processing Systems, 36:74799–74855, 2023\.
- \[28\]M\. Xu, L\. Shan, F\. Ghaffari, X\. Wang, X\. Liu, and M\. Hajiesmaili\.Heterogeneous multi\-agent multi\-armed bandit on stochastic block models\.Proceedings of the ACM on Measurement and Analysis of Computing Systems, 9\(3\):1–59, 2025\.
- \[29\]S\. Q\. Yahyaa, M\. M\. Drugan, and B\. Manderick\.Annealing\-pareto multi\-objective multi\-armed bandit algorithm\.In2014 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning \(ADPRL\), pages 1–8\. IEEE, 2014\.
- \[30\]M\. Zhang, R\. Deo\-Campo Vuong, and H\. Luo\.No\-regret learning for fair multi\-agent social welfare optimization\.Advances in Neural Information Processing Systems, 37:57671–57700, 2024\.
- \[31\]J\. Zhu, R\. Sandhu, and J\. Liu\.A distributed algorithm for sequential decision making in multi\-armed bandit with homogeneous rewards\.In2020 59th IEEE Conference on Decision and Control \(CDC\), pages 3078–3083\. IEEE, 2020\.

## Appendix ATechnical appendices and supplementary material

### A\.1Related Work

MA\-MABThe study of multi\-agent multi\-armed bandits \(MA\-MAB\) with a fixed set of agents has gained significant attention in distributed learning systems\[[14](https://arxiv.org/html/2605.06864#bib.bib14),[31](https://arxiv.org/html/2605.06864#bib.bib31),[27](https://arxiv.org/html/2605.06864#bib.bib27),[26](https://arxiv.org/html/2605.06864#bib.bib26),[23](https://arxiv.org/html/2605.06864#bib.bib23),[28](https://arxiv.org/html/2605.06864#bib.bib28)\]\. A central distinction in this literature is between homogeneous settings, where all agents share identical reward distributions for each arm\[[14](https://arxiv.org/html/2605.06864#bib.bib14),[31](https://arxiv.org/html/2605.06864#bib.bib31)\]and heterogeneous settings, where reward distributions vary across agents\[[27](https://arxiv.org/html/2605.06864#bib.bib27)\]\. While homogeneous models are more tractable and better understood, heterogeneous settings introduce additional challenges due to conflicting observations and agent\-specific variability\.

Another key dimension is the communication structure among agents\. In centralized approaches, a global coordinator aggregates information from all agents, whereas in decentralized settings, agents communicate locally over a network\. Within decentralized MA\-MAB, different graph models have been studied, including fully connected networks\[[14](https://arxiv.org/html/2605.06864#bib.bib14)\], connected deterministic graphs\[[26](https://arxiv.org/html/2605.06864#bib.bib26),[23](https://arxiv.org/html/2605.06864#bib.bib23)\], random graphs\[[27](https://arxiv.org/html/2605.06864#bib.bib27)\], and structured models such as stochastic block graphs\[[28](https://arxiv.org/html/2605.06864#bib.bib28)\]\. These choices significantly impact learning performance, as they govern how efficiently information propagates across agents\.

Despite this progress, existing work typically studies these aspects in isolation and does not fully address the combined challenges of heterogeneous rewards and time\-varying decentralized communication, particularly in multi\-objective settings\. Our work builds on this literature by integrating these components within a unified framework\.

A closely related line of work studies multi\-agent bandits with fairness objectives, particularly through Nash Social Welfare \(NSW\) regret\. Prior work\[[10](https://arxiv.org/html/2605.06864#bib.bib10),[13](https://arxiv.org/html/2605.06864#bib.bib13)\]considers a setting with a utility matrix specifying rewards for each agent under homogeneous rewards and centralized communication, while subsequent extensions address non\-stationary utilities\[[30](https://arxiv.org/html/2605.06864#bib.bib30)\]\. These approaches operate on scalar utilities, where each entry of the utility matrix directly represents an agent’s reward for an arm\. In contrast, our formulation incorporates multi\-dimensional rewards, where utilities are derived as linear combinations of reward components weighted by agent\-specific preference vectors, building on\[[10](https://arxiv.org/html/2605.06864#bib.bib10)\]\.

MO\-MABMulti\-objective multi\-armed bandits \(MO\-MAB\) extend the classical bandit framework by replacing scalar rewards with vector\-valued rewards, which introduces significant challenges in both learning and evaluation\. A natural approach is to extend confidence\-bound methods to this setting\. In particular,Pareto UCB1\[[5](https://arxiv.org/html/2605.06864#bib.bib5)\]maintains coordinate\-wise confidence bounds and identifies an estimated Pareto front rather than a single optimal arm, from which actions are selected\. This approach achieves logarithmic Pareto regret using multi\-dimensional concentration inequalities, with subsequent refinements improving performance\[[6](https://arxiv.org/html/2605.06864#bib.bib6)\]\. However, such methods rely on maintaining and exploring the Pareto front, whose size and complexity can grow with the reward dimension, making efficient learning increasingly difficult in high\-dimensional settings\. Other variants, such as PF\-LEX\[[11](https://arxiv.org/html/2605.06864#bib.bib11)\]incorporate alternative preference structures like lexicographic ordering, though they similarly operate within a Pareto\-based framework\.

Despite these advances, existing approaches remain largely confined to single\-agent settings and focus on Pareto optimality as the primary notion of performance\. A complementary line of work from multi\-objective optimization \(MOO\) considers algorithms such as evolutionary methods\[[9](https://arxiv.org/html/2605.06864#bib.bib9)\]and Bayesian optimization techniques \(e\.g\., annealing Pareto knowledge gradient\[[29](https://arxiv.org/html/2605.06864#bib.bib29)\]\), which have demonstrated strong empirical performance in navigating trade\-offs across objectives\. However, these methods typically lack regret guarantees, limiting their applicability in online learning contexts\. Another common strategy is to apply scalarization, converting the vector\-valued problem into a scalar bandit problem via linear or Chebyshev functions\. While computationally appealing, such approaches obscure the underlying multi\-objective structure and depend heavily on the choice of preference weights\. Related work optimizing alternative welfare criteria, such as the General Gini Index \(GGI\)\[[3](https://arxiv.org/html/2605.06864#bib.bib3)\]similarly evaluates performance relative to a fixed scalarization rather than directly addressing multi\-objective trade\-offs\.

In contrast to existing MO\-MAB literature, which primarily focuses on Pareto\-based optimality, we adopt a utility\-based perspective for evaluating vector\-valued rewards\. By modeling agent\-specific preferences through preference vectors, we map multi\-dimensional rewards to utilities and move beyond Pareto front identification toward optimizing aggregated objectives\. This formulation naturally enables the incorporation of social welfare criteria, such as Nash Social Welfare, linking multi\-objective bandits with fairness\-aware optimization\.

MO\-MA\-MABMulti\-objective multi\-agent decision making has been studied in the context of multi\-objective partially observable stochastic games \(MOPOSGs\)\[[21](https://arxiv.org/html/2605.06864#bib.bib21)\]\. These provide a general framework that can be specialized along key dimensions—observability, the form of the reward function, and the temporal structure of interactions—allowing a wide range of problem settings to be identified\. The presence of multiple objectives complicates the notion of optimality, as agents may evaluate outcomes according to different utility functions\. A useful way to structure these problems is through the distinction between rewards and utilities\. Rewards may be team\-based\[[2](https://arxiv.org/html/2605.06864#bib.bib2),[4](https://arxiv.org/html/2605.06864#bib.bib4),[12](https://arxiv.org/html/2605.06864#bib.bib12),[19](https://arxiv.org/html/2605.06864#bib.bib19),[15](https://arxiv.org/html/2605.06864#bib.bib15)\], where all agents observe a common vector\-valued reward, or individual\[[18](https://arxiv.org/html/2605.06864#bib.bib18),[25](https://arxiv.org/html/2605.06864#bib.bib25)\], where rewards differ across agents\. Utilities can be shared \(team utilities\)\[[2](https://arxiv.org/html/2605.06864#bib.bib2),[4](https://arxiv.org/html/2605.06864#bib.bib4),[12](https://arxiv.org/html/2605.06864#bib.bib12),[19](https://arxiv.org/html/2605.06864#bib.bib19)\], agent\-specific \(individual utilities\)\[[15](https://arxiv.org/html/2605.06864#bib.bib15),[18](https://arxiv.org/html/2605.06864#bib.bib18),[25](https://arxiv.org/html/2605.06864#bib.bib25)\], or aggregated to capture fairness considerations \(social choice\)\[[8](https://arxiv.org/html/2605.06864#bib.bib8),[17](https://arxiv.org/html/2605.06864#bib.bib17),[20](https://arxiv.org/html/2605.06864#bib.bib20),[22](https://arxiv.org/html/2605.06864#bib.bib22)\]\. Different solution concepts arise depending on this formulation: coverage sets for team utilities, equilibrium and stability notions for individual utilities, and mechanism design approaches for social choice settings\.

A recent line of work considers cooperative multi\-objective bandits under adversarial corruption\[[24](https://arxiv.org/html/2605.06864#bib.bib24)\]\. In this setting, agents operate under homogeneous rewards with centralized communication, and performance is measured via regret defined through anLL\-Lipschitz scalarization of vector\-valued rewards\. The key challenge is to ensure reliable learning when observations may be corrupted by an adversary\. Specifically, a bounded number of observations can be verified as uncorrupted, controlled by a budgetvv, while the remaining observations may be perturbed by a corruption vector with total magnitude constrained byτ\\tau\. The authors study three communication strategies—raw sample sharing, sufficient statistic sharing, and recommendation\-only sharing—and characterize how corruption impacts regret in each case\. In particular, sharing raw samples propagates corrupted information and leads to regret scaling with both the corruption budget and the number of agents, whereas the latter two strategies mitigate this effect and depend only on the corruption level\.

### A\.2Regret Bound for Pareto UCB1 Gossip

We use the structure of the proof ofPareto UCB1\[[5](https://arxiv.org/html/2605.06864#bib.bib5)\]using ideas from the proof ofGossip Successive Elimination\[[16](https://arxiv.org/html/2605.06864#bib.bib16)\]to bound the deviation between the global average and the centered mean vector\. We first bound

ℙ​\[zi,k​\(t\+1\)⊀μk\+ϵ​𝟏\]≤ℙ​\[zi,k​\(t\+1\)⊀μ~k​\(t\)\+ϵ2​𝟏\]\+ℙ​\[μ~k​\(t\)⊀μk\+ϵ2​𝟏\]\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+\\epsilon\\mathbf\{1\}\]\\leq\\mathbb\{P\}\\left\[z\_\{i,k\}\(t\+1\)\\nprec\\tilde\{\\mu\}\_\{k\}\(t\)\+\\frac\{\\epsilon\}\{2\}\\mathbf\{1\}\\right\]\+\\mathbb\{P\}\\left\[\\tilde\{\\mu\}\_\{k\}\(t\)\\nprec\\mu\_\{k\}\+\\frac\{\\epsilon\}\{2\}\\mathbf\{1\}\\right\]Note that we use the decomposition into consensus and estimation error like in\[[16](https://arxiv.org/html/2605.06864#bib.bib16)\]\. The intermediateμ~k​\(t\)=1n​∑i=1nμ^i,k​\(t\)\\tilde\{\\mu\}\_\{k\}\(t\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\hat\{\\mu\}\_\{i,k\}\(t\)is the average of the local averages\. Thenμ~k​\(t\)\\tilde\{\\mu\}\_\{k\}\(t\)is a weighted average of independent random variables\. We can bound the estimation error using Chernoff and union bound\. By Chernoff’s bound, for a weighted sum of random variables

ℙ​\[S\>𝔼​\[S\]\+ϵ\]≤exp⁡\(−2​ϵ2∑jaj2\)\\mathbb\{P\}\[S\>\\mathbb\{E\}\[S\]\+\\epsilon\]\\leq\\exp\\left\(\\frac\{\-2\\epsilon^\{2\}\}\{\\sum\_\{j\}a\_\{j\}^\{2\}\}\\right\)Then we can representμ~kd​\(t\)\\tilde\{\\mu\}\_\{k\}^\{d\}\(t\)as

μ~kd​\(t\)=1n​∑i=1nX^i,kd​\(t\)=1n​∑i=1n1Ti,k​\(t\)​∑τ=1t𝟙\{Ai​\(τ\)=k\}​Xi,kd​\(τ\)=∑i=1n∑τ=1t1n​Ti,k​\(t\)​𝟙\{Ai​\(τ\)=k\}​Xi,k​\(τ\)\\tilde\{\\mu\}\_\{k\}^\{d\}\(t\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\hat\{X\}\_\{i,k\}^\{d\}\(t\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{T\_\{i,k\}\(t\)\}\\sum\_\{\\tau=1\}^\{t\}\\mathbbm\{1\}\_\{\\\{A\_\{i\}\(\\tau\)=k\\\}\}X\_\{i,k\}^\{d\}\(\\tau\)=\\sum\_\{i=1\}^\{n\}\\sum\_\{\\tau=1\}^\{t\}\\frac\{1\}\{nT\_\{i,k\}\(t\)\}\\mathbbm\{1\}\_\{\\\{A\_\{i\}\(\\tau\)=k\\\}\}X\_\{i,k\}\(\\tau\)In this case

∑jaj2=∑i=1n∑τ=1Ti,k​\(t\)1\(n​Ti,k​\(t\)\)2=∑i=1n1n2​Ti,k​\(t\)≤1n​∑i=1n1Ti,k​\(t\)\\sum\_\{j\}a\_\{j\}^\{2\}=\\sum\_\{i=1\}^\{n\}\\sum\_\{\\tau=1\}^\{T\_\{i,k\}\(t\)\}\\frac\{1\}\{\(nT\_\{i,k\}\(t\)\)^\{2\}\}=\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{n^\{2\}T\_\{i,k\}\(t\)\}\\leq\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{T\_\{i,k\}\(t\)\}Ford∈\[D\]d\\in\[D\]

ℙ​\[μ~kd​\(t\)\>μkd\+ϵ2\]≤exp⁡\(−12​n​ϵ2∑i=1n1Ti,k​\(t\)\)≤exp⁡\(−12​n​ϵ2nsk​\(t\)\)=exp⁡\(−12​sk​\(t\)​ϵ2\)\\mathbb\{P\}\\left\[\\tilde\{\\mu\}\_\{k\}^\{d\}\(t\)\>\\mu\_\{k\}^\{d\}\+\\frac\{\\epsilon\}\{2\}\\right\]\\leq\\exp\\left\(\\frac\{\-\\frac\{1\}\{2\}n\\epsilon^\{2\}\}\{\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{T\_\{i,k\}\(t\)\}\}\\right\)\\leq\\exp\\left\(\\frac\{\-\\frac\{1\}\{2\}n\\epsilon^\{2\}\}\{\\frac\{n\}\{s\_\{k\}\(t\)\}\}\\right\)=\\exp\\left\(\-\\frac\{1\}\{2\}s\_\{k\}\(t\)\\epsilon^\{2\}\\right\)wheresk=mini∈\[n\]⁡Ti,k​\(t\)s\_\{k\}=\\min\_\{i\\in\[n\]\}T\_\{i,k\}\(t\)\. Therefore, by union bound the estimation error

ℙ​\[μ~k​\(t\)⊀μk\+ϵ2​𝟏\]=ℙ​\[∪d=1Dμ~kd​\(t\)\>μkd\+ϵ2\]≤D​exp⁡\(−12​sk​\(t\)​ϵ2\)\\mathbb\{P\}\\left\[\\tilde\{\\mu\}\_\{k\}\(t\)\\nprec\\mu\_\{k\}\+\\frac\{\\epsilon\}\{2\}\\mathbf\{1\}\\right\]=\\mathbb\{P\}\\left\[\\cup\_\{d=1\}^\{D\}\\tilde\{\\mu\}\_\{k\}^\{d\}\(t\)\>\\mu\_\{k\}^\{d\}\+\\frac\{\\epsilon\}\{2\}\\right\]\\leq D\\exp\\left\(\-\\frac\{1\}\{2\}s\_\{k\}\(t\)\\epsilon^\{2\}\\right\)To bound consensus error like in\[[16](https://arxiv.org/html/2605.06864#bib.bib16)\]we find a recurrence, viewing it as a orthogonal projection from the average of the local averages\. To achieve this, we unroll and using the row stochasticity property ofWtW\_\{t\}\. Departing from\[[16](https://arxiv.org/html/2605.06864#bib.bib16)\], we vectorize across agentsiiand dimensionsdd\.zk​\(t\+1\)∈ℝn×Dz\_\{k\}\(t\+1\)\\in\\mathbb\{R\}^\{n\\times D\}is the global average at timet\+1t\+1andμ~k​\(t\)∈ℝn×D\\tilde\{\\mu\}\_\{k\}\(t\)\\in\\mathbb\{R\}^\{n\\times D\}is the average of the local averages at timett\. We letek​\(t\+1\)=zk​\(t\+1\)−μ~k​\(t\)e\_\{k\}\(t\+1\)=z\_\{k\}\(t\+1\)\-\\tilde\{\\mu\}\_\{k\}\(t\)be the consensus error at timet\+1t\+1\. Lastly supposeuk​\(t\)=μ^k​\(t\)−μ^k​\(t\)u\_\{k\}\(t\)=\\hat\{\\mu\}\_\{k\}\(t\)\-\\hat\{\\mu\}\_\{k\}\(t\)is the local update attt\.

ek​\(t\+1\)\\displaystyle e\_\{k\}\(t\+1\)=zk​\(t\+1\)−μ~k​\(t\)\\displaystyle=z\_\{k\}\(t\+1\)\-\\tilde\{\\mu\}\_\{k\}\(t\)=zk​\(t\+1\)−1n​𝟏𝟏⊤​μ^k​\(t\)\\displaystyle=z\_\{k\}\(t\+1\)\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\hat\{\\mu\}\_\{k\}\(t\)=Wt​zk​\(t\)\+uk​\(t\)−1n​𝟏𝟏⊤​μ^k​\(t\)\\displaystyle=W\_\{t\}z\_\{k\}\(t\)\+u\_\{k\}\(t\)\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\hat\{\\mu\}\_\{k\}\(t\)=Wt​zk​\(t\)\+uk​\(t\)−1n​𝟏𝟏⊤​μ^k​\(t−1\)−1n​𝟏𝟏⊤​uk​\(t\)\\displaystyle=W\_\{t\}z\_\{k\}\(t\)\+u\_\{k\}\(t\)\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\hat\{\\mu\}\_\{k\}\(t\-1\)\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}u\_\{k\}\(t\)=\(Wt​zk​\(t\)−1n​𝟏𝟏⊤​μ^k​\(t−1\)\)\+\(I−1n​𝟏𝟏⊤\)​uk​\(t\)\\displaystyle=\\left\(W\_\{t\}z\_\{k\}\(t\)\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\hat\{\\mu\}\_\{k\}\(t\-1\)\\right\)\+\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)u\_\{k\}\(t\)=Wt​ek​\(t\)\+\(I−1n​𝟏𝟏⊤\)​uk​\(t\)\\displaystyle=W\_\{t\}e\_\{k\}\(t\)\+\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)u\_\{k\}\(t\)Unrolling we have

ek​\(t\)=∑τ=1t−1\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)​uk​\(τ\)e\_\{k\}\(t\)=\\sum\_\{\\tau=1\}^\{t\-1\}\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)u\_\{k\}\(\\tau\)Next, we bound the Frobenius norm ofek​\(t\)e\_\{k\}\(t\)\.

‖ek​\(t\)‖F2\\displaystyle\\left\\lVert e\_\{k\}\(t\)\\right\\rVert\_\{F\}^\{2\}=∑d=1D‖∑τ=1t−1\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)​ukd​\(τ\)‖22\\displaystyle=\\sum\_\{d=1\}^\{D\}\\left\\lVert\\sum\_\{\\tau=1\}^\{t\-1\}\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)u\_\{k\}^\{d\}\(\\tau\)\\right\\rVert\_\{2\}^\{2\}≤∑d=1D∑τ=1t−1‖\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)​ukd​\(τ\)‖22\\displaystyle\\leq\\sum\_\{d=1\}^\{D\}\\sum\_\{\\tau=1\}^\{t\-1\}\\left\\lVert\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)u\_\{k\}^\{d\}\(\\tau\)\\right\\rVert\_\{2\}^\{2\}≤∑d=1D∑τ=1t−1‖\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)‖o​p2​‖ukd​\(τ\)‖22\\displaystyle\\leq\\sum\_\{d=1\}^\{D\}\\sum\_\{\\tau=1\}^\{t\-1\}\\left\\lVert\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)\\right\\rVert\_\{op\}^\{2\}\\left\\lVert u\_\{k\}^\{d\}\(\\tau\)\\right\\rVert\_\{2\}^\{2\}=∑τ=1t−1‖\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)‖o​p2​∑d=1D‖ukd​\(τ\)‖22\\displaystyle=\\sum\_\{\\tau=1\}^\{t\-1\}\\left\\lVert\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)\\right\\rVert\_\{op\}^\{2\}\\sum\_\{d=1\}^\{D\}\\left\\lVert u\_\{k\}^\{d\}\(\\tau\)\\right\\rVert\_\{2\}^\{2\}=∑τ=1t−1‖\(∏s=τ\+1t−1Ws\)​\(I−1n​𝟏𝟏⊤\)‖o​p2​‖uk​\(τ\)‖F2\\displaystyle=\\sum\_\{\\tau=1\}^\{t\-1\}\\left\\lVert\\left\(\\prod\_\{s=\\tau\+1\}^\{t\-1\}W\_\{s\}\\right\)\\left\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\\right\)\\right\\rVert\_\{op\}^\{2\}\\left\\lVert u\_\{k\}\(\\tau\)\\right\\rVert\_\{F\}^\{2\}Referencing preliminary fact B3 in\[[16](https://arxiv.org/html/2605.06864#bib.bib16)\], ifWtW\_\{t\}is double stochastic, symmetric, and iid, for allv∈Vv\\in Vands,t∈ℕs,t\\in\\mathbb\{N\}withs<ts<t

ℙ​\[‖Wt​…​Ws\+1​1n​𝟏‖≥δ\]≤λ2​\(𝔼​\[W2\]\)t−sδ2\\mathbb\{P\}\\left\[\\left\\lVert W\_\{t\}\\dots W\_\{s\+1\}\\frac\{1\}\{n\}\\mathbf\{1\}\\right\\rVert\\geq\\delta\\right\]\\leq\\frac\{\\lambda\_\{2\}\(\\mathbb\{E\}\[W^\{2\}\]\)^\{t\-s\}\}\{\\delta^\{2\}\}LetAt,τ=Wt−1​…​Wτ\+1​\(I−1n​𝟏𝟏⊤\)A\_\{t,\\tau\}=W\_\{t\-1\}\\dots W\_\{\\tau\+1\}\(I\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\)\. Due to the row stochasticity ofWtW\_\{t\}

At,τ​ei=Wt−1​…​Wτ\+1​\(ei−1n​𝟏𝟏⊤​ei\)=Wt−1​…​Wτ\+1​\(ei−1n​𝟏\)=Wt−1​…​Wτ\+1​ei−1n​𝟏A\_\{t,\\tau\}e\_\{i\}=W\_\{t\-1\}\\dots W\_\{\\tau\+1\}\\left\(e\_\{i\}\-\\frac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}e\_\{i\}\\right\)=W\_\{t\-1\}\\dots W\_\{\\tau\+1\}\\left\(e\_\{i\}\-\\frac\{1\}\{n\}\\mathbf\{1\}\\right\)=W\_\{t\-1\}\\dots W\_\{\\tau\+1\}e\_\{i\}\-\\frac\{1\}\{n\}\\mathbf\{1\}Since‖At,τ‖o​p≤∑i=1n‖A​ei‖22\\left\\lVert A\_\{t,\\tau\}\\right\\rVert\_\{op\}\\leq\\sqrt\{\\sum\_\{i=1\}^\{n\}\\left\\lVert Ae\_\{i\}\\right\\rVert\_\{2\}^\{2\}\},

ℙ​\[‖At,τ‖o​p≥δ\]\\displaystyle\\mathbb\{P\}\[\\left\\lVert A\_\{t,\\tau\}\\right\\rVert\_\{op\}\\geq\\delta\]≤ℙ​\[∑i=1n‖At,τ​ei‖22≥δ2\]\\displaystyle\\leq\\mathbb\{P\}\\left\[\\sum\_\{i=1\}^\{n\}\\left\\lVert A\_\{t,\\tau\}e\_\{i\}\\right\\rVert\_\{2\}^\{2\}\\geq\\delta^\{2\}\\right\]≤∑i=1nℙ​\[‖At,τ​ei‖22≥δn\]=∑i=1nℙ​\[‖At,τ​ei‖2≥δn\]\\displaystyle\\leq\\sum\_\{i=1\}^\{n\}\\mathbb\{P\}\\left\[\\left\\lVert A\_\{t,\\tau\}e\_\{i\}\\right\\rVert\_\{2\}^\{2\}\\geq\\frac\{\\delta\}\{n\}\\right\]=\\sum\_\{i=1\}^\{n\}\\mathbb\{P\}\\left\[\\left\\lVert A\_\{t,\\tau\}e\_\{i\}\\right\\rVert\_\{2\}\\geq\\frac\{\\delta\}\{\\sqrt\{n\}\}\\right\]≤∑i=1nn​λ2​\(𝔼​\[W2\]\)t−τ−1δ2=n2​λ2​\(𝔼​\[W2\]\)t−τ−1δ2\\displaystyle\\leq\\sum\_\{i=1\}^\{n\}\\frac\{n\\lambda\_\{2\}\(\\mathbb\{E\}\[W^\{2\}\]\)^\{t\-\\tau\-1\}\}\{\\delta^\{2\}\}=\\frac\{n^\{2\}\\lambda\_\{2\}\(\\mathbb\{E\}\[W^\{2\}\]\)^\{t\-\\tau\-1\}\}\{\\delta^\{2\}\}Letρ=λ2​\(𝔼​\[W2\]\)\\rho=\\lambda\_\{2\}\(\\mathbb\{E\}\[W^\{2\}\]\)whereρ<1\\rho<1\. Settingδ=ρ\(t−s−1\)/2​t\\delta=\\rho^\{\(t\-s\-1\)/2\}t, the bound holds with probabilityn2t2\\frac\{n^\{2\}\}\{t^\{2\}\}\. We use the union bound to show

ℙ\[∃τ<t:∥At,τ∥o​p≥ρ\(t−s−1\)/2t\]≤∑t=1t−1ℙ\[∥At,τ∥o​p≥ρ\(t−s−1\)/2t\]=\(t−1\)n2t2≤n2t\\mathbb\{P\}\[\\exists\\tau<t:\\left\\lVert A\_\{t,\\tau\}\\right\\rVert\_\{op\}\\geq\\rho^\{\(t\-s\-1\)/2\}t\]\\leq\\sum\_\{t=1\}^\{t\-1\}\\mathbb\{P\}\[\\left\\lVert A\_\{t,\\tau\}\\right\\rVert\_\{op\}\\geq\\rho^\{\(t\-s\-1\)/2\}t\]=\(t\-1\)\\frac\{n^\{2\}\}\{t^\{2\}\}\\leq\\frac\{n^\{2\}\}\{t\}As a result,

ℙ\[∀τ<t:∥At,τ∥o​p≤ρ\(t−s−1\)/2t\]≥1−n2t\\mathbb\{P\}\[\\forall\\tau<t:\\left\\lVert A\_\{t,\\tau\}\\right\\rVert\_\{op\}\\leq\\rho^\{\(t\-s\-1\)/2\}t\]\\geq 1\-\\frac\{n^\{2\}\}\{t\}Now we bound the second term in the product‖uk​\(τ\)‖F2\\left\\lVert u\_\{k\}\(\\tau\)\\right\\rVert\_\{F\}^\{2\}\. In the worse case scenario, we have that armkkis pulled atτ\\tau\. Recall that

μ^i,k​\(τ\)=Ti,k​\(τ−1\)​μ^i,k​\(τ−1\)\+Xi,k​\(τ\)Ti,k​\(τ−1\)\+1\\hat\{\\mu\}\_\{i,k\}\(\\tau\)=\\frac\{T\_\{i,k\}\(\\tau\-1\)\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)\+X\_\{i,k\}\(\\tau\)\}\{T\_\{i,k\}\(\\tau\-1\)\+1\}Then

μ^i,k​\(τ\)−μ^i,k​\(τ−1\)\\displaystyle\\hat\{\\mu\}\_\{i,k\}\(\\tau\)\-\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)=Ti,k​\(τ−1\)​μ^i,k​\(τ−1\)\+Xi,k​\(τ\)−Ti,k​\(τ\)​μ^i,k​\(τ−1\)Ti,k​\(τ\)\\displaystyle=\\frac\{T\_\{i,k\}\(\\tau\-1\)\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)\+X\_\{i,k\}\(\\tau\)\-T\_\{i,k\}\(\\tau\)\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)\}\{T\_\{i,k\}\(\\tau\)\}=Xi,k​\(τ\)−μ^i,k​\(τ−1\)Ti,k​\(τ\)≤1Ti,k​\(τ\)\\displaystyle=\\frac\{X\_\{i,k\}\(\\tau\)\-\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)\}\{T\_\{i,k\}\(\\tau\)\}\\leq\\frac\{1\}\{T\_\{i,k\}\(\\tau\)\}as rewards are in the range\[0,1\]\[0,1\]\. Summing over agentsi∈\[n\]i\\in\[n\]

‖uk​\(τ\)‖F2=∑i=1n\(μ^i,k​\(τ\)−μ^i,k​\(τ−1\)\)2≤∑i=1n1Ti,k​\(τ\)2≤nτ2\\left\\lVert u\_\{k\}\(\\tau\)\\right\\rVert\_\{F\}^\{2\}=\\sum\_\{i=1\}^\{n\}\(\\hat\{\\mu\}\_\{i,k\}\(\\tau\)\-\\hat\{\\mu\}\_\{i,k\}\(\\tau\-1\)\)^\{2\}\\leq\\sum\_\{i=1\}^\{n\}\\frac\{1\}\{T\_\{i,k\}\(\\tau\)^\{2\}\}\\leq\\frac\{n\}\{\\tau^\{2\}\}Overall,

‖ek​\(t\)‖F\\displaystyle\\left\\lVert e\_\{k\}\(t\)\\right\\rVert\_\{F\}≤t​n​∑τ=1t−1ρ\(t−τ−1\)/2τ\\displaystyle\\leq t\\sqrt\{n\}\\sum\_\{\\tau=1\}^\{t\-1\}\\frac\{\\rho^\{\(t\-\\tau\-1\)/2\}\}\{\\tau\}=t​n​∑j=0t−2ρj/2t−j−1\\displaystyle=t\\sqrt\{n\}\\sum\_\{j=0\}^\{t\-2\}\\frac\{\\rho^\{j/2\}\}\{t\-j\-1\}≤\(t​n\)​1t​∑j=0t−2ρj/2≤n​∑j=0∞ρj/2=n1−ρ\\displaystyle\\leq\(t\\sqrt\{n\}\)\\frac\{1\}\{t\}\\sum\_\{j=0\}^\{t\-2\}\\rho^\{j/2\}\\leq\\sqrt\{n\}\\sum\_\{j=0\}^\{\\infty\}\\rho^\{j/2\}=\\frac\{\\sqrt\{n\}\}\{1\-\\sqrt\{\\rho\}\}with probability at least1−n2t1\-\\frac\{n^\{2\}\}\{t\}\. If the Frobenius norm of the consensus error matrix is bounded, each of the entries in the matrix is bounded\.

ℙ\[∩i=1n∩d=1D\|zi,kd\(t\)−μ~kd\|≤n1−ρ\]≥1−n2t\\mathbb\{P\}\\left\[\\cap\_\{i=1\}^\{n\}\\cap\_\{d=1\}^\{D\}\\left\|z\_\{i,k\}^\{d\}\(t\)\-\\tilde\{\\mu\}\_\{k\}^\{d\}\\right\|\\leq\\frac\{\\sqrt\{n\}\}\{1\-\\sqrt\{\\rho\}\}\\right\]\\geq 1\-\\frac\{n^\{2\}\}\{t\}Then for all agentsi∈\[n\]i\\in\[n\], settingϵ≥2​n1−p\\epsilon\\geq\\frac\{2\\sqrt\{n\}\}\{1\-\\sqrt\{p\}\}

ℙ​\[zi,k​\(t\+1\)⊀μ~k​\(t\)\+ϵ2​𝟏\]≤ℙ​\[∪d=1Dzi,kd​\(t\)\>μ~kd​\(t\)\+n1−ρ\]≤n2t\\mathbb\{P\}\\left\[z\_\{i,k\}\(t\+1\)\\nprec\\tilde\{\\mu\}\_\{k\}\(t\)\+\\frac\{\\epsilon\}\{2\}\\mathbf\{1\}\\right\]\\leq\\mathbb\{P\}\\left\[\\cup\_\{d=1\}^\{D\}z\_\{i,k\}^\{d\}\(t\)\>\\tilde\{\\mu\}\_\{k\}^\{d\}\(t\)\+\\frac\{\\sqrt\{n\}\}\{1\-\\sqrt\{\\rho\}\}\\right\]\\leq\\frac\{n^\{2\}\}\{t\}Combining estimation and consensus bounds

ℙ​\[zi,k​\(t\+1\)⊀μk\+ϵ​𝟏\]≤D​exp⁡\(−12​sk​\(t\)​ϵ2\)\+n2t\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+\\epsilon\\mathbf\{1\}\]\\leq D\\exp\\left\(\-\\frac\{1\}\{2\}s\_\{k\}\(t\)\\epsilon^\{2\}\\right\)\+\\frac\{n^\{2\}\}\{t\}Using the same argument withϵ≥2​n1−p\\epsilon\\geq\\frac\{2\\sqrt\{n\}\}\{1\-\\sqrt\{p\}\}

ℙ​\[zi,k​\(t\+1\)⊁μk−ϵ​𝟏\]≤D​exp⁡\(−12​sk​\(t\)​ϵ2\)\+n2t\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nsucc\\mu\_\{k\}\-\\epsilon\\mathbf\{1\}\]\\leq D\\exp\\left\(\-\\frac\{1\}\{2\}s\_\{k\}\(t\)\\epsilon^\{2\}\\right\)\+\\frac\{n^\{2\}\}\{t\}Recall thatsk=mini∈\[n\]⁡Ti,k​\(t\)s\_\{k\}=\\min\_\{i\\in\[n\]\}T\_\{i,k\}\(t\)\. The Pareto UCB1 Gossip exploration term is given byci,k​\(t\)=8​log⁡\(t​D​\|𝒜∗\|4\)Ti,k​\(t\)\+2​n1−pc\_\{i,k\}\(t\)=\\sqrt\{\\frac\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{T\_\{i,k\}\(t\)\}\}\+\\frac\{2\\sqrt\{n\}\}\{1\-\\sqrt\{p\}\}\. Definedk​\(t\)=8​log⁡\(t​D​\|𝒜∗\|4\)sk​\(t\)\+2​n1−pd\_\{k\}\(t\)=\\sqrt\{\\frac\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{s\_\{k\}\(t\)\}\}\+\\frac\{2\\sqrt\{n\}\}\{1\-\\sqrt\{p\}\}so thatdk​\(t\)≥ci,k​\(t\)d\_\{k\}\(t\)\\geq c\_\{i,k\}\(t\)\. Substitutingϵ=dk​\(t\)\\epsilon=d\_\{k\}\(t\)into the bounds

ℙ​\[zi,k​\(t\+1\)⊀μk\+dk​\(t\)​𝟏\]≤D​exp⁡\(−12​sk​\(t\)​\(8​log⁡\(t​D​\|𝒜∗\|4\)sk​\(t\)\)\)\+n2t=D​\(t​D​\|𝒜∗\|4\)−4\+n2t=1\|𝒜∗\|​t4\+n2t\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+d\_\{k\}\(t\)\\mathbf\{1\}\]\\leq D\\exp\\left\(\-\\frac\{1\}\{2\}s\_\{k\}\(t\)\\left\(\\frac\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{s\_\{k\}\(t\)\}\\right\)\\right\)\+\\frac\{n^\{2\}\}\{t\}=D\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)^\{\-4\}\+\\frac\{n^\{2\}\}\{t\}=\\frac\{1\}\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|t^\{4\}\}\+\\frac\{n^\{2\}\}\{t\}Equivalently, we have

ℙ​\[zi,k​\(t\+1\)⊁μk−dk​\(t\)​𝟏\]≤1\|𝒜∗\|​t4\+n2t\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nsucc\\mu\_\{k\}\-d\_\{k\}\(t\)\\mathbf\{1\}\]\\leq\\frac\{1\}\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|t^\{4\}\}\+\\frac\{n^\{2\}\}\{t\}The goal is to bound the counter of a suboptimal armkkfor a particular agentii\. Letl\>0l\>0be the number of times armkkis pulled during a “warm\-up period"\.

Ti,k​\(T\)\\displaystyle T\_\{i,k\}\(T\)=1\+∑t=K\+1T𝟙\{Ai​\(t\)=k\}\\displaystyle=1\+\\sum\_\{t=K\+1\}^\{T\}\\mathbbm\{1\}\_\{\\\{A\_\{i\}\(t\)=k\\\}\}≤l\+∑t=K\+1T𝟙\{Ai​\(t\)=k,Ti,k​\(t−1\)≥l\}\\displaystyle\\leq l\+\\sum\_\{t=K\+1\}^\{T\}\\mathbbm\{1\}\_\{\\\{A\_\{i\}\(t\)=k,T\_\{i,k\}\(t\-1\)\\geq l\\\}\}≤l\+∑t=K\+1T∑h=1\|𝒜∗\|𝟙\{zi,k​\(t\+1\)\+ci,k​\(t\)⊀zi,h​\(t\+1\)\+ci,h​\(t\),Ti,k​\(t−1\)≥l\}\\displaystyle\\leq l\+\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\mathbbm\{1\}\_\{\\\{z\_\{i,k\}\(t\+1\)\+c\_\{i,k\}\(t\)\\nprec z\_\{i,h\}\(t\+1\)\+c\_\{i,h\}\(t\),T\_\{i,k\}\(t\-1\)\\geq l\\\}\}≤l\+∑t=K\+1T∑sk=lT∑sh=1T∑h=1\|𝒜∗\|𝟙\{zi,k​\(t\+1\)\+ci,k​\(sk\)⊀zi,h​\(t\+1\)\+ci,h​\(sh\),Ti,k​\(t−1\)=sk,Ti,h​\(t−1\)=sh\}\\displaystyle\\leq l\+\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\mathbbm\{1\}\_\{\\\{z\_\{i,k\}\(t\+1\)\+c\_\{i,k\}\(s\_\{k\}\)\\nprec z\_\{i,h\}\(t\+1\)\+c\_\{i,h\}\(s\_\{h\}\),T\_\{i,k\}\(t\-1\)=s\_\{k\},T\_\{i,h\}\(t\-1\)=s\_\{h\}\\\}\}whereci,k​\(sk\)c\_\{i,k\}\(s\_\{k\}\)is the explore term for armkkafter it is pulledsks\_\{k\}times andci,h​\(sh\)c\_\{i,h\}\(s\_\{h\}\)is the explore term for armhhafter it is pulledshs\_\{h\}times\. Note that the global averages cannot be indexed by counters but the explore terms can\. For the last inequality fixing a Pareto armhh, at a timettthe indicator is upper bounded by summing over the possible counter values\. The countersks\_\{k\}for armkkcan take values fromlltoTT\. The countershs\_\{h\}for armhhcan take values from11toTT\. If UCB of armkkwith countsks\_\{k\}is not dominated by UCB of armhhwith countsks\_\{k\}, at least one of the following conditions hold\.

zi,h​\(t\+1\)⊁μh−ci,h​\(sh\)​𝟏;zi,k​\(t\+1\)⊀μk\+ci,k​\(sk\)​𝟏;μh⊁μk\+2​ci,k​\(sk\)​𝟏z\_\{i,h\}\(t\+1\)\\nsucc\\mu\_\{h\}\-c\_\{i,h\}\(s\_\{h\}\)\\mathbf\{1\};z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+c\_\{i,k\}\(s\_\{k\}\)\\mathbf\{1\};\\mu\_\{h\}\\nsucc\\mu\_\{k\}\+2c\_\{i,k\}\(s\_\{k\}\)\\mathbf\{1\}After an interval of time, it happens that statement 3 does not hold\. This happens when2​ci,k​\(sk\)≤Δk2c\_\{i,k\}\(s\_\{k\}\)\\leq\\Delta\_\{k\}\. This implies that

2​\(8​log⁡\(t​D​\|𝒜∗\|4\)sk\+2​n1−p\)≤Δk2\\left\(\\sqrt\{\\frac\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{s\_\{k\}\}\}\+\\frac\{2\\sqrt\{n\}\}\{1\-\\sqrt\{p\}\}\\right\)\\leq\\Delta\_\{k\}Using the stronger inequality2​8​log⁡\(t​D​\|𝒜∗\|4\)sk≤Δk2\\sqrt\{\\frac\{8\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{s\_\{k\}\}\}\\leq\\Delta\_\{k\}, whensk≥32​log⁡\(t​D​\|𝒜∗\|4\)Δk2s\_\{k\}\\geq\\frac\{32\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{\\Delta\_\{k\}^\{2\}\}statement 3 does not hold\. Set the warm\-up periodl=⌈32​log⁡\(t​D​\|𝒜∗\|4\)Δk2⌉l=\\lceil\{\\frac\{32\\log\(t\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{\\Delta\_\{k\}^\{2\}\}\}\\rceil\. After this warm\-up period if armkkis not dominated, statement 1 or 2 must hold\. Taking expectations on both sides

𝔼​\[Ti,k​\(t\)\]\\displaystyle\\mathbb\{E\}\[T\_\{i,k\}\(t\)\]≤l\+∑t=K\+1T∑sk=lT∑sh=1T∑h=1\|𝒜∗\|ℙ​\[zi,k​\(t\+1\)\+ci,k​\(sk\)⊀zi,h​\(t\+1\)\+ci,h​\(sh\),Ti,k​\(t−1\)=sk,Ti,h​\(t−1\)=sh\]\\displaystyle\\leq l\+\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\+c\_\{i,k\}\(s\_\{k\}\)\\nprec z\_\{i,h\}\(t\+1\)\+c\_\{i,h\}\(s\_\{h\}\),T\_\{i,k\}\(t\-1\)=s\_\{k\},T\_\{i,h\}\(t\-1\)=s\_\{h\}\]≤l\+∑t=K\+1T∑sk=lT∑sh=1T∑h=1\|𝒜∗\|ℙ​\[zi,h​\(t\+1\)⊁μh−ci,h​\(sh\)​𝟏,Ti,k​\(t−1\)=sk,Ti,h​\(t−1\)=sh\]\+∑t=K\+1T∑sk=lT∑sh=1T∑h=1\|𝒜∗\|ℙ​\[zi,k​\(t\+1\)⊀μk\+ci,k​\(sk\)​𝟏,Ti,k​\(t−1\)=sk,Ti,h​\(t−1\)=sh\]\\displaystyle\\begin\{split\}&\\leq l\+\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\mathbb\{P\}\[z\_\{i,h\}\(t\+1\)\\nsucc\\mu\_\{h\}\-c\_\{i,h\}\(s\_\{h\}\)\\mathbf\{1\},T\_\{i,k\}\(t\-1\)=s\_\{k\},T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\\\ &\\qquad\+\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+c\_\{i,k\}\(s\_\{k\}\)\\mathbf\{1\},T\_\{i,k\}\(t\-1\)=s\_\{k\},T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\end\{split\}=l\+∑h=1\|𝒜∗\|∑t=K\+1T∑sh=1Tℙ​\[zi,h​\(t\+1\)⊁μh−ci,h​\(sh\)​𝟏,Ti,h​\(t−1\)=sh\]\+∑h=1\|𝒜∗\|∑t=K\+1T∑sk=lTℙ​\[zi,k​\(t\+1\)⊀μk\+ci,k​\(sk\)​𝟏,Ti,k​\(t−1\)=sk\]\\displaystyle\\begin\{split\}&=l\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\mathbb\{P\}\[z\_\{i,h\}\(t\+1\)\\nsucc\\mu\_\{h\}\-c\_\{i,h\}\(s\_\{h\}\)\\mathbf\{1\},T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\\\ &\\qquad\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+c\_\{i,k\}\(s\_\{k\}\)\\mathbf\{1\},T\_\{i,k\}\(t\-1\)=s\_\{k\}\]\\end\{split\}=l\+∑h=1\|𝒜∗\|∑t=K\+1T∑sh=1Tℙ​\[zi,h​\(t\+1\)⊁μh−ci,h​\(sh\)​𝟏\|Ti,h​\(t−1\)=sh\]​ℙ​\[Ti,h​\(t−1\)=sh\]\+∑h=1\|𝒜∗\|∑t=K\+1T∑sk=lTℙ​\[zi,k​\(t\+1\)⊀μk\+ci,k​\(sk\)​𝟏\|Ti,k​\(t−1\)=sk\]​ℙ​\[Ti,k​\(t−1\)=sk\]\\displaystyle\\begin\{split\}&=l\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\mathbb\{P\}\[z\_\{i,h\}\(t\+1\)\\nsucc\\mu\_\{h\}\-c\_\{i,h\}\(s\_\{h\}\)\\mathbf\{1\}\|T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\mathbb\{P\}\[T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\\\ &\\qquad\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\mathbb\{P\}\[z\_\{i,k\}\(t\+1\)\\nprec\\mu\_\{k\}\+c\_\{i,k\}\(s\_\{k\}\)\\mathbf\{1\}\|T\_\{i,k\}\(t\-1\)=s\_\{k\}\]\\mathbb\{P\}\[T\_\{i,k\}\(t\-1\)=s\_\{k\}\]\\end\{split\}≤l\+∑h=1\|𝒜∗\|∑t=K\+1T∑sh=1T\(1\|𝒜∗\|​t4\+n2t\)​ℙ​\[Ti,h​\(t−1\)=sh\]\+∑h=1\|𝒜∗\|∑t=K\+1T∑sk=lT\(1\|𝒜∗\|​t4\+n2t\)​ℙ​\[Ti,k​\(t−1\)=sk\]\\displaystyle\\begin\{split\}&\\leq l\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{h\}=1\}^\{T\}\\left\(\\frac\{1\}\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|t^\{4\}\}\+\\frac\{n^\{2\}\}\{t\}\\right\)\\mathbb\{P\}\[T\_\{i,h\}\(t\-1\)=s\_\{h\}\]\\\\ &\\qquad\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}\\sum\_\{s\_\{k\}=l\}^\{T\}\\left\(\\frac\{1\}\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|t^\{4\}\}\+\\frac\{n^\{2\}\}\{t\}\\right\)\\mathbb\{P\}\[T\_\{i,k\}\(t\-1\)=s\_\{k\}\]\\end\{split\}=l\+∑h=1\|𝒜∗\|∑t=K\+1T2​\(1\|𝒜∗\|​t4\+n2t\)=l\+2​∑t=K\+1T1t4\+\|𝒜∗\|​n2t≤l\+2​∑t=K\+1∞1t4\+2​\|𝒜∗\|​n2​∑t=K\+1T1t\\displaystyle=l\+\\sum\_\{h=1\}^\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\\sum\_\{t=K\+1\}^\{T\}2\\left\(\\frac\{1\}\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|t^\{4\}\}\+\\frac\{n^\{2\}\}\{t\}\\right\)=l\+2\\sum\_\{t=K\+1\}^\{T\}\\frac\{1\}\{t^\{4\}\}\+\\frac\{\\left\|\\mathcal\{A\}^\{\*\}\\right\|n^\{2\}\}\{t\}\\leq l\+2\\sum\_\{t=K\+1\}^\{\\infty\}\\frac\{1\}\{t^\{4\}\}\+2\\left\|\\mathcal\{A\}^\{\*\}\\right\|n^\{2\}\\sum\_\{t=K\+1\}^\{T\}\\frac\{1\}\{t\}≤l\+π445\+2​\|𝒜∗\|​n2​\(log⁡T\+1\)\\displaystyle\\leq l\+\\frac\{\\pi^\{4\}\}\{45\}\+2\\left\|\\mathcal\{A\}^\{\*\}\\right\|n^\{2\}\(\\log T\+1\)The Pareto regret of a policyπ\\piat timettfor a single agentiiis bounded by

∑k∉𝒜∗32​log⁡\(T​D​\|𝒜∗\|4\)Δk\+\(1\+π445\+2​\|𝒜∗\|​n2​\(log⁡T\+1\)\)​∑k∈𝒜∗Δk\\sum\_\{k\\notin\\mathcal\{A\}^\{\*\}\}\\frac\{32\\log\(T\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{\\Delta\_\{k\}\}\+\\left\(1\+\\frac\{\\pi^\{4\}\}\{45\}\+2\\left\|\\mathcal\{A\}^\{\*\}\\right\|n^\{2\}\(\\log T\+1\)\\right\)\\sum\_\{k\\in\\mathcal\{A\}^\{\*\}\}\\Delta\_\{k\}As a result, the global Pareto regret of a policyπ\\piat timett

RegT​\(π\)≤n​∑k∉𝒜∗32​log⁡\(T​D​\|𝒜∗\|4\)Δk\+n​\(1\+π445\+2​\|𝒜∗\|​n2​\(log⁡T\+1\)\)​∑k∈𝒜∗Δk\\text\{Reg\}\_\{T\}\(\\pi\)\\leq n\\sum\_\{k\\notin\\mathcal\{A\}^\{\*\}\}\\frac\{32\\log\(T\\sqrt\[4\]\{D\\left\|\\mathcal\{A\}^\{\*\}\\right\|\}\)\}\{\\Delta\_\{k\}\}\+n\\left\(1\+\\frac\{\\pi^\{4\}\}\{45\}\+2\\left\|\\mathcal\{A\}^\{\*\}\\right\|n^\{2\}\(\\log T\+1\)\\right\)\\sum\_\{k\\in\\mathcal\{A\}^\{\*\}\}\\Delta\_\{k\}

### A\.3Regret Bound for Simulated NSW UCB Gossip

NSW regret over agentsi∈\[N\]i\\in\[N\]over time stepst∈\[T\]t\\in\[T\]is given by

RT=∑i=1N∑t=1TNSW​\(p∗,μ¯\)−NSW​\(pit,μ¯\)R\_\{T\}=\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\-\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)whereμ¯j,k=1N​∑i=1Nμi,j,k∗\\bar\{\\mu\}\_\{j,k\}=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mu\_\{i,j,k\}^\{\*\}\. First, we will bound the regret incurred during the firstKKtime steps\.

∑i=1N∑t=1KNSW​\(p∗,μ¯\)−NSW​\(pit,μ¯\)≤N​K​NSW​\(p∗,μ¯\)=N​K\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{K\}\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\-\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\\leq NK\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)=NKsince rewards are restricted to the interval\[0,1\]\[0,1\]\. It suffices to consider regret incurred post warm up period\. We will bound the deviation between the global average and the centered arm mean using the decomposition

zi,j,k​\(t\)−μ¯j,k=\(zi,j,k​\(t\)−z¯j,k​\(t\)\)\+\(z¯j,k​\(t\)−μ¯j,k\)z\_\{i,j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}=\(z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\)\+\(\\bar\{z\}\_\{j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\)Note thatz¯j,k​\(t\)=1N​∑i=1Nzi,j,k​\(t\)\\bar\{z\}\_\{j,k\}\(t\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}z\_\{i,j,k\}\(t\)\. The first term in the decomposition represents the consensus error and the second term represents the sampling error\. We will bound each term separately with a series of lemmas\. In Lemma 1, we will draw a meaningful connection between the global averages and local averages\. In particular, we show that for allj∈\[N\]j\\in\[N\],k∈\[K\]k\\in\[K\], andt∈\[T\]t\\in\[T\]

z¯j,k​\(t\)=1N​∑i=1Nμ^i,j,k​\(t−1\)\\bar\{z\}\_\{j,k\}\(t\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)Consequently, we have thatzj,k​\(t\)z\_\{j,k\}\(t\)is an unbiased estimator ofμj,k\\mu\_\{j,k\}\. That is,𝔼​\[zj,k​\(t\)\]=1N​∑i=1N𝔼​\[μ^i,j,k​\(t−1\)\]=μ¯j,k\\mathbb\{E\}\[z\_\{j,k\}\(t\)\]=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\mathbb\{E\}\[\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\]=\\bar\{\\mu\}\_\{j,k\}\. Suppose thatzj,k​\(t\)z\_\{j,k\}\(t\)andΔ​μ^j,k​\(t\)=μ^j,k​\(t\)−μ^j,k​\(t\)\\Delta\\hat\{\\mu\}\_\{j,k\}\(t\)=\\hat\{\\mu\}\_\{j,k\}\(t\)\-\\hat\{\\mu\}\_\{j,k\}\(t\)are vectors inℝN\\mathbb\{R\}^\{N\}defined as expected\. We can rewrite the gossip update as

zj,k​\(t\+1\)=Wt​zj,k​\(t\)\+Δ​μ^j,k​\(t\)z\_\{j,k\}\(t\+1\)=W\_\{t\}z\_\{j,k\}\(t\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(t\)We can vectorize the centered global average asz¯j,k​\(t\)=1N​𝟙⊤​zj,k​\(t\)\\bar\{z\}\_\{j,k\}\(t\)=\\frac\{1\}\{N\}\\mathbbm\{1\}^\{\\top\}z\_\{j,k\}\(t\)making

z¯j,k​\(t\+1\)=1N​𝟙⊤​Wt​zj,k​\(t\)\+1N​𝟙⊤​Δ​μ^j,k​\(t\)\\bar\{z\}\_\{j,k\}\(t\+1\)=\\frac\{1\}\{N\}\\mathbbm\{1\}^\{\\top\}W\_\{t\}z\_\{j,k\}\(t\)\+\\frac\{1\}\{N\}\\mathbbm\{1\}^\{\\top\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(t\)SinceWtW\_\{t\}is doubly stochastic,

z¯j,k​\(t\+1\)=1N​𝟙⊤​zj,k​\(t\)\+1N​𝟙⊤​Δ​μ^j,k​\(t\)=z¯j,k​\(t\)\+1N​∑i=1NΔ​μ^i,j,k​\(t\)\\bar\{z\}\_\{j,k\}\(t\+1\)=\\frac\{1\}\{N\}\\mathbbm\{1\}^\{\\top\}z\_\{j,k\}\(t\)\+\\frac\{1\}\{N\}\\mathbbm\{1\}^\{\\top\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(t\)=\\bar\{z\}\_\{j,k\}\(t\)\+\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(t\)Unrolling the recursion we have

z¯j,k​\(t\)=z¯j,k​\(1\)\+1N​∑s=1t−1∑i=1NΔ​μ^i,j,k​\(s\)\\bar\{z\}\_\{j,k\}\(t\)=\\bar\{z\}\_\{j,k\}\(1\)\+\\frac\{1\}\{N\}\\sum\_\{s=1\}^\{t\-1\}\\sum\_\{i=1\}^\{N\}\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)By definition we also have that

μ^i,j,k​\(t−1\)=μ^i,j,k​\(0\)\+∑s=1t−1Δ​μ^i,j,k​\(s\)\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)=\\hat\{\\mu\}\_\{i,j,k\}\(0\)\+\\sum\_\{s=1\}^\{t\-1\}\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)making

1N​∑i=1Nμ^i,j,k​\(t−1\)=1N​∑i=1Nμ^i,j,k​\(0\)\+1N​∑s=1t−1∑i=1NΔ​μ^i,j,k​\(s\)\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(0\)\+\\frac\{1\}\{N\}\\sum\_\{s=1\}^\{t\-1\}\\sum\_\{i=1\}^\{N\}\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)Sincezi,j,k​\(1\)=μ^i,j,k​\(0\)=0z\_\{i,j,k\}\(1\)=\\hat\{\\mu\}\_\{i,j,k\}\(0\)=0, we know thatz¯j,k​\(1\)=1N​∑i=1Nμ^i,j,k​\(0\)\\bar\{z\}\_\{j,k\}\(1\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(0\)\. This allows us to concludez¯j,k​\(t\)=1N​∑i=1Nμ^i,j,k​\(t−1\)\\bar\{z\}\_\{j,k\}\(t\)=\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\. In Lemma 2, we bound the consensus error for alli,j∈\[N\]i,j\\in\[N\],k∈\[K\]k\\in\[K\], andt∈\[T\]t\\in\[T\]\. Assume that

∏τ=st−1Wτ=1N​𝟙𝟙⊤\+Es:t​where​‖Es:t‖2≤ρt−s<1\\prod\_\{\\tau=s\}^\{t\-1\}W\_\{\\tau\}=\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\+E\_\{s:t\}\\text\{ where \}\\left\\lVert E\_\{s:t\}\\right\\rVert\_\{2\}\\leq\\rho^\{t\-s\}<1We can unroll the gossip update forzj,k​\(t\+1\)z\_\{j,k\}\(t\+1\)\.

zj,k​\(1\)\\displaystyle z\_\{j,k\}\(1\)=0\\displaystyle=0zj,k​\(2\)\\displaystyle z\_\{j,k\}\(2\)=W1​zj,k​\(1\)\+Δ​μ^j,k​\(1\)=Δ​μ^j,k​\(1\)\\displaystyle=W\_\{1\}z\_\{j,k\}\(1\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(1\)=\\Delta\\hat\{\\mu\}\_\{j,k\}\(1\)zj,k​\(3\)\\displaystyle z\_\{j,k\}\(3\)=W2​zj,k​\(2\)\+Δ​μ^j,k​\(2\)=W2​Δ​μ^j,k​\(1\)\+Δ​μ^j,k​\(2\)\\displaystyle=W\_\{2\}z\_\{j,k\}\(2\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(2\)=W\_\{2\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(1\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(2\)zj,k​\(4\)\\displaystyle z\_\{j,k\}\(4\)=W3​zj,k​\(3\)\+Δ​μ^j,k​\(3\)=W3​W2​Δ​μ^j,k​\(1\)\+W3​Δ​μ^j,k​\(2\)\+Δ​μ^j,k​\(3\)\\displaystyle=W\_\{3\}z\_\{j,k\}\(3\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(3\)=W\_\{3\}W\_\{2\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(1\)\+W\_\{3\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(2\)\+\\Delta\\hat\{\\mu\}\_\{j,k\}\(3\)zj,k​\(t\)\\displaystyle z\_\{j,k\}\(t\)=∑s=1t−1\(∏τ=s\+1t−1Wt\)​Δ​μ^j,k​\(s\)\\displaystyle=\\sum\_\{s=1\}^\{t\-1\}\\left\(\\prod\_\{\\tau=s\+1\}^\{t\-1\}W\_\{t\}\\right\)\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)We will decompose∏τ=s\+1t−1Wτ=1N​𝟙𝟙⊤\+Es\+1:t​where​‖Wτ−1N​𝟙𝟙⊤‖2≤ρ\\prod\_\{\\tau=s\+1\}^\{t\-1\}W\_\{\\tau\}=\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\+E\_\{s\+1:t\}\\text\{ where \}\\left\\lVert W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\\right\\rVert\_\{2\}\\leq\\rhofor everyτ\\tau\. We now claim that

∏τ=s\+1t−1Wt−1N​𝟙𝟙⊤=∏τ=s\+1t−1\(Wt−1N​𝟙𝟙⊤\)\\prod\_\{\\tau=s\+1\}^\{t\-1\}W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}=\\prod\_\{\\tau=s\+1\}^\{t\-1\}\(W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)By induction, for the base caseτ=s\+1\\tau=s\+1we have thatWt−1N​𝟙𝟙⊤=Wt−1N​𝟙𝟙⊤W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}=W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\. For the inductive step, we prove that if the claim holds forτ=s\+m\\tau=s\+mform≥1m\\geq 1, it will hold forτ=s\+m\+1\\tau=s\+m\+1\. LettingPm=∏τ=s\+1s\+mWtP\_\{m\}=\\prod\_\{\\tau=s\+1\}^\{s\+m\}W\_\{t\},

∏τ=s\+1s\+m\+1Wt−1N​𝟙𝟙⊤=Pm​Ws\+m\+1−Pm​1N​𝟙𝟙⊤\+Pm​1N​𝟙𝟙⊤−1N​𝟙𝟙⊤=Pm​\(Ws\+m\+1−1N​𝟙𝟙⊤\)\\prod\_\{\\tau=s\+1\}^\{s\+m\+1\}W\_\{t\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}=P\_\{m\}W\_\{s\+m\+1\}\-P\_\{m\}\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\+P\_\{m\}\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}=P\_\{m\}\(W\_\{s\+m\+1\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)asPmP\_\{m\}is doubly stochastic\. By the inductive hypothesis,Pm−1N​𝟙𝟙⊤=∏τ=s\+1s\+m\(Wτ−1N​𝟙𝟙⊤\)P\_\{m\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}=\\prod\_\{\\tau=s\+1\}^\{s\+m\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)\. Substituting this result in forPmP\_\{m\},

Pm​\(Ws\+m\+1−1N​𝟙𝟙⊤\)\\displaystyle P\_\{m\}\(W\_\{s\+m\+1\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)=\(∏τ=s\+1s\+m\(Wτ−1N​𝟙𝟙⊤\)\+1N​𝟙𝟙⊤\)​\(Ws\+m\+1−1N​𝟙𝟙⊤\)\\displaystyle=\\left\(\\prod\_\{\\tau=s\+1\}^\{s\+m\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)\+\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\\right\)\(W\_\{s\+m\+1\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)=1N​𝟙𝟙⊤​\(Ws\+m\+1−1N​𝟙𝟙⊤\)\+∏τ=s\+1s\+m\+1\(Wτ−1N​𝟙𝟙⊤\)\\displaystyle=\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\(W\_\{s\+m\+1\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)\+\\prod\_\{\\tau=s\+1\}^\{s\+m\+1\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)=∏τ=s\+1s\+m\+1\(Wτ−1N​𝟙𝟙⊤\)\\displaystyle=\\prod\_\{\\tau=s\+1\}^\{s\+m\+1\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)As a result,

∥Es:t−1∥2=∥∏τ=s\+1t−1\(Wτ−1N𝟙𝟙⊤\)∥2≤∏τ=s\+1t−1\(Wτ−1N𝟙𝟙⊤≤ρt−s−1\\left\\lVert E\_\{s:t\-1\}\\right\\rVert\_\{2\}=\\left\\lVert\\prod\_\{\\tau=s\+1\}^\{t\-1\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\)\\right\\rVert\_\{2\}\\leq\\prod\_\{\\tau=s\+1\}^\{t\-1\}\(W\_\{\\tau\}\-\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\\leq\\rho^\{t\-s\-1\}Using the decomposition forWtW\_\{t\}we can rewritezj,k​\(t\)z\_\{j,k\}\(t\)\.

zj,k​\(t\)\\displaystyle z\_\{j,k\}\(t\)=1N​𝟙𝟙⊤​∑s=1t−1Δ​μ^j,k​\(s\)\+∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\\displaystyle=\\frac\{1\}\{N\}\\mathbbm\{1\}\\mathbbm\{1\}^\{\\top\}\\sum\_\{s=1\}^\{t\-1\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\+\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)=1N​𝟙​∑i=1N∑s=1t−1Δ​μ^i,j,k​\(s\)\+∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\\displaystyle=\\frac\{1\}\{N\}\\mathbbm\{1\}\\sum\_\{i=1\}^\{N\}\\sum\_\{s=1\}^\{t\-1\}\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)\+\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)=1N​𝟙​∑i=1Nμ^i,j,k​\(t−1\)\+∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\\displaystyle=\\frac\{1\}\{N\}\\mathbbm\{1\}\\sum\_\{i=1\}^\{N\}\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\+\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)=𝟙​μ¯j,k​\(t−1\)\+∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\\displaystyle=\\mathbbm\{1\}\\bar\{\\mu\}\_\{j,k\}\(t\-1\)\+\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)Applying the triangle inequality,

\|\[∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\]i\|≤∑s=1t−1‖Es:t‖2​‖Δ​μ^j,k​\(s\)‖∞\\left\|\\left\[\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\]\_\{i\}\\right\|\\leq\\sum\_\{s=1\}^\{t\-1\}\\left\\lVert E\_\{s:t\}\\right\\rVert\_\{2\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}Lemma 1 allows us to conclude,

\|zi,j,k​\(t\)−z¯j,k​\(t\)\|=\|\[∑s=1t−1Es:t​Δ​μ^j,k​\(s\)\]i\|≤∑s=1t−1‖Es:t‖2​‖Δ​μ^j,k​\(s\)‖∞≤∑s=1t−1ρt−s−1​‖Δ​μ^j,k​\(s\)‖∞\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\\right\|=\\left\|\\left\[\\sum\_\{s=1\}^\{t\-1\}E\_\{s:t\}\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\]\_\{i\}\\right\|\\leq\\sum\_\{s=1\}^\{t\-1\}\\left\\lVert E\_\{s:t\}\\right\\rVert\_\{2\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}\\leq\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}In Lemma 3, we determine an increment bound for‖Δ​μ^j,k​\(s\)‖∞\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}\. When an update occurs the local average

μ^i,j,k​\(s\)=Ti,j,k​\(s−1\)​μ^i,j,k​\(s−1\)\+Si,j​\(s\)Ti,j,k​\(s\)​where​Ti,j,k​\(s\)=Ti,j,k​\(s−1\)\+1\\hat\{\\mu\}\_\{i,j,k\}\(s\)=\\frac\{T\_\{i,j,k\}\(s\-1\)\\hat\{\\mu\}\_\{i,j,k\}\(s\-1\)\+S\_\{i,j\}\(s\)\}\{T\_\{i,j,k\}\(s\)\}\\text\{ where \}T\_\{i,j,k\}\(s\)=T\_\{i,j,k\}\(s\-1\)\+1WritingΔ​μ^i,j,k​\(s\)\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)in terms of this update

Δ​μ^i,j,k​\(s\)\\displaystyle\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)=μ^j,k​\(s\)−μ^j,k​\(s−1\)\\displaystyle=\\hat\{\\mu\}\_\{j,k\}\(s\)\-\\hat\{\\mu\}\_\{j,k\}\(s\-1\)=Ti,j,k​\(s−1\)​μ^i,j,k​\(s−1\)\+Si,j​\(s\)−Ti,j,k​\(s\)​μ^i,j,k​\(s−1\)Ti,j,k​\(s\)\\displaystyle=\\frac\{T\_\{i,j,k\}\(s\-1\)\\hat\{\\mu\}\_\{i,j,k\}\(s\-1\)\+S\_\{i,j\}\(s\)\-T\_\{i,j,k\}\(s\)\\hat\{\\mu\}\_\{i,j,k\}\(s\-1\)\}\{T\_\{i,j,k\}\(s\)\}=Si,j​\(s\)−μ^i,j,k​\(s−1\)Ti,j,k​\(s\)\\displaystyle=\\frac\{S\_\{i,j\}\(s\)\-\\hat\{\\mu\}\_\{i,j,k\}\(s\-1\)\}\{T\_\{i,j,k\}\(s\)\}This implies that

\|Δ​μ^i,j,k​\(s\)\|=\|Si,j​\(s\)−μ^i,j,k​\(s−1\)\|Ti,j,k​\(s\)≤1Ti,j,k​\(s\)\\left\|\\Delta\\hat\{\\mu\}\_\{i,j,k\}\(s\)\\right\|=\\frac\{\\left\|S\_\{i,j\}\(s\)\-\\hat\{\\mu\}\_\{i,j,k\}\(s\-1\)\\right\|\}\{T\_\{i,j,k\}\(s\)\}\\leq\\frac\{1\}\{T\_\{i,j,k\}\(s\)\}Therefore

‖Δ​μ^j,k​\(s\)‖∞≤maxi∈\[N\]⁡1Ti,j,k​\(s\)​and​\|zi,j,k​\(t\)−z¯j,k​\(t\)\|≤∑s=1t−1ρt−s−1​maxi∈\[N\]⁡1Ti,j,k​\(s\)\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}\\leq\\max\_\{i\\in\[N\]\}\\frac\{1\}\{T\_\{i,j,k\}\(s\)\}\\text\{ and \}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\\right\|\\leq\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\max\_\{i\\in\[N\]\}\\frac\{1\}\{T\_\{i,j,k\}\(s\)\}In the next series of lemmas we consider the sampling error for particulari,j∈\[N\]i,j\\in\[N\],k∈\[K\]k\\in\[K\], andt∈\[T\]t\\in\[T\]\. In Lemma 4, we relate the off\-diagonal counterTi,j,k​\(t\)T\_\{i,j,k\}\(t\)to its associated diagonal counterTi,i,k​\(t\)T\_\{i,i,k\}\(t\)\. In order forTi,j,kT\_\{i,j,k\}to increase, we must haveait=ka\_\{i\}^\{t\}=kandj∈𝒩i​\(t\)j\\in\\mathcal\{N\}\_\{i\}\(t\)\. Conditioning on the history of armsℱt=\{ai1,…,ait\}\\mathcal\{F\}\_\{t\}=\\\{a\_\{i\}^\{1\},\\dots,a\_\{i\}^\{t\}\\\},

Ti,j,k​\(t\)∼Binomial​\(Ti,i,k​\(t\),p\)T\_\{i,j,k\}\(t\)\\sim\\text\{Binomial\}\(T\_\{i,i,k\}\(t\),p\)where𝔼​\[Ti,j,k​\(t\)\]=p​Ti,i,k​\(t\)\\mathbb\{E\}\[T\_\{i,j,k\}\(t\)\]=pT\_\{i,i,k\}\(t\)\. Applying Chernoff’s bound

ℙ​\[Ti,j,k​\(t\)≤\(1−δ\)​p​Ti,i,k​\(t\)\]≤exp⁡\(−δ22​p​Ti,i,k​\(t\)\)\\mathbb\{P\}\[T\_\{i,j,k\}\(t\)\\leq\(1\-\\delta\)pT\_\{i,i,k\}\(t\)\]\\leq\\exp\\left\(\-\\frac\{\\delta^\{2\}\}\{2\}pT\_\{i,i,k\}\(t\)\\right\)Settingδ=12\\delta=\\frac\{1\}\{2\},

ℙ​\[Ti,j,k​\(t\)≤p2​Ti,i,k​\(t\)\]≤exp⁡\(−p​Ti,i,k​\(t\)8\)\\mathbb\{P\}\[T\_\{i,j,k\}\(t\)\\leq\\frac\{p\}\{2\}T\_\{i,i,k\}\(t\)\]\\leq\\exp\\left\(\-\\frac\{pT\_\{i,i,k\}\(t\)\}\{8\}\\right\)Defining a burn\-in periodτ=32​log⁡\(N2​K​T\)p\\tau=\\frac\{32\\log\(N^\{2\}KT\)\}\{p\}, forTi,i,k​\(t\)≥τT\_\{i,i,k\}\(t\)\\geq\\tau, we havep​Ti,i,k​\(t\)8≥4​log⁡\(N2​K​T\)\\frac\{pT\_\{i,i,k\}\(t\)\}\{8\}\\geq 4\\log\(N^\{2\}KT\)\. Therefore

ℙ​\[Ti,j,k​\(t\)≤p2​Ti,i,k​\(t\)\]≤exp⁡\(−4​log⁡\(N2​K​T\)\)=\(N2​K​T\)−4\\mathbb\{P\}\[T\_\{i,j,k\}\(t\)\\leq\\frac\{p\}\{2\}T\_\{i,i,k\}\(t\)\]\\leq\\exp\(\-4\\log\(N^\{2\}KT\)\)=\(N^\{2\}KT\)^\{\-4\}Taking a union bound overi,j∈\[N\]i,j\\in\[N\],k∈\[K\]k\\in\[K\], andt∈\[T\]t\\in\[T\],

ℙ\[∀i,j,k,t:Ti,j,k\(t\)≤p2Ti,i,k\(t\)\]≥1−N2KT⋅\(N2KT\)−4=1−\(N2KT\)−3\\mathbb\{P\}\[\\forall i,j,k,t:T\_\{i,j,k\}\(t\)\\leq\\frac\{p\}\{2\}T\_\{i,i,k\}\(t\)\]\\geq 1\-N^\{2\}KT\\cdot\(N^\{2\}KT\)^\{\-4\}=1\-\(N^\{2\}KT\)^\{\-3\}Additionally, we can identify a piecewise bound for the off\-diagonal counterTi,j,k​\(t\)T\_\{i,j,k\}\(t\)\.

1Ti,j,k​\(t\)≤\{2p⋅1Ti,i,k​\(t\)if​Ti,i,k​\(t\)≥τ1otherwise\\frac\{1\}\{\\sqrt\{T\_\{i,j,k\}\(t\)\}\}\\leq\\begin\{cases\}\\sqrt\{\\frac\{2\}\{p\}\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}&\\text\{if \}T\_\{i,i,k\}\(t\)\\geq\\tau\\\\ 1&\\text\{otherwise\}\\end\{cases\}In Lemma 5, we determine a local concentration bound on the local averages\. Suppose that the update times for agentiiestimating the value of armkkwith respect to agentjj’s preferences are given by the sequenceτ1,…,τm\\tau\_\{1\},\\dots,\\tau\_\{m\}whereτm=Ti,j,k​\(t\)\\tau\_\{m\}=T\_\{i,j,k\}\(t\)\. Then,

μ^i,j,k​\(t\)=1m​∑r=1mSi,j​\(τr\)\\hat\{\\mu\}\_\{i,j,k\}\(t\)=\\frac\{1\}\{m\}\\sum\_\{r=1\}^\{m\}S\_\{i,j\}\(\\tau\_\{r\}\)whereSi,j​\(τr\)∈\[0,1\]S\_\{i,j\}\(\\tau\_\{r\}\)\\in\[0,1\]are iid with𝔼​\[Si,j​\(τr\)\]=μi,j,k∗\\mathbb\{E\}\[S\_\{i,j\}\(\\tau\_\{r\}\)\]=\\mu\_\{i,j,k\}^\{\*\}\. By Hoeffding’s bound

ℙ​\[\|1m​∑r=1mSi,j​\(τr\)−μi,j,k∗\|≥ϵ\]≤2​exp⁡\(−2​m​ϵ2\)\\mathbb\{P\}\[\\left\|\\frac\{1\}\{m\}\\sum\_\{r=1\}^\{m\}S\_\{i,j\}\(\\tau\_\{r\}\)\-\\mu\_\{i,j,k\}^\{\*\}\\right\|\\geq\\epsilon\]\\leq 2\\exp\(\-2m\\epsilon^\{2\}\)Settingϵ=C​log⁡\(N2​K​t\)m\\epsilon=C\\sqrt\{\\frac\{\\log\(N^\{2\}Kt\)\}\{m\}\},

2​exp⁡\(−2​m​ϵ2\)=2​exp⁡\(−2​C2​log⁡\(N2​K​t\)\)=2​\(N2​K​t\)−2​C22\\exp\(\-2m\\epsilon^\{2\}\)=2\\exp\(\-2C^\{2\}\\log\(N^\{2\}Kt\)\)=2\(N^\{2\}Kt\)^\{\-2C^\{2\}\}We can choose aCCsuch that with probability at least1−\(N2​K​t\)−31\-\(N^\{2\}Kt\)^\{\-3\},

\|μ^i,j,k​\(t\)−μi,j,k∗\|≤C​log⁡\(N2​K​t\)Ti,j,k​\(t\)\\left\|\\hat\{\\mu\}\_\{i,j,k\}\(t\)\-\\mu\_\{i,j,k\}^\{\*\}\\right\|\\leq C\\sqrt\{\\frac\{\\log\(N^\{2\}Kt\)\}\{T\_\{i,j,k\}\(t\)\}\}In Lemma 6, we derive a bound for the sampling error\. Using Lemma 1,

\|z¯j,k​\(t\)−μ¯j,k\|=\|1N​∑i=1N\(μ^i,j,k​\(t−1\)−μi,j,k∗\)\|\\left\|\\bar\{z\}\_\{j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|=\\left\|\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\(\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\-\\mu\_\{i,j,k\}^\{\*\}\)\\right\|By the triangle inequality,

\|1N​∑i=1N\(μ^i,j,k​\(t−1\)−μi,j,k∗\)\|≤1N​∑i=1N\|μ^i,j,k​\(t−1\)−μi,j,k∗\|\\left\|\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\(\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\-\\mu\_\{i,j,k\}^\{\*\}\)\\right\|\\leq\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\left\|\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\-\\mu\_\{i,j,k\}^\{\*\}\\right\|Using Lemma 5, with probability at least1−\(N2​K​t\)−31\-\(N^\{2\}Kt\)^\{\-3\},

1N​∑i=1N\|μ^i,j,k​\(t−1\)−μi,j,k∗\|≤1N​∑i=1NC​log⁡\(N​K​t\)Ti,j,k​\(t−1\)\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}\\left\|\\hat\{\\mu\}\_\{i,j,k\}\(t\-1\)\-\\mu\_\{i,j,k\}^\{\*\}\\right\|\\leq\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}C\\sqrt\{\\frac\{\\log\(NKt\)\}\{T\_\{i,j,k\}\(t\-1\)\}\}Applying Lemma 4, with probability at least1−\(N2​K​t\)−31\-\(N^\{2\}Kt\)^\{\-3\},

1N​∑i=1NC​log⁡\(N​K​t\)Ti,j,k​\(t−1\)≤C​log⁡\(N​K​t\)N​\(∑i=1N2p⋅1Ti,i,k​\(t−1\)\+𝟙Ti,i,k​\(t−1\)<τ\)\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}C\\sqrt\{\\frac\{\\log\(NKt\)\}\{T\_\{i,j,k\}\(t\-1\)\}\}\\leq\\frac\{C\\sqrt\{\\log\(NKt\)\}\}\{N\}\\left\(\\sum\_\{i=1\}^\{N\}\\sqrt\{\\frac\{2\}\{p\}\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\-1\)\}\}\+\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}\\right\)Now that we have developed bounds for consensus and sampling error, it remains to relate these errors to NSW regret\. To make this connection, we first show a preliminary fact\. Suppose that we have sequencesa1,…,aNa\_\{1\},\\dots,a\_\{N\}andb1,…,bNb\_\{1\},\\dots,b\_\{N\}\. We also introduce setsV1,…,VNV\_\{1\},\\dots,V\_\{N\}such thatVj=\{a1,…​aj,bj\+1,…​bN\}V\_\{j\}=\\\{a\_\{1\},\\dots a\_\{j\},b\_\{j\+1\},\\dots b\_\{N\}\\\}\. Using the construction

∏j=1Naj−∏j=1Nbj=∏u∈VNu−∏v∈V0v\\prod\_\{j=1\}^\{N\}a\_\{j\}\-\\prod\_\{j=1\}^\{N\}b\_\{j\}=\\prod\_\{u\\in V\_\{N\}\}u\-\\prod\_\{v\\in V\_\{0\}\}vWe can equate the following expression to a certain telescoping sum

∏u∈VNu−∏v∈V0v=∑j=1N\(∏u∈Vju−∏v∈Vj−1v\)\\prod\_\{u\\in V\_\{N\}\}u\-\\prod\_\{v\\in V\_\{0\}\}v=\\sum\_\{j=1\}^\{N\}\\left\(\\prod\_\{u\\in V\_\{j\}\}u\-\\prod\_\{v\\in V\_\{j\-1\}\}v\\right\)Notice the two products within the telescoping sum share the same factors expect foraja\_\{j\}andbjb\_\{j\}\. The shared terms can be factored out resulting in

∑j=1N\(∏u∈Vju−∏v∈Vj−1v\)=∑j=1N∏l<jal​∏l\>jbl​\(aj−bj\)\\sum\_\{j=1\}^\{N\}\\left\(\\prod\_\{u\\in V\_\{j\}\}u\-\\prod\_\{v\\in V\_\{j\-1\}\}v\\right\)=\\sum\_\{j=1\}^\{N\}\\prod\_\{l<j\}a\_\{l\}\\prod\_\{l\>j\}b\_\{l\}\(a\_\{j\}\-b\_\{j\}\)From here, we can rewrite the NSW regret in term of deviations between the global averages and the centered arm means\. Letui,jtu\_\{i,j\}^\{t\}be the utility for thejjth agent with respect to the global averages anduj∗u\_\{j\}^\{\*\}be the utility for thejjth agent with respect to the centered arm means\.

\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|\\displaystyle\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|=\|∑j=1N\(uj∗−ui,jt\)​∏l<jul∗​∏l\>jui,jt\|\\displaystyle=\\left\|\\sum\_\{j=1\}^\{N\}\(u\_\{j\}^\{\*\}\-u\_\{i,j\}^\{t\}\)\\prod\_\{l<j\}u\_\{l\}^\{\*\}\\prod\_\{l\>j\}u\_\{i,j\}^\{t\}\\right\|≤∑j=1N\|uj∗−ui,jt\|​∏l<j\|ul∗\|​∏l\>j\|ui,jt\|\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\left\|u\_\{j\}^\{\*\}\-u\_\{i,j\}^\{t\}\\right\|\\prod\_\{l<j\}\\left\|u\_\{l\}^\{\*\}\\right\|\\prod\_\{l\>j\}\\left\|u\_\{i,j\}^\{t\}\\right\|≤∑j=1N\|uj∗−ui,jt\|\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\left\|u\_\{j\}^\{\*\}\-u\_\{i,j\}^\{t\}\\right\|≤∑j=1N∑k=1Kpk​\|zi,j,k​\(t\)−μ¯j,k\|\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|This result allows us to bound the deviation between the NSW under the centered arm means and the NSW under the global average matrix of agentii\. For anyp∈ΔKp\\in\\Delta\_\{K\},

\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|\\displaystyle\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|≤∑j=1N∑k=1Kpk​\|zi,j,k​\(t\)−μ¯j,k\|\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|≤∑j=1N∑k=1Kpk​\|zi,j,k​\(t\)−z¯j,k​\(t\)\|\+\|z¯j,k​\(t\)−μ¯j,k\|\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\\right\|\+\\left\|\\bar\{z\}\_\{j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|Focusing on the sampling error term, applying Lemma 6

∑j=1N∑k=1Kpk​\|z¯j,k​\(t\)−μ¯j,k\|\\displaystyle\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|\\bar\{z\}\_\{j,k\}\(t\)\-\\bar\{\\mu\}\_\{j,k\}\\right\|≤∑j=1N∑k=1Kpk​C​log⁡\(N​K​t\)N​\(∑i′=1N2p⋅1Ti′,i′,k​\(t−1\)\+𝟙Ti′,i′,k​\(t−1\)<τ\)\\displaystyle\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\frac\{C\\sqrt\{\\log\(NKt\)\}\}\{N\}\\left\(\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sqrt\{\\frac\{2\}\{p\}\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)\}\}\+\\mathbbm\{1\}\_\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)<\\tau\}\\right\)=C​log⁡\(N​K​t\)​∑i′=1N∑k=1Kpk​\(2p⋅1Ti′,i′,k​\(t−1\)\+𝟙Ti′,i′,k​\(t−1\)<τ\)\\displaystyle=C\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\(\\sqrt\{\\frac\{2\}\{p\}\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)\}\}\+\\mathbbm\{1\}\_\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)<\\tau\}\\right\)=C​log⁡\(N​K​t\)​\(∑i′=1N∑k=1Kpk​2p⋅1Ti′,i′,k​\(t−1\)\+∑i′=1N∑k=1Kpk​𝟙Ti′,i′,k​\(t−1\)<τ\)\\displaystyle=C\\sqrt\{\\log\(NKt\)\}\\left\(\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sqrt\{\\frac\{2\}\{p\}\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)\}\}\+\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\mathbbm\{1\}\_\{T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)<\\tau\}\\right\)Choosingi=arg mini∗∈\[N\]​Ti′,i′,k​\(t−1\)i=\\text\{arg\\,min\}\_\{i^\{\*\}\\in\[N\]\}T\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\-1\)and using that indicators variables are at most one, we obtain the simplified bound

C​N​log⁡\(N​K​t\)​\(2p​∑k=1Kpk⋅1Ti,i,k​\(t−1\)\+𝟙Ti,i,k​\(t−1\)<τ\)CN\\sqrt\{\\log\(NKt\)\}\\left\(\\sqrt\{\\frac\{2\}\{p\}\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\-1\)\}\}\+\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}\\right\)Looking at the consensus error term and applying Lemma 3,

∑j=1N∑k=1Kpk​\|zi,j,k​\(t\)−z¯j,k​\(t\)\|≤∑j=1N∑k=1Kpk​∑s=1t−1ρt−s−1​‖Δ​μ^j,k​\(s\)‖∞\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\left\|z\_\{i,j,k\}\(t\)\-\\bar\{z\}\_\{j,k\}\(t\)\\right\|\\leq\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}Combining our two results,

\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|≤C​N​log⁡\(N​K​t\)​2p​∑k=1Kpk⋅1Ti,i,k​\(t−1\)\+Γt−1\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|\\leq CN\\sqrt\{\\log\(NKt\)\}\\sqrt\{\\frac\{2\}\{p\}\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\-1\)\}\}\+\\Gamma\_\{t\-1\}where

Γt−1=C​N​log⁡\(N​K​t\)​∑k=1Kpk​𝟙Ti,i,k​\(t−1\)<τ\+∑j=1N∑k=1Kpk​∑s=1t−1ρt−s−1​‖Δ​μ^j,k​\(s\)‖∞\\Gamma\_\{t\-1\}=CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}\+\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}For simplicity, we can rewrite the sampling error in terms ofTi,i,k​\(t\)T\_\{i,i,k\}\(t\)instead ofTi,i,k​\(t−1\)T\_\{i,i,k\}\(t\-1\)\. In the worst case, we haveTi,i,k​\(t\)=Ti,i,k​\(t−1\)\+1T\_\{i,i,k\}\(t\)=T\_\{i,i,k\}\(t\-1\)\+1\. ForTi,i,k​\(t\)≥2T\_\{i,i,k\}\(t\)\\geq 2, we can show that

1Ti,i,k​\(t−1\)≤2Ti,i,k​\(t\)\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\-1\)\}\}\\leq\\frac\{\\sqrt\{2\}\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}We can rewrite the bound as

\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|≤2​C​Np​log⁡\(N​K​t\)​∑k=1Kpk⋅1Ti,i,k​\(t\)\+Γt−1\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|\\leq\\frac\{2CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKt\)\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\cdot\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\+\\Gamma\_\{t\-1\}In Lemma 7 we construct a clean eventCitC\_\{i\}^\{t\}\.

Cit=\{p∈ΔK:\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|≤αt​∑k=1Kpk​log⁡\(N​K​t\)Ti,i,k​\(t\)\+Γt−1\}C\_\{i\}^\{t\}=\\\{p\\in\\Delta\_\{K\}:\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|\\leq\\alpha\_\{t\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sqrt\{\\frac\{\\log\(NKt\)\}\{T\_\{i,i,k\}\(t\)\}\}\+\\Gamma\_\{t\-1\}\\\}whereαt=C​Np\\alpha\_\{t\}=\\frac\{CN\}\{\\sqrt\{p\}\}collapsing2​C2CintoCC\. Applying Lemma 6,ℙ​\[Cit\]≥1−O​\(\(N2​K​T\)−3\)\\mathbb\{P\}\[C\_\{i\}^\{t\}\]\\geq 1\-O\(\(N^\{2\}KT\)^\{\-3\}\)\. The sampling error resembles the explore term in the UCB objective\. Now, we relate the bound for\|NSW​\(p,μ¯\)−NSW​\(p,zi​\(t\)\)\|\\left\|\\text\{NSW\}\(p,\\bar\{\\mu\}\)\-\\text\{NSW\}\(p,z\_\{i\}\(t\)\)\\right\|to a bound for\|NSW​\(p∗,μ¯\)−NSW​\(pit,μ¯\)\|\\left\|\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\-\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\\right\|the deviation of interest for regret\. For the sake of clarity, we set

explore1​\(p\)=αt​∑k=1Kpk​log⁡\(N​K​t\)Ti,i,k​\(t\)\\text\{explore\}\_\{1\}\(p\)=\\alpha\_\{t\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sqrt\{\\frac\{\\log\(NKt\)\}\{T\_\{i,i,k\}\(t\)\}\}We also break upΓt−1\\Gamma\_\{t\-1\}so that

explore2​\(p\)=C​N​log⁡\(N​K​t\)​∑k=1Kpk​𝟙Ti,i,k​\(t−1\)<τ\\text\{explore\}\_\{2\}\(p\)=CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}and

cons​\(p\)=∑j=1N∑k=1Kpk​∑s=1t−1ρt−s−1​‖Δ​μ^j,k​\(s\)‖∞\\text\{cons\}\(p\)=\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}We can relateNSW​\(p∗,μ^\)\\text\{NSW\}\(p^\{\*\},\\hat\{\\mu\}\)toNSW​\(p∗,zi​\(t\)\)\\text\{NSW\}\(p^\{\*\},z\_\{i\}\(t\)\)with the clean event in Lemma 7\.

NSW​\(p∗,μ¯\)≤NSW​\(p∗,zi​\(t\)\)\+sample1​\(p∗\)\+sample2​\(p∗\)\+cons​\(p∗\)\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\\leq\\text\{NSW\}\(p^\{\*\},z\_\{i\}\(t\)\)\+\\text\{sample\}\_\{1\}\(p^\{\*\}\)\+\\text\{sample\}\_\{2\}\(p^\{\*\}\)\+\\text\{cons\}\(p^\{\*\}\)Next, we relateNSW​\(p∗,zi​\(t\)\)\\text\{NSW\}\(p^\{\*\},z\_\{i\}\(t\)\)toNSW​\(pit,zi​\(t\)\)\\text\{NSW\}\(p\_\{i\}^\{t\},z\_\{i\}\(t\)\)using the fact that our algorithm optimizes the objective function\.

NSW​\(p∗,zi​\(t\)\)\+sample1​\(p∗\)≤NSW​\(pit,zi​\(t\)\)\+sample1​\(pit\)\\text\{NSW\}\(p^\{\*\},z\_\{i\}\(t\)\)\+\\text\{sample\}\_\{1\}\(p^\{\*\}\)\\leq\\text\{NSW\}\(p\_\{i\}^\{t\},z\_\{i\}\(t\)\)\+\\text\{sample\}\_\{1\}\(p\_\{i\}^\{t\}\)Finally, we can relateNSW​\(pit,μ^\)\\text\{NSW\}\(p\_\{i\}^\{t\},\\hat\{\\mu\}\)toNSW​\(pit,zi​\(t\)\)\\text\{NSW\}\(p\_\{i\}^\{t\},z\_\{i\}\(t\)\)with the clean event in Lemma 7\.

NSW​\(pit,zi​\(t\)\)≤NSW​\(pit,μ¯\)\+sample1​\(pit\)\+sample2​\(pit\)\+cons​\(pit\)\\text\{NSW\}\(p\_\{i\}^\{t\},z\_\{i\}\(t\)\)\\leq\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\+\\text\{sample\}\_\{1\}\(p\_\{i\}^\{t\}\)\+\\text\{sample\}\_\{2\}\(p\_\{i\}^\{t\}\)\+\\text\{cons\}\(p\_\{i\}^\{t\}\)Chaining inequalities, we can relateNSW​\(p∗,μ¯\)\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)toNSW​\(pit,μ¯\)\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\.

NSW​\(p∗,μ¯\)≤NSW​\(pit,μ¯\)\+sample2​\(p∗\)\+cons​\(p∗\)\+2​sample1​\(pit\)\+sample2​\(pit\)\+cons​\(pit\)\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\\leq\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\+\\text\{sample\}\_\{2\}\(p^\{\*\}\)\+\\text\{cons\}\(p^\{\*\}\)\+2\\text\{sample\}\_\{1\}\(p\_\{i\}^\{t\}\)\+\\text\{sample\}\_\{2\}\(p\_\{i\}^\{t\}\)\+\\text\{cons\}\(p\_\{i\}^\{t\}\)Thus, we can reformulate NSW regret in term of the sample and consensus errors\.

RT=∑i=1N∑t=1TNSW​\(p∗,μ¯\)−NSW​\(pit,μ¯\)≤∑i=1N∑t=1Tsample2​\(p∗\)\+cons​\(p∗\)\+2​sample1​\(pit\)\+sample2​\(pit\)\+cons​\(pit\)R\_\{T\}=\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{NSW\}\(p^\{\*\},\\bar\{\\mu\}\)\-\\text\{NSW\}\(p\_\{i\}^\{t\},\\bar\{\\mu\}\)\\leq\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{sample\}\_\{2\}\(p^\{\*\}\)\+\\text\{cons\}\(p^\{\*\}\)\+2\\text\{sample\}\_\{1\}\(p\_\{i\}^\{t\}\)\+\\text\{sample\}\_\{2\}\(p\_\{i\}^\{t\}\)\+\\text\{cons\}\(p\_\{i\}^\{t\}\)We bound each of the error terms individually starting with the sampling error 1\. Before proceeding, in Lemma 8, we will prove a helpful result which bounds with high probability the time an arm counter stays at a specific value\. Fix an agentiiand armkk\. We are interested in the count for agentiipulling armkk,Ti,i,k​\(t\)T\_\{i,i,k\}\(t\)\. LetSs:u=∑t=supi,ktS\_\{s:u\}=\\sum\_\{t=s\}^\{u\}p\_\{i,k\}^\{t\}be the sum of the probability that agentiipulls armkkfrom timesstouu\. SupposeEs:uE\_\{s:u\}is the event that armkkis not pulled in the time frame fromsstouu\. Conditioning on the history of arm pulls,ℙ​\[ait≠k\|ℱt−1\]=1−pi,kt\\mathbb\{P\}\[a\_\{i\}^\{t\}\\neq k\|\\mathcal\{F\}\_\{t\-1\}\]=1\-p\_\{i,k\}^\{t\}\. Leveraging independenceℙ​\[Es:u\]=∏t=su\(1−pi,kt\)\\mathbb\{P\}\[E\_\{s:u\}\]=\\prod\_\{t=s\}^\{u\}\(1\-p\_\{i,k\}^\{t\}\)\. Using the identity1−x≤e−x1\-x\\leq e^\{\-x\}we can bound the probability

ℙ​\[Es:u\]=∏t=su\(1−pi,kt\)≤exp⁡\(−∑t=supi,kt\)=e−Ss:u\\mathbb\{P\}\[E\_\{s:u\}\]=\\prod\_\{t=s\}^\{u\}\(1\-p\_\{i,k\}^\{t\}\)\\leq\\exp\(\-\\sum\_\{t=s\}^\{u\}p\_\{i,k\}^\{t\}\)=e^\{\-S\_\{s:u\}\}Letτl\\tau\_\{l\}be the first timeTi,i,k​\(t\)=lT\_\{i,i,k\}\(t\)=landIl=\[τl,τl\+1−1\]I\_\{l\}=\[\\tau\_\{l\},\\tau\_\{l\+1\}\-1\], the interval thatTi,i,k​\(t\)=lT\_\{i,i,k\}\(t\)=l\. Suppose thatAl=∑t∈Ilpi,ktA\_\{l\}=\\sum\_\{t\\in I\_\{l\}\}p\_\{i,k\}^\{t\}is the sum of the probability that agentiipulls armkkwhenTi,i,k​\(t\)=lT\_\{i,i,k\}\(t\)=l\. Using the previous result,

ℙ​\[Al≥B​log⁡T\]≤e−Al≤e−B​log⁡T=T−B\\mathbb\{P\}\[A\_\{l\}\\geq B\\log T\]\\leq e^\{\-A\_\{l\}\}\\leq e^\{\-B\\log T\}=T^\{\-B\}Union bounding theTTphase for all counters settingB≥3B\\geq 3

ℙ\[∃l:Al≥BlogT\]≤T⋅T−B=T1−B\\mathbb\{P\}\[\\exists l:A\_\{l\}\\geq B\\log T\]\\leq T\\cdot T^\{\-B\}=T^\{1\-B\}ℙ\[∀l:Al≤BlogT\]≥1−T−2\\mathbb\{P\}\[\\forall l:A\_\{l\}\\leq B\\log T\]\\geq 1\-T^\{\-2\}We will split the bound of sampling error 1 into a warm up regime and an asymptotic regime\.

∑i′=1N∑t=1Tsample1​\(pi′t\)\\displaystyle\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{sample\}\_\{1\}\(p\_\{i^\{\\prime\}\}^\{t\}\)≤C​Np​log⁡\(N​K​T\)​∑i′=1N∑t=1T∑k=1Kpi′,kt​1Ti,i,k​\(t\)\\displaystyle\\leq\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\sum\_\{k=1\}^\{K\}p\_\{i^\{\\prime\},k\}^\{t\}\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}=C​Np​log⁡\(N​K​T\)​∑i′=1N∑k=1K∑t=1Tpi′,kt​1Ti,i,k​\(t\)\\displaystyle=\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\sum\_\{t=1\}^\{T\}p\_\{i^\{\\prime\},k\}^\{t\}\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}≤C​Np​log⁡\(N​K​T\)​∑i′=1N∑k=1K\(∑t:∑pi′,kt<B​τ​log⁡Tpi′,kt​1Ti,i,k​\(t\)\+∑t:∑pi′,kt≥B​τ​log⁡Tpi′,kt​1Ti,i,k​\(t\)\)\\displaystyle\\leq\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\left\(\\sum\_\{t:\\sum p\_\{i^\{\\prime\},k\}^\{t\}<B\\tau\\log T\}p\_\{i^\{\\prime\},k\}^\{t\}\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\+\\sum\_\{t:\\sum p\_\{i^\{\\prime\},k\}^\{t\}\\geq B\\tau\\log T\}p\_\{i^\{\\prime\},k\}^\{t\}\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\\right\)≤C​Np​log⁡\(N​K​T\)​∑i′=1N∑k=1K\(∑l=1τAl⋅1l\+1τ​∑t=1Tpi′,kt\)\\displaystyle\\leq\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\left\(\\sum\_\{l=1\}^\{\\tau\}A\_\{l\}\\cdot\\frac\{1\}\{l\}\+\\frac\{1\}\{\\sqrt\{\\tau\}\}\\sum\_\{t=1\}^\{T\}p\_\{i^\{\\prime\},k\}^\{t\}\\right\)≤C​Np​log⁡\(N​K​T\)​∑i′=1N∑k=1K\(B​τ​log⁡T\+Tτ\)\\displaystyle\\leq\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\left\(B\\tau\\log T\+\\frac\{T\}\{\\sqrt\{\\tau\}\}\\right\)=C​Np​log⁡\(N​K​T\)​\(N​K​O​\(T3/4\)\)\\displaystyle=\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\(NKO\(T^\{3/4\}\)\)In the last step, we optimizeτ\\tauby setting it toT\\sqrt\{T\}\. Note that in the sum over the warm up and asymptotic regime we have arm probability of agenti′i^\{\\prime\}times a term involving the counter for agentii, the agent with the lowest counter\. We reconcile this in the warm up regime by applying the trivial bound1Ti,i,k​\(t\)≤1\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\\leq 1and we can bound the sum of arm probabilities for agenti′i^\{\\prime\}byB​log⁡TB\\log Tusing Lemma 8\. In the asymptotic regime, note that for alli′i^\{\\prime\},Ti′,i′,k​\(t\)≥τT\_\{i^\{\\prime\},i^\{\\prime\},k\}\(t\)\\geq\\tauby a converse argument that can proven in the same spirit as Lemma 8\. Therefore,1Ti,i,k​\(t\)≤1τ\\frac\{1\}\{\\sqrt\{T\_\{i,i,k\}\(t\)\}\}\\leq\\frac\{1\}\{\\sqrt\{\\tau\}\}\. To boundsample2​\(pit\)\\text\{sample\}\_\{2\}\(p\_\{i\}^\{t\}\), we follow a similar structure to the previous bound relying on Lemma 8\.

∑i′=1N∑t=1Tsample2​\(pi′t\)\\displaystyle\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{sample\}\_\{2\}\(p\_\{i^\{\\prime\}\}^\{t\}\)≤C​N​log⁡\(N​K​t\)​∑i′=1N∑t=1T∑k=1Kpi′,kt​𝟙Ti,i,k​\(t−1\)<τ\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\sum\_\{k=1\}^\{K\}p\_\{i^\{\\prime\},k\}^\{t\}\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}≤C​N​log⁡\(N​K​t\)​∑i′=1N∑k=1K∑t=1Tpi′,kt​𝟙t:∑pi,kt<B​τ​log⁡T\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\sum\_\{t=1\}^\{T\}p\_\{i^\{\\prime\},k\}^\{t\}\\mathbbm\{1\}\_\{t:\\sum p\_\{i,k\}^\{t\}<B\\tau\\log T\}≤C​N​log⁡\(N​K​t\)​∑i′=1N∑k=1K∑l=1τAl\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\sum\_\{l=1\}^\{\\tau\}A\_\{l\}≤C​N​log⁡\(N​K​t\)​∑i′=1N∑k=1KB​τ​log⁡T\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}B\\tau\\log T=C​N​log⁡\(N​K​t\)​\(N​K​O​\(log2⁡T\)\)\\displaystyle=CN\\sqrt\{\\log\(NKt\)\}\(NKO\(\\log^\{2\}T\)\)To optimize the bound we chooseτ=log⁡T\\tau=\\log T\. We apply the same argument tosample2​\(p∗\)\\text\{sample\}\_\{2\}\(p^\{\*\}\)\.

∑i′=1N∑t=1Tsample2​\(p∗\)\\displaystyle\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{sample\}\_\{2\}\(p^\{\*\}\)≤C​N​log⁡\(N​K​t\)​∑i′=1N∑t=1T∑k=1Kpk∗​𝟙Ti,i,k​\(t−1\)<τ\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\sum\_\{k=1\}^\{K\}p\_\{k\}^\{\*\}\\mathbbm\{1\}\_\{T\_\{i,i,k\}\(t\-1\)<\\tau\}≤C​N​log⁡\(N​K​t\)​∑i′=1N∑t=1T𝟙t:∑pi,kt<B​τ​log⁡T\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\mathbbm\{1\}\_\{t:\\sum p\_\{i,k\}^\{t\}<B\\tau\\log T\}≤C​N​log⁡\(N​K​t\)​∑i′=1N∑k=1Kτ\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\\sum\_\{i^\{\\prime\}=1\}^\{N\}\\sum\_\{k=1\}^\{K\}\\tau≤C​N​log⁡\(N​K​t\)​\(N​K​O​\(log⁡T\)\)\\displaystyle\\leq CN\\sqrt\{\\log\(NKt\)\}\(NKO\(\\log T\)\)Finally, we boundcons​\(pit\)\\text\{cons\}\(p\_\{i\}^\{t\}\)andcons​\(p∗\)\\text\{cons\}\(p^\{\*\}\)\. As we observe later, we need not differentiate betweenpitp\_\{i\}^\{t\}andp∗p^\{\*\}\.

∑i=1N∑t=1Tcons​\(p\)\\displaystyle\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\text\{cons\}\(p\)≤∑i=1N∑t=1T∑j=1N∑k=1Kpk​∑s=1t−1ρt−s−1​‖Δ​μ^j,k​\(s\)‖∞\\displaystyle\\leq\\sum\_\{i=1\}^\{N\}\\sum\_\{t=1\}^\{T\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{t\-1\}\\rho^\{t\-s\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}=∑i=1N∑j=1N∑k=1Kpk​∑s=1T−1‖Δ​μ^j,k​\(s\)‖∞​∑t=s\+1Tρt−s−1\\displaystyle=\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{T\-1\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}\\sum\_\{t=s\+1\}^\{T\}\\rho^\{t\-s\-1\}≤11−ρ​∑i=1N∑j=1N∑k=1Kpk​∑s=1T‖Δ​μ^j,k​\(s\)‖∞\\displaystyle\\leq\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{s=1\}^\{T\}\\left\\lVert\\Delta\\hat\{\\mu\}\_\{j,k\}\(s\)\\right\\rVert\_\{\\infty\}≤11−ρ​∑i=1N∑j=1N∑k=1Kpk​∑l=1N∑s=1T\|Δ​μ^l,j,k​\(s\)\|\\displaystyle\\leq\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{l=1\}^\{N\}\\sum\_\{s=1\}^\{T\}\\left\|\\Delta\\hat\{\\mu\}\_\{l,j,k\}\(s\)\\right\|Froms=1s=1toTT,\|Δ​μ^l,j,k​\(s\)\|\>0\\left\|\\Delta\\hat\{\\mu\}\_\{l,j,k\}\(s\)\\right\|\>0exactlyTl,j,k​\(T\)T\_\{l,j,k\}\(T\)instances\. For1≤n≤Tl,j,k​\(t\)1\\leq n\\leq T\_\{l,j,k\}\(t\),\|Δ​μ^l,j,k​\(s\)\|≤1n\\left\|\\Delta\\hat\{\\mu\}\_\{l,j,k\}\(s\)\\right\|\\leq\\frac\{1\}\{n\}by Lemma 3\.

11−ρ​∑i=1N∑j=1N∑k=1Kpk​∑l=1N∑s=1T\|Δ​μ^l,j,k​\(s\)\|\\displaystyle\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{l=1\}^\{N\}\\sum\_\{s=1\}^\{T\}\\left\|\\Delta\\hat\{\\mu\}\_\{l,j,k\}\(s\)\\right\|≤11−ρ​∑i=1N∑j=1N∑k=1Kpk​∑l=1N∑n=1Tl,j,k​\(T\)1n\\displaystyle\\leq\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{l=1\}^\{N\}\\sum\_\{n=1\}^\{T\_\{l,j,k\}\(T\)\}\\frac\{1\}\{n\}≤11−ρ​∑i=1N∑j=1N∑k=1Kpk​∑l=1N\(log⁡T\+1\)\\displaystyle\\leq\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\\sum\_\{l=1\}^\{N\}\(\\log T\+1\)=11−ρ​∑i=1N∑j=1N∑k=1Kpk​\(N​\(log⁡T\+1\)\)\\displaystyle=\\frac\{1\}\{1\-\\rho\}\\sum\_\{i=1\}^\{N\}\\sum\_\{j=1\}^\{N\}\\sum\_\{k=1\}^\{K\}p\_\{k\}\(N\(\\log T\+1\)\)=N31−ρ​\(log⁡T\+1\)\\displaystyle=\\frac\{N^\{3\}\}\{1\-\\rho\}\(\\log T\+1\)Combining all error terms, we observe that thesample1​\(pi′t\)\\text\{sample\}\_\{1\}\(p\_\{i^\{\\prime\}\}^\{t\}\)term dominates regret\. Thus, our final bound on NSW regret is

RT≤O​\(C​Np​log⁡\(N​K​T\)​\(N​K​O​\(T3/4\)\)\)R\_\{T\}\\leq O\(\\frac\{CN\}\{\\sqrt\{p\}\}\\sqrt\{\\log\(NKT\)\}\(NKO\(T^\{3/4\}\)\)\)

### A\.4Experimental Reproducibility Details

Experiments were run on a Dell XPS 13 \(9315\) with a 12th Gen Intel Core i7\-1250U CPU \(1\.10 GHz\) and 32 GB RAM\. All code was executed in Jupyter Notebook environments, with runtimes of approximately 2 hours and 1\.5 hours for the two experimental settings\. To facilitate reproducibility, the source code is available in an anonymized GitHub repository:[https://anonymous\.4open\.science/r/Pareto\-NSW\-MO\-MA\-MAB\-Experiments\-04FC/](https://anonymous.4open.science/r/Pareto-NSW-MO-MA-MAB-Experiments-04FC/)\.