The Greedy Advantage in Finite-Horizon Bandits

AI summary

Overview

Research area: Multi-armed bandits, sequential experimentation, and operations research / statistical machine learning theory.

Technical level: Advanced. The paper combines asymptotic regret analysis (absorption probabilities, drifted random walks, Lundberg roots) with numerical benchmarking against state-of-the-art bandit algorithms.

Scope: The paper develops finite-horizon regret theory and calibration rules for regularized greedy policies in K-armed Bernoulli bandits, and shows through numerical experiments that these policies match or outperform modern bandit algorithms.

What This Paper Is About

Classical bandit theory judges algorithms by their regret as the horizon T grows to infinity, which favors exploration-heavy policies that drive the probability of committing to a suboptimal arm to zero. Many real applications, however, run over finite, externally imposed horizons, where continued exploration is itself costly. The paper asks whether a greedy policy, made less trigger-happy by regularization, can beat asymptotically optimal algorithms within a fixed finite horizon, and it answers yes by characterizing the finite-horizon regret of such policies.

Key Contributions

1. First finite-horizon theory for regularized greedy bandits. The authors derive closed-form, two-sided regret envelopes for the policy that selects the arm maximizing the regularized score p̂_i(t) = (S_i(t) + α)/(N_i(t) + β), decomposing regret into a linear absorption term and a transient abandonment term.

2. New analytical tools for absorbing dynamics. The analysis introduces a score-minimum reduction that converts the adaptive multi-arm process into independent one-arm objects, combined with boundary-crossing arguments for drifted random walks, Lundberg-root change-of-measure estimates, and local Stieltjes replacement arguments.

3. Sharpened guarantees for classical greedy. As the limiting case α = β = 0, the framework yields substantially tighter bounds for the pure greedy policy than previously available analytical benchmarks, including the upper bound of Jedor et al. (2021) and the Bayesian greedy formula of Bayati et al. (2020).

4. Calibration rules under varying information. The regret decomposition yields principled ways to choose (α, β), ranging from oracle settings in which the problem instance is known to fully adaptive implementations requiring no knowledge of either the horizon or the arm means; numerical experiments show these calibrated policies match or outperform Thompson Sampling, OGI, and IDS.

Main Findings

• Regret splits into two terms. Finite-horizon regret decomposes into a linear term R_linear = T Σ_{i=2, p_i < p_1}^{K} δ_i P(Q_i), which comes from permanent convergence to a suboptimal arm, and a transient term R_transient, which is independent of T and reflects delayed abandonment of competing arms.

• Regularization moves the two terms in opposite directions. Increasing the regularization margin Δ_i := α − p_i β raises the rate parameter λ_i := 2Δ_i / σ_i² (with σ_i² := p_i(1 − p_i)), which suppresses the probability of suboptimal convergence exponentially, while simultaneously increasing R_transient by delaying abandonment.

• A closed-form absorption probability. The approximation P̃(Q_i) = Σ_{m=i}^{K} (1/m) exp{−Σ_{h=1}^{m} λ_h δ_hm} [1 − exp{−(Σ_{h=1}^{m} λ_h) δ_{m,m+1}}] is given explicitly, with δ_hh := 0 and δ_{K,K+1} := ∞, and the bracket interpreted as zero when m = K.

• Two-sided envelope (Theorem 2). For α > 0 satisfying α ≥ p_1 β ≥ 0, and for every finite horizon T, R_linear(T)(1 − o(1)) − o(1) ≤ R(T) ≤ (R_linear(T) + R_transient)(1 + o(1)), where R_transient := C_Δ := (K − 1)Δ_1. The small-o terms are taken with respect to the regularization strength, not the horizon.

• The asymptotic regime is in regularization, not horizon. Assumption 1 takes Δ_1 → ∞ while T stays fixed, with Δ_i = Θ(Δ_1), β = O(Δ_1), and every nonzero pairwise gap p_i − p_j = Θ(Δ_1^{−κ}) for a common κ ∈ (1/2, 1).

• Envelopes are empirically tight. Across Monte Carlo experiments with arm means drawn from Uniform[0.01, 0.99], N = 10,000 replications, horizon T = 5,000, and (α, β) settings of (10, 0), (25, 0), and (25, 25), the analytical envelope closely matched realized regret for K = 2 and K = 10; small gaps where the upper envelope falls slightly below the Monte Carlo curve are attributed to finite-regularization effects from the omitted o(1) remainders.

• Apparent regret plateaus are not plateaus. For any fixed regularization parameters, Theorem 2 shows regret remains asymptotically linear in T; the visible saturation arises because the linear coefficient is exponentially small in the regularization level, so transient costs dominate over practical horizons.

