Competing bandits: Learning under competition

Yishay Mansour, Aleksandrs Slivkins, Zhiwei Steven Wu

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

5 Scopus citations

Abstract

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
DOIs
StatePublished - Jan 1 2018
Externally publishedYes
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
Volume94
ISSN (Print)1868-8969

Other

Other9th Innovations in Theoretical Computer Science, ITCS 2018
CountryUnited States
CityCambridge
Period1/11/181/14/18

Keywords

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

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

  • Cite this

    Mansour, Y., Slivkins, A., & Wu, Z. S. (2018). Competing bandits: Learning under competition. In A. R. Karlin (Ed.), 9th Innovations in Theoretical Computer Science, ITCS 2018 [48] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 94). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.ITCS.2018.48