Year: 2020

Abstract:
We study the problem of regret minimization for distributed bandits learning, in which M agents work collaboratively to minimize their total regret under the coordination of a central server. Our goal is to design communication protocols with near-optimal regret and little communication cost, which is measured by the total amount of transmitted data. For distributed multi-armed bandits, we propose a protocol with near-optimal regret and only O(M log(MK)) communication cost, where K is the number of arms. The communication cost is independent of the time horizon T , has only logarithmic dependence on the number of arms, and matches the lower bound except for a logarithmic factor. For distributed d-dimensional linear bandits, we propose a protocol that achieves near-optimal regret and has communication cost of order O ((Md+ d log log d) log T ), which has only logarithmic dependence on T .

heading: 1 INTRODUCTION
text: Bandit learning is a central topic in online learning, and has various real-world applications, including clinical trials (Wang, 1991), model selection (Maron & Moore, 1994) and recommendation systems (Agarwal et al., 2009; Li et al., 2010; Abe et al., 2003). In many tasks using bandit algorithms, it is appealing to employ more agents to learn collaboratively and concurrently in order to speed up the learning process. In many other tasks, the sequential decision making is distributed by nature. For instance, multiple spatially separated labs may be working on the same clinical trial. In such distributed applications, communication between agents is critical, but may also be expensive or time-consuming. Another example is a recommendation system deployed on multiple servers to handle high demand. Since the communication between servers may cause service latency, it would be desirable to design communication strategies without communicating too much. This motivates us to consider efficient protocols for distributed learning in bandit problems.
A straightforward communication protocol for bandit learning is immediate sharing: each agent shares every new sample immediately with others. Under this scheme, agents can have good collaborative behaviors close to that in a centralized setting. However, the amount of communicated data is directly proportional to the total size of collected samples. When the bandit is played for a long timescale, the cost of communication would render this scheme impractical. A natural question to ask is: How ∗These two authors contributed equally.
much communication is actually needed for near-optimal performance? In this work, we show that the answer is somewhat surprising: The required communication cost has almost no dependence on the time horizon.
In this paper, we consider the distributed learning of stochastic multi-armed bandits (MAB) and stochastic linear bandits. There are M agents interacting with the same bandit instance in a synchronized fashion. In time steps t = 1, · · · , T , each agent pulls an arm and observes the associated reward. Between time steps, agents can communicate via a server-agent network. Following the typical formulation of single-agent bandit learning, we consider the task of regret minimization (Lai et al., 1987; Dani et al., 2008; Bubeck et al., 2012). The total regret of all agents is used as the performance criterion of a communication protocol. The communication cost is measured by the total amount of data communicated in the network. Our goal is to minimize communication cost while maintaining near-optimal performance, that is, regret comparable to the optimal regret of a single agent in MT interactions with the bandit instance.
For multi-armed bandits, we propose the DEMAB protocol, which achieves near-optimal regret. The amount of transmitted data per agent in DEMAB is independent of T , and is logarithmic with respect to other parameters. For linear bandits, we propose the DELB protocol, which achieves near-optimal regret, and has communication cost with at most logarithmic dependence on T .

heading: 1.1 PROBLEM SETTING
text: Communication Model The communication model we consider consists of a server and several agents. Agents can communicate with the server by sending or receiving packets. Each data packet contains integers or real numbers. We define the communication cost of a protocol as the number of integers or real numbers communicated between server and agents1. We assume that communication between server and agents has zero latency. Note that protocols in our model can be easily adapted to a network without a server, by designating an agent as the server.
Distributed Multi-armed Bandits In distributed multi-armed bandits, there are M agents, labeled 1,...,M . Each agent is given access to the same stochastic K-armed bandit instance. Each arm k in the instance is associated with a reward distribution Pk. Pk is supported on [0, 1] with mean µ(k). Without loss of generality, we assume that arm 1 is the best arm (i.e. µ(1) ≥ µ(k), ∀k ∈ [K]). At each time step t = 1, 2, ..., T , each agent i chooses an arm at,i, and receives reward rt,i independently sampled from Pat,i . The goal of the agents is to minimize their total regret, which is defined as
REG(T ) = T∑ t=1 M∑ i=1 (µ(1)− µ(at,i)) .
Distributed Linear Bandits In distributed linear bandits, the agents are given access to the same d-dimensional stochastic linear bandits instance. In particular, we assume that at time step t, agents are given an action set D ⊆ { x ∈ Rd : ‖x‖2 ≤ 1 } . Agent i chooses action xt,i ∈ D and observes reward yt,i. We assume that the mean of the reward is decided by an unknown parameter θ∗ ∈ Rd: yt,i = x T t,iθ ∗ + ηt,i, where ηt,i ∈ [−1, 1] are independent and have zero mean. For simplicity, we assume ‖θ∗‖2 ≤ 1. For distributed linear bandits, the cumulative regret is defined as the sum of individual agent’s regrets:
REG(T ) = T∑ t=1 M∑ i=1 ( max x∈D xT θ∗ − xTt,iθ∗ ) .
Here, we assume that the action set is fixed. A more general setting considers a time-varying action set Dt. In both cases, algorithms with O(d √ T log T ) regret have been proposed (Abbasi-Yadkori et al., 2011), while a regret lower bound of Ω ( d √ T ) is shown in Dani et al. (2008).
For both distributed multi-armed bandits and distributed linear bandits, our goal is to use as little communication as possible to achieve near-optimal regret. Since any M -agent protocol running for
1In our protocols, the number of bits each integer or real number uses is only logarithmic w.r.t. instance scale. Using the number of bits as the definition of communication complexity instead will only result in an additional logarithmic factor. The number of communicated bits is analyzed at the end of Appendix C G and H
T steps can be simulated by a single-agent bandit algorithm running for MT time steps, the regret of any protocol is lower bounded by the optimal regret of a single-agent algorithm running for MT time steps. Therefore, we consider Õ( √ MKT ) regret for multi-armed bandits and Õ(d √ MT ) regret for linear bandits to be near-optimal.
We are mainly interested in the case where the time horizon T is the dominant factor (compared to M or K). Unless otherwise stated, we assume that T > max{M log
2M K ,M,K} in the multi-armed
bandits case and T > M in the linear bandits case.

heading: 1.2 OUR CONTRIBUTION
text: Now we give an overview of our results. In both settings, we present communication-efficient protocols that achieve near-optimal regret. Our results are summarized in Table 1.
Our results are compared with a naive baseline solution called immediate sharing in Table 1: each agent sends the index of the arm he pulled and the corresponding reward he received to every other agent via the server immediately. This protocol can achieve near-optimal regret for both MAB and linear bandits (O( √ MKT ) and Õ(d √ MT )), but comes with high communication cost (O(M2T ) and O(M2dT )).
Distributed MAB For distributed multi-armed bandits, we propose DEMAB (Distributed Elimination for MAB) protocol, which achieves near-optimal regret (O (√ MKT log(MK) ) ) with
O(M log(MK)) communication cost. The communication cost is independent of the number of time steps T and grows only logarithmically w.r.t. the number of arms. We also prove the following lower bound: For any protocol with regret bound o(M √ KT ), the expected communication cost is at least Ω(M). That is, in order to achieve near-optimal regret, the communication cost of DEMAB matches our lower bound except for logarithmic factors.
Distributed Linear Bandits We propose DELB (Distributed Elimination for Linear Bandits), an elimination based protocol for distributed linear bandits which achieves near-optimal regret bound (O ( d √ MT log T ) ) with communication cost O ((Md+ d log log d) log T ). The communication cost of DELB enjoys nearly linear dependence on both M and d, and has at most logarithmic dependence on T . For the more general case where the action set is time-varying, we propose DisLinUCB (Distributed LinUCB) protocol, which achieves near-optimal regret with O ( M1.5d3
) communication cost.

heading: 2 RELATED WORK
text: There has been growing interest in bandits problems with multiple players. One line of research considers the challenging problem of multi-armed bandits with collisions (Rosenski et al., 2016;
Bistritz & Leshem, 2018; Kalathil et al., 2014), in which the reward for an arm is 0 if it is chosen by more than one player. The task is to minimize regret without communication. Their setting is motivated by problems in cognitive radio networks, and is fairly different from ours.
Szörényi et al. (2013) and Korda et al. (2016) consider the distributed learning of MAB and linear bandits with restriction on the communication network. Motivated by fully decentralized applications, Szörényi et al. (2013) consider P2P communication networks, where an agent can communicate with only two other agents at each time step. A gossip-based -greedy algorithm is proposed for distributed MAB. Their algorithm achieves a speedup linear in M in terms of error rate, but the communication cost is linear in T . The work of Korda et al. (2016) uses a gossip protocol for regret minimization in distributed linear bandits. The main difference between their setting and ours is that each agent is only allowed to communicate with one agent at each time step in Korda et al. (2016) 2. Their algorithm achieves near-optimal ( O ( d √ MT log T )) total regret using O(Md2T ) communication
cost.
Another setting in literature concerns about distributed pure exploration in multi-armed bandits (Hillel et al., 2013; Tao et al., 2019), where the communication model is the most similar one to ours. These works use elimination based protocols for collaborative exploration, and establish tight bounds for communication-speedup tradeoff. However, their task (speedup in pure exploration) is not directly comparable to ours (i.e. are not reducible to each other). Moreover, in Hillel et al. (2013); Tao et al. (2019), the number of communication rounds is used as the measure of communication, while we use the amount of transmitted data.

heading: 3 MAIN RESULTS FOR MULTI-ARMED BANDITS
text: In this section, we first summarize the single-agent elimination algorithm (Auer & Ortner, 2010), and then present our Distributed Elimination for MAB (DEMAB) protocol. The regret and communication efficiency of the protocol is then analyzed in Sec. 3.3. A communication lower bound is presented in Sec. 3.4.

heading: 3.1 ELIMINATION ALGORITHM FOR SINGLE-AGENT MAB
text: The elimination algorithm (Auer & Ortner, 2010) is a near-optimal algorithm for single-agent MAB. The agent acts in phases l = 1, 2, · · · , and maintains a set of active arms Al. Initially, A1 = [K] (all arms). In phase l, each arm in Al is pulled for Θ(4l log T ) times; arms with average reward 2−l lower than the maximum are then eliminated from Al. For each arm k ∈ [K], define its suboptimality gap to be ∆k := µ(1)−µ(k). In the elimination algorithm, with high probability arm k will be eliminated after approximately lk = log2 ∆ −1 k phases, in
which it is pulled for at most O ( ∆−2k log T ) times. It follows that regret is O (∑ k:∆k>0 ∆−1k log T ) ,
which is almost instance-optimal. The regret is O (√ KT log T ) in the worst case.
In order to apply elimination algorithm to our setting and remove the log T dependence in the regret bound, we slightly modify the elimination algorithm: In phase l, each arm in Al is pulled for Θ(4l log(4−lT )) instead of Θ(4l log(T )) times. By doing this, the regret bound can be improved from √ KT log T to √ KT logK. Our DEMAB protocol is based on this modified elimination algorithm. See Section 3.2 and Appendix C for detailed explanation.

