# The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms

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

## Key facts

- Cited by 28 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2020.

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

- [A survey on multi-player bandits](https://mlsanity.com/paper/2211.16275/) (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)
- [Parallelizing Contextual Bandits](https://mlsanity.com/paper/2105.10590/) (2021)
- [Rotting Infinitely Many-armed Bandits](https://mlsanity.com/paper/2201.12975/) (2022)
- [Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms](https://mlsanity.com/paper/2210.00340/) (2022)
- [Discounted Thompson Sampling for Non-Stationary Bandit Problems](https://mlsanity.com/paper/2305.10718/) (2023)
- [Byzantine-Resilient Decentralized Multi-Armed Bandits](https://mlsanity.com/paper/2310.07320/) (2023)
- [Adaptive Instruction Composition for Automated LLM Red-Teaming](https://mlsanity.com/paper/2604.21159/) (2026)
- [Auto-Transfer: Learning to Route Transferrable Representations](https://mlsanity.com/paper/2202.01011/) (2022)
- [An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints](https://mlsanity.com/paper/2404.14202/) (2024)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)
- [Max-Utility Based Arm Selection Strategy For Sequential Query Recommendations](https://mlsanity.com/paper/2108.13810/) (2021)
- [Discover Life Skills for Planning with Bandits via Observing and Learning How the World Works](https://mlsanity.com/paper/2207.08130/) (2022)
- [Tracking Most Significant Shifts in Infinite-Armed Bandits](https://mlsanity.com/paper/2502.00108/) (2025)
- [Sequential Bayesian Evaluation of Large Language Model Behavior](https://mlsanity.com/paper/2511.10661/) (2025)
- [Mixture-Greedy for Online Generative Model Selection: Is UCB Necessary in Diversity-Aware Multi-Armed Bandits?](https://mlsanity.com/paper/2603.21716/) (2026)
- [Improving Sequential Query Recommendation with Immediate User Feedback](https://mlsanity.com/paper/2205.06297/) (2022)
- [Approximate information maximization for bandit games](https://mlsanity.com/paper/2310.12563/) (2023)
- [Little Exploration is All You Need](https://mlsanity.com/paper/2310.17538/) (2023)
- [An Exploration-free Method for a Linear Stochastic Bandit Driven by a Linear Gaussian Dynamical System](https://mlsanity.com/paper/2504.03926/) (2025)
- [Preference-based learning for news headline recommendation](https://mlsanity.com/paper/2506.06334/) (2025)
- [UCB for Large-Scale Pure Exploration: Beyond Sub-Gaussianity](https://mlsanity.com/paper/2511.22273/) (2025)
- [Is Pure Exploitation Sufficient in Exogenous MDPs with Linear Function Approximation?](https://mlsanity.com/paper/2601.20694/) (2026)
- [Learning to Assign Prediction Tasks to Agents with Capacity Constraints](https://mlsanity.com/paper/2605.27999/) (2026)
- [Annealed Softmax Greedy in Many-Armed Bayesian Bandits](https://mlsanity.com/paper/2605.31034/) (2026)
- [Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity](https://mlsanity.com/paper/2609.38659/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

We investigate a Bayesian k-armed bandit problem in the many-armed regime, where k ≥ √T and T represents the time horizon. Initially, and aligned with recent literature on many-armed bandit problems, we observe that subsampling plays a key role in designing optimal algorithms; the conventional UCB algorithm is sub-optimal, whereas a subsampled UCB (SS-UCB), which selects Theta(√T) arms for execution under the UCB framework, achieves rate-optimality. However, despite SS-UCB's theoretical promise of optimal regret, it empirically underperforms compared to a greedy algorithm that consistently chooses the empirically best arm. This observation extends to contextual settings through simulations with real-world data. Our findings suggest a new form of free exploration beneficial to greedy algorithms in the many-armed context, fundamentally linked to a tail event concerning the prior distribution of arm rewards. This finding diverges from the notion of free exploration, which relates to covariate variation, as recently discussed in contextual bandit literature. Expanding upon these insights, we establish that the subsampled greedy approach not only achieves rate-optimality for Bernoulli bandits within the many-armed regime but also attains sublinear regret across broader distributions. Collectively, our research indicates that in the many-armed regime, practitioners might find greater value in adopting greedy algorithms.