Pith. sign in

REVIEW 4 major objections 4 minor 44 references

The Greedy Advantage in Finite-Horizon Bandits

T0 review · 4 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper claims that a simple regularized greedy rule—pull the arm with the largest (successes+α)/(pulls+β)—matches or beats sophisticated bandit algorithms over finite horizons, via a closed-form regret envelope that tunes α and β.

desk verdict Solid new asymptotic theory for regularized greedy bandits, but the calibration rules inherit an unproven fixed-gap transfer and the 1/m absorption prefactor is wrong at unequal arm variances. read the letter →

arxiv 2607.29375 v1 pith:QECTSSOG submitted 2026-07-31 stat.ML cs.LG

Kai Zhou , Michael Lingzhi Li , Kai Wang This is my paper
classification stat.MLcs.LG MSC 62L0568T05
keywords finite-horizonbanditsregularizedgreedyregretenvelopeabsorptionprobabilitycalibrationrulesBernoulliLundbergroot
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Most bandit algorithms are designed for long horizons, but many real experiments have fixed, short horizons. This paper argues that in that setting the usual wisdom is reversed: the danger is not too little exploration but occasional permanent commitment to a suboptimal arm, and continued exploration itself is costly. It studies a class of regularized greedy policies that select the arm with the largest (successes+α)/(pulls+β), derives a two-sided envelope for finite-horizon regret, and shows the regret splits into a transient exploration term and a linear absorption term whose probability has a closed exponential form. The resulting calibration rules for (α,β) produce horizon-aware and fully adaptive versions that, in the paper's experiments, match or outperform standard algorithms like Thompson sampling, optimistic Gittins indices, and information-directed sampling.

What carries the argument

The score-minimum reduction: each arm's eventual absorption is decided by its minimum regularized score over an independent reward stream. The event that a given arm's score minimum is low enough to absorb is a boundary-crossing event for a Bernoulli random walk with negative drift, controlled by a Lundberg root. This root yields a local exponential tail with rate λ_i = 2(α−p_iβ)/(p_i(1−p_i)). A local Stieltjes replacement argument converts the multivariate absorbing probability into a closed-form integral that evaluates to the eP(Qᵢ) sum. This machinery carries the proof and gives the calibration objective.

What would settle it

Run the calibrated policies on a large ensemble of randomly drawn fixed-gap Bernoulli instances (say 1000 instances, 5 arms, T=5000) and compare simulated absorption frequencies with eP(Qᵢ). If relative error exceeds 20% for a substantial fraction of instances, the regime transfer fails and the calibration rules lose their theoretical justification. Equivalently, find any fixed-gap instance where the claimed upper envelope in Theorem 2 falls below the Monte Carlo regret by a non-negligible margin—the paper already concedes small violations in some panels.

Watch

Extended reading notes

Core claim

The central discovery is a finite-horizon regret decomposition: for any fixed horizon T, the regret of the regularized greedy policy is sandwiched between T times a linear absorption term and the same term plus a transient cost (K−1)Δ₁. The absorption probability for each suboptimal arm i is approximated by eP(Qᵢ) = Σ_{m=i}^K (1/m) exp(−Σ_{h=1}^m λ_h δ_{hm}) [1 − exp(−(Σ_{h=1}^m λ_h) δ_{m,m+1})], where λ_h = 2(α − p_h β)/(p_h(1−p_h)) is a regularization-adjusted rate. This closed form makes the trade-off visible: increasing (α,β) shrinks the exponential absorption probability while lengthening the transient phase. The paper derives calibration rules that balance the two, presents this as the

Load-bearing premise

The load-bearing assumption is that the closed-form absorption probability, proven under an asymptotic regime where gaps shrink as the regularization grows, remains accurate at the fixed, moderate gaps used in calibration and experiments; the paper provides no fixed-gap theorem and only limited empirical checks.

Editorial extensions