heading: 3.2 THE DEMAB PROTOCOL
text: The DEMAB protocol executes in two stages. In the first stage, each agent directly runs the singleagent modified elimination algorithm for D = dT/MKe time steps. The remaining arms of agent i are denoted as A(i). In D time steps, an agent completes at least l0 = blog4 D1000K log(MK)c phases. The purpose of this separate burn-in period is to eliminate the worst arms quickly without communication, so that in the second stage, elimination can begin with a small threshold of O(2−l0). D and l0 is chosen so that the total regret within the first stage is Õ (√ MT ) .
2Our algorithms can be modified to meet this restriction with almost no change in performance.
Protocol 1: Distributed Elimination for Multi-Armed Bandits (DEMAB) 1 D = dT/MKe, l0 = blog4 ( D 1000K log(MK) ) c, ml = b4l+3 log(MKT · 4−l)c
/* Stage 1: Separate Burn-in */ 2 for Agent i = 1, · · · ,M do 3 Agent i runs single-agent elimination for D time steps, denote remaining arms as A(i)
/* Switching: Random Allocation */ 4 Generate public random numbers r1,...,rK uniformly distributed in [M ] 5 B(i)l0+1 = { a ∈ A(i)|ra = i } , Bl0+1 = ⋃ i∈[M ] B (i) l0+1
/* Stage 2: Distributed Elimination */ 6 for l = l0 + 1, · · · do 7 if Nl = |Bl| > M then 8 Agent i sends n(i)l =
∣∣∣B(i)l ∣∣∣ to server; server broadcasts nmax = maxi n(i)l 9 if (n(1)l , ..., n (M) l ) is not balanced then
10 Reallocate // Adjust B(i)l so that their sizes are balanced
11 Agent i pulls each a ∈ B(i)l for ml times, denotes average reward as ûl(a), and then pulls arms in round-robin for (nmax − n(i)l )ml times before the next communication round 12 Communication round: Agent i sends max a∈B(i)l
ûl to server and waits to receive u∗l = maxa∈Bl ûl from server
13 Agent i eliminates bad arms: B(i)l+1 = { a ∈ B(i)l : ûl(a) + 2−l ≥ u∗l } 14 else 15 For each arm in Bl, the server asks M/Nl agents to pull it mlNl/M times 16 Server computes ûl(a), the average reward for ml pulls of arm a 17 Server eliminates bad arms: Bl+1 = { a ∈ Bl : ûl(a) + 2−l ≥ maxb∈Bl ûl(b) }
Between the two stages, the remaining arms are randomly allocated to agents. Public randomness is used to allocate the remaining arms to save communication. Agents first generate (r1, · · · , rK), K uniformly random numbers in [M ], from a public random number generator. Agent i then computes B(i) = { a ∈ A(i)|ra = i } . By doing so, agent i keeps each arm in A(i) with probability 1/M ,
and the resulting sets B(1), · · · ,B(M) are disjoint. Meanwhile, every arm in ⋂ i∈[M ]A(i) is kept in
Bl0+1 = ⋃ i∈[M ] B(i), so that the best arm remains in Bl0+1 with high probability3.
In the second stage, agents start to simulate a single-agent elimination algorithm starting from phase l0 + 1. Initially, the arm set is Bl0+1. In phase l, each arm in Bl will be pulled for at least ml = d4l+3 log(MKT · 4l)e times. Denote the average reward of arm a in phase l by ûl(a). If ûl(a) < maxa′∈Bl ûl(a
′)− 2−l, it will be eliminated; the arm set after the elimination is Bl+1. This elimination in the second stage is performed over M agents in two ways: In distributed mode or in centralized mode. Let Nl = |Bl| be the number of remaining arms at the start of phase l. If Nl is larger than M , the elimination is performed in distributed mode. That is, agent i keeps a set of arms B(i)l , and pulls each arm in B (i) l for ml times in phase l. Each agent only needs to send the highest average reward to the server, who then computes and broadcasts maxa∈Bl ûl(a). Agent i then eliminates low-rewarding arms from B(i)l on its local copy. When Nl ≤ M , the elimination is performed in centralized mode. That is, Bl will be kept and updated by the server4. In phase l, the server assigns an arm in Bl to M/Nl agents, and asks each of
3⋃ i∈[M ] A
(i) may not be a subset of Bl0+1, which is not a problem in the regret analysis. 4In the conversion from distributed mode to centralized mode, agents send their local copy to the server.
Since the remaining action sets of agents are disjoint, the communication cost is O(M).
them to pull it mlNl/M times5. The server waits for the average rewards to be reported, and then performs elimination on Bl.
One critical issue here is load balancing, especially in distributed mode. Suppose that n(i)l = |B (i) l |, nmax = maxi∈[M ] n (i) l . Then the length of phase l is determined by nmaxml. Agent i would need to keep pulling arms for (nmax − n(i)l )ml times until the start of the next communication round. This will cause an arm to be pulled for much more than ml times in phase l, and can hurt the performance. Therefore, it is vital that at the start of phase l, ~nl := ( n (1) l , ..., n (M) l ) is balanced6.
The subroutine Reallocate is designed to ensure this by reallocating arms when ~nl is not balanced. First, the server announces the total number of arms; then, agents with more-than-average number of arms donate surplus arms to the server; the server then distributes the donated arms to the other agents, so that every agent has the same number of arms. However, calling Reallocate is communicationexpensive: it takes O (min{Nl, Nl′ −Nl}) communication cost, where l is the current phase and l′ is the last phase where Reallocate is called. Fortunately, since { B(i)l0+1 } i∈[M ] are generated randomly, it is unlikely that one of them contain too many good arms or too many bad arms. By exploiting shared randomness, we greatly reduce the expected communication cost needed for load balancing.
Detailed descriptions of the single-agent elimination algorithm, the Reallocate subroutine, and the DEMAB protocol are provided in Appendix B.
Access to a public random number generator, which is capable of generating and sharing random numbers with all agents with negligible communication cost, is assumed in DEMAB. This is not a strong assumption, since it is well known that a public random number generator can be replaced by private random numbers with a little additional communication (Newman, 1991). In our case, only O (M log T ) additional bits of communication, or O(M) additional communication cost, are required for all of our theoretical guarantees to hold. See Appendix C for detailed discussion.

heading: 3.3 REGRET AND COMMUNICATION EFFICIENCY OF DEMAB
text: In this subsection, we show that the DEMAB protocol achieves near-optimal regret with efficient communication, as captured by the following theorem.
Theorem 1. The DEMAB protocol incurs O (√ MTK log(MK) ) regret, O ( M log MKδ ) communication cost with probability 1− δ, and O (M log(MK)) communication cost in expectation.
The worst-case regret bound above can be improved to an instance-dependent near-optimal regret bound by changing the choice of D and l0 to 0. In that case the communication cost is O(M log T ), which is a small increase. See Theorem 5 in appendix for detailed discussion.
We now give a sketch of the proof of Theorem 1.
Regret In the first stage, each agent runs a separate elimination algorithm for D timesteps, which has regret O( √ KD log(MK)). Total regret for all agents in this stage is O(M √ KD logD) =
O( √ MT log(MK)). After the first stage, each agent must have completed at least l0 phases. Hence,
with high probability, before the second stage, Bl0+1 = ⋃ i∈[M ] B (i) l0+1
contains the optimal arm and only arms with suboptimality gap less than 2−l0+1.
In the second stage, if a ∈ Bl, it will be pulled at most 2ml times in phase l because of our load balancing effort. Therefore, if arm k has suboptimality gap 0 < ∆k < 2−l0+1, it will be pulled for Õ ( ∆−2k ) times. It follows that regret in the second stage is O (√ MKT log(MK) ) , and that total
regret is O (√ MKT log (MK) ) .
5The indivisible case is handled in Appendix B. 6By saying a vector of numbers is balanced, we mean the maximum is at most twice the minimum.
Communication In the first stage and the random allocation of arms, no communication is needed. The focus is therefore on the second stage.
During a phase, apart from the potential cost of calling Reallocate, communication cost isO (M). The communication cost of calling Reallocate in phase l is at most O (min {Nl, Nl′ −Nl}), where l′ is the last phase where Reallocate is called. Therefore, total cost for calling Reallocate in one execution is at mostO (Nl1), where l1 is the first phase in which Reallocate is called. From the definition of ml and l0, we can see that there are at most L = O (log(MK)) phases in the second stage. Therefore in the worst case, communication cost is O (ML+K) since Nl1 ≤ K. However, in expectation, Nl1 is much smaller than K. That is to say, Reallocate is called for the first time when Nl is much smaller that K with high probability. Since arms are randomly allocated to agents during switching step, when the total number of remaining arms is large enough, ~nl would be balanced with high probability. In fact, with probability 1− δ, Nl1 = O ( M log MKδ ) . Setting δ = 1/K, we can show that the expected communication complexity is O(M logMK).

heading: 3.4 LOWER BOUND
text: Intuitively, in order to avoid a Ω ( M √ KT ) scaling of regret, Θ(M) amount of communication cost
is necessary; otherwise, most of the agents can hardly do better than a single-agent algorithm. We prove this intuition in the following theorem. Theorem 2. For any protocol with regret bound o(M √ KT ), the expected communication cost is at least Ω(M).
The theorem is proved using a reduction from single-agent bandits to multi-agent bandits, i.e. a mapping from protocols to single-agent algorithms. This theorem shows that, in order to achieve near-optimal regret ( Õ (√ MKT ))
, the communication cost is at least Ω(M). That is to say, the communication cost of DEMAB protocol matches the lower bound except for a logarithmic factor.

heading: 4 MAIN RESULTS FOR LINEAR BANDITS
text: In this section, we first summarize the single-agent elimination algorithm for linear bandits (Lattimore & Szepesvári, 2019, chap. 22), and then present the Distributed Elimination for Linear Bandits (DELB) protocol. DELB is designed for the case where the action set D is fixed. Our results for linear bandits with time-varying action set is presented in Sec. 4.4. For convenience, we assume D is a finite set, which is without loss of generality from a regret point of view7.

heading: 4.1 ELIMINATION ALGORITHM FOR SINGLE-AGENT LINEAR BANDIT
text: The elimination algorithm for linear bandits (Lattimore & Szepesvári, 2019) also iteratively eliminates arms from the initial action set. In phase l, the algorithm maintains an active action setAl. It computes a distribution πl(·) overAl and pulls arms according to πl(·). A total of nl pulls is made in this phase according to πl(·). Then, linear regression is used to estimate the expected reward of each arm based on these pulls. Arms with estimated rewards Θ(2−l) lower than the maximum are eliminated at the end of the phase.
To ensure that arms with suboptimality gap Θ(2−l) are eliminated in phase l with high probability, the estimation error in phase l needs to be smaller than 2−l. On the other hand, to minimize regret, the number of pulls make in phase l needs to be as small as possible, especially when l is small. Suppose that Vl(π) = ∑ x∈Al π(x)xx > and gl(π) = maxx∈Al x >Vl(π)
−1x. By analyzing linear regression (see, e.g., Lattimore & Szepesvári (2019, chap. 21)), one can show that if each arm x ∈ Supp(πl) is pulled ⌈ π(x)gl(π)4 l log ( 1 δ )⌉ times, the estimation error for any arm x ∈ Al is at most 2−l with high probability. Thus, to minimize ml, one should find a distribution π(·) that minimizes gl(π), a task known as G-optimal design (Pukelsheim, 2006). It is known that the optimal value for gl(π) is d, and
7When D is infinite, we can replace D with an -net of D, and only take actions in the -net. If < 1/T , this will not affect the scaling of the regret. This is a feasible approach, but computationally inefficient.
that there exists a minimizer π∗ such that the support set of π∗, also called the core set, has cardinality at most d(d+1)/2. Consequently, only ∑ x∈Supp(π∗l ) dπ∗(x)gl(π∗)4l log( 1δ )e ≤ O(4 ld log( 1δ )+d 2) pulls are needed in phase l.

