Title: DISTRIBUTED BANDIT LEARNING: NEAR-OPTIMAL REGRET WITH EFFICIENT COMMUNICATION

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(M K)) 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 ((M d + d log log d) log T ), which has only logarithmic dependence on T .

1. 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, 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 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 M T 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 .

1.1. PROBLEM SETTING:

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 P k . P k 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 a t,i , and receives reward r t,i independently sampled from P at,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) -µ(a t,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 ∈ R d : x 2 ≤ 1 . Agent i chooses action x t,i ∈ D and observes reward y t,i . We assume that the mean of the reward is decided by an unknown parameter θ * ∈ R d : y t,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 x T θ * -x T t,i θ * .

Here, we assume that the action set is fixed. A more general setting considers a time-varying action set D t . 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 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(

√ M KT ) and Õ(d √ M T )), but comes with high communication cost (O(M 2 T ) and O(M 2 dT )).

Distributed MAB For distributed multi-armed bandits, we propose DEMAB (Distributed Elimination for MAB) protocol, which achieves near-optimal regret (O M KT log(M K) ) 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 √ 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 √ M T log T ) with communication cost O ((M d + 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 M 1.5 d 3 communication cost.

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; 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

√ M T log T total regret using O(M d 2 T ) 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.

3. MAIN RESULTS FOR MULTI-ARMED BANDITS:

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.

3.1. ELIMINATION ALGORITHM FOR SINGLE-AGENT MAB:

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 A l . Initially, A 1 = [K] (all arms). In phase l, each arm in A l is pulled for Θ(4 l log T ) times; arms with average reward 2 -l lower than the maximum are then eliminated from A l .

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

l k = log 2 ∆ -1 k phases, in which it is pulled for at most O ∆ -2 k log T times. It follows that regret is O k:∆ k >0 ∆ -1 k 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 A l is pulled for Θ(4 l log(4 -l T )) instead of Θ(4 l log(T )) times. By doing this, the regret bound can be improved from √ KT log T to √ KT 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. In the first stage, each agent directly runs the singleagent modified elimination algorithm for D = T /M K time steps. The remaining arms of agent i are denoted as A (i) . In D time steps, an agent completes at least l 0 = log 4

D 1000K log(M K)

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 l 0 is chosen so that the total regret within the first stage is Õ √ M T .

Protocol 1: Distributed Elimination for Multi-Armed Bandits (DEMAB)

D = T /M K , l 0 = log 4 D 1000K log(M K) , m l = 4 l+3 log(M KT • 4 -l ) / * Stage 1: Separate Burn-in * / for Agent i = 1, • • • , M do

Agent i runs single-agent elimination for D time steps, denote remaining arms as A (i) / * Switching: Random Allocation * / Generate public random numbers r 1 ,...,r K uniformly distributed in [M ]

B (i) l0+1 = a ∈ A (i) |r a = i , B l0+1 = i∈[M ] B (i) l0+1 / * Stage 2: Distributed Elimination * / for l = l 0 + 1, • • • do if N l = |B l | > M then Agent i sends n (i) l = B (i) l to server; server broadcasts n max = max i n (i) l if (n (1) l , ..., n (M ) l ) is not balanced then Reallocate // Adjust B (i) l

so that their sizes are balanced

Agent i pulls each a ∈ B (i)

l for m l times, denotes average reward as ûl (a), and then pulls arms in round-robin for (n max -n 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 (r 1 , • • • , r K ), K uniformly random numbers in [M ], from a public random number generator. Agent i then computes i) |r a = i . By doing so, agent i keeps each arm in A (i) with probability 1/M , and the resulting sets i) , so that the best arm remains in B l0+1 with high probability3 .

B (i) = a ∈ A (

B (1) , • • • , B (M ) are disjoint. Meanwhile, every arm in i∈[M ] A (i) is kept in B l0+1 = i∈[M ] B (

In the second stage, agents start to simulate a single-agent elimination algorithm starting from phase l 0 + 1. Initially, the arm set is B l0+1 . In phase l, each arm in B l will be pulled for at least m l = 4 l+3 log(M KT • 4 l ) times. Denote the average reward of arm a in phase l by ûl (a). If ûl (a) < max a ∈B l ûl (a ) -2 -l , it will be eliminated; the arm set after the elimination is B l+1 .

This elimination in the second stage is performed over M agents in two ways: In distributed mode or in centralized mode. Let N l = |B l | be the number of remaining arms at the start of phase l. If N l is larger than M , the elimination is performed in distributed mode. That is, agent i keeps a set of arms B l for m l times in phase l. Each agent only needs to send the highest average reward to the server, who then computes and broadcasts max a∈B l ûl (a). Agent i then eliminates low-rewarding arms from B (i) l on its local copy. When N l ≤ M , the elimination is performed in centralized mode. That is, B l will be kept and updated by the server 4 . In phase l, the server assigns an arm in B l to M/N l agents, and asks each of them to pull it m l N l /M times5 . The server waits for the average rewards to be reported, and then performs elimination on B l .

One critical issue here is load balancing, especially in distributed mode. Suppose that n

(i) l = |B (i) l |, n max = max i∈[M ] n (i)

l . Then the length of phase l is determined by n max m l . Agent i would need to keep pulling arms for (n max -n (i) l )m l times until the start of the next communication round. This will cause an arm to be pulled for much more than m l times in phase l, and can hurt the performance. Therefore, it is vital that at the start of phase l, n l := n (1) l , ..., n (M ) l is balanced6 .

The subroutine Reallocate is designed to ensure this by reallocating arms when n l 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{N l , N l -N l }) 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.

3.3. REGRET AND COMMUNICATION EFFICIENCY OF DEMAB:

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 M T K log(M K) regret, O M log M K δ commu- nication cost with probability 1 -δ, and O (M log(M K)) 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 l 0 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(M K)). Total regret for all agents in this stage is

O(M √ KD log D) = O( M T log(M K)).

After the first stage, each agent must have completed at least l 0 phases. Hence, with high probability, before the second stage,

B l0+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 ∈ B l , it will be pulled at most 2m l 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 Õ ∆ -2 k times. It follows that regret in the second stage is O M KT log(M K) , and that total

regret is O M KT log (M K) .

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 is O (M ).

The communication cost of calling:

Reallocate in phase l is at most O (min {N l , N l -N l }),

where l is the last phase where Reallocate is called. Therefore, total cost for calling Reallocate in one execution is at most O (N l1 ), where l 1 is the first phase in which Reallocate is called. From the definition of m l and l 0 , we can see that there are at most L = O (log(M K)) phases in the second stage. Therefore in the worst case, communication cost is

O (M L + K) since N l1 ≤ K.

However, in expectation, N l1 is much smaller than K. That is to say, Reallocate is called for the first time when N l 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, n l would be balanced with high probability. In fact, with probability

1 -δ, N l1 = O M log M K δ . Setting δ = 1/K, we can show that the expected communication complexity is O(M log M K).

3.4. LOWER BOUND:

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 Õ √ M KT , 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.

4. MAIN RESULTS FOR LINEAR BANDITS:

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 .

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 l, the algorithm maintains an active action set A l . It computes a distribution π l (•) over A l and pulls arms according to π l (•). A total of n l 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 V l (π) = x∈A l π(x)xx and g l (π) = max x∈A l x V l (π) -1 x. 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)g l (π)4 l log 1 δ times, the estimation error for any arm x ∈ A l is at most 2 -l with high probability. Thus, to minimize m l , one should find a distribution π(•) that minimizes g l (π), a task known as G-optimal design (Pukelsheim, 2006) . It is known that the optimal value for g l (π) is d, and 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 ) π * (x)g l (π * )4 l log( 1 δ ) ≤ O(4 l d log( 1 δ ) + d 2 ) pulls are needed in phase l.

