Title: The Externalities of Exploration and How Data Diversity Helps Exploitation,
Abstract: 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 $\tilde{O}(T^{1/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.