heading: 4.2 THE DELB PROTOCOL
text: In this protocol, we parallelize the data collection part of each phase by sending instructions to agents in a communication-efficient way. In phase l, the server and all agents first locally solve the same G-optimal design problem on Al, the remaining set of actions. In our case, only a 2-approximation to the optimal design is needed. That is, we only need to find πl(·) with g(π) ≤ 2d. By using the Frank-Wolfe algorithm under appropriate initialization (Todd, 2016, Proposition 3.17), we can find such a 2-approximate solution with a support smaller than ξ = 48d log log d.
After that, the server assigns arms in Al to agents. Since the server and the agents obtain the same core set when solving the approximate G-optimal design8, the server only needs to send the index among ξ arms to identify and allocate each arm. After pulling arms, agents send the average reward for each arm to the server, who computes the least squares estimator. The agents and the server then eliminate low rewarding arms from their local copies of Al. For notational convenience, we define V (π) = ∑ x∈D π(x)xx >, g(π) = maxx∈D x >V (π)−1x.
Protocol 2: Distributed Elimination for Linear Bandits (DELB) 1 A1 = D, C1 = 600 2 for l = 1, 2, 3, ... do
/* All agents and server: Solve a G-optimal design problem */ 3 Find distribution πl(·) over Al such that: 1. its support has size at most ξ = 48d log log d; 2.
g(π) ≤ 2d /* Server: Assign pulls and summarize results */
4 Assign ml(x) = dC14ld2πl(x) lnMT e pulls for each arm x ∈ Supp(πl) and wait for results9. 5 Receive rewards for each arm x ∈ Al reported by agents 6 For each arm in the support of πl(·), calculate the average reward µ(x) 7 Compute10X = ∑ x∈Supp(πl)ml(x)µ(x)x, Vl = ∑ x∈Supp(πl)ml(x)xx >, θ̂ = V −1l X 8 Send θ̂ to all agents /* All agents and server: Eliminate low-rewarding arms */
9 Eliminate low rewarding arms: Al+1 = { x ∈ Al : maxb∈Al〈θ̂, b− x〉 ≤ 2−l+1 }

heading: 4.3 REGRET AND COMMUNICATION EFFICIENCY OF DELB
text: We state our results for the elimination-based protocol for distributed linear bandits. The full proof is given in Appendix G.
Theorem 3. The DELB protocol achieves expected regret O ( d √ TM log T ) with communication
cost O ((Md+ d log log d) log T ).
Proof sketch: In round l, the number of pulls is at most 48d log log d+ C14ld2 logMT . Based on the analysis for elimination-based algorithm, we can show that the suboptimality gap 〈θ∗, x∗ − x〉 is at most 2−l+2 with probability 1− 1/MT for any arm x pulled in phase l. Suppose there are at most L phases, we can prove that E(REG(T )) ≤ ∑L l=1O(d √ 4ld2 log2 TM) ≤ O(d √ TM log TM).
In each phase, communication cost comes from three parts: assigning arms to agents, receiving average rewards of each arm and sending θ̂ to agents. In the first and second part, each arm x ∈ Supp(πl) is designated to as few agents as possible. We can show that the communication cost
8The Frank-Wolfe algorithm and its initialization are deterministic. 9We assign the pulls of each arm to as few agents as possible. See Appendix F for detailed description.
10Vl is always invertible when Al spans Rd. When Al doesn’t span Rd, we can always consider span(Al) in phase l and reduce the number of dimensions.
of these parts is O(M + d log log d). In the third part, the cost of sending θ̂ is Md. Since l is at most O(log T ), the total communication is O ((Md+ d log log d) log T ) .

heading: 4.4 PROTOCOL FOR LINEAR BANDITS WITH TIME-VARYING ACTION SET
text: In some previous work on linear bandits (Chu et al., 2011; Abbasi-Yadkori et al., 2011), the action set available at timestep t may depend on t. That is, players can only choose actions from Dt at time t, while regret is defined against the optimal action in Dt. The DELB protocol does not apply in this scenario. To handle this setting, we propose a different protocol DisLinUCB (Distributed LinUCB) based on LinUCB (Abbasi-Yadkori et al., 2011).
In our distributed algorithm, agent i uses all samples available for him to maintain a confidence set Ct,i ⊆ Rd for the parameter θ∗. In each step, he chooses an optimistic estimate θ̃t,i = argmaxθ∈Ct−1,i (maxx∈D〈x, θ〉) and then chooses action Xt,i = argmaxx∈D 〈 x, θ̃t,i 〉 ,
which maximizes the reward according to the estimate θ̃t,i. We denote ∑ τ xτx T τ and ∑ τ xτyτ as W and U in our algorithm respectively. We use Wt,i and Ut,i to denote the sum calculated using available samples for agent i at time step t. We construct the confidence set Ct,i using Wt,i and Ut,i:
Ct,i = θ ∈ Rd : ‖θ̂t,i − θ‖V t,i ≤ √√√√2 log(det (V t,i)1/2 det(λI)−1/2 δ ) + λ1/2  , (1) where V t,i = λI +Wt,i, θ̂t,i = (λI +Wt,i) −1 Ut,i, ‖x‖V := xTV x. Essentially, without synchronization, agents in our protocol execute LinUCB separately. In a synchronization round, agents share all newly acquired samples with each other. The remaining question is when to synchronize.
Our key observation, which comes from the analysis in Abbasi-Yadkori et al. (2011), is that the change in the log-determinant of V t is a good indicator of learning progress. Based on this observation, we only synchronize when agent i finds that the log-determinant of V t,i has changed significantly since the last synchronization. We designed this synchronization criterion carefully such that, on the one hand, regret is close to the lower bound and on the other hand, the number of synchronization rounds is small. The full protocol is described below.
Protocol 3: Distributed Linear UCB (DisLinUCB) 1 for t = 1, · · · , T do 2 for Agent i = 1, · · · ,M do 3 Compute Wt,i = ∑ τ xτx T τ and Vt,i = I + ∑ τ xτyτ using all available samples 4 Construct the confidence ellipsoid Ct,i using Wt,i and θ̂t,i = V −1t,i Ut,i. 5 (xt,i, θ̃t,i) = arg max(x,θ)∈Dt×Ct,i〈x, θ〉 6 Play xt,i and observe reward yt,i. 7 Update Wt,i and Vt,i 8 if log (detVt,i/detVlast) · (t− tlast) > T log(MT )/(dM) then 9 Start a synchronization round
10 tlast = t, Vlast = I + ∑ τ xτyτ using all available examples
We state the following regret and communication bound for this protocol. The proof is deferred to Appendix H.
Theorem 4. The DisLinUCB protocol can achieve a regret of O ( d √ MT log2(T ) ) with
O ( M1.5d3 ) communication cost.
Although the regret bound is still near-optimal, the communication cost has worse dependencies on M and d compared to that of DELB.

heading: 5 CONCLUSIONS AND FUTURE WORK
text: In this work, we propose communication-efficient protocols with near-optimal regret for both multiarmed bandits and linear bandits problem. For multi-armed bandits, we propose DEMAB protocol, which achieves √ MKT log(MK) regret with M log(MK) communication cost. The communication cost of DEMAB protocol matches the lower bound we proposed except for a logarithmic factor. For distributed linear bandits, our DELB protocol and DisLinUCB protocol achieve near-optimal regret with O ((Md+ d log log d) log T ) and O ( M1.5d3 ) communication cost respectively.
An interesting open question is proving lower bounds of communication cost in order to achieve nearoptimal regret in linear bandits. From a reduction from multi-armed bandits to linear bandits, Thm. 2 implies Ω(M) communication lower bound for linear bandits. However, there is still a gap between this bound and the communication cost of DELB protocol. We conjecture that close-to-Md amount of communication is necessary, which is the case in offline distributed linear regression (Zhang et al., 2013; Braverman et al., 2016) in the context of achieving an optimal risk rate.

heading: 6 ACKNOWLEDGEMENTS
text: The authors thank Chi Jin, Chicheng Zhang and Nan Jiang for helpful discussions. This work is supported by National Basic Research Program of China (973 Program) (grant no. 2015CB352502), NSFC (61573026), BJNSF (L172037) and Beijing Acedemy of Artificial Intelligence.

heading: A ORGANIZATION
text: The appendix is organized as follows.
Sections B-E are mainly about distributed multi-armed bandits.
In Section B, we present omitted details for the DEMAB protocol. In Section C, we analyze the performance of DEMAB and prove Theorem 1. We also analyze the number of communicated bits in DEMAB in this section. In Section D, we discuss how to remove the usage of public randomness in the DEMAB protocol with little increase in communication cost. In Section E, we give a proof of the communication lower bound for multi-armed bandit.
Sections F-H are mainly about distributed linear bandits.
In Section F, we present the omitted details of DELB protocol. In Section G, we prove the regret and communication cost bounds of DELB protocol, and also analyze the number of communicated bits in DELB. In Section H, we analyze the performance of the DisLinUCB protocol.
Finally, in Section I, we demonstrate that our protocols can be adapted to the P2P communication networks considered in Korda et al. (2016), which proves our claim in footnote 2 of the main paper.

