# Bandit Learning with Positive Externalities

arXiv: https://arxiv.org/abs/1802.05693 · HTML: https://mlsanity.com/paper/1802.05693/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Feb 2018.

## Built on by (most cited first, 5 of 5)

- [Online Recommendations for Agents with Discounted Adaptive Preferences](https://mlsanity.com/paper/2302.06014/) (2023)
- [Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality](https://mlsanity.com/paper/2406.19824/) (2024)
- [Incentivized Bandit Learning with Self-Reinforcing User Preferences](https://mlsanity.com/paper/2105.08869/) (2021)
- [Batched Bandits with Crowd Externalities](https://mlsanity.com/paper/2109.14733/) (2021)
- [Influencing Bandits: Arm Selection for Preference Shaping](https://mlsanity.com/paper/2403.00036/) (2024)

## Abstract (arXiv)

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.