Collaborative top distribution identifications with limited interaction (extended abstract)

Nikolai Karpov, Qin Zhang, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
PublisherIEEE Computer Society
Pages160-171
Number of pages12
ISBN (Electronic)9781728196213
DOIs
StatePublished - Nov 2020
Event61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 - Virtual, Durham, United States
Duration: Nov 16 2020Nov 19 2020

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2020-November
ISSN (Print)0272-5428

Conference

Conference61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
Country/TerritoryUnited States
CityVirtual, Durham
Period11/16/2011/19/20

ASJC Scopus subject areas

  • General Computer Science

Fingerprint

Dive into the research topics of 'Collaborative top distribution identifications with limited interaction (extended abstract)'. Together they form a unique fingerprint.

Cite this