Distributed Bandit Learning: Near-Optimal Regret with Efficient Communication
Authors: Yuanhao Wang
Jiachen Hu
Xiaoyu Chen
Liwei Wang
Venue:  (2020)
Keywords: Theory
Bandit Algorithms
Communication Efficiency

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\left(\left(Md+d\log \log d\right)\log T\right)$, which has only logarithmic dependence on $T$.

Published as a conference paper at ICLR 2020
DISTRIBUTED BANDIT LEARNING: NEAR-OPTIMAL REGRET WITH EFFICIENT COMMUNICATION
Yuanhao Wang'
Jiachen Hu
Institute for Interdisciplinary Information Sciences, Tsinghua University
School of Electronics Engineering and Computer Science, Peking University Ni NickH@puu edu. cn
y 600ai 1s. I wwwssnnghaaeeu.... edu. cn
Xiaoyu Chen
Key Laboratory of Machine Perception, MOE, School of EECS,
Peking University
cxy300ple eetepkkuuedu.ccmmm .n
Liwei Wang
Key Laboratory of Machine Perception, MOE, School of EECS Center for Data Science, Peking University wanglw@cis, pku. edu.er. en
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 central server. Our goal 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( M K)) communication cost, where K is the number of arms. The communication cost independent of the time horizon T, has only logarithmic dependence on the number of arms, and matches the lower bound except for logarithmic factor. For distributed d-dimensional linear bandits, propose protocol that achieves near-optimal regret and has communication cost order ((Md + d log log d) log T), which has only logarithmic dependence on T.
INTRODUCTION
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, appealing employ more agents to learn collaboratively and concurrently 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 the same clinical trial. In such distributed applications, communication between agents is critical, but may also be expensive or time-consuming. Another example is recommendation system deployed on multiple servers to handle high demand. Since the communication between servers may cause service latency, it would be desirable design communication strategies without communicating too much. This motivates us to consider efficient protocols for distributed learning in bandit problems.
straightforward communication protocol for bandit learning immediate sharing: each agent shares every new sample immediately with others. Under this scheme, agents can have good collaborative behaviors close to that centralized setting. However, the amount of communicated data is directly proportional to the total size of collected samples. When the bandit is played for long timescale, the cost communication would render this scheme impractical. natural question to ask is: How
'These authors contributed equally.

---

Published as a conference paper at ICLR 2020
much communication is actually needed for near-optimal performance? In this work, 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 syn- chronized fashion. In time steps = 1, , each agent pulls an arm and observes the associated reward. Between time steps, agents can communicate via server-agent network. Following the typical formulation of single-agent bandit learning, we consider the task of regret minimization (Lai al., 1987 Dani et al.) 2008, Bubeck et al., 2012). The total regret of all agents used as the performance criterion of communication protocol. The communication cost is measured by the total amount of data communicated the network. Our goal is to mínimize communication cost while maintaining near-optimal performance, that is, regret comparable to the optimal regret of single agent in MT interactions with the bandit instance.
For multi-armed bandits, propose the DEMAB protocol, which achieves near-optimal regret. The amount of transmitted data per agent in DEMAB is independent 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.
1.1 PROBLEM SETTING
Communication Model The communication model consider consists of 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 the number of integers or real numbers communicated between server and agents"" [I] 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 Kaarned bandit instance. Each arm & in the instance is associated with reward distribution Px. P& is supported on [0, 1] with mean ((k).. Without loss of generality, we assume that arm is the best arm (i.e. p(1) 2 p(k), Vk E [K]). At each time step 1, 1,2,.. ..., T, each agent chooses an arm 4t,s, and receives reward rt.; independently
sampled from Pa,, The goal of the agents is to minimize their total regret, which is defined
M
REG(T) = Σ
(u(1) - u(a,,))
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 f, agents are given an action set D S {a Rd ||^||| I 1}. Agent chooses action Zt, E D and observes reward yt. :- We assume that the mean of the reward decided by an unknown parameter e Rd: Vt.: = = + Th, where T, E 1] are independent and have zero mean. For simplicity, we assume ||0* ||2 I 1. For distributed linear bandits, the cumulative regret is defined as the sum of individual agent's regrets:
REG(T) ΣΣ
max x TTO -0=,",,0' x...00)) ZED
Here, assume that the action set is fixed. A more general setting considers varying action set D, In both cases, algorithms with O T') regret have been proposed (Abbasi- Yadkori et al. 2011), while regret lower bound of Ω (dvT) 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
In our protocols, the number of bits each integer or real number uses is only logarithmic w.r.t instance scale. Using the number of hits 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 Glad
2

---