heading: B DETAILED DESCRIPTION OF DEMAB
text: In this section, we give a detailed description of the DEMAB protocol and some subroutines used in the protocol.
Protocol 4: Distributed Elimination for Multi-armed Bandits (DEMAB) 1 D = dT/MKe, C2 = 1000, l0 = blog4 ( D C2K log(MK) ) c, ml = d4l+3 log(MKT · 4−l)e
/* Stage 1: Separate Burn-in */ 2 for agent i = 1, ...,M do 3 A(i) =Eliminate([K],D) /* Switching: Random Allocation */ 4 Generate public random numbers r1, ..., rK in [M ] 5 B(i)l0+1 = {a ∈ A
(i)|ra = i} /* Stage 2: Distributed Elimination */
6 for l = l0 + 1, ... do 7 if Centralize has not been called then
/* distributed mode */ 8 Agents send n(i)l = ∣∣∣B(i)l ∣∣∣ to server, Nl = ∑i n(i)l , Nmax = maxi n(i)l
9 if Nl ≤M then 10 Centralize, go to line 22 11 if ~nl is not balanced then 12 Reallocate
13 Server sends Nmax to all agents 14 for agent i = 1, ...,M do 15 Pull each a ∈ B(i)l for ml times, denote average as ûl(·) 16 Pull other arms in round-robin for (Nmax − |Bl|)ml times 17 Send (arg maxa′ ûl(a′),maxa′ ûl(a′)) to server 18 Server receives (a∗j,l, u ∗ j,l) from agent j, and sends u ∗ l = maxj u ∗ j,l to every agent 19 for agent i = 1, ...,M do 20 Elimination: B(i)l+1 = { i ∈ B(i)l : ûl(a) + 2−l ≥ u∗l
} 21 else
/* centralized mode */ 22 Server assigns arms in Bl to agents evenly and schedules ml pulls for each arm 23 Agents pull arms as required by the server, and report the average for the pulled arm 24 Server calculates ûl(a), average reward for ml pulls in this phase, for each arm a ∈ Bl 25 Elimination: Bl+1 = { a ∈ Bl : ûl(a) + 2−l ≥ maxj∈Bl ûl(j)
} Eliminate: Eliminate executes the single-agent elimination algorithm. In this function, each agent runs the single-agent elimination algorithm for D time steps, then return the remaining arms.
Protocol 5: Eliminate Input: A set of arms A1, time step D.
1 for l = 1, ... do 2 for a ∈ Al do 3 Pull arm a for ml = d4l+3 log(4−lMKT )e times, denote average reward as µ̂l(a) 4 If time step D is reached, go to line 6 5 Elimination: Al+1 = { a ∈ Al : µ̂l(a) > maxk∈Al µ̂l(k)− 2−l
} 6 Return Al
Reallocate: In Reallocate, the server announces the average number of arms; agents with morethan-average arms then donate surplus arms to the server; the server then distributes the donated arms to the other agents, so that every agent has nearly the same number of arms. After calling
Reallocate, ~nl becomes balanced again. The function contains the following two parts: One running on the server, and the other running on each agent.
Protocol 6: Reallocate for Server Input: n(1)l ,...,n (M) l
1 n̄ = b ∑M i=1 n (i) l /Mc 2 Send “reallocation”, n̄ to every player 3 Receive a set of n(i)l − n̄ arms, A′i, from player i if n (i) l > n̄; Atemp = ⋃ iA′i 4 for i = 1, ...,M do 5 If n(i)l < n̄, send n (i) l − n̄ arms in Atemp to player i, and remove them from Atemp 6 Send the remaining arms in Atemp to players 1,...,|Atemp| (one each)
Protocol 7: Reallocate for Agents 1 if Receive “reallocation”, n̄ then 2 if n(i)l > n̄ then 3 Pick a subset of n(i)l − n̄ arms, A′i, from B (i) l , and send them to server 4 B(i)l = B (i) l \ A′i 5 else 6 Wait until receiving A′i from server, B (i) l = B (i) l ∪ A′i
Centralize: When the number of arms drops below M , the subroutine Centralize is called, in which agents send their local copy of remaining arms, B(i)l , to the server, and server receives Bl = ⋃ i∈[M ] B (i) l .
Protocol 8: Centralize 1 for agent i = 1, ...,M do 2 Send B(i)l to server
3 Server receives B(i)l from agent i, and calculates Bl = ⋃ i B (i) l
Assignment Strategy: In centralized mode, server assigns arms to agents in the following way. Let Nl = |Bl|. If M is exactly divisible by Nl, for each arm in Bl, server asks M/Nl separate agents to play it for dmlNl/Me times. If not, we allocate pulls to agents in the following way: Let pl = dmlNl/Me denote the average pulls each agent needs to perform. Our assignment starts from the arm with the smallest index ak1 and agent 1. For arm akj and agent i, if agent i has been assigned pl pulls, we turn to agent i + 1. If we have finished allocating ml pulls for arm akj , we continue designating arm akj+1 . The assignment is finished until all pulls are scheduled to agents.

heading: C PROOF OF THEOREM 1
text: In this section, we give a full proof of Theorem 1, which bounds the total regret and communication cost of the DEMAB protocol. In the analysis below, we will use B̃l to represent B(1)l ∪ · · · ∪ B (M) l (in the distributed mode) or Bl (in the centralized mode). It refers to the set of remaining arms at the start of the l-th phase at stage 2, either held separately by the agents or held by the server.
Suppose that the protocol terminates when l = l′. We also let NM (a, t) = ∑t j=1 ∑M i=1 I [ai,j = a] be the number of times arm a is pulled before time step t. Without loss of generality, we assume that arm 1 is the best arm, and define ∆k := µ(1)− µ(k). We first state a few facts and lemmas.
Fact 1. We state some facts regarding the execution of the algorithm.
1. At line 6 of the server’s part in Reallocate, |Atemp| < M ;
2. After Reallocate is called, 〈∣∣∣B(1)l ∣∣∣ , · · · , ∣∣∣B(M)l ∣∣∣〉 is balanced; 3. For any player i, the number of completed phases in stage 1 is at least l0 =⌊ log4 ( D
C2K logMK
)⌋ , and at most lD = ⌈ log4 ( D
C′2 logMK
)⌉ .
4. The number of phases at stage 2 is less than L = 4 + 5 log(MK) = O (log(MK)).
Proof. 1. Let S+ = {i : n(i)l ≥ n̄} and S− = {i : n (i) l < n̄}. At line 3 of server’s reallocate code, server receives ∑ i∈S+ ( n (i) l − n̄ ) arms. At line 5, ∑ i∈S−(n̄− n (i) l ) arms are removed. So at line 6,
|Atemp| = ∑ i∈S+ (n (i) l − n̄)− ∑ i∈S− (n̄− n(i)l ) = ∑ i∈[M ] n (i) l −Mb ∑ i∈[M ] n (i) l /Mc < M.
2. Let n(i)l = ∣∣∣B(i)l ∣∣∣. If maxi n(i)l ≤ 2 mini n(i)l , the reallocation procedure will do nothing,
and 〈n(1)l , ..., n (M) l 〉 is by definition balanced. If maxi n (i) l > 2 mini n (i) l , then at the end of the reallocation procedure, every player has a new set of arms B(i)l such that n̄ ≤ ∣∣∣B(i)l ∣∣∣ ≤ n̄+ 1. This
implies that the number of arms is balanced, since when reallocation is called, ∑ i n (i) l ≥M .
3. The length of the l-th phase at stage 1 is at most Kd4l+3 log(4−lMKT )e. After l phases, the number of timesteps is at most
K l∑ p=1 4p+3 log(4−pMKT ) ≤ 4 l+4 3 ( log(4−lMKT ) + 1 3 ) .
Setting C2 = 1000 and l0 = blog4 ( D C2K logMK ) c, one can verify that
4l0+4
3
( log(4−l0MKT ) + 1
3
) ≤ 256D
3C2 log(MK)
( log(C2M 2K3 log(MK) + 1
3 )
) ≤ D.
Since the total number of timesteps in stage 1 is D, we know that the number of completed phases in stage 1 is at least l0.
On the other hand, in l phases, the number of timesteps is at least
l∑ p=1 4p+3 log(4−pMKT ) ≥ 4l+3 log(4−lMKT ).
By setting C ′2 = 512 and lD = ⌈ log4 ( D
C′2 logMK
)⌉ , one can show that 4lD+3 log(4−lDMKT ) >
D. Therefore, the number of of completed phases in stage 1 is at most lD.
4. Suppose that stage 2 has L = 4 + 5 log(MK) phases, then the total number of phases during stage 1 and stage 2 is at least L+ l0. In phase L+ l0, at least 4l0+L+3 log ( 4−(l0+L)MKT ) pulls are made. With some elementary calculation, one can show that the number of arms pulled in phase L+ l0 is MT · MKlog(MK) log log(MK) M , which is even greater than the total number of timesteps MT . That is to say, the number of phases in stage 2 is less than L.
Via a direct application of Hoeffding’s inequality and union bound, we have the following lemma. Lemma C.1. Denote the average rewards computed by agent i in phase l of stage 1 be µ̂i,l(·). At stage 1, we denote the following even as Λl: in phase l at stage 1, for any agent i, for any arm a ∈ A(i)l , |µ̂i,l(a)− µ(a)| ≤ 2−l−1. Then Pr [Λl] ≥ 1− 2 · 4l/(MKT ).
Proof. For any agent i, any phase l ≤ lD, denote the empirical mean for arm a in phase l by ûi,l(a). By a direct application of Hoeffding’s bound and union bound, we can observe that for any fixed i, l, a, by Hoeffding’s bound,
Pr [ |µ̂i,l(a)− µ(a)| > 2−l−1 ] ≤ 2 exp { −1
2 ml · 4−l−1
} ≤ 2 · 4 l
(MK)2T .
A union bound for all arms a ∈ A(i)l and all agents i ∈ [M ] proves the lemma.
Lemma C.2. For phase l in stage 1, Λ1 ∧ · · · ∧ Λl implies the following:
1. 1 ∈ A(i)l+1;
2. ∀i ∈ [M ], ∀a ∈ A(i)l+1, µ(a) ≥ µ(1)− 2−l+1;
3. Recall that NM (k, t) = ∑t j=1 ∑M i=1 I [ai,j = k] is the number of times arm k is pulled
for all agents before time step t. If li = dlog2 ∆−1i e + 1 ≤ l, then NM (i,D) ≤ C5M log(MKT∆ 2 i )/∆ 2 i ;

