TY - GEN
T1 - Collaborative top distribution identifications with limited interaction (extended abstract)
AU - Karpov, Nikolai
AU - Zhang, Qin
AU - Zhou, Yuan
N1 - Publisher Copyright:
© 2020 IEEE.
PY - 2020/11
Y1 - 2020/11
N2 - We consider the following problem in this paper: 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 the n distributions in parallel. Our goal is to characterize the tradeoffs between the running time of learning process and the number of rounds of interaction between agents, which is very expensive in various scenarios. We give optimal time-round tradeoffs, as well as demonstrate complexity separations between top-1 arm identification and top-m arm identifications for general m and between fixed-time and fixed-confidence variants. As a byproduct, we also give an algorithm for selecting the distribution with the m-th largest mean in the collaborative learning model.
AB - We consider the following problem in this paper: 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 the n distributions in parallel. Our goal is to characterize the tradeoffs between the running time of learning process and the number of rounds of interaction between agents, which is very expensive in various scenarios. We give optimal time-round tradeoffs, as well as demonstrate complexity separations between top-1 arm identification and top-m arm identifications for general m and between fixed-time and fixed-confidence variants. As a byproduct, we also give an algorithm for selecting the distribution with the m-th largest mean in the collaborative learning model.
UR - http://www.scopus.com/inward/record.url?scp=85100357036&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85100357036&partnerID=8YFLogxK
U2 - 10.1109/FOCS46700.2020.00024
DO - 10.1109/FOCS46700.2020.00024
M3 - Conference contribution
AN - SCOPUS:85100357036
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 160
EP - 171
BT - Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PB - IEEE Computer Society
T2 - 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Y2 - 16 November 2020 through 19 November 2020
ER -