aiqbench analysis
This research introduces regularized greedy algorithms specifically optimized for finite-horizon multi-armed bandit problems, addressing the practical constraints of externally imposed time limits often overlooked in asymptotic literature. By deriving novel regret envelopes that decompose exploration costs and convergence terms, the study provides principled calibration rules that allow these policies to match or exceed state-of-the-art performance without relying on infinite-time assumptions. The findings offer a more robust theoretical foundation for sequential decision-making systems operating under strict temporal boundaries.
The Greedy Advantage in Finite-Horizon Bandits
arXiv:2607.29375v1 Announce Type: cross Abstract: 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.
Abstract: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.
Machine Learning (stat.ML); Machine Learning (cs.LG)
arXiv:2607.29375 [stat.ML]
(or arXiv:2607.29375v1 [stat.ML] for this version)
https://doi.org/10.48550/arXiv.2607.29375 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 231 words
Related coverage
Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors
arXiv · Sep 30, 2026
From Relaxed Indexability to Exact Indexability: A $t$-Step Approach for Partially Observable Restless Bandits
arXiv · Aug 26, 2026
Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
arXiv · Oct 16, 2026
Fooling Algorithms in Non-Stationary Bandits using Belief Inertia
arXiv · Sep 30, 2026