Distributed Exploration in Multi-Armed Bandits
We study exploration in Multi-Armed Bandits in a setting where k players collaborate in order to identify an ε-optimal arm. Our motivation comes from recent employment of bandit algorithms in computationally intensive, large-scale applications. Our results demonstrate a non-trivial tradeoff between the number of arm pulls required by each of the players, and the amount of communication between them. In particular, our main result shows that by allowing the k players to communicate only once, they are able to learn √ k times faster than a single player. That is, distributing learning to k players gives rise to a factor √ k parallel speedup. We complement this result with a lower bound showing this is in general the best possible. On the other extreme, we present an algorithm that achieves the ideal factor k speed-up in learning performance, with communication only logarithmic in 1/ε.
The paper considers the possibility of parallelizing 
      the best arm identification problem. In specific, they ask how and what 
      speed-up can by achieved by running k instances of an algorithm in 
      parallel if they are allowed to share some information with each other. 
      The information sharing is done by each of the instances broadcasting some 
      information for the rest of the algorithms (typically at the end of the 
      run), but with the restriction that the number of broadcasted bits is 
      limited (typically of size \tilde{O}(n) for each instance). The 
      authors compare their algorithms to the full-communication method, the 
      no-communication method, and the method that takes the majority vote (MV) 
      of the individuals recommendations. The first one generates too much 
      network data, the second one obviously achieves no speed-up, and, as they 
      claim, the MV method achieves no speed-up either. In contrast, the 
      algorithm they propose achieves a speed-up of \sqrt{k}. They also show 
      that this is optimal if only one round of communication is allowed. 
      Finally, they show that if more communication rounds are allowed, 
      then there is a trade-off between the possible speed-up (up to k) and the 
      amount of information exchanged. EVALUATIION The 
      writing style is clear (mostly---but more about that below), the proposed 
      solutions are simple but clever, and the problem is both non-trivial and 
      reasonable (their motivating example is the distributed computation model 
      of MapReduce). However, there are two issues which should be 
      clarified. First of all, please define precisely what you mean by 
      ``speed-up'', and state your goals formally! It is quite natural to think 
      that if some algorithm A achieves confidence 1-\delta in time T, whereas a 
      distributed version achieves confidence 1-\delta' during the same time for 
      some \delta' much less than \delta, then this is a kind of speed-up. 
      (Indeed, for a stand-alone version of A to achieve the same 1-\delta' 
      confidence could take much longer than T.) And, in this sense, MV would 
      clearly achieve a speed-up: if time T is enough for A to output the best 
      arm with probability 2/3, then increasing k to infinity, and simply taking 
      the majority vote of the k instances of A (each run for time T) would 
      return the best arm with a probability getting arbitrarily close to 1. 
      Also, the performance of the MV method should be treated with more 
      care. In order to achieve that (in expectation) at least half of the 
      players return the best arm, the individual algorithms indeed have to 
      output the best arm with probability at least 1/2. However, for the MV 
      method to work this is not at all required. In fact, it is enough to have 
      that the individual algorithms output the best arm with higher probability 
      as any other suboptimal arm. Finally, two less significant 
      questions: 1. In the second line of the proof of Lemma 3.3 why do you 
      have the multiplicator 6 in front of H/\sqrt{k}? 2. In the second line 
      of the proof of Lemma 3.4 shouldn't 12n be devided by \Delta^\star in the 
      logarithm?