License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2018.48
URN: urn:nbn:de:0030-drops-83341
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8334/
Go to the corresponding LIPIcs Volume Portal

Mansour, Yishay ; Slivkins, Aleksandrs ; Wu, Zhiwei Steven

Competing Bandits: Learning Under Competition

pdf-format:
LIPIcs-ITCS-2018-48.pdf (0.7 MB)

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.

BibTeX - Entry

@InProceedings{mansour_et_al:LIPIcs:2018:8334,
  author =	{Yishay Mansour and Aleksandrs Slivkins and Zhiwei Steven Wu},
  title =	{{Competing Bandits: Learning Under Competition}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{48:1--48:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Anna R. Karlin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8334},
  URN =		{urn:nbn:de:0030-drops-83341},
  doi =		{10.4230/LIPIcs.ITCS.2018.48},
  annote =	{Keywords: machine learning, game theory, competition, exploration, rationality}
}

Keywords: machine learning, game theory, competition, exploration, rationality
Collection: 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Issue Date: 2018
Date of publication: 12.01.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI