Bandit Learning with Positive Externalities

Abstract

In many platforms, user arrivals exhibit a self-reinforcing behavior: future user arrivals are likely to have preferences similar to users who were satisfied in the past. In other words, arrivals exhibit positive externalities. We study multiarmed bandit (MAB) problems with positive externalities. We show that the self-reinforcing preferences may lead standard benchmark algorithms such as UCB to exhibit linear regret. We develop a new algorithm, Balanced Exploration (BE), which explores arms carefully to avoid suboptimal convergence of arrivals before sufficient evidence is gathered. We also introduce an adaptive variant of BE which successively eliminates suboptimal arms. We analyze their asymptotic regret, and establish optimality by showing that no algorithm can perform better.

arXiv comment31 pages, 1 table, 2 figures

Cited by in corpus (8)

• Hidden Incentives for Auto-Induced Distributional Shift
• Optimal dynamic information provision in traffic routing
• Multi-Armed Bandits for Correlated Markovian Environments with Smoothed Reward Feedback
• Incentivized Bandit Learning with Self-Reinforcing User Preferences
• Learning by Repetition: Stochastic Multi-armed Bandits under Priming Effect
• Batched Bandits with Crowd Externalities
• Dynamic social learning under graph constraints
• Bandits with Temporal Stochastic Constraints