heading: In particular, let lD be the maximum number of phases for all agents at stage 1. Λ1 ∧ · · · ∧ ΛlD also implies the following:
text: 4. ∃i ∈ [M ], 1 ∈ B(i)l0+1;
5. ∀i ∈ [M ],∀a ∈ B(i)l0+1, µ(a) ≥ µ(1)− 2 −l0+1;
Proof. These results are direct implications of lemma C.1.
1. Notice that if Λl happens,
µ̂i,l(1) ≥ µ(1)− 2−l−1 ≥ µ(a)− 2−l−1 ≥ µ̂i,l(a)− 2−l. Thus, arm 1 will never be eliminated throughout the first l phases.
2. Λl implies that for any a ∈ A(i)l+1,
µ̂i,l(a) ≥ max k∈A(i)l µ̂i,l(k)− 2−l ≥ µ̂i,l(1)− 2−l,
which means
µ(a) ≥ µ̂i,l(a)− 2−l−1 ≥ µ̂i,l(1)− 2−l − 2−l−1 ≥ µ(1)− 2−l+1.
3. From statement 2 we know that Λ1 ∧ · · · ∧ Λl implies that arm i will be eliminated after li phases, which is less than l. Therefore, before eliminated, the total number of times arm i is pulled at stage 1 by any agent is at most
li∑ l=1 ml ≤ 4li+4 3 ( log(4−liMKT ) + 1 3 ) ≤ C5 log(MKT∆ 2 i ) ∆2i
for some absolute constant C5. Multiplying by M proves the assertion.
4. Let A(i) denote the remaining arms at the end of stage 1 for agent i. From statement 1 we know that Λ1 ∧ · · · ∧ΛlD implies 1 ∈ A(i) for any i ∈ [M ]. So at line 5 in protocol 1, arm 1 will be assign to agent ra.
5. Let A(i) denote the remaining arms at the end of stage 1 for agent i. From statement 2 we know that Λ1 ∧ · · · ∧ ΛlD implies µ(a) ≥ µ(1)− 2−l (i)+1 for any arm in ⋃ i∈[M ]A(i). Here l(i) denotes
the number of phases for agent i at stage 1. Since Bl0+1 = ⋃ i∈[M ] B (i) l0+1 is a subset of ⋃ i∈[M ]A(i) and li ≥ l0, we conclude that ∀a ∈ Bl0+1, µ(a) ≥ µ(1)− 2−l (i)+1 ≥ µ(1)− 2−l0+1.
Lemma C.3. For l > l0, denote the following event by Ωl: at stage 2, for any a ∈ Bl,
|ûl(a)− µ(a)| ≤ 2−l−1.
Then Pr [Ωl] ≥ 1− 2 · 4l/(M2KT ).
Proof. Recall that for any l > l0, ûl(a) is the average of ml independent samples of the reward from arm a. Therefore, for fixed l and a, by Hoeffding’s inequality,
Pr [ |ûl(a)− µ(a)| > 2−l−1 ] ≤ 2 exp { −1
2 ml · 4−l−1
} ≤ 2 · 4 l
(MK)2T .
A union bound for all a ∈ Bl proves this lemma.
Lemma C.4. Recall that ∆i = µ(1) − µ(i). If ∆i > 0, let li = dlog2 ∆−1i e + 1. Let Λ denote Λ1 ∧ · · · ∧ ΛlD . Then at stage 2, Λ ∧ Ωl0 ∧ · · · ∧ Ωli implies the following:
NM (i, T )−NM (i,D) ≤ C4 log(MKT∆
2 i )
∆2i + η(a),
where C4 is a universal constant, and ∑ a∈[K] η(a) ≤M logM .
Proof. Suppose that |B̃l| > M . By Fact 1, at phase l ≥ l0 + 1 in stage 2, the sequence〈∣∣∣B(1)l ∣∣∣ , · · · , ∣∣∣B(M)l ∣∣∣〉 is balanced. Therefore, during phase l at stage 2, the number of times an arm in B̃l is pulled is at most 2ml.
If |B̃l| ≤M , an arm in B̃l is also pulled at most 2ml times, unless |B̃l| ·ml < M . In that case, a phase only lasts for 1 timestep. This is possible only whenml < M , which requires l < blog4Mc < logM . We denote the number of times a is pulled in such phases by η(a).
On the other hand, let li = dlog2 1∆i e + 1. If li ≤ l0, Λ2 implies that i /∈ B̃l0+1. In that case, the number of times arm i is pulled after timestep D is 0. Assume Ωl0+1 ∧ · · · ∧ Ωli holds and i ∈ B̃li . Then
ûli ≥ µ(1)− 2−li−1 ≥ µ(i) + ∆i − 2−li−1 ≥ ûli(i) + 2−li .
Therefore, Ωl0+1 ∧ · · · ∧ Ωli implies that i /∈ B̃li+1. In this case, number of times arm i is pulled is
NM (i, T )−NM (i,D) ≤ li+1∑ l=l0+1 2ml + η(a)
≤ 8 3
4li+4 [ log(MKT · 4−li−1) + 1
3
] + L+ η(a)
≤ 2 15 log(MKT∆2i )
3∆2i + 4 + 5 log(MK) + η(a) ≤ ( 215 + 27 ) log(MKT∆2i )
3∆2i + η(a).
It is not hard to see that ∑ a∈[K] η(a) ≤M logM .
Lemma C.5. Let l ≥ l0 + 1, and nl = ∣∣∣B̃l∣∣∣. With probability 1− 2LKδ, either nl < 21M log 1δ or no reallocation is performed before the start of the l-th phase at stage 2. Proof. Let Yi,l = I [ i ∈ B̃l ] , Xi,j = I [ri = j], i ∈ [K], j ∈ [M ]. Observe that Xi,j and Yi′,l
are independent. This is because the elimination process between B̃l and B̃l+1 uses exactly ml
independent samples for each arm; therefore, the conditional probability for remaining has no dependence on which player an arm is assigned to. Let ~Y denote {Yi,l,∀i, l}. Since∣∣∣B(j)l ∣∣∣ = K∑
i=1
Yi,lXi,j , ∣∣∣B̃l∣∣∣ = nl = K∑
i=1
Yi,l,
by Chernoff’s inequality,
Pr [ K∑ i=1 Yi,lXi,j > 4 3M K∑ i=1 Yi,l ∣∣∣∣∣ ~Y ] ≤ exp { − ∑K i=1 Yi,l 21M } ,
Pr [ K∑ i=1 Yi,lXi,j < 2 3M K∑ i=1 Yi,l ∣∣∣∣∣ ~Y ] ≤ exp { − ∑K i=1 Yi,l 18M } .
Consequently,
Pr
 4 ∣∣∣B̃l∣∣∣
3M > ∣∣∣B(j)l ∣∣∣ > 2 ∣∣∣B̃l∣∣∣ 3M ∣∣∣∣∣∣nl > 21M log 1δ 
≥1− E~Y
[ exp ( − nl
21M
) + exp ( − nl
18M )∣∣∣nl > 21M log 1 δ ] ≥1− 2δ.
Note that 23M ∣∣∣B̃l∣∣∣ < ∣∣∣B(j)l ∣∣∣ < 43M ∣∣∣B̃l∣∣∣ for all j ∈ [K] implies that 〈∣∣∣B(1)l ∣∣∣ , · · · , ∣∣∣B(M)l ∣∣∣〉 is balanced. Therefore, if nl > 21M log 1δ , with probability 1− 2(l − l0)Kδ, no reallocation will be performed before the l-th phase at stage 2.
Now we are ready to prove Theorem 1. Theorem 1. The DEMAB protocol incurs O (√ MTK log(MK)) ) regret, O ( M log MKδ ) communication cost with probability 1− δ, and O (M log(MK)) communication cost in expectation.
Proof. Regret: Let li = dlog2 ∆−1i e+ 1. By Lemma C.2, when Λ1 ∧ · · · ∧ Λli holds,
NM (i,D) ≤ C5M log(MKT∆
2 i )
∆2i .
Therefore, the probability that this does not hold is at most li∑ p=1 Pr [ Λp ] ≤ li∑ p=1 2 · 4p MKT ≤ 128 3MKT∆2i .
Thus for any arm i,
E [NM (i,D)] ≤ C5M log(MKT∆
2 i )
∆2i +
128
3MKT∆2i ·MD
≤ C5M log(MKT∆ 2 i )
∆2i +
64
3∆2i .
Similarly, if li ≥ l0, when Λ ∧ Ωl0+1 ∧ · · · ∧ Ωli holds,
NM (i, T )−NM (i,D) ≤ C4 log(MKT∆
2 i )
∆2i + η(i).
The probability that this does not hold is at most
Pr [ Λ ] + li+1∑ p=l0 Pr [ Ωp ] ≤ lD∑ p=1 2 · 4p MKT + li∑ p=l0 2 · 4p M2KT ≤ 256C2C′2 + 1283 MT∆2i ≤ 600 MT∆2i .
Therefore
E [NM (i, T )−NM (i,D)] ≤ C4 log(MKT∆
2 i )
∆2i + η(i) +
600
MT∆2i ·MT
= C4 log(MKT∆
2 i )
∆2i +
600 ∆2i + η(i).
It follows that
K∑ a=1 ∆aE [NM (a,D)] = ∑
a:∆a> 1
∆aE [NM (a,D)] + ∑
a:∆a≤ 1
∆aE[NM (a,D)]
≤ KC5M log(MKT 2 1) + 256/3
1 + 1 ·MD ≤ C6 √ MT log(MK),
where in the last line we choose 1 = √ K log(K) T , and C6 is some absolute constant. Similarly,
K∑ a=1 ∆aE [NM (a, T )−NM (a,D)] ≤ ∑
a:∆a> 2
∆aE [NM (a, T )−NM (a,D)] + 2 ·MT
≤M logM +KC4 log(MKT 2 2) + C9
2 + 2 ·MT ≤M logM + (3C4 + 601) √ MKT log(K),
where in the last line we chose 1 = √ K log(K) MT . By our assumption, M logM ≤ √ MTK log(K). Therefore by the definition of total regret,
E [REG(T )] = K∑ a=1 ∆aE [NM (a,D)] + K∑ a=1 ∆a (E [NM (a, T )]− E [NM (a,D)])
≤ C6 √ MT log(MK) + (3C4 + 601 + 1) √ MKT log(K) ≤ √ 2 ·max{C6, 3C4 + 602} √ MT (K log(K) + log(MK)).
Communication: Total communication in stage 1 is 0. We first consider the worst case communication cost in stage 2. Note that during a phase (either in distributed mode or in centralized mode), the communication cost is O(M) if reallocation is not performed. The cost for reallocation at the start of phase l isO (min{nl, nl′ − nl}), where l′ is the last phase where reallocation is performed. Summing this over all phases (at most L = O(log(MK))) in stage 2, we conclude that total communication cost for reallocation is O(ML+K).
Define l1 to be the first phase such that reallocation is performed. Then, our argument above shows that communication cost is O(ML + nl1). If nl1 > 21M log 1 δ , the event in lemma C.5 will be violated for some l. The probability for that is at most 2L2Kδ. By resetting δ, we can show that with probability 1− δ, nl1 < 21M log ( 2L2K δ ) . Therefore, with probability 1− δ, total communication cost is
O ( ML+ 21M log ( 2L2K
δ
)) = O ( M log MK
δ
) .
In particular, by choosing δ = 1/K, we can show that expected communication cost is O (M log(MK)) .
Theorem 5. When D = l0 = 0 in DEMAB, the protocol incurs near-optimal instance-dependent regret O( ∑ k:∆k>0
∆−1k log T + M logM). With probability 1 − δ the communication cost is O (M log(T/δ)). The expected communication cost is O (M log T ).
Proof. Regret: In the case D = 0, it can be seen from the proof of Theorem 1 that
E [NM (i, T )] ≤ C4 log(MKT∆
2 i )
∆2i + η(i) +
600 ∆2i ,
where ∑ i∈[K] η(i) ≤M log(M). It follows that total expected regret is
E [ ∑ i:∆i>0 NM (i, T )∆i ] ≤ ∑ i:∆i>0 ∆iη(i) + ∑ i:∆i>0 C4 log(MKT∆ 2 i ) + 600 ∆i
= O ( M log(M) +
∑ k:∆k>0 ∆−1k log T
) .
Communication: By the proof of Theorem 1, the worst-case communication cost of this protocol is O (M log T +K). This is because we need O(M) communication at the end of each phase to perform elimination, and at most a total number ofO(K) additional communication among all phases to perform reallocation.
Let l∗ be the last complete phase such that nl∗+1 > 21M log(KL′/δ). By lemma C.5, no reallocation is needed before phase l∗ + 1 with probability 1− δ, so the total communication before phase l∗ + 1 is O(ML′).
From the beginning of phase l∗ + 1, the total communication in the following phases is at most O(ML′ +M log(KL′/δ)).
Therefore, with probability 1 − δ, the communication cost is O (M log T +M log(KL′/δ)) = O (M log(T/δ)). Let δ = 1/K, the expected communication is O (M log T + (ML′ +K)/K) = O (M log T ).
Finite precision: We now show that only O(log T ) bits are needed for each number sent in DEMAB. The integers sent in DEMAB are numbers in {0, · · · ,K}. Therefore O(log T ) bits are sufficient for each integer11. In the DEMAB protocol, the only real numbers that are transmitted are the average reward in a phase. In our proof, it is only required that the average of ml samples is 1 4l+2 log(MKT4−l)
-subgaussian. In fact, the average of ml samples is 14l+3 log(MKT4−l) -subgaussian. Therefore, we can use randomized rounding for the average reward with precision = 14TM . Then, the rounding error for each real number has zero mean, and is 1
M4l+3 log(MKT4−l) -subgaussian. When
computing the average of ml samples at phase l, at most M rounding error terms will contribute to it, whose sum is 1
4l+3 log(MKT4−l) -subgaussian. Therefore, the concentration inequality in lemma
C.3 and consequently our main theorem still holds. Apparently log2 1 = O (log(MT )) = O(log T ). Therefore, expected number of communicated bits is O (M log(MK) log T ).

