# The Externalities of Exploration and How Data Diversity Helps Exploitation

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2018.

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

- [Federated Linear Contextual Bandits](https://mlsanity.com/paper/2110.14177/) (2021)
- [Smoothed Analysis with Adaptive Adversaries](https://mlsanity.com/paper/2102.08446/) (2021)
- [Generalized Linear Bandits with Local Differential Privacy](https://mlsanity.com/paper/2106.03365/) (2021)
- [Fair Exploration via Axiomatic Bargaining](https://mlsanity.com/paper/2106.02553/) (2021)
- [Oracle-Efficient Online Learning for Beyond Worst-Case Adversaries](https://mlsanity.com/paper/2202.08549/) (2022)
- [Dynamic Sparse Training via Balancing the Exploration-Exploitation Trade-off](https://mlsanity.com/paper/2211.16667/) (2022)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [Multi-disciplinary fairness considerations in machine learning for clinical trials](https://mlsanity.com/paper/2205.08875/) (2022)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Bandit Social Learning: Exploration under Myopic Behavior](https://mlsanity.com/paper/2302.07425/) (2023)
- [Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits](https://mlsanity.com/paper/2306.14872/) (2023)
- [From Noise to Signal to Selbstzweck: Reframing Human Label Variation in the Era of Post-training in NLP](https://mlsanity.com/paper/2510.12817/) (2025)
- [Leveraging the Power of Conversations: Optimal Key Term Selection in Conversational Contextual Bandits](https://mlsanity.com/paper/2505.21393/) (2025)
- [Creator Incentives in Recommender Systems: A Cooperative Game-Theoretic Approach for Stable and Fair Collaboration in Multi-Agent Bandits](https://mlsanity.com/paper/2604.08643/) (2026)
- [Getting too personal(ized): The importance of feature choice in online adaptive algorithms](https://mlsanity.com/paper/2309.02856/) (2023)
- [New Classes of the Greedy-Applicable Arm Feature Distributions in the Sparse Linear Bandit Problem](https://mlsanity.com/paper/2312.12400/) (2023)
- [Collaborative Min-Max Regret in Grouped Multi-Armed Bandits](https://mlsanity.com/paper/2506.10313/) (2025)
- [Annealed Softmax Greedy in Many-Armed Bayesian Bandits](https://mlsanity.com/paper/2605.31034/) (2026)
- [Contextual Slate GLM Bandits with Limited Adaptivity](https://mlsanity.com/paper/2606.31449/) (2026)
- [Exact Regret Frontiers and Externality Scheduling in Centralized Serial-Dictatorship Bandits](https://mlsanity.com/paper/2609.19963/) (2026)

## Abstract (arXiv)

Online learning algorithms, widely used to power search and content optimization on the web, must balance exploration and exploitation, potentially sacrificing the experience of current users for information that will lead to better decisions in the future. Recently, concerns have been raised about whether the process of exploration could be viewed as unfair, placing too much burden on certain individuals or groups. Motivated by these concerns, we initiate the study of the externalities of exploration - the undesirable side effects that the presence of one party may impose on another - under the linear contextual bandits model. We introduce the notion of a group externality, measuring the extent to which the presence of one population of users impacts the rewards of another. We show that this impact can in some cases be negative, and that, in a certain sense, no algorithm can avoid it. We then study externalities at the individual level, interpreting the act of exploration as an externality imposed on the current user of a system by future users. This drives us to ask under what conditions inherent diversity in the data makes explicit exploration unnecessary. We build on a recent line of work on the smoothed analysis of the greedy algorithm that always chooses the action that currently looks optimal, improving on prior results to show that a greedy approach almost matches the best possible Bayesian regret rate of any other algorithm on the same problem instance whenever the diversity conditions hold, and that this regret is at most tildeO(T1/3). Returning to group-level effects, we show that under the same conditions, negative group externalities essentially vanish under the greedy algorithm. Together, our results uncover a sharp contrast between the high externalities that exist in the worst case, and the ability to remove all externalities if the data is sufficiently diverse.