If this is right

  • Practitioners can implement a finite-horizon experiment with a greedy rule and a horizon-dependent prior (α,β), avoiding the computational overhead of index-based or information-directed policies while matching their regret.
  • The regret envelope turns the abstract exploration–exploitation trade-off into an explicit one-dimensional optimization: the optimal α is the unique solution of a scalar equation (Proposition 6), making calibration easy to deploy.
  • If the empirical agreement at moderate regularization holds in general, the formula gives a quantitative explanation for why greedy-like exploration can be appropriate when the horizon is short.
  • The same decomposition applies to the pure-greedy limit α=β=0, giving branchwise regret bounds that the paper shows are tighter than previous analytical greedy bounds.
  • The fully adaptive variant removes the need to know either the horizon or arm means, so the method is applicable to experimentation platforms with unknown stopping times.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The transfer of the absorption formula from the shrinking-gap regime to fixed gaps is tested only lightly in the paper (one random instance per configuration). A large-scale random-instance test could reveal systematic bias in eP(Qᵢ) for moderate α or larger K, which would weaken the stated justification of the calibration rules but not necessarily the empirical performance.
  • Inference: Because the 1/m prefactor in eP(Qᵢ) arises from uniform tie-breaking, the optimal (α,β) should depend on the tie-breaking rule; platforms that break ties by index or with a fixed randomization seed will likely need different calibration constants.
  • Inference: The exponential form couples each arm's regret gap δ and regularization margin through products λ_h δ_{hm}, suggesting a natural extension to bounded rewards or contextual bandits by replacing the Bernoulli Lundberg root with the appropriate exponential-family cumulant.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

Summary. The paper studies regularized greedy policies for K-armed Bernoulli bandits over a finite horizon T, where the policy selects the arm maximizing (S_i + α)/(N_i + β). The main theoretical result, Theorem 2, decomposes finite-horizon regret into a linear absorption term T Σ δ_i P(Q_i) and a transient abandonment cost, and provides a two-sided envelope in a large-regularization asymptotic regime (Assumption 1). The key quantitative object is the asymptotic absorption probability eP(Q_i) of Theorem 4. Section 3 uses this expression to derive oracle, horizon-aware, and fully adaptive calibration rules for (α, β), and extensive numerical experiments report that the calibrated policies match or outperform Thompson Sampling, OGI, IDS, and other benchmarks. The pure-greedy case (α=β=0) is treated separately in Appendix H through an initial-success-set decomposition.

Significance. If the finite-gap calibration theory held as stated, this would be a valuable contribution: it would provide the first finite-horizon theoretical account of regularized greedy policies, an explicit trade-off between suboptimal absorption and transient exploration, and a computationally cheap alternative to state-of-the-art bandit algorithms. The paper's decomposition of regret into linear absorption regret plus transient abandonment cost is clean, and the appendix machinery (score-minimum reduction, Lundberg-root crossings, Stieltjes replacement) is structurally coherent. The authors also provide a code repository and use large replication counts (N=5,000) and statistically significant comparisons. However, the significance is currently conditional: the calibration rules and the headline empirical wins depend on transferring an asymptotic absorption formula to fixed-gap, moderate-regularization settings, and that transfer is neither proven nor convincingly validated at the level of the absorption probabilities themselves.

