# The Greedy Advantage in Finite-Horizon Bandits

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 38 references that are in the map.
- First posted on arXiv 31 Jul 2026.

## Builds on (most cited first, 4 of 4)

- [Algorithms for multi-armed bandit problems](https://mlsanity.com/paper/1402.6028/) (2014)
- [On the Prior Sensitivity of Thompson Sampling](https://mlsanity.com/paper/1506.03378/) (2015)
- [Be Greedy in Multi-Armed Bandits](https://mlsanity.com/paper/2101.01086/) (2021)
- [Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure](https://mlsanity.com/paper/2503.04010/) (2025)

## Abstract (arXiv)

Organizations increasingly rely on sequential experimentation to improve decision-making. While the multi-armed bandit literature has developed algorithms with strong asymptotic regret guarantees, many practical applications operate over finite and externally imposed horizons. Motivated by the finite-horizon setting, we develop a class of regularized greedy algorithms for multi-armed Bernoulli bandits. We derive the first finite-horizon regret envelopes for regularized greedy bandits, showing that finite-horizon regret decomposes into transient exploration costs and a suboptimal convergence term that decays exponentially with the regularization strength. This characterization yields principled calibration rules for the regularization parameters and, as a limiting case, sharper regret guarantees for the classical greedy policy. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art algorithms. These results suggest that regularized greedy policies can provide an effective approach for finite-horizon bandit problems.