The Greedy Advantage in Finite-Horizon Bandits

arXiv:2607.29375 · stat.ML, cs.LG · Submitted 2026-07-31 · Read on arXiv

Kai Zhou, Michael Lingzhi Li, Kai Wang

stat.ML, cs.LG

Submitted: 2026-07-31

Comments: 122 pages, 3 figures, submitted to Management Science and under peer review

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Regret — 165× in this paper · explained in 4 episodes
• Regularization — 66× in this paper · explained in 3 episodes
• Benchmark — 33× in this paper · explained in 2 episodes
• Calibration — 25× in this paper · explained in 9 episodes
• Localization — 11× in this paper · explained in 2 episodes
• Absorb — 9× in this paper · explained in 1 episode
• Regret Guarantees — 7× in this paper · explained in 2 episodes
• Monotonicity — 5× in this paper · explained in 2 episodes
• Accuracy — 4× in this paper · explained in 1 episode
• Core — 4× in this paper · explained in 2 episodes
• Contextual Bandit — 3× in this paper · explained in 2 episodes
• Contextual Bandits — 3× in this paper · explained in 3 episodes
• Monte Carlo — 3× in this paper
• Regret Bound — 3× in this paper · explained in 2 episodes
• Entanglement — 2× in this paper · explained in 5 episodes
• Regret Bounds — 2× in this paper · explained in 2 episodes
• Composition — 1× in this paper · explained in 2 episodes
• Computational Tractability — 1× in this paper · explained in 2 episodes
• Editor — 1× in this paper · explained in 2 episodes
• Information Gain — 1× in this paper · explained in 2 episodes
• Papers — 1× in this paper · explained in 3 episodes
• Parameterization — 1× in this paper · explained in 2 episodes
• Reinforcement Learning — 1× in this paper · explained in 4 episodes

Sources

• Be Greedy in Multi-Armed Bandits
• Algorithms for multi-armed bandit problems
• On the Prior Sensitivity of Thompson Sampling
• Greedy Algorithm for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure

Related papers

• Behavior of prediction performance metrics with rare events
• Optimal Estimation of Generic Dynamics by Path-Dependent Neural Jump ODEs
• A Posterior-Dynamics Framework for Imaging Inverse Problems with Pretrained Diffusion Priors
• Scalable Posterior Uncertainty for Flexible Density-Based Clustering
• A Transport Geometry of Benign Overfitting
• Efficient quadratic entropy with distance sketches