Published as a conference paper at ICLR 2020
Setting
Algorithm
Regret
Communication
Immediate Sharing
VMKT
O(M²T)
Multi-armed bandits
DEMAB (Sec.
3.2
MMT log( (MK)
((Mlo)(MK))
Lower bound (Sec.
3.4
(MvKT)
((M)
Immediate Sharing
(dv/MT log
O(MadT)
Linear bandits
DCB (Korda al.
2016
0 dv log?T
O (MdT)
DELB (Sec. 4.2
0 (d/MT log
O ((Md+ dlog log d) log
DisLinUCB (Sec.
4.4)
0 d/MT log
0 (M)
Table I: Summary of baseline approaches and our results
steps can be simulated by single-agent bandit algorithm running for MT time steps, the regret of any protocol is lower bounded by the optimal regret of single-agent algorithm running for MT time steps. Therefore, consider Ó ((VMM (MKT) regret for multi-armed bandits and (dvMTT) regret for linear bandits to be near-optimal.
We 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" bandits case and T M in the linear bandits case.
.,, K in the multi-armed
K
1.2 OUR CONTRIBUTION
Now we give an overview of our results. In both settings, we present communication-eficiienn protocols that achieve near-optimal regret. Our results are summarized in Table [
Our results are compared with naive baseline solution called immediate sharing in Table each agent sends the index of the arm he pulled and the corresponding reward received to every other agent via the server immediately. This protocol can achieve near-optimal regret for both MAB and linear bandits (O(MMKT) and O(dVMT)) but comes with high communication cost (O(M?T) and O(M2dT)
Distributed MAB For distributed multi-armed bandits, we propose DEMAB (Distributed Elim- ination for MAB) protocol, which achieves near-optimal regret (O ( MKTllg(MK)) with O(M log( M K)) 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 V KT),, the expected communication cost is at least ((M) That is, 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 (dv MT log T)) with communication cost O ((Md + d log log d) log 7'). The communication cost of DELB enjoys nearly linear dependence dependence on 7'. For the more general case where the action set is time-varying, we propose DisLinUCB (Distributed LinUCB) protocol, which achieves near-optimal regret with (M 1- d communication cost.
both M and d, and has most logarithmic
2 RELATED WORK
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

---

Published as a conference paper at ICLR 2020
Bistritz & Leshem
2018 Kalathil al.] 2014), in which the reward for 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. (016)) consider the distributed learning of MAB and linear bandits with restriction 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 each time step. A gossip-based e-greedy algorithm 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 al. (2016) uses gossip protocol for regret minimization in distributed linear bandits. The main difference between their setting and ours is that each agent
only allowed to communicate with one agent at each time step in Korda et al. (2016) Their
algorithm achieves near-optimal (o (dvMT log T) total regret using (M communication cost.
Another setting in literature concerns about distributed pure exploration in multi-armed bandits (Hillel al., 2013 Tao et al.) 2019), where the communication model is the most similar one ours. These works use elimination based protocols for collaborative exploration, and establish tight bounds for communication speelou tradeoff. However, their task (speedup in pure exploration) not directly comparable to ours (i.e. are not reducible to each other). Moreover, in Hillel et al. (2013); TToo et al. (2019), the number of communication rounds used as the measure of communication, while we use the amount of transmitted data.
MAIN RESULTS FOR MUL.II-RMMED BANDITS
In this section, 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
3.1 ELIMINATION ALGORITHM FOR SINGLE-AGENT MAB
The elimination algorithm (Auer & Ortner 2010 a near-optimal algorithm for single-agent MAB. The agent acts in phases | = 2, and maintains set of active arms A, Initially, A1 [K] (all arms). In phase I, each arm in Ar is pulled for (4' log T) times; arms with average reward lower than the maximum
then eliminated from Ai
For each arm & E [K], define its suboptimality gap to be A. := (111 p(k).. In the elimination algo- rithm, with high probability arm l will be eliminated after approximately 1 = logz A phases, in which it is pulled for at most O (Az² log T) times. It follows that regret is O (EmA, A log 7),
which is almost instance-optimal. The regret is O (VKT ( I) in the worst case.
In order to apply climination algorithm to our setting and remove the log T dependence in the regret bound, we slightly modify the elimination algorithm: In phase I, each arm in Ar is pulled for (4' (og(4-(T) instead of ( (o'')o)TT) times. By doing this, the regret bound can be improved from / VoTlog to VKT log K. Our DEMAB protocol is based on this modified elimination algorithm. See Section 3.2 and Appendix C for detailed explanation.
3.2 THE DEMAB PROTOCOL
The DEMAB protocol executes in two stages. the first stage, each agent directly runs the single- agent modified elimination algorithm for D= [T/M K time steps. The remaining arms of agent D i are denoted as A In D time steps, agent completes at least lo [loga Too0 of KJ- phases. The purpose of this separate burn-in period is eliminate the worst arms quickly without communication, so that in the second stage, elimination can begin with a small threshold of O(2-b))
D and /o is chosen so that the total regret within the first stage is Ô (VMT).
"Our algorithms can he modified meet this restriction with almost change in performance.
4

---

Published as a conference paper at ICLR 2020
Protocol 1: Distributed Elimination for Multi-Armed Bandits (DEMAB)
D [T/MK], 1o = [logı 1000 log( (K)
D
J. my [4 log( MKT 4-)
/+ Stage 1: Separate Burn-in
* /
for Agent ..... .M do
Agent rums single-agent climination for D time steps, denote remaining A40)
* Switching: Random Allocation
Generate public random numbers "1,""P" uniformly distributed in [M]]
[ {a |r =t}. Bo+ = -VeeM 1-
/* Stage
Distributed Elimination
for | = to + 1, 1.... do
N₁ [ > M then
Agent sends m
to server; server broadcasts Amna max; mi
if (mg (1) m
(M)) is not balanced then
Reallocate // Adjust B| so that their sizes are balanced
10
Agent pulls each E ( for my times, denotes average reward (a), and then pulls arms in round-robin for (Tmaa (9) mm times before the next communication round Communication round: Agent sends max aEB(1) to server and waits to receive
12
"i maX án from server
Agent climinates bad arms: B = a B(0) (i(a) + +2 2 ut else
13
14
15
For each arm in Br, the server asks M/N agents to pull it m/M times Server computes (a),, the average reward for my pulls of arm a
16
Server eliminates bad arms: Bi+1 {a Bi in(a) + 2-1 maxses, (n{b)}
17
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.... .Tx), K uniformly random numbers in [M], from public random number generator. Agent then computes agent keeps each arm in A with probability 1/M, and the resulting sets (()). ... (M) are disjoint. Meanwhile, every arm in [keim] A ) kept in
B(()) {a A i}. By doing
Bl Ule ((0), that the best arm remains in B with high probability
In the second stage, agents start to simulate single-agent elimination algorithm starting from phase lo + 1. Initially, the arm set is Bl,+1- In phase 1, each arm in B₁ will be pulled for at least my [44 (M KT 4')1 times. Denote the average reward of (a(a) < max,'eB, (a') - 2-1 it will be eliminated; the arm set after the elimination B
in phase 1 by (a). If
This elimination in the second stage is performed over M agents in two ways: In distributed mode or in centralized mode. Let N₁ |B:] be the number of remaining arms at the start of phase l. If N₁ is larger than M, the elimination is performed in distributed mode. That is, agent keeps of arms ()) and pulls each arm in 13(") for my times in phase I. Each agent only needs to send the highest average reward to the server, who then computes and broadcasts max âz(a). Agent i
then eliminates low-rewgr arms from B(i on its local copy.
When Nj M,, the elimination is performed in centralized mode. That is, Bi will be kept and updated by the server) Rl In phase I, the server assigns an arm in B, to M/N; agents, and asks each of
UUEEMn (1) may not subset of Bi which is not problem in the regret analysis.
'In the conversion from distributed mode to centralized mode, agents send their local copy to the server. Since the remaining action agents disjoint, the communication cost is O(M).
5

---

Published as a conference paper at ICLR 2020
them to pull it myNi /M times performs elimination on Bi.
The server waits for the average rewards be reported, and then
One critical issue here is load balancing, especially in distributed mode. Suppose that ny ( = |05
7maz = m mi Then the length of phase is determined by 7. Agent would need to keep pulling arms for (Amax ni (8) mm times until the start of the next communication round. This will cause an arm to be pulled for much more than my times in phase 1, and can hurt the performance.
Therefore, is vital that at the start of phase I, my == (m) ,. n. (M)) is balanced 6
(1)
The subroutine Reallocats is designed to ensure this by reallocating arms when ñi not balanced. First, the server announces the total number of arms; then, agents with more-than-averagl 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
e is communication expensive: takes O (min Ni, Ni- Ni)) communication cost, where is the current phase and
I' is the last phase where Reall 1 ocate is called. Fortunately, since {
are generated randomly, is unlikely that one of them contain too many good arms or too many bad arms. By exploiting shared randomness, greatly reduce the expected communication cost needed for load balancing.
[Bo+1] iE[M)]
Detailed descriptions of the single-agent elimination algorithm, the Real 1 1 ocate subroutine, and the DEMAB protocol are provided in Appendix B
Access to 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 well known that 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 (MM) additional communication cost, are required for all of our theoretical guarantees to hold. See Appendix C
Corr for detailed discussion.
3.3 REGRET AND COMMUNICATION EFFICIENCY OF DEMAB
In this subsection, we show that the DEMAB protocol achieves near-optimal regret with efficient communication, captured by the following theorem.
Theorem 1. The DEMAB protocol incurs O MTK log(MK)) regret, (M log MK
8
commu-
nication cost with probability 1 8. and O (M log 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 lg to 0. In that case the communication cost is OMM log T), which is a small increase. See Theorem 5 in appendix for detailed discussion.
We now give sketch of the proof of Theorem
Regret In the first stage, each agent runs a separate elimination algorithm for timesteps, which has regret O( (o))))). Total regret for all agents in this stage O(M /KDlog D) After the first stage, each agent must have completed at least to phases. Hence, with high probability, before the second stage. B Uieran ( contains the optimal arm and only arms with suboptimality gap less than 2 2
In the second stage, if Br, will be pulled at most 2m; times in phase / because of our load balancing effort. Therefore, if arm l has suboptimality gap 0 < A₁ < 2--o++1, it will be pulled for
Ô (A times. It follows that regret in the second stage is O (oKklog(MK)) and that total
regret is O [MKTlog (MK)
"The indivisible case is handled in Appendix B
"By saying vector of numbers is halanced, we the maximum is twice the minimum.

---

Published as a conference paper at ICLR 2020
Communication In the first stage and the random allocation of arms, communication is needed. The focus is therefore on the second stage.
During phase, apart from the potential cost of calling Real locate, communication cost is O (M).
The communication cost of calling Reallocate in phase is at most (min {N,, NNr- - -N where I' is the last phase where Reallocate is called. Therefore, total cost for calling Rea llocate e in one execution at most O (Ni, ). where / is the first phase in which Reallocal called. From the definition of my and lo. can see that there are most L (log( (M) K)) phases in the second stage. Therefore in the worst case, communication cost is O (ML + K) since Nr, S K.
However, in expectation, Nr, is much smaller than K. That is to say. Decaleccte e is called for the first time when Ni 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, ñi would be balanced with high probability. In fact, with probability 6, N₁, O (M log 6 KK, we can show that the expected communication complexity is ( log MK).
MT ). Setting
3.4 LOWER BOUND
Intuitively, in order to avoid a ? (MVKT) KT scaling of regret, ((M) amount of communication cost is necessary; otherwise, most of the agents can hardly do better than single-agent algorithm. We prove this intuition in the following theorem.
Theorem 2. For any protocol with regret bound oM VKT), the expected communication cost is at least (MM)
The theorem is proved using reduction from single-agent bandits multi-agent bandits, i.c. mapping from protocols to single-agent algorithms. This theorem shows that, in order to achieve near-optimal regret (ō (VMKT) the communication cost is least (MM). That is say, the communication cost of DEMAB protocol matches the lower bound except for a logarithmic factor.
4 MAIN RESULTS FOR LINEAR BANDITS
In this section, we first summarize the single-agen 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 finite set, which is without loss of generality from regret point of view
4.1 ELIMINATION ALGORITHM FOR SINGLE-AGENT LINEAR BANDIT
The elimination algorithm for linear bandits (Lattimore & Szepesvári 2019) also iteratively eliminates arms from the initial action set. In phase I, the algorithm maintains an active action set Aç. It computes a distribution (-) over A and pulls arms according to TT(-). ). A total of n; pulls is made in this phase according to x (-). Then, linear regression is used to estimate the expected reward of each arm based on these pulls. Arms with estimated rewards O lower than the maximum are eliminated at the end of the phase.
To ensure that arms with suboptimality gap O ') are eliminated in phase with high probability. the estimation error in phase needs to be smaller than 2-! On the other hand, to minimize regret, the number of pulls make in phase/ needs to be as small as possible, especially when / is small. Suppose (T( æ. By analyzing linear regression (see, e.g., Lattimore Szepesvári 2019 chap. 21)), one can show that if each arm x E Supp(m) is pulled n (x))((())' log (3) times, the estimation error for any arm x E Ai is at most 2 with high probability. Thus, to minimize my, one should find distribution π T-)) that minimizes gi (( (7), task known as G-optimal design (Pukelsheim, 2006). It is known that the optimal value for gi (T)) is d, and
that VT( = -Ere π ( and (T( = max
one
When D is infinite, we replace DD with an e-net of D. and only take actions in the e-net. If < 1/T, this will affect the scaling of the regret. This is feasible approach, hut computationally inefficient.
7

---

Published as a conference paper at ICLR 2020
that there exists minimizer n" such that the support set x², also called the core set, has cardinality at most d(d+1)/2 Consequently, only Exesupp(rr) [ (x))((=))) log( & (4'd +d²) pulls are needed in phase
4.2 THE DELB PROTOCOL
In this protocol, we parallelize the data collection part of each phase by sending instructions to agents in communication- -ffiiiien way. In phase I, the server and all agents first locally solve the same G-optimal design problem on A,, the remaining set of actions.
our case, only 2-approximation to the optimal design is needed. That is, we only need to find (.(-) with g(T) s 2d. By using the Trank-Wold algorithm under appropriate initialization (Todd] 2016 Proposition 3.17), we can find such 22 2-approximate solution with support smaller than 48d log logd.
After that, the server assigns arms in A to agents. Since the server and the agents obtain the same core set when solving the approximate G-optimal desigr 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 Ar.
For notational convenience, define ( ExED 7 (x)Ex)) ,()) maxzeD x V
Protocol 2: Distributed Elimination for Linear Bandits (DELB)
A D, C1 600
for | = 1,2,3,... do
/* All agents and server: Solve a G-optimal design problem
Find distribution mT(-) over Ai such that: 1. its support has size at most ç = 48d log d; 2.
g(T) $ 2d
/* Server: Assign pulls and summari ze results
Assign mi(x) [C)4'd(m(x)) In MT pulls for each arm E Supp(T) and wait for results Receive rewards for each arm x E A, reported by agents
For each arm in the support of m.))), calculate the average reward μ(x)
Compute X EEpppp((n) m((z)u(z)x, Vi = Ex mi(x)or T, 0 = V
Send to all agents
/* All agents and server: Eliminate low-rewarding arms
Eliminate low rewarding arms: A A: max.ea, x) 2-
4.3 REGRET AND COMMUNICATION EFFICIENCY OF DELB
We state our results for the elimination-basee 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 1, the number of pulls is most 48d log log + d2 log MT. Based on the analysis for elimination-based algorithm, we can show that the suboptimality gap (0", x) is most 2 2-1 with probability 1 1//T for any
pulled in phase 1. Suppose there most L phases, we can prove that B(REG(T)) < Ete Old 4'd2 log" TM) < Mog TM..
In each phase, communication cost comes from three parts: assigning average rewards of each arm and sending Ô agents. In the first and second part, each arm a E Supp(m) is designated to as few agents as possible. We can show that the communication cost
agents, receiving
"The Frank-Wolfe algorithm and its initialization are deterministic. We assign the pulls of each arm to as few agents as possible. See Appendix F For detailed description. 191, is always invertible when A₁ spans Rd. When A, doesn't span Rdd, we can always consider spa)(Ar)) in phase and reduce the number of dimensions.
8

---

Published as a conference paper at ICLR 2020
of these parts is O(M + d log log d). In the third part, the cost of sending 0 is Md. Since / is most (log T the total communication is ((Md + d log log d) log
4.4 PROTOCOL FOR LINEAR BANDITS WITH TIME-VARYING ACTION SET
In some previous work on linear bandits (Chu et al. 2011 Abbasi- Yadkori et al. 2011). the action set available at timestep may depend on t. That is, players can only choose actions from Dj at time while regret is defined against the optimal action in Dr. The DELB protocol does not apply in this scenario. To handle this setting, we propose different protocol DisLinUCB (Distributed LinUCB) based on LinUCB (Abbasi- Yadkori et al. 2011).
In our distributed algorithm, agent uses all samples available for him to maintain a confi- dence set Cr S Id for the parameter 0", In each step, he chooses an optimistic estimate d, = argmax (maxred(z, (x, and then chooses action Xt,; = argmax (z, 0r.)..).
which maximizes the reward according to the estimate fr.3. We denote Σ, -,- and Σ, Ir as W and U in our algorithm respectively. We use Wi, and Ut, to denote the sum calculated using available samples for agent at time step We construct the confidence set C.,, using W,, and U,
det (Vo,) 1/2 det(Al)-1/2
Ci.i = 0 Rd 110 Ollv,, $ /
log
1122
(1)
where Ve,, =I= We,i. 0,,, (AI W Ur. | := x² Vv. Essentially, without synchro- nization, agents in our protocol execute LinUCB separately. synchronization round, agents share all newly acquired samples with each other. The remaining question is when to synchronize.
XI
Our key observation, which comes from the analysis in in/Abbasi- Yadkori et al. (201T). is that the change in the fog-determinant of V, is good indicator of learning progress. Based this observation, only synchronize when agent finds that the log-determinant the last synchronization. We designed this synchronization criterion carefully such that, the one hand, regret close to the lower bound and on the other hand, the number of synchronization rounds small. The full protocol is described below.
f.; has changed significantly since
Protocol 3: Distributed Linear UCB (DisLinUCB)
for f 1,... T do
for Agent i = 1, M do Compute WG, = E. o, and V2, = 11.=1+2 E, Eydr using all available samples Construct the confidence ellipsoid Ge,; using W., and 0r,: - (21,,, Br,)) arg maX xc.,, 0)
Play 24,; and observe reward Vt,i-
Update Wr, and V,, if log (det /d, Vinst) (t -t- tiast)
then
Start a synchronization round
last L, Viast I Σ, F.Ur 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 (dvMMTlo'' (T)) with
O 5M communication cost.
Although the regret bound is still optrmal the communication cost has worse dependencies on M and d compared that of DELB.

---

Published as a conference paper at ICLR 2020
5 CONCLUSIONS AND FUTURE WORK
In this work, we propose communication--eficccnn protocols with near-optimal regret for both multi- armed bandits and linear bandits problem. For multi-armed bandits, we propose DEMAB protocol, which achieves V KT log(MM (M K) regret with M log( J)) communication cost. The communica- tion cost of DEMAB protocol matches the lower bound we proposed except for logarithmic factor. For distributed linear bandits, our DELB protocol and DisL.nnUCB protocol achieve near-optimal regret with O ((Md + d log log d) log T) and O (MLS d communication cost respectively.
An interesting open question proving lower bounds of communication cost order to achieve near- optimal regret in linear bandits. From reduction from multi-armed bandits to linear bandits, Thm. implies (MM communication lower bound for linear bandits. However, there still a gap between this bound and the communication cost of DELB protocol. We conjecture that close-to- 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 optimal risk rate.
ACKNOWLEDGEMENTS
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.
REFERENCES
Yasin Abbasi-Yad Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pp. 2312-2320, 2011.
Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263-22) 293, 2003.
Deepak Agarwal, Bee-Chung Chen, Pradheep Elango, Nitin Motgi, Seung-Tace Taek Park, Raghu Ra- makrishnan, Scott Roy, and Joe Zachariah. Online models for content optimization. In Advances in Neural Information Processing Systems, pp. 17-24, 2009.
Peter Auer and Ronald Ortner. Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem. Periodica Mathematica Hungarica, (1(1-2):55 65, 2010.
Ilai Bistritz and Amir Leshem. Distributed multi-player bandits-a game of thrones approach. In Advances in Neural Information Processing Systems. pp. 7222-7232, 2018
Mark Braverman, Ankit Garg, Tengyu Ma, Huy L Nguyen, and David P Woodruff. Communication lower bounds for statistical estimation problems via a distributed data processing inequality. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pp. 1011-
ACM, 2016.
Sébastien Bubeck, Nicolo Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, pp. 208-214, 2011.
Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In 2 Anmual Conference on Learning Theory COLT 2008, Helsinki, Finland. July 9-12, 2008, pp. 355-366, 2008. URL htth:://:oot/000es cs hels sinkii...... fad.fiii ftipaaprss 80 Dan.aaniiip. F
Eshcar Hillel, Zohar S Karnin, Tomer Koren, Ronny Lempel, and Oren Somekh. Distributed exploration in multi-armed bandits. In Advances in Neural Information Processing Systems, pp. 854 862, 2013.
10

---

Published as a conference paper at ICLR 2020
Dileep Kalathil, Naumaan Nayaar, and Rahul Jain. Decentralized learning for multiplayer multiarmed bandits. IEEE Transactions on Information Theory, 60(4):2331-234) 2014.
Nathan Korda, Balázs Szörényi, and Li Shuai. Distributed clustering of linear bandits in peer to peer networks. In Journal of machine learning research workshop and conference proceedings, volume 48, pp. 1301-1309. International Machine Learning Societ, 2016.
Tze Leung Lai et al. Adaptive treatment allocation and the multi-armed bandit problem. The Annals of Statistics, 15(3):1091-1114, 1987.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. preprint, 2019.
Lihong Li, Wei Chu, John Langford, and Robert Schapire. A contextual-bande approach to personalized news article recommendation. In Proceedings the 19th international conference on World wide web, pp. 661-670. ACM, 2010.
Oded Maron and Andrew W Moore. Hoeffding races: Accelerating model selection search for classification and function approximation. In Advances neural information processing systems, pp. 59-66, 1994.
Ilan Newman. Private common random bits in communication complexity. Information processsinnnposssi letters, 39(2):67-71, 1991.
Friedrich Pukelsheim. Optimal design of experiments. SIAM, 2006.
Jonathan Rosenski, Ohad Shamir, and Liran Szlak. Multi-player bandits-a musical chairs approach. In International Conference on Machine Learning, pp. 155-163, 2016.
Balázs Szörényi, Róbert Bekete, István Hegedūs, Róbert Ormándi, Márk Jelasity, and Balázs Kégl. Gossip-basee based distributed stochastic bandit algorithms. In Journal of Machine Learning Research Workshop and Conference Proceedings, volume 2, pp. 1056-1064. International Machine Learning Societ, 2013.
Chao Tao, Qin Zhang, and Yuan Zhou. Collaborative learning with limited interaction: Tight bounds for distributed exploration in multi-armed bandits. arXiv peprrnn::904.00220 2019.
Michael Todd. Minimum-volume ellipsoids: Theory and algorithms, volume 23. SIAM, 2016.
You-Gan Wang. Sequential allocation in clinical trials. Communications in Statistics-Thent and Methods, 20(3):991-805, 1991.
Yuchen Zhang, John Duchi, Michael Jordan, and Martin J Wainwright. Information-theorels lower bounds for distributed statistical estimation with communication constraints. In Advances in Neural Information Processing Systems, pp. 2328-2336, 2013.

---

Published as a conference paper at ICLR 2020
A
ORGANIZATION
The appendix is organized as follows.
Sections B are mainly about distributed multi- armed bandits.
we present omitted details for the DEMAB protocol. In Section C we analyze the performance of DEMAB and prove Theorem [ 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 we give proof of the
In Section B
the DEMAB protocol with little increase in communication cost. In Section
communication lower bound for multi-armed bandit.
Sections H are mainly about distributed linear bandits.
In Section 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 we analyze the performance of the DisLinUCB protocol.
Finally, in Section 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.
12

---

Published as a conference paper at ICLR 2020
B DETAILED DESCRIPTION OF DEMAB
In this section, we give detailed description of the DEMAB protocol and some subroutines used in the protocol.
Protocol 4: Distributed Eliimiation for Multi-armed Bandits (DEMAB)
D = [T/MK]] C2 = 1000, lo = [loga
J. my [4' log(MKT .4-1)
C2 (Kg(
/* Stage 1: Separate Burn-in
for agent i 1, ..., M do
L A =E1im -tl:=mimmmattee]i....
/+ Switching: Random Allocation
Generate public random numbers ri,., TK [M]
1ot1 {a |r =1]
/* Stage
Distributed Elimination
for I = lo 1,... do
Centralize has not been called then
/+ distributed mode
Agents send (1) B to server, Ni = 2i nf)
Nmar max; ni
(5)
if Ni S M then
10
Centralize, go line 22
if is not balanced then Reallocate
12
13
Server sends Naa to all agents for agent 1,... M do
Pull each a B(d) for my times, denote average as ûn(-) Pull other arms in round-robin for (Nmaz - [B:l)m; times
15
Send (arg max.' úz(a"), max,' (a')) to server
17
Server receives (a), mf,1) from agent j. and sends ut max, u²,, to every agent for agent 1,..., M
18
19
Elimination: (
B(a) (r((a) +2 2 ni}
20
21
else
/+ centralized mode
22
Server assigns arms in By to agents evenly and schedules my pulls for each arm Agents pull arms required by the server, and report the average for the pulled arm Server calculates (a). average reward for my pulls this phase, for each arm a E B
24
Elimination: B = E Bi : (a) + 2-1 2 maxjeB, (n)))
25
Eliminate: El 1mm nate executes the single-agent elimination algorithm. this function, each agent runs the single-agent elimination algorithm for D time steps, then return the remaining arms.
Protocol 5: El Climinate
Input: A set of arms AI, time step D.
for
1.... do
for E Ai do
Pull arm a for my [41+3 log(4- times, denote average reward as (a)
time step D reached, go to line
Elimination: Art1 = {a E A fa((a) > max (a(k) - 2-1}
Return At
In Reallocate the server announces the average number of arms; agents with more- than-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 number of arms. After calling
Reallocate:
13

---

Published as a conference paper at ICLR 2020
Real locato, nú 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: Ri 7
(M)
- /MJ
M (8)
Send "reallocation". n to every player
Receive a set ni (6)
arms, Ar, from player if mi > nt; Atemp - U,
for i 1, M do
m (0) n, send ni (i) ń arms in Atemp to player i, and remove them from Atemp Send the remaining arms Atemp to players Atempl (one each)
Protocol 7: Reallocate for Agents
if Receive "reallocation", then > ñ then Pick subset of ni n arms, A/, from (l()) and send them to server 0 = B A
else
Wait until receiving A₁ from server, B(x) B(9) A
When the number of arms drops below M, the subroutine Centralize is called, in which agents send their local copy of remaining arms, B(() to the server, and server receives Bi U ((().
Centralize:
Protocol 8: Central ize
for agent 1, M do [ Send B(() to server
Server receives B(() from agent i, and calculates B; U, B(
Assignment Strategy: In centralized mode, server assigns arms to agents the following way. Let N, = |Br]. If M is exactly divisible by Ni. for each arm in B,, server asks M/N: separate agents to play it for [mNNi times. not, we allocate pulls to agents the following way: Let Pl N MM denote the average pulls each agent needs to perform. Our assignment starts from the arm with the smallest index 0k, and agent 1. For arm ak,, and agent i, agent has been assigned pt pulls, designating arm akj+1
agent 1. If have finished allocating my pulls for aky, continue The assignment is finished until all pulls are scheduled to agents.
C PROOF OF THEOREM
In this section, we give 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, to represent B(") .... ((A) (in the distributed mode) or B3 (in the centralized mode). It refers to the set of remaining arms at the start of the 1-th phase at stage 2, either held separately by the agents or held by the server.
Suppose that the protocol terminates when / l'. We also let (ar t) = E ΣM [a. = a] be the number of times arm a is pulled before time step Without loss of generality, we assume that arm 1 is the best arm, and define Ag := μ(1) u(k).
We first state few facts and lemmas.
Fact We state some facts regarding the execution of the algorithm.
1. At line 6 of the server's part in Real locate, Atempl M;
14

---

Published as a conference paper at ICLR 2020
2. After Reallocate called, < (1()))
1: B B) is balanced;
3. For any player i, the mumber of completed phases in stage is at least lo = log, log MR) and at most LD |logs 1o M
4. The number of phases stage 2 is less than L 4 + 5 5log (K) = O (log(MK)),
(1) Proof. 1. Let 5 = f n4
2 n and S = fi: n( < n.. At line of server's reallocate
code, server receives Eies-
ni
(8)
7t arms. At line 5, Eies (n ni ) arms are removed. So at
line 6,
Atempl = Σ
(ml
- 7)
Σ
(n - (2)
Σ M
( n
ML Σ
Ti ( /M] <
M.
iEST
iES
(E[M]
Let (6) = | max; ni < 2 min; ni ( the reallocation procedure will do nothing, and (m/ (1) ,..., mi ( ( reallocation procedure, every player has a new set arms B,d) such that ñ S |
by definition balanced. If max; ni (4) > min; ni
(6) tten at the end of the
(i)
S n +
This
(0) implies that the number of arms is balanced, since when reallocation is called, E, m > M.
3. The length of the 1-th phase stage 1 is at most K [T4 log(4 1og(4-|MTT]] After phases, the number of timesteps is at most
4'+1
(og(44"MMKT) + 1 3
K
4p+ 1og(4~PMKT)
<
Setting C2 = 1000 and lg = [logı
D
J. one can verify that
T2K log MR
10 14
1
256D
+ 1 S.D.
Log(4~lo
3
3C2 log(MK)
Since the total number of timesteps in stage is D, we know that the number of completed phases in stage is at least lo-
On the other hand, in I phases, the number of timesteps is least
Σ 41+3 (gg(4 > 44+3 log MKT)..
D By setting C²2 512 and lo log Cg log MK D. Therefore, the number of of completed phases in stage is at most lp.
show that 4'0 log(4-lp MKT)
Suppose that stage has L + 5 log(M K) phases, then the total number of phases during stage 1 and stage is least lo- In phase + In. at least 4lo+++3 log (4-(+++L) M MKT) pulls are made. With some elementary calculation, one can show that the number of arms pulled in phase MK L lo is MT. To log log(MK) which is even greater than the total number of timesteps MT. That is say, the number of phases in stage 2 is less than T..
Via 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 I of stage 1 be (.a()))) Ar stage we denote the following even as Ae: phase at stage 1, for any agent i, for any amm a E A
(i,,(a) u(a) S 21-11
Then Pr [Ar 1 -2.4//(KTT)
15

---

Published as a conference paper at ICLR 2020
Proof. For any agent i, any phase 1 S lD. denote the empirical mean for arm in phase I by (.,(a). By a direct application of Hoeffding's 's bound and union bound, we can observe that for any fixed 2, by Hoeffding's bound,
{
1 my 4 1-11
2 2.4'
Pr [lAr,(a) u(a)l > 2-1 S 2 exp
2
(MK)²T
union bound for arms a E A and all agents E [M] proves the lemma.
Lemma C.2. For phase in stage A ... As implies the following:
1. 1 Affi
2. Vi E [M], Va E A 2 p(1) -2 22-111
3. Recall that (M, t) = EEj= EM [as.j kk] is the number of times arm l is pulled
for all agents before time step t. If l = [log2 A, + S I, then Nu (i. D) s C5 M
log Cog
(
In particular, let lD be the maximum number of phases for all agents stage 1. A A A Alp also implies the following:
4. 3i E [M], E ( 1o+1
5. E [M]] Va E u(a) 2 p(1) - 2-
Proof. These results are direct implications of lemma C.I
Notice that if A happens,
(1) 2 p(1) 2-1 x(aa 2-11-1 2v,(()) 2
Thus, arm 1 will never be eliminated throughout the first phases.
2. A implies that for any A
(s,((a) 2 max (k.)(k)) -2 2---222- (c.(1 - -2 kEA
which means
(aa) 2 (a),(a) 2 (1.,(1) - 22- 2 p(1) 2-111
From statement we know that A A... A implies that arm will eliminated after phases, which is less than 1. Therefore, before eliminated, the total number of times arm i is pulled at stage by any agent is at most
4/+41 3
(10g(4~hMKT)+ + !)
Cs logo (MKTA?)
Σ my S
A?
for some absolute constant Cs. Multiplying by M proves the assertion.
4. Let (t) denote the remaining arms at the end of stage for agent i. From statement 1 we know that A -..-A Alp implies E (+) for any E [M]. So at line protocol 1, arm will be assign to agent Ta-
5. Let A(1) denote the remaining arms at the end of stage I for agent i. From statement 2 we know that A₁
A Alp implies μιa) μ(1) 2 2-1 for any arm in Ule A Here (6) denotes the number of phases for agent at stage 1. Since Bi Uie(M] ((6) ( a subset of Use[M A
and 4 > lo. we conclude that Va E Bi uua) 2 p(1) - 2 1 > ((1) - 2
16

---

Published as a conference paper at ICLR 2020
Lemma C.3. For 1 >> ly, denote the following event by 94: stage for any E Bi,
(ār(a) - ulaa S 2--1-1
Then Pr [St) 2 2. 2 2
Proof. Recall that for any lo. ún (a) is the average of my independent samples of the reward from arm Therefore, for fixed and by Hoeffding's 's inequality,
Pr [[ - p(a)) > 2- - 2 exp
2-
{-1 1 mi
1-111 1 (MK)2T
2.4
2
A union bound for all a E B3 proves this lemma.
Lemma C.4. Recall that D; = (u(1) slt). I, > O, ler 4 = flog2 4,
+ 1. Let denote
A1 A A Asp- Then at stage 2, A A Qtp
S4; implies the following:
C4 (olg(MMTAA) + (aa),
(M NM <
A
where C4 a universal constant, and Ene(K] m(a)= S M log M.
Proof. Suppose that [B:] > M. By Fact at phase 2 to + in stage 2, the sequence B
B
B(A0) is balanced. Therefore, during phase stage 2, the number of times
an arm in B, is pulled is at most 2m,.
[B]] S. M, an arm in B, also pulled at most 2m, times, unless |Bil-m < M. that case, a phase only lasts for 1 timestep. This is possible only when my < M, which requires < [log, M < log M. We denote the number times a is pulled in such phases by 17(a).
On the other hand, let 4 = [log2 2, + ++ 1. If I lo. A2 implies that é & Bl,+1. In that case, the number of times arm i is pulled after timestep D is Assume Dot A... Ω2 holds and E B,,. Then
u. p(1) 2-11-1 2 ((1) + A - 2-4-11 in +-
Therefore, Sig+1 A... A Q4 implies that i $ Bi,41. In this case, number of times arm i is pulled is
4+1
(1 - (is D) <
2m + 7(a)
1=p+1
8 1+4
log(MKT 4 4-4-1)+ 1 3
L n(a)
2 log (MKTA)
+4 + (MK) 1((a)
3A
(215_ 27)
log (MMTA)? + (a))).
3A
It is not hard to see that Eme(K ((a)= M log M.
Lemma C.S. Let l 2 lo and n4 Bi With probability 2LK5, either n4 21M log } or no reallocation is performed before the start of the 1-th phase at stage 2.
Proof. Let Y., I B.]. X1,, = I[r;= i [K],j E [M]. Observe that X1,5 and Y: independent. This is because the elimination process between B, and B uses exactly mi
17

---

Published as a conference paper at ICLR 2020
independent samples for each arm; therefore, the conditional probability for remaining has dependence which player arm is assigned to. Let Y denote (Yi,,, Vi, J.. Since
B
Y
B
n
Yu..
by Chernoff's inequality,
4
K
2i-1 YL
K
Pr
Yi,
S exxp
3M
21M
K
2
K
K Liml Y1,
Pr
YuxKs
<
Yi,1
8
S exp
3M
18M
Consequently,
4
B
B
B
Pr
21M log
3M
3M
14t 18M
21
exp
21M
exp
n4 21M log
8)
21 28.
Note that 2
3M
[
<
3M
4
B for all j E [K] implies that (B((1)
B B(a0)) is
balanced. Therefore, if 21M log J. with probability 1 2(1 Ko,, no reallocation will be performed before the 1-th phase at stage
Now ready to prove Theorem
Theorem 1.
The DEMAB protocol incurs O ( MT log(MK)) regret, O (M log MK) com-
munication cost with probability 1 - 8, and O (M log(MK)) communication cost in expectation.
Proof. Regret: Let 4 [log2 A, 11 + 1. By Lemma C.2
when A ... A Ar, holds,
NM (i, D) < C, Cg (Mg(M))A3)
A
Therefore, the probability that this does not hold most
2 4
128
Pr
MKT
3MKTA?
Thus for any arm i,
E M D)) < C.M log (KTA?)
128
MD
A
3MKTA
C&M log M (KTA?
64
A
3A
Similarly, if 2 lo. when A Do0 A Qr holds,
C4 lo (i))
NM(i,T) NM(i,
A
The probability that this does not hold is at most
A
4+1
Ω
2 4P
4F
256 C.
C
+
3
-
600
MKT
M
MTA?
MTA?
p=
p=la
18

---

Published as a conference paper at ICLR 2020
Therefore
Cs log( M (MTTA))
600
E (i, - (a D)
+ +
MT
A
MTA?
Ca Co M MKTA
600
(1).
A
A
follows that
K
ANr(( D)]
E
A A. (Nr Dj]+ Σ
(Nr( D))
a:d.2E1
a:
C5 (MKTe) + 256/3
K
+ MD
61
Cov MTlog(MMs
where in the last line we choose El
K KogiK) K) T
and Ce is some absolute constant. Similarly,
K
A E. (NM(a,T) (ar D)J
E
A,E T) - Na, D)] + MT
a:A.2<2
S M log M K C4 (olog(MKT(3) Cg
62 MT
62
S M log M + (3C4 + 601) MKTlog(K),
where in the last line we chose Therefore by the definition of total regret,
logiK) MT
By our assumption, M log M S MTK log(K)
K
E [
Σ A. ( D)
Σ
Aa (E (N -N D)I)
< Ca CaV Mog + (3C4 + 601 1) / MMTT
s 2 max 3C4 + 602) v MT(K log (K) + log (MK).
Communication: Total communication in stage 1 O. We first consider the worst case communica- tion cost in stage? 2. Note that during phase (either in distributed mode in centralized mode), the communication cost is ((M) if reallocation not performed. The cost for reallocation at the start of phase / is O (minn nu, ny r2,) where I' is the last phase where reallocation performed. Summing this over all phases (at most L = Ollog(M (M K))) in stage 2, we conclude that total communication cost for reallocation is O(ML K).
Define 4 to be the first phase such that reallocation is performed. Then, our argument above shows that communication cost is O(ML + n1,). If n4 21M log J the event in lemma C.5 will be violated for some 1. The probability for that most K By resetting 6, we can show that with 21.2K Therefore, with probability 1 5, total communication
probability 1 8, n,, 21M log cost
o
o ( ML (MLL+ 21M log 8
222 )) =0 -0 Mog log
MK
In particular, by choosing 8 1/K, we show that expected communication cost is O (M lM)(M))).
Theorem 5. When - ly = 0 in DEMAB, the protocol incurs near-optimal instance deppedee regret O(EkAe>0 >o AF log + M Mo. With probability 1 8 the communication cost is O (M ( The expected communication cost is O (M log T)-
19

---

Published as a conference paper at ICLR 2020
Proof. Regret: In the case D 0, it can be seen from the proof of Theorem
that
E (1, T)) C4 Colog(MKTAA) + 17(()) + A?
600
A
where ΣiE[K] (11)= S M (M). It follows that total expected regret is
C1 (log(MKTA3)++
E
Σ (i,
Σ Ami(t)+
Σ
A
LiA
:A,30
:A:30
M Mlog(M) +
Σ
A
log
k:AE>0
Communication: By the proof of Theorem 1 the worst-case communication cost of this protocol O (M log T' + K). This is because we need ((M) communication at the end of each phase to perform elimination, and most a total number of O(K) additional communication among all phases to perform reallocation.
Let (* be the last complete phase such that 41++1 21M log( (K)) By lemma C.5 no reallocation needed before phase l" with probability 6, so the total communication before phase I" + O(MT'.
From the beginning of phase 1" + 1, the total communication in the following phases at most O(ML' M log(KL'/o))
Therefore, with probability 8, the communication cost is (M log T + Mlog(K1./0)) (L//0)) = O (M log(T/8)). Let 5 1/K, the expected communication is O (M log T + (MT' + K)/K) O (M log
Finite precision: We now show that only Ollog T) bits are needed for each number sent in DEMAB. The integers sent in DEMAB are numbers in {0...., K}. Therefore O T) bits are sufficient for each intege ITT In the DEMAB protocol, the only real numbers that are transmitted are the average reward phase. In our proof, it is only required that the average of my samples is TT 347 subgaussian. In fact, the average of my samples is [+3igg suugaa/a -Sbbgaussian.
Therefore, we can use randomized rounding for the average reward with precision = T7 Then, the rounding error for each real number has zero mean, and is Mo -uugaussian. When computing the average of my samples at phase I, at most M rounding error terms will contribute to it, whose sum is 2T43 MMTgggMK4447 K74-T -Subgaussian. Therefore, the concentration inequality in lemma
C,3 and consequently our main theorem still holds. Apparently log, O (log(MT)) = Ollog T). Therefore, expected number of communicated bits is Ô (M log K) T).
D REMOVING PUBLIC RANDOMNESS
The DEMAB protocol makes use of a public random number generator. can be viewed as a sequence of uniformly random bits written public blackboard that every agent can read, and reading from this sequence does not require communication. In practice, this can be approximated by using 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 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 's Theorem Newman (199T). 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.
Recall that T > K.
20

---

Published as a conference paper at ICLR 2020
There exists protocol for distributed MAB that does public randomness with expected regret MMKTTlll It has communication cost bounded by O(M log(MK) + K) (worst case), and expected communication cost (M log(M
Theorem 6.
Proof. We make the following modifications to the original DEMAB protocol. Instead of using a public random bit string s we predetermine strings $1.....B (which can be hardcoded in advance), and randomly choose from them. That is, the server will generate random number uniformly distributed in [B), and broadcast it to everyone. The communication cost of doing so will be M flog2 B). We now analyze how the choice of ....... B affects the performance of the protocol.
In terms of regret bound, observe that for any random string 8, the expected regret of any bandits instance X is always D(MMTTTo T). Therefore, regret bound will not be affected when public randomness is removed.
Now define / (XX,)) 8) to be the expected communication cost of the DEMAB protocol using the public random string s and interacting with the multi- bandit instance X. Our analysis for DEMAB tells us that _e1, VX,,
Ry [f(x, x) S e₁ M Mog(MK)
Therefore, if we draw i...d. uniform bit strings ..., SB.
B f(x, si)
E
Σ
S C. log(M)..
B
We say that a set of bit strings {s ... SB} is bad for bandit X if
s(X,
f(X,s:) > 20 MlgMMMK)
B
We know that there exists > 0 such that 0 < f(X, S c2(M log(MK) + K). Therefore, by Hoeffding's 's inequality,
EI(, 20, log(MK) MoggK)(MKK B
1
2Bc M log(MK) c2(1 + K/(M log( (MMK))
Pr $1
exp
In other words, for fixed X, the probability that we will draw bad set {si, 3B) is exponentially small. Therefore, for a family of bandits with size Q, the probability for drawing a set of $1, $1...., $B
that is bad for some bandit is at most Q exp ca(1+ log( [K]] J. If we can show that this quantity is smaller than 1, it would follow that there exists {si,... SB) such that it is not bad for any bandit in the family.
2B M log( MK)
Now, we consider the following family X' of bandits. For each arm, the expected reward could be a/A, where {0. 1,.., A AA-T] []. The reward distribution is Bernoulli. The size of this family is Q S (A-1 that X, is Bernoulli bandit, and that the expectation of each arm is in /1/4,3/4|) Apparently we find a bandit Xº X' such that their expected rewards are A-close in || ll As result, the KL- divergence of each arm's reward in X, and X2 is ( Let H(X) = {01.1. T1,1, aT,M TT.M) be the random history of the DEMAB interacting with the bandit instance X. Since communication cost determined given (X), Vs.
+1)* 11)"
Now, consider any other bandit X1. Without loss of generality, we can assume
1f(X1, f(X2, s)1 S 02 (M log(MK) + K) (Tx)
o ((M (M)gg + K)- VTMA).
With A = K the right-hand-side is O (M)).. Therefore, it suffices to consider the bandit family X.
Bhhich has K[ K[log, M] hits For general bandit instance X1, when reward is received, can generate Bernoulli reward with expectation r/2 + 1/4 to replace it. The regret bound will increase only constant factor.
21

---

Published as a conference paper at ICLR 2020
Therefore, only need to guarantee that 1+K/[M log (M)) C' log MKT, where C" is universal constant. This can be met by setting B 12C K log(M In this case, we can such that for any bandit instance X, when choosing randomly from this set, the expectation of ((X,s) 9) is O log(MK)
BM log( MK)
guarantee that there exists a of bit strings ..., $B).
The additional communication overhead for generating the random string (in bits) is
O (M log B) O (M log K M log log(M
Therefore, under our usual assumption that T max [M, K), the number of total communicated bits is bounded by O (Mlog K + .M log T). In our formulation, we may view log T bits as one packet. Therefore additional communication cost O (M). follows that total expected communication cost is ( log( ()).
E PROOF FOR THEOREM
Proof. In order to prove the theorem, we show that for any protocol with communication cost less that M/ (c a constant), the regret is at least Q(M v KT).
First, we list two lemmas that will be used in our proof.
Lemma E.1. [Latimore & Szepesvári algorithm with expected regret
2019 Theorem 9.1) For K-armed bandits, there is an
REG(T) S 38VKT. KT.
Lemma E.2. (Lattimore & Szepesvári there exists an instance such that
2019 Theorem 15.2) For K K-armed bandits, for any algorithm,
REG(T)2 Z V (K-K11) 1)T.
75
The original lower bound is proved for Gaussian bandits, which doesn't fit exactly in our setting. we modified the proof work for Bernoulli bandits, which results in different constant.
We now prove the theorem's 's statement via reduction from single agent bandit to multi-agent bandit. That is, 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 receive.
Consider a communication protocol with communication cost B(M). We denote X; (i [M] to be the number of integers or real numbers that agent sends receives throughout run. X, is random variable. Since expected communication cost is less than M/c,
E.X, SX,&S//
Denote S as the set of M/2 agents with smaller EX;- The expected communication cost of any i E S is most 2/c. For any E S, P(X, 1) EX, < 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 j.
The simulation is as follows. Interacting with single agent bandit with time T, we run the code for agent in the protocol. When no communication is needed, may proceed to the next line of agent i's code. When this line code sends message or waits for a message, we terminate the code. In the rest of the timesteps, we single-agent optimal algorithm (the one used to realize lemma E.
Then, if agent j's code has probability of involving in communication, and if agent j's regret REG, (T) < A. via this reduction, we can obtain algorithm for single-agent MAB with expected regret
REG(T) A + 38v KT.
22

---

Published as a conference paper at ICLR 2020
By lemma 2, (TG(T) cannot have regret upper bound better than v V 1)/75. Therefore
38v 2 V(K 1)7/75.
388 < 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 Ω (MVKT).
F OMITTED DETAILS OF DELB
Assignment Strategy: At line
assign pulls to agents in the following way. Let pt [2 m=) denote the average pulls each agent needs to perform. Our assignment starts from the arm with the largest mi m²(x) and agent 1. For arm 2g and agent i, agent has been assigned with Pt pulls, turn agent + 1. If we have finished designating m2(2)) pulls for arm Ih. continue designating arm Z8+11. The assignment is finished until all pulls are scheduled to agents. Observe that at the start of each phase, each agent has the same Ar the server. Therefore, at line 3 they obtain the same Ti, with the support size at most log log d. In that case, the server only needs to send index (0(1) communication cost) over 48d log log arms, instead of vector (!2(d) communication cost), to identify an arm I E Supp(T)).
G PROOF OF THEOREM
First, we consider some properties of the elimination based protocol for linear bandits. Fact Let denote the total number of pulls in the 1-th phase, then
C d2 log MT s Ti S + + dd log MT,
where & 48d d.
For an arm in the core set Supp(m:). the DELB protocol pulls it [C14'd' log MT times. Thus total number of pulls in phase satisfies
Proof.
Σ
mi(a)
Σ
C,l'd 2 C14' log(MT),
(E
aESupp(R1)
and
Σ mi(a)= <
Σ
(C)4 S 48d log + C,4'd log MT.
aESupp(m)
@ESupp(m)
Lemma G.1. In phase I, with probability 1 1/TM, for any a e D,
(0 10-00 0-, 2-
Proof. First, construct e--covering of D with = 1-2 Denote the center of the covering as X (ū1,... ..., ZQ}. Here Q satisfies Q 3d2d((+2)
Assume that Ô is calculated from linear regression Ti, . Fe. For fixed E D, is known that (0 .) is subgaussian with variance proxy
(x, V..VV x2,) 2== =|101 S 2/1
(2)
$=1
Therefore with probability 1 1 25,
(0 0r xx)
$ $ ||0|| 12 log
23

---

Published as a conference paper at ICLR 2020
Suppose pulls are made in phase l. In case,
|| |, S g(T)
2
log MT
Therefore with probability 1 25.
(0 0- 2x)
S 2--++1 I+1
2
log
Cid MT
Choose M/)2 It can be shown that with C = 600,
2 2log(2MTQ) log 2 + + d log 3 + 2d log 2 + dd2
1
Cid MT
300d
64
Therefore with probability 1 M/(TM), for all X (0 0r x) $ 2-1
Now, consider an arbitrary a D. There exists 5 E such that ||> ø|| s 2 21-2, Therefore with probability 1 - 1/TM, for any D
(0 0 x)
- (0 0", x)
+ (0 - 0 s)
2 2-111 110
1- 101-11 ||
$ 2-
Lemma G.2. Let x² arg max ,x) be the optimal arm. Then with probability 1 log( (g(MM)/(TM) x² will not be eliminated until the protocol terminates.
Proof. x² is eliminated at the end round I, one the following must happen: either (1)
(0-0" 0" x-) 2-1, (2) there exists x*, (0 0* xx) 2- Therefore the probability for r to be eliminated at particular round is less than 1 1/(TM). The total number of phases is at most log MT. Hence union bound proves the proposition.
Lemma G.3. Suppose d (PggTM))TTO and A5 denotes the suboptimality gap of x, i.e. A, = (0", ,x' - -x). For suboptimal E D, define L in ...-- An). Then with probability 8, for any suboptimal x, & AI,-
Proof. First, let us only consider the case where x² is not eliminated. That is,
Pr E D x E A. S Pr [æ'is eliminated] Pr [Bx At,-1, x E Ar, 1= E Ar,] Note that conditioned on x² E Arr fo Ar,1 ArE A implies that at phase ly 1, either (0 10-00 0r, .n) > 2 or (0- - 0-,x*) 2- Therefore the probability that there exists such is less than log(TM)/TH)) Hence, with probability (oggTM))TMM will be eliminated before phase Lg.
We are now ready to prove our main result for DELB.
Theorem 3. DELB protocol has expected regret O (dvTM log T), and has communication cost O ((Md + d log log d) log
We note that at the start of round the remaining arms have suboptimality gap at most 8-2 2- Suppose that the last finished phase L. Therefore total regret is
Proof. Regret:
REG(T) < A log MT 8 2- + 2MT
1
od TM.
24

---

Published as a conference paper at ICLR 2020
Apparently Cf log TM S TM. Therefore
REG(T) S v C3 TM & CrdyTM TM.
Under our usual assumption that T > M, this can be simplified to ([g//MMlogT) Here C3 and T7 are some universal constants.
Communication Cost: Let pi =E, my (x) 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 + [mi(2)/pi agents. Therefore, total communication for scheduling is at most
([mi(=)/pi) 1) s 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 + dloog log d). On the other hand, total number of phases is apparently (log TM). Hence total communication is
O ((Md + d 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 less than max } (recall that & = 48d log log d). Therefore, every integer can be encoded with (log(d))) bits. remains to be proven that transmitting each real number with logarithmic bits is sufficient. In the DELB protocol, two types of real numbers transmitted: average of rewards, and entries of 0. To transmit real numbers with finite number of bits, make the following modifications to the original protocol: 1. when transmitting average rewards at line 5, use randomized rounding with precision 6 1 M²7: 2. after computing 0 = V, X at line 7, let Ô be the entry-wise rounded
vector of with 62 AT7Z
It can be seen that we only need to prove that after the modifications, lemma G.1 still holds. In each phase, originally μ(r) is m,( -uugaauuuaasiia but only required to be my((r) -subgaussian for (2) to _
still
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 MT me(=] Therefore. after the modifications, the computed p(x)) is (a) -tusssaauusssn, hence, holds. It follows that with
probability - 1/(TM), for all x E X, (0 ,", x*)x) $ 2-1-2 Therefore, for any E D,
(0 (0-0 0", x)) 2--111
Combined with the fact that for any x E D,
(0 1 0) I ||@ ا| Vdez < MT --1111
we can prove that with probability 1 - 1/(TM), for all x e X,
60- 0", .)) -11-2
Therefore, after the modifications, the regret of the protocol is still (d/TM log T). The amount of communicated bits is thus
O ((Md + dlog log log T log(dT))
25

---

Published as a conference paper at ICLR 2020
H PROOF OF THEOREM 4
First, let restate the DisLinUCB protocol in full detail.
Protocol 3: Distributed Linear UCB (DisLinUCB)
D log log (d))
for Agent i = 1, ...., M do L Set W sym,; = 0, U Usyn, = O, W Wewwii O, Unew,i = O, flast = O, Viast = AI
for f 1.... T do
for Agent i = 1, M do
Vt, = AI W sym,e W neww, 0r,- Vi,i (Usyn, Unew,)).
Construct the confidence ellipsoid Ci, using Ve, and 01.
(Ki,i, 02,i) arg maX(x,0)ED.xX... (ar, Play di, and get the reward Vt,é- Update Wnew.i = Wew,,i + Te, Unew,i = U Unew,s + Dt,i
10
11
Ve,i = + Wsy..i + Wnew,.
if log (det V Viast,i)
(asst) D then
13
Send synchronization signal to server to start a communication round.
14
if communication round is started then Send W new, and Unew,i to server
Server computes Wyn = Weyn + EE= Wnew.j. Ueyn Usy + Eje Unew. Receive W Wayn Usyn from server Set W Wnew,; 0, U Unew,t Mast
16
17
18
Viast AI W Wsyn
Let us then state several lemmas that will be useful in our proof.
Lemma H.1. For any with probability M, 0* always lies in the constructed Ct, for all and all i.
Proof. Using Theorem 2 in /bbasii Abbasi-Yadkori et (201T) and union bound over all agents, we can prove the lemma.
For any positive definite matrix Vo Rdxdd any vector x E Rd, define the norm of x w.r.t Vo as |,ll|, == VxTVon
Lemma H.2. (Lemma 1l Abbasi- Yadkori al. 2011
Let {x,)==) be sequence in Rdd, V is
x d positive definite matrix and define V. = V
Σ.=1
X, X.T Then we have that
det (Vn) det(V)
log
X 12 7-
Further, if X S I. for all then
det 1, [1 } < 2 (log det (V.) - log V) < (dlog ((trace(V) nL?) /d) log det V).
Using Lemma we can bound single step pseudo-regret Tt,
Lemma H.3. With probability M6, single step pseudo-regret Tt, (0' D1,s) is bounded
by
Pa,s E (121og det
+ +x1/2) | =0 =o |
5
(3)
26

---

Published as a conference paper at ICLR 2020
Proof. Assuming 0* E Cr,i.
Tt,i = (0" ,x)) , x(,))
I (0r, 21,a) . - 10" xr,i)
(0e,- H¹, IILI)
(0e.s Br,s, D1,i) + 10c, 0", I2.,)
- | 6,,i Vi,
I + | 000
22og dee()))))/dde((())-
det
< 2
+ 1212 Isselllugs
T Vallog
|
Now we are ready to prove Theorem
Theorem 4. DisLinUCB protocol achieves regret o (dVMTlog((T)) with O &M com-
munication cost.
Proof. Regret: Set 6 1/(MMT), the expected regret caused by the failure of Eq. (3) is at most MT 1/(MT) = (1), thus mainly consider the case where Eq. B holds.
In our protocol, there will be number of epochs divided by communication rounds. We denote
Viast in epoch p as Vz. Suppose that there are P epochs, then Vp will be the matrix with all samples included.
Observe that det Vo = dot(AT)= 1d. dot((p)) -
(r(Vp)
S (A++ <A+MMT Therefore
(Vp) log det((V)
MT
< dllog
1+
Ad
Let R [d (1+ + XF) It follows that for all but R epochs, we have
det V det V,-1 < 2.
1
(4)
We call those satisfying Eq. good epochs. In these epochs, we can use the argument for theorem
4 in Abbasi- Yadkori et al. (2011). First, imagine the MT pulls are all made by agent
in round-robin fashion (i.e. he takes F1,1, 21,2..., II,M, 22,1 IT,M)) We use V,, AI E ((og)) "p. denote the Ve, this imaginary agent calculates when he gets Tr.i If Te,i one of those good epochs(say the j-th epoch), then we that
det Vi,i 5
det V,
< 2. det Ve, det V₁-1
<
Therefore
T
F1 0
dlog
V Fhe
T Vie x1.i
T
det Ve,
0
xi V. xn, det Ve,
V
0
(1 dlog
T
2n V.s x0.
27

---

Published as a conference paper at ICLR 2020
We can then the argument for the single agent regret bound and prove regret in these good epochs.
We denote regret all good epochs as REGgood: Suppose B, means the set (t, i) pairs that belong to epoch p, and Pa good means the set of good epochs, using lemma H.2 we have
REG good
ΣΣ Tt
MT Σ
Σ
2
pE pEPdood (1,5)EB,
00
T dMT 8
Σ Prood (L,))EB,
Σ min (Iee:lliTz
det (Vp) del (Vp-))
00
dMT log
log
Pood
det (Vp) det (Vo)
0
dMT log(
log
0 dv MT MoTTog(MT))
Now we focus on epochs that are not good. For each bad epoch, suppose at the start of the epoch we have Viast Suppose that the epoch starts from time step fo, and the length of the epoch is n. Then agent proceeds as V to,is ... Viotnii Our argument above tells us that regret in this epoch satisfies
REG < (Vilog T/8
Σ
min (1eesall :. s O (Vilog T/8)
Σ
log det Vlast
det Viotn.
1= 1o
Now, for all but agent, n log
det Vigttni det Veave
< D. Therefore we can show that
-VD. Since de((V)) + MT/d)", we know that the number of such epochs are rare. (Less than R = Odlog MT)). Therefore the second part of the regret is
REG(n) S (V
RFGbba O (Md log" 1.5 MT). D2/22
If we choose D
log MT) dM
then REG(T) O (dvMTlog' (MTT)) Since T> > M, we have REG(T) = (IVMMTloo22
Communication: Let a
(P
Apparently there could be most [T/a] such epochs that
contains more than a time steps. If j-th epoch contains less than a time steps, log det V det V,
Since
P-1
det Vj++1 det Vp S R, det Vo
log
log
det Vj
j=0
There could be most a number epochs is at most
epochs with less than a time steps. Therefore, the total
1
T
Ra o D
TR D
With our choice of D. the right-hand-side is O (M). Communication is only required at the end of each epoch, when each agent sends ( numbers to the server, and then downloads (dd) numbers. Therefore, in each epoch, communication cost is O(Md). Hence, total communication cost is O (M1.5.33.
28

---

Published as a conference paper at ICLR 2020
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, is observed, we replace it with a random integer in {+1} with expectation St,i- Second, after line 8, after 34, is played, we round each entry of T1,i with precision 6, and use the rounded vector in the calculation in line 9. In this case, each entry of W Wnew, and Unew, is a multiple of e². Therefore, transmitting them requires (dd loge=!) bits. The total communication complexity is then O (M dه log - bits.
Finite precision:
We now discuss how to choose such that regret is not effected. Define
REG (H)
max (x Te,i, )r); xED
M
T
REG (H)
=
max (v - Tt,i, 0-).
ZED;
1=1
Here H is a shorthand for a history (I1,1, $1,1, TT MT.M). ). D refers to set of rounded actions. For every E DD there exists I D such that | =|| S dd.. Therefore
REG (70) - REG (70) MT
On the other hand, let be the (random) history of the DisLinUCB with rounding on action sets D., while H is the (random) history of the DisLinUCB with rounding running on action sets D,, Then at each time step, the mapping from past history to the next action is the same. Therefore KLHH H) O(MTde)). It follows that
E REG (70) E REG (D) < (VM3T9
(
When the action set is D., no rounding is needed, so the regret analysis for the DinL.iUUBB protocol without rounding directly follows. Therefore,
E [REG (H)] = (dVMMloo" (N))=((NTT))3'T)
By choosing = (MT) -1, we can guarantee E [REG (H)) = (dv A.VMTlog' T) for any action set. In this case, the total number of communicated bits O 5, log log
DEMAB AND DELB IN P2P COMMUNICATION NETWORKS
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 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, 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 (log(MM)) communication stages in DEMAB and Olog 7) communication stages in DELB, the extension of communication stages incurs at most O 2 log M K)) regret DEMAB and O(M² 20aa//oog7 T) regret in DELB for M agents. When the time horizon T is large (i.e. T > M log M), the additional term is dominated by Another issue for P2P networks is that there no longer physical server in the networks. To solve this problem, we can designate agent the server: agent 1 will execute both the codes for the server and the codes for an agent.
/MKTllog T') and O (d/MT'log
Specifically, by saying "extending the length of the communication stage", mean that Procedure and [I] to realize communication subroutines used in our protocols in P2P networks:
sending message to the server and receiving messages from the server.
29

---

Published as a conference paper at ICLR 2020
Procedure 4: Server2Agent: Agent 1 sends message my to agent i in a P2P network.
For the next M 1 time steps:
/* For agent 1:
Send my to agent + at the i-th step
Pull an arbitrary arm each time step
/* For agent i(i>1) 1):
#/
Receive my from agent 1 at the (i - ))stt step
Pull an arbitrary arm each time step
Procedure 5: Agent2Server: Agents i(i > 1) sends message my to agent in P2P network.
For the next M - 1 time steps:
/* For agent 1:
Receive m4+1 from agent i + 1 at the i-th step
Pulls an arbitrary arm at each time step
For agent i(i 1):
Send m, to agent at the (i 1)-st step
Pull an arbitrary arm at each time step
1.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 T by Procedure Server2Agent and Agent2Server. In this way, it costs M time steps instead of a single time step to collect, aggregate, and boardeast information. We have the following theorem showing the efficacy of distributing DEMAB in P2P network.
Theorem
The DEMAB protocol in P2P networks O (v MKTllg T + M log( MK)), with expected communication cost O (M (MMogg(KK))
incurs
regret
When T > M log M, the regret bound of this protocol is near-optimal O (VMKT
We compare DEMAB protocol in P2P net with the original one (i.e. Protocol I 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 no shorter than that in Protocol Therefore, the number of phases after phase to + 1 (included) in new protocol is more than that in Protocol [ which is ((log(M (MK)). In each phase starting from phase to + 1, new protocol needs O(M) additional steps to complete the communication in this phase, incurring ((M) additional regret per agent. Therefore, this protocol incurs ((M2) additional regret per phase starting from phase 4, + 1. The total regret of this protocol thereby O (VM KT log + M log (og(M)))
Proof. Regret:
We still consider only distributed elimination stage. There three communica- tion stages per phase in Protocol Line 8, 12, and 15.
Communication:
In line 8 of DEMAB protocol, the total communication is ((M) since A'az is boardcast from the
server, and each agent sends n; (i) to the server. We can observe that the communication cost at corresponding place is also ((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 ((M) for both protocols.
In summary, the communication cost of the protocol is the same that of Protocol which is O (M ())(MK)).
30

---

Published as a conference paper at ICLR 2020
1.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 a P2P network has regret O (dyMTllog + M log T) with expected communication cost O ((Md + d'log log d) Tog When > M3 log M, the regret of DELB is a near-optimal regret (ddMMMWa log') T).
Proof. The proof is very similar the proof of theorem Note that in the P2P version of DELB, there are (loog I') communication stages in total, which incurs ((M² log T") additional regret. The communication cost of the new protocol is the same Protocol 2 for the same reason mentioned in the proof of theorem
31


Reviews:
[{"review_id": "S1lV0dNpYS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper considers the problem of distributed multi-arm bandit, where M players are playing in the same stochastic environment. The goal of the paper is to have small over-all regret for all the players without a significant amount of communication between the players. \n\n\n\nThe main contribution of this paper is obtaining regret ~root(M KT) with ~M bits of communication in MAB, and regret ~d*root(MT) with ~Md bits of communication in linear bandit setting. \n\nThe main intuition of the algorithms in this paper is to do \"best arm identification\" with epoching: At every epoch t, the central server sends the set of possible best arms to each player and each player pulls it for 2^t /M times, followed by a communication round. Thus, the cumulative regret is comparable to having one player doing this epoch strategy for MT iterations, where the regret follows.\n\nThe problem considered in this paper is interesting and the result is new, the technique looks simple on paper but it requires a masterful combination of known tricks in (linear) MAB to obtain the best bound.  \n\n\nIt seems that in the MAB setting, the lower bound could be further strengthened with a log(K) factor, since removing this factor would ultimately require \"dynamic epoching\" which is not possible with limited communication. This would mostly complete the picture in the distributed MAB regime.\n\n\nMissing citation:\nThe authors are missing citations relevant to distributed MAB with collisions, see for example \n\"Non-Stochastic Multi-Player Multi-Armed Bandits: Optimal Rate With Collision Information, Sublinear Without\"\n\n\nAfter Rebuttal: I have read the authors' responses and acknowledge the sensibility of the statement.\n\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJlMtWL79H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\nThis paper considers the problem of obtaining an optimal regret algorithm in a distributed setting without incurring a large communication cost. In the standard and linear MAB settings, the authors propose algorithms and show that they achieve optimal regret up to logarithmic factors with communication costs that are almost independent of the horizon T. In addition the authors establish interesting lower bounds on the communication cost to obtain sublunar regret.\n\nOverall I found the paper very well motivated and clearly written. I did not go through the proofs in the appendix carefully, but I did check a few sections and found them to be correct. I did have a few concerns. \n\nI found the discussion around load balancing very confusing. Perhaps the authors could provide a picture to explain the issue? In addition, there is a lack of experiments- it is always nice to see comparisons to baseline even though the theory implies you would do better. Finally, the algorithm doesn’t seem extremely practical from an applied point of view - for a linear amount of time all the bandits are pulling the same arms and there is no communication at all. I understand this repeated work doesn’t affect the regret - but it is an artifact of using elimination. In general optimism based approaches (such as UCB) tend to work significantly better than elimination-style methods. I’d be curious to hear the authors comment on whether they think a UCB style algorithm is possible in this setting.\n\nOverall I recommend the paper for acceptance. \n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJeHVjyb5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \nThe authors establish regret guarantees as well as communication guarantees. The interesting result is that with constant communication the regret scales as if full communication was available.  \n\nThe results are interesting and I do not have any objections with the paper, except that ICLR might not be the right avenue for such work given that it lacks any ideas regarding representation learning.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackles the problem of regret minimization in a multi-agent bandit problem, where distributed learning bandit algorithms collaborate in order to minimize their total regret. More specifically, the work focuses on efficient communication protocols and the regret corresponds to the communication cost. The goal is therefore to design protocols with little communication cost. The authors first establish lower bounds on the communication cost, and then introduce an algorithm with provable near-optimal regret.

The only concern with the paper is that ICLR may not be the appropriate venue given that this work lacks representation learning contributions. However, all reviewers being otherwise positive about the quality and contributions of this work, I would recommend acceptance.
Decision: Accept (Poster)