Collaborative Top Distribution Identifications with Limited Interaction


Nikolai Karpov February 10, 2023.


We consider the following problem: given a set of n distributions, find the top-m ones with the largest means. This problem is also called top-m arm identifications in the literature of reinforcement learning, and has numerous applications. We study the problem in the collaborative learning model where we have multiple agents who can draw samples from n distributions in parallel. In this talk, we discuss tradeoffs between the running time of learning process and the number of rounds of interaction between agents.

Based on joint work with Qin Zhang and Yuan Zhou

Enjoy Reading This Article?

Here are some more articles you might like to read next:

  • Redundancy and Resilience in Distributed Optimization
  • Reconstructing Graphs from Random Subgraphs.
  • Derandomization from Time-Space Tradeoffs
  • Are quantum speedups for learning expressive classes possible?
  • Approximating CSPs in the streaming setting