Bandit Social Learning under Myopic Behavior

We study social learning dynamics motivated by reviews on online platforms. The agents collectively follow a simple multi-armed bandit protocol, but each agent acts myopically, without regards to exploration. We allow a wide range of myopic behaviors that are consistent with (parameterized) confidence intervals for the arms' expected rewards. We derive stark exploration failures for any such behavior, and provide matching positive results. As a special case, we obtain the first general results on failure of the greedy algorithm in bandits, thus providing a theoretical foundation for why bandit algorithms should explore. 1 1 Early versions of our results on the greedy algorithm (Corollary 3.6 and Theorem 6.1) have been available in a book chapter by A. Slivkins [54, Ch. 11]. The authors acknowledge Mark Sellke for proving Theorem 6.1 and suggesting a proof plan for a version of Corollary 3.6. The authors are grateful to Mark Sellke and Chara Podimata for brief collaborations (with A. Slivkins) in the initial stages of this project. 2 In practice, online platforms provide summaries such as the average score and the number of samples. 37th Conference on Neural Information Processing Systems (NeurIPS 2023).