Competing bandits: Learning under competition

Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu

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

16 Scopus citations


Most modern systems strive to learn from interactions with users, and many engage in exploration: making potentially suboptimal choices for the sake of acquiring new information. We initiate a study of the interplay between exploration and competition—how such systems balance the exploration for learning and the competition for users. Here the users play three distinct roles: they are customers that generate revenue, they are sources of data for learning, and they are self-interested agents which choose among the competing systems. In our model, we consider competition between two multi-armed bandit algorithms faced with the same bandit instance. Users arrive one by one and choose among the two algorithms, so that each algorithm makes progress if and only if it is chosen. We ask whether and to what extent competition incentivizes the adoption of better bandit algorithms. We investigate this issue for several models of user response, as we vary the degree of rationality and competitiveness in the model. Our findings are closely related to the “competition vs. innovation” relationship, a well-studied theme in economics.

Original languageEnglish (US)
Title of host publication9th Innovations in Theoretical Computer Science, ITCS 2018
EditorsAnna R. Karlin
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770606
StatePublished - Jan 1 2018
Event9th Innovations in Theoretical Computer Science, ITCS 2018 - Cambridge, United States
Duration: Jan 11 2018Jan 14 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Other9th Innovations in Theoretical Computer Science, ITCS 2018
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© Yishay Mansour, Aleksandrs Slivkins, and Zhiwei Steven Wu.


  • Competition
  • Exploration
  • Game theory
  • Machine learning
  • Rationality


Dive into the research topics of 'Competing bandits: Learning under competition'. Together they form a unique fingerprint.

Cite this