Collaborative Top Distribution Identifications with Limited Interaction

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 {\em 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.

arXiv commentAccepted for presentation at FOCS 2020

References in corpus (18)

• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Distributed Learning in Multi-Armed Bandit with Multiple Players
• lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits
• Communication Complexity of Distributed Convex Learning and Optimization
• Optimal Best Arm Identification with Fixed Confidence
• Delay and Cooperation in Nonstochastic Bandits
• Online Learning with Switching Costs and Other Adaptive Adversaries
• Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem
• Distributed Exploration in Multi-Armed Bandits
• Adaptive Crowdsourcing Algorithms for the Bandit Survey Problem
• Provably Efficient Q-Learning with Low Switching Cost
• Towards Instance Optimal Bounds for Best Arm Identification
• Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime
• Distributed Non-Stochastic Experts
• Scalable Coordinated Exploration in Concurrent Reinforcement Learning
• Tight Bounds for Collaborative PAC Learning via Multiplicative Weights
• On Communication Complexity of Classification Problems

Cited by in corpus (2)

• Online Learning for Cooperative Multi-Player Multi-Armed Bandits
• Collaborative Pure Exploration in Kernel Bandit