major comments (4)
  1. [§3.1, Eq. (3); Appendix E.2, Eq. (E.16)] The calibration objective Eq. (3) uses eP(Q_i) with the prefactor 1/m. The derivation in Eq. (E.16) yields the prefactor λ_i/(Σ_{h=1}^m λ_h), which is replaced by 1/m via the equal-λ approximation λ_h = λ_i(1+o(1)) under Assumption 1. At the fixed gaps and moderate regularization used in Section 3, this replacement is not justified and can be materially wrong: for K=2, β=0, p1=0.9, p2=0.5, the first-order prefactor is λ_2/(λ_1+λ_2) ≈ 0.265, not 1/2. Since Proposition 6 and the oracle/adaptive calibrations are derived from Eq. (3), the 'principled calibration' claim rests on this unverified equal-λ approximation. The authors should either prove a fixed-gap version of Theorem 4 with explicit error bounds, or directly validate eP(Q_i) against Monte Carlo absorption probabilities over the range of gaps and variances used in the experiments.
  2. [§2.4, §3.1, Theorems 2 and 4 / Assumption 1] Theorem 4 is proven only under Assumption 1, in which the regularization scale diverges and every nonzero gap satisfies p_i−p_j = Θ(Δ1^{−κ}) with T fixed. The calibration rules (Eqs. (2)–(3)) and all experiments use fixed arm means and fixed, moderate regularization levels. Section 2.4 provides only one random instance per panel (N=10,000 replications) and three hand-picked (α, β) pairs, and it concedes that the asymptotic upper envelope sometimes falls below the Monte Carlo curve. This is a load-bearing gap: without a theorem or a systematic numerical demonstration that Theorem 4 remains accurate at fixed gaps, Eqs. (2)–(3) have no stated validity in exactly the regime where calibration and experiments operate.
  3. [Theorem 2] The two-sided envelope in Theorem 2 is not tight in the regime where it is actually proven. Under Assumption 1, δ_i = Θ(Δ1^{−κ}) and eP(Q_i) decays exponentially in Δ1^{1−κ}, so R_linear(T) = o(1); the lower bound R_linear(1−o(1))−o(1) is therefore asymptotically zero (possibly negative), and the upper bound is dominated by R_transient = (K−1)Δ1, which for K=2, α=25 is 25 while the simulated regret is of order a few. The claimed tightness of the envelope is thus an empirical property of the finite-gap regime, not a consequence of the theorem. The text should clearly separate the provable asymptotic certificate from the asserted finite-gap accuracy.
  4. [Appendix H / Theorem 2, Part 2] The pure-greedy branchwise quantities are not fully closed-form: Appendix H explicitly keeps the multi-success branches 'in root-based or numerical form rather than replaced by the macroscopic asymptotic envelopes.' This undercuts the abstract's phrasing that the paper derives analytical finite-horizon regret expressions for the pure-greedy case. In addition, the theorem statement defines R^pg_linear and R^pg_linear with the same symbol, which is confusing. Please clarify whether the pure-greedy envelope is an analytically evaluated bound or an algorithmically evaluated numerical quantity, and correct the notation.
minor comments (4)
  1. [Theorem 2, Part 2] The two displayed definitions of R^pg_linear appear to be identical; one is presumably intended to be a lower envelope and the other an upper envelope, or they should be distinguished by different superscripts.
  2. [§3.2, Algorithms 3–4] The Fully Adaptive policy claims to require 'no knowledge of either the horizon or the arm means,' but it depends on a fixed coefficient φ=500 and on the backoff parameter ε_o=0.2 from §3.1. These are free parameters not derived from the theory. Please state this limitation explicitly and, ideally, report sensitivity to φ and ε_o.
  3. [§3.3.1, Tables 1–4] Confidence intervals are omitted from the tables although statistical significance at the 1% level is claimed. Reporting standard errors or confidence intervals for the mean regret comparisons would make the empirical claims easier to assess.
  4. [Abstract / §2.3] The phrase 'finite-horizon regret envelopes' suggests bounds valid for fixed T as T varies; the actual asymptotic is taken with respect to the regularization strength Δ1 → ∞ with T held fixed. The abstract and introduction should be more precise about this asymptotic direction.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the regret envelope and calibration rules are derived from a fresh boundary-crossing analysis, not from the outcomes they are used to predict; the regime-transfer caveat is a validity concern, not circularity.

full rationale