• Pure greedy bounds improve on prior work. In comparisons for K ∈ {2, 5, 8, 10}, the branchwise characterization of Part 2 of Theorem 2 produced substantially tighter upper bounds than the existing analytical benchmarks and substantially improved on the previously available analytical lower benchmark. The authors note that the Bayati et al. (2020) result is derived under a many-arm asymptotic requiring K ≥ 30 log T / c_0 (for example, K ≥ 256 when T = 5,000 and c_0 = 1), far above the K values in their experiments, so it is included as a reference point rather than a benchmark.

• Explicit numeric regret values are not reported in the provided text. The paper states that calibrated regularized greedy policies consistently match or outperform Thompson Sampling, OGI, and IDS, but the truncated content contains no tabulated regret figures for those comparisons.

Methodology in Plain English

The authors study the simplest version of the sequential decision problem: K arms with unknown success probabilities p_1 ≥ p_2 ≥ ⋯ ≥ p_K, binary rewards, and a fixed number of rounds T. Their policy is almost entirely greedy. It pulls each arm once, then always pulls whichever arm currently has the highest score, where the score is the observed success rate "smoothed" by adding α imaginary successes and β imaginary trials. Setting α = β = 0 recovers pure greedy.

The trick that makes the analysis tractable is to stop thinking about the trajectory moment by moment. Instead, the authors show that each arm's fate can be summarized by the lowest score it ever attains. Whichever arm has the deepest drawdown relative to its mean is the one that gets abandoned. This converts a complicated adaptive process into a set of independent single-arm problems whose tail probabilities have exponential bounds expressible in closed form.

With absorption probabilities in hand, total regret is just the probability of landing on the wrong arm times how bad that arm is times how many rounds remain, plus the finite cost of sampling arms that eventually get dropped. The authors take an asymptotic limit in which the regularization strength grows while T stays fixed, so that both regret terms survive and can be written out explicitly. They then validate the resulting formulas against Monte Carlo simulations and against algorithms from the literature.

Why This Matters

Research impact. The paper challenges the habit of evaluating bandit algorithms by asymptotic T → ∞ regret. It argues that driving suboptimal-convergence probability to zero necessarily requires ongoing exploration that is costly within a finite window, and it supplies the theory to trade the two costs off deliberately. It also gives the classical greedy policy sharper regret guarantees than previously available.

Real-world applications (drawn from the paper):

• Pharmaceutical companies running adaptive clinical trials, learning about treatment performance while patients are still being enrolled.
• Hospital systems sequentially allocating patients across treatment protocols and observing binary outcomes such as recovery or deterioration.
• Organizations opening facilities sequentially and observing binary indicators of operational success, such as whether a facility meets a target utilization threshold.
• Digital platforms allocating traffic across recommendations and interface designs and observing binary engagement outcomes such as clicks or purchases.

Industry relevance. Greedy policies are trivial to implement and cheap to compute, while UCB, Thompson sampling, and information-directed methods demand infrastructure for posterior sampling, confidence bounds, or information-gain computations. The paper's calibrated regularized greedy policies offer competitive finite-horizon performance with that simplicity intact, which matters for A/B testing platforms, recommendation systems, and marketing or product-launch campaigns that run for a bounded period rather than forever.

Future Directions

• Calibration beyond oracle access. The paper derives calibration rules spanning oracle settings and fully adaptive ones; an open question is how close adaptive calibration can come to oracle performance across heterogeneous instances and horizons.

• Extension beyond Bernoulli rewards. The theory is developed specifically for binary outcomes; whether the absorption-probability machinery carries over to general reward distributions is not established in the provided content.

• Extension beyond the i.i.d. bandit. The literature review notes greedy successes in contextual bandits, dynamic pricing, and correlated-reward settings, but the paper's own theory covers the non-contextual Bernoulli case.

• Reconciling finite-horizon and asymptotic objectives. The results suggest the asymptotically optimal exploration schedule is not optimal within a fixed window; characterizing the correct objective more broadly for finite-horizon deployment is left as a question for the field.

Target Audience

Advanced graduate students and researchers in bandit theory, sequential decision-making, and reinforcement learning, along with operations research and management science scholars working on experimental design. The paper is also relevant to practitioners in clinical trials, online experimentation, recommendation systems, and healthcare operations who need algorithms tuned for finite horizons rather than asymptotic guarantees, and who must choose policies in settings where the paper reports calibrated greedy rivals established methods.

Authors’ 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.