4.2. THE DELB PROTOCOL:

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 A l , 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 A l 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 A l .

For notational convenience, we define

V (π) = x∈D π(x)xx , g(π) = max x∈D x V (π) -1 x.

Protocol 2: Distributed Elimination for Linear Bandits (DELB) Receive rewards for each arm x ∈ A l reported by agents

A 1 = D, C 1 = 600 for l = 1,

For each arm in the support of π l (•), calculate the average reward µ(x)

Compute 10 X = x∈Supp(π l ) m l (x)µ(x)x, V l = x∈Supp(π l ) m l (x)xx , θ = V -1 l X

Send θ to all agents / * All agents and server: Eliminate low-rewarding arms * /

Eliminate low rewarding arms:

A l+1 = x ∈ A l : max b∈A l θ, b -x ≤ 2 -l+1

4.3. REGRET AND COMMUNICATION EFFICIENCY OF DELB:

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 √ T M log T with communication cost O ((M d + d log log d) log T ).

Proof sketch: In round l, the number of pulls is at most 48d log log d + C 1 4 l d 2 log M T . 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/M T for any arm x pulled in phase l. Suppose there are at most L phases, we can prove that E(REG(T ))

≤ L l=1 O(d 4 l d 2 log 2 T M ) ≤ O(d √ T M log T M ).

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 of these parts is O(M + d log log d). In the third part, the cost of sending θ is M d. Since l is at most O(log T ), the total communication is O ((M d + d log log d) log T ) .

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 t may depend on t. That is, players can only choose actions from D t at time t, while regret is defined against the optimal action in D t . 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 C t,i ⊆ R d for the parameter θ * . In each step, he chooses an optimistic estimate θ t,i = argmax θ∈Ct-1,i (max x∈D x, θ ) and then chooses action X t,i = argmax x∈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 W t,i and U t,i to denote the sum calculated using available samples for agent i at time step t. We construct the confidence set C t,i using W t,i and U t,i :

EQUATION

where

V t,i = λI + W t,i , θt,i = (λI + W t,i ) -1 U t,i , x V := x T V 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)