The paper's central derivation is self-contained. Theorem 4 (Appendix E) obtains the absorption probability P(Qi) from score-minimum reduction, Lundberg-root boundary-crossing estimates, and local Stieltjes replacement; no fitted constants enter, and the calibration objective in Eq. (3) is obtained by algebraically substituting Theorem 4's closed form into Eq. (2), not by fitting (alpha,beta) to the reported regret tables. The pure-greedy part (Appendix H) is also a separate branch decomposition, and the numerical benchmarks are external comparisons. The strongest caveat is the regime transfer: under Assumption 1 the lambda_h are all asymptotically equal, and the 1/m prefactor in Theorem 4 (via Appendix E.2, Eq. E.17) is an equal-lambda limit; applying the same formula at fixed gaps is an approximation whose support rests on Section 2.4's numerical checks ('we generate one random instance with arm means sampled independently from Uniform[0.01,0.99]' and 'In a few panels, the asymptotic upper envelope lies slightly below the Monte Carlo curve'). That is a possible correctness/robustness gap, not circularity: the predicted quantity is not an input to any derivation step, no parameter fitted to the experiments is renamed a prediction, and no load-bearing self-citation or imported uniqueness theorem is used to force the result. Thus the derivation chain is not circular.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The ledger is clean on the derivation side: eP(Qi) contains no fitted constants, and the calibration rule is derived, not optimized against test data. The cost is concentrated in two hand-set constants (epsilon_o = 0.2, phi = 500), an unproven regime-transfer premise (fixed gaps at finite Delta), and the narrowed pure-greedy claim. No new physical or model entities are introduced.

free parameters (2)
  • epsilon_o (backoff from boundary zeta = 1/p1) = 0.2
    Proposition 6 shows the optimal tilt is attained only at the inadmissible boundary zeta = 1/p1; practitioners set zeta = 1/p1 − epsilon_o with epsilon_o = 0.2 fixed by hand (Section 3.1: 'Throughout the numerical experiments, we set epsilon_o = 0.2'). No principled criterion is given.
  • phi (Fully Adaptive design-horizon coefficient) = 500
    The anytime design horizon bT_t = max(phi K, t/sqrt(log(e+t))) uses phi = 500, set by hand (Section 3.2, 3.3). For K = 2 this fixes the effective design horizon at 1000 for most of the tested range, which is in the middle of the tested T/K values — a choice that plausibly helps the algorithm.
assumptions (5)
  • domain assumption Assumption 1: coupled asymptotic regime — Delta_i = Theta(Delta_1), beta = O(Delta_1), and every nonzero gap p_i − p_j = Theta(Delta_1^{−kappa}) with kappa in (1/2,1), horizon T fixed
    The entire theorem is proven only under this coupled scaling (Section 2.3). The practical use assumes it transfers to fixed gaps at finite Delta, which is not proven. This is the paper's most fragile premise.
  • ad hoc to paper The asymptotic absorption formula of Theorem 4 is accurate at finite Delta with fixed gaps
    Never proven; supported by Section 2.4 numerics (one random instance per panel) and by the calibration use in Eq. (2)–(3). The authors concede the upper envelope sometimes falls below the MC curve in a few panels.
  • standard math Standard stochastic-process facts: Lundberg-root existence/uniqueness, optional stopping/Wald identities, Borel–Cantelli, law of the iterated logarithm, Hoeffding bounds
    Used throughout Appendices A–D (e.g., Lemma C.1, Corollary D.2). Standard, not controversial.
  • domain assumption Bernoulli rewards with p_i in [epsilon_p, 1−epsilon_p], epsilon_p in (0,1/2), K fixed, all arms pulled once at initialization
    Problem setup (Section 2.1). Standard modeling restriction that excludes degenerate gaps and boundary means; the theory does not cover K growing with T or rewards beyond Bernoulli.
  • ad hoc to paper In the pure-greedy case, the multi-success branches are 'kept in root-based or numerical form rather than replaced by the macroscopic asymptotic envelopes' (Appendix H)
    The abstract/conclusion claim 'sharper regret guarantees for the classical greedy policy' is narrower than stated: the pure-greedy result is an implicit Stieltjes/numerical characterization, not a closed-form bound.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Greedy Advantage in Finite-Horizon Bandits." pith.science (2026). https://pith.science/paper/QECTSSOG