heading: D REMOVING PUBLIC RANDOMNESS
text: The DEMAB protocol makes use of a public random number generator. It can be viewed as a sequence of uniformly random bits written on a public blackboard that every agent can read, and reading from this sequence does not require communication. In practice, this can be approximated by using a pseudorandom number generator with a truly random seed. In this case, regardless of the amount of public random number used, the communication cost is O(M), which is the cost of broadcasting a short random seed.
However, we can also totally remove the usage of public random numbers. The role of shared randomness in communication complexity has already been investigated. It is known that shared randomness can be efficiently replaced by private randomness and additional communication, as stated by the Newman’s Theorem Newman (1991). In our case, the argument is slightly different: we are considering an online learning task instead of function evaluation. Also, in DEMAB, the communication cost itself depends on the public random bits. In particular, we show the following theorem.
11Recall that T > K.
Theorem 6. There exists a protocol for distributed MAB that does not use public randomness with expected regret O( √ MKT log T ). It has communication cost bounded by O(M log(MK) + K) (worst case), and expected communication cost O(M log(MK)).
Proof. We make the following modifications to the original DEMAB protocol. Instead of using a public random bit string s 12, we predetermine B strings s1,...,sB (which can be hardcoded in advance), and randomly choose from them. That is, the server will generate a random number uniformly distributed in [B], and broadcast it to everyone. The communication cost of doing so will be Mdlog2Be. We now analyze how the choice of s1, ..., sB affects the performance of the protocol. In terms of regret bound, observe that for any random string s, the expected regret of any bandits instance X is always O( √ MKT log T ). Therefore, regret bound will not be affected when public randomness is removed.
Now define f(X, s) to be the expected communication cost of the DEMAB protocol using the public random string s and interacting with the multi-armed bandit instance X . Our analysis for DEMAB tells us that ∃c1, ∀X ,
Er [f(X, s)] ≤ c1M log(MK). Therefore, if we draw i.i.d. uniform bit strings s1, ..., sB ,
Es1,...,sB
[ 1
B B∑ i=1 f(X, si)
] ≤ c1M log(MK).
We say that a set of bit strings {s1, ..., sB} is bad for a bandit X if
1
B B∑ i=1 f(X, si) > 2c1M log(MK).
We know that there exists c2 > 0 such that 0 ≤ f(X, si) ≤ c2(M log(MK) + K). Therefore, by Hoeffding’s inequality,
Pr s1,...,sB
[ 1
B B∑ i=1 f(X, si) > 2c1M log(MK)
] ≤ exp { − 2Bc 2 1M log(MK)
c2(1 +K/(M log(MK)))
} .
In other words, for fixed X , the probability that we will draw a bad set {s1, ..., sB} is exponentially small. Therefore, for a family of bandits with size Q, the probability for drawing a set of s1, ..., sB that is bad for some bandit is at most Q · exp { − 2Bc 2 1M log(MK)
c2(1+K/(M log(MK)))
} . If we can show that this
quantity is smaller than 1, it would follow that there exists {s1, · · · , sB} such that it is not bad for any bandit in the family.
Now, we consider the following family X of bandits. For each arm, the expected reward could be a/∆, where a ∈ { 0, 1, ..., b∆−1c } . The reward distribution is Bernoulli. The size of this family is
Q ≤ ( ∆−1 + 1 )K . Now, consider any other bandit X1. Without loss of generality, we can assume that X1 is a Bernoulli bandit, and that the expectation of each arm is in [1/4, 3/4]13. Apparently we can find a bandit X2 ∈ X such that their expected rewards are ∆-close in ‖ · ‖∞. As a result, the KLdivergence of each arm’s reward in X1 and X2 is O(∆2). Let H(X) = {a1,1, r1,1, ..., aT,M , rT,M} be the random history of the DEMAB interacting with the bandit instance X . Since communication cost is determined given H(X), ∀s,
|f(X1, s)− f(X2, s)| ≤ c2 (M log(MK) +K) dTV (H(X1), H(X2)) = O ( (M log(MK) +K) · √ TM∆ ) .
With ∆ = K−1(MT )−0.5, the right-hand-side is O (M log(MK)). Therefore, it suffices to consider the bandit family X .
12which has Kdlog2Me bits 13For a general bandit instance X1, when reward r is received, we can generate a Bernoulli reward with
expectation r/2 + 1/4 to replace it. The regret bound will increase by only a constant factor.
Therefore, we only need to guarantee that BM log(MK)1+K/(M log(MK)) > C ′K logMKT , where C ′ is a universal constant. This can be met by setting B = d2C ′K2 log(MKT )e. In this case, we can guarantee that there exists a set of bit strings {s1, ..., sB}, such that for any bandit instance X , when choosing s randomly from this set, the expectation of f(X, s) is O(M log(MK)).
The additional communication overhead for generating the random string (in bits) is
O (M logB) = O (M logK +M log log(MKT )) .
Therefore, under our usual assumption that T > max{M,K}, the number of total communicated bits is bounded by O (M logK +M log log T ). In our formulation, we may view log T bits as one packet. Therefore additional communication cost is O (M). It follows that total expected communication cost is O(M log(MK)).

heading: E PROOF FOR THEOREM 2
text: Proof. In order to prove the theorem, we show that for any protocol with communication cost less that M/c (c is a constant), the regret is at least Ω(M √ KT ).
First, we list two lemmas that will be used in our proof.
Lemma E.1. (Lattimore & Szepesvári, 2019, Theorem 9.1) For K-armed bandits, there is an algorithm with expected regret
REG(T ) ≤ 38 √ KT.
Lemma E.2. (Lattimore & Szepesvári, 2019, Theorem 15.2) ForK-armed bandits, for any algorithm, there exists an instance such that
REG(T ) ≥ 1 75
√ (K − 1)T .
The original lower bound is proved for Gaussian bandits, which doesn’t fit exactly in our setting. we modified the proof to work for Bernoulli bandits, which results in a different constant.
We now prove the theorem’s statement via a reduction from single agent bandit to multi-agent bandit. That is, we map communication protocols to single-agent algorithms in the following way. For simplicity, we consider protocols as M blocks of code. In agent i’s block, each line could be a local computation, sending a message, or waiting for a message to receive.
Consider a communication protocol with communication cost B(M). We denote Xi (i ∈ [M ]) to be the number of integers or real numbers that agent i sends or receives throughout a run. Xi is a random variable. Since expected communication cost is less than M/c,
M∑ i=1 EXi ≤M/c.
Denote S as the set of M/2 agents with smaller EXi. The expected communication cost of any i ∈ S is at most 2/c. For any i ∈ S, P(Xi ≥ 1) ≤ EXi ≤ 2/c. That is, for any of these agents, the probability of either speaking to or hearing from someone is less than 2/c. Suppose that agent j is such an agent. Then, we can map the communication protocol to a single-agent algorithm by simulating agent j.
The simulation is as follows. Interacting with single agent bandit with time T , we run the code for agent i in the protocol. When no communication is needed, we may proceed to the next line of agent i’s code. When this line of code sends a message or waits for a message, we terminate the code. In the rest of the timesteps, we run a single-agent optimal algorithm (the one used to realize lemma E.1).
Then, if agent j’s code has δ probability of involving in communication, and if agent j’s regret REGj(T ) ≤ A, via this reduction, we can obtain an algorithm for single-agent MAB with expected regret
REG(T ) ≤ A+ δ · 38 √ KT.
By lemma 2, REG(T ) cannot have a regret upper bound better than √ T (K − 1)/75. Therefore
A+ δ · 38 √ KT ≥ √ (K − 1)T/75.
If 38δ < 1/75, we can show that A = Ω (√ KT ) . In our case, c = 3000 will suffice. Since we can
show this for any agent in S, we can show that total regret is Ω ( M √ KT ) .

heading: F OMITTED DETAILS OF DELB
text: Assignment Strategy: At line 4, we assign pulls to agents in the following way. Let pl = d ∑ xml(x)/Me denote the average pulls each agent needs to perform. Our assignment starts from the arm with the largest ml(x) and agent 1. For arm xk and agent i, if agent i has been assigned with pl pulls, we turn to agent i+ 1. If we have finished designating ml(xk) pulls for arm xk, we continue designating arm xk+1. The assignment is finished until all pulls are scheduled to agents. Observe that at the start of each phase, each agent has the same Al as the server. Therefore, at line 3 they obtain the same πl, with the support size at most d log log d. In that case, the server only needs to send a index (O(1) communication cost) over ξ = 48d log log d arms, instead of a vector (Ω(d) communication cost), to identify an arm x ∈ Supp(πl).

