Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory

Lili Su, Martin Zubeldia, Nancy Lynch

Research output: Contribution to journalArticlepeer-review

Abstract

We consider multi-Armed bandit problems in social groups wherein each individual has bounded memory and shares the common goal of learning the best arm/option. We say an individual learns the best option if eventually (as t-∞) it pulls only the arm with the highest expected reward. While this goal is provably impossible for an isolated individual due to bounded memory, we show that, in social groups, this goal can be achieved easily with the aid of social persuasion (i.e., communication) as long as the communication networks/graphs satisfy some mild conditions. In this work, we model and analyze a type of learning dynamics which are wellobserved in social groups. Specifically, under the learning dynamics of interest, an individual sequentially decides on which arm to pull next based on not only its private reward feedback but also the suggestion provided by a randomly chosen neighbor. To deal with the interplay between the randomness in the rewards and in the social interaction, we employ the mean-field approximation method. Considering the possibility that the individuals in the networks may not be exchangeable when the communication networks are not cliques, we go beyond the classic mean-field techniques and apply a refined version of mean-field approximation. Notably, our results hold even if the communication graphs are highly sparse.

Original languageEnglish (US)
Pages (from-to)1-2
Number of pages2
JournalPerformance Evaluation Review
Volume47
Issue number1
DOIs
StatePublished - Dec 17 2019
Externally publishedYes

Bibliographical note

Publisher Copyright:
© 2019 Copyright is held by the owner/author(s).

Keywords

  • bio-inspired distributed algorithms
  • distributed systems
  • mean-field approximation

Fingerprint

Dive into the research topics of 'Collaboratively Learning the Best Option on Graphs, Using Bounded Local Memory'. Together they form a unique fingerprint.

Cite this