@misc{pith2026260729375,
  author       = {Pith},
  title        = {Pith review of: The Greedy Advantage in Finite-Horizon Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QECTSSOG}},
  note         = {Machine review of arXiv:2607.29375}
}
read the original 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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

44 extracted references · 4 linked inside Pith

  1. [1]

    Bulletin of the American Mathematical Society , volume=

    Some aspects of the sequential design of experiments , author=. Bulletin of the American Mathematical Society , volume=

  2. [2]

    Advances in Applied Mathematics , volume=

    Asymptotically efficient adaptive allocation rules , author=. Advances in Applied Mathematics , volume=

  3. [3]

    Advances in Applied Probability , volume=

    Sample mean based index policies with O(log n) regret for the multi-armed bandit problem , author=. Advances in Applied Probability , volume=

  4. [4]

    Machine Learning , volume=

    Finite-time analysis of the multiarmed bandit problem , author=. Machine Learning , volume=

  5. [5]

    Conference on Learning Theory , pages=

    The KL-UCB algorithm for bounded stochastic bandits and beyond , author=. Conference on Learning Theory , pages=

  6. [6]

    Biometrika , volume=

    On the likelihood that one unknown probability exceeds another in view of the evidence of two samples , author=. Biometrika , volume=

  7. [7]

    Journal of the Royal Statistical Society: Series B , volume=

    Bandit processes and dynamic allocation indices , author=. Journal of the Royal Statistical Society: Series B , volume=

  8. [8]

    Foundations and Trends in Machine Learning , volume=

    A tutorial on Thompson sampling , author=. Foundations and Trends in Machine Learning , volume=