heading: G PROOF OF THEOREM 3
text: First, we consider some properties of the elimination based protocol for linear bandits. Fact 2. Let Tl denote the total number of pulls in the l-th phase, then
C14 ld2 logMT ≤ Tl ≤ ξ + C14ld2 logMT,
where ξ = 48d log log d.
Proof. For an arm x in the core set Supp(πl), the DELB protocol pulls it dC14ld2πl(x) logMT e times. Thus the total number of pulls in phase l satisfies∑
a∈Supp(πl)
ml(a) ≥ ∑
a∈Supp(πl)
C14 ld2πl(x) ≥ C14ld2 log(MT ),
and ∑ a∈Supp(πl) ml(a) ≤ ∑ a∈Supp(πl) ( C14 ld2πl(x) + 1 ) ≤ 48d log log d+ C14ld2 logMT.
Lemma G.1. In phase l, with probability 1− 1/TM , for any x ∈ D,∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ 2−l. Proof. First, we construct an l-covering of D with l = 2−l−2. Denote the center of the covering as X = {x̄1, ..., x̄Q}. Here Q satisfies Q ≤ 3d2d(l+2).
Assume that θ̂ is calculated from linear regression on x1, ... , xt′ . For fixed x ∈ D, it is known that 〈θ̂ − θ∗, x〉 is subgaussian with variance proxy
t′∑ s=1 〈x, V −1l xs〉 2 = ‖x‖2 V −1l ≤ 2‖x‖2 V −1l . (2)
Therefore with probability 1− 2δ,∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ 2√‖x‖2 V −1l log 1 δ .
Suppose nl pulls are made in phase l. In our case,
‖x‖2 V −1l ≤ g(π) nl ≤ 2 4lC1d logMT .
Therefore with probability 1− 2δ,∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ 2−l+1√ 2 C1d logMT log 1 δ .
Choose δ = 1/(2TMQ). It can be shown that with C1 = 600,
2 log(2MTQ) C1d logMT ≤ log 2 + 1 + d log 3 + 2d log 2 + d/2 300d ≤ 1 64 .
Therefore with probability 1− 1/(TM), for all x ∈ X∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ 2−l−2. Now, consider an arbitrary x ∈ D. There exists x̄ ∈ X such that ‖x− x̄‖ ≤ 2−l−2. Therefore with probability 1− 1/TM , for any x ∈ D,∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ ∣∣∣〈θ̂ − θ∗, x̄〉∣∣∣+ ∣∣∣〈θ̂ − θ∗, x− x̄〉∣∣∣
≤ 2−l−1 + ‖θ̂ − θ̂∗‖ · ‖x− x̄‖ ≤ 2−l.
Lemma G.2. Let x∗ = arg maxx∈D〈θ∗, x〉 be the optimal arm. Then with probability 1 − log(MT )/(TM), x∗ will not be eliminated until the protocol terminates.
Proof. If x∗ is eliminated at the end of round l, one of the following must happen: either (1)∣∣∣〈θ̂ − θ∗, x∗〉∣∣∣ > 2−l; or (2) there exists x 6= x∗, ∣∣∣〈θ̂ − θ∗, x〉∣∣∣ > 2−l. Therefore the probability for x∗ to be eliminated at a particular round is less than 1− 1/(TM). The total number of phases is at most logMT . Hence a union bound proves the proposition.
Lemma G.3. Suppose δ = 2 log(TM)/TM , and ∆x denotes the suboptimality gap of x, i.e. ∆x = 〈θ∗, x∗ − x〉. For suboptimal x ∈ D, define lx = inf{l : 8 · 2−l ≤ ∆x}. Then with probability 1− δ, for any suboptimal x, x 6∈ Alx .
Proof. First, let us only consider the case where x∗ is not eliminated. That is,
Pr [∃x ∈ D : x ∈ Alx ] ≤ Pr [x∗is eliminated] + Pr [∃x : x ∈ Alx−1, x ∈ Alx |x∗ ∈ Ala ] . Note that conditioned on x∗ ∈ Alx , {x ∈ Alx−1 ∧ x ∈ Alx} implies that at phase lx − 1, either∣∣∣〈θ̂ − θ∗, x〉∣∣∣ > 2−lx+1 or ∣∣∣〈θ̂ − θ∗, x∗〉∣∣∣ > 2−lx+1. Therefore the probability that there exists such x is less than log(TM)/TM . Hence, with probability 1 − 2 log(TM)/TM , x will be eliminated before phase lx.
We are now ready to prove our main result for DELB. Theorem 3. DELB protocol has expected regret O ( d √ TM log T ) , and has communication cost
O ((Md+ d log log d) log T ).
Proof. Regret: We note that at the start of round l, the remaining arms have suboptimality gap at most 8 · 2−l. Suppose that the last finished phase is L. Therefore total regret is
REG(T ) ≤ L∑ l=1 C14 ld2 logMT · 8 · 2−l + δ · 2MT
≤ C32Ld2 log TM.
Apparently C14Ld2 log TM ≤ TM . Therefore
REG(T ) ≤ √ C234 Ld4 log2 TM ≤ C7d √ TM log TM.
Under our usual assumption that T > M , this can be simplified to O(d √ TM log T ). Here C3 and C7 are some universal constants.
Communication Cost: Let pl = ∑ xml(x)/M denote the average pulls each agent needs to perform. Observe that for each arm, the number of agents that it is assigned to is at most 1 + dml(x)/ple agents. Therefore, total communication for scheduling is at most∑
x
(dml(x)/ple+ 1) ≤ 2ξ +M = O(M + d log log d).
Similarly, total communication for reporting averages is the same. The cost for sending θ̂ is Md. Hence, communication cost per phase is O(Md+ d log log d). On the other hand, total number of phases is apparently O(log TM). Hence total communication is
O ((Md+ d log log d) log TM)
Under the assumption that T > M , this can be simplified to O ((Md+ d log log d) log T ).
Finite precision: We now discuss the number of bits needed in DELB. The integers sent in DELB are less than max{T, ξ} (recall that ξ = 48d log log d). Therefore, every integer can be encoded with O(log(dT )) bits. It remains to be proven that transmitting each real number with logarithmic bits is sufficient. In the DELB protocol, two types of real numbers are transmitted: average of rewards, and entries of θ̂. To transmit real numbers with finite number of bits, we make the following modifications to the original protocol: 1. when transmitting average rewards at line 5, use randomized rounding with precision 1 = 1M2T ; 2. after computing θ̃ = V −1 l X at line 7, let θ̂ be the entry-wise rounded vector of θ̃ with 2 = 1MTd .
It can be seen that we only need to prove that after the modifications, lemma G.1 still holds. In each phase, originally µ(x) is 1ml(x) -subgaussian, but is only required to be 2 ml(x)
-subgaussian for (2) to hold. After the modification, the contribution of rounding error to a µ(x) comes from at most M independent terms, and is therefore subgaussian with variance proxy 1MT ≤ 1 ml(x)
. Therefore, after the modifications, the computed µ(x) is 2ml(x) -subgaussian; hence, (2) holds. It follows that with
probability 1− 1/(TM), for all x ∈ X , ∣∣∣〈θ̃ − θ∗, x〉∣∣∣ ≤ 2−l−2. Therefore, for any a ∈ D, ∣∣∣〈θ̃ − θ∗, x〉∣∣∣ ≤ 2−l−1. Combined with the fact that for any x ∈ D,∣∣∣〈θ̃ − θ̂, x〉∣∣∣ ≤ ‖θ̃ − θ̂‖ ≤ √d 2 ≤ 1
MT ≤ 2−l−1,
we can prove that with probability 1− 1/(TM), for all x ∈ X ,∣∣∣〈θ̂ − θ∗, x〉∣∣∣ ≤ 2−l−2. Therefore, after the modifications, the regret of the protocol is still O ( d √ TM log T ) . The amount of communicated bits is thus
O ((Md+ d log log d) · log T · log(dT )) .

