# Greedy Algorithm almost Dominates in Smoothed Contextual Bandits

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

## Key facts

- Cited by 20 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 May 2020.

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

- [Repeated Bilateral Trade Against a Smoothed Adversary](https://mlsanity.com/paper/2302.10805/) (2023)
- [Exploration and Incentives in Reinforcement Learning](https://mlsanity.com/paper/2103.00360/) (2021)
- [Safe Policy Learning through Extrapolation: Application to Pre-trial Risk Assessment](https://mlsanity.com/paper/2109.11679/) (2021)
- [Analysis of Thompson Sampling for Partially Observable Contextual Multi-Armed Bandits](https://mlsanity.com/paper/2110.12175/) (2021)
- [Strategic Apple Tasting](https://mlsanity.com/paper/2306.06250/) (2023)
- [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)
- [Incentive-Aware Recommender Systems in Two-Sided Markets](https://mlsanity.com/paper/2211.15381/) (2022)
- [Thompson Sampling in Partially Observable Contextual Bandits](https://mlsanity.com/paper/2402.10289/) (2024)
- [Apple Tasting Revisited: Bayesian Approaches to Partially Monitored Online Binary Classification](https://mlsanity.com/paper/2109.14412/) (2021)
- [Efficient Algorithms for Learning to Control Bandits with Unobserved Contexts](https://mlsanity.com/paper/2202.00867/) (2022)
- [Demystifying Online Clustering of Bandits: Enhanced Exploration Under Stochastic and Smoothed Adversarial Contexts](https://mlsanity.com/paper/2501.00891/) (2025)
- [Incentivized Exploration via Filtered Posterior Sampling](https://mlsanity.com/paper/2402.13338/) (2024)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Exploration and Persuasion](https://mlsanity.com/paper/2410.17086/) (2024)
- [Infrequent Exploration in Linear Bandits](https://mlsanity.com/paper/2510.26000/) (2025)
- [Prior-Agnostic Incentive-Compatible Exploration](https://mlsanity.com/paper/2602.20465/) (2026)
- [Personalized Alignment Revisited: The Necessity and Sufficiency of User Diversity](https://mlsanity.com/paper/2605.09119/) (2026)
- [Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits](https://mlsanity.com/paper/2609.28718/) (2026)
- [Adaptive Random Matrices in Gaussian Bandits: Spectral Universality and Selection-Induced Outliers](https://mlsanity.com/paper/2609.30321/) (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 in order to gain information that will lead to better decisions in the future. While necessary in the worst case, explicit exploration has a number of disadvantages compared to the greedy algorithm that always "exploits" by choosing an action that currently looks optimal. We 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 in the linear contextual bandits model. We improve 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(T1/3).