Show all 44 references
  1. [9]

    Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages=

    Contextual multi-armed bandits , author=. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics , pages=

  2. [10]

    Journal of Machine Learning Research , volume=

    Contextual bandits with similarity information , author=. Journal of Machine Learning Research , volume=

  3. [11]

    International Conference on Machine Learning , pages=

    Taming the monster: A fast and simple algorithm for contextual bandits , author=. International Conference on Machine Learning , pages=

  4. [12]

    2020 , publisher=

    Bandit Algorithms , author=. 2020 , publisher=

    2020

  5. [13]

    INFORMS Journal on Computing , volume=

    Computing a classic index for finite-horizon bandits , author=. INFORMS Journal on Computing , volume=

  6. [14]

    Conference on Learning Theory , pages=

    Regret analysis of the finite-horizon Gittins index strategy for multi-armed bandits , author=. Conference on Learning Theory , pages=

  7. [15]

    Advances in Neural Information Processing Systems , volume=

    On explore-then-commit strategies , author=. Advances in Neural Information Processing Systems , volume=

  8. [16]

    Management Science , volume=

    Simultaneously learning and optimizing using controlled variance pricing , author=. Management Science , volume=

  9. [17]

    Operations Research , volume=

    Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies , author=. Operations Research , volume=

  10. [18]

    Mathematics of Operations Research , volume=

    Chasing demand: Learning and earning in a changing environment , author=. Mathematics of Operations Research , volume=

  11. [19]

    Management Science , volume=

    Mostly exploration-free algorithms for contextual bandits , author=. Management Science , volume=

  12. [20]

    arXiv preprint arXiv:2503.04010 , year=

    Greedy algorithm for structured bandits: A sharp characterization of asymptotic success and failure , author=. arXiv preprint arXiv:2503.04010 , year=

  13. [21]

    Reinforcement Learning: An Introduction , author=

  14. [22]

    arXiv preprint arXiv:1506.03378 , year=

    On the prior sensitivity of Thompson sampling , author=. arXiv preprint arXiv:1506.03378 , year=

    arXiv

  15. [23]

    arXiv preprint arXiv:2603.11276 , year=

    RIE-Greedy: Regularization-induced exploration for contextual bandits , author=. arXiv preprint arXiv:2603.11276 , year=

    arXiv

  16. [24]

    Large Deviations Techniques and Applications , author=

  17. [25]

    Stochastic Simulation: Algorithms and Analysis , author=

  18. [26]

    2020 , type =

    Bayati, Mohsen and Hamidi, Nima and Johari, Ramesh and Khosravi, Khashayar , title =. 2020 , type =

    2020

  19. [27]

    arXiv preprint arXiv:2101.01086 , year =

    Jedor, Matthieu and Louëdec, Jonathan and Perchet, Vianney , title =. arXiv preprint arXiv:2101.01086 , year =

    arXiv

  20. [28]

    2009 , MONTH = Jun, HAL_ID =

    Audibert, Jean-Yves and Bubeck, S. 2009 , MONTH = Jun, HAL_ID =

    2009

  21. [29]

    Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , pages =

    On Bayesian Upper Confidence Bounds for Bandit Problems , author =. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics , pages =. 2012 , editor =

    2012

  22. [30]

    The Annals of Statistics , number =

    KULLBACK-LEIBLER UPPER CONFIDENCE BOUNDS FOR OPTIMAL SEQUENTIAL ALLOCATION , author =. The Annals of Statistics , number =

  23. [31]

    arXiv preprint arXiv:1402.6028 , year=

    Algorithms for multi-armed bandit problems , author=. arXiv preprint arXiv:1402.6028 , year=

    arXiv

  24. [32]

    The Annals of Statistics , volume=

    Batched Bandit Problems , author=. The Annals of Statistics , volume=

  25. [33]

    Proceedings of Thirty Fourth Conference on Learning Theory , series=

    Double Explore-then-Commit: Asymptotic Optimality and Beyond , author=. Proceedings of Thirty Fourth Conference on Learning Theory , series=. 2021 , publisher=

    2021

  26. [34]

    Management Science , volume=

    Multi-Armed Bandit Experimental Design: Online Decision-Making and Adaptive Inference , author=. Management Science , volume=

  27. [35]

    Operations Research , volume=

    The Fragility of Optimized Bandit Algorithms , author=. Operations Research , volume=

  28. [36]

    Management Science , volume=

    A Simple and Optimal Policy Design with Safety Against Heavy-Tailed Risk for Stochastic Bandits , author=. Management Science , volume=

  29. [37]

    Management Science , year=

    Collaborative Learning and Decision Making on Pricing and Recommendation: A Simple Framework for Planning , author=. Management Science , year=

  30. [38]

    Management Science , year=

    Speed Up the Cold-Start Learning in Two-Sided Bandits with Many Arms , author=. Management Science , year=

  31. [39]

    Operations Research , volume =

    Russo, Daniel , title =. Operations Research , volume =. 2020 , type =

    2020

  32. [40]

    Journal of the American Statistical Association , volume =

    Colton, Theodore , title =. Journal of the American Statistical Association , volume =. 1963 , type =

    1963

  33. [41]

    Advances in Neural Information Processing Systems , volume =

    Russo, Daniel and Van Roy, Benjamin , title =. Advances in Neural Information Processing Systems , volume =. 2014 , type =

    2014

  34. [42]

    , title =

    Min, Seungki and Maglaras, Costis and Moallemi, Ciamac C. , title =. Management Science , volume =. 2024 , type =

    2024

  35. [43]

    and Gutin, Eli , title =

    Farias, Vivek F. and Gutin, Eli , title =. Operations Research , volume =. 2022 , type =

    2022

  36. [44]

    IEEE Transactions on Automatic Control , volume=

    A Structured Multiarmed Bandit Problem and the Greedy Policy , author=. IEEE Transactions on Automatic Control , volume=. 2009 , doi=

    2009

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.