2018/06/01 by Manish Raghavan, Raghavan, Manish, Aleksandrs Slivkins +5 · 3 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Computers and Society (cs.CY) #Data Stream Mining Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mobile Crowdsensing and Crowdsourcing
paper · pdf · doi:10.48550/arxiv.1806.00543
openalex publication_date 2018/06/01 · openalex created_date 2022/10/03 · openalex updated_date 2026/07/28
Online learning algorithms, widely used to power search and content\noptimization on the web, must balance exploration and exploitation, potentially\nsacrificing the experience of current users for information that will lead to\nbetter decisions in the future. Recently, concerns have been raised about\nwhether the process of exploration could be viewed as unfair, placing too much\nburden on certain individuals or groups. Motivated by these concerns, we\ninitiate the study of the externalities of exploration - the undesirable side\neffects that the presence of one party may impose on another - under the linear\ncontextual bandits model. We introduce the notion of a group externality,\nmeasuring the extent to which the presence of one population of users impacts\nthe rewards of another. We show that this impact can in some cases be negative,\nand that, in a certain sense, no algorithm can avoid it. We then study\nexternalities at the individual level, interpreting the act of exploration as\nan externality imposed on the current user of a system by future users. This\ndrives us to ask under what conditions inherent diversity in the data makes\nexplicit exploration unnecessary. We build on a recent line of work on the\nsmoothed analysis of the greedy algorithm that always chooses the action that\ncurrently looks optimal, improving on prior results to show that a greedy\napproach almost matches the best possible Bayesian regret rate of any other\nalgorithm on the same problem instance whenever the diversity conditions hold,\nand that this regret is at most \O(T1/3). Returning to group-level\neffects, we show that under the same conditions, negative group externalities\nessentially vanish under the greedy algorithm. Together, our results uncover a\nsharp contrast between the high externalities that exist in the worst case, and\nthe ability to remove all externalities if the data is sufficiently diverse.\n