A smoothed analysis of the greedy algorithm for the linear contextual bandit problem

Sampath Kannan, Jamie Morgenstern, Aaron Roth, Bo Waggoner, Zhiwei Steven Wu

Research output: Contribution to journalConference articlepeer-review

38 Scopus citations


Bandit learning is characterized by the tension between long-term exploration and short-term exploitation. However, as has recently been noted, in settings in which the choices of the learning algorithm correspond to important decisions about individual people (such as criminal recidivism prediction, lending, and sequential drug trials), exploration corresponds to explicitly sacrificing the well-being of one individual for the potential future benefit of others. In such settings, one might like to run a “greedy” algorithm, which always makes the optimal decision for the individuals at hand - but doing this can result in a catastrophic failure to learn. In this paper, we consider the linear contextual bandit problem and revisit the performance of the greedy algorithm. We give a smoothed analysis, showing that even when contexts may be chosen by an adversary, small perturbations of the adversary's choices suffice for the algorithm to achieve “no regret”, perhaps (depending on the specifics of the setting) with a constant amount of initial training data. This suggests that in slightly perturbed environments, exploration and exploitation need not be in conflict in the linear setting.1.

Original languageEnglish (US)
Pages (from-to)2227-2236
Number of pages10
JournalAdvances in Neural Information Processing Systems
StatePublished - 2018
Event32nd Conference on Neural Information Processing Systems, NeurIPS 2018 - Montreal, Canada
Duration: Dec 2 2018Dec 8 2018

Bibliographical note

Publisher Copyright:
© 2018 Curran Associates Inc.All rights reserved.


Dive into the research topics of 'A smoothed analysis of the greedy algorithm for the linear contextual bandit problem'. Together they form a unique fingerprint.

Cite this