heading: H PROOF OF THEOREM 4
text: First, let us restate the DisLinUCB protocol in full detail.
Protocol 3: Distributed Linear UCB (DisLinUCB) 1 D = T log(MT )/(dM), λ = 1 2 for Agent i = 1, ...,M do 3 Set Wsyn,i = 0, Usyn,i = 0, Wnew,i = 0, Unew,i = 0, tlast = 0, Vlast = λI 4 for t = 1, ..., T do 5 for Agent i = 1, ...,M do 6 V t,i = λI +Wsyn,i +Wnew,i, θ̂t,i = V −1 t,i (Usyn,i + Unew,i). 7 Construct the confidence ellipsoid Ct,i using V t,i and θ̂t,i. 8 (xt,i, θ̃t,i) = arg max(x,θ)∈Dt×Ct,i〈x, θ〉 9 Play xt,i and get the reward yt,i.
10 Update Wnew,i = Wnew,i + xt,ixTt,i, Unew,i = Unew,i + xt,iyt,i. 11 Vt,i = λI +Wsyn,i +Wnew,i 12 if log (detVt,i/detVlast,i) · (t− tlast) > D then 13 Send a synchronization signal to server to start a communication round. 14 if A communication round is started then 15 Send Wnew,i and Unew,i to server 16 Server computes Wsyn = Wsyn + ∑M j=1Wnew,j , Usyn = Usyn + ∑M j=1 Unew,j 17 Receive Wsyn, Usyn from server 18 Set Wnew,i = 0, Unew,i = 0, tlast = t, Vlast = λI +Wsyn
Let us then state several lemmas that will be useful in our proof.
Lemma H.1. For any δ > 0, with probability 1−Mδ, θ∗ always lies in the constructed Ct,i for all t and all i.
Proof. Using Theorem 2 in Abbasi-Yadkori et al. (2011) and union bound over all agents, we can prove the lemma.
For any positive definite matrix V0 ∈ Rd×d, any vector x ∈ Rd, define the norm of x w.r.t. V0 as ‖x‖V0 := √ xTV0x. Lemma H.2. (Lemma 11 in Abbasi-Yadkori et al. (2011)) Let {Xt}∞t=1 be a sequence in Rd, V is a d× d positive definite matrix and define V t = V + ∑t s=1XsX > s . Then we have that
log
( det ( V n )
det(V )
) ≤
n∑ t=1 ‖Xt‖2V −1t−1 .
Further, if ‖Xt‖2 ≤ L for all t, then n∑ t=1 min { 1, ‖Xt‖2V −1t−1 } ≤ 2 ( log det ( V n ) − log detV ) ≤ 2 ( d log (( trace(V ) + nL2 ) /d ) − log detV ) .
Using Lemma H.1, we can bound single step pseudo-regret rt,i. Lemma H.3. With probability 1−Mδ, single step pseudo-regret rt,i = 〈θ∗, x∗ − xt,i〉 is bounded by
rt,i ≤ 2 (√ 2 log ( det(V̄t,i)1/2 det(λI)−1/2
δ
) + λ1/2 ) ‖xt,i‖V̂ −1t,i = O (√ d log T
δ
) ‖xt,i‖V̄ −1t,i .
(3)
Proof. Assuming θ∗ ∈ Ct,i,
rt,i = 〈θ∗, x∗〉 − 〈θ∗, xt,i〉 ≤ 〈θ̃t,i, xt,i〉 − 〈θ∗, xt,i〉 = 〈θ̃t,i − θ∗, xt,i〉 = 〈θ̃t,i − θ̂t,i, xt,i〉+ 〈θ̂t,i − θ∗, xt,i〉
≤ ∥∥∥θ̃t,i − θ̂t,i∥∥∥
V̄t,i ‖xt,i‖V̄ −1t,i + ∥∥∥θ̂t,i − θ∗∥∥∥ V̄t,i ‖xt,i‖V̄ −1t,i
≤ 2 (√ 2 log ( det(V̄t,i)1/2 det(λI)−1/2
δ
) + λ1/2 ) ‖xt,i‖V̄ −1t,i
= O (√ d log T
δ
) ‖xt,i‖V̄ −1t,i .
Now we are ready to prove Theorem 4. Theorem 4. DisLinUCB protocol achieves a regret of O ( d √ MT log2(T ) ) with O ( M1.5d3 ) com-
munication cost.
Proof. Regret: Set δ = 1/(M2T ), the expected regret caused by the failure of Eq. (3) is at most MT · 1/(MT ) = O(1), thus we mainly consider the case where Eq. (3) holds. In our protocol, there will be a number of epochs divided by communication rounds. We denote Vlast in epoch p as Vp. Suppose that there are P epochs, then VP will be the matrix with all samples included.
Observe that detV0 = det(λI) = λd. det(VP ) ≤ ( tr(VP ) d )d ≤ (λ+MT/d)d. Therefore
log det(VP )
det(V0) ≤ d log
( 1 + MT
λd
) .
Let R := dd log ( 1 + MTλd ) e. It follows that for all but R epochs, we have
1 ≤ detVj detVj−1 ≤ 2. (4)
We call those satisfying Eq. 4 good epochs. In these epochs, we can use the argument for theorem 4 in Abbasi-Yadkori et al. (2011). First, we imagine the MT pulls are all made by one agent in a round-robin fashion (i.e. he takes x1,1, x1,2,..., x1,M , x2,1,..., xT,M ). We use Ṽt,i = λI +∑ {(p,q):(p<t)∨(p=t∧q<i)} xp,qx T p,q to denote the V t,i this imaginary agent calculates when he gets to xt,i. If xt,i is in one of those good epochs(say the j-th epoch), then we can see that
1 ≤ det Ṽt,i det V̄t,i ≤ detVj detVj−1 ≤ 2.
Therefore
rt,i ≤ O (√ d log T
δ
)√ xTt,iV̄ −1 t,i xt,i
≤ O (√ d log T
δ
)√ xTt,iṼ −1 t,i xt,i ·
det Ṽt,i det V̄t,i
≤ O (√ d log T
δ
)√ 2xTt,iṼ −1 t,i xt,i.
We can then use the argument for the single agent regret bound and prove regret in these good epochs.
We denote regret in all good epochs as REGgood. Suppose Bp means the set of (t, i) pairs that belong to epoch p, and Pgood means the set of good epochs, using lemma H.2, we have
REGgood = ∑ t ∑ i rt,i
≤ √ MT ∑ p∈Pgood ∑ (t,i)∈Bp r2t,i
≤ O √√√√dMT log(T δ ) ∑
p∈Pgood ∑ (t,i)∈Bp min ( ‖xt,i‖2Ṽ −1t,i , 1 ) ≤ O √√√√dMT log(T δ ) ∑
p∈Pgood
log
( det (Vp)
det (Vp−1) ) ≤ O (√ dMT log( T
δ ) log
( det (VP )
det (V0) )) ≤ O ( d √ MT log(MT ) ) .
Now we focus on epochs that are not good. For each bad epoch, suppose at the start of the epoch we have Vlast. Suppose that the epoch starts from time step t0, and the length of the epoch is n. Then agent i proceeds as V t0,i, ..., V t0+n,i. Our argument above tells us that regret in this epoch satisfies
REG ≤ 2 (√ d log T/δ ) M∑ i=1 n∑ t=t0 min ( ‖xt,i‖V̄ −1t,i , 1 ) ≤ O (√ d log T/δ ) · M∑ i=1 √ n log detVt0+n,i detVlast .
Now, for all but 1 agent, n log detVt0+n,idetVlast < D. Therefore we can show that REG(n) ≤ O (√ d log T/δ ) ·M √ D.
Since det(VP ) ≤ (λ+MT/d)d, we know that the number of such epochs are rare. (Less than R = O(d logMT )). Therefore the second part of the regret is
REGbad ≤ O ( Md1.5 log1.5MT ) ·D1/2.
If we choose D = ( T logMT dM ) , then REG(T ) = O ( d √ MT log2(MT ) ) . Since T > M , we have
REG(T ) = O ( d √ MT log2(T ) ) .
Communication: Let α = ( DT R )0.5 . Apparently there could be at most dT/αe such epochs that
contains more than α time steps. If the j-th epoch contains less than α time steps, log (
detVj+1 detVj ) > Dα .
Since P−1∑ j=0 log ( detVj+1 detVj ) = log detVP detV0 ≤ R,
There could be at most d RD/αe = d Rα D e epochs with less than α time steps. Therefore, the total number of epochs is at most
dT α e+ dRα D e = O
(√ TR
D
) .
With our choice of D, the right-hand-side is O ( M0.5d ) . Communication is only required at the
end of each epoch, when each agent sends O(d2) numbers to the server, and then downloads O(d2) numbers. Therefore, in each epoch, communication cost is O(Md2). Hence, total communication cost is O ( M1.5d3 ) .
Finite precision: we now consider the number of bits transmitted in the DisLinUCB protocol. To that end, we make the following minor modification to DisLinUCB. First, when reward yt,i is observed, we replace it with a random integer in {±1} with expectation yt,i. Second, after line 8, after xt,i is played, we round each entry of xt,i with precision , and use the rounded vector in the calculation in line 9. In this case, each entry of Wnew,i and Unew,i is a multiple of 2. Therefore, transmitting them requires O(d2 log −1) bits. The total communication complexity is then O ( M1.5d3 log −1 ) bits.
We now discuss how to choose such that regret is not effected. Define
REG (H) := M∑ i=1 T∑ t=1 max x∈Dt 〈x− xt,i, θ∗〉,
REG (H) := M∑ i=1 T∑ t=1 max x∈Dt 〈x− xt,i, θ∗〉.
HereH is a shorthand for a history (x1,1, y1,1, · · · , xT,M , yT,M ). D refers to set of rounded actions. For every x ∈ D, there exists x̄ ∈ D such that ‖x− x̄‖ ≤
√ d . Therefore∣∣REG (H)−REG (H)∣∣ ≤MT√d .
On the other hand, let H be the (random) history of the DisLinUCB with rounding on action sets Dt, while H is the (random) history of the DisLinUCB with rounding running on action sets Dt. Then at each time step, the mapping from past history to the next action is the same. Therefore KL(H,H) = O(MTd 2). It follows that∣∣E [REG (H)]− E [REG (H)]∣∣ ≤ O (√M3T 3d ) . When the action set is Dt, no rounding is needed, so the regret analysis for the DisLinUCB protocol without rounding directly follows. Therefore,
E [ REG ( H )] = O ( d √ MT log2 T ) .
By choosing = (MT )−1, we can guarantee E [REG (H)] = O ( d √ MT log2 T ) for any action
set. In this case, the total number of communicated bits is O ( M1.5d3 log T ) .

heading: I DEMAB AND DELB IN P2P COMMUNICATION NETWORKS
text: In this section, we will briefly discuss how to implement our protocols (i.e. DEMAB and DELB) in the P2P communication network considered in Korda et al. (2016). We show that our protocols can be adopted to P2P networks after little modification. The communication cost will remain the same, while regret bounds would only increase marginally.
In P2P communication networks, an agent can receive information from at most one other agent at a time, which leads to an information delay for each agent. In order to cope with such delay, we need to extend the length of each communication stage from 1 time step to M time steps, so that agents can complete the communication in turn. Since there are at most O(log(MK)) communication stages in DEMAB and O(log T ) communication stages in DELB, the extension of communication stages incurs at most O(M2 log(MK)) regret in DEMAB and O(M2 log T ) regret in DELB for M agents. When the time horizon T is large (i.e. T > M3 logM ), the additional term is dominated by O (√ MKT log T ) and O ( d √ MT log T ) . Another issue for P2P networks is that there is no longer a physical server in the networks. To solve this problem, we can designate agent 1 as the server: agent 1 will execute both the codes for the server and the codes for an agent.
Specifically, by saying “extending the length of the communication stage”, we mean that we can use Procedure 10 and 11 to realize communication subroutines used in our protocols in P2P networks: sending message to the server and receiving messages from the server.
Procedure 4: Server2Agent: Agent 1 sends message mi to agent i in a P2P network. 1 For the next M − 1 time steps: /* For agent 1: */ 2 Send mi to agent i+ 1 at the i-th step 3 Pull an arbitrary arm at each time step
/* For agent i(i > 1): */ 4 Receive mi from agent 1 at the (i− 1)-st step 5 Pull an arbitrary arm at each time step
Procedure 5: Agent2Server: Agents i(i > 1) sends message mi to agent 1 in a P2P network. 1 For the next M − 1 time steps: /* For agent 1: */ 2 Receive mi+1 from agent i+ 1 at the i-th step 3 Pulls an arbitrary arm at each time step
/* For agent i(i > 1): */ 4 Send mi to agent 1 at the (i− 1)-st step 5 Pull an arbitrary arm at each time step
I.1 DEMAB IN P2P NETWORKS
For distributed DEMAB in a P2P network, we can replace the communication stage in DEMAB (i.e. line 8, 12, 15 of Protocol 1) by Procedure Server2Agent and Agent2Server. In this way, it costs M time steps instead of a single time step to collect, aggregate, and boardcast information. We have the following theorem showing the efficacy of distributing DEMAB in a P2P network. Theorem 7. The DEMAB protocol in P2P networks incurs regret O (√ MKT log T +M2 log(MK) ) , with expected communication cost O (M log(MK)).
When T > M3 logM , the regret bound of this protocol is near-optimal O (√ MKT log T ) .
Proof. Regret: We compare DEMAB protocol in P2P net with the original one (i.e. Protocol 1). The burn-in stage (i.e. Stage 1) of both protocols are the same. For distributed elimination stage (i.e. Stage 2), the length of each phase in the new protocol is no shorter than that in Protocol 1. Therefore, the number of phases after phase l0 + 1 (included) in new protocol is no more than that in Protocol 1, which is O(log(MK)). In each phase starting from phase l0 + 1, new protocol needs O(M) additional steps to complete the communication in this phase, incurring O(M) additional regret per agent. Therefore, this protocol incurs O(M2) additional regret per phase starting from phase l0 + 1. The total regret of this protocol is thereby O (√ MKT log T +M2 log(MK) ) .
Communication: We still consider only distributed elimination stage. There are three communication stages per phase in Protocol 1: Line 8, 12, and 15.
In line 8 of DEMAB protocol, the total communication is O(M) since nmax is boardcast from the server, and each agent sends n(i)l to the server. We can observe that the communication cost at corresponding place is also O(M) by replacing the boardcast with Server2Agent. In line 12, the communication cost of both protocols is still the same due to the same reason. In line 15, the new protocol calls Agent2Server which runs for M steps, while the agents report the rewards in the original protocol in a single step. The communication cost is O(M) for both protocols.
In summary, the communication cost of the new protocol is the same as that of Protocol 1, which is O (M log(MK)).
I.2 DELB IN P2P NETWORKS
Very similar to the P2P version of DEMAB, we can also distribute DELB to P2P networks by replacing the communication stage of DELB by Server2Agent and Agent2Server. We have the following theorem for the P2P version of DELB. Theorem 8. The DELB protocol in a P2P network has regret O ( d √ MT log T +M2 log T ) with
expected communication cost O ((Md+ d log log d) log T ). When T > M3 logM , the regret of DELB is a near-optimal regret O ( d √ MT log T ) .
Proof. The proof is very similar to the proof of theorem 7. Note that in the P2P version of DELB, there are O(log T ) communication stages in total, which incurs O(M2 log T ) additional regret. The communication cost of the new protocol is the same as Protocol 2 for the same reason mentioned in the proof of theorem 7.

Review summaries:
The authors study a bandit problem where there are multiple agents (say, M) and each of the agents is playing a multi-armed bandit problem for T rounds. The agents can communicate with each other in order to achieve small regret. The problem is to design a strategy for arm-playing and communication so that the agents all combined can achieve a small regret w/o communicating a lot. The authors study this bandit problem in 2 settings: 1. multi-armed bandit setting and 2.  bandit linear optimization. For both these settings, the authors establish elimination style algorithms with communication. upon communication the sub-optimal arms are eliminated and the game continues with the remaining arms.