for t = 1, • • • , T do for Agent i = 1, • • • , M do Compute W t,i = τ x τ x T

τ and V t,i = I + τ x τ y τ using all available samples Construct the confidence ellipsoid C t,i using W t,i and θt,i = V -1 t,i U t,i .

(x t,i , θt,i ) = arg max (x,θ)∈Dt×Ct,i x, θ

Play x t,i and observe reward y t,i .

Update W t,i and V t,i if log (det V t,i /det V last ) • (t -t last ) > T log(M T )/(dM ) then

Start a synchronization round

t last = t, V last = 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. Although the regret bound is still near-optimal, the communication cost has worse dependencies on M and d compared to that of DELB.

5. CONCLUSIONS AND FUTURE WORK:

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 M KT log(M K) regret with M log(M K) communication cost. The communication cost of DEMAB protocol matches the lower bound we proposed except for a logarithmic factor. 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-M d 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.

A ORGANIZATION:

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.

B DETAILED DESCRIPTION OF DEMAB:

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)

D = T /M K , C 2 = 1000, l 0 = log 4 D C2K log(M K) , m l = 4 l+3 log(M KT • 4 -l ) / * Stage 1: Separate Burn-in * / for agent i = 1, ..., M do A (i) =Eliminate([K],D) / * Switching: Random Allocation * / Generate public random numbers r 1 , ..., r K in [M ] B (i) l0+1 = {a ∈ A (i) |r a = i} / * Stage 2: Distributed Elimination * / for l = l 0 + 1, ... do if Centralize has not been called then / * distributed mode * / Agents send n (i) l = B (i) l to server, N l = i n (i) l , N max = max i n (i) l if N l ≤ M then

Centralize, go to line 22

if n l is not balanced then

Reallocate:

Server sends N max to all agents

for agent i = 1, ..., M do

Pull each a ∈ B Return A l 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 

EQUATION

|A temp | = i∈S + (n (i) l -n) - i∈S - (n -n (i) l ) = i∈[M ] n (i) l -M i∈[M ] n (i) l /M < M. 2. Let n (i) l = B (i) l . If max i n (i) l ≤ 2 min i n (i)

l , the reallocation procedure will do nothing, and n

(1) l , ..., n (M ) l is by definition balanced. If max i n (i) l > 2 min i 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 K 4 l+3 log(4 -l M KT ) . After l phases, the number of timesteps is at most

K l p=1 4 p+3 log(4 -p M KT ) ≤ 4 l+4 3 log(4 -l M KT ) + 1 3 .

Setting C 2 = 1000 and l 0 = log 4 D C2K log M K , one can verify that

4 l0+4 3 log(4 -l0 M KT ) + 1 3 ≤ 256D 3C 2 log(M K) log(C 2 M 2 K 3 log(M K) + 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 l 0 .

On the other hand, in l phases, the number of timesteps is at least

l p=1 4 p+3 log(4 -p M KT ) ≥ 4 l+3 log(4 -l M KT ).

By setting C 2 = 512 and l D = log 4

D C 2 log M K , one can show that 4 l D +3 log(4 -l D M KT ) > D.

Therefore, the number of of completed phases in stage 1 is at most l D . 4. Suppose that stage 2 has L = 4 + 5 log(M K) phases, then the total number of phases during stage 1 and stage 2 is at least L + l 0 . In phase L + l 0 , at least 4 l0+L+3 log 4 -(l0+L) M KT pulls are made. With some elementary calculation, one can show that the number of arms pulled in phase

L + l 0 is M T • M K log(M K) log log(M K) M

, which is even greater than the total number of timesteps M T . 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 • 4 l /(M KT ).

Proof. For any agent i, any phase l ≤ l D , denote the empirical mean for arm a in phase l by û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 m l • 4 -l-1 ≤ 2 • 4 l (M K) 2 T .

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 N M (k, t) = t j=1 M i=1 I [a i,j = k]

is the number of times arm k is pulled for all agents before time step t.

If l i = log 2 ∆ -1 i + 1 ≤ l, then N M (i, D) ≤ C 5 M log(M KT ∆ 2 i )/∆ 2 i ;

In particular, let l D be the maximum number of phases for all agents at stage 1.

Λ 1 ∧ • • • ∧ Λ l D also implies the following: 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 l i 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 m l ≤ 4 li+4 3 log(4 -li M KT ) + 1 3 ≤ C 5 log(M KT ∆ 2 i ) ∆ 2 i

for some absolute constant C 5 . 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 ∧ • • • ∧ Λ l D implies 1 ∈ A (i) for any i ∈ [M ].

So at line 5 in protocol 1, arm 1 will be assign to agent r a . 5. Let A (i) denote the remaining arms at the end of stage 1 for agent i. From statement 2 we know that

Λ 1 ∧ • • • ∧ Λ l D 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

B l0+1 = i∈[M ] B (i) l0+1 is a subset of i∈[M ] A (i) and l i ≥ l 0 , we conclude that ∀a ∈ B l0+1 , µ(a) ≥ µ(1) -2 -l (i) +1 ≥ µ(1) -2 -l0+1 .

Lemma C.3. For l > l 0 , denote the following event by Ω l : at stage 2, for any a ∈ B l ,

|û l (a) -µ(a)| ≤ 2 -l-1 . Then Pr [Ω l ] ≥ 1 -2 • 4 l /(M 2 KT ).

Proof. Recall that for any l > l 0 , ûl (a) is the average of m l independent samples of the reward from arm a. Therefore, for fixed l and a, by Hoeffding's inequality,

Pr |û l (a) -µ(a)| > 2 -l-1 ≤ 2 exp - 1 2 m l • 4 -l-1 ≤ 2 • 4 l (M K) 2 T .

A union bound for all a ∈ B l proves this lemma.

Lemma C.4. Recall that

∆ i = µ(1) -µ(i). If ∆ i > 0, let l i = log 2 ∆ -1 i + 1. Let Λ denote Λ 1 ∧ • • • ∧ Λ l D . Then at stage 2, Λ ∧ Ω l0 ∧ • • • ∧ Ω li implies the following: N M (i, T ) -N M (i, D) ≤ C 4 log(M KT ∆ 2 i ) ∆ 2 i + η(a),

where C 4 is a universal constant, and

a∈[K] η(a) ≤ M log M . Proof. Suppose that | Bl | > M . By Fact 1, at phase l ≥ l 0 + 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 Bl is pulled is at most 2m l .

If | Bl | ≤ M , an arm in Bl is also pulled at most 2m l times, unless | Bl |•m l < M . In that case, a phase only lasts for 1 timestep. This is possible only when m l < M , which requires l < log 4 M < log M . We denote the number of times a is pulled in such phases by η(a).

On the other hand, let l i = log 2 1 ∆i + 1. If l i ≤ l 0 , Λ 2 implies that i / ∈ Bl0+1 . In that case, the number of times arm i is pulled after timestep D is 0.

Assume Ω l0+1 ∧ • • • ∧ Ω li holds and i ∈ Bli . Then ûli ≥ µ(1) -2 -li-1 ≥ µ(i) + ∆ i -2 -li-1 ≥ ûli (i) + 2 -li . Therefore, Ω l0+1 ∧ • • • ∧ Ω li implies that i / ∈ Bli+1 .

In this case, number of times arm i is pulled is

N M (i, T ) -N M (i, D) ≤ li+1 l=l0+1 2m l + η(a) ≤ 8 3 4 li+4 log(M KT • 4 -li-1 ) + 1 3 + L + η(a) ≤ 2 15 log(M KT ∆ 2 i ) 3∆ 2 i + 4 + 5 log(M K) + η(a) ≤ 2 15 + 27 log(M KT ∆ 2 i ) 3∆ 2 i + η(a). It is not hard to see that a∈[K] η(a) ≤ M log M .

Lemma C.5. Let l ≥ l 0 + 1, and n l = Bl . With probability 1 -2LKδ, either n l < 21M log 1 δ or no reallocation is performed before the start of the l-th phase at stage 2.

Proof. Let Y i,l = I i ∈ Bl , X i,j = I [r i = j], i ∈ [K], j ∈ [M ].

Observe that X i,j and Y i ,l are independent. This is because the elimination process between Bl and Bl+1 uses exactly m l 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 {Y i,l , ∀i, l}. Since

B (j) l = K i=1 Y i,l X i,j , Bl = n l = K i=1 Y i,l , by Chernoff's inequality, Pr K i=1 Y i,l X i,j > 4 3M K i=1 Y i,l Y ≤ exp - K i=1 Y i,l 21M , Pr K i=1 Y i,l X i,j < 2 3M K i=1 Y i,l Y ≤ exp - K i=1 Y i,l 18M .

Consequently,

Pr   4 Bl 3M > B (j) l > 2 Bl 3M n l > 21M log 1 δ   ≥1 -E Y exp - n l 21M + exp - n l 18M n l > 21M log 1 δ ≥1 -2δ. Note that 2 3M Bl < B (j) l < 4 3M Bl for all j ∈ [K] implies that B (1) l , • • • , B (M ) l is balanced. Therefore, if n l > 21M log 1 δ ,

with probability 1 -2(l -l 0 )Kδ, no reallocation will be performed before the l-th phase at stage 2. Proof. Regret:

Let l i = log 2 ∆ -1 i + 1. By Lemma C.2, when Λ 1 ∧ • • • ∧ Λ li holds, N M (i, D) ≤ C 5 M log(M KT ∆ 2 i ) ∆ 2 i .

Therefore, the probability that this does not hold is at most

li p=1 Pr Λ p ≤ li p=1 2 • 4 p M KT ≤ 128 3M KT ∆ 2 i .

Thus for any arm i,

E [N M (i, D)] ≤ C 5 M log(M KT ∆ 2 i ) ∆ 2 i + 128 3M KT ∆ 2 i • M D ≤ C 5 M log(M KT ∆ 2 i ) ∆ 2 i + 64 3∆ 2 i . Similarly, if l i ≥ l 0 , when Λ ∧ Ω l0+1 ∧ • • • ∧ Ω li holds, N M (i, T ) -N M (i, D) ≤ C 4 log(M KT ∆ 2 i ) ∆ 2 i + η(i).

The probability that this does not hold is at most

Pr Λ + li+1 p=l0 Pr Ω p ≤ l D p=1 2 • 4 p M KT + li p=l0 2 • 4 p M 2 KT ≤ 256 C2 C 2 + 128 3 M T ∆ 2 i ≤ 600 M T ∆ 2 i . Therefore E [N M (i, T ) -N M (i, D)] ≤ C 4 log(M KT ∆ 2 i ) ∆ 2 i + η(i) + 600 M T ∆ 2 i • M T = C 4 log(M KT ∆ 2 i ) ∆ 2 i + 600 ∆ 2 i + η(i).

It follows that

K a=1 ∆ a E [N M (a, D)] = a:∆a> 1 ∆ a E [N M (a, D)] + a:∆a≤ 1 ∆ a E[N M (a, D)] ≤ K C 5 M log(M KT 2 1 ) + 256/3 1 + 1 • M D ≤ C 6 M T log(M K),

where in the last line we choose 1 = K log(K)

T:

, and C 6 is some absolute constant. Similarly,

K a=1 ∆ a E [N M (a, T ) -N M (a, D)] ≤ a:∆a> 2 ∆ a E [N M (a, T ) -N M (a, D)] + 2 • M T ≤ M log M + K C 4 log(M KT 2 2 ) + C 9 2 + 2 • M T ≤ M log M + (3C 4 + 601) M KT log(K),

where in the last line we chose

1 = K log(K) M T

. By our assumption, M log M ≤ M T K log(K). Therefore by the definition of total regret,

E [REG(T )] = K a=1 ∆ a E [N M (a, D)] + K a=1 ∆ a (E [N M (a, T )] -E [N M (a, D)]) ≤ C 6 M T log(M K) + (3C 4 + 601 + 1) M KT log(K) ≤ √ 2 • max{C 6 , 3C 4 + 602} M T (K log(K) + log(M K)).

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 is O (min{n l , n l -n l }), where l is the last phase where reallocation is performed. Summing this over all phases (at most L = O(log(M K))) in stage 2, we conclude that total communication cost for reallocation is O(M L + K).

Define l 1 to be the first phase such that reallocation is performed. Then, our argument above shows that communication cost is O(M L + n l1 ). If n l1 > 21M log 1 δ , the event in lemma C.5 will be violated for some l. The probability for that is at most 2L 2 Kδ. By resetting δ, we can show that with probability 1 -δ, n l1 < 21M log 2L 2 K δ . Therefore, with probability 1 -δ, total communication cost is

O M L + 21M log 2L 2 K δ = O M log M K δ .

In particular, by choosing δ = 1/K, we can show that expected communication cost is O (M log(M K)) .

Theorem 5. When D = l 0 = 0 in DEMAB, the protocol incurs near-optimal instance-dependent regret O( k:

∆ k >0 ∆ -1 k log T + M log M ). 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 [N M (i, T )] ≤ C 4 log(M KT ∆ 2 i ) ∆ 2 i + η(i) + 600 ∆ 2 i ,

where i∈[K] η(i) ≤ M log(M ). It follows that total expected regret is

E i:∆i>0 N M (i, T )∆ i ≤ i:∆i>0 ∆ i η(i) + i:∆i>0 C 4 log(M KT ∆ 2 i ) + 600 ∆ i = O M log(M ) + k:∆ k >0 ∆ -1 k 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 of O(K) additional communication among all phases to perform reallocation.

Let l * be the last complete phase such that n l * +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(M L ).

From the beginning of phase l * + 1, the total communication in the following phases is at most

O(M L + 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 + (M L + 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 m l samples is 1 4 l+2 log(M KT 4 -l ) -subgaussian. In fact, the average of m l samples is 1 4 l+3 log(M KT 4 -l ) -subgaussian. Therefore, we can use randomized rounding for the average reward with precision = 1 4T M . Then, the rounding error for each real number has zero mean, and is 1 M 4 l+3 log(M KT 4 -l ) -subgaussian. When computing the average of m l samples at phase l, at most M rounding error terms will contribute to it, whose sum is 1 4 l+3 log(M KT 4 -l ) -subgaussian. Therefore, the concentration inequality in lemma C.3 and consequently our main theorem still holds. Apparently log 2 1 = O (log(M T )) = O(log T ). Therefore, expected number of communicated bits is O (M log(M K) log T ).

D REMOVING PUBLIC RANDOMNESS:

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.

Therefore, we only need to guarantee that BM log(M K) 1+K/(M log(M K)) > C K log M KT , where C is a universal constant. This can be met by setting B = 2C K 2 log(M KT ) . In this case, we can guarantee that there exists a set of bit strings {s 1 , ..., s B }, such that for any bandit instance X, when choosing s randomly from this set, the expectation of f (X, s) is O(M log(M K)).

The additional communication overhead for generating the random string (in bits) is

O (M log B) = O (M log K + M log log(M KT )) .

Therefore, under our usual assumption that T > max{M, K}, the number of total communicated bits is bounded by O (M log K + 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(M K)).

E PROOF FOR THEOREM 2:

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) For K-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 X i (i ∈ [M ]) to be the number of integers or real numbers that agent i sends or receives throughout a run. X i is a random variable. Since expected communication cost is less than M/c,

M i=1 EX i ≤ M/c.

Denote S as the set of M/2 agents with smaller EX i . The expected communication cost of any i ∈ S is at most 2/c. For any i ∈ S, P(X i ≥ 1) ≤ EX i ≤ 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 REG j (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 .

F OMITTED DETAILS OF DELB:

Assignment Strategy: At line 4, we assign pulls to agents in the following way. Let p l =

x m l (x)/M denote the average pulls each agent needs to perform. Our assignment starts from the arm with the largest m l (x) and agent 1. For arm x k and agent i, if agent i has been assigned with p l pulls, we turn to agent i + 1. If we have finished designating m l (x k ) pulls for arm x k , we continue designating arm x k+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 A l 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 ).

G PROOF OF THEOREM 3:

First, we consider some properties of the elimination based protocol for linear bandits. Fact 2. Let T l denote the total number of pulls in the l-th phase, then

C 1 4 l d 2 log M T ≤ T l ≤ ξ + C 1 4 l d 2 log M T,

where ξ = 48d log log d.

Proof. For an arm x in the core set Supp(π l ), the DELB protocol pulls it C 1 4 l d 2 π l (x) log M T times. Thus the total number of pulls in phase l satisfies

a∈Supp(π l ) m l (a) ≥ a∈Supp(π l ) C 1 4 l d 2 π l (x) ≥ C 1 4 l d 2 log(M T ),

and

a∈Supp(π l ) m l (a) ≤ a∈Supp(π l ) C 1 4 l d 2 π l (x) + 1 ≤ 48d log log d + C 1 4 l d 2 log M T. Lemma G.1. In phase l, with probability 1 -1/T M , 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 , ..., xQ }. Here Q satisfies Q ≤ 3 d 2 d(l+2) .

Assume that θ is calculated from linear regression on x 1 , ... , x t . For fixed x ∈ D, it is known that θ -θ * , x is subgaussian with variance proxy

EQUATION

Therefore with probability 1 -2δ,

θ -θ * , x ≤ 2 x 2 V -1 l log 1 δ . Apparently C 1 4 L d 2 log T M ≤ T M . Therefore REG(T ) ≤ C 2 3 4 L d 4 log 2 T M ≤ C 7 d T M log T M .

Under our usual assumption that T > M , this can be simplified to O(d √ T M log T ). Here C 3 and C 7 are some universal constants.

Communication Cost: Let p l = x m l (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 + m l (x)/p l agents. Therefore, total communication for scheduling is at most 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 = 1 M 2 T ; 2. after computing θ = V -1 l X at line 7, let θ be the entry-wise rounded vector of θ with 2 = 1 M T d . 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 1 m l (x) -subgaussian, but is only required to be 2 m l (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 1 M T ≤ 1 m l (x) . Therefore, after the modifications, the computed µ(x) is 2 m l (x) -subgaussian; hence, (2) holds. It follows that with probability 1 -1/(T M ), 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 M T ≤ 2 -l-1 ,

we can prove that with probability 1 -1/(T M ), for all x ∈ X,

θ -θ * , x ≤ 2 -l-2 .

Therefore, after the modifications, the regret of the protocol is still O d √ T M log T . The amount of communicated bits is thus

O ((M d + d log log d) • log T • log(dT )) . Proof. Assuming θ * ∈ C t,i , r t,i = θ * , x * -θ * , x t,i ≤ θt,i , x t,i -θ * , x t,i = θt,i -θ * , x t,i = θt,i -θt,i , x t,i + θt,i -θ * , x t,i ≤ θt,i -θt,i Vt,i x t,i V -1 t,i + θt,i -θ * Vt,i x t,i V -1 t,i ≤ 2 2 log det( Vt,i ) 1/2 det(λI) -1/2 δ + λ 1/2 x t,i V -1 t,i = O d log T δ x t,i V -1 t,i

. Now we are ready to prove Theorem 4. Proof. Regret: Set δ = 1/(M 2 T ), the expected regret caused by the failure of Eq. ( 3) is at most M T • 1/(M T ) = 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 V last in epoch p as V p . Suppose that there are P epochs, then V P will be the matrix with all samples included.

Observe that det V 0 = det(λI) = λ d . det(V P ) ≤ tr(V P )

d d ≤ (λ + M T /d) d . Therefore log det(V P ) det(V 0 ) ≤ d log 1 + M T λd .

Let R := d log 1 + M T λd . It follows that for all but R epochs, we have

EQUATION

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 M T pulls are all made by one agent in a round-robin fashion (i.e. he takes x 1,1 , x 1,2 ,..., x 1,M , x 2,1 ,..., x T,M ). We use Ṽt,i = λI + {(p,q):(p<t)∨(p=t∧q<i)} x p,q x T p,q to denote the V t,i this imaginary agent calculates when he gets to x t,i . If x t,i is in one of those good epochs(say the j-th epoch), then we can see that

1 ≤ det Ṽt,i det Vt,i ≤ det V j det V j-1 ≤ 2. Therefore r t,i ≤ O d log T δ x T t,i V -1 t,i x t,i ≤ O d log T δ x T t,i Ṽ -1 t,i x t,i • det Ṽt,i det Vt,i ≤ O d log T δ 2x T t,i Ṽ -1 t,i x t,i .

We can then use the argument for the single agent regret bound and prove regret in these good epochs.

We 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 y t,i is observed, we replace it with a random integer in {±1} with expectation y t,i . Second, after line 8, after x t,i is played, we round each entry of x t,i with precision , and use the rounded vector in the calculation in line 9. In this case, each entry of W new,i and U new,i is a multiple of 2 . Therefore, transmitting them requires O(d 2 log -1 ) bits. The total communication complexity is then O M 1.5 d 3 log -1 bits.

We now discuss how to choose such that regret is not effected. Define On the other hand, let H be the (random) history of the DisLinUCB with rounding on action sets D t , while H is the (random) history of the DisLinUCB with rounding running on action sets D t .

Then at each time step, the mapping from past history to the next action is the same. Therefore KL(H, H) = O(M T d 2 ). It follows that

E REG (H) -E REG H ≤ O √ M 3 T 3 d .

When the action set is D t , no rounding is needed, so the regret analysis for the DisLinUCB protocol without rounding directly follows. Therefore, 

E

I 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 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 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.

:

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 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

Our algorithms can be modified to meet this restriction with almost no change in performance.

i∈[M ] A(i) may not be a subset of B l 0 +1 , which is not a 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 sets of agents are disjoint, the communication cost is O(M ).

The indivisible case is handled in Appendix B.

By saying a vector of numbers is balanced, we mean the maximum is at most twice the minimum.

When 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.

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.

V l is always invertible when A l spans R d . When A l doesn't span R d , we can always consider span(A l ) in phase l and reduce the number of dimensions.

Recall that T > K.

which has K log 2 M bits

For 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.

Figures and Tables:

l times before the next communication round Communication round: Agent i sends max a∈B (i) l ûl to server and waits to receive u * l = max a∈B l ûl from server Agent i eliminates bad arms: B in B l , the server asks M/N l agents to pull it m l N l /M times Server computes ûl (a), the average reward for m l pulls of arm a Server eliminates bad arms: B l+1 = a ∈ B l : ûl (a) + 2 -l ≥ max b∈B l ûl (b)

2, 3, ... do / * All agents and server: Solve a G-optimal design problem * / Find distribution π l (•) over A l such that: 1. its support has size at most ξ = 48d log log d; 2. g(π) ≤ 2d / * Server: Assign pulls and summarize results * / Assign m l (x) = C 1 4 l d 2 π l (x) ln M T pulls for each arm x ∈ Supp(π l ) and wait for results 9 .

The DisLinUCB protocol can achieve a regret of O d √ M T log 2 (T ) with O M 1.5 d 3 communication cost.

For distributed linear bandits, our DELB protocol and DisLinUCB protocol achieve near-optimal regret with O ((M d + d log log d) log T ) and O M 1.5 d 3 communication cost respectively.

for m l times, denote average as ûl (•) Pull other arms in round-robin for (N max -|B l |)m l times Send (arg max a ûl (a ), max a ûl (a )) to server Server receives (a * j,l , u * j,l ) from agent j, and sends u * l = max j u * j,l to every agent for agent i = 1, ..., M do Server assigns arms in B l to agents evenly and schedules m l pulls for each arm Agents pull arms as required by the server, and report the average for the pulled arm Server calculates ûl (a), average reward for m l pulls in this phase, for each arm a ∈ B l Elimination: B l+1 = a ∈ B l : ûl (a) + 2 -l ≥ max j∈B l û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 A 1 , time step D. for l = 1, ... do for a ∈ A l do Pull arm a for m l = 4 l+3 log(4 -l M KT ) times, denote average reward as μl (a) If time step D is reached, go to line 6 Elimination: A l+1 = a ∈ A l : μl (a) > max k∈A l μl (k) -2 -l

any player i, the number of completed phases in stage 1 is at least l 0 number of phases at stage 2 is less thanL = 4 + 5 log(M K) = O (log(M K)).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,

Now we are ready to prove Theorem 1. Theorem 1. The DEMAB protocol incurs O M T K log(M K)) regret, O M log M K δ communication cost with probability 1 -δ, and O (M log(M K)) communication cost in expectation.

m l (x)/p l + 1) ≤ 2ξ + M = O(M + d log log d). Similarly, total communication for reporting averages is the same. The cost for sending θ is M d. Hence, communication cost per phase is O(M d + d log log d). On the other hand, total number of phases is apparently O(log T M ). Hence total communication is O ((M d + d log log d) log T M ) Under the assumption that T > M , this can be simplified to O ((M d + d log log d) log T ).

DisLinUCB protocol achieves a regret of O d √ M T log 2 (T ) with O M 1.5 d 3 communication cost.

Vt 0 +n,i det V last < D. Therefore we can show that REG(n) ≤ O d log T /δ • M √ D.Since det(V P ) ≤ (λ + M T /d) d , we know that the number of such epochs are rare. (Less than R = O(d log M T )). Therefore the second part of the regret isREG bad ≤ O M d 1.5 log 1.5 M T • D 1/2 . If we choose D = T log M T dM , then REG(T ) = O d √ M T log 2 (M T ) . Since T > M , we have REG(T ) = O d √ M T log 2 (T ) .Communication: Let α = DT R 0.5 . Apparently there could be at most T /α such epochs that contains more than α time steps. If the j-th epoch contains less than α time steps, log With our choice of D, the right-hand-side is O M 0.5 d . Communication is only required at the end of each epoch, when each agent sends O(d 2 ) numbers to the server, and then downloads O(d 2 ) numbers. Therefore, in each epoch, communication cost is O(M d 2 ). Hence, total communication cost is O M 1.5 d 3 .

t,i , θ * .Here H is a shorthand for a history (x 1,1 , y 1,1 , • • • , x T,M , y T,M ). D refers to set of rounded actions. For every x ∈ D, there existsx ∈ D such that x -x ≤ √ d . Therefore REG (H) -REG (H) ≤ M T √ d .

REG H = O d √ M T log 2 T . By choosing = (M T ) -1 , we can guarantee E [REG (H)] = O d √ M T log 2 Tfor any action set. In this case, the total number of communicated bits is O M 1.5 d 3 log T .

from 1 time step to M time steps, so that agents can complete the communication in turn. Since there are at most O(log(M K)) communication stages in DEMAB and O(log T ) communication stages in DELB, the extension of communication stages incurs at most O(M 2 log(M K)) regret in DEMAB and O(M 2 log T ) regret in DELB for M agents. When the time horizon T is large (i.e. T > M 3 log M ), the additional term is dominated by O √ M KT log T and O d √ M T log T .

denote regret in all good epochs as REG good . Suppose B p means the set of (t, i) pairs that belong to epoch p, and P good means the set of good epochs, using lemma H.2, we have Now we focus on epochs that are not good. For each bad epoch, suppose at the start of the epoch we have V last . Suppose that the epoch starts from time step t 0 , 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

Table content: <table><tr><td/><td>REG good =</td><td/><td/><td/><td/><td>r t,i</td><td/><td/><td/><td/></tr><tr><td/><td/><td>t</td><td/><td>i</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="4">≤ M T</td><td/><td/><td/><td/><td/><td colspan="2">r 2 t,i</td></tr><tr><td/><td/><td/><td/><td/><td colspan="6">p∈P good (t,i)∈Bp</td></tr><tr><td/><td/><td/><td colspan="2"></td><td/><td/><td/><td/><td/><td/><td></td></tr><tr><td/><td colspan="2">≤ O</td><td colspan="5">  dM T log(</td><td>T δ</td><td>)</td><td colspan="2">p∈P good (t,i)∈Bp</td><td>min x t,i</td><td>2 Ṽ -1 t,i</td><td>, 1</td><td> </td></tr><tr><td/><td/><td/><td colspan="2"></td><td/><td/><td/><td/><td/><td/><td></td></tr><tr><td/><td colspan="2">≤ O</td><td colspan="5"> dM T log(</td><td>T δ</td><td>)</td><td colspan="2">p∈P good</td><td>log</td><td>det (V p ) det (V p-1 )</td><td></td></tr><tr><td/><td colspan="2">≤ O</td><td/><td colspan="3">dM T log(</td><td colspan="2">T δ</td><td colspan="2">) log</td><td>det (V P ) det (V 0 )</td></tr><tr><td/><td/><td/><td/><td>√</td><td/><td/><td/><td/><td/><td/></tr><tr><td/><td colspan="4">≤ O d</td><td colspan="6">M T log(M T ) .</td></tr><tr><td>REG ≤ 2</td><td>d log T /δ</td><td colspan="2">M i=1</td><td colspan="2">n t=t0</td><td colspan="5">min x t,i V -1 t,i</td><td>, 1 ≤ O</td><td>d log T /δ •</td><td>M i=1</td><td>n log</td><td>det V t0+n,i det V last</td><td>.</td></tr></table>

Peer review (iclr2020):
This 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. Overall 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. I 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. Overall I recommend the paper for acceptance.