The Greedy Advantage in Finite-Horizon Bandits

Unknown

Conceptio › Archive › arXiv CS

arXiv CSopen access

The Greedy Advantage in Finite-Horizon Bandits

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

The Greedy Advantage in Finite-Horizon Bandits Kai Zhou Tsinghua University, [email protected]

Michael Lingzhi Li Harvard Business School, [email protected]

Kai Wang

arXiv:2607.29375v1 [stat.ML] 31 Jul 2026

Tsinghua University, [email protected]

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. Key words: multi-armed bandits, regularized greedy algorithms, regret guarantees

1. Introduction Organizations increasingly use sequential experimentation to improve decision-making. For example, pharmaceutical companies use adaptive trial designs to learn about treatment performance while patients are still being enrolled, and digital platforms test recommendations and interface designs by allocating user traffic adaptively. In all these settings, the dilemma is: each action generates information that can improve future decisions, but each action also affects current performance. Multi-armed bandits provide a natural mathematical model for this trade-off (Robbins, 1952). A decision-maker repeatedly selects among competing actions, observes stochastic rewards, and updates future choices based on the accumulated data. The classical bandit literature has long established that greedy policies can converge to suboptimal actions and incur regret that is linear 1

in T relative to an oracle (Lai and Robbins, 1985; den Boer and Zwart, 2014; Keskin and Zeevi, 2014; Bastani and Bayati, 2020). In response, the literature has developed a rich class of algorithms with strong asymptotic regret guarantees, including upper confidence bound policies (Agrawal, 1995; Auer et al., 2002; Garivier and Cappé, 2011), Thompson sampling (Thompson, 1933; Russo et al., 2018), and extensions to other settings (Slivkins, 2014; Agarwal et al., 2014). These policies aim to balance exploration and exploitation to achieve sublinear regret as the horizon T → ∞. However, the operational environments that motivate bandit algorithms often impose finite and externally imposed horizons. In online experimentation, the horizon may be determined by the duration of a product launch. In clinical trials, it is often bounded by operational constraints on trial length. In these settings, the relevant objective is to perform well within the finite window in which decisions actually matter. This observation changes the principle of algorithmic design. Greedy policies are asymptotically vulnerable because noise in the observed rewards can induce permanent commitment to a suboptimal arm, leading to linear regret that eventually dominates any policy with sublinear regret as T → ∞. Over a finite operational horizon, however, the relevant comparison is not determined by asymptotic rates alone. Exploration-based policies incur sampling costs throughout the horizon, while greedy-like policies incur large regret only on sample paths that lead to suboptimal convergence. The relative performance of these algorithms therefore depends on the probability and regret contribution of such suboptimal-convergence paths. The central question is whether this finite-horizon perspective can change the relative attractiveness of different policies. This paper answers the question in the affirmative. Many asymptotically optimal bandit algorithms aim to drive the probability of permanent convergence to a suboptimal arm to zero as T → ∞, thus achieving sublinear regret. We argue that this asymptotic objective does not necessarily lead to the best finite-horizon performance. Driving the probability of suboptimal convergence to zero requires continued exploration, and this exploration is itself costly within a finite horizon. Instead, we seek policies that explicitly balance the cost of continued exploration against the cost of occasional suboptimal convergence. The objective is no longer to eliminate suboptimal convergence asymptotically, but to make its probability sufficiently small that its finite-horizon contribution is outweighed by the exploration cost it avoids. This principle motivates a class of regularized greedy algorithms. Rather than relying on continued exploration to avoid suboptimal convergence, these algorithms retain the greedy rule while using regularization to reduce the probability of premature commitment. The regularization parameters determine how aggressively the algorithm abandons competing arms, and thus balance the transient cost of delayed abandonment against the probability of convergence to a suboptimal arm. We formalize the above argument in the context of multi-armed Bernoulli bandits. Bernoulli rewards capture operational experimentation settings in which actions generate binary outcomes, such as conversion or non-conversion, treatment response or non-response, and success or failure relative to a predefined operational target. In this setting, the regularized greedy algorithm pulls

each arm once and then repeatedly selects the arm with the largest regularized empirical mean, pbi (t) =

Si (t) + α , Ni (t) + β

i = 1, . . . , K,

where Si (t) and Ni (t) denote the cumulative successes and pulls of arm i at each time period t = 1, . . . , T , while (α, β) encode pseudo-successes and pseudo-trials. The pure greedy algorithm corresponds to α = β = 0. Positive regularization increases the amount of evidence required before an arm is abandoned, reducing the probability of premature suboptimal convergence while preserving the greedy structure of the policy. To quantify how regularization changes the trade-off between exploration and suboptimal convergence, we study the absorbing probabilities of the greedy dynamics. Let Qi denote the event that the algorithm permanently converges to arm i, and index the arms so that p1 ≥ p2 ≥ · · · ≥ pK . On Qi with i ≥ 2 and pi < p1 , the algorithm spends a finite transient period sampling the remaining arms before allocating asymptotically all future pulls to arm i, thereby incurring linear regret at rate δi = p1 − pi . Finite-horizon regret therefore decomposes into the linear component Rlinear = T

K X

δi P(Qi ),

i=2 pi <p1

together with finite transient abandonment costs Rtransient . Our main result derives analytical finite-horizon expressions for both regret components that characterize how regularization affects performance over a fixed decision horizon. The analysis considers a fixed horizon T while the regularization strength grows, yielding the envelope Rlinear (1 − o(1)) − o(1) ≤ R(T ) ≤ (Rlinear + Rtransient )(1 + o(1)), where the small-o terms are taken with respect to the regularization strength rather than the horizon. These expressions reveal that regularization affects the two terms in opposite directions. Increasing the regularization strength suppresses Rlinear exponentially by reducing the probability of suboptimal convergence, while increasing Rtransient by delaying abandonment. The finite-horizon design problem therefore reduces to choosing (α, β) to balance an exponentially decreasing suboptimalconvergence term against an increasing transient term. We then propose calibration rules for (α, β) under different levels of information, 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. Across extensive numerical experiments, calibrated regularized greedy policies consistently match or outperform state-of-the-art bandit algorithms, including Thompson Sampling (Thompson, 1933), OGI (Optimistic Gittins Indices; Farias and Gutin, 2022), and IDS (Information-Directed Sampling, Russo and Van Roy, 2014). These results demonstrate that appropriately calibrated greedy policies are competitive for finite-horizon bandit problems, combining ease of implementation with computational tractability.

1.1. Literature Review Classical multi-armed bandit work established asymptotic regret lower bounds and developed policies that attain sublinear regret, including upper confidence bound algorithms, Thompson sampling, and their many extensions (Robbins, 1952; Lai and Robbins, 1985; Agrawal, 1995; Auer et al., 2002; Garivier and Cappé, 2011; Thompson, 1933; Russo et al., 2018; Lattimore and Szepesvári, 2020). Most of this literature evaluates performance through asymptotic regret as the horizon grows large. A related line of work studies finite-horizon and limited-adaptivity settings through Bayesian dynamic programming, Gittins-index methods, explore-then-commit policies, batched bandits, and experimental designs that balance online performance against other objectives such as inference or tail risk (Gittins, 1979; Niño-Mora, 2011; Russo and Van Roy, 2014; Garivier et al., 2016; Perchet et al., 2016; Jin et al., 2021; Farias and Gutin, 2022; Simchi-Levi and Wang, 2025; Simchi-Levi et al., 2025; Fan and Glynn, 2025). This literature recognizes that exploration is itself costly over finite horizons. Our analysis focuses on a different way of controlling this tradeoff. The policy remains greedy with respect to a regularized estimator, so exploration is not imposed through confidence bounds, randomization, or prescribed exploration phases. Instead, regularization changes the learning dynamics by reducing the probability of suboptimal absorption while increasing the transient cost of abandoning competing arms. Our work is particularly related to the literature on greedy bandits. Pure greedy policies eliminate exploration costs but are vulnerable to permanent commitment to a suboptimal arm. In dynamic pricing settings, den Boer and Zwart (2014) and Keskin and Zeevi (2014, 2017) showed that greedy learning can converge to suboptimal decisions with positive probability and therefore incur linear regret. In bandits with correlated arm rewards, Mersereau et al. (2009) showed that greedy policies can exploit cross-arm learning to achieve logarithmic cumulative Bayes risk. In contextual settings, Bastani and Bayati (2020) identified conditions under which greedy learning remains asymptotically optimal, while Slivkins et al. (2025) characterized broader conditions governing the success and failure of greedy algorithms. Recent work has also emphasized that greedy or neargreedy policies can be effective when structural features of the environment generate sufficient learning or reduce the cost of initial exploration (Cao, 2025; Bayati et al., 2026). These papers identify costly exploration and suboptimal convergence as central issues in sequential learning. We complement this literature by explicitly characterizing the absorbing probabilities of suboptimal arms and studying how regularization suppresses their aggregate regret contribution. The regularized greedy policies studied in this paper select actions according to the estimator (Si + α)/(Ni + β). Estimators of this form have appeared in prior work through optimistic initialization heuristics, pseudo-observations, and posterior means under Beta priors (Gittins, 1979; Liu and Li, 2015; Sutton and Barto, 2018). Existing work, however, primarily employs these estimators as algorithmic or Bayesian modeling devices rather than analyzing their finite-horizon behavior. 1.2. Our Contributions Overall, this paper makes two major contributions.

First, the paper develops a finite-horizon theory for regularized greedy K-armed Bernoulli bandits (Section 2). Motivated by the trade-off between continued exploration and occasional suboptimal convergence, we characterize finite-horizon regret with two components: a linear term arising from convergence to a suboptimal arm and a transient term arising from delayed abandonment. To the best of our knowledge, this is the first finite-horizon theory for regularized greedy bandits. The analysis develops new tools combining absorption analysis, score-minimum reductions, boundarycrossing arguments for drifted random walks, Lundberg-root change-of-measure estimates, and local Stieltjes replacement arguments to characterize the probability of convergence to each suboptimal arm. This yields regret envelopes, explicit calibration rules for the regularization parameters, and, as a limiting case, sharper regret guarantees for the classical greedy algorithm. The analytical tools may also be useful for studying other finite-horizon sequential learning problems. Second, the paper demonstrates that the proposed algorithms perform strongly across a broad range of finite-horizon settings (Section 3). We derive calibration procedures for (α, β) under varying levels of problem information, ranging from oracle settings to fully adaptive ones requiring no knowledge of either the horizon or the arm means. Extensive numerical experiments show that calibrated regularized greedy policies consistently match or outperform modern state-of-the-art bandit algorithms, including Thompson sampling, OGI, and IDS, across a wide range of instances and horizons. In all, these results establish regularized greedy as an efficient, practical and theoretically grounded approach to finite-horizon implementations. Section 4 concludes the paper, and the electronic companion provides all proofs.

2. Bounding Regret for Bernoulli Bandits 2.1. Problem Setup We consider a K-armed Bernoulli bandit over a finite horizon T , where K ≥ 2 is fixed and T ≥ K. The arms have unknown success probabilities pi ∈ [ϵp , 1 − ϵp ] for some fixed ϵp ∈ (0, 1/2), indexed without loss of generality so that p1 ≥ p2 ≥ · · · ≥ pK and p1 > pK . Conditional on selecting arm i ∈ {1, . . . , K}, the decision-maker observes a binary reward at each time period t = 1, . . . , T : Xt ∼ Bernoulli(pi ). Bernoulli bandits arise naturally in a range of operational settings involving sequential allocation with binary feedback. In healthcare operations, a hospital system may sequentially allocate patients across treatment protocols and observe binary clinical outcomes such as recovery or deterioration. In facility deployment problems, an organization may open facilities sequentially and observe binary indicators of operational success, such as whether a facility achieves a target utilization threshold. In online experimentation and recommendation systems, the decision-maker allocates traffic across alternatives and observes binary engagement outcomes such as clicks or purchases. In all such settings, the decision-maker repeatedly allocates resources under uncertainty and updates future decisions using binary feedback from prior allocations.

At each time period t = 1, . . . , T , the decision-maker selects an arm At ∈ {1, . . . , K} using a policy based on the available history and then observes a reward Xt ∼ Bernoulli(pAt ) independently across time, conditional on the selected actions. We define the action and reward histories through time t as A1:t = (A1 , . . . , At ),

X1:t = (X1 , . . . , Xt ),

and let Ht = (A1:t , X1:t ) denote the information available after period t. A valid, possibly randomized, policy is therefore a sequence of history-dependent decision rules ( πt : Ht−1 → SK ,

SK :=

u ∈ [0, 1]K :

K X

) ui = 1 ,

i=1

and πt,i (Ht−1 ) denotes the probability of selecting arm i at time t conditional on the history Ht−1 . The decision-maker seeks a policy minimizing cumulative regret over the finite horizon T . For each arm i = 1, . . . , K, define Ni (t) =

t X

1{As = i},

Si (t) =

s=1

t X

Xs 1{As = i},

s=1

as the cumulative number of pulls and cumulative number of successes through time t, respectively. Since arms are indexed so that p1 ≥ p2 ≥ · · · ≥ pK , define the regret gaps δi := p1 − pi ≥ 0 for i = 1, · · · , K, so that δ1 = 0. The cumulative expected regret of policy π over horizon T is Rπ (T ) = Eπ

" T X

# (p1 − pAt ) =

t=1

K X

δi Eπ [Ni (T )],

i=2

where Eπ [·] denotes expectation taken with respect to the probability measure induced by policy π and the Bernoulli reward realizations. 2.2. Regularized Greedy Policies We study a class Π of regularized greedy policies. Each policy πα,β ∈ Π is indexed by two parameters (α, β). After an initialization step, policy πα,β assigns each arm i = 1, . . . , K the score pbi (t) =

Si (t) + α , Ni (t) + β

and selects an arm with maximal score, breaking ties uniformly at random. Algorithm 1 gives the full policy specification. The classical greedy policy corresponds to α = β = 0. The parameters (α, β) regularize the empirical comparison that determines which arms remain competitive. When β > 0 and Ni (t) > 0, the score can be written as pbi (t) =

Ni (t) Si (t) β α · + · , Ni (t) + β Ni (t) Ni (t) + β β

i = 1, . . . , K.

Thus the regularized score is a weighted average of the empirical mean and the baseline value α/β, with weight on the baseline decreasing as arm i is sampled. The ratio α/β determines the level toward which the score is initially pulled, while β determines how quickly the regularization vanishes. Along any history in which an arm continues to be sampled, the regularization effect disappears asymptotically and the score converges to the empirical mean. The next section characterizes how the choice of (α, β) affects finite-horizon regret through the transient exploration cost and the probability of eventual convergence to a suboptimal arm. Algorithm 1 Regularized Greedy Policy 1: Input: Horizon T , number of arms K, regularization parameters (α, β). 2: Initialize: Pull each arm once during periods t = 1, . . . , K. Observe rewards X1 , . . . , XK , set At = t

for t = 1, . . . , K, and initialize Ni (K) = 1,

Si (K) = Xi ,

i = 1, . . . , K.

Si (t − 1) + α , Ni (t − 1) + β

i = 1, . . . , K.

3: for t = K + 1, . . . , T do 4:

Compute the regularized estimates pbi (t − 1) =

Let Gt := arg max pbi (t − 1) 1≤i≤K

be the set of current score maximizers. 6:

Select At uniformly at random from Gt .

Observe Xt ∼ Bernoulli(pAt ).

Update Ni (t) = Ni (t − 1) + 1{At = i},

Si (t) = Si (t − 1) + Xt 1{At = i},

i = 1, . . . , K.

9: end for

Throughout the analysis, we impose the feasibility condition α ≥ 0,

β ≥ 0,

α ≥ p1 β.

The pure-greedy policy corresponds to α = β = 0. 2.3. A Closed-Form Two-Sided Regret Envelope We now derive our main analytical characterization of the regret Rπα,β (T ). For convenience, define ∆i := α − pi β,

σi2 := pi (1 − pi ),

λi :=

2∆i , σi2

i = 1, . . . , K.

For 1 ≤ i < j ≤ K, let δij := pi − pj , and recall that δi = δ1i = p1 − pi denotes the regret gap of arm i. The quantity ∆i represents the effective regularization margin of arm i, while λi is the corresponding regularization-adjusted rate parameter that appears in the absorbing-probability characterization below. The regret decomposition developed in this paper consists of two components: a linear term Rlinear , which scales with T and captures regret from convergence to a suboptimal arm, and a transient term Rtransient , which is independent of T and captures the regret incurred during learning. Although this decomposition holds without additional assumptions, obtaining explicit expressions for the two components is challenging because of the discrete Bernoulli observations and the nonlinear regularization induced by (α, β). We therefore study a large-regularization asymptotic regime in which the horizon remains fixed while the regularization scale grows. Unlike the classical asymptotic regime with T → ∞, this regime preserves both regret components and permits explicit characterization of the score-minimum and boundary-crossing probabilities. Throughout the remainder of the paper, we consider the following asymptotic regime. Assumption 1 (Asymptotic regime). As ∆1 → ∞, the regularization scale satisfies ∆i = Θ(∆1 ),

β = O(∆1 ),

i = 1, . . . , K.

Moreover, for a common κ ∈ (1/2, 1), every nonzero pairwise gap satisfies pi − pj = Θ(∆−κ 1 ),

1 ≤ i < j ≤ K such that pi > pj .

The asymptotics are taken with respect to the regularization scale ∆1 , while the horizon T remains fixed throughout the analysis. The conditions ∆i = Θ(∆1 ) and β = O(∆1 ) ensure that the regularized scores of all arms grow on the same asymptotic scale. The assumption pi − pj = Θ(∆−κ 1 ) specifies how distinct arm means evolve as the regularization increases. This scaling ensures that both the transient component and the linear component of the regret admit explicit asymptotic characterizations within the same asymptotic regime. Consequently, the resulting asymptotic analysis yields explicit regret expressions while retaining the finite-horizon regret decomposition. Section 2.4 further demonstrates that the resulting regret envelopes remain accurate well beyond the asymptotic regime, including the moderate regularization levels used in our numerical experiments. Given this asymptotic regime, we now present the principal result of the paper. Theorem 2 characterizes the finite-horizon regret of the regularized policies with α > 0 through upper and lower envelopes, and then derives the corresponding finite-horizon regret characterization for the classical greedy policy. The proof roadmap of the theorem will be discussed in Section 2.5. Theorem 2 (Two-sided finite-horizon regret envelope). Consider a K-armed Bernoulli bandit with success probabilities satisfying 1 − ϵp ≥ p1 ≥ p2 ≥ · · · ≥ pK ≥ ϵp and p1 > pK . Let πα,β denote the

regularized greedy policy with parameters (α, β). 1. Regularized greedy algorithm (α > 0). Suppose α ≥ p1 β ≥ 0 and Assumption 1 holds. For i = 2, . . . , K with pi < p1 , define the closed-form approximation to the absorption probability of suboptimal arm i by

e i ) := P(Q

K X 1 m=i

( exp −

m X

(

1 − exp −

λh δhm

h=1

m X

! λh

δm,m+1

h=1

where δhh := 0, δK,K+1 := ∞, and the second exponential in the bracket is interpreted as zero when m = K. Define

Rlinear (T ) := T

K X

e i ), δi P(Q

Rtransient := C∆ := (K − 1)∆1 .

i=2 pi <p1

Then, for every finite horizon T , Rlinear (T )(1 − o(1)) − o(1) ≤ Rπα,β (T ) ≤ (Rlinear (T ) + Rtransient )(1 + o(1)). 2. Pure greedy algorithm (α = β = 0). For the classical greedy policy, define K X

Rpg linear (T ) := T

pg Rlinear (T ) := T

δi Ppg (Qi ),

i=2 pi <p1

K X

δi Ppg (Qi ),

i=2 pi <p1

and Rpg transient (T ) :=

K X X

K X X pg pg (pi − pj )U j|i,T . Rtransient (T ) := i=1 j̸=i pj <pi

pg (pj − pi )U j|i,T ,

i=1 j̸=i pj >pi

Then pg

pg Rpg linear (T ) − Rtransient (T ) ≤ Rπ0,0 (T ) ≤ Rlinear (T ) + Rtransient (T ), pg

where Ppg (Qi ), Ppg (Qi ), and U j|i,T are the explicit branchwise quantities defined in Appendix H. Theorem 2 establishes upper and lower bounds for the finite-horizon regret of the regularized greedy policy. The regret is decomposed into two explicit terms. The first,

Rlinear (T ) = T

K X

e i ), δi P(Q

i=2 pi <p1

is the regret contributed by eventual convergence to suboptimal arms. The second, Rtransient , is the

finite cost incurred before the remaining arms are abandoned. e i ). Each term is a The role of regularization is visible directly from the expression for P(Q weighted sum of exponentials whose exponent is proportional to the rate parameters λi = 2∆i /σi2 . Increasing the regularization margin therefore increases λi linearly, causing the probabilities of suboptimal convergence to decay exponentially. At the same time, larger regularization delays abandonment and increases Rtransient . The theorem therefore quantifies the finite-horizon trade-off between an exponentially decreasing linear-regret component and an increasing transient component through upper and lower bounds. The theorem also gives the corresponding finite-horizon regret characterization for the classical greedy policy. The remainder of this section first demonstrates that the first-order regret envelopes accurately characterize finite-horizon regret through numerical experiments. We then outline the main ideas of the proof of the theorem, with its complete technical arguments deferred to the online appendix. Section 3 then uses the regret decomposition to derive calibration rules for (α, β) that balance the linear and transient regret components. 2.4. Empirical Tightness of the Regret Envelope To illustrate the performance of these bounds, we examine the finite-horizon accuracy of the regret envelope in Theorem 2 for representative K-armed Bernoulli bandits. For each displayed value of K, we generate one random instance with arm means sampled independently from Uniform[0.01, 0.99]. Every Monte Carlo curve is averaged over N = 10,000 replications, and the horizon is T = 5,000. Since the policy first pulls each arm once, all figures display only the region T ≥ K. Regularized greedy. Figure 1 compares the regret envelope of Theorem 2 with realized regret under three representative regularization choices. The left column considers the two-arm case (K = 2), and the right column considers the ten-arm case (K = 10). The first two rows vary α with β = 0, while the final row considers balanced regularization with α = β. Across all six configurations, the regret envelope closely matches the realized regret. The agreement remains strong even for moderate regularization levels and randomly generated arm means, suggesting that the asymptotic approximation remains accurate well beyond the asymptotic regime of Theorem 2. In a few panels, the asymptotic upper envelope lies slightly below the Monte Carlo curve; this small discrepancy reflects finite-regularization effects from the omitted o(1) remainders. Although the regret appears to plateau over the displayed horizon, it is not constant. Theorem 2 shows that the regret remains asymptotically linear in T for any fixed regularization parameters. The apparent saturation arises because the linear coefficient is exponentially small in the regularization level, so over practical horizons the linear growth is dominated by the transient term. Increasing the regularization further reduces this coefficient by suppressing the probability of permanent commitment to suboptimal arms, causing the realized regret to appear nearly flat even though its asymptotic growth remains linear. Pure greedy. We next consider the special case α = β = 0. This regime permits a direct comparison with the existing analytical literature because several regret characterizations are available for the

Figure 1

(a) K = 2, (α, β) = (10, 0)

(b) K = 10, (α, β) = (10, 0)

(d) K = 10, (α, β) = (25, 0)

(e) K = 2, (α, β) = (25, 25)

(f ) K = 10, (α, β) = (25, 25)

Finite-horizon accuracy of the regularized-greedy regret envelope in Theorem 2. Each panel

compares Monte Carlo (MC) regret, the analytical two-sided envelope, and the pure-greedy reference for the displayed K and (α, β).

classical greedy policy. We compare Part 2 of Theorem 2 with the upper bound of Jedor et al. (2021), the singleton-failure lower benchmark motivated by their greedy failure example, and the Bayesian greedy formula of Bayati et al. (2020). We note that the analysis of Bayati et al. (2020) is derived under a many-arm asymptotic requiring K ≥ 30 log T /c0 (e.g., K ≥ 256 when T = 5,000 and c0 = 1), whereas our experiments consider substantially smaller values of K. We therefore include their result as an analytical point of reference rather than a benchmark. Figure 2 reports the comparison for K ∈ {2, 5, 8, 10}. Across all configurations, the branchwise characterization of Theorem 2 yields substantially tighter regret bounds than the existing analytical benchmarks. The upper envelope closely tracks the realized regret, while the lower envelope substantially improves upon the previously available analytical lower benchmark. Figures 1 and 2 together show that the regret envelopes of Theorem 2 remain accurate across

a broad range of regularization strengths and numbers of arms. In the regularized regime, the envelopes accurately characterize both the magnitude of finite-horizon regret and the effect of regularization. In the pure-greedy regime, the same analytical framework yields substantially sharper regret bounds than the existing literature.

Figure 2

(a) K = 2

(b) K = 5

(d) K = 10

Pure-greedy regret envelope from Part 2 of Theorem 2. Each panel compares MC regret, our

branchwise envelope, and existing analytical benchmarks for the displayed K.

We next outline the proof of Theorem 2. The analysis proceeds by characterizing the probabilities of absorption into each arm together with the transient regret accumulated before the remaining arms are abandoned. It shows how the finite-horizon regret decomposition reduces to these two quantities. 2.5. Proof Roadmap: Reduction to Absorbing Probabilities and Conditional Abandonment Costs We recall that the regret of the regularized greedy policy can be written as

R(T ) =

K X

δi E[Ni (T )].

i=2

The proof begins by separating the pulls of suboptimal arms into two sources. The first source is suboptimal absorption. If the policy eventually commits to a suboptimal arm, it incurs regret at rate δi for the remainder of the horizon. The second source is transient sampling: arms that are eventually abandoned may still be pulled a finite number of times before leaving the competition. Our first step is to show that the greedy trajectory almost surely absorbs into a single arm

(Lemma A.1). For each arm i, define Qi := {∃ Te < ∞ such that At = i for all t ≥ Te},

i = 1, . . . , K,

where Te denotes the (path-dependent) absorption time. The events Q1 , . . . , QK form an almostsure partition of the sample space. Conditional on Qi , define the capped transient pulls of arm j ̸= i by Uj|i,T := E[min{T, Nj } | Qi ] , where Nj is the total number of pulls of arm j over the infinite trajectory. Terms conditioned on probability-zero events are interpreted as zero. Conditioning on the absorbing partition yields the regret sandwich

K X

δi P(Qi ) −

i=2 pi <p1

K X

P(Qi )

i=1

(pj − pi ) Uj|i,T

j̸=i pj >pi

(1)

≤R(T ) ≤T

K X

δi P(Qi ) +

i=2 pi <p1

K X

P(Qi )

i=1

(pi − pj ) Uj|i,T .

j̸=i pj <pi

The leading term is the linear absorption regret, K X

Rlinear (T ) = T

δi P(Qi ),

i=2 pi <p1

while the remaining terms capture the transient abandonment cost. The remainder of the proof thus reduces to two tasks: characterizing the absorbing probabilities P(Qi ) and bounding the conditional abandonment costs Uj|i,T . Section 2.5.1 provides the main ingredients in our characterization of P(Qi ), and Section 2.5.2 establishes the corresponding conditional abandonment costs Uj|i,T . 2.5.1. Absorbing Probabilities: Score Minima and Exponential Evaluation. We first characterize the absorbing probabilities P(Qi ) that determine the linear regret component Rlinear (T ). While absorption is defined through the entire adaptive trajectory of the greedy policy, it admits an equivalent characterization through the minimum regularized score attained by each arm. This reduction converts the adaptive multi-arm process into a collection of independent one-arm objects, which can then be analyzed explicitly. For each arm i, let Si (n) denote the cumulative successes along an independent potential reward stream after n pulls, and define Mi := inf

n≥1

Si (n) + α , n+β

Li := pi − Mi .

14 Theorem 2 Two-sided regret envelope

Absorbing probabilities P(Qi )

Conditional abandonment costs Uj|i,T

Pure-greedy branch decomposition Appendix H

Absorption and score-minimum reduction Appendices A–B

Lundberg-root crossing estimates Appendices C–D

Conditional abandonment analysis Appendix F

Figure 3

Dependency structure of the proof of Theorem 2. Arrows read “provides input to”. The regu-

larized proof combines the absorbing-probability analysis with conditional abandonment-cost bounds. The pure-greedy part is handled separately through the initialization-branch decomposition.

Here Mi is the minimum regularized score attained by arm i, while Li is the corresponding drawdown below the arm mean. For each x ∈ (0, pi ), define the associated one-arm boundary bi (x) := α − (pi − x)β = ∆i + βx. The following theorem shows that these score minima determine the absorbing events and characterizes their tail probabilities. Theorem 3 (Score-minimum reduction and one-arm tail envelope). For every i = 1, . . . , K, the absorbing event Qi satisfies {Lj > Li + pj − pi , ∀j ̸= i} ⊆ Qi ⊆ {Lj ≥ Li + pj − pi , ∀j ̸= i} . Moreover, for every x ∈ (0, pi ), the strict and weak one-arm tails satisfy exp −θi (x) bi (x) + pi − x ≤ P(Li > x) ≤ P(Li ≥ x) ≤ exp {−θi (x)bi (x)} , where θi (x) > 0 is the unique positive Lundberg root satisfying (1 − pi ) exp{θi (x)(pi − x)} + pi exp{−θi (x)(1 − pi + x)} = 1. The proof of Theorem 3 is given in Appendices B–D. The theorem consists of two steps. The first reduces the adaptive absorbing event to a comparison of the independent score minima L1 , . . . , LK , eliminating the need to analyze the full greedy trajectory directly. The second characterizes the distribution of each score minimum through a one-arm boundary-crossing problem. Specifically, the event {Li > x} is equivalent to a Bernoulli random walk crossing the boundary bi (x), whose probability is governed by the Lundberg exponent θi (x). To illustrate the main idea, we give an informal derivation of the absorbing-probability formula; the rigorous approximation arguments are deferred to the appendix. Under the large-regularization

regime, the relevant score minima lie near the lower endpoint x = 0. As x ↓ 0, θi (x) =

2 x + O(x2 ), pi (1 − pi )

bi (x) = ∆i + βx,

so θi (x)bi (x) = λi x + O(∆i x2 + βx2 ),

λi :=

2∆i . pi (1 − pi )

Consequently, P(Li > x) = exp{−λi x}[1 + o(1)], so each score minimum is locally exponential with rate λi . Larger regularization margins therefore make large score drawdowns exponentially less likely. For arm i to absorb, its score minimum must be sufficiently small, while the score minima of the competing arms must exceed the shifted levels Li + pj − pi . Conditioning on Li = ℓ therefore gives the Stieltjes representation Z P(Qi ) ≈

P(Lj ≥ ℓ + pj − pi ) dFi (ℓ),

[0,pi ) j̸=i

where Fi denotes the distribution of Li . Under large regularization, the integral is concentrated on ℓ = O(∆−1 i ), allowing the local exponential approximation above to be substituted into the integrand. This reduces the absorbing probability to the reference integral Z ∞ λi 0

    X exp −λi ℓ − λj (ℓ + pj − pi )+ dℓ.   j̸=i

The positive-part terms partition the integral according to the ordered gaps δij . For j < i, the shift is always nonnegative and contributes the constant factor exp{−λj δji }. For j > i, the term (ℓ − δij )+ becomes active only after ℓ crosses the ordered gap δij . Evaluating the integral over these successive regions yields the following asymptotic absorbing-probability formula. Theorem 4 (Asymptotic absorbing-probability formula). Suppose Assumption 1 holds. For every suboptimal arm i = 2, . . . , K with pi < p1 , P(Qi ) =

K X 1 m=i

( exp −

m X

)" λh δhm

(

1 − exp −

h=1

m X

! λh

)# δm,m+1

(1 + o(1)),

h=1

where empty sums are interpreted as zero, δhh := 0, and δK,K+1 := ∞. For m = K, the second exponential in the bracket is interpreted as zero. The proof is given in Appendix E. Substituting these absorbing probabilities into the decompo-

sition of Section 2.5 yields the linear regret contribution

Rlinear (T ) = T

K X

e i ), δi P(Q

i=2 pi <p1

e i ) denotes the asymptotic expression in Theorem 4. The remaining task is therefore where P(Q to characterize the transient abandonment cost, which determines the second component of the finite-horizon regret envelope. 2.5.2. Conditional Abandonment Costs and Regret Synthesis. It remains to characterize the transient abandonment cost appearing in the regret decomposition of Section 2.5. Conditional on the absorbing event Qi , the absorbing arm determines the score level that every remaining arm must eventually cross before it is abandoned. Once the absorbing arm is fixed, the evolution of each nonabsorbing arm thus decouples and reduces to a collection of one-arm first-passage problems. Relative to the realized score minimum of the absorbing arm, the comparison walk for arm j has drift pi − pj − ℓ, where ℓ denotes the realized centered score minimum of the absorbing arm. When pi > pj , this drift changes sign at ℓ = δij , separating the analysis into positive- and negative-drift regimes. When pj > pi , the drift remains negative throughout. When pi = pj , the finite-horizon cap directly gives Uj|i,T ≤ T . Applying the one-arm boundary-crossing analysis to these two regimes yields the following conditional abandonment bounds. Theorem 5 (Conditional abandonment envelope). Under Assumption 1, for every i ̸= j,  P(Qj ) ∆i κ−1   1 + O(∆1 ) + T o ,   δij P(Qi )      Uj|i,T ≤ T,        ∆   i (1 + o(1)) + T o(1), δji

pi > pj , pi = pj , pi < pj .

Moreover, on the optimal branches Qi , i ∈ [K] with pi = p1 , K X i=1 pi =p1

P(Qi )

(pi − pj )Uj|i,T ≤ C∆ (1 + o(1)) + Rlinear (T )o(1)

j̸=i pj <pi

The proof of Theorem 5 appears in Appendix F. There we integrate the pointwise first-passage bounds against the conditional distribution of the absorbing score minimum. The same endpoint localization used in the absorbing-probability analysis shows that only the lower-endpoint behavior

of the absorbing score minimum contributes at first order, which yields the explicit conditional abandonment bounds in the theorem. We treat the optimal branches Qi with pi = p1 separately because they contribute to the transient term at first order. With both the absorbing probabilities and conditional abandonment costs characterized, only the synthesis step remains. Appendix G combines Theorems 4 and 5 to establish our main result (Theorem 2). The absorbing probabilities determine the linear regret component Rlinear (T ), while the conditional abandonment bounds determine the transient component Rtransient . The same regret decomposition also yields the pure-greedy result. Its analysis follows the same structure but requires a different initialization-branch decomposition, and is deferred to Appendix H.

3. Horizon-Calibrated Greedy Policies Theorem 2 characterizes the finite-horizon regret of regularized greedy as a function of the prior (α, β). The natural question is how the prior should be chosen. The regret bound shows that increasing the prior reduces suboptimal absorption but increases transient regret, so the prior is selected by optimizing this finite-horizon trade-off. We first study an oracle setting in which the horizon and arm means are known. The resulting oracle policy serves as a benchmark and motivates the practical algorithms developed later for settings in which these quantities are unknown. 3.1. Oracle Calibration Suppose the horizon T and the arm means p1 ≥ · · · ≥ pK are known. We calibrate the regularization parameters by minimizing the leading-order regret envelope of Theorem 2. Dropping the o(1) remainder, define R(T ; α, β) = T

K X

e i ) + (K − 1)∆1 , δi P(Q

(2)

i=2 pi <p1

e i ) denotes the asymptotic absorbing probability in Theorem 2. The first where δi = p1 − pi and P(Q term is the linear regret contribution, while the second is the transient abandonment cost. Write β = ζα, where 0 ≤ ζ < 1/p1 . Under this parameterization, the implied baseline value is 1/ζ. For m = 2, . . . , K, define ϱm (ζ) =

m X 2(1 − ph ζ) h=1

ph (1 − ph )

Pm (ph − pm ),

γm =

i=2,pi <p1 (p1 − pi )

Pm−1 −

i=2,pi <p1 (p1 − pi )

m−1

where the second sum is interpreted as zero when m = 2. Substituting the asymptotic absorbing probabilities into (2) gives

R(T ; α, ζ) = T

K X m=2

γm exp{−αϱm (ζ)} + (K − 1)α(1 − p1 ζ).

(3)

The following proposition characterizes the optimal calibration. Proposition 6 (Horizon calibration with known gaps). Consider min

R(T ; α, ζ).

α≥0, 0≤ζ<1/p1

For each fixed 0 ≤ ζ < 1/p1 , define T0 (ζ) := (K − 1)(1 − p1 ζ)/

m=2,pm <p1 γm ϱm (ζ) and ϱmin (ζ) :=

min2≤m≤K,pm <p1 ϱm (ζ). The optimizer over α ≥ 0 is   0,    ⋆ α (T, ζ) = the unique positive solution of     PK γ ϱ (ζ) exp{−αϱ (ζ)} = (K−1)(1−p1 ζ) , m m=2 m m T

T ≤ T0 (ζ),

T > T0 (ζ).

The optimization over ζ attains its infimum at the upper boundary: inf

min R(T ; α, ζ) = lim min R(T ; α, ζ). ζ↑1/p1 α≥0

0≤ζ<1/p1 α≥0

Moreover, for every fixed 0 ≤ ζ < 1/p1 and every T > T0 (ζ), (K − 1)(1 − p1 ζ) T R(T ; α (T, ζ), ζ) ≤ 1 + log . ϱmin (ζ) T0 (ζ) ⋆

The proof is given in Appendix I. Proposition 6 completely characterizes the oracle regularization. When T ≤ T0 (ζ), regularization cannot improve the regret upper bound, so the optimizer is the classical greedy policy with α = 0. When T > T0 (ζ), the optimal regularization is the unique solution of the scalar equation in Proposition 6, balancing the exponentially decreasing absorption term against the increasing transient cost. The proposition also shows that the optimal tilt satisfies ζ ⋆ (T ) ↑ 1/p1 . Since ζ = 1/p1 lies outside the admissible region of our asymptotic analysis, we instead use ζϵ◦ =

1 − ϵ◦ , p1

where ϵ◦ > 0 is fixed. Throughout the numerical experiments, we set ϵ◦ = 0.2. The resulting oracle calibration is αϵ⋆◦ (T ) ∈ arg min R(T ; α, ζϵ◦ ), α≥0

βϵ⋆◦ (T ) = ζϵ◦ αϵ⋆◦ (T ).

(4)

Algorithm 2 summarizes the resulting oracle policy. Throughout this section, let (α, β) = Cal(T, pb) denote the calibrated pair obtained from Proposition 6 using design horizon T and ordered design vector pb. When all components of pb are equal, we set Cal(T, pb) = (0, 0). In this case, γm = 0 for every m = 2, . . . , K, so the objective in (3) is strictly increasing in α for every feasible ζ and is minimized at zero regularization.

Finally, Proposition 6 implies that, for every fixed problem instance and every fixed backoff ϵ◦ > 0, recalibrating to the design horizon T yields an upper bound of order

T 1 + log T0 (ζϵ◦ )

for the regret certificate (2). Thus, the oracle calibration increases only logarithmically with the horizon under the finite-horizon regret envelope. Algorithm 2 Oracle 1: Input: mean multiset {p1 , . . . , pK }; horizon T . 2: Sort the mean values in decreasing order to obtain p̃. 3: Set (α, β) = Cal(T, p̃). 4: Pull each arm once. 5: for t = K + 1, . . . , T do 6:

Pull At ∈ arg maxi (Si + α)/(Ni + β).

Observe Xt and update SAt and NAt .

8: end for

3.2. Operationalizing the Calibration The oracle policy assumes that the arm means are known. In most real-world settings, however, they are unknown and must be estimated online. We therefore replace the unknown means by online estimates while retaining the calibration rule from the previous subsection. We consider two settings depending on whether the horizon T is known. Horizon-Aware. Suppose the horizon T is known but the arm means are not. We replace the unknown means by the Jeffreys-smoothed estimates p̃i (t) =

Si (t) + 1/2 , Ni (t) + 1

sort them to obtain the design vector p̃(t), and calibrate (α, β) using the true horizon T . Following the standard doubling technique, the calibration is recomputed only when maxi Ni (t) has doubled since the previous recalibration. Between recalibrations, the same pair (α, β) is used. Fully Adaptive. Suppose neither the horizon nor the arm means are known. We estimate the arm means as in the horizon-aware policy. To remove the dependence on the unknown horizon, we follow a standard anytime-style construction from the bandit literature and replace T by the growing design horizon mo n lp Tbt = max φK, t log(e + t) , where φ is a fixed coefficient. At each recalibration, we apply the same calibration rule with T replaced by Tbt . Recalibration follows the same doubling schedule as in the horizon-aware policy.

Algorithm 3 Horizon-Aware 1: Input: horizon T . 2: Pull each arm once. 3: Form p̃i = (Si + 1/2)/(Ni + 1) and sort to obtain p̃. 4: Set (α, β) = Cal(T, p̃) and Ical = maxi Ni . 5: for t = K + 1, . . . , T do 6:

if maxi Ni ≥ 2Ical then

Form p̃i = (Si + 1/2)/(Ni + 1) and sort to obtain p̃.

Set (α, β) = Cal(T, p̃) and Ical = maxi Ni .

end if

10:

Pull At ∈ arg maxi (Si + α)/(Ni + β).

11:

Observe Xt and update SAt and NAt .

12: end for

Algorithm 4 Fully Adaptive 1: Input: coefficient φ. 2: Pull each armnonce.l

3: Set Tb = max φK, K

mo p log(e + K) .

4: Form p̃i = (Si + 1/2)/(Ni + 1) and sort to obtain p̃. 5: Set (α, β) = Cal(Tb, p̃) and Ical = maxi Ni . 6: for t = K + 1, K + 2, . . . do 7: 8: 9: 10:

if maxi Ni ≥ 2In cal then mo l p Set Tb = max φK, (t − 1) log(e + t − 1) . Form p̃i = (Si + 1/2)/(Ni + 1) and sort to obtain p̃. Set (α, β) = Cal(Tb, p̃) and Ical = maxi Ni .

11:

end if

12:

Pull At ∈ arg maxi (Si + α)/(Ni + β).

13:

Observe Xt and update SAt and NAt .

14: end for

3.3. Numerical Experiments The previous sections developed horizon-calibrated regularized greedy policies under three information settings. We now evaluate their empirical performance. Experimental Design. We consider K ∈ {2, 5} and horizon-per-arm values T /K ∈ {600, 800, 1,000, 1,200, 1,400, 1,600}. We evaluate the proposed policies under two arm-mean environments, one uniform and one scaled Poisson-generated. For each configuration, reported quantities are averaged over M = 100 randomly generated Bernoulli bandit instances and N = 5,000 independent replications per instance. In the uniform environment, arm means are drawn independently from Uniform[0.01, 0.99]; in the scaled Poisson environment, arm means are drawn independently from a scaled Poisson(10)/30 distribution restricted to [0.01, 0.99]. In both environments, the arm means are sorted in decreasing order. All policies are evaluated on the same instance ensemble under common random numbers with master seed 20260630. Oracle, Horizon-Aware, and Fully Adaptive use ϵ◦ = 0.2, bisection accuracy εα = 10−3 , and φ = 500. Mean regret and mean running time

are reported across instances, and configurations exceeding the 24-hour time limit are marked as unfinished. Benchmarks. We compare against thirteen standard policies covering the main classes of exploration strategies used in the bandit literature. Each algorithm is initialized by pulling each arm once, with ties in any arg max broken uniformly at random: • Pure Greedy (Jedor et al., 2021), which selects At = arg maxi Si /Ni and coincides with our policy at α = 0. • ϵ-Greedy (Fixed) (Kuleshov and Precup, 2014), which selects At = arg maxi Si /Ni with probability 1 − ϵ and a uniformly random arm otherwise, with ϵ = 0.1. • ϵ-Greedy (Decay) (Kuleshov and Precup, 2014), which applies the same rule as ϵ-Greedy (Fixed) with ϵ replaced by the decaying rate ϵt = min(1, c/t) and c = 1. • UCB1 (Upper Confidence Bound 1; Auer et al., 2002), which selects At = arg maxi Si /Ni + p c log t/Ni with c = 2. • KL-UCB (Cappé et al., 2013), which selects At = arg maxi max{q ∈ [Si /Ni , 1] : Ni d(Si /Ni , q) ≤ log t + c log log t} with c = 3, where d(x, y) = x log xy + (1 − x) log 1−x 1−y is the Kullback-Leibler divergence. • MOSS (the Minimax Optimal Strategy in the Stochastic case; Audibert and Bubeck, 2009), p which selects At = arg maxi Si /Ni + max(log(T /(KNi )), 0)/Ni . • Thompson Sampling (Thompson, 1933), which draws θi ∼ Beta(1 + Si , 1 + Ni − Si ) from a Beta(1, 1) prior and selects At = arg maxi θi . • BayesUCB (Kaufmann et al., 2012), which uses the same Beta(1, 1) prior and selects At = arg maxi Q 1 − 1/t; Beta(1 + Si , 1 + Ni − Si ) , where Q(· ; ·) is the posterior quantile function. • IDS (Information-Directed Sampling; Russo and Van Roy, 2014), which uses a Beta(1, 1) prior, computes for each arm the posterior instantaneous regret ∆i (t) = Et [Rt,A∗ − Rt,i ] and information gain gi (t) = It (A∗ ; Yt,i ), and samples from a distribution πt minimizing the P P information ratio ( i πi ∆i (t))2 /( i πi gi (t)), with the optimizer implemented by searching over two-arm mixtures. • OGI (Optimistic Gittins Indices; Farias and Gutin, 2022), which uses a tractable optimistic approximation to the Gittins index with a time-varying discount factor and is implemented in its one-step form with a Beta(1, 1) prior by setting ai = 1 + Si (t), bi = 1 + Ni (t) − Si (t), and γt = 1 − 1/t at time t, computing the index vi,t as the solution λ ∈ [0, 1] of λ = ai ai +bi [1 − γt FBeta(ai +1,bi ) (λ)] + γt λFBeta(ai ,bi ) (λ), and selecting At = arg maxi vi,t .

• IRS.FH (Information Relaxation Sampling with finite-horizon penalty; Min et al., 2024), which modifies Thompson sampling by using a finite-horizon posterior predictive score and,

at time t, sets the remaining horizon to τt = T −t+1, draws pei ∼ Beta(1+Si (t), 1+Ni (t)−Si (t)) ei ∼ Binomial(τt −1, pei ) for each arm i, computes m ei )/(2+Ni (t)+τt −1), and R e FH = (1+Si (t)+R i,t

and selects At = arg maxi m e FH i,t . • ETC (Explore-then-Commit; Colton, 1963;nGarivier let al., 2016), mo which first explores in round-robin until each arm has mETC = min ⌊T /K⌋ , (T /K)2/3

pulls, and then commits

to At = arg maxi Si /Ni for the remaining periods. • DETC (Double Explore-then-Commit; Jin et al., 2021), which first pulls every arm until each √ has m1 = ⌈ log T ⌉ pulls, sets i(0) = arg maxi Si /Ni , pulls i(0) for m2 = ⌈(log T )2 ⌉ additional pulls, then checks each arm j ̸= i(0) with at most m2 additional pulls, and finally commits to At = i(0) if the check succeeds, or otherwise pulls every arm for another m2 rounds and commits to At = arg maxi Sifb /Nifb based on this fallback sample. Performance metrics. We report mean regret over the ensemble of instances and replications. Throughout this section, the strongest benchmark denotes the classical benchmark with the lowest mean regret in the corresponding configuration. Let Rbest denote its mean regret. For each calibrated policy, we report the relative regret (Rours − Rbest )/Rbest , where negative values indicate lower regret than the strongest benchmark. Because Oracle uses the true arm means, it serves only as a reference. We therefore also report the relative regret increase of Horizon-Aware and Fully Adaptive over Oracle, (Rours − ROracle )/ROracle . We also report average wall-clock time per instance. Let Cbest denote the average running time of the strongest benchmark and Cours that of the calibrated policy. The reported relative time difference is (Cours − Cbest )/Cbest , where negative values indicate lower running time than the strongest benchmark. Computing environment. All experiments used CPU-only computation. Each policy–configuration pair was run as a separate job on a server with two Intel Xeon 6258R processors, 56 CPU cores, and 192 GB of memory. Within each job, instance-level simulations were parallelized by assigning one CPU core to each task. 3.3.1. Numerical Results. Tables 1–4 report the performance of the proposed policies under the uniform and scaled Poissongenerated arm-mean distributions over the values of K and T /K. For readability, we omit confidence intervals from the tables. All highlighted comparisons below are statistically significant at the 1% level. Horizon-Aware is the strongest implementable policy in all 24 configurations and reduces mean regret by 13.5% on average relative to the strongest completed benchmark. Fully Adaptive exhibits a similar pattern. It also outperforms the strongest completed benchmark in every configuration and reduces mean regret by 10.2% on average, demonstrating the broad competitiveness of the anytime calibration. Both policies reduce mean running time by at least 98.8% relative to the corresponding strongest benchmarks. Across all configurations, the strongest benchmark in terms of regret is either IDS or OGI. Both are substantially more computationally intensive in practice: IDS requires information-directed

calculations, whereas OGI requires index optimization. We also observe that OGI and IRS.FH perform better under the uniform arm-mean distribution, consistent with the fact that the uniform distribution coincides with the prior specification assumed by these policies. The empirical behavior closely follows the finite-horizon regret decomposition developed in Section 2. The proposed policies calibrate regularization to balance transient abandonment costs against the probability of suboptimal convergence over a finite horizon. The empirical improvements indicate that this tradeoff is a principal determinant of finite-horizon performance. The comparison with existing horizon-aware algorithms further illustrates this point. MOSS, IRS.FH, ETC, and DETC already incorporate knowledge of the horizon, yet Horizon-Aware remains the strongest implementable policy across all tested configurations. The improvement therefore does not come from incorporating horizon information itself. Rather, it comes from using the finite-horizon regret envelope to determine the amount of regularization warranted by the horizon. The benefit of calibration tends to increase with the horizon because reducing the probability of suboptimal absorption has the largest cumulative effect on regret. As the number of arms increases, the improvement becomes more moderate, consistent with the finite-arm approximation becoming less accurate in larger problems. This pattern suggests that further gains are more likely to come from sharper, albeit more complex, finite-arm approximations. Nevertheless, the proposed policies remain competitive with the strongest benchmark algorithms throughout the experimental design. Finally, Oracle Calibration provides a useful reference for assessing the proposed methodology. As expected, it achieves the lowest regret in every configuration. Horizon-Aware and Fully Adaptive nevertheless remain close to this oracle benchmark, trailing Oracle by only 7.08% and 11.1% on average, respectively. This result demonstrates that most of the benefit of oracle calibration can be retained without prior knowledge of the underlying problem instance.

4. Conclusion This paper studies finite-horizon experimentation through a class of regularized greedy policies. We derive analytical expressions for the finite-horizon regret, characterize the probability of suboptimal convergence, and use these results to calibrate the regularization parameters under varying levels of information, ranging from oracle settings to fully adaptive implementations. The analysis suggests a different perspective on finite-horizon bandit problems. Classical bandit algorithms are designed to achieve asymptotically optimal regret by continuing to explore as the horizon grows. Over finite operational horizons, however, the dominant source of regret is often not insufficient exploration, but premature commitment to a suboptimal arm. The resulting design problem is thus to balance the transient cost of delaying commitment against the probability of suboptimal convergence. Regularization provides a direct mechanism for controlling this trade-off. The numerical experiments reinforce this characterization. Across a broad range of horizons and numbers of arms, the proposed policies consistently match or outperform state-of-the-art bandit algorithms, including Thompson Sampling, OGI, IDS and KL-UCB. In general, these results suggest that simple, well-calibrated algorithms can compete with state-

24 Table 1

Performance comparison for K = 2 under uniformly distributed arm means. Each entry averages

over M = 100 Bernoulli bandit instances and N = 5,000 replications per instance. Time reports mean seconds per instance. Rows labeled “vs. strongest benchmark” report percentage differences in regret and running time relative to the lowest-regret completed benchmark, while rows labeled “vs. Oracle” report relative regret increases over Oracle. Negative values indicate improvements. Boldface identifies the lowestregret non-Oracle policy, boxes identify the strongest completed benchmark, slashes indicate unfinished configurations, and double dashes indicate inapplicable entries. Running-time differences at or below −99.9% are reported as −99.9%.

Policy

T /K = 600

T /K = 800

T /K = 1,000

T /K = 1,200

T /K = 1,400

T /K = 1,600

Mean

Time

Horizon-Aware 4.11 2.81 4.43 3.44 4.71 3.92 4.98 4.60 5.19 5.30 5.39 5.67 vs. strongest benchmark -13.7% -99.9% -15.3% -99.9% -16.3% -99.9% -16.7% -99.9% -17.4% -99.9% -17.9% -99.9% – +5.10% – +6.11% – +6.89% – +7.55% – vs. Oracle +4.39% – +4.25% Fully Adaptive 4.16 2.64 4.49 3.21 4.78 3.73 5.07 4.61 5.31 5.34 5.54 5.65 vs. strongest benchmark -12.6% -99.9% -14.2% -99.9% -15.1% -99.9% -15.1% -99.9% -15.4% -99.9% -15.6% -99.9% – +6.66% – +8.16% – +9.45% – +10.5% – vs. Oracle +5.68% – +5.65% Pure Greedy ϵ-Greedy (Fixed) ϵ-Greedy (Decay) UCB1 KL-UCB MOSS Thompson Sampling BayesUCB IDS OGI IRS.FH ETC DETC

42.5 23.4 18.6 21.4 10.6 10.1 6.04 5.62 4.75 4.78 5.71 25.2 25.0

0.946 1.07 1.05 1.00 9.52 1.12 1.98 14.6 6,211 179 3.61 0.318 0.518

56.5 30.0 23.5 24.4 11.8 11.1 6.55 6.24 5.23 5.27 6.20 30.2 27.5

1.23 1.23 1.25 1.20 12.4 1.34 2.45 19.3 8,692 245 4.57 0.311 0.594

70.4 1.40 36.6 1.54 28.2 1.56 26.9 1.47 12.8 15.7 11.9 1.69 6.96 3.11 6.75 24.1 5.63 10,800 5.68 314 6.62 5.64 34.6 0.384 29.4 0.710

84.4 1.69 43.1 1.83 32.9 1.89 29.0 1.82 13.7 18.5 12.6 2.00 7.32 3.74 7.21 29.3 5.97 13,244 6.04 381 6.99 6.71 38.9 0.463 31.2 0.824

98.4 1.96 49.6 2.51 37.4 2.16 30.9 2.04 14.4 21.3 13.1 2.31 7.63 4.43 7.61 35.7 6.28 15,640 6.37 454 7.29 7.78 43.2 0.551 32.9 0.943

112 2.23 56.1 2.44 41.9 2.48 32.6 2.34 15.1 24.4 13.7 2.65 7.92 4.91 7.98 39.4 6.56 17,854 6.66 522 7.58 8.82 46.9 0.624 34.4 1.10

Oracle 3.93 0.846 4.25 1.22 4.48 1.50 4.69 1.69 4.86 1.98 5.01 2.22 vs. strongest benchmark -17.3% -99.9% -18.8% -99.9% -20.4% -99.9% -21.5% -99.9% -22.7% -99.9% -23.6% -99.9%

of-the-art bandit methods in finite-horizon settings. We hope this work motivates further study of simple algorithmic designs tailored to finite-horizon objectives.

Code Availability A repository is available at https://osf.io/96udf/overview?view_only=4ecd77023d5147a8bd ca4be9e9528454.

References Agarwal, A., Hsu, D., Kale, S., Langford, J., Li, L., and Schapire, R. (2014). Taming the monster: A fast and simple algorithm for contextual bandits. International Conference on Machine Learning, pages 1638–1646. Agrawal, R. (1995). Sample mean based index policies with o(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4):1054–1078. Audibert, J.-Y. and Bubeck, S. (2009). Minimax policies for adversarial and stochastic bandits. In Proceedings of the 22th Annual Conference on Learning Theory, pages 217–226, Montreal, Canada. Auer, P., Cesa-Bianchi, N., and Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2):235–256.

25 Table 2

Performance comparison for K = 5 under the uniform arm-mean distribution. The format is the

same as Table 1.

Policy

T /K = 600

T /K = 800

T /K = 1,000

T /K = 1,200

T /K = 1,400

T /K = 1,600

Mean

Time

Horizon-Aware 17.2 9.32 18.9 10.7 20.1 13.7 21.3 15.1 22.4 17.1 23.3 18.2 vs. strongest benchmark -10.6% -98.9% -10.7% -99.1% -11.2% -99.1% -11.2% -99.2% -10.4% -99.2% -10.5% -99.2% vs. Oracle +5.51% – +6.84% – +7.84% – +8.44% – +9.77% – +10.4% – Fully Adaptive 18.0 9.78 19.5 10.9 21.7 13.3 22.9 14.7 24.0 16.5 25.0 17.5 vs. strongest benchmark -6.77% -98.8% -7.97% -99.1% -4.26% -99.1% -4.30% -99.2% -4.04% -99.2% -3.67% -99.3% vs. Oracle +10.0% – +10.1% – +16.3% – +16.8% – +17.6% – +18.8% – Pure Greedy ϵ-Greedy (Fixed) ϵ-Greedy (Decay) UCB1 KL-UCB MOSS Thompson Sampling BayesUCB IDS OGI IRS.FH ETC DETC

132 2.82 113 2.99 90.6 3.04 114 3.10 47.0 55.9 40.8 3.68 24.1 8.40 23.3 91.1 19.5 37,062 19.3 847 23.0 17.6 128 0.590 193 1.34

175 3.76 146 4.04 117 4.09 129 4.11 51.6 72.0 44.4 4.91 25.8 11.2 25.6 122 21.3 49,177 21.1 1,154 24.7 23.3 154 0.801 207 1.68

218 4.71 178 4.93 143 5.09 141 5.21 55.3 89.5 47.3 6.39 27.1 14.1 27.4 156 22.7 61,642 22.7 1,468 26.1 28.6 176 0.988 222 1.99

261 5.63 211 5.99 169 6.15 151 6.26 58.3 106 49.8 7.47 28.2 16.8 28.9 187 24.0 74,120 23.9 1,788 27.2 34.2 198 1.18 233 2.34

304 243 195 160 61.0 51.9 29.2 30.3 / 25.0 28.2 220 244

6.55 7.19 7.19 7.22 125 8.61 20.9 221 / 2,081 40.2 1.49 2.78

347 275 220 168 63.4 53.8 30.1 31.5 / 26.0 29.1 238 253

7.54 7.93 8.08 8.03 146 10.1 22.4 252 / 2,413 45.5 1.64 3.02

Oracle 16.3 2.77 17.7 3.77 18.6 4.65 19.6 5.59 20.4 6.58 21.1 7.38 vs. strongest benchmark -15.3% -99.7% -16.4% -99.7% -17.7% -99.7% -18.1% -99.7% -18.4% -99.7% -18.9% -99.7%

Table 3

Performance comparison for K = 2 under the scaled Poisson-generated arm-mean distribution.

The format is the same as Table 1.

Policy

T /K = 600

T /K = 800

T /K = 1,000

T /K = 1,200

T /K = 1,400

T /K = 1,600

Mean

Time

Horizon-Aware 7.21 4.14 7.95 5.24 8.58 5.67 9.10 6.85 9.52 7.83 9.97 8.51 vs. strongest benchmark -9.13% -99.9% -11.1% -99.9% -12.3% -99.9% -13.4% -99.9% -14.7% -99.9% -15.2% -99.9% – +6.97% – +7.22% – +6.80% – +7.56% – vs. Oracle +6.19% – +6.40% Fully Adaptive 7.28 3.95 8.05 4.63 8.68 5.67 9.27 7.07 9.78 8.00 10.2 8.25 vs. strongest benchmark -8.27% -99.9% -9.97% -99.9% -11.2% -99.9% -11.8% -99.9% -12.4% -99.9% -12.8% -99.9% – +8.25% – +9.16% – +9.76% – +10.5% – vs. Oracle +7.19% – +7.74% Pure Greedy ϵ-Greedy (Fixed) ϵ-Greedy (Decay) UCB1 KL-UCB MOSS Thompson Sampling BayesUCB IDS OGI IRS.FH ETC DETC

43.1 15.2 27.3 22.8 15.2 13.0 9.62 9.36 7.93 8.13 8.91 14.9 20.4

0.906 0.981 0.960 0.942 9.42 1.07 1.95 13.9 6,806 202 3.48 0.269 0.480

57.5 18.3 35.5 27.3 17.6 14.7 10.7 10.7 8.94 9.19 9.99 17.5 23.9

1.20 1.25 1.28 1.20 12.6 1.35 2.48 18.3 9,360 278 4.44 0.317 0.600

71.8 1.44 21.2 1.59 43.5 1.59 31.1 1.49 19.7 15.3 16.1 1.71 11.7 3.18 11.8 22.9 9.78 11,634 10.1 357 10.9 5.54 19.8 0.391 27.2 0.722

86.1 1.74 23.9 1.87 51.5 1.92 34.6 1.80 21.5 18.7 17.4 2.01 12.5 3.75 12.7 27.2 10.5 14,254 10.8 438 11.6 6.52 22.0 0.463 30.2 0.840

100 2.01 26.6 2.18 59.4 2.21 37.7 2.08 23.1 21.8 18.5 2.35 13.2 4.37 13.6 32.0 11.2 16,783 11.5 521 12.3 7.66 24.1 0.561 33.0 0.950

114 2.28 29.2 2.47 67.2 2.51 40.6 2.37 24.6 24.6 19.4 2.70 13.8 4.96 14.4 36.4 11.7 19,274 12.2 602 13.0 8.72 25.8 0.641 35.7 1.10

Oracle 6.79 0.988 7.47 1.22 8.02 1.40 8.49 1.77 8.91 1.97 9.26 2.26 vs. strongest benchmark -14.4% -99.9% -16.4% -99.9% -18.0% -99.9% -19.2% -99.9% -20.2% -99.9% -21.1% -99.9%

Bastani, H. and Bayati, M. (2020). Mostly exploration-free algorithms for contextual bandits. Management Science, 66(4):1511–1531. Bayati, M., Cao, J., and Chen, W. (2026). Speed up the cold-start learning in two-sided bandits with many arms. Management Science. Articles in Advance. Bayati, M., Hamidi, N., Johari, R., and Khosravi, K. (2020). Unreasonable effectiveness of greedy algorithms

26 Table 4

Performance comparison for K = 5 under the scaled Poisson-generated arm-mean distribution.

The format is the same as Table 1.

Policy

T /K = 600

T /K = 800

T /K = 1,000

T /K = 1,200

T /K = 1,400

T /K = 1,600

Mean

Time

Horizon-Aware 32.3 13.5 35.6 15.4 38.3 19.8 40.4 22.4 42.6 25.3 44.2 25.9 vs. strongest benchmark -7.06% -99.9% -7.72% -99.9% -8.40% -99.9% -20.5% -99.0% -20.7% -99.1% -21.5% -99.2% vs. Oracle +7.43% – +7.87% – +7.67% – +7.26% – +7.92% – +7.55% – Fully Adaptive 33.6 13.7 36.6 15.7 40.6 19.4 43.1 21.6 45.0 24.8 46.7 24.9 vs. strongest benchmark -3.18% -99.9% -5.14% -99.9% -2.90% -99.9% -15.3% -99.1% -16.2% -99.1% -17.1% -99.2% vs. Oracle +11.9% – +10.9% – +14.1% – +14.2% – +14.0% – +13.6% – Pure Greedy ϵ-Greedy (Fixed) ϵ-Greedy (Decay) UCB1 KL-UCB MOSS Thompson Sampling BayesUCB IDS OGI IRS.FH ETC DETC

197 2.99 73.5 3.05 141 3.16 133 3.17 85.1 57.0 55.5 3.69 46.7 8.61 49.3 91.8 34.8 42,261 39.2 1,060 43.9 17.2 83.9 0.609 120 1.30

262 3.89 89.8 4.10 185 4.31 156 4.17 97.2 73.3 61.7 4.90 51.4 11.3 55.4 122 38.6 55,733 43.8 1,460 48.4 22.9 99.4 0.790 137 1.73

327 5.13 105 5.14 228 5.42 177 5.26 107 92.6 66.7 6.25 55.2 14.2 60.5 152 41.8 70,331 47.6 1,877 52.1 28.1 112 1.01 154 1.92

392 120 271 194 115 71.1 58.3 64.8 / 50.8 55.2 125 170

5.84 6.12 6.58 6.27 112 7.49 17.0 182 / 2,278 33.3 1.20 2.25

457 135 313 210 123 74.8 61.1 68.6 / 53.7 57.8 137 184

6.88 7.20 7.63 7.29 131 8.57 19.8 213 / 2,708 38.6 1.38 2.58

522 149 355 225 129 78.1 63.5 72.0 / 56.3 60.4 148 198

7.89 8.20 8.37 8.30 149 10.0 22.5 243 / 3,127 44.1 1.58 2.97

Oracle 30.1 2.84 33.0 3.83 35.6 4.72 37.7 5.58 39.5 6.73 41.1 7.49 vs. strongest benchmark -13.5% -99.9% -14.5% -99.9% -14.9% -99.9% -25.8% -99.8% -26.5% -99.8% -27.0% -99.8%

in multi-armed bandit with many arms. Curran Associates, Inc. Cao, J. (2025). Collaborative learning and decision making on pricing and recommendation: A simple framework for planning. Management Science. Articles in Advance. Cappé, O., Garivier, A., Maillard, O.-A., Munos, R., and Stoltz, G. (2013). Kullback-leibler upper confidence bounds for optimal sequential allocation. The Annals of Statistics, 41(3):1516–1541. Colton, T. (1963). A model for selecting one of two medical treatments. Journal of the American Statistical Association, 58(302):388–400. den Boer, A. V. and Zwart, B. (2014). Simultaneously learning and optimizing using controlled variance pricing. Management Science, 60(3):770–783. Fan, L. and Glynn, P. W. (2025). The fragility of optimized bandit algorithms. Operations Research, 73(6):3173–3198. Farias, V. F. and Gutin, E. (2022). Optimistic gittins indices. Operations Research, 70(6):3432–3456. Garivier, A. and Cappé, O. (2011). The kl-ucb algorithm for bounded stochastic bandits and beyond. Conference on Learning Theory, pages 359–376. Garivier, A., Kaufmann, E., and Lattimore, T. (2016). On explore-then-commit strategies. Advances in Neural Information Processing Systems, 29. Gittins, J. C. (1979). Bandit processes and dynamic allocation indices. Journal of the Royal Statistical Society: Series B, 41(2):148–177. Jedor, M., Louëdec, J., and Perchet, V. (2021). arXiv:2101.01086.

Be greedy in multi-armed bandits.

arXiv preprint

27 Jin, T., Xu, P., Xiao, X., and Gu, Q. (2021). Double explore-then-commit: Asymptotic optimality and beyond. In Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2584–2633. PMLR. Kaufmann, E., Cappe, O., and Garivier, A. (2012). On bayesian upper confidence bounds for bandit problems. In Lawrence, N. D. and Girolami, M., editors, Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of Proceedings of Machine Learning Research, pages 592–600, La Palma, Canary Islands. PMLR. Keskin, N. B. and Zeevi, A. (2014). Dynamic pricing with an unknown demand model: Asymptotically optimal semi-myopic policies. Operations Research, 62(5):1142–1167. Keskin, N. B. and Zeevi, A. (2017). Chasing demand: Learning and earning in a changing environment. Mathematics of Operations Research, 42(2):277–307. Kuleshov, V. and Precup, D. (2014).

Algorithms for multi-armed bandit problems.

arXiv preprint

arXiv:1402.6028. Lai, T. L. and Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22. Lattimore, T. and Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press. Liu, C.-Y. and Li, L. (2015). On the prior sensitivity of thompson sampling. arXiv preprint arXiv:1506.03378. Mersereau, A. J., Rusmevichientong, P., and Tsitsiklis, J. N. (2009). A structured multiarmed bandit problem and the greedy policy. IEEE Transactions on Automatic Control, 54(12):2787–2802. Min, S., Maglaras, C., and Moallemi, C. C. (2024). Thompson sampling with information relaxation penalties. Management Science, 71(3):1988–2010. Niño-Mora, J. (2011). Computing a classic index for finite-horizon bandits. INFORMS Journal on Computing, 23(2):254–267. Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016). Batched bandit problems. The Annals of Statistics, 44(2):660–681. Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527–535. Russo, D. and Van Roy, B. (2014). Learning to optimize via information-directed sampling. Advances in Neural Information Processing Systems, 27. Russo, D., Van Roy, B., Kazerouni, A., Osband, I., and Wen, Z. (2018). A tutorial on thompson sampling. Foundations and Trends in Machine Learning, 11(1):1–96. Simchi-Levi, D. and Wang, C. (2025). Multi-armed bandit experimental design: Online decision-making and adaptive inference. Management Science, 71(6):4828–4846. Simchi-Levi, D., Zheng, Z., and Zhu, F. (2025). A simple and optimal policy design with safety against heavy-tailed risk for stochastic bandits. Management Science, 71(7):6298–6318. Slivkins, A. (2014). Contextual bandits with similarity information. Journal of Machine Learning Research,

28 15:2533–2568. Slivkins, A. et al. (2025). Greedy algorithm for structured bandits: A sharp characterization of asymptotic success and failure. arXiv preprint arXiv:2503.04010. Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. MIT Press, 2 edition. Thompson, W. R. (1933). On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285–294.

The Greedy Advantage in Finite-Horizon Bandits Electronic Companion

Throughout the appendices, arms are indexed without loss of generality so that 1 − ϵp ≥ p1 ≥ p2 ≥ · · · ≥ pK ≥ ϵp ,

p1 > pK ,

(EC.1)

where ϵp ∈ (0, 1/2) is an arbitrarily small but fixed constant. Thus the arm means remain in a fixed compact subset of (0, 1), ties are permitted, and p1 > pK ensures that at least one arm is suboptimal. For 1 ≤ i < j ≤ K, define the pairwise gap δij := pi − pj ≥ 0. In particular, when arm 1 is compared with arm i, write δi := δ1i = p1 − pi ,

i = 2, . . . , K,

and set δ1 := 0. The regularization parameters satisfy α ≥ 0,

β ≥ 0,

∆i := α − pi β ≥ 0,

i = 1, . . . , K.

Under the ordering of arm means, the conditions ∆i ≥ 0 for all i are equivalent to α ≥ p1 β. The pure-greedy policy is included as the special case α = β = 0.

A. Absorption of Greedy Trajectories This section establishes the pathwise absorption structure of the greedy dynamics. We allow both regularized greedy policies and the pure-greedy policy. For any fixed parameter configuration, we prove that the process cannot keep switching among two or more arms indefinitely. More precisely, there exists an almost surely finite random time T0 and an almost surely unique random absorbing arm Iabs ∈ {1, . . . , K} such that At = Iabs ,

∀t ≥ T0 .

This conclusion does not require all arm means to be distinct. Even when several arms have identical success probabilities, the handover process almost surely terminates, and the trajectory commits to one of the tied arms. The proof proceeds by ruling out pairwise entanglement: for any pair of arms i ̸= j, the event that both arms are sampled infinitely often has probability zero. If pi ̸= pj , this follows from concentration of the two scores around different limits. If pi = pj , the argument uses repeated negative fluctuations and the monotonicity of handover thresholds to rule out perpetual cycling.

Consequently, the absorbing events Qi := {Iabs = i},

i = 1, . . . , K,

(A.1)

form an almost-sure partition of the sample space: K X

P(Qi ) = 1.

i=1

For each arm i, we also define the complementary absorbing event Qci := to a null set, Qci = {Iabs ̸= i}.

j̸=i Qj . Equivalently, up

This absorption result is the starting point for the score-minimum

reduction in the next section: once the eventual winner is known to be a single absorbing arm, comparisons among the arms’ potential score minima, equivalently their centered score-minimum variables, can be used to sandwich the absorbing event Qi and its complement Qci . A.1. Topological Collapse to Absorbing States We prove that the greedy trajectory almost surely commits to a single arm. This conclusion applies both to regularized greedy policies and to the pure-greedy policy. The proof does not identify which arm is selected; it only rules out the possibility that two or more arms are sampled infinitely often. After n ≥ 1 pulls of arm i, define its score by pbi (n) :=

Si (n) + α . n+β

Recall that the algorithm first pulls each arm once. Thus all scores below are well-defined on their own clocks n ≥ 1. When α = β = 0, this reduces to pbi (n) = Si (n)/n. At each decision time, the policy selects an arm with maximal current score, breaking ties uniformly at random. For each arm i, define the event Ei := {Ni (t) → ∞}. For each pair i ̸= j, define the pairwise entanglement event Eij := Ei ∩ Ej . The event that at least two arms are sampled infinitely often is

E≥2 :=

(K X

) 1Ei ≥ 2

i=1

[

Eij .

(A.2)

1≤i<j≤K

Lemma A.1 (Topological collapse to absorbing states). For every fixed parameter configuration, there exist an almost surely finite random time T0 and an almost surely unique random arm Iabs ∈ {1, . . . , K} such that At = Iabs ,

∀t ≥ T0 .

(A.3)

Consequently, the absorbing events form an almost-sure partition: K X i=1

P(Qi ) = 1.

(A.4)

Proof. We prove P(Eij ) = 0,

1 ≤ i < j ≤ K.

Then P(E≥2 ) = 0 follows from the finite union bound applied to (A.2). Step 1. Almost-sure score concentration on each arm’s own clock. We first prove an arm-wise own-clock convergence statement. This step does not assert that any particular arm is sampled infinitely often along the actual trajectory. Instead, for each arm i, we consider its potential score sequence indexed by its own pull count n. Later, on the event Ei = {Ni (t) → ∞}, this own-clock convergence can be evaluated along the random subsequence n = Ni (t). If Ei does not occur, no asymptotic score statement for arm i along calendar time is needed. For each arm i, decompose the regularized score around its true mean: pbi (n) − pi =

Si (n) − pi n α − pi β Si (n) + α − pi = + . n+β n+β n+β

Since β ≥ 0, 1/(n + β) ≤ 1/n. Hence Si (n) − pi n |α − pi β| Si (n) |α − pi β| ≤ − pi + . + n+β n+β n n+β

|b pi (n) − pi | ≤

(A.5)

Fix an arbitrary ε > 0. Since α, β, and pi are fixed, |α − pi β|/(n + β) −→ 0. Therefore there exists ni,ε < ∞ such that, for all n ≥ ni,ε , ε |α − pi β| ≤ . n+β 2

(A.6)

Combining (A.5) and (A.6), for all n ≥ ni,ε , P (|b pi (n) − pi | > ε) ≤ P

Si (n) ε − pi > n 2

By Hoeffding’s inequality, P

Si (n) ε − pi > n 2

nε2 ≤ 2 exp − 2

The right-hand side is summable. Hence ∞ X

P (|b pi (n) − pi | > ε) < ∞.

(A.7)

n=1

Define the deviation event Aεi,n := {|b pi (n) − pi | > ε}. The event that this deviation occurs infinitely T S ε often is the limsup event lim supn→∞ Aεi,n = ∞ N =1 n≥N Ai,n . By (A.7) and the Borel–Cantelli

lemma, P lim supn→∞ Aεi,n = 0. Equivalently, P (∃Ni,ε < ∞ such that |b pi (n) − pi | ≤ ε for all n ≥ Ni,ε ) = 1.

(A.8)

Since ε > 0 is arbitrary, applying (A.8) to the countable sequence εm = 1/m gives, for each fixed arm i, pbi (n) → pi

almost surely as n → ∞.

Because K is finite, there exists a probability-one event Ωc on which pbi (n) → pi

as n → ∞

(A.9)

holds simultaneously for all arms i = 1, . . . , K. This is an own-clock statement. Consequently, on Ωc ∩ Ei , where Ni (t) → ∞, we may evaluate (A.9) along the random own-clock sequence n = Ni (t) and obtain pbi (Ni (t)) → pi

as t → ∞.

(A.10)

Thus, on Ωc ∩ Eij , both pbi (Ni (t)) → pi and pbj (Nj (t)) → pj . This is the only way Step 1 is used below. The fact that at least one arm must be sampled infinitely often follows later from the P identity K i=1 Ni (t) = t. Step 2. Pairwise impossibility when pi ̸= pj . Consider any pair i < j with pi > pj . On Eij ∩ Ωc , both Ni (t) and Nj (t) diverge. Let γij := (pi − pj )/3 > 0. By (A.9), there exists a finite random time Tij such that, for all t ≥ Tij , pbi (Ni (t)) > pi − γij ,

pbj (Nj (t)) < pj + γij .

Since pi − γij > pj + γij , we obtain pbi (Ni (t)) > pbj (Nj (t)),

∀t ≥ Tij .

Thus arm j cannot be selected after Tij , because arm i has a strictly larger score. This contradicts Ej . Therefore, P(Eij ) = 0

whenever pi ̸= pj .

Step 3. Pairwise impossibility when pi = pj . The intuition is simple. Suppose the policy keeps switching among arms with the same mean p. At each switch, the newly selected arm must have a score at least as large as the currently active arm. But while an arm is not selected, its score does not change. Hence the score level at which switches occur cannot increase over time; the sequence of handover score levels is nonincreasing. At the same time, each tied arm is sampled from a Bernoulli stream with mean p, so its score will eventually fluctuate below p. If switching continued forever, these downward fluctuations would

eventually push the handover score level below p. Once this happens, the handover level cannot later rise back above p, because it is nonincreasing. But if all tied arms were sampled infinitely often, their scores would converge back to p, so the handover score level would also have to approach p. This contradiction rules out perpetual switching among equal-mean arms. Consider any pair i < j with pi = pj =: p. We show that Eij ∩ Ωc is impossible. Assume, toward a contradiction, that ω ∈ Eij ∩ Ωc . Let K∞ := {k : Nk (t, ω) → ∞} be the set of arms sampled infinitely often on this path. Since i, j ∈ K∞ , we have |K∞ | ≥ 2. By Step 2, no two arms in K∞ can have different means. Hence pk = p,

∀k ∈ K∞ .

(A.11)

After the last pull of every arm outside K∞ , the selected arm always belongs to K∞ . Since |K∞ | ≥ 2, the selected arm must change infinitely many times among arms in K∞ . Let h1 < h2 < h3 < · · · be the successive decision times at which a new arm in K∞ is selected after a different arm in K∞ was selected previously. Let Bm := Ahm be the newly selected arm at the m-th handover. The relevant score at a handover is the score immediately before the new arm is pulled, because this is the score used by the greedy rule to select the arm. Define Vm := pbBm (NBm (hm − 1)) . Then, just before the decision at time hm , arm Bm is a maximizer among the arms in K∞ , and hence Vm = max pbk (Nk (hm − 1)) .

(A.12)

k∈K∞

During the interval from the decision at hm up to just before the decision at hm+1 , every arm other than Bm is passive. In particular, the next handover arm Bm+1 is passive throughout this interval. Therefore, NBm+1 (hm+1 − 1) = NBm+1 (hm − 1), and so Vm+1 = pbBm+1 NBm+1 (hm+1 − 1) = pbBm+1 NBm+1 (hm − 1)

≤ max pbk (Nk (hm − 1)) k∈K∞

= Vm . Thus V1 ≥ V2 ≥ V3 ≥ · · · .

(A.13)

For every k ∈ K∞ , the law of the iterated logarithm gives infinitely many negative fluctuations: Sk (n) − pn < −

1p 2p(1 − p)n log log n 2

for infinitely many n.

(A.14)

Using pbk (n) − p =

Sk (n) − pn + α − pβ , n+β

and the fact that α − pβ is fixed, (A.14) implies pbk (n) < p

for infinitely many n.

(A.15)

We claim that Vm < p for some finite m. Suppose otherwise: Vm ≥ p,

∀m.

(A.16)

For each arm k ∈ K∞ , define its first below-p pull count by νk := inf {n ≥ 1 : pbk (n) < p}. By (A.15), νk < ∞,

k ∈ K∞ .

Consider the first time at which arm k reaches pull count νk . Immediately after that pull, pbk (νk ) < p. If at that time every other arm in K∞ also has score strictly below p, then the maximal score among arms in K∞ is already below p, and therefore Vm < p at the next handover, contradicting (A.16). Otherwise, at least one arm in K∞ has score at least p. In that case arm k, whose score is now strictly below p, cannot be selected again as long as (A.16) holds. Thus, under (A.16), once arm k reaches pull count νk , it can never be selected again. Indeed, after that pull its score is strictly below p. If it were selected again at a later handover, then all competing arms in K∞ would have scores no larger than this strictly below-p frozen score, and hence the maximal handover score would be strictly below p, contradicting (A.16). Therefore arm k would be selected only finitely many times. Since k ∈ K∞ is arbitrary, this already contradicts the definition of K∞ , under which every arm in K∞ is sampled infinitely often. Hence (A.16) is impossible. Therefore, there exists m0 < ∞ such that Vm0 < p. Let ε := p − Vm0 > 0. By (A.13), Vm ≤ p − ε,

∀m ≥ m0 .

(A.17)

On the other hand, since every arm in K∞ is sampled infinitely often and K∞ is finite, min Nk (hm − 1) → ∞.

k∈K∞

By (A.9) and (A.11), max |b pk (Nk (hm − 1)) − p| → 0.

k∈K∞

Using (A.12), we get Vm → p. This contradicts (A.17). Therefore, P(Eij ) = 0 whenever pi = pj . Step 4. Finite union over pairs and construction of the absorbing arm.

Combining the unequal-mean and equal-mean cases, we have 1 ≤ i < j ≤ K.

P(Eij ) = 0, By (A.2), 

 [

P(E≥2 ) = P 

Eij  ≤

1≤i<j≤K

P(Eij ) = 0.

(A.18)

1≤i<j≤K

On the other hand, at least one arm must be sampled infinitely often. Indeed,

i=1 Ni (t) = t, t ≥ 1,

and therefore it is impossible that all Ni (t) remain bounded. Hence

K [

! Ei

= 1.

(A.19)

i=1

Combining (A.18) and (A.19), we obtain

K X

! 1Ei = 1

= 1.

(A.20)

i=1

On the probability-one event in (A.20), let Iabs be the unique arm satisfying EIabs . Every arm j ̸= Iabs has a finite last pull time. Define T0 := 1 + maxj̸=Iabs sup{t ≥ 1 : At = j}, with the convention that the supremum over an empty set is 0. Then T0 < ∞ almost surely and At = Iabs , ∀t ≥ T0 . This proves (A.3). Finally, by (A.1), Qi := {Iabs = i}, i = 1, . . . , K. Since Iabs is almost surely well-defined and unique, the events Q1 , . . . , QK are disjoint up to null sets and exhaust the sample space up to a null set. Therefore

K X

P(Qi ) = 1.

i=1

This proves (A.4).

A.2. Regret Decomposition and Core Quantities We next translate the absorbing-state partition into a finite-horizon regret decomposition. The purpose of this subsection is not yet to evaluate the absorbing probabilities, but to identify the finite-horizon quantities that must be controlled in the rest of the appendix. For each arm i, let Ni (T ) :=

T X

1{At = i}

t=1

be the number of pulls of arm i up to horizon T . We also define the terminal pull count Ni := lim Ni (T ) ∈ N ∪ {∞}. T →∞

The distinction is important: Ni (T ) is horizon-dependent, while Ni is the total number of pulls over the infinite trajectory. Recall that Qi denotes the event that the process eventually absorbs into arm i. On Qi , arm i is pulled forever, while every arm j ̸= i is eventually abandoned. Hence, Nj < ∞

j ̸= i.

on Qi ,

For finite-horizon regret, the relevant abandoned-arm count is the capped terminal count. For every T < ∞, Ni (T ) ≤ min{T, Ni },

i = 1, . . . , K.

(A.21)

Since arms are indexed so that p1 ≥ p2 ≥ · · · ≥ pK , the finite-horizon regret is R(T ) = E

" T X

# (p1 − pAt ) =

t=1

K X

δi E[Ni (T )] =

i=1

K X

δi E[Ni (T )].

(A.22)

i=2 pi <p1

Proposition A.2 (Absorption-based regret skeleton). For every finite horizon T , R(T ) ≥ T

and R(T ) ≤ T

K X

δi P(Qi ) −

K X

i=2 pi <p1

i=1

K X

δi P(Qi ) +

i=2 pi <p1

P(Qi )

(pj − pi ) E[min{T, Nj } | Qi ],

(A.23)

(pi − pj ) E[min{T, Nj } | Qi ].

(A.24)

j̸=i pj >pi

P(Qi )

i=1

X j̸=i pj <pi

Terms conditioned on events of probability zero are interpreted as zero contributions. Proof. Using the absorbing partition from Lemma A.1,

E[Nj (T )] =

K X

P(Qi ) E[Nj (T ) | Qi ].

i=1

Substituting (A.25) into (A.22), and recalling that δi = 0 when pi = p1 , gives R(T ) =

K X

P(Qi )

i=1

K X

δj E[Nj (T ) | Qi ].

j=1

Fix i ∈ [K]. Since exactly one arm is pulled in every period, K X j=1

Nj (T ) = T,

(A.25)

and hence E[Ni (T ) | Qi ] = T −

E[Nj (T ) | Qi ].

j̸=i

It follows that

K X

δj E[Nj (T ) | Qi ] = T δi +

j=1

(δj − δi ) E[Nj (T ) | Qi ].

(A.26)

j̸=i

Because δj − δi = (p1 − pj ) − (p1 − pi ) = pi − pj , substituting this identity into (A.26), and then summing over the absorbing partition, yields

R(T ) = T

K X

δi P(Qi ) +

i=2 pi <p1

K X

P(Qi )

X (pi − pj ) E[Nj (T ) | Qi ].

i=1

(A.27)

j̸=i

For each i ∈ [K], the centered correction admits the sign decomposition X

(pi − pj ) E[Nj (T ) | Qi ] =

j̸=i

(pi − pj ) E[Nj (T ) | Qi ] −

(pj − pi ) E[Nj (T ) | Qi ].

(A.28)

j̸=i pj >pi

j̸=i pj <pi

For the lower bound, discard the nonnegative first sum on the right-hand side of (A.28). Moreover, for j ̸= i, the capped-count domination (A.21) gives Nj (T ) ≤ min{T, Nj }

on Qi .

Therefore, X

(pi − pj ) E[Nj (T ) | Qi ] ≥ −

j̸=i

(pj − pi ) E[min{T, Nj } | Qi ].

j̸=i pj >pi

Substituting this inequality into (A.27) proves (A.23). For the upper bound, discard instead the nonpositive second sum on the right-hand side of (A.28). Using again (A.21), X X (pi − pj ) E[Nj (T ) | Qi ] ≤ (pi − pj ) E[min{T, Nj } | Qi ]. j̸=i

j̸=i pj <pi

Substituting this inequality into (A.27) proves (A.24).

The decomposition above shows that the leading finite-horizon regret is governed by the absorbing probabilities P(Qi ),

i = 2, . . . , K,

pi < p1 ,

while the remaining terms are capped transient abandonment costs of the form E[min{T, Nj } | Qi ],

j ̸= i.

The subsequent sections therefore focus on the two core tasks: characterizing the absorbing probabilities P(Qi ),

i = 2, . . . , K,

pi < p1 ,

and controlling the capped abandonment costs E[min{T, Nj } | Qi ],

j ̸= i.

B. Score-Minimum Reduction and Boundary-Crossing Reformulation This section converts the absorbing events into static comparisons among arm-wise score minima. From this section through Appendix G, we focus on the regularized case α > 0. The pure-greedy case (α, β) = (0, 0) is treated separately in Appendix H. This restriction avoids a boundary phenomenon that occurs under pure greedy. When α = β = 0, the score of an arm is the empirical mean Si (n)/n, which can equal zero whenever the arm has accumulated no successes. For example, if all arms receive a zero reward on their first pull, several arms start exactly at score zero, and further zero rewards may keep an arm at the same boundary for multiple pulls. Thus the relevant event is no longer a simple first arrival at a positive boundary; it may involve repeated contacts with the zero boundary. By contrast, when α > 0, every regularized score (Si (n) + α)/(n + β) is strictly positive. The score can become small, but it does not hit zero, so the one-arm score-minimum event can be represented cleanly as a first-passage boundary-crossing event. Therefore, we only treat the regularized regime here. For each arm i, we first define its potential score minimum Mi along an independent infinite reward stream, and we introduce the centered score-minimum variable Li := pi − Mi . The absorption result from Appendix A allows us to compare eventual winners through these potential score minima: arm i can absorb only if its potential score minimum is no smaller than the competing arms’ potential score minima, up to strict or weak tie conventions. This yields an event sandwich for Qi in terms of inequalities involving Mi , equivalently Li . We then show that, for a fixed centered level ℓi ∈ (0, pi ), the one-arm event {Li > ℓi } is exactly a boundary-crossing event for a negativedrift Bernoulli random walk with boundary height bi (ℓi ) = ∆i + βℓi . This reformulation is the bridge from the absorbing-event skeleton to the Lundberg-root analysis developed in the following sections. B.1. Event Sandwich via Potential Score Minima We now define the static variables that determine the absorbing events. For each arm i, let Xi,1 , Xi,2 , . . . be an independent infinite reward stream with Xi,n ∼ Bernoulli(pi ), n ≥ 1. Define the potential cumulative successes by Si (n) :=

n X r=1

Xi,r ,

n ≥ 1,

and recall that the potential regularized score after n pulls is pbi (n) = (Si (n) + α)/(n + β). The potential score minimum of arm i is Mi := inf n≥1 pbi (n). Although we write the definition in infimum form, this infimum is an attained minimum. Indeed, pbi (n) → pi almost surely, while the centered Bernoulli partial sums have arbitrarily large negative fluctuations along a subsequence; hence pbi (n) < pi for some finite n almost surely. After that strict descent below pi , convergence back to pi implies that only finitely many later indices can improve the minimum. Therefore there exists an almost surely finite random index n⋆i such that Mi = pbi (n⋆i ). We then define the centered score-minimum variable Li := pi − Mi . Because α > 0, the potential regularized score is strictly positive: pbi (n) > 0, n ≥ 1. Moreover, the preceding strict descent below pi gives Mi < pi almost surely. Consequently, 0 < Li < pi almost surely on Qi . For each arm i, define the strict and weak score-minimum winner events Wi> :=

Mi > max Mj j̸=i

Wi≥ :=

Mi ≥ max Mj j̸=i

Lemma B.1 (Absorbing-event sandwich by potential score minima). For each arm i, Wi> ⊆ Qi ⊆ Wi≥ .

(B.1)

Equivalently, in centered score-minimum form, {Li − Lj < pi − pj , ∀j ̸= i} ⊆ Qi ⊆ {Li − Lj ≤ pi − pj , ∀j ̸= i} . Consequently, with Qci =

(B.2)

j̸=i Qj ,

{∃j ̸= i : Mj > Mi } ⊆ Qci ⊆ {∃j ̸= i : Mj ≥ Mi } .

(B.3)

Proof. We first prove the weak necessary inclusion. Suppose Qi occurs. Then arm i is pulled infinitely often. Let n⋆i < ∞ be an index at which the potential score minimum of arm i is attained: pbi (n⋆i ) = Mi . Since arm i is pulled infinitely often on Qi , the actual trajectory eventually reaches this pull count. Let t⋆i be the decision epoch immediately after the n⋆i -th pull of arm i. At that epoch, the current score of arm i is exactly Mi . We claim that no competing arm can have potential score minimum strictly above Mi . Suppose, toward a contradiction, that for some j ̸= i, Mj > Mi . At the epoch t⋆i , the current score of arm j is one of its potential scores, and therefore is at least its potential minimum Mj . Hence

pbj (Nj (t⋆i )) ≥ Mj > Mi = pbi (Ni (t⋆i )). Moreover, after t⋆i , as long as arm i is not selected, its score remains frozen at Mi . Arm j’s score, whether frozen or updated by future pulls, can never fall below Mj , and hence can never fall below Mi . Thus there is always at least one arm with score strictly larger than arm i’s frozen score Mi . Consequently, arm i can never again be a maximizer of the greedy score after t⋆i . This contradicts Qi , because on Qi arm i is selected forever after some finite time. Therefore, Mj ≤ Mi , j ̸= i. Equivalently, Qi ⊆ Wi≥ .

(B.4)

We now prove the strict sufficient inclusion. Suppose Mi > max Mj . j̸=i

(B.5)

If Qi did not occur, then by the absorbing partition from Lemma A.1, there would exist some r ̸= i such that Qr occurs. Applying the weak necessary inclusion already proved, but now to the absorbing arm r, gives Mi ≤ Mr . This contradicts (B.5). Hence Wi> ⊆ Qi .

(B.6)

Combining (B.4) and (B.6) proves (B.1). It remains to rewrite the comparison in terms of Li . Since Mi = pi − Li , we have Mi > Mj ⇐⇒ pi − Li > pj − Lj ⇐⇒ Li − Lj < pi − pj ,

(B.7)

Mi ≥ Mj ⇐⇒ pi − Li ≥ pj − Lj ⇐⇒ Li − Lj ≤ pi − pj .

(B.8)

and similarly

Substituting (B.7) and (B.8) into (B.1) proves (B.2). Finally, taking complements in (B.1) gives (Wi≥ )c ⊆ Qci ⊆ (Wi> )c .

(B.9)

(Wi≥ )c = {∃j ̸= i : Mj > Mi } ,

(B.10)

(Wi> )c = {∃j ̸= i : Mj ≥ Mi } .

(B.11)

The two complement events are

Substituting (B.10) and (B.11) into (B.9) proves (B.3).

B.2. One-Arm Centered-Minimum Crossing and CGF Setup The event sandwich in Appendix B.1 reduces the complement Qci to comparisons among centered score-minimum variables. In particular, {∃j ̸= i : Li − Lj > pi − pj } ⊆ Qci ⊆ {∃j ̸= i : Li − Lj ≥ pi − pj } .

(B.12)

Thus, after conditioning on the competing variables Lj , the relevant events reduce to one-arm inequalities of the form Li > pi − pj + Lj ,

Li ≥ pi − pj + Lj .

The purpose of this subsection is to rewrite these one-arm inequalities as boundary-crossing events. The strict and weak versions correspond to the same random walk and the same boundary, with only a strict–weak crossing convention. The difference will later be absorbed into a bounded discrete-overshoot correction. Fix an arm i ∈ {1, . . . , K} and a deterministic centered level ℓi ∈ (0, pi ). The nontrivial crossing regime is exactly this interior interval. If ℓi ≥ pi , then {Li > ℓi } and {Li ≥ ℓi } are empty because Li < pi . If ℓi ≤ 0, then the score threshold pi − ℓi is above the limiting score pi , and crossing is eventually automatic. Hence the Lundberg-root analysis is needed only for ℓi ∈ (0, pi ). Recall Li := pi − inf pbi (n). n≥1

Although the score minimum is written as an infimum, it is attained in every crossing event considered here. Equivalently,

inf pbi (n) ≤ pi − ℓi

n≥1

= {∃n ≥ 1 : pbi (n) ≤ pi − ℓi } .

(B.13)

Define qi := 1 − pi , and recall ∆i := α − pi β. For the level ℓi , define the boundary height bi (ℓi ) := α − (pi − ℓi )β = ∆i + βℓi . Under α > 0, β ≥ 0, and ∆i ≥ 0, bi (ℓi ) > 0. For the potential reward stream of arm i, define the level-dependent increment Zi,r (ℓi ) := (pi − ℓi ) − Xi,r ,

r ≥ 1,

and the associated random walk Ui,n (ℓi ) :=

n X r=1

Zi,r (ℓi ) = (pi − ℓi )n − Si (n),

n ≥ 1,

with Ui,0 (ℓi ) := 0. The increment Zi,r (ℓi ) takes the two values  pi − ℓi , Zi,r (ℓi ) = −(q + ℓ ), i

Xi,r = 0, Xi,r = 1.

Its mean is E[Zi,r (ℓi )] = (pi − ℓi ) − pi = −ℓi < 0. Thus the crossing of the positive boundary bi (ℓi ) is an upward large-deviation event for a negative-drift Bernoulli random walk. Lemma B.2 (One-arm centered-minimum crossing). For every i and every ℓi ∈ (0, pi ), {Li > ℓi } = sup Ui,n (ℓi ) > bi (ℓi ) .

(B.14)

n≥1

Moreover, {Li ≥ ℓi } = sup Ui,n (ℓi ) ≥ bi (ℓi ) .

(B.15)

n≥1

Proof. For the strict event, {Li > ℓi } =

pi − inf pbi (n) > ℓi n≥1

inf pbi (n) < pi − ℓi

n≥1

= {∃n ≥ 1 : pbi (n) < pi − ℓi } Si (n) + α < pi − ℓi . = ∃n ≥ 1 : n+β

(B.16)

For every n ≥ 1, Si (n) + α < pi − ℓi ⇐⇒ Si (n) + α < (pi − ℓi )(n + β) n+β ⇐⇒ (pi − ℓi )n − Si (n) > α − (pi − ℓi )β ⇐⇒ Ui,n (ℓi ) > bi (ℓi ).

(B.17)

Combining (B.16) and (B.17) gives (B.14). For the weak event, the attainment property (B.13) gives {Li ≥ ℓi } =

pi − inf pbi (n) ≥ ℓi n≥1

inf pbi (n) ≤ pi − ℓi

n≥1

= {∃n ≥ 1 : pbi (n) ≤ pi − ℓi } Si (n) + α ≤ pi − ℓi . = ∃n ≥ 1 : n+β

(B.18)

For every n ≥ 1, Si (n) + α ≤ pi − ℓi ⇐⇒ Si (n) + α ≤ (pi − ℓi )(n + β) n+β ⇐⇒ (pi − ℓi )n − Si (n) ≥ α − (pi − ℓi )β ⇐⇒ Ui,n (ℓi ) ≥ bi (ℓi ).

(B.19)

Combining (B.18) and (B.19) proves (B.15).

Define the strict and weak first-passage times τi> (ℓi ) := inf {n ≥ 1 : Ui,n (ℓi ) > bi (ℓi )} ,

τi≥ (ℓi ) := inf {n ≥ 1 : Ui,n (ℓi ) ≥ bi (ℓi )} .

Lemma B.2 gives {Li > ℓi } = {τi> (ℓi ) < ∞},

{Li ≥ ℓi } = {τi≥ (ℓi ) < ∞}.

The two first-passage conventions differ only at the nboundary. Foro either convention, write τi (ℓi ) for the corresponding first-passage time: τi (ℓi ) ∈ τi> (ℓi ), τi≥ (ℓi ) . On the crossing event {τi (ℓi ) < ∞}, define the overshoot ri (ℓi ) := Ui,τi (ℓi ) (ℓi ) − bi (ℓi ).

(B.20)

Because an upward crossing can occur only through a single positive increment of size pi − ℓi , the overshoot satisfies 0 ≤ ri (ℓi ) ≤ pi − ℓi . Thus the terminal state at first passage can be written uniformly as Ui,τi (ℓi ) (ℓi ) = bi (ℓi ) + ri (ℓi ),

0 ≤ ri (ℓi ) ≤ pi − ℓi .

(B.21)

More precisely, for strict crossing, τi (ℓi ) = τi> (ℓi )

=⇒

0 < ri (ℓi ) ≤ pi − ℓi ,

τi (ℓi ) = τi≥ (ℓi )

=⇒

0 ≤ ri (ℓi ) < pi − ℓi .

whereas for weak crossing,

The common terminal representation (B.21) is sufficient for the Lundberg estimates below. This bounded overshoot is the only correction separating the strict and weak sides of the event sandwich in (B.12). We now introduce the cumulant generating function (CGF) of the one-step increment. For

θ ∈ R, define Λi (θ, ℓi ) := log E [exp {θZi,1 (ℓi )}] = log [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}] . At the origin, Λi (0, ℓi ) = 0. Its first derivative at the origin is the negative drift: ∂θ Λi (0, ℓi ) = E[Zi,1 (ℓi )] = −ℓi < 0. The positive Lundberg root, when it exists, is denoted by θi (ℓi ) > 0,

Λi (θi (ℓi ), ℓi ) = 0.

(B.22)

The corresponding tilted drift is vi (ℓi ) := ∂θ Λi (θi (ℓi ), ℓi ). The next section proves the existence and uniqueness of θi (ℓi ), the strict positivity of vi (ℓi ), and the endpoint behavior of both quantities.

C. Analytic Properties of the Lundberg Root and Tilted Drift We now characterize the one-arm crossing probability from Appendix B.2. For any arm i and any level ℓi ∈ (0, pi ), recall that {Li > ℓi } =

sup Ui,n (ℓi ) > bi (ℓi ) ,

bi (ℓi ) = ∆i + βℓi .

n≥1

The probability of this event is governed by the exponential cost of pushing the negative-drift walk Ui,n (ℓi ) above the boundary bi (ℓi ). We write this cost in root-based form as P(Li > ℓi ) ≈ exp{−θi (ℓi )bi (ℓi )}. The term θi (ℓi ) is the Lundberg exponent. It is defined as the positive solution of Λi (θ, ℓi ) = 0,

Λi (θ, ℓi ) = log [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}] .

This equation is the martingale condition. Indeed, when θ = θi (ℓi ), the process exp{θUi,n (ℓi )} has mean one at every step. Stopping this martingale at the first crossing time gives the root-based crossing identity up to the bounded overshoot at the boundary. Thus the exponent θi (ℓi )bi (ℓi ) is the primitive quantity behind the one-arm drawdown tail. The section establishes the properties of this exponent needed in the asymptotic analysis. First, for each ℓi ∈ (0, pi ), the equation Λi (θ, ℓi ) = 0 has a unique positive solution. The associated tilted drift vi (ℓi ) = ∂θ Λi (θi (ℓi ), ℓi ) is strictly positive, which will later bound the time needed for the

tilted walk to reach the boundary. Second, as ℓi ↓ 0, θi (ℓi ) =

2 ℓi + O(ℓ2i ), pi (1 − pi )

vi (ℓi ) = ℓi + O(ℓ2i ).

Combining this expansion with bi (ℓi ) = ∆i + βℓi gives θi (ℓi )bi (ℓi ) =

2∆i ℓi + O(∆i ℓ2i + βℓ2i ), pi (1 − pi )

which is the source of the local exponential envelope

2∆i P(Li > ℓi ) ≈ exp − ℓi . pi (1 − pi ) Finally, as ℓi ↑ pi , the positive jump size pi − ℓi vanishes, the root diverges at scale (pi − ℓi )−1 , and vi (ℓi ) ≍ pi − ℓi . These endpoint estimates provide the root and drift controls used in the crossing envelopes, the local Stieltjes replacement, and the later abandonment-cost bounds. C.1. Existence and Uniqueness of the Lundberg Root We first prove that the positive Lundberg root introduced in (B.22) is well-defined for every arm i and every level ℓi ∈ (0, pi ). Recall that Λi (θ, ℓi ) = log [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}] . Lemma C.1 (Existence and uniqueness of the Lundberg root). For every arm i and every ℓi ∈ (0, pi ), the equation Λi (θ, ℓi ) = 0 has a unique positive solution θi (ℓi ) > 0. Proof. Consider any i and any ℓi ∈ (0, pi ). By definition, Λi (0, ℓi ) = 0. Moreover, ∂θ Λi (0, ℓi ) = qi (pi − ℓi ) − pi (qi + ℓi ) = −ℓi < 0. Hence, by continuity, there exists ε > 0 such that Λi (θ, ℓi ) < 0, 0 < θ < ε. On the other hand, since pi ∈ [ϵp , 1 − ϵp ], ϵp > 0, and pi − ℓi > 0, the positive-jump term dominates as θ → ∞. More precisely, Λi (θ, ℓi ) = log [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}] = θ(pi − ℓi ) + log [qi + pi exp{−θ}] , where we used (pi − ℓi ) + (qi + ℓi ) = 1. Therefore, Λi (θ, ℓi ) → ∞ as θ → ∞. Since θ 7→ Λi (θ, ℓi ) is continuous, the intermediate value theorem implies that there exists at least one positive solution of Λi (θ, ℓi ) = 0.

It remains to prove uniqueness. Direct differentiation gives qi pi exp{θ(pi − ℓi )} exp{−θ(qi + ℓi )} [(pi − ℓi ) + (qi + ℓi )]2 [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}]2 qi pi exp{θ(pi − ℓi )} exp{−θ(qi + ℓi )} = > 0. [qi exp{θ(pi − ℓi )} + pi exp{−θ(qi + ℓi )}]2

∂θ2 Λi (θ, ℓi ) =

(C.1)

Thus θ 7→ Λi (θ, ℓi ) is strictly convex. Suppose, toward a contradiction, that there are two distinct positive roots 0 < θa < θb . Since Λi (0, ℓi ) = 0, Λi (θb , ℓi ) = 0, strict convexity implies that Λi (θ, ℓi ) < 0, 0 < θ < θb . In particular, Λi (θa , ℓi ) < 0, which contradicts the assumption that θa is a root. Therefore the positive root is unique. Recall the tilted drift associated with the positive Lundberg root: vi (ℓi ) := ∂θ Λi (θi (ℓi ), ℓi ). The preceding convexity argument also implies that this drift is strictly positive. Corollary C.2 (Strict positivity of the tilted drift). For every arm i and every ℓi ∈ (0, pi ), vi (ℓi ) > 0. Proof. By Lemma C.1, θi (ℓi ) is the unique positive root of Λi (θ, ℓi ) = 0. Moreover, ∂θ Λi (0, ℓi ) = −ℓi < 0, and θ 7→ Λi (θ, ℓi ) is strictly convex by (C.1). Since Λi (0, ℓi ) = Λi (θi (ℓi ), ℓi ) = 0,

(C.2)

the derivative at the positive root must be strictly positive. Indeed, if ∂θ Λi (θi (ℓi ), ℓi ) ≤ 0, then strict convexity would imply ∂θ Λi (θ, ℓi ) < 0, 0 < θ < θi (ℓi ), and consequently Z θi (ℓi ) Λi (θi (ℓi ), ℓi ) − Λi (0, ℓi ) =

∂θ Λi (θ, ℓi ) dθ < 0, 0

which contradicts (C.2). Therefore, vi (ℓi ) = ∂θ Λi (θi (ℓi ), ℓi ) > 0. C.2. Lower-Endpoint Behavior as ℓi ↓ 0 We next analyze the behavior of θi (ℓi ) and vi (ℓi ) as the drawdown level approaches the lower endpoint. The key point is that the Lundberg equation can be rewritten as an inverse relation between ℓi and θi (ℓi ). Separate the ℓi -dependent linear term in the CGF: Λi (θ, ℓi ) = −θℓi + Λi,0 (θ), where Λi,0 (θ) := θpi + log (qi + pi exp{−θ}) .

(C.3)

Thus the root equation Λi (θi (ℓi ), ℓi ) = 0 is equivalent to ℓi =

Λi,0 (θi (ℓi )) = gi (θi (ℓi )), θi (ℓi )

(C.4)

where, for θ > 0, gi (θ) :=

Λi,0 (θ) . θ

Lemma C.3 (Lower-endpoint equivalence between level and root). The map gi is continuous and strictly increasing from (0, ∞) onto (0, pi ). Consequently, ℓi 7→ θi (ℓi ) is continuous and strictly increasing on (0, pi ), and ℓi ↓ 0

⇐⇒

θi (ℓi ) ↓ 0.

(C.5)

Proof. We verify the endpoint limits and monotonicity of gi . First, Λ′i,0 (0) = 0.

Λi,0 (0) = 0, Hence, by L’Hopital’s rule,

lim gi (θ) = lim Λ′i,0 (θ) = 0. θ↓0

(C.6)

θ↓0

Next define hi (θ) := θΛ′i,0 (θ) − Λi,0 (θ). Then h′i (θ) = θΛ′′i,0 (θ). A direct calculation gives Λ′′i,0 (θ) =

pi qi exp{−θ} > 0, (qi + pi exp{−θ})2

θ > 0.

Therefore, h′i (θ) > 0, θ > 0. Since hi (0) = 0, it follows that hi (θ) > 0, θ > 0. Consequently, gi′ (θ) =

θΛ′i,0 (θ) − Λi,0 (θ) hi (θ) = 2 > 0, 2 θ θ

θ > 0.

(C.7)

Thus gi is strictly increasing. Finally, from (C.3), gi (θ) = pi + 1θ log (qi + pi exp{−θ}). Since qi ∈ [ϵp , 1 − ϵp ], ϵp > 0, lim gi (θ) = pi .

θ→∞

(C.8)

Combining (C.6), (C.7), and (C.8), gi is a continuous strictly increasing bijection from (0, ∞) onto (0, pi ). By (C.4), θi (ℓi ) = gi−1 (ℓi ). This proves the continuity and monotonicity of θi (ℓi ), and the endpoint equivalence (C.5). We now use this inverse representation to compute the local expansion of the root and the tilted drift. Let σi2 := pi qi .

Lemma C.4 (Local expansion of the root and tilted drift). For every arm i = 1, . . . , K, as ℓi ↓ 0, θi (ℓi ) =

4(1 − 2pi ) 2 2 ℓi + ℓi + O(ℓ3i ), σi2 3σi4

(C.9)

2(1 − 2pi ) 2 ℓi + O(ℓ3i ). 3σi2

(C.10)

and vi (ℓi ) = ℓi − In particular, θi (ℓi ) =

2 ℓi + O(ℓ2i ), σi2

vi (ℓi ) = ℓi + O(ℓ2i ).

(C.11)

Proof. For i ∈ {1, . . . , K}, by the standing interior condition, 1 ϵp (1 − ϵp ) ≤ σi2 = pi (1 − pi ) ≤ . 4

(C.12)

Thus σi2 is bounded away from both zero and infinity, and therefore ℓi ↓ 0

ℓi ↓ 0. σi2

⇐⇒

The function Λi,0 is real analytic in a neighborhood of θ = 0. Its normalized derivatives at the origin satisfy Λ′i,0 (0) Λi,0 (0) = = 0, σi2 σi2

Λ′′i,0 (0) σi2

= 1,

Λ′′′ i,0 (0) σi2

(4)

= −(1 − 2pi ),

Λi,0 (0) σi2

= 1 − 6σi2 .

(4)

Because Λi,0 (θ)/σi2 is jointly continuous in (θ, pi ), the standing interior condition (EC.1) ensures that it is uniformly bounded over all admissible pi and all θ in a sufficiently small neighborhood of zero. Hence

Λi,0 (θ) 1 − 2pi 3 1 θ + O(θ4 ), = θ2 − 2 2 6 σi

(C.13)

uniformly over all arms and admissible arm means. Recalling that gi (θ) = Λi,0 (θ)/θ, we obtain gi (θ) 1 1 − 2pi 2 θ + O(θ3 ). = θ− 2 2 6 σi

(C.14)

Moreover, d gi (θ) 1 = > 0. 2 dθ σi θ=0 2 Therefore, the analytic inverse function theorem applies at the origin. By the inverse relation (C.4), gi θi (ℓi ) ℓi = , σi2 σi2

(C.15)

and Lemma C.3 ensures that the resulting local inverse coincides with ℓi 7→ θi (ℓi ) for all sufficiently

small ℓi > 0. Write the local inverse expansion directly in powers of ℓi /σi2 : ℓi θi (ℓi ) = di,1 2 + di,2 σi

ℓi σi2

3 ! .

(C.16)

Substituting (C.16) into (C.15) and using (C.14) gives " 2 # 2 3 ! ℓi ℓi ℓi 1 ℓi 1 − 2pi 2 ℓi di,1 2 + di,2 = di,1 − +O . 2 2 2 2 6 σi σi σi σi σi2 Matching the first-order coefficient gives di,1 = 2. Matching the second-order coefficient gives 1 − 2pi 2 1 di,2 − di,1 = 0, 2 6 and hence di,2 =

1 − 2pi 2 4(1 − 2pi ) di,1 = . 3 3

Consequently, ℓi 4(1 − 2pi ) θi (ℓi ) = 2 2 + 3 σi

ℓi σi2

3 ! .

Using (C.12), this becomes θi (ℓi ) =

2 4(1 − 2pi ) 2 ℓi + ℓi + O(ℓ3i ), 2 σi 3σi4

which proves (C.9). The derivative of gi (θ)/σi2 at the origin equals 1/2 for every arm, and the higher-order coefficients remain uniformly bounded under the standing interior condition (EC.1). Hence the inverse expansion and its remainder are uniform over all admissible arm means. It remains to expand the tilted drift. By definition, vi (ℓi ) = ∂θ Λi (θi (ℓi ), ℓi ) = −ℓi + Λ′i,0 (θi (ℓi )). Differentiating (C.13) gives Λ′i,0 (θ) σi2

=θ−

1 − 2pi 2 θ + O(θ3 ). 2

Dividing (C.17) by σi2 , we obtain vi (ℓi ) ℓi 1 − 2pi 2 = − 2 + θi (ℓi ) − θi (ℓi ) + O θi3 (ℓi ) . 2 2 σi σi

(C.17)

Using the expansion already obtained for θi (ℓi ), we have " # 3 ! ℓi ℓi 4(1 − 2pi ) ℓi 2 1 − 2pi ℓi 2 vi (ℓi ) ℓi =− 2 +2 2 + 4 − +O 3 2 σi2 σi σi σi2 σi2 σi2 3 ! 2(1 − 2pi ) ℓi 2 ℓi ℓi +O . = 2− 3 σi σi2 σi2 Multiplying by σi2 and using (C.12) yields vi (ℓi ) = ℓi −

2(1 − 2pi ) 2 ℓi + O(ℓ3i ), 3σi2

which proves (C.10). The first-order statements in (C.11) follow immediately.

C.3. Upper-Endpoint Behavior as ℓi ↑ pi We now record the upper-endpoint behavior of the Lundberg root and the tilted drift.

Lemma C.3, the inverse relation ℓi = gi (θi (ℓi )) implies ℓi ↑ pi

⇐⇒

θi (ℓi ) → ∞.

(C.18)

Thus it remains to identify the precise divergence scale of θi (ℓi ) and the corresponding scale of vi (ℓi ). Lemma C.5 (Upper-endpoint expansion of the Lundberg root). As ℓi ↑ pi , θi (ℓi )(pi − ℓi ) = log

1 + o(1). qi

(C.19)

Equivalently, θi (ℓi ) =

log(1/qi ) +o pi − ℓ i

In particular, θi (ℓi ) ≍

1 pi − ℓi

as ℓi ↑ pi .

(C.20)

(C.21)

Proof. By (C.18), θi (ℓi ) → ∞ as ℓi ↑ pi . The Lundberg equation gives qi exp{θi (ℓi )(pi − ℓi )} + pi exp{−θi (ℓi )(qi + ℓi )} = 1. Since qi + ℓi → 1 and θi (ℓi ) → ∞, we have pi exp{−θi (ℓi )(qi + ℓi )} → 0. Therefore (C.22) implies qi exp{θi (ℓi )(pi − ℓi )} → 1.

(C.22)

Taking logarithms yields θi (ℓi )(pi − ℓi ) → log

1 . qi

This proves (C.19). The expansion (C.20) and the order estimate (C.21) follow immediately.

Lemma C.6 (Upper-endpoint expansion of the tilted drift). As ℓi ↑ pi , vi (ℓi ) = pi − ℓi + o(pi − ℓi ).

(C.23)

vi (ℓi ) ∼ pi − ℓi .

(C.24)

Equivalently,

Proof. By definition, vi (ℓi ) = ∂θ Λi (θi (ℓi ), ℓi ). Using the explicit form of Λi , and using the Lundberg equation to set the denominator equal to one, we obtain vi (ℓi ) = qi (pi − ℓi ) exp{θi (ℓi )(pi − ℓi )} − pi (qi + ℓi ) exp{−θi (ℓi )(qi + ℓi )}.

(C.25)

The Lundberg equation also gives qi exp{θi (ℓi )(pi − ℓi )} = 1 − pi exp{−θi (ℓi )(qi + ℓi )}.

(C.26)

Substituting (C.26) into (C.25), we get vi (ℓi ) = (pi − ℓi ) [1 − pi exp{−θi (ℓi )(qi + ℓi )}] − pi (qi + ℓi ) exp{−θi (ℓi )(qi + ℓi )} = (pi − ℓi ) − pi [(pi − ℓi ) + (qi + ℓi )] exp{−θi (ℓi )(qi + ℓi )} = (pi − ℓi ) − pi exp{−θi (ℓi )(qi + ℓi )}.

(C.27)

By Lemma C.5, log(1/qi ) θi (ℓi ) = +o pi − ℓ i

1 pi − ℓi

Since log(1/qi ) > 0 and qi + ℓi → 1, for all ℓi sufficiently close to pi , θi (ℓi )(qi + ℓi ) ≥

1 log(1/qi ) . 2 pi − ℓ i

Therefore,

log(1/qi ) exp − exp{−θi (ℓi )(qi + ℓi )} 2(pi − ℓi ) 0≤ ≤ . pi − ℓi pi − ℓi The right-hand side converges to zero because the exponential decay in (pi − ℓi )−1 dominates the

logarithmic divergence of (pi − ℓi )−1 . Equivalently,  log(1/qi )  exp − 2(pi − ℓi )   = − log(1/qi ) − log(pi − ℓi ) −→ −∞. log    pi − ℓ i 2(pi − ℓi ) 

Hence exp{−θi (ℓi )(qi + ℓi )} = o(pi − ℓi ).

(C.28)

Substituting (C.28) into (C.27) gives vi (ℓi ) = pi − ℓi + o(pi − ℓi ). This proves (C.23) and (C.24).

Combining Lemmas C.4 and C.6, together with the strict positivity and continuity of vi on compact subintervals of (0, pi ), yields the global endpoint order vi (ℓi ) ≍ min{ℓi , pi − ℓi },

ℓi ∈ (0, pi ).

(C.29)

D. Two-Sided Lundberg Bounds with Discrete Overshoot This section turns the root-based crossing exponent from Appendix C into the tail approximation used in the suboptimal-convergence calculation. For each arm i, the object is the drawdown tail F i,◦ (ℓi ) = P(Li ◦ ℓi ),

◦ ∈ {>, ≥}.

Appendix C identifies the exponent θi (ℓi ). We now use the martingale associated with this exponent to control the crossing probability itself. At the first crossing time, the walk has reached the boundary bi (ℓi ) = ∆i +βℓi plus an overshoot ri (ℓi ). The overshoot is bounded because a crossing can occur only through a single positive jump of size pi − ℓi . Optional stopping therefore gives the exact representation F i,◦ (ℓi ) =

exp{−θi (ℓi )bi (ℓi )} . E[exp{θi (ℓi )ri (ℓi )} | τi◦ (ℓi ) < ∞]

The denominator is bounded between one and exp{θi (ℓi )(pi − ℓi )}, which yields a two-sided nonasymptotic envelope for both strict and weak drawdown tails. We then specialize this envelope to the lower-endpoint regime that is relevant under large regularization. Using θi (ℓi ) =

2 ℓi + O(ℓ2i ), pi (1 − pi )

bi (ℓi ) = ∆i + βℓi ,

we obtain, uniformly for 0 < ℓi ≤ η∆ , F i,◦ (ℓi ) = exp{−λi ℓi } [1 + o(1)] ,

λi =

2∆i . pi (1 − pi )

Outside this local window, the same root-based envelope gives a super-polynomial tail bound. Thus the exact law of Li can be localized near zero and replaced, inside suitable Stieltjes integrals, by the exponential reference measure with density λi exp{−λi x}. This replacement is the input used in the subsequent product-tail and suboptimal-convergence calculations. D.1. Root-Based One-Arm Drawdown Envelope For ◦ ∈ {>, ≥}, define  τ > (ℓi ), i τi◦ (ℓi ) := τ ≥ (ℓ ), i

◦ =>, ◦ =≥ .

The corresponding drawdown tails are F i,> (ℓi ) := P(Li > ℓi ),

F i,≥ (ℓi ) := P(Li ≥ ℓi ).

By Lemma B.2, F i,◦ (ℓi ) = P(τi◦ (ℓi ) < ∞),

◦ ∈ {>, ≥}.

(D.1)

For the selected convention ◦ ∈ {>, ≥}, we use the terminal residual ri (ℓi ) already defined in (B.20), with τi (ℓi ) = τi◦ (ℓi ). Thus, on {τi◦ (ℓi ) < ∞}, the unified terminal representation (B.21) gives Ui,τi◦ (ℓi ) (ℓi ) = bi (ℓi ) + ri (ℓi ),

0 ≤ ri (ℓi ) ≤ pi − ℓi .

(D.2)

For strict crossing, 0 < ri (ℓi ) ≤ pi − ℓi , whereas for weak crossing, 0 ≤ ri (ℓi ) < pi − ℓi . The coarser bound in (D.2) is sufficient for the Lundberg bounds below. Lemma D.1 (Root-based first-passage identity). For every arm i, every ℓi ∈ (0, pi ), and every ◦ ∈ {>, ≥}, F i,◦ (ℓi ) =

exp{−θi (ℓi )bi (ℓi )} . E [exp{θi (ℓi )ri (ℓi )} | τi◦ (ℓi ) < ∞]

(D.3)

Equivalently, 1 = E exp θi (ℓi ) bi (ℓi ) + ri (ℓi ) 1{τi◦ (ℓi ) < ∞} .

(D.4)

Proof. For every arm i, every ℓi ∈ (0, pi ), and ◦ ∈ {>, ≥}, to simplify notations inside the proof, write θi := θi (ℓi ), bi := bi (ℓi ), τi := τi◦ (ℓi ). Let Fi,n := σ(Xi,1 , . . . , Xi,n ),

n ≥ 0.

Define Mi,n := exp {θi Ui,n (ℓi ) − nΛi (θi , ℓi )} ,

Mi,0 = 1.

Since θi is the Lundberg root, Λi (θi , ℓi ) = 0. Therefore, Mi,n = exp {θi Ui,n (ℓi )}. Because Ui,n (ℓi ) = Ui,n−1 (ℓi ) + Zi,n (ℓi ), and Zi,n (ℓi ) is independent of Fi,n−1 , we have E[Mi,n | Fi,n−1 ] = exp {θi Ui,n−1 (ℓi ) − (n − 1)Λi (θi , ℓi )} × E [exp {θi Zi,n (ℓi ) − Λi (θi , ℓi )}] = Mi,n−1 . Thus {Mi,n }n≥0 is a positive mean-one martingale. For a deterministic horizon N , the stopped time τi ∧ N is bounded. Optional stopping gives 1 = E[Mi,τi ∧N ]. Splitting according to whether crossing has occurred by time N , 1 = E [Mi,τi 1{τi ≤ N }] + E [Mi,N 1{τi > N }] .

(D.5)

Letting N → ∞, the first term converges by monotone convergence: E [Mi,τi 1{τi ≤ N }] → E [Mi,τi 1{τi < ∞}] .

(D.6)

For the second term, on {τi > N }, the boundary has not yet been crossed, and hence Ui,N (ℓi ) ≤ bi . Therefore, 0 ≤ Mi,N 1{τi > N } ≤ exp{θi bi }. If τi < ∞, then 1{τi > N } = 0 for all sufficiently large N . If τi = ∞, then by the strong law of large numbers and the negative drift of Ui,n (ℓi ), Ui,N (ℓi )/N → −ℓi a.s. Thus Ui,N (ℓi ) → −∞, and consequently Mi,N 1{τi > N } → 0 a.s. Dominated convergence gives E [Mi,N 1{τi > N }] → 0.

(D.7)

Combining (D.5), (D.6), and (D.7), we obtain 1 = E [Mi,τi 1{τi < ∞}] .

(D.8)

On {τi < ∞}, the terminal representation (D.2) gives Mi,τi = exp θi bi + ri (ℓi ) . Substituting this into (D.8) gives 1 = E exp θi bi + ri (ℓi ) 1{τi < ∞} , which is (D.4). Factoring out exp{θi bi }, we get 1 = exp{θi bi }E [exp{θi ri (ℓi )}1{τi < ∞}] = exp{θi bi }P(τi < ∞)E [exp{θi ri (ℓi )} | τi < ∞] . Using (D.1) and rearranging proves (D.3).

Corollary D.2 (Root-based drawdown tail envelope). For every arm i, every ℓi ∈ (0, pi ), and

every ◦ ∈ {>, ≥}, exp −θi (ℓi ) bi (ℓi ) + pi − ℓi ≤ F i,◦ (ℓi ) ≤ exp {−θi (ℓi )bi (ℓi )} .

(D.9)

In particular, the coarser but sometimes more convenient bound exp −θi (ℓi ) bi (ℓi ) + pi ≤ F i,◦ (ℓi ) ≤ exp {−θi (ℓi )bi (ℓi )}

(D.10)

also holds. Proof. By (D.2) and θi (ℓi ) > 0, 1 ≤ exp{θi (ℓi )ri (ℓi )} ≤ exp{θi (ℓi )(pi − ℓi )} on {τi◦ (ℓi ) < ∞}. Taking conditional expectations gives 1 ≤ E [exp{θi (ℓi )ri (ℓi )} | τi◦ (ℓi ) < ∞] ≤ exp{θi (ℓi )(pi − ℓi )}.

(D.11)

Substituting (D.11) into (D.3) proves (D.9). Since pi − ℓi ≤ pi , (D.10) follows immediately.

D.2. Asymptotic Closed-Form Envelope Near the Lower Endpoint We now specialize the root-based envelope to the asymptotic regime used throughout the subsequent closed-form analysis. Assumption D.3 (Asymptotic regime). As ∆1 → ∞, the regularization scale satisfies ∆i = Θ(∆1 ),

β = O(∆1 ),

i = 1, . . . , K.

(D.12)

Moreover, for a common κ ∈ (1/2, 1), every nonzero pairwise gap satisfies pi − pj = Θ(∆−κ 1 ),

1 ≤ i < j ≤ K such that pi > pj .

(D.13)

All asymptotic statements below are taken with respect to ∆1 → ∞, while K and the finitehorizon parameter T remain fixed. Condition (D.12) places the regularization margins of all arms on the same asymptotic scale. Since α = ∆1 + p1 β, it also follows that α = Θ(∆1 ). Furthermore, the standing interior condition (EC.1) implies λi :=

2∆i 2∆i = = Θ(∆1 ), 2 pi (1 − pi ) σi

i = 1, . . . , K.

For the subsequent lower-endpoint analysis, define η∆ := ∆−κ 1 .

(D.14)

Because κ ∈ (1/2, 1), η∆ → 0,

∆1 η∆ → ∞,

2 ∆ 1 η∆ → 0.

Accordingly, every nonzero pairwise gap satisfies pi − pj = Θ(η∆ ),

∆1 (pi − pj )2 → 0.

∆1 (pi − pj ) → ∞,

Since pi ≥ ϵp for every arm and η∆ → 0, we have η∆ < pi for all i = 1, . . . , K and all sufficiently large ∆1 . Define the lower-endpoint bulk window and its complementary tail window by Bi := (0, η∆ ],

Ti := (η∆ , pi ),

i = 1, . . . , K.

Lemma D.4 (Closed-form lower-endpoint envelope). Under Assumption D.3, for every arm i = 1, . . . , K and every ◦ ∈ {>, ≥}, the lower-endpoint tail satisfies ) , F i,◦ (ℓi ) = exp{−λi ℓi } 1 + O(∆1−2κ 1

ℓi ∈ Bi ,

(D.15)

uniformly over ℓi ∈ Bi . Moreover, there exists a constant ci > 0, depending only on pi , such that for all sufficiently large ∆1 , sup F i,◦ (ℓi ) ≤ exp{−ci ∆1 η∆ } = O(∆−∞ 1 ).

(D.16)

ℓi ∈Ti

Proof. We first prove the quantified bulk approximation. By Lemma C.4, θi (ℓi ) =

2 ℓi + O(ℓ2i ) σi2

as ℓi ↓ 0.

(D.17)

Since η∆ = ∆−κ 1 → 0, this expansion holds uniformly for ℓi ∈ Bi = (0, η∆ ]. Using bi (ℓi ) = ∆i + βℓi , we obtain, uniformly on Bi , 2 2 ) ℓ + O(ℓ [∆i + βℓi ] i i σi2 2∆i = 2 ℓi + O(βℓ2i ) + O(∆i ℓ2i ) + O(βℓ3i ) σi

θi (ℓi )bi (ℓi ) =

= λi ℓi + O(∆1 ℓ2i ), where we used λi = 2∆i /σi2 , ∆i = Θ(∆1 ), β = O(∆1 ), and ℓi ≤ η∆ → 0. By Lemma D.1, log F i,◦ (ℓi ) = −θi (ℓi )bi (ℓi ) − log E [exp{θi (ℓi )ri (ℓi )} | τi◦ (ℓi ) < ∞] .

(D.18)

The residual bound in (D.2) gives 0 ≤ ri (ℓi ) ≤ pi − ℓi on {τi◦ (ℓi ) < ∞}. Therefore, since θi (ℓi ) > 0, 0 ≤ log E [exp{θi (ℓi )ri (ℓi )} | τi◦ (ℓi ) < ∞] ≤ θi (ℓi )(pi − ℓi ) = O(ℓi ),

(D.19)

uniformly on Bi , where the last step uses (D.17). Combining (D.18) and (D.19), we obtain log F i,◦ (ℓi ) = −λi ℓi + O(∆1 ℓ2i + ℓi ),

ℓi ∈ Bi .

(D.20)

Consequently, for some constant Ci < ∞ independent of ∆1 , 2 sup log F i,◦ (ℓi ) + λi ℓi ≤ Ci (∆1 η∆ + η∆ ) = Ci ∆1−2κ + ∆−κ = O(∆1−2κ ), 1 1 1

ℓi ∈Bi

→ 0. Exponentiating (D.20) and where the last equality follows from κ < 1. Since κ > 1/2, ∆1−2κ 1 using exp{O(x)} = 1 + O(x) as x → 0, uniformly in ℓi ∈ Bi , yields ) , F i,◦ (ℓi ) = exp{−λi ℓi } 1 + O(∆1−2κ 1

ℓi ∈ Bi .

This proves the local approximation (D.15). It remains to prove the tail suppression on Ti = (η∆ , pi ). By Corollary D.2, F i,◦ (ℓi ) ≤ exp{−θi (ℓi )bi (ℓi )},

ℓi ∈ (0, pi ).

(D.21)

By Lemma C.3, ℓi 7→ θi (ℓi ) is increasing. Hence, for every ℓi ∈ Ti , θi (ℓi ) ≥ θi (η∆ ). By Lemma C.4, θi (η∆ ) =

(D.22)

2 2 η∆ + O(η∆ ). σi2

Since η∆ → 0, after decreasing the constant if necessary, there exists ci > 0, depending only on pi , such that θi (η∆ ) ≥ ci η∆

(D.23)

for all sufficiently large ∆1 . Moreover, bi (ℓi ) = ∆i + βℓi ≥ ∆i ≥ ∆1 ,

ℓi ∈ Ti ,

(D.24)

where the last inequality follows from ∆i = α − pi β ≥ α − p1 β = ∆1 under the ordering pi ≤ p1

and β ≥ 0. Combining (D.22), (D.23), and (D.24), we get θi (ℓi )bi (ℓi ) ≥ ci ∆1 η∆ ,

ℓi ∈ Ti .

Substituting this lower bound into (D.21) yields sup F i,◦ (ℓi ) ≤ exp{−ci ∆1 η∆ }. ℓi ∈Ti 1−κ Since η∆ = ∆−κ . Because κ < 1, ∆1−κ → ∞. Moreover, for every M > 0, 1 , we have ∆1 η∆ = ∆1 1

1−κ ∆M → 0. 1 exp{−ci ∆1 η∆ } = exp M log ∆1 − ci ∆1 Thus exp{−ci ∆1 η∆ } = O(∆−∞ 1 ), and therefore sup F i,◦ (ℓi ) ≤ exp{−ci ∆1 η∆ } = O(∆−∞ 1 ).

ℓi ∈Ti

This proves (D.16).

The lemma shows that the lower-endpoint bulk provides the effective closed-form survival envelope ) , F i,◦ (ℓi ) = exp{−λi ℓi } 1 + O(∆1−2κ 1

ℓi ∈ (0, η∆ ],

whereas the complement (η∆ , pi ) is exponentially suppressed by (D.16). This is a survival-envelope statement, not an absolute-continuity statement for the exact law of Li . The exact distribution Fi need not admit an ordinary density. We therefore use the exponential form only through the Rη following local Stieltjes replacement. In the statement below, Stieltjes integrals written as 0 ∆ are Rp over the interval [0, η∆ ], and 0 i is over [0, pi ), which is harmless because Li ∈ (0, pi ) almost surely. Corollary D.5 (Local Stieltjes replacement through a reference integrand). Let Fi denote the distribution function of Li . Let Gex ∆ : [0, pi ) → [0, ∞) be a measurable exact integrand. Suppose that there exists a nonnegative reference integrand Gref ∆ : [0, η∆ ] → [0, ∞), absolutely continuous on [0, η∆ ], such that

Z η∆ J∆ :=

Gref ∆ (x)λi exp{−λi x} dx > 0.

(D.25)

Assume the local exact-to-reference approximation Z η∆

ref Gex ∆ (x) − G∆ (x) dFi (x) = o(J∆ ),

(D.26)

the reference weighted-variation condition Gref ∆ (η∆ ) exp{−λi η∆ } +

Z η∆ 0

d ref G (x) exp{−λi x} dx ≤ CG J∆ , dx ∆

(D.27)

where CG < ∞ is independent of ∆1 , and the exact tail-localization condition E [Gex ∆ (Li )1{Li > η∆ }] = o(J∆ ). Then

Z pi

Gex ∆ (x) dFi (x) =

Z η∆

(D.28)

Gref ∆ (x)λi exp{−λi x} dx [1 + o(1)] .

(D.29)

This corollary should be read as a replacement principle for integrals, not as an absolutecontinuity statement for Fi . The exact integrand Gex ∆ may contain exact survival factors and need not be smooth. Smoothness is required only for the reference integrand Gref ∆ . In later applications, (D.26) is usually verified by a uniform local approximation ref Gex ∆ (x) = G∆ (x)(1 + o(1)),

together with the estimate

Z η∆

0 ≤ x ≤ η∆ ,

Gref ∆ (x) dFi (x) = J∆ (1 + o(1)),

which is proved inside the argument below. Proof. We write Fi (x) := P(Li ≤ x),

0 ≤ x < pi .

F i,> (x) := P(Li > x),

Since 0 < Li < pi almost surely, Fi (0) = 0, and Fi (x) = 1 − F i,> (x),

0 ≤ x < pi .

The lower-endpoint tail envelope gives, uniformly for 0 < x ≤ η∆ , F i,> (x) = exp{−λi x} [1 + ε∆ (x)] ,

sup |ε∆ (x)| = O(∆1−2κ ) = o(1). 1

0<x≤η∆

Consequently, after increasing the constant if necessary, F i,> (x) − exp{−λi x} ≤ a∆ exp{−λi x},

0 < x ≤ η∆ ,

where a∆ := C∆1−2κ = o(1). 1 We first reduce the local exact integral to the reference integral. Define ex,loc I∆ :=

Z η∆ 0

Gex ∆ (x) dFi (x),

ref,loc I∆ :=

Z η∆ 0

Gref ∆ (x) dFi (x).

(D.30)

By the local exact-to-reference approximation (D.26), ex,loc ref,loc ≤ I∆ − I∆

Z η∆

ref Gex ∆ (x) − G∆ (x) dFi (x) = o(J∆ ).

(D.31)

Thus it remains to replace the Stieltjes measure dFi by the local exponential reference measure only for the reference integrand Gref ∆ . ref,loc We now evaluate I∆ . The almost-sure support condition Li > 0 gives Fi (0) = 0. Moreover,

Gref ∆ is absolutely continuous on [0, η∆ ], so Stieltjes integration by parts gives Z η∆

ref Gref ∆ (x) dFi (x) = G∆ (η∆ )Fi (η∆ ) −

Z η∆ Fi (x) 0

d ref G (x) dx. dx ∆

Using Fi (x) = 1 − F i,> (x), we obtain Z η∆

d ref 1 − F i,> (x) G (x) dx dx ∆ 0 Z η∆ Z η∆ d ref d ref ref = Gref (η ) − G (η )F G (x) dx + G∆ (x) F i,> (x) dx (η ) − i,> ∆ ∆ ∆ ∆ ∆ ∆ dx dx 0 0 Z η∆ d ref ref ref G (x) F i,> (x) dx. = G∆ (0) − G∆ (η∆ )F i,> (η∆ ) + (D.32) dx ∆ 0

ref,loc I∆ = Gref ∆ (η∆ ) 1 − F i,> (η∆ ) −

On the other hand, the exponential reference integral J∆ can be integrated by parts in the ordinary sense: Z η∆ J∆ =

Gref ∆ (x)λi exp{−λi x} dx

0 ref = Gref ∆ (0) − G∆ (η∆ ) exp{−λi η∆ } +

Z η∆ 0

d ref G (x) exp{−λi x} dx. dx ∆

(D.33)

Subtracting (D.33) from (D.32) yields the exact difference identity ref,loc − J∆ = −Gref I∆ ∆ (η∆ ) F i,> (η∆ ) − exp{−λi η∆ } +

Z η∆ 0

d ref G∆ (x) F i,> (x) − exp{−λi x} dx. dx

Taking absolute values and using (D.30), we get ref,loc I∆ − J∆

Z η∆ d ref ref ≤ a∆ G∆ (η∆ ) exp{−λi η∆ } + G (x) exp{−λi x} dx . dx ∆ 0

By the reference weighted-variation condition (D.27), ref,loc I∆ − J∆ ≤ a∆ CG J∆ = o(J∆ ).

Therefore, ref,loc I∆ = J∆ (1 + o(1)).

(D.34)

Combining (D.31) and (D.34), we obtain ex,loc I∆ = J∆ (1 + o(1)).

(D.35)

It remains to add the complement (η∆ , pi ). Since Gex ∆ is nonnegative, Z pi

Gex ∆ (x) dFi (x) =

Z η∆

ex Gex ∆ (x) dFi (x) + E [G∆ (Li )1{Li > η∆ }] 0 ex,loc = I∆ + E [Gex ∆ (Li )1{Li > η∆ }] .

(D.36)

By the exact tail-localization condition (D.28), E [Gex ∆ (Li )1{Li > η∆ }] = o(J∆ ).

(D.37)

Substituting (D.35) and (D.37) into (D.36) gives Z pi

Gex ∆ (x) dFi (x) = J∆ (1 + o(1)).

Finally, recalling the definition of J∆ in (D.25), we obtain (D.29).

The shorthand filoc (ℓ) := λi exp{−λi ℓ} will be used only for the density of the local exponential reference measure. Thus, an integral written informally against filoc should always be read as an application of Corollary D.5, not as a claim that the exact law Fi is absolutely continuous. Corollary D.6 (Product-tail Stieltjes replacement). For every arm i and every ◦ ∈ {>, ≥}, suppose that the positive shifted levels appearing on the local window are all O(η∆ ), in the sense that (x + pr − pi ) = O(η∆ ).

sup

(D.38)

0≤x≤η∆ , r̸=i x+pr −pi >0

Then Z pi Y 0

r̸=i

Z η∆ F r,◦ (x + pr − pi ) dFi (x) = 0

   X  exp − λr (x + pr − pi )+ λi exp{−λi x} dx [1 + o(1)] ,   r̸=i

(D.39) where shifted levels x + pr − pi ≤ 0 contribute survival factor one.

Proof. We apply Corollary D.5 with Gex ∆ (x) =

F r,◦ (x + pr − pi ),

(D.40)

r̸=i

    X , Gref (x) = exp − λ (x + p − p ) r r i + ∆   r̸=i

and Z η∆ J∆ = 0

    X exp − λr (x + pr − pi )+ λi exp{−λi x} dx.  

(D.41)

r̸=i

We now verify the three requirements in Corollary D.5: the local exact-to-reference approximation, the weighted-variation condition for Gref ∆ , and the exact tail-localization condition. First consider the local window 0 ≤ x ≤ η∆ . For any r ̸= i, if x + pr − pi ≤ 0, then the corresponding exact survival factor is one by the nonpositive-level convention, and the corresponding exponential reference factor is also one: F r,◦ (x + pr − pi ) = 1 = exp {−λr (x + pr − pi )+ } . If x + pr − pi > 0, then by (D.38) the shifted level lies in the lower-endpoint region, uniformly over 0 ≤ x ≤ η∆ and r ̸= i. Hence the lower-endpoint tail envelope gives ) , F r,◦ (x + pr − pi ) = exp {−λr (x + pr − pi )} 1 + O(∆1−2κ 1 uniformly over all such x and r. Since K is fixed and κ > 1/2, multiplying the finitely many factors gives Y r̸=i

   X  ) F r,◦ (x + pr − pi ) = exp − λr (x + pr − pi )+ 1 + O(∆1−2κ 1   r̸=i

= Gref ∆ (x) [1 + o(1)] ,

(D.42)

uniformly for 0 ≤ x ≤ η∆ . We next check the weighted-variation condition for Gref ∆ . The map x 7→ (x + pr − pi )+ is absolutely continuous. Therefore Gref ∆ is absolutely continuous on [0, η∆ ], and for almost every

x ∈ [0, η∆ ],     X d d ref λr (x + pr − pi )+ G∆ (x) = exp −   dx dx r̸=i       X X   λr (x + pr − pi )+ ≤ λr exp −   r̸=i r̸=i   X = λr  Gref ∆ (x). r̸=i

Multiplying by exp{−λi x} and integrating gives Z η∆ 0

 d ref G (x) exp{−λi x} dx ≤  dx ∆

 X

Z η∆

λr 

P Gref ∆ (x) exp{−λi x} dx =

r̸=i

r̸=i λr

λi

J∆ .

(D.43)

P Since K is fixed and λr = Θ(∆1 ) for every r, the ratio ( r̸=i λr )/λi is uniformly bounded. The endpoint term in the weighted-variation condition is controlled by the same reference interef gral. Since λi η∆ → ∞, for all sufficiently large ∆1 , λ−1 i ≤ η∆ . The function x 7→ G∆ (x) exp{−λi x}

is nonincreasing on [0, η∆ ]. Hence Z η∆ J∆ =

Gref ∆ (x)λi exp{−λi x} dx ≥ λi

Z η∆ η∆ −λ−1 i

ref Gref ∆ (x) exp{−λi x} dx ≥ G∆ (η∆ ) exp{−λi η∆ }.

(D.44) Combining (D.43) and (D.44), we obtain Gref ∆ (η∆ ) exp{−λi η∆ } +

Z η∆ 0

d ref G (x) exp{−λi x} dx ≤ CJ∆ . dx ∆

(D.45)

Thus the weighted-variation condition of Corollary D.5 is satisfied. We now verify the local exact-to-reference condition. By (D.42), Z η∆

ref Gex ∆ (x) − G∆ (x)

Z η∆ dFi (x) ≤ o(1)

Gref ∆ (x) dFi (x).

(D.46)

Applying the local Stieltjes replacement estimate (D.34) from the proof of Corollary D.5 to the present reference integrand Gref ∆ , with J∆ defined by (D.41), gives Z η∆

Gref ∆ (x) dFi (x) = J∆ [1 + o(1)] .

Substituting (D.47) into (D.46), we get Z η∆

ref Gex ∆ (x) − G∆ (x) dFi (x) = o(J∆ ).

This is exactly the local exact-to-reference approximation required in Corollary D.5.

(D.47)

It remains to prove the exact tail-localization condition. Since each one-arm survival factor is at most one, Z

F r,◦ (x + pr − pi ) dFi (x) ≤

F r,◦ (pr − pi ) dFi (x).

(η∆ ,pi ) r̸=i pr >pi

(η∆ ,pi ) r̸=i

Indeed, if pr > pi , then x + pr − pi ≥ pr − pi for x > η∆ , and the survival function is nonincreasing; if pr ≤ pi , the corresponding factor is bounded by one. By (D.38), every positive gap pr − pi with pr > pi is O(η∆ ). Hence the lower-endpoint tail envelope gives F r,◦ (pr − pi ) ≤ C exp {−λr (pr − pi )} ,

pr > pi .

Moreover, the one-arm tail suppression for Li gives P(Li > η∆ ) ≤ exp{−c∆1 η∆ } = O(∆−∞ 1 ). Therefore        X  Y F r,◦ (x + pr − pi ) dFi (x) ≤ C exp − λr (pr − pi ) exp{−c∆1 η∆ }.   (η∆ ,pi ) r̸=i    r̸=i 

(D.48)

pr >pi

We now lower-bound J∆ by the same better-arm exponential factor. Fix a small constant a > 0. Since η∆ ≫ ∆−1 1 , we have a/∆1 ≤ η∆ for all sufficiently large ∆1 . For 0 ≤ x ≤ a/∆1 , X

λr (x + pr − pi )+ ≤

r̸=i

λr (pr − pi ) + x

r̸=i pr >pi

λr ≤

r̸=i

λr (pr − pi ) + C ′ a,

r̸=i pr >pi

because K is fixed and λr = Θ(∆1 ). Also λi = Θ(∆1 ). Hence    X  J∆ = exp − λr (x + pr − pi )+ λi exp{−λi x} dx   0 r̸=i   Z a/∆1  X  ≥ exp − λr (x + pr − pi )+ λi exp{−λi x} dx   0 r̸=i        X  ′ ≥ c exp − λr (pr − pi ) .      r̸=i  Z η∆

pr >pi

(D.49)

Dividing (D.48) by (D.49), we obtain Z

F r,◦ (x + pr − pi ) dFi (x)

(η∆ ,pi ) r̸=i

J∆

≤ C exp{−c∆1 η∆ }/c′ = o(1).

This proves the exact tail-localization condition required in Corollary D.5. All assumptions of Corollary D.5 have now been verified for the choices (D.40)–(D.41). Therefore,

Z pi Y 0

F r,◦ (x + pr − pi ) dFi (x) = J∆ [1 + o(1)] .

r̸=i

Substituting the expression for J∆ from (D.41) gives (D.39).

E. Asymptotic Suboptimal-Convergence Formula This section derives an asymptotic closed-form expression for the probability that a suboptimal arm becomes the eventual winner. The proof starts from the score-minimum sandwich, which reduces suboptimal convergence to comparisons among independent potential score minima. This representation separates the constraints imposed by arms with larger means from those imposed by arms with smaller means, and leads to a Stieltjes integral formula for the winner event in terms of the centered score-minimum variables. The main asymptotic step is to localize this Stieltjes integral near the lower endpoint of the candidate winning arm. In the large-regularization regime, the relevant centered score minimum concentrates on this local scale under the winner comparison, while the complementary region is negligible relative to the local contribution. On the local scale, the one-arm Lundberg envelopes reduce uniformly to elementary exponential forms. The resulting reference integral is then evaluated by splitting the positive-part terms according to the ordered gaps between arm means, yielding the desired asymptotic suboptimal-convergence formula with relative 1 + o(1) error. E.1. Root-Based Score-Minimum Representation We first express the absorbing probability through the arm-wise centered score-minimum variables. Recall that Mk = pk − Lk , k = 1, . . . , K. The outer Stieltjes measure below is the distribution Fi of the centered score-minimum variable Li of the candidate absorbing arm i. On the candidate branch Qi , the relevant centered score minimum satisfies Li ∈ (0, pi ) a.s. on Qi . Thus the outer Stieltjes integrals are taken over [0, pi ). Proposition E.1 (Root-based score-minimum envelope for Qi ). For every arm i, adopt the following conventions. Whenever ℓi + pj − pi ≤ 0, set θj (ℓi + pj − pi ) = 0. Whenever 0 < ℓi + pj − pi < pj , θj (ℓi + pj − pi ) denotes the unique positive solution of qj exp{θ(pi − ℓi )} + pj exp{−θ(qi + ℓi )} = 1.

Then     X exp − ∆i + βℓi + pi − ℓi θj (ℓi + pj − pi ) dFi (ℓi )   [0,pi )

j̸=i

≤P(Qi )

(E.1)

  Z   X ≤ exp − ∆i + βℓi θj (ℓi + pj − pi ) dFi (ℓi ).   [0,pi ) j̸=i

Proof. Recall the strict and weak score-minimum winner events Wi> = {Mi > Mj , ∀j ̸= i} ,

Wi≥ = {Mi ≥ Mj , ∀j ̸= i} .

By Lemma B.1, Wi> ⊆ Qi ⊆ Wi≥ .

(E.2)

Using Mk = pk − Lk , for every j ̸= i, Mi > Mj ⇐⇒ pi − Li > pj − Lj ⇐⇒ Lj > Li + pj − pi , and similarly Mi ≥ Mj ⇐⇒ Lj ≥ Li + pj − pi . Therefore, Wi> = {Lj > Li + pj − pi , ∀j ̸= i} ,

Wi≥ = {Lj ≥ Li + pj − pi , ∀j ̸= i} .

Recall the strict and weak one-arm tails F j,> (x) := P(Lj > x),

F j,≥ (x) := P(Lj ≥ x).

When the shifted level x = ℓi + pj − pi is nonpositive, the comparison Lj > x or Lj ≥ x is automatic for the score-minimum event under consideration. Thus both strict and weak tail factors are taken to be one: x ≤ 0.

F j,> (x) = F j,≥ (x) = 1,

Equivalently, a nonpositive shifted level contributes no exponential penalty, and we encode this by the convention θj (x) = 0 for x ≤ 0. Because the potential reward streams are independent across arms, the centered score-minimum variables L1 , . . . , LK are independent. Conditioning on Li = ℓi , we obtain P(Wi> ) =

Z P (Lj > ℓi + pj − pi , ∀j ̸= i) dFi (ℓi ) = [0,pi )

[0,pi ) j̸=i

F j,> (ℓi + pj − pi ) dFi (ℓi ). (E.3)

Likewise, P(Wi≥ ) =

Z P (Lj ≥ ℓi + pj − pi , ∀j ̸= i) dFi (ℓi ) =

F j,≥ (ℓi + pj − pi ) dFi (ℓi ). (E.4)

[0,pi ) j̸=i

[0,pi )

We now apply the one-arm root-based envelopes. Since ℓi ∈ [0, pi ), every shifted level satisfies ℓi + pj − pi < pj . Thus the upper endpoint never occurs. When ℓi + pj − pi ≤ 0, the tail factor is one and the convention θj (ℓi + pj − pi ) = 0 makes the corresponding exponential factor equal to one. Now consider the nontrivial case 0 < ℓi + pj − pi < pj . The Lundberg root of arm j at level ℓi + pj − pi is defined by Λj (θj (ℓi + pj − pi ), ℓi + pj − pi ) = 0. Using the explicit CGF, this equation becomes qj exp {θj (ℓi + pj − pi ) [pj − (ℓi + pj − pi )]} + pj exp {−θj (ℓi + pj − pi ) [qj + ℓi + pj − pi ]} = 1. Since pj − (ℓi + pj − pi ) = pi − ℓi , qj + ℓi + pj − pi = qi + ℓi , this reduces to qj exp{θj (ℓi + pj − pi )(pi − ℓi )} + pj exp{−θj (ℓi + pj − pi )(qi + ℓi )} = 1. Thus θj (ℓi + pj − pi ) is precisely the unique positive solution specified in Proposition E.1. For positive shifted levels, Corollary D.2 gives F j,> (ℓi + pj − pi ) ≥ exp {−θj (ℓi + pj − pi ) [bj (ℓi + pj − pi ) + pj − (ℓi + pj − pi )]} ,

(E.5)

F j,≥ (ℓi + pj − pi ) ≤ exp {−θj (ℓi + pj − pi )bj (ℓi + pj − pi )} . The shifted affine boundary simplifies exactly: bj (ℓi + pj − pi ) = ∆j + β(ℓi + pj − pi ) = α − pj β + βℓi + βpj − βpi = α − pi β + βℓi = ∆i + βℓi . Moreover, pj − (ℓi + pj − pi ) = pi − ℓi .

(E.6)

Combining (E.5)–(E.6), and using the zero-root convention for nonpositive shifted levels, yields Y j̸=i

    X F j,> (ℓi + pj − pi ) ≥ exp − ∆i + βℓi + pi − ℓi θj (ℓi + pj − pi ) ,   j̸=i

(E.7)

Y j̸=i

    X F j,≥ (ℓi + pj − pi ) ≤ exp − ∆i + βℓi θj (ℓi + pj − pi ) .  

(E.8)

j̸=i

Substituting (E.7) into (E.3), substituting (E.8) into (E.4), and using (E.2), proves (E.1).

E.2. Asymptotic Closed-Form Evaluation We now evaluate the score-minimum Stieltjes representation in Proposition E.1 under Assumption D.3. Consider a candidate absorbing arm i. On the local window 0 ≤ ℓi ≤ η∆ , the assumed pairwise-gap scale ensures that every positive shifted level ℓi + pr − pi , r ̸= i, remains within the lower-endpoint region. Therefore, the local root expansion in Lemma C.4 and the tail envelope in Lemma D.4 apply to all shifted levels appearing in the local Stieltjes representation. Proposition E.2 (Macroscopic suboptimal-convergence formula). Under Assumption D.3, for every arm i ≥ 2 with pi < p1 , P(Qi ) =

K X 1 m=i

( exp −

m X

(

1 − exp −

λh δhm

m X

! λh

)# δm,m+1

(1 + o(1)),

(E.9)

h=1

where empty sums are interpreted as zero, δhh := 0, and δK,K+1 := ∞. For m = K, the second exponential in the bracket is interpreted as zero. Proof. By the score-minimum sandwich and the Stieltjes representation in Proposition E.1, for ◦ ∈ {>, ≥}, P(Wi◦ ) =

F j,◦ (ℓi + pj − pi ) dFi (ℓi ),

[0,pi ) j̸=i

and P(Wi> ) ≤ P(Qi ) ≤ P(Wi≥ ).

(E.10)

We first evaluate P(Wi◦ ). For 0 ≤ ℓi ≤ η∆ , the pairwise-gap scale in (D.13) ensures that every positive shifted level ℓi + pj − pi is O(η∆ ). Hence Corollary D.6 gives P(Wi◦ ) =

Z η∆ 0

   X  exp − λj (ℓi + pj − pi )+ λi exp{−λi ℓi } dℓi (1 + o(1)).  

(E.11)

j̸=i

Using the ordering p1 ≥ · · · ≥ pK , the shifted positive parts are  ℓi + δji , j < i, (ℓi + pj − pi )+ = (ℓ − δ ) , j > i. i ij +

(E.12)

Substituting (E.12) into (E.11), we obtain        X  Z η∆   X X P(Wi◦ ) = λi exp − λj δji exp − λi + λ j  ℓi − λj (ℓi − δij )+ dℓi (1 + o(1)).   0   j<i

j<i

j>i

We next extend the upper integration limit from η∆ to infinity. By the standing interior condition (EC.1) and the regularization scale (D.12), uniformly over k ∈ [K], λk = 2∆k /σk2 = Θ(∆1 ). P Hence λi + j<i λj = Θ(∆1 ). Since (ℓi − δij )+ ≥ 0,         Z ∞     X X X exp − λi + λ j  ℓi − λj (ℓi − δij )+ dℓi ≤ exp − λi + λj  ℓi dℓi     η∆ η∆ j<i j>i j<i n o P exp − λi + j<i λj η∆ P = λi + j<i λj

Z ∞

≤ C∆−1 1 exp{−∆1 η∆ /C}. Conversely, fix a small constant a > 0. Since η∆ = ∆−κ 1 by (D.14) and κ < 1, we have a/∆1 ≤ η∆ for all sufficiently large ∆1 . Hence Z η∆ 0

        Z a/∆1     X X X X exp − λi + λj  ℓi − λj (ℓi − δij )+ dℓi ≥ exp − λi + λj + λj  ℓi dℓi     0 j<i

j>i

j<i

j>i

≥ c∆−1 1 . Therefore, because ∆1 η∆ → ∞,       X X exp − λi + λj  ℓi − λj (ℓi − δij )+ dℓi   η∆ j<i j>i     Z η∆   X X λ j  ℓi − λj (ℓi − δij )+ dℓi . =o(1) exp − λi +   0 Z ∞

j<i

j>i

Consequently,        X Z ∞   X X P(Wi◦ ) = λi exp − λj δji exp − λi + λj  ℓi − λj (ℓi − δij )+ dℓi (1 + o(1)).   0   j<i

j<i

j>i

(E.13) It remains to evaluate the elementary integral. Because the arms are ordered by nonincreasing means, for the arm i under consideration, the gaps δik = pi − pk , k > i, are nondecreasing in k.

With the endpoint convention δii = 0 and δi,K+1 = ∞, we have 0 = δii ≤ δi,i+1 ≤ · · · ≤ δiK ≤ δi,K+1 = ∞. Split [0, ∞) according to these breakpoints:

[0, ∞) =

K [

[δim , δi,m+1 ).

m=i

If consecutive arms have equal means, then the corresponding breakpoints coincide and the resulting interval is empty; such intervals contribute zero to the piecewise integral. For m ∈ {i, . . . , K} and ℓi ∈ [δim , δi,m+1 ), X

λj (ℓi − δij )+ =

j>i

m X

λk (ℓi − δik ),

k=i+1

and therefore  − λi +

 X

λj  ℓi −

j<i

λj (ℓi − δij )+ = −

j>i

m X

! λk

ℓi +

k=1

λk δik .

k=i+1

Thus       X X   exp − λi + λj ℓi − λj (ℓi − δij )+ dℓi   0 j<i j>i ! ) ( )Z ( m m K δi,m+1 X X X exp − λk ℓi dℓi = exp λk δik

Z ∞

m=i

k=i+1

δim

k=1

" ( ! ) ( ! )# Pm m m K X X X exp k=i+1 λk δik Pm exp − λk δim − exp − λk δi,m+1 . = k=1 λk m=i

k=1

(E.14)

k=1

For m = K, the second exponential in the bracket is interpreted as zero because δi,K+1 = ∞. Substituting (E.14) into (E.13), we get, for both ◦ => and ◦ =≥,   Pm K  X X exp λk δik ◦ Pk=i+1 P(Wi ) = λi exp − λj δji m   k=1 λk j<i m=i " ( ! ) ( ! )# m m X X × exp − λk δim − exp − λk δi,m+1 (1 + o(1)). k=1

(E.15)

k=1

We now simplify the common leading expression in (E.15). For m ∈ {i, . . . , K}, consider first the first exponential term inside the bracket of (E.15). Its

total exponent, including the prefactor outside the bracket, is −

m X

λj δji +

j<i

λk δik −

k=i+1

m X

! λh

δim .

m X

h=1

Equivalently, this is the negative of Ai,m :=

λj δji −

j<i

m X

λk δik +

k=i+1

λh

δim .

h=1

We simplify Ai,m . For every j < i, δji + δim = (pj − pi ) + (pi − pm ) = pj − pm = δjm . For every k = i + 1, . . . , m, δim − δik = (pi − pm ) − (pi − pk ) = pk − pm = δkm . Therefore, Ai,m =

X j<i

X j<i m X

m X

λj (δji + δim ) + λi δim +

λk (δim − δik )

k=i+1

λj δjm + λi δim +

m X

λk δkm

k=i+1

λh δhm ,

h=1

Hence the first exponential term in the bracket contributes exp {−

h=1 λh δhm }.

Now consider the second exponential term in the bracket of (E.15). For m < K, its total exponent, including the same prefactor outside the bracket, is the negative of Bi,m :=

λj δji −

j<i

m X k=i+1

λk δik +

m X

! λh

δi,m+1 .

h=1

The same algebra gives, for j < i, δji + δi,m+1 = δj,m+1 , and, for k = i + 1, . . . , m, δi,m+1 − δik = δk,m+1 . Thus Bi,m = =

X j<i m X h=1

λj δj,m+1 + λi δi,m+1 +

m X k=i+1

λh δh,m+1 .

λk δk,m+1

Since h ≤ m, we have δh,m+1 = δhm + δm,m+1 . Therefore, Bi,m =

m X

λh δhm +

h=1

m X

! λh

δm,m+1 .

h=1

For m = K, the second exponential term is interpreted as zero, which is equivalent to the convention δK,K+1 = ∞. Substituting these exponent identities into (E.15), we obtain the rate-exact compact form P(Wi◦ ) =

K X

λi Pm

m=i

h=1 λh

( exp −

m X

) λh δhm

(

× 1 − exp −

h=1

m X

! λh

δm,m+1

(1 + o(1)). (E.16)

h=1

We next simplify the prefactor λi /

h=1 λh . By (D.13), uniformly over the finitely many indices

h ≤ m, |ph − pi | = O(η∆ ) = o(1), where the conclusion is immediate when ph = pi . Moreover, σh2 − σi2 = ph (1 − ph ) − pi (1 − pi ) = (ph − pi ) 1 − (ph + pi ) . By the standing interior condition (EC.1), σh2 − σi2 ≤ |ph − pi | = O(η∆ ), while σi2 ≥ ϵp (1 − ϵp ) > 0. Consequently, σh2 = 1 + O(η∆ ) = 1 + o(1), σi2 uniformly over h ≤ m. Similarly, ∆h − ∆i = −(ph − pi )β. By (D.12), ∆i = Θ(∆1 ),

β = O(∆1 ).

Therefore, |ph − pi |β ∆h −1 = = O(η∆ ) = o(1), ∆i ∆i uniformly over h ≤ m. Combining the preceding estimates gives λh ∆h σi2 = = 1 + O(η∆ ) = 1 + o(1). λi ∆i σh2

Hence, λh = λi (1 + o(1)), Because K is fixed,

m X

h = 1, . . . , m.

λh = mλi (1 + o(1)).

h=1

Consequently, λ Pm i

h=1 λh

1 (1 + o(1)). m

(E.17)

Substituting (E.17) into (E.16) yields P(Wi◦ ) =

K X 1 m=i

( exp −

m X h=1

) λh δhm

(

× 1 − exp −

m X

! λh

δm,m+1

(1 + o(1)).

(E.18)

h=1

The simplified expression in (E.18) holds for both ◦ => and ◦ =≥. This is because Corollary D.6 applies to the strict and weak Stieltjes integrals in the same way: both integrals are localized on the same lower-endpoint window, both exact product tails are replaced by the same exponential reference product, and the contribution outside the localized window is negligible. Consequently, P(Wi≥ ) = P(Wi> )(1 + o(1)), and hence P(Wi≥ ) − P(Wi> ) = o P(Wi> ) .

(E.19)

Combining (E.18) and (E.19) with the sandwich (E.10) proves (E.9).

F. Conditional Abandonment Costs Given the Absorbing Arm This section estimates the finite-horizon abandonment costs incurred before a nonabsorbing arm is discarded. Consider any two distinct arms i ̸= j. On the event Qi , arm i is the unique absorbing arm, while arm j is eventually abandoned. Conditioning on the realized centered score minimum Li = ℓi of the absorbing arm fixes the score floor pi − ℓi . The evolution of arm j, relative to this floor, can then be compared with a one-arm boundary-crossing problem. This comparison gives an upper representation for the capped count min{T, Nj }, but only after using a strict crossing convention; equality with the absorbing floor may still allow tie-breaking, and is therefore kept as a finite-horizon correction. The first step is to derive a pairwise winner-conditioned Stieltjes upper bound. The strict scoreminimum factors define the denominator, while the numerator uses a strict-crossing time only for the abandoned arm j and keeps weak winner factors for all remaining competitors. The only equality correction that must be retained is the pairwise boundary event Mj = Mi . This keeps the conditioning on Qi explicit and avoids treating the adaptive count Nj as an exact one-arm hitting

time. The second step is to bound the strict capped first-passage envelope pointwise. When pi > pj , the comparison drift is δij − ℓi , so the critical interface ℓi = δij separates a positive-drift region from a negative-drift region. The positive-drift side is controlled by a direct Wald bound, the negativedrift side by a tilted Lundberg–Wald bound, and the interface itself only by the finite-horizon cap T . When pj > pi , the comparison walk has negative drift for every ℓi > 0, so the tilted Lundberg–Wald bound applies throughout. When pi = pj , no nonzero drift scale is available, and the finite-horizon cap gives the only general bound. The final step is asymptotic. Under the macroscopic lower-endpoint regime, the centered score minimum Li is localized through winner-weighted Stieltjes ratios rather than through a direct conditional law of Li given Qi . This localization turns the strict root-based Stieltjes upper envelope into explicit closed-form conditional-abandonment bounds. The equality correction needed for the abandoned arm j is kept in pairwise form. More precisely, only the boundary event Mj = Mi can invalidate the strict-crossing upper bound for Nj . This pairwise boundary event is shown to be negligible on the suboptimal-convergence scale of arm j, which is essential when the absorbing arm is optimal. The optimal absorbing branches are then refined separately, because they generate the only transient correction that remains visible in the final regret upper envelope. F.1. Winner-Conditioned Capped Boundary-Crossing Upper Representation For any two distinct arms i ̸= j, on Qi , arm i is eventually pulled forever and arm j is eventually abandoned. For finite-horizon regret, we only need the capped count min{T, Nj }. The goal of this subsection is to dominate this capped count by a one-arm comparison time and then integrate this domination over the centered score minimum Li of the absorbing arm. Recall that Mi = pi − Li . Condition on Li = ℓi . The corresponding score floor is pi − ℓi . Define the comparison walk of arm j against this fixed floor by Uj|i,n (ℓi ) := (pi − ℓi )n − Sj (n),

n ≥ 1,

(F.1)

with boundary height bi (ℓi ) := α − (pi − ℓi )β = ∆i + βℓi .

(F.2)

We use two comparison times. The weak first-passage time is ≥ τj|i (ℓi ) := inf n ≥ 1 : Uj|i,n (ℓi ) ≥ bi (ℓi ) , which is the first potential pull count n for which the regularized score of arm j is no larger than pi − ℓi . The strict first-passage time is > τj|i (ℓi ) := inf n ≥ 1 : Uj|i,n (ℓi ) > bi (ℓi ) ,

(F.3)

which is the first potential pull count n for which the regularized score of arm j is strictly below

pi − ℓi . The strict time is the one that can be used to upper-bound the actual abandoned count. Equality with the floor may still allow tie-breaking to select arm j, so the weak time alone is not a pathwise upper bound on Nj . The drift of the comparison walk is dj|i (ℓi ) := E Uj|i,n (ℓi ) − Uj|i,n−1 (ℓi ) = pi − pj − ℓi . Thus, if pi > pj , then dj|i (ℓi ) = δij − ℓi , so the drift changes sign at ℓi = δij . If pj > pi , then dj|i (ℓi ) = −(δji + ℓi ) < 0, so the comparison is always in the negative-drift regime. We now derive the pathwise capped envelope. For the ordered pair (i, j), define the pairwise equality part of the score-minimum comparison by Eij= := Wi≥ ∩ {Mj = Mi }. This is the only boundary event relevant for the abandoned count of arm j. Indeed, equality between Mi and some other competitor Mr , r ̸= j, does not prevent the strict-crossing argument from upper-bounding Nj . Since Qi ⊆ Wi≥ , on Qi either Mj < Mi or Mj = Mi . On the event Mj < Mi , the strict > comparison with arm j is available. In particular, if the actual trajectory ever reaches the τj|i (Li )-

th potential pull of arm j, then arm j’s score is strictly below Mi , while arm i’s current score is always at least its potential minimum Mi . Hence arm j can never again be a maximizer after that strict crossing. On the pairwise equality event Mj = Mi , we use only the finite-horizon cap. Therefore, > min{T, Nj }1Qi ≤ min{T, τj|i (Li )}1W ≥ ∩{M <M } + T 1Eij= . i

The factor T is kept explicitly as the finite-horizon cap. Throughout the asymptotic estimates below, the limit is taken only in the regularization scale ∆1 → ∞. The horizon T is treated as an external finite-horizon parameter and is not absorbed into any o(·) term. Conditioning on Li = ℓi and using independence of the potential reward streams, the numerator satisfies Z E[min{T, Nj }1Qi ] ≤ [0,pi )

K h i Y > > E min{T, τj|i (ℓi )}1{τj|i (ℓi ) < ∞} F r,≥ (ℓi + pr − pi ) dFi (ℓi ) + T P(Eij= ). r=1 r̸=i,j

(F.4) > Here the strict event for arm j is contained in the one-arm factor 1{τj|i (ℓi ) < ∞}, while the

remaining competitors enter only through weak winner factors. For the denominator, the strict side of the score-minimum sandwich gives P(Qi ) ≥ P(Wi> ) =

[0,pi ) r̸=i

F r,> (ℓi + pr − pi ) dFi (ℓi ).

(F.5)

Combining (F.4) and (F.5), we obtain the pairwise winner-conditioned capped upper representation Z [0,pi )

K h i Y > > E min{T, τj|i (ℓi )}1{τj|i (ℓi ) < ∞} F r,≥ (ℓi + pr − pi ) dFi (ℓi ) + T P(Eij= ) r=1 r̸=i,j P(Wi> )

E[min{T, Nj } | Qi ] ≤

. (F.6)

This representation is an upper envelope for the capped abandonment cost. F.2. Pointwise Capped First-Passage Envelopes We now bound the one-arm capped factor appearing in (F.6). Consider any i ̸= j and ℓi ∈ (0, pi ). > Throughout this subsection, τj|i (ℓi ), Uj|i,n (ℓi ), and bi (ℓi ) are defined by (F.1), (F.2), and (F.3).

On the strict crossing event, the terminal state has the bounded-overshoot form > Uj|i,τ > (ℓi ) (ℓi ) = bi (ℓi ) + rj|i (ℓi ), j|i

> 0 < rj|i (ℓi ) ≤ pi − ℓi .

(F.7)

> The coarse bound rj|i (ℓi ) ≤ pi − ℓi is the only overshoot information needed below.

When the comparison drift is negative, the relevant shifted level for arm j is y := ℓi + pj − pi . The negative-drift regime is exactly 0 < y < pj . In this case, let θj (y) > 0 be the Lundberg root of arm j at level y, i.e., qj exp{θj (y)(pj − y)} + pj exp{−θj (y)(qj + y)} = 1.

(F.8)

The associated tilted drift is vj (y) := ∂θ Λj (θj (y), y) = qj (pj − y) exp{θj (y)(pj − y)} − pj (qj + y) exp{−θj (y)(qj + y)} = pj − y − pj exp{−θj (y)(qj + y)}. The last equality follows from the Lundberg balance (F.8). In particular, vj (y) > 0 by Corollary C.2. Since bj (y) = ∆j + βy = ∆i + βℓi = bi (ℓi ), > the comparison time τj|i (ℓi ) is the strict first-passage time of the one-arm crossing problem for arm

j at shifted level y. Lemma F.1 (Pointwise capped first-passage envelope). For every i ̸= j, every ℓi ∈ (0, pi ), and every finite horizon T , h i > > E min{T, τj|i (ℓi )}1{τj|i (ℓi ) < ∞} ≤ Hj|i,T (ℓi ),

(F.9)

where Hj|i,T is defined as follows. If pi > pj , then  bi (ℓi ) + pi − ℓi   , min T,    δij − ℓi     Hj|i,T (ℓi ) := T,       bi (ℓi ) + pi − ℓi   , min T, exp{−θj (ℓi − δij )bi (ℓi )} vj (ℓi − δij )

0 < ℓi < δij , ℓi = δij , δij < ℓi < pi .

If pj > pi , then

bi (ℓi ) + pi − ℓi Hj|i,T (ℓi ) := min T, exp{−θj (ℓi + δji )bi (ℓi )} vj (ℓi + δji )

0 < ℓi < pi .

If pi = pj , then Hj|i,T (ℓi ) := T,

0 < ℓi < pi .

Proof. We consider the three cases separately. First suppose pi > pj and 0 < ℓi < δij . Then the comparison drift is positive: dj|i (ℓi ) = δij − ℓi > 0. > By the strong law, τj|i (ℓi ) < ∞ almost surely. Since the increments are bounded and have strictly

positive mean δij − ℓi , this first-passage time has finite expectation. Wald’s identity, together with the terminal bound (F.7), therefore gives h i > (δij − ℓi ) E[τj|i (ℓi )] = E Uj|i,τ > (ℓi ) (ℓi ) ≤ bi (ℓi ) + pi − ℓi . j|i

Therefore

h i bi (ℓi ) + pi − ℓi > E min{T, τj|i (ℓi )} ≤ min T, . δij − ℓi

At the interface pi > pj and ℓi = δij , the comparison drift is zero. We do not use a zero-drift hitting-time expectation. The finite-horizon cap gives directly h i > > E min{T, τj|i (δij )}1{τj|i (δij ) < ∞} ≤ T. It remains to treat the negative-drift case 0 < y = ℓi + pj − pi < pj . This includes ℓi > δij when pi > pj , all ℓi ∈ (0, pi ) when pj > pi , and all ℓi > 0 when pi = pj . The increment distribution of Uj|i,n (ℓi ) is the one-arm crossing distribution for arm j at level y. Under the tilted measure generated by the martingale exp{θj (y)Uj|i,n (ℓi )}, the comparison walk has positive drift vj (y). Since the tilted increments remain bounded, the first-passage time has finite expectation under the

tilted measure. Wald’s identity and (F.7) therefore give h i b (ℓ ) + p − ℓ i i i i > . Eθ τj|i (ℓi ) ≤ vj (y) Changing measure back at the crossing time gives oi h i h n > > > E τj|i (ℓi )1{τj|i (ℓi ) < ∞} = Eθ τj|i (ℓi ) exp −θj (y)Uj|i,τ > (ℓi ) (ℓi ) j|i h i θ > ≤ exp{−θj (y)bi (ℓi )}E τj|i (ℓi ) ≤ exp{−θj (y)bi (ℓi )}

bi (ℓi ) + pi − ℓi . vj (y)

Since the capped expectation is also at most T , we obtain h i bi (ℓi ) + pi − ℓi > > E min{T, τj|i (ℓi )}1{τj|i (ℓi ) < ∞} ≤ min T, exp{−θj (y)bi (ℓi )} . vj (y) For pi = pj , the simpler bound Hj|i,T (ℓi ) = T is weaker but sufficient and no shifted-level notation is needed. In the two cases where the negative-drift tilted estimate is used, the shifted level is y = ℓi − δij when pi > pj and ℓi > δij , and y = ℓi + δji when pj > pi . Combining the positive-drift, interface, and negative-drift estimates proves (F.9).

Proposition F.2 (Root-based integrated capped upper envelope). For every i ̸= j and every finite horizon T , Z Hj|i,T (ℓi ) [0,pi )

E[min{T, Nj } | Qi ] ≤

K Y

F r,≥ (ℓi + pr − pi ) dFi (ℓi ) + T P(Eij= )

r=1 r̸=i,j

P(Wi> )

(F.10)

Moreover, the pairwise equality probability admits the Stieltjes representation P(Eij= ) =

K Y F j,≥ (ℓi + pj − pi ) − F j,> (ℓi + pj − pi ) × F r,≥ (ℓi + pr − pi ) dFi (ℓi ).

[0,pi )

(F.11)

r=1 r̸=i,j

Shifted levels below zero contribute equal strict and weak tail factors, and therefore make zero contribution to the difference in (F.11). Proof. By (F.6), it is enough to bound the one-arm capped factor h i > > E min{T, τj|i (ℓi )}1{τj|i (ℓi ) < ∞} . Lemma F.1 gives the pointwise bound by Hj|i,T (ℓi ). Substituting this pointwise bound into (F.6)

proves (F.10). It remains to derive (F.11). By definition, Eij= = Wi≥ ∩ {Mj = Mi }. Conditioning on Li = ℓi , the event Mj = Mi is equivalent to Lj = ℓi + pj − pi . The remaining competitors must satisfy the weak winner inequalities Lr ≥ ℓi + pr − pi ,

r ̸= i, j.

By independence of the potential reward streams, we obtain P(Eij= ) =

Z P (Lj = ℓi + pj − pi ) [0,pi )

Z =

K Y

F r,≥ (ℓi + pr − pi ) dFi (ℓi )

r=1 r̸=i,j K Y F j,≥ (ℓi + pj − pi ) − F j,> (ℓi + pj − pi ) × F r,≥ (ℓi + pr − pi ) dFi (ℓi ).

[0,pi )

r=1 r̸=i,j

This proves (F.11).

F.3. Winner-Conditioned Endpoint Localization We next record the endpoint localization of the absorbing arm under winner conditioning. This result controls moments and tail probabilities of Li under the winner-weighted Stieltjes ratios appearing in the capped abandonment envelope. The resulting pairwise abandonment estimates are derived in the next subsection. The following arguments apply under Assumption D.3 to every absorbing arm i. Since κ < 1, −1 we have ∆−1 1 = o(η∆ ). Thus every nonzero pairwise gap is asymptotically larger than the O(∆1 )

endpoint window on which Li is localized. In particular, on 0 ≤ ℓ ≤ a0 /∆1 , a lower-mean competitor r with pi > pr satisfies ℓ + pr − pi < 0 for all sufficiently large ∆1 , so its tail factor remains equal to one. At the same time, every positive shifted level arising on this window remains within the lowerendpoint scale η∆ , and hence the local root and tail expansions apply. Equal-mean competitors are permitted and are treated separately below. For ◦ ∈ {>, ≥}, define the winner weight Φ◦i (ℓ) :=

F r,◦ (ℓ + pr − pi ),

r̸=i

where shifted levels below zero contribute tail factor one. Let Di> := P(Wi> ) =

Z [0,pi )

Φ> i (ℓ) dFi (ℓ).

Lemma F.3 (Winner-weighted endpoint localization). Under Assumption D.3, for every arm i,

there exist constants C, c > 0, independent of ∆1 , such that Z pi x

Φ≥ i (ℓ) dFi (ℓ) ≤ C exp{−c∆1 x},

Di>

0 ≤ x ≤ η∆ .

(F.12)

Consequently, for every fixed integer m ≥ 1 and every a ∈ (0, η∆ ], Z a 0

ℓm Φ≥ i (ℓ) dFi (ℓ) Di>

= O(∆−m 1 ).

(F.13)

≥ The same two estimates hold with Φ> i in place of Φi in the numerator. In particular,

P(Li > x | Qi ) ≤ C exp{−c∆1 x},

0 ≤ x ≤ η∆ ,

(F.14)

and −m E[Lm i 1{Li ≤ a} | Qi ] = O(∆1 ).

(F.15)

Proof. Recall that, for ◦ ∈ {>, ≥}, Φ◦i (ℓ) =

F r,◦ (ℓ + pr − pi ),

r̸=i

where shifted levels below zero contribute tail factor one. Also recall Z > > Di = P(Wi ) = Φ> i (ℓ) dFi (ℓ). [0,pi )

Numerator upper bound. Since every shifted level ℓ + pr − pi is nondecreasing in ℓ, each one-arm tail factor is nonincreasing in ℓ. Hence ≥ Φ≥ i (ℓ) ≤ Φi (0),

ℓ ≥ 0.

We compare the weak and strict weights at zero. If pr − pi ≤ 0, both tail factors are one. If pr − pi > 0, Corollary D.2 gives F r,≥ (pr − pi ) ≤ exp{θr (pr − pi )(pr − (pr − pi ))} F r,> (pr − pi ) = exp{θr (pr − pi )pi }. The Lundberg equation at level pr − pi implies qr exp{θr (pr − pi )pi } ≤ 1, and therefore F r,≥ (pr − pi ) 1 ≤ . qr F r,> (pr − pi )

53 > Since K is fixed, multiplying the factorwise bounds yields Φ≥ i (0) ≤ CΦi (0). Using the one-arm

lower-endpoint tail envelope for Li , uniformly for 0 ≤ x ≤ η∆ , P(Li > x) ≤ C exp{−c∆1 x}. Therefore, Z pi x

≥ > Φ≥ i (ℓ) dFi (ℓ) ≤ Φi (0)P(Li > x) ≤ CΦi (0) exp{−c∆1 x}.

(F.16)

Denominator lower bound. We now prove that the denominator is not much smaller than the zerolevel winner weight. More precisely, we show that there exists c > 0, independent of ∆1 , such that > Φ> i (ℓ) ≥ cΦi (0),

a0 , ∆1

0≤ℓ≤

(F.17)

where a0 > 0 is a fixed constant to be chosen later. Since Φ> i is a product over competitors, it is enough to show that each factor F r,> (ℓ + pr − pi ) is bounded below by a positive constant times its value at ℓ = 0, uniformly over 0 ≤ ℓ ≤ a0 /∆1 . First consider a lower-mean competitor r with pi > pr . The shifted level is ℓ + pr − pi = ℓ − δir . The purpose here is to show that this factor stays equal to one throughout the small window. By 1−κ ) → ∞. Hence, for (D.13), δir = Θ(η∆ ). Since η∆ = ∆−κ 1 by (D.14) and κ < 1, ∆1 δir = Θ(∆1

every fixed a0 , a0 /∆1 < δir for all sufficiently large ∆1 . Therefore, ℓ + pr − pi ≤ 0,

0≤ℓ≤

a0 . ∆1

By the nonpositive-level convention, the corresponding strict tail factor is one throughout the window, and it is also one at ℓ = 0. Thus lower-mean competitors cause no loss in (F.17). Next consider an equal-mean competitor r with pr = pi . The shifted level is ℓ, and the goal is to show that this small positive shift only changes the strict tail by a constant factor. Since F r,> (0) = 1, it is enough to lower-bound F r,> (ℓ). By the lower side of Corollary D.2, F r,> (ℓ) ≥ exp −θr (ℓ) br (ℓ) + pr − ℓ .

(F.18)

On 0 ≤ ℓ ≤ a0 /∆1 , the lower-endpoint expansion gives θr (ℓ) ≤ Cℓ. Moreover, using ∆r = Θ(∆1 ), β = O(∆1 ), and ℓ ≤ a0 /∆1 , br (ℓ) + pr − ℓ = ∆r + βℓ + pr − ℓ ≤ C∆1 .

(F.19)

Combining (F.18)–(F.19), we obtain a constant ceq := exp{−Ceq a0 } > 0 such that F r,> (ℓ) ≥ ceq ,

0≤ℓ≤

a0 . ∆1

Thus equal-mean competitors also lose only a constant factor. Finally consider a higher-mean competitor r with pr > pi . The shifted level moves from δri = pr − pi to δri + ℓ. Our goal is to prove that this O(∆−1 1 ) shift changes the strict tail only by a

constant factor: F r,> (δri + ℓ) ≥ chigh,r F r,> (δri ),

0≤ℓ≤

a0 . ∆1

(F.20)

By (D.13), δri = Θ(η∆ ). Moreover, since κ < 1, a0 /∆1 = o(η∆ ). Therefore, 0 < δri ≤ δri + ℓ ≤ Cloc η∆ ,

0≤ℓ≤

a0 , ∆1

for all sufficiently large ∆1 . Thus the whole shifted-level interval lies in the lower-endpoint region. In particular, Lemma C.4 gives, uniformly over this interval, θr (y) ≤ Cθ y,

vr (y) ≥ cv y,

θr (y) ≤ Cθ/v , vr (y)

0 < y ≤ Cloc η∆ .

(F.21)

Also, since pr − (δri + ℓ) = pi − ℓ, we have pr − (δri + ℓ) = pi − ℓ ≥

pi , 2

0≤ℓ≤

a0 , ∆1

for all sufficiently large ∆1 . Hence the upper endpoint is not involved. By the two-sided root envelope, F r,> (δri + ℓ) ≥ exp −θr (δri + ℓ) br (δri + ℓ) + pi − ℓ , F r,> (δri ) ≤ exp {−θr (δri )br (δri )} .

(F.22) (F.23)

Dividing (F.22) by (F.23) gives F r,> (δri + ℓ) ≥ exp {− [θr (δri + ℓ)br (δri + ℓ) − θr (δri )br (δri )]} F r,> (δri ) × exp {−θr (δri + ℓ)(pi − ℓ)} .

(F.24)

We bound the two exponential factors separately. For the first factor, differentiate the product θr (y)br (y). Differentiating the root equation Λr (θr (y), y) = 0 gives θr′ (y) =

θr (y) , vr (y)

because ∂y Λr (θ, y) = −θ and ∂θ Λr (θr (y), y) = vr (y). Therefore d br (y) ′ ′ {θr (y)br (y)} = θr (y)br (y) + θr (y)br (y) = θr (y) +β . dy vr (y) On 0 < y ≤ Cloc η∆ , (F.21) gives θr (y)/vr (y) ≤ Cθ/v and θr (y) ≤ Cθ η∆ . Moreover, br (y) = ∆r + βy = O(∆1 ),

β = O(∆1 ).

(F.25)

Substituting these bounds into (F.25), we obtain a constant Cder < ∞ such that d {θr (y)br (y)} ≤ Cder ∆1 . dy δri ≤y≤δri +a0 /∆1 sup

Therefore, Z δri +ℓ θr (δri + ℓ)br (δri + ℓ) − θr (δri )br (δri ) = δri

d {θr (y)br (y)} dy dy

≤ Cder ∆1 ℓ ≤ Cder a0 . Thus the first exponential factor in (F.24) is bounded below by exp{−Cder a0 }.

(F.26)

For the second factor, the Lundberg equation implies qr exp{θr (y)(pr − y)} ≤ 1,

0 < y < pr .

With y = δri + ℓ, this becomes exp{−θr (δri + ℓ)(pi − ℓ)} ≥ qr .

(F.27)

Combining (F.26) and (F.27), we get F r,> (δri + ℓ) ≥ qr exp{−Cder a0 }, F r,> (δri )

0≤ℓ≤

a0 . ∆1

Thus (F.20) holds with chigh,r := qr exp{−Cder a0 }. Combining the lower-mean, equal-mean, and higher-mean competitor cases, define  K−1   cΦ := min 1, ceq , min chigh,r  ,   r̸=i 

pr >pi

with the convention that the minimum over an empty set is 1. Here ceq is the constant factor obtained in the equal-mean case. Then every competitor factor in Φ> i (ℓ) is bounded below by its zero-level value times the corresponding constant factor. Hence > Φ> i (ℓ) ≥ cΦ Φi (0),

which proves (F.17).

0≤ℓ≤

a0 , ∆1

It remains to convert this local weight bound into a denominator bound. Using (F.17), Di> =

Z [0,pi )

Φ> i (ℓ) dFi (ℓ) ≥

Z a0 /∆1 0

> Φ> i (ℓ) dFi (ℓ) ≥ cΦ Φi (0)P

a0 Li ≤ ∆1

Since a0 /∆1 ≤ η∆ for all sufficiently large ∆1 , the local one-arm tail envelope gives a0 a0 = exp −λi P Li > 1 + O(∆1−2κ ) . 1 ∆1 ∆1 Because λi = Θ(∆1 ), choosing a0 sufficiently large yields 1 a0 ≥ P Li ≤ ∆1 2 for all large ∆1 . Therefore Di> ≥ cD Φ> i (0),

cD :=

cΦ . 2

(F.28)

Conclusion. Combining (F.16) and (F.28) gives (F.12). The same tail bound with Φ> i in the ≥ numerator follows because Φ> i (ℓ) ≤ Φi (ℓ).

Ra For the moment bound, first note that for 0 ≤ ℓ ≤ a, ℓm = m 0 xm−1 1{x ≤ ℓ} dx. Therefore, by Tonelli’s theorem, Z a ℓ 0

Z a Z a m−1 m x 1{x ≤ ℓ} dx Φ≥ i (ℓ) dFi (ℓ)

Φ≥ i (ℓ) dFi (ℓ) Di>

Di> Z a Z a

xm−1

Φ≥ i (ℓ) dFi (ℓ) Di>

Z pi Z a ≤m

xm−1

Φ≥ i (ℓ) dFi (ℓ) Di>

dx.

Using (F.12), Z a 0

ℓm Φ≥ i (ℓ) dFi (ℓ) Di>

Z a ≤ Cm

xm−1 exp{−c∆1 x} dx

Z ∞ ≤ Cm 0

xm−1 exp{−c∆1 x} dx = O(∆−m 1 ).

> This proves (F.13). The same moment bound with Φ> i in the numerator follows again from Φi (ℓ) ≤

Φ≥ i (ℓ).

Finally, by the score-minimum sandwich, Z pi P(Li > x | Qi ) ≤

Φ≥ i (ℓ) dFi (ℓ) Di>

which gives (F.14). The conditional moment bound (F.15) follows from (F.14) by the same layercake argument.

≥ ≥ > The same estimates hold with Φ> i in place of Φi in the numerator, because Φi (ℓ) ≤ Φi (ℓ).

Thus, in later applications, either strict or weak winner-weighted numerator integrals over lower> > endpoint windows have moments of order O(∆−m 1 ) after normalization by Di = P(Wi ).

F.4. Asymptotic Conditional-Abandonment Envelope We now evaluate the root-based upper envelope in Proposition F.2 under Assumption D.3 for every pair i ̸= j. The pointwise bounds from Lemma F.1 are integrated against the winner weights, while Lemma F.3 controls the resulting endpoint moments that arise from this integration. Throughout this subsection, T denotes the finite-horizon cap in min{T, Nj } and is kept as an external parameter. All O(·) and o(·) terms refer to the limit ∆1 → ∞, with every displayed factor of T left explicit. By (D.13), every nonzero pairwise gap is of order η∆ . Hence all positive shifted levels entering the local Stieltjes replacements remain within the lower-endpoint region, while ∆1 η∆ → ∞ separates every nonzero comparison gap from the O(∆−1 1 ) endpoint window of the absorbing arm. When pi = pj , no nonzero drift scale is available, and the finite-horizon cap is used directly. Proposition F.4 (Asymptotic capped conditional-abandonment upper envelope). Under Assumption D.3, for every pair i ̸= j and every finite-horizon parameter T , if pi = pj , then E[Nj (T ) | Qi ] ≤ E[min{T, Nj } | Qi ] ≤ T.

(F.29)

If pi ̸= pj , then

E[Nj (T ) | Qi ] ≤ E[min{T, Nj } | Qi ] ≤

 P(Qj ) ∆i  κ−1    δij 1 + O(∆1 ) + T o P(Qi ) ,

pi > pj ,

 ∆i   (1 + o(1)) + T o(1),  δji

pj > pi .

(F.30)

Terms conditioned on probability-zero events are interpreted as zero contributions. Proof. The first inequality follows from Nj (T ) ≤ min{T, Nj }. If pi = pj , then the finite-horizon cap gives directly E[min{T, Nj } | Qi ] ≤ T , which proves (F.29). Hence, for the rest of the proof, assume pi ̸= pj . By (D.13) and (D.14), every nonzero comparison gap is of order η∆ , and hence is separated

from the O(∆−1 1 ) endpoint window because κ < 1. All positive shifted levels appearing on the lower-endpoint windows are also O(η∆ ). Therefore, Lemma F.3 applies to the winner-weighted Stieltjes ratios below. We prove the noncritical bounds in (F.30) by evaluating the root-based integrated envelope in Proposition F.2. For a Borel set B ⊆ [0, pi ), write Z Hj|i,T (ℓ)

Ij|i,T (B) := B

and Di> := P(Wi> ) =

K Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ),

r=1 r̸=i,j

F r,> (ℓ + pr − pi ) dFi (ℓ).

[0,pi ) r̸=i

The strict and weak winner Stieltjes replacements for arm i have the same leading order. Since Wi> ⊆ Qi ⊆ Wi≥ , we have P(Qi ) = Di> (1 + o(1)). Thus ratios with denominator Di> and ratios with denominator P(Qi ) are interchangeable at the precision used below. We repeatedly use the weighted endpoint moment bound from Lemma F.3: for every a ≤ η∆ and every fixed integer m ≥ 0, Z a

ℓm

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

= O(∆−m 1 ),

Di>

(F.31)

where m = 0 means an O(1) bound. Positive-drift branch: pi > pj . Recall δij := pi − pj > 0. By (D.13) and (D.14), δij = Θ(η∆ ),

∆1 δij → ∞,

2 ∆1 δij → 0.

Choose ω∆ := ∆−1−ξ , 1

0 < ξ < κ.

Then ω∆ = o(δij ),

ω∆ = o(η∆ ),

∆1 ω∆ = o(1).

Fix a small constant 0 < ε < 21 min{pi , pj }. For all sufficiently large ∆1 , we split interval [0, pi ) into following pieces: • Bulk region 0 ≤ ℓ ≤ δij /2; • Left noncritical region δij /2 < ℓ < δij − ω∆ ; • Singular layer |ℓ − δij | ≤ ω∆ ; • Right noncritical region δij + ω∆ < ℓ ≤ pi − ε; • Upper-endpoint region pi − ε < ℓ < pi .

We evaluate the bulk explicitly, show that the two noncritical regions and the upper-endpoint region are negligible, and then control the singular layer by a finite-horizon cap. Bulk region 0 ≤ ℓ ≤ δij /2. On this interval, ℓ + pj − pi = ℓ − δij ≤ −

δij < 0, 2

so the j-factor in the winner weight is equal to one. By the positive-drift part of Lemma F.1, Hj|i,T (ℓ) ≤

∆i + βℓ + pi , δij − ℓ

δij . 2

0≤ℓ≤

For this display, set fij (ℓ) :=

∆i + βℓ + pi . δij − ℓ

Then ∆i + p i , fij (0) = δij

fij′ (0) =

β ∆i + p i ∆1 + =O 2 2 δij δij δij

! ,

sup

|fij′′ (ℓ)| = O

0≤ℓ≤δij /2

∆1 3 δij

! .

Using Taylor’s formula and (F.31), Ij|i,T ([0, δij /2]) 1 ∆i −1 −2 + O(δij ) + O(δij )+O ≤ > 3 δij Di ∆1 δij ∆i ) . = 1 + O(∆κ−1 1 δij

(F.32)

Left noncritical region δij /2 < ℓ < δij − ω∆ . On this region the comparison drift is still positive, and δij − ℓ ≥ ω∆ . Moreover, the shifted level of arm j is nonpositive: ℓ + pj − pi = ℓ − δij < 0. Thus the j-factor in the winner weight is equal to one. The positive-drift part of Lemma F.1 gives Hj|i,T (ℓ) ≤

∆i + βℓ + pi − ℓ C∆1 ≤ , δij − ℓ ω∆

δij < ℓ < δij − ω∆ . 2

Therefore, Z δij −ω∆ Y K

Ij|i,T (δij /2, δij − ω∆ ) C∆1 ≤ > ω∆ Di

δij /2

Di> Z δij −ω∆ Y

C∆1 = ω∆

δij /2

C∆1 ω∆

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

Di> Z pi Y

≤

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r=1 r̸=i,j

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

δij /2 r̸=i

Di>

≤

C∆1 exp{−c∆1 δij } = O(∆−∞ 1 ). ω∆

(F.33)

The last inequality uses Lemma F.3 with x = δij /2. Right noncritical region δij + ω∆ < ℓ ≤ pi − ε. Here the shifted level of arm j is positive: y := ℓ + pj − pi = ℓ − δij ≥ ω∆ . The restriction ℓ ≤ pi − ε also gives pj − y = pi − ℓ ≥ ε. Therefore, by the global tilted-drift order (C.29), vj (y) ≥ c min{y, pj − y} ≥ cω∆ .

(F.34)

The negative-drift part of Lemma F.1 gives Hj|i,T (ℓ) ≤ exp{−θj (y)bi (ℓ)}

∆i + βℓ + pi − ℓ . vj (y)

Using (F.34) and ∆i + βℓ + pi − ℓ = O(∆1 ), we obtain Hj|i,T (ℓ) ≤

C∆1 exp{−θj (y)bi (ℓ)}. ω∆

(F.35)

We next compare the tilted exponential with the strict j-tail in the winner denominator. Since bj (y) = ∆j + βy = ∆i + βℓ = bi (ℓ), the lower side of the root envelope gives F j,> (y) ≥ exp −θj (y) bi (ℓ) + pj − y . Hence

exp{−θj (y)bi (ℓ)} 1 ≤ exp{θj (y)(pj − y)} ≤ , q F j,> (y) j

(F.36)

where the last inequality follows from the Lundberg equation qj exp{θj (y)(pj − y)} ≤ 1. Combining (F.35) and (F.36), we have the effective pointwise bound Hj|i,T (ℓ) ≤

C∆1 F j,> (ℓ − δij ), ω∆

δij + ω∆ < ℓ ≤ pi − ε.

Therefore, Z pi −ε F j,> (ℓ − δij )

Ij|i,T (δij + ω∆ , pi − ε] C∆1 ≤ ω∆ Di>

δij +ω∆

K Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r=1 r̸=i,j Di>

Z pi C∆1 ≤ ω∆

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

δij +ω∆ r̸=i

Di> Z pi Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ) C∆1 δij /2 r̸=i ≤ ω∆ Di> C∆1 exp{−c∆1 δij } = O(∆−∞ ≤ 1 ). ω∆

(F.37)

Combining (F.33) and (F.37), we obtain Ij|i,T {ℓ > δij /2, |ℓ − δij | > ω∆ , ℓ ≤ pi − ε} = O(∆−∞ 1 ). Di>

(F.38)

Upper-endpoint region pi − ε < ℓ < pi . Set s := pi − ℓ. Then s ∈ (0, ε), and the shifted level of arm j is ℓ + pj − pi = pj − s.

(F.39)

Thus this is an upper-endpoint crossing for arm j. By (F.39) and the upper-endpoint tilted-drift order (C.24), after possibly reducing ε > 0, there exists c > 0 such that vj (pj − s) ≥ cs,

0 < s ≤ ε.

The negative-drift part of Lemma F.1 therefore gives Hj|i,T (ℓ) ≤ exp{−θj (pj − s)bi (ℓ)} ≤

bi (ℓ) + s vj (pj − s)

C∆1 exp{−θj (pj − s)bi (ℓ)}. s

(F.40)

Here we used bi (ℓ) + s = O(∆1 ). We now compare the tilted exponential with the strict j-tail. Since bj (pj − s) = ∆j + β(pj − s) = ∆i + β(pi − s) = bi (ℓ), the lower side of Corollary D.2 implies F j,> (pj − s) ≥ exp −θj (pj − s) bi (ℓ) + s . Hence

exp{−θj (pj − s)bi (ℓ)} 1 ≤ exp{θj (pj − s)s} ≤ , qj F j,> (pj − s)

(F.41)

where the last inequality follows from the Lundberg equation qj exp{θj (pj − s)s} ≤ 1. Combining

(F.40) and (F.41), we obtain the effective pointwise bound Hj|i,T (ℓ) ≤

C∆1 F j,> (ℓ + pj − pi ), pi − ℓ

pi − ε < ℓ < pi .

Therefore, K

Z pi Ij|i,T ({pi − ε < ℓ < pi }) ≤ C∆1 Di>

Y 1 F j,> (ℓ + pj − pi ) F r,≥ (ℓ + pr − pi ) dFi (ℓ) pi −ε pi − ℓ r=1 r̸=i,j Di>

Z pi ≤ C∆1

1 Y F r,≥ (ℓ + pr − pi ) dFi (ℓ) pi −ε pi − ℓ r̸=i

Di>

We next record the winner-weighted upper-endpoint tail bound. For 0 < s ≤ ε, Z pi Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

pi −s r̸=i

≤

Di>

P(Li > pi − s) . Di>

By the upper-endpoint root expansion for arm i, c∆1 . P(Li > pi − s) ≤ exp {−θi (pi − s)bi (pi − s)} ≤ exp − s On the other hand, the denominator lower bound in Lemma F.3, together with the intermediate> gap scale of the positive shifted levels in Φ> i (0), gives Di ≥ exp{−C∆1 η∆ }. Since η∆ → 0, after

decreasing c > 0 if necessary, Z pi Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

pi −s r̸=i

Di>

c∆1 ≤ C exp − s

0 < s ≤ ε.

It remains to integrate the algebraic prefactor (pi − ℓ)−1 . Let sn := 2−n ε, n = 0, 1, 2, . . ., and split the upper-endpoint region into dyadic shells An := {pi − sn < ℓ ≤ pi − sn+1 }. On An , we have (pi − ℓ)−1 ≤ s−1 n+1 . Moreover, by the upper-endpoint tail bound for Li , the denominator lower bound (F.28), and the fact that ∆1 η∆ = o(∆1 /sn ) uniformly for sn ≤ ε, there exists c > 0 such that

Z pi

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

pi −sn r̸=i

Di>

c∆1 ≤ exp − sn

n = 0, 1, 2, . . . .

(F.42)

Therefore, Z pi ∞ X Ij|i,T ({pi − ε < ℓ < pi }) 1 ≤ C∆ 1 > s Di n=0 n+1 ∞ X

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

pi −sn r̸=i

Di>

c∆1 exp − ≤ C∆1 sn+1 sn n=0 ∞ X 2n+1 c2n ∆1 ≤ C∆1 exp − ε ε 1

n=0

= O(∆−∞ 1 ).

(F.43)

Singular layer |ℓ − δij | ≤ ω∆ . This layer contains the only region, up to the noncritical and upper-endpoint parts already shown negligible, where the strict comparison with arm j may fail to give a useful pathwise upper bound. We therefore control it by a finite-horizon cap. The size of this layer is compared with the strict-winner scale of arm j through lower-endpoint crossing envelopes. Define the singular-layer event Aij,∆ := Qi ∩ {|Li − δij | ≤ ω∆ } . Since Qi ⊆ Wi≥ , conditioning on Li = ℓ gives the exact weak-layer upper bound Z P(Aij,∆ ) ≤

F h,≥ (ℓ + ph − pi ) dFi (ℓ).

(F.44)

[δij −ω∆ , δij +ω∆ ] h̸=i

We now bound the factors in the integrand. On the layer |ℓ − δij | ≤ ω∆ , the h = j factor is bounded by one. For h > j, the corresponding factor is also bounded by one; under strict ordering the shifted level is in fact nonpositive for all sufficiently large ∆1 . For h < j, h ̸= i, we have ℓ + ph − pi = δhj + (ℓ − δij ). If δhj > 0, then this shifted level is δhj + O(ω∆ ). Since δhj = O(η∆ ), ω∆ = o(η∆ ), and ∆1 ω∆ = o(1), the lower-endpoint tail envelope gives, uniformly on the singular layer, F h,≥ (ℓ + ph − pi ) ≤ exp {−λh δhj + o(1)} . If δhj = 0, the same upper bound is trivial because the right-hand side is exp{o(1)} and the survival factor is at most one. Therefore, uniformly over the singular layer,        X  Y F h,≥ (ℓ + ph − pi ) ≤ exp − λh δhj + o(1) .     h<j  h<j  h̸=i

h̸=i

Combining this with (F.44), we obtain        X  P(Aij,∆ ) ≤ exp − λh δhj + o(1) Fi (δij + ω∆ ) − Fi (δij − ω∆ )−      h<j  h̸=i        X  = exp − λh δhj + o(1) F i,≥ (δij − ω∆ ) − F i,> (δij + ω∆ ) .      h<j 

(F.45)

h̸=i

It remains to bound the Li -mass of the short window. Because δij = Θ(η∆ ) and ω∆ = o(η∆ ), both endpoints δij ± ω∆ lie on the lower-endpoint scale for all sufficiently large ∆1 . Hence, for both ◦ ∈ {>, ≥}, the local lower-endpoint approximation gives ) , F i,◦ (x) = exp{−λi x} 1 + O(∆1−2κ 1

x ∈ {δij − ω∆ , δij + ω∆ } .

Therefore, Fi (δij + ω∆ ) − Fi (δij − ω∆ )− = F i,≥ (δij − ω∆ ) − F i,> (δij + ω∆ ) Z δij +ω∆ exp{−λi (δij − ω∆ )} ≤C λi exp{−λi x} dx + C∆1−2κ 1 δij −ω∆

≤ C λi ω∆ + ∆1−2κ exp{−λi (δij − ω∆ )} 1 ≤ C λi ω∆ + ∆1−2κ exp{−λi δij + o(1)}. 1

(F.46)

In the last step we used λi ω∆ = o(1). The integral term is the mass of the exponential reference term is the uniform lower-endpoint approximation error. measure over the window, while the ∆1−2κ 1 with ξ > 0, and κ > 1/2. Both terms are o(1), because λi = Θ(∆1 ), ω∆ = ∆−1−ξ 1 Substituting (F.46) into (F.45) gives         X 1−2κ P(Aij,∆ ) ≤ C λi ω∆ + ∆1 exp −λi δij − λh δhj + o(1)     h<j   h̸=i    X  − λ δ + o(1) = C λi ω∆ + ∆1−2κ exp h hj 1   h<j     X  = o exp − λh δhj + o(1)  .  

(F.47)

h<j

We next compare this upper bound with a restricted strict-winner lower bound for arm j. Fix a small constant a > 0. Since a/∆1 ≤ η∆ for all sufficiently large ∆1 , the contribution to P(Wj> )

from 0 ≤ x ≤ a/∆1 gives P(Qj ) ≥ P(Wj> ) Z a/∆1 ≥c 0

    X λh (x + δhj ) λj exp{−λj x} dx [1 + o(1)] . exp −   h<j

Here the fixed constant c > 0 accounts for competitor factors not displayed in the integral; on the O(∆−1 1 ) window these factors are either automatic or bounded below by a positive constant. Evaluating the integral gives     X λh (x + δhj ) λj exp{−λj x} dx exp −   h<j         X    X λj a 1 − exp − λj + . P = exp − λh δhj λh    λj + h<j λh  ∆1 

Z a/∆1 0

h<j

Since K is fixed and λh = Θ(∆1 ) for every h, the last two factors are bounded below by a positive constant. Hence     X P(Qj ) ≥ c exp − λh δhj .  

(F.48)

h<j

Combining (F.47) and (F.48), we obtain P(Aij,∆ ) = o(P(Qj )). Finally, since Di> := P(Wi> ), P(Qi ) = Di> (1 + o(1)), the finite-horizon contribution of the singular layer is P(Aij,∆ ) P (Qi , |Li − δij | ≤ ω∆ ) P(Qj ) T =T =To . P(Qi ) P(Qi ) P(Qi )

(F.49)

Pairwise equality correction. It remains to control the pairwise equality correction Eij= . We prove that, in the positive-drift branch pi > pj , P(Eij= ) = o(P(Qj )).

(F.50)

This estimate is stronger than the global strict–weak winner comparison for arm i, and it is the estimate needed on every branch Qi satisfying pi = p1 . By (F.11), the pairwise equality probability is P(Eij= ) =

Z pi

K Y F j,≥ (ℓ − δij ) − F j,> (ℓ − δij ) × F h,≥ (ℓ + ph − pi ) dFi (ℓ).

δij

(F.51)

h=1 h̸=i,j

The lower limit δij is harmless because, for ℓ < δij , the shifted level of arm j is negative and the strict and weak tail factors are both equal to one.

Set y := ℓ − δij , then ℓ + p h − p i = y + ph − p j ,

h ̸= i, j.

On the local region 0 ≤ y ≤ η∆ , all positive shifted levels in (F.51) are O(η∆ ). For ◦ ∈ {>, ≥}, the lower-endpoint tail envelope gives, uniformly for 0 ≤ y ≤ η∆ , F j,◦ (y) = exp{−λj y} [1 + εj,◦ (y)] ,

sup |εj,◦ (y)| ≤ C0 ∆1−2κ . 1

0≤y≤η∆

Since the weak tail contains the strict tail, F j,≥ (y) ≥ F j,> (y). Therefore 0 ≤ F j,≥ (y) − F j,> (y) = exp{−λj y} [εj,≥ (y) − εj,> (y)] ≤ 2C0 ∆1−2κ exp{−λj y}. 1

(F.52)

Thus, after increasing the constant if necessary, 0 ≤ F j,≥ (y) − F j,> (y) ≤ a∆ exp{−λj y},

= o(1), a∆ := C∆1−2κ 1

(F.53)

uniformly for 0 ≤ y ≤ η∆ . Using (F.53), the local Stieltjes replacement for Li , and the same lower-endpoint replacements for the remaining weak factors, we obtain

P(Eij= ) ≤ a∆

Z η∆ 0

      K   X exp −λj y − λh (y + ph − pj )+ λi exp{−λi (δij + y)} dy [1 + o(1)] + o(Jij,∆ ),     h=1   h̸=i,j

where       Z η∆ K   X Jij,∆ := exp −λj y − λh (y + ph − pj )+ λi exp{−λi (δij + y)} dy.   0   h=1  

(F.54)

h̸=i,j

The contribution of y > η∆ , together with the upper-endpoint part, is o(Jij,∆ ) by the same taillocalization argument used in Corollary D.6. Therefore P(Eij= ) = o(Jij,∆ ).

(F.55)

We now compare Jij,∆ with the suboptimal-convergence scale of arm j. The lower-endpoint

reference integral for the strict winner event of arm j is       Z η∆ K   X Jj,∆ := exp −λi (y + δij ) − λh (y + ph − pj )+ λj exp{−λj y} dy.   0   h=1  

(F.56)

h̸=i,j

Comparing (F.54) and (F.56), we have Jij,∆ = λi Jj,∆ /λj . Since λi = Θ(∆1 ) and λj = Θ(∆1 ), λi /λj = Θ(1). Moreover, by the local Stieltjes replacement and the strict/weak winner sandwich for arm j, P(Qj ) = Jj,∆ [1 + o(1)]. Hence Jij,∆ = O(P(Qj )).

(F.57)

Combining (F.55) and (F.57) proves (F.50). Consequently, using Di> = P(Wi> ) and P(Qi ) = Di> (1 + o(1)), T

P(Eij= ) Di>

P(Qj ) =To P(Qi )

(F.58)

Combining the bulk estimate (F.32), the noncritical estimate (F.38), the upper-endpoint estimate (F.43), the singular-layer contribution (F.49), and the pairwise equality correction (F.58), we obtain

P(Qj ) ∆i κ−1 E[min{T, Nj } | Qi ] ≤ 1 + O(∆1 ) + T o . δij P(Qi )

This proves the branch pi > pj . Large-deviation branch: pj > pi . Recall δji := pj − pi > 0. The shifted level in Lemma F.1 is y = ℓ + δji . By (D.13) and (D.14), δji = Θ(η∆ ),

∆1 δji → ∞,

2 ∆1 δji → 0.

There is no interface singularity in this branch, because y = ℓ + δji > 0 for every ℓ ≥ 0. We first evaluate the lower-endpoint contribution 0 ≤ ℓ ≤ η∆ , and then show that the remaining contribution ℓ > η∆ is negligible. On 0 ≤ ℓ ≤ η∆ , we have δji ≤ y = ℓ + δji ≤ δji + η∆ = O(η∆ ). Thus every positive shifted level used in the local part of this branch is inside the same O(η∆ ) lowerendpoint window. In particular, the expansions of θj (y), vj (y), and the one-arm tail envelopes are used only uniformly over 0 < y ≤ Cη∆ . Therefore, the lower-endpoint expansions apply uniformly. In particular, vj (y) ≥ y(1 − O(η∆ )) = (ℓ + δji )(1 − O(η∆ )).

(F.59)

Moreover, bj (y) = ∆j + β(ℓ + δji ) = ∆i + βℓ = bi (ℓ).

(F.60)

The negative-drift part of Lemma F.1 therefore gives Hj|i,T (ℓ) ≤ exp{−θj (y)bi (ℓ)}

bi (ℓ) + pi − ℓ . vj (y)

(F.61)

We next compare the tilted exponential in (F.61) with the strict j-tail that is absent from Ij|i,T . By the lower side of Corollary D.2 and (F.60), F j,> (y) ≥ exp −θj (y) bi (ℓ) + pj − y . Since pj − y = pi − ℓ, we have exp{−θj (y)bi (ℓ)} ≤ exp{θj (y)(pi − ℓ)} F j,> (y) = exp{θj (y)(pj − y)} 1 ≤ , qj

(F.62)

where the last inequality follows from the Lundberg equation qj exp{θj (y)(pj − y)} ≤ 1. Combining (F.61), (F.59), and (F.62), and using y = ℓ+δji , we obtain, uniformly for 0 ≤ ℓ ≤ η∆ , Hj|i,T (ℓ) ≤

bi (ℓ) + pi − ℓ (1 + O(η∆ )) F j,> (ℓ + δji ). ℓ + δji

Since ℓ + δji ≥ δji and bi (ℓ) + pi − ℓ = ∆i + βℓ + pi − ℓ ≤ ∆i + βℓ + pi , this implies Hj|i,T (ℓ) ≤

∆i + βℓ + pi (1 + O(η∆ )) F j,> (ℓ + δji ), δji

0 ≤ ℓ ≤ η∆ .

(F.63)

Substituting (F.63) into the integral over [0, η∆ ], we get Z η∆ (∆i + βℓ + pi )F j,> (ℓ + δji ) Ij|i,T ([0, η∆ ]) 1 + O(η∆ ) ≤ > δji Di

Di> (∆i + βℓ + pi )

1 + O(η∆ ) δji

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r=1 r̸=i,j

Z η∆ ≤

K Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

Di>

The last step uses F j,> (ℓ + δji ) ≤ F j,≥ (ℓ + δji ). We now apply the winner-weighted moment bounds. The leading-order equivalence between

strict and weak winner Stieltjes replacements, together with the tail bound in Lemma F.3, gives Z η∆ Y 0

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

= 1 + o(1).

Di> The m = 1 case of Lemma F.3 gives Z η∆ Y ℓ F r,≥ (ℓ + pr − pi ) dFi (ℓ) 0

r̸=i

= O(∆−1 1 ).

Di> Therefore, using β = O(∆1 ) and ∆i = Θ(∆1 ),

Ij|i,T ([0, η∆ ]) 1 + O(η∆ ) ≤ (∆i + pi )(1 + o(1)) + βO(∆−1 1 ) > δji Di ∆i = (1 + o(1)) . δji

(F.64)

It remains to prove that the contribution of (η∆ , pi ) is negligible. For ℓ > η∆ , the shifted level satisfies y = ℓ + δji ≥ η∆ . After the same strict-tail cancellation as in (F.62), the effective pointwise envelope is bounded by Hj|i,T (ℓ) ≤ C∆1

1 1 F j,> (ℓ + δji ), + η∆ pi − ℓ

η∆ < ℓ < pi .

(F.65)

Indeed, this follows from vj (ℓ+δji ) ≍ min{ℓ+δji , pi −ℓ}, together with ℓ+δji ≥ η∆ and bi (ℓ)+pi −ℓ = O(∆1 ). Substituting (F.65) gives Z pi Ij|i,T ((η∆ , pi )) ≤ C∆1 Di>

η∆

r=1 r̸=i,j

Di> Z pi

≤ C∆1

K Y −1 η∆ + (pi − ℓ)−1 F j,> (ℓ + δji ) F r,≥ (ℓ + pr − pi ) dFi (ℓ)

η∆

−1 Y F r,≥ (ℓ + pr − pi ) dFi (ℓ) η∆ + (pi − ℓ)−1 r̸=i Di>

(F.66)

−1 The term with η∆ is bounded by

Z pi Y C

∆1 η∆

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

η∆ r̸=i

by Lemma F.3 with x = η∆ .

Di>

≤C

∆1 exp{−c∆1 η∆ } = O(∆−∞ 1 ) η∆

(F.67)

For the term with (pi − ℓ)−1 , split (η∆ , pi ) into the part away from the upper endpoint and the upper-endpoint part. On (η∆ , pi − ε], the algebraic factor is bounded by ε−1 . Hence the weighted tail-localization estimate gives Z pi −ε

(pi − ℓ)−1

η∆

C∆1

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

= O(∆−∞ 1 ).

Di>

(F.68)

It remains to consider pi − ε < ℓ < pi . For this part, we use the same upper-endpoint dyadic estimate as in (F.43). Namely, for 0 < s ≤ ε, Z pi Y

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

pi −s r̸=i

Di>

c∆1 ≤ C exp − s

(F.69)

Let sn := 2−n ε, n = 0, 1, 2, . . .. Since (pi − ℓ)−1 ≤ s−1 n+1 on {pi − sn < ℓ ≤ pi − sn+1 }, (F.69) implies Z pi pi −ε

C∆1

(pi − ℓ)−1

F r,≥ (ℓ + pr − pi ) dFi (ℓ)

r̸=i

Di>

∞ X

c∆1 ≤ C∆1 exp − s sn n=0 n+1 ∞ X 2n+1 c2n ∆1 ≤ C∆1 exp − = O(∆−∞ 1 ). ε ε 1

n=0

(F.70) Combining (F.66), (F.67), (F.68), and (F.70), we obtain Ij|i,T ((η∆ , pi )) = O(∆−∞ 1 ). Di>

(F.71)

Combining (F.64) and (F.71), and using η∆ = ∆−κ 1 , yields Ij|i,T ([0, pi )) ∆i ≤ (1 + o(1)) . > δji Di The strict-crossing bound only misses the pairwise boundary part where Mj = Mi . This pairwise boundary part is Eij= , and it is contained in the global strict–weak gap Wi≥ \ Wi> . Therefore, by (E.19), applied to arm i, P(Eij= ) ≤ P(Wi≥ ) − P(Wi> ) = o(Di> ),

Di> := P(Wi> ).

Together with P(Qi ) = Di> (1 + o(1)), its finite-horizon contribution is P(Eij= ) T = T o(1). P(Qi )

Therefore, E[min{T, Nj } | Qi ] ≤

∆i (1 + o(1)) + T o(1), δji

which proves the branch pj > pi . This proves both noncritical branches in (F.30) and completes the proof.

G. Finite-Horizon Cumulative Regret Envelope This section converts the absorption-based regret skeleton into explicit finite-horizon regret envelopes. The leading term is the suboptimal-absorption regret: on Qi , a suboptimal arm i ≥ 2 is eventually pulled for almost all large times, producing the contribution T δi P(Qi ). The remaining terms are finite transient corrections, coming from pulls spent away from the absorbing arm before the trajectory settles. We first state a root-based two-sided envelope by combining three ingredients already established above: the absorption-based regret decomposition, the root-based score-minimum envelopes for P(Qi ), and the winner-conditioned strict-crossing upper envelope for capped abandonment counts. The equality part of the score-minimum comparison is kept as a finite-horizon correction. This step is an assembly step; no new boundary-crossing estimate is needed. We then specialize the envelope to the macroscopic lower-endpoint regime. The absorbing e i ), obtained by rearranging the probabilities are replaced by their closed-form approximations P(Q suboptimal-convergence formula into a form adapted to the regret sum. The transient correction on suboptimal absorbing branches is super-polynomially small, while branches absorbing into an optimal arm contribute the only non-negligible deterministic abandonment correction. The equality corrections are controlled in pairwise form. In the positive-drift case, the boundary event Mj = Mi is shown to be negligible on the suboptimal-convergence scale of arm j, which allows the corresponding optimal-branch equality corrections to be absorbed into T P∆ o(1). This yields a P e i ), with an explicit upper transient finite-horizon regret sandwich centered at T K δi P(Q i=2,pi <p1

term. Throughout this section, T is an external finite-horizon parameter. The asymptotic notation refers only to the limit ∆1 → ∞ under the stated regularization and gap regime. We therefore keep the horizon dependence explicit through factors such as T , T o(P(Qj )), and T P∆ o(1), and we do not assign a separate asymptotic scale to T . G.1. Root-Based Two-Sided Regret Envelope We first combine the absorption-based regret skeleton with the root-based score-minimum envelopes and the pairwise winner-conditioned strict-crossing upper envelope for capped abandonment counts. This subsection is only an assembly step. Throughout this subsection, we use the shifted-root convention from Proposition E.1: whenever ℓi + pr − pi ≤ 0, the corresponding root θr (ℓi + pr − pi ) is interpreted as 0, and the corresponding

tail factor is interpreted as one. For each arm i, define     X Pi− := exp − ∆i + βℓi + pi − ℓi θr (ℓi + pr − pi ) dFi (ℓi ),   [0,pi ) r̸=i   Z   X + Pi := exp − ∆i + βℓi θr (ℓi + pr − pi ) dFi (ℓi ).   [0,pi ) Z

r̸=i

The root-tail bounds and the winner sandwich imply Pi− ≤ P(Wi> ) ≤ P(Qi ) ≤ P(Wi≥ ) ≤ Pi+ .

(G.1)

We next recall the pairwise equality event from the conditional-abandonment representation. For i ̸= k, let = := Wi≥ ∩ {Mk = Mi }. Eik

This is the only equality event that can invalidate the strict-crossing upper bound for the abandoned count of arm k on the absorbing branch Qi . The exact Stieltjes representation from (F.11) gives = )= P(Eik

K Y F k,≥ (ℓi + pk − pi ) − F k,> (ℓi + pk − pi ) × F r,≥ (ℓi + pr − pi ) dFi (ℓi ).

[0,pi )

r=1 r̸=i,k

Shifted levels below zero contribute equal strict and weak tail factors and therefore make zero contribution to the difference. For i ̸= k, define the joint transient upper envelope + Ck|i,T :=

Z Hk|i,T (ℓi ) [0,pi )

K Y

= ). F r,≥ (ℓi + pr − pi ) dFi (ℓi ) + T P(Eik

r=1 r̸=i,k

Here Hk|i,T is the strict-crossing capped first-passage envelope from Lemma F.1. The weak tails for the remaining competitors match the pairwise winner-conditioned representation. The final term controls only the boundary event Mk = Mi , which is the only equality obstruction relevant for the abandoned count of arm k. The factor T is kept explicitly as the finite-horizon multiplier. The corrected strict-crossing numerator bound gives Z E[min{T, Nk }1Qi ] ≤

Hk|i,T (ℓi ) [0,pi )

K Y

= F r,≥ (ℓi + pr − pi ) dFi (ℓi ) + T P(Eik )

r=1 r̸=i,k

+ = Ck|i,T .

This is the joint version of the pairwise conditional-abandonment envelope.

(G.2)

Proposition G.1 (Root-based two-sided regret envelope). For every finite horizon T , R(T ) ≥ T

K X

δi Pi− −

i=2 pi <p1

and R(T ) ≤ T

K X

K X X

+ (pj − pi ) Cj|i,T ,

(G.3)

+ (pi − pj ) Cj|i,T .

(G.4)

i=1 j̸=i pj >pi

δi Pi+ +

i=2 pi <p1

K X X i=1 j̸=i pj <pi

Proof. We first consider the lower bound. By Proposition A.2, R(T ) ≥ T

K X

δi P(Qi ) −

K X

i=2 pi <p1

K X

P(Qi )

i=1

δi P(Qi ) −

(pj − pi ) E[min{T, Nj } | Qi ]

j̸=i pj >pi

K X X

i=2 pi <p1

(pj − pi ) E[min{T, Nj }1Qi ] .

i=1 j̸=i pj >pi

Using the lower probability envelope in (G.1) and the joint transient upper envelope in (G.2), we obtain R(T ) ≥ T

K X

δi Pi− −

i=2 pi <p1

K X X

+ (pj − pi ) Cj|i,T ,

i=1 j̸=i pj >pi

which proves (G.3). For the upper bound, Proposition A.2 gives R(T ) ≤ T

K X

δi P(Qi ) +

K X

i=2 pi <p1

K X

P(Qi )

i=1

δi P(Qi ) +

K X X

i=2 pi <p1

(pi − pj ) E[min{T, Nj } | Qi ]

j̸=i pj <pi

(pi − pj ) E[min{T, Nj }1Qi ] .

i=1 j̸=i pj <pi

Using the upper probability envelope in (G.1) and applying (G.2) with absorbing arm i and abandoned arm j, we obtain R(T ) ≤ T

K X i=2 pi <p1

δi Pi+ +

K X X

+ (pi − pj ) Cj|i,T ,

i=1 j̸=i pj <pi

which proves (G.4).

The bounds in Proposition G.1 have the same structure as the absorption-based regret skeleton.

The terms Pi− and Pi+ control the linear regret from suboptimal absorbing arms, while the terms + Ck|i,T control the finite-horizon transient corrections. Absorption into an arm tied with an optimal

arm has zero linear regret because its regret gap is zero. Likewise, transient pulls between equalmean arms do not enter either side of the centered regret envelope. The equality correction is = ), because only the boundary event M = M can obstruct included in pairwise form through T P(Eik i k

the strict-crossing upper bound for the abandoned count of arm k. G.2. Asymptotic Closed-Form Regret Envelope We now specialize the root-based regret envelope to the macroscopic lower-endpoint regime under Assumption D.3. The common intermediate scale in (D.13) ensures that Proposition F.4 applies to every distinct-mean pair. Equal-mean pairs do not contribute to the centered transient corrections because their coefficient pi − pj is zero. Recall λh :=

2∆h , ph (1 − ph )

δij := pi − pj

(i < j),

δi := δ1i .

For every i = 2, . . . , K with pi < p1 , define the closed-form suboptimal-absorption approximation e i ) := P(Q

K X 1 m=i

( exp −

m X

)" λh δhm

(

1 − exp −

h=1

m X

! λh

)# δm,m+1

(G.5)

h=1

where δhh := 0, and for m = K, the bracket is interpreted as 1. Empty sums are interpreted as zero. Finally, set K X

P∆ :=

e i ), δi P(Q

C∆ := (K − 1)∆1 .

i=2 pi <p1

Proposition G.2 (Asymptotic closed-form regret sandwich). Under Assumption D.3, for every finite-horizon parameter T , T P∆ (1 − o(1)) − O(∆−∞ 1 ) ≤ R(T ) ≤ T P∆ (1 + o(1)) + C∆ (1 + o(1)).

(G.6)

Here the relative o(1) factors are with respect to ∆1 → ∞. The horizon T is kept as an external finite-horizon parameter and is not assigned a separate asymptotic scale. Proof. Let Isub := {i ∈ {2, . . . , K} : pi < p1 } denote the set of suboptimal arms. We first identify the closed-form approximation of the absorbing probabilities. By Proposition E.2, for every i ∈ Isub , e i )(1 + o(1)), P(Qi ) = P(Q

(G.7)

e i ) is defined in (G.5). Since K is fixed, the relative error in (G.7) is uniform over i ∈ Isub . where P(Q

Therefore, K X

δi P(Qi ) =

i=2 pi <p1

δi P(Qi )

i∈Isub

(G.8)

e i )(1 + o(1)) δi P(Q

i∈Isub

= P∆ (1 + o(1)). We also record a super-polynomial upper bound for every suboptimal absorbing probability. By the weak side of the score-minimum sandwich, Qi ⊆ {Mi ≥ M1 } for i ∈ Isub . Since Mr = pr − Lr , this implies pi − Li ≥ p1 − L1 , and hence L1 ≥ Li + δi ≥ δi

on Qi .

Therefore, by the one-arm lower-endpoint envelope, P(Qi ) ≤ P(L1 ≥ δi ) ≤ exp{−c∆1 δi } = O(∆−∞ 1 ),

i ∈ Isub ,

) → ∞. Since K is fixed, summing over the suboptimal arms gives because ∆1 δi = Θ(∆1−κ 1 X

P(Qi ) = O(∆−∞ 1 ).

(G.9)

i∈Isub

We next control the centered transient correction in the regret lower bound. For every pair j ̸= i satisfying pj > pi , Proposition F.4 gives E[min{T, Nj } | Qi ] ≤

∆i (1 + o(1)) + T o(1). pj − p i

Multiplying by pj − pi , we obtain (pj − pi )E[min{T, Nj } | Qi ] ≤ ∆i (1 + o(1)) + T (pj − pi )o(1). The condition pj > pi implies pi < p1 , so only i ∈ Isub contributes. Moreover, pj − pi ≤ p1 − pi = δi . Consequently, using the uniform regularization scale ∆i = Θ(∆1 ), the finiteness of K, and (G.9), K X i=1

P(Qi )

X j̸=i pj >pi

(pj − pi ) E[min{T, Nj } | Qi ] ≤ C∆1

P(Qi ) + T

i∈Isub

= O(∆−∞ 1 ) + T P∆ o(1),

X i∈Isub

δi P(Qi )o(1) (G.10)

where the last equality follows from (G.8). We now control the upper transient correction on suboptimal absorbing branches. For i ∈ Isub and pj < pi , Proposition F.4 gives P(Qj ) ∆i κ−1 1 + O(∆1 ) + T o . E[min{T, Nj } | Qi ] ≤ pi − pj P(Qi ) Multiplying by (pi − pj )P(Qi ) yields (pi − pj )P(Qi )E[min{T, Nj } | Qi ] ≤ ∆i P(Qi ) 1 + O(∆κ−1 ) + T (pi − pj )P(Qj )o(1). 1 Since pj < pi ≤ p1 , arm j is suboptimal and pi − pj ≤ p1 − pj = δj . It follows from (G.9), the finiteness of K, and (G.8) that X i∈Isub

P(Qi )

(pi − pj ) E[min{T, Nj } | Qi ] ≤ C∆1

P(Qi ) + T

i∈Isub

j̸=i pj <pi

δj P(Qj )o(1)

j∈Isub

(G.11)

= O(∆−∞ 1 ) + T P∆ o(1). It remains to control the upper transient correction on branches absorbing into an optimal arm. If pi = p1 and j ∈ Isub , then pi − pj = δj ,

∆i = ∆1 .

Therefore, Proposition F.4 gives P(Qj ) ∆1 κ−1 E[min{T, Nj } | Qi ] ≤ 1 + O(∆1 ) + T o . δj P(Qi ) Multiplying by δj P(Qi ) gives δj P(Qi )E[min{T, Nj } | Qi ] ≤ ∆1 P(Qi ) 1 + O(∆κ−1 ) + T δj P(Qj )o(1). 1 Summing over all i satisfying pi = p1 and all j ∈ Isub , and using K X i=1 pi =p1

P(Qi ) ≤ 1,

|Isub | ≤ K − 1,

we obtain K X i=1 pi =p1

P(Qi )

X δj P(Qj )o(1) δj E[min{T, Nj } | Qi ] ≤ (K − 1)∆1 1 + O(∆κ−1 ) + T 1 j∈Isub

j∈Isub

(G.12)

= C∆ (1 + o(1)) + T P∆ o(1). We now prove the regret lower bound. By Proposition A.2, R(T ) ≥ T

K X

δi P(Qi ) −

i=2 pi <p1

K X

P(Qi )

i=1

(pj − pi ) E[min{T, Nj } | Qi ].

j̸=i pj >pi

Using (G.10) and then (G.8), we obtain R(T ) ≥ T P∆ (1 + o(1)) − T P∆ o(1) − O(∆−∞ 1 ) = T P∆ (1 − o(1)) − O(∆−∞ 1 ).

(G.13)

We next prove the regret upper bound. By Proposition A.2, R(T ) ≤ T

K X

δi P(Qi )

i=2 pi <p1

K X i=1 pi =p1

P(Qi )

δj E[min{T, Nj } | Qi ]

j∈Isub

P(Qi )

i∈Isub

(pi − pj ) E[min{T, Nj } | Qi ].

j̸=i pj <pi

Using (G.8), (G.11), and (G.12), we obtain R(T ) ≤ T P∆ (1 + o(1)) + C∆ (1 + o(1)) + T P∆ o(1) + O(∆−∞ 1 ) = T P∆ (1 + o(1)) + C∆ (1 + o(1)),

(G.14)

where the super-polynomial term is absorbed into the final o(1) remainder. Combining (G.13) and (G.14) proves (G.6).

Thus the finite-horizon regret is centered at the explicit suboptimal-absorption term T P∆ . The lower centered correction and the upper corrections from suboptimal absorbing branches are O(∆−∞ 1 ) + T P∆ o(1), while the remaining upper correction arises from branches absorbing into an optimal arm and is bounded by the deterministic transient term C∆ (1+o(1)). The pairwise equality corrections generated by the strict-crossing representation are controlled pairwise: for each optimal

absorbing arm i and suboptimal arm j, the event Mj = Mi contributes only T o(P(Qj )), and hence its regret contribution is absorbed into T P∆ o(1).

H. Pure Greedy Regime This section treats the pure greedy regime (α, β) = (0, 0). In this case the score-minimum boundarycrossing formulation used for regularized greedy becomes singular at zero, because an arm with no observed success has empirical score exactly zero. The policy still pulls every arm once at initialization, so the correct starting point is the initial success set S0 := {i : Xi = 1}. The pure-greedy trajectory decomposes into three branches. If S0 = ∅, all empirical scores are zero and the policy enters an absolute-zero renewal phase until the first success occurs. If |S0 | = 1, the unique initially successful arm immediately dominates all zero-score arms and absorbs. If |S0 | ≥ 2, all initially unsuccessful arms are permanently discarded, and the initially successful arms evolve as a warm-started fixed (1, 1)-regularized greedy subproblem on the active set S0 . In this reduced subproblem, every active arm starts with score 1, corresponding to one prior success and one prior pull. We first formalize this initial success-set bifurcation. We then evaluate the all-zero and singleton branches explicitly, reduce the multi-success branches to warm-started fixed (1, 1)-regularized subproblems, and combine the branchwise quantities into a finite-horizon regret sandwich. The multi-success subproblems are kept in root-based or numerical form rather than replaced by the macroscopic asymptotic envelopes, since their effective margins ∆′i = 1 − pi are fixed and do not diverge. H.1. Initial Success-Set Bifurcation In the pure greedy regime, the empirical score after the first mandatory pull is exactly the first observed reward. Therefore the trajectory after initialization is determined by the initial success set S0 := {i : Xi = 1}, where Xi ∼ Bernoulli(pi ), i = 1, . . . , K, are independent first-pull rewards. For A ⊆ {1, . . . , K}, define EA := {S0 = A}. Then P(EA ) =

i∈A

(1 − pj ).

j ∈A /

Lemma H.1 (Initial success-set bifurcation). Under the pure greedy policy, after the first mandatory pull of each arm, exactly one of the following cases occurs. 1. If A = ∅, then all empirical scores are zero. The policy repeatedly breaks ties among all K arms until the first success occurs. 2. If A = {i}, then arm i absorbs immediately: E{i} ⊆ Qi ,

Nj = 1

for all j ̸= i.

(H.1)

3. If |A| ≥ 2, then every arm outside A is abandoned after its initial pull: j∈ / A.

Nj = 1,

(H.2)

Conditional on EA , the future competition among the arms in A is exactly the warm-started (1, 1)-regularized greedy process on A. More precisely, each active arm starts the reduced process with score 1. After n ≥ 0 additional pulls of arm i ∈ A, its score is pbA i (n) =

1 + SiA (n) S A (n) + α′ = i 1+n n + β′

with α′ = 1, β ′ = 1.

Thus the reduced margins are ∆′i = α′ − pi β ′ = 1 − pi ,

i ∈ A.

Proof. After initialization, the empirical score of arm i is Xi . If A = ∅, all scores are zero, so the greedy rule has no strict maximizer and continues to tie-break among all arms until a selected arm succeeds. If A = {i}, then arm i has score 1, while every arm j ̸= i has score 0. As long as arm i is pulled, its empirical score remains strictly positive because its cumulative number of successes is at least one. Hence every zero-score arm is permanently dominated, and arm i is selected forever. This proves (H.1). If |A| ≥ 2, then each arm in A has one initial success and therefore has empirical score 1, while each arm outside A has score 0. Thus no arm outside A can ever be selected again, proving (H.2). For i ∈ A, let n ≥ 0 be the number of additional pulls after initialization and let SiA (n) be the number of additional successes. The empirical score is S A (n) + α′ 1 + SiA (n) = i 1+n n + β′

with (α′ , β ′ ) = (1, 1).

Therefore the remaining dynamics on A coincide with a warm-started (1, 1)-regularized greedy process, and the corresponding margins are ∆′i = 1 − pi . Finally, this warm start is compatible with the score-minimum reduction used below. At the beginning of the reduced process every active arm has score 1. Since pi ∈ (0, 1), an active arm that remains at score 1 remains a maximizer whenever it is present; under uniform tie-breaking among maximizers, each active arm is pulled at least once after the branch starts, almost surely. Moreover, the initial reduced-time score 1 cannot be the score minimum, because the relevant limiting mean is pi < 1. Hence including the initial warm-start state or starting the score-minimum analysis from the first additional pull gives the same potential score minimum almost surely. This lemma separates the pure-greedy trajectory into an all-zero renewal branch, deterministic singleton branches, and fixed (1, 1)-regularized multi-success subproblems.

H.2. Absolute-Zero Renewal and Singleton Absorption We now evaluate the two branches that can be resolved explicitly: the all-zero branch E∅ and the singleton branches E{i} . Absolute-zero renewal. On E∅ , all arms have empirical score zero after initialization. The policy therefore breaks ties uniformly among all K arms until the first success occurs. Let

PΣ :=

K X

pr .

(H.3)

r=1

In each zero-renewal round, arm i is selected with probability 1/K and succeeds with probability pi . Hence the probability that a given round ends with a success of arm i is pi /K, while the probability of any success is PΣ /K. Therefore, P(Qi | E∅ ) =

pi , PΣ

i = 1, . . . , K.

Let G0 be the number of failed zero-renewal rounds before the first success. Since each round succeeds with probability PΣ /K, E[G0 | E∅ ] =

K − PΣ . PΣ

Conditional on a failed renewal round, the selected arm is not uniformly distributed. Before conditioning on failure, the tie-breaking rule selects each arm with probability 1/K. However, if arm j is selected, the round fails with probability 1 − pj . Hence

P(arm j selected and failure) =

1 − pj , K

P(failure) =

K − PΣ 1 X (1 − ph ) = . K K h=1

Therefore, P(arm j selected | failure) =

1 − pj . K − PΣ

Thus failed renewal rounds are biased toward arms with larger failure probability 1 − pj . The failure labels before the terminating success are independent of the label of the terminating success. Hence, conditional on E∅ and Qi , the expected number of failed renewal pulls assigned to arm j is 1 − pj K − PΣ 1 − pj · = . PΣ K − PΣ PΣ Therefore, if j ̸= i, E[Nj | E∅ , Qi ] = 1 +

1 − pj . PΣ

Equivalently, the all-zero branch contributes P(E∅ ∩ Qi ) =

"K Y r=1

# (1 − pr )

pi , PΣ

(H.4)

E[Nj 1E∅ ∩Qi ] =

"K Y r=1

pi (1 − pr ) PΣ

1 − pj 1+ , PΣ

j ̸= i.

(H.5)

Singleton absorption. Now consider the singleton branch E{i} . In this branch, arm i has empirical score 1 after initialization, while every other arm has empirical score 0. By Lemma H.1, arm i absorbs immediately and every arm j ̸= i is pulled exactly once. Hence P(E{i} ∩ Qi ) = pi

Y (1 − pr ),

(H.6)

r̸=i

P(E{i} ∩ Qj ) = 0,

j ̸= i, Y E[Nj 1E{i} ∩Qi ] = pi (1 − pr ),

j ̸= i.

(H.7)

r̸=i

The remaining branches are those with at least two initial successes. On those branches, the puregreedy trajectory reduces to a warm-started fixed (1, 1)-regularized subproblem on the initially successful arms. H.3. Multi-Success Branches as Fixed (1, 1) Subproblems We now consider the branches EA with |A| ≥ 2. On such a branch, every arm outside A is abandoned after its initial pull, while the arms in A evolve as a warm-started fixed (1, 1)-regularized greedy process. In this reduced process, every active arm starts with score 1, corresponding to one prior success and one prior pull, and subsequent pulls are counted on the additional-pull clock. This subsection records the branchwise absorbing probabilities and capped transient counts generated by this reduced process. (1,1)

For each A ⊆ {1, . . . , K} with |A| ≥ 2, let PA

denote the law of this warm-started reduced (1,1)

(1, 1)-regularized process on the active set A. Under PA

, the score of arm h ∈ A after n ≥ 0

additional pulls is pbA h (n) =

1 + ShA (n) . 1+n

e A be the event that this reduced process absorbs into arm i ∈ A, and let N e A be the number Let Q i j of additional pulls of arm j ∈ A after the initial pure-greedy pull. Define (1,1)

ψiA := PA

e A ), (Q i h i (1,1) ejA } Q eA µA := E min{T, N i , j|i,T A

i, j ∈ A, j ̸= i.

These are fixed-parameter quantities. Since the reduced margins are ∆′h = 1 − ph , h ∈ A, they do not diverge with ∆1 . Therefore the macroscopic closed-form envelopes are not applied to the multi-success branches. A

We next define root-based envelopes for ψiA . Let FhA , F h,> , F h,≥ , and θhA denote the centered score-minimum distribution, strict and weak score-minimum tails, and Lundberg root of arm h in the reduced (1, 1)-regularized process. Shifted levels below zero contribute tail factor one and root

value zero. In the warm-started reduced process, the potential score minimum can be written as 1 + ShA (n) . n≥0 1+n

MhA := inf

The initial value at n = 0 is 1. Since ph < 1, this initial value does not affect the attained score minimum almost surely. Thus the one-arm boundary-crossing representation may equivalently be applied on the additional-pull clock after the first subsequent pull. For a centered level x ∈ (0, ph ), the reduced boundary is bA h (x) = 1 − ph + x, which is the (1, 1)-regularized boundary with reduced margin ∆′h = 1 − ph . For i ∈ A, define       Z   X A A exp − θh (x + ph − pi ) dFiA (x), ψ i :=   [0,pi )     h∈A h̸=i       Z   X A A ψ i := exp −(1 − pi + x) θh (x + ph − pi ) dFiA (x).   [0,pi )   h∈A   h̸=i

These are direct applications of the root-based score-minimum envelope to the reduced process. Indeed, in the reduced (1, 1)-regularized process, the boundary for the candidate absorbing arm i at centered level x is bA i (x) = 1 − pi + x. For a competitor h ∈ A, the shifted level is x + ph − pi , and the shifted boundary satisfies bA h (x + ph − pi ) = 1 − ph + x + ph − pi = 1 − pi + x. The corresponding positive jump size is ph − (x + ph − pi ) = pi − x. Hence the upper root envelope uses the exponent factor bA h (x + ph − pi ) = 1 − pi + x, while the lower root envelope uses bA h (x + ph − pi ) + ph − (x + ph − pi ) = 1. Together with the strict/weak winner sandwich in the reduced process, this gives A

ψA ≤ ψiA ≤ ψ i . i

(H.8)

A (x) be the strict-crossing We also need a fixed-parameter capped transient envelope. Let Hj|i,T

capped first-passage envelope from Lemma F.1, applied to the reduced active set A with (α′ , β ′ ) = (1, 1). In particular, the critical interface is bounded only by the finite-horizon cap T . A Let MhA and LA h := ph − Mh , h ∈ A, denote the potential score minimum and the centered

score-minimum variable of arm h in the reduced (1, 1)-regularized process on A. Define the strict

and weak score-minimum winner events in this reduced process by fA,> := M A > M A , ∀h ∈ A, h ̸= i , W i h i

fA,≥ := M A ≥ M A , ∀h ∈ A, h ̸= i . W i h i

The reduced absorbing event satisfies the same score-minimum sandwich as in the regularized fA,> ⊆ Q eA ⊆ W fA,≥ . process: W i

For i, j ∈ A, j ̸= i, define the pairwise equality event in the reduced process by fA,≥ ∩ {MjA = MiA }. EijA,= := W i This is the only equality event that can invalidate the strict-crossing upper bound for the abandoned e A . Equality between M A and another active count of arm j on the reduced absorbing branch Q

i i A competitor Mh , h ̸= j, does not affect the strict comparison with arm j. A A A Equivalently, after conditioning on LA i = x, the equality Mj = Mi is the event Lj = x+pj −pi .

The remaining active competitors must satisfy the weak winner inequalities LA h ≥ x + ph − pi ,

h ∈ A, h ̸= i, j.

Thus, by independence of the reduced potential streams, the pairwise equality probability admits the Stieltjes representation (1,1)

eA,= := PA ij Z =

(EijA,= ) i Y h A A A F j,≥ (x + pj − pi ) − F j,> (x + pj − pi ) F h,≥ (x + ph − pi ) dFiA (x).

[0,pi )

h∈A h̸=i,j

As before, shifted levels below zero contribute equal strict and weak tail factors and hence make zero contribution to the difference. Define the reduced pairwise capped transient envelope by Z [0,pi )

A Hj|i,T (x)

F h,≥ (x + ph − pi ) dFiA (x) + T eA,= ij

h∈A h̸=i,j

µA j|i,T :=

ψA i

(H.9)

This is the reduced-process pairwise version of Proposition F.2. The strict-crossing time is used only for the abandoned arm j, while the remaining active competitors enter through weak winner factors. The finite-horizon correction is also pairwise: it controls only the boundary event MjA = MiA , which is the only equality obstruction relevant for the abandoned count of arm j. The same pathwise argument as in Proposition F.2 gives (1,1)

ψiA µA j|i,T = EA

e A }1 eA min{T, N j Q i

Z ≤ [0,pi )

A Hj|i,T (x)

F h,≥ (x + ph − pi ) dFiA (x) + T eA,= ij .

(H.10)

h∈A h̸=i,j A

A,= A A A , (H.9) and (H.10) imply µA Since ψiA ≥ ψ A j|i,T ≤ µj|i,T . The quantities ψ i , ψ i , eij , and µj|i,T are i

fixed-parameter root-based or Stieltjes quantities and can be evaluated numerically by solving the one-arm root equations and approximating the associated Stieltjes integrals. Lemma H.2 (Multi-success branch composition). For every A ⊆ {1, . . . , K} with |A| ≥ 2, define πA :=

h∈A

(1 − ph ).

(H.11)

h∈A /

Then, for i ∈ A, P(EA ∩ Qi ) = πA ψiA ,

(H.12)

P(EA ∩ Qi ) = 0.

(H.13)

while for i ∈ / A,

Moreover, for i ∈ A and j ̸= i,  1 + µA , A j|i,T E[min{T, Nj }1EA ∩Qi ] ≤ πA ψ i 1,

j ∈ A,

(H.14)

j∈ / A.

Proof. Conditional on EA , the future dynamics on A coincide with the warm-started reduced (1, 1)regularized process defined above, and no arm outside A can be selected again. Hence the absorbing arm must belong to A, and P(Qi | EA ) = ψiA for i ∈ A. Multiplying by P(EA ) = πA gives (H.12) and (H.13). If j ∈ / A, then arm j is pulled once during initialization and never again. If j ∈ A and j ̸= i, then on EA ∩ Qi , arm j has one initial pull plus its additional pulls inside the reduced process. Therefore

 1 + min{T, N e A }, j min{T, Nj } ≤ 1,

j ∈ A, j∈ / A.

A Using ψiA ≤ ψ i and µA j|i,T ≤ µj|i,T gives (H.14).

Thus every multi-success branch is reduced to warm-started fixed (1, 1)-regularized quantities on the active set A, weighted by the explicit initial-branch probability πA .

H.4. Finite-Horizon Regret Synthesis and Linear-Regret Floor We now combine the all-zero, singleton, and multi-success branches. Recall PΣ =

h=1 ph from

(H.3), and keep the convention δi = p1 − pi . The pure-greedy finite-horizon regret is Rpg (T ) =

K X

δj E[Nj (T )].

j=2

The branchwise formulas below use the mandatory-initialization convention of this appendix. If a global horizon is counted from before initialization, the same statements hold for T ≥ K, up to the harmless deterministic initialization adjustment. For each arm i, define the lower and upper pure-greedy absorbing-probability envelopes

Ppg (Qi ) :=

"K Y

# (1 − ph )

h=1

Ppg (Qi ) :=

"K Y

Y pi + pi (1 − ph ) + PΣ h̸=i

# (1 − ph )

h=1

Y pi + pi (1 − ph ) + PΣ h̸=i

, πA ψ A i

A⊆{1,...,K} |A|≥2, i∈A

πA ψ i ,

A⊆{1,...,K} |A|≥2, i∈A

where πA is defined in (H.11). By (H.8), these quantities satisfy Ppg (Qi ) ≤ P(Qi ) ≤ Ppg (Qi ).

(H.15)

For i ̸= j, define the pure-greedy joint capped-count upper envelope pg

U j|i,T :=

"K Y

Y 1 − pj pi (1 − ph ) 1+ + pi (1 − ph ) + PΣ PΣ

h=1

h̸=i

X A⊆{1,...,K} |A|≥2, i∈A

 1 + µA , A j|i,T πA ψ i 1,

j ∈ A, j∈ / A. (H.16)

Here µA j|i,T is the pairwise strict-crossing reduced-process envelope from (H.9), including the reduced pairwise equality correction T eA,= ij . Combining (H.5), (H.7), and (H.14), we have pg

E[min{T, Nj }1Qi ] ≤ U j|i,T ,

i ̸= j.

(H.17)

Proposition H.3 (Pure-greedy finite-horizon regret sandwich). For pure greedy (α, β) = (0, 0), for every finite horizon T , Rpg (T ) ≥ T

K X i=2 pi <p1

δi Ppg (Qi ) −

K X X i=1 j̸=i pj >pi

(pj − pi ) U j|i,T ,

(H.18)

and Rpg (T ) ≤ T

K X

δi Ppg (Qi ) +

i=2 pi <p1

K X X

(pi − pj ) U j|i,T .

(H.19)

i=1 j̸=i pj <pi

Proof. The initialization events EA , A ⊆ {1, . . . , K}, form a partition. The all-zero branch contributions are given by (H.4) and (H.5); the singleton contributions are given by (H.6)–(H.7); and the multi-success contributions are bounded by Lemma H.2. Summing over branches gives (H.15) and (H.17). The regret skeleton from Proposition A.2 applies to pure greedy as well, since absorption holds also in the pure-greedy regime. Its lower side gives Rpg (T ) ≥ T

K X

δi P(Qi ) −

i=2 pi <p1

K X X

(pj − pi ) E[min{T, Nj }1Qi ] .

i=1 j̸=i pj >pi

Using P(Qi ) ≥ Ppg (Qi ) and (H.17) proves (H.18). Similarly, the upper side of Proposition A.2 gives Rpg (T ) ≤ T

K X i=2 pi <p1

δi P(Qi ) +

K X X

(pi − pj ) E[min{T, Nj }1Qi ] .

i=1 j̸=i pj <pi

Using P(Qi ) ≤ Ppg (Qi ) and (H.17) proves (H.19).

Remark H.4 (Singleton linear-regret floor). The pure-greedy policy has a positive finite-horizon linear-regret floor whenever at least one suboptimal arm has pi ∈ (0, 1). Indeed, on the singleton branch E{i} with pi < p1 , arm i absorbs immediately after the initialization phase. Hence, for any Q finite horizon T ≥ K, Ni (T ) ≥ T − K + 1 on E{i} . Since P(E{i} ) = pi h̸=i (1 − ph ), we obtain the finite-horizon lower bound Rpg (T ) ≥ (T − K + 1)

K X i=2 pi <p1

δi pi

(1 − ph ).

h̸=i

Thus the regret of pure greedy grows at least linearly in the finite horizon T , independently of the multi-success subproblem bounds. A

Remark H.5 (Numerical evaluation of fixed (1, 1)-subproblem envelopes). The quantities ψ A , ψi , i and µA j|i,T are fixed-parameter root-based envelopes. They are not replaced by the macroscopic closed-form formula because the reduced margins ∆′h = 1 − ph do not diverge. Numerically, one solves the one-arm Lundberg root equations for the reduced (1, 1)-process and evaluates the corresponding Stieltjes integrals by discretization or quadrature.

I. Regret-Certificate Calibration for Regularized Greedy This section records the regret certificate used to calibrate the regularized greedy policies. The certificate is obtained from the closed-form upper side of Theorem 2 by dropping the asymptotic remainders and keeping the two leading finite-horizon components. The horizon T is treated as a design parameter, and the arm means are treated as fixed inputs to the certificate. Thus the calibration rule can be applied to a fixed instance even though the regret envelope itself is justified under the regularization-asymptotic regime. The upper side of Theorem 2 decomposes regret into a suboptimal-absorption term and a P e i ), where δi P(Q transient-abandonment correction. The suboptimal-absorption term is T K i=2, pi <p1

e i ) is the closed-form suboptimal-convergence approximation defined in (G.5). The leading P(Q transient correction is (K −1)∆1 . Dropping the asymptotic remainders in the regret upper envelope therefore gives the calibration certificate

Rcert (T ; α, β) := T

K X

e i ) + (K − 1)∆1 . δi P(Q

(I.1)

i=2 pi <p1

This certificate preserves the main finite-horizon trade-off identified by the theory: larger regulare i ), while increasing the transient cost ization reduces the suboptimal-absorption probabilities in P(Q through ∆1 . I.1. Fixed-Tilt Optimization over the Regularization Strength We next fix the tilt and optimize the regularization strength. Write 0≤ζ<

β = ζα,

1 . p1

For this fixed tilt, define χi (ζ) := 1 − pi ζ,

ωi (ζ) :=

2χi (ζ) , pi (1 − pi )

i = 1, . . . , K.

Then ∆i = αχi (ζ),

λi = αωi (ζ).

Because ζ < 1/p1 and pi ≤ p1 , all χi (ζ) are positive. For m = 2, . . . , K, define ϱm (ζ) :=

m X

ωh (ζ)δhm .

h=1

Also set ϱK+1 (ζ) := ∞. Substituting λh = αωh (ζ) into (G.5) gives e i ; α, ζ) = P(Q

K X 1 m=i

[exp{−αϱm (ζ)} − exp{−αϱm+1 (ζ)}] ,

i = 2, . . . , K such that pi < p1 .

Indeed, m X

ωh (ζ)δhm +

h=1

m X

! ωh (ζ) δm,m+1 =

h=1

m X

ωh (ζ)δh,m+1 =

h=1

m+1 X

ωh (ζ)δh,m+1 ,

h=1

because δm+1,m+1 = 0. This gives the telescoping form above. Define Ξm :=

m X

δi ,

m = 2, . . . , K,

Ξ1 := 0,

i=2 pi <p1

and γm :=

Ξm−1 Ξm − , m m−1

m = 2, . . . , K.

Equivalently, P m m−1 X (m − 1)δm − m−1 1 X 1 i=2,pi <p1 δi γm = . δi − δi = m m−1 m(m − 1) i=2 pi <p1

i=2 pi <p1

Since δ2 ≤ · · · ≤ δm , if δm = 0, then δi = 0 for every i ≤ m, and hence γm = 0. If δm > 0, then m−1 X

δi ≤ (m − 2)δm < (m − 1)δm ,

i=2 pi <p1

so γm > 0. Therefore, γm ≥ 0,

γm > 0

⇐⇒

pm < p1 .

e i ; α, ζ) against the regret gaps. Using the convention We now sum the fixed-tilt expansion of P(Q

exp{−αϱK+1 (ζ)} = 0 and δi = 0 whenever pi = p1 , we obtain K X

e i ; α, ζ) = δi P(Q

K X

δi

m=i

i=2 pi <p1

K X m=2

K X 1

 1   m

m X

[exp{−αϱm (ζ)} − exp{−αϱm+1 (ζ)}]   δi  [exp{−αϱm (ζ)} − exp{−αϱm+1 (ζ)}]

i=2 pi <p1

K X Ξm m=2 K X

exp{−αϱm (ζ)} −

K X Ξm m=2 K+1 X

exp{−αϱm+1 (ζ)}

Ξm Ξm−1 exp{−αϱm (ζ)} − exp{−αϱm (ζ)} m m−1 m=2 m=3 K X Ξm Ξm−1 = − exp{−αϱm (ζ)} m m−1 =

m=2 K X

γm exp{−αϱm (ζ)}.

m=2

In the fourth equality, the term with m = K +1 vanishes because ϱK+1 (ζ) = ∞. Thus the weighted suboptimal-absorption term collapses into a nonnegative weighted sum of exponentials. Therefore, using the certificate in (I.1), the fixed-tilt certificate is

Rcert (T ; α, ζ) = T

K X

γm exp{−αϱm (ζ)} + (K − 1)αχ1 (ζ).

m=2

For later use, define (K − 1)χ1 (ζ) T0 (ζ) := PK m=2 γm ϱm (ζ) and ϱmin (ζ) := min ϱm (ζ). 2≤m≤K pm <p1

Proposition I.1 (Fixed-tilt calibration and logarithmic certificate growth). Suppose that at least one arm is suboptimal, so that pK < p1 , and fix 0 ≤ ζ < 1/p1 . If T ≤ T0 (ζ), then the minimizer of Rcert (T ; α, ζ) over α ≥ 0 is α⋆ (T, ζ) = 0. If T > T0 (ζ), then α⋆ (T, ζ) > 0 is uniquely characterized by K X

γm ϱm (ζ) exp{−α⋆ (T, ζ)ϱm (ζ)} =

m=2

(K − 1)χ1 (ζ) . T

(I.2)

Moreover, for T > T0 (ζ), (K − 1)χ1 (ζ) T Rcert (T ; α (T, ζ), ζ) ≤ 1 + log . ϱmin (ζ) T0 (ζ) ⋆

(I.3)

Thus, for fixed arm means and fixed feasible tilt, the minimized certificate is at most logarithmic in T . The unique positive solution in (I.2) can be computed by bisection in time polynomial in K and log(1/εα ), where εα denotes the desired accuracy for α⋆ (T, ζ). Proof. Differentiating the fixed-tilt certificate with respect to α gives ∂α Rcert (T ; α, ζ) = (K − 1)χ1 (ζ) − T

K X

γm ϱm (ζ) exp{−αϱm (ζ)}.

m=2

Differentiating once more gives K X

∂α2 Rcert (T ; α, ζ) = T

γm ϱ2m (ζ) exp{−αϱm (ζ)}.

m=2

For m ≥ 2, both γm and ϱm (ζ) are nonnegative. Moreover, if pm < p1 , then γm > 0, and ϱm (ζ) =

m X

ωh (ζ)(ph − pm ) > 0,

h=1

because the term with h = 1 is strictly positive. Since at least one arm is suboptimal, at least one term in

K X

γm ϱ2m (ζ) exp{−αϱm (ζ)}

m=2

is strictly positive. Hence ∂α2 Rcert (T ; α, ζ) > 0. Thus Rcert (T ; α, ζ) is strictly convex in α, and its derivative is strictly increasing. At α = 0, ∂α Rcert (T ; 0, ζ) = (K − 1)χ1 (ζ) − T

K X

γm ϱm (ζ).

m=2

This derivative is nonnegative exactly when T ≤ T0 (ζ). In that case, strict convexity implies that the constrained minimizer over α ≥ 0 is α⋆ (T, ζ) = 0. If T > T0 (ζ), the right derivative at zero is negative. Moreover, lim ∂α Rcert (T ; α, ζ) = (K − 1)χ1 (ζ) > 0.

α→∞

Since the derivative is continuous and strictly increasing, it has a unique zero. This zero is the unique minimizer and satisfies (I.2). The left-hand side of (I.2) is continuous and strictly decreasing in α, so bisection computes the solution. Each evaluation requires a finite sum over m = 2, . . . , K, so the computation is polynomial in K and log(1/εα ). It remains to prove the logarithmic growth bound. Let cζ := (K − 1)χ1 (ζ),

Sζ :=

K X m=2

γm ϱm (ζ).

Then T0 (ζ) = cζ /Sζ . At the interior minimizer,

K X

γm ϱm (ζ) exp{−α⋆ ϱm (ζ)} = cζ .

m=2

For every m such that γm > 0, ϱm (ζ) ≥ ϱmin (ζ), while indices with γm = 0 make no contribution. We have T

K X

γm exp{−α⋆ ϱm (ζ)} ≤

m=2

K X

ϱmin (ζ)

m=2

γm ϱm (ζ) exp{−α⋆ ϱm (ζ)} =

cζ . ϱmin (ζ)

(I.4)

Also, K X

γm ϱm (ζ) exp{−α⋆ ϱm (ζ)} ≤ Sζ exp{−α⋆ ϱmin (ζ)}.

m=2

Together with the first-order condition, this gives cζ ≤ Sζ exp{−α⋆ ϱmin (ζ)}. T Hence

⋆

α ≤

ϱmin (ζ)

log

T Sζ cζ

1 ϱmin (ζ)

log

T T0 (ζ)

(I.5)

Combining (I.4) and (I.5) with ⋆

Rcert (T ; α , ζ) = T

K X

γm exp{−α⋆ ϱm (ζ)} + cζ α⋆

m=2

proves (I.3).

I.2. Tilt Monotonicity and the Practical Near-Boundary Choice We now discuss the choice of ζ. Consider the interior calibration regime in which α⋆ (T, ζ) > 0,

∆⋆1 (T, ζ) > 0.

The previous subsection optimizes the certificate over α at a fixed tilt. For every fixed 0 ≤ ζ < 1/p1 , ∆1 = αχ1 (ζ),

χ1 (ζ) = 1 − p1 ζ > 0.

Thus α 7→ ∆1 is one-to-one on (0, ∞). Optimizing over α > 0 is therefore equivalent to optimizing over ∆1 > 0, with ∆⋆1 (T, ζ) = χ1 (ζ)α⋆ (T, ζ). We use this equivalent ∆1 -parametrization only to make the dependence on ζ transparent.

For fixed ∆1 > 0 and ζ, we have α=

∆1 , χ1 (ζ)

β=

ζ∆1 . χ1 (ζ)

Define the normalized rates m

ϱm (ζ) X 1 − ph ζ 2 ϱm (ζ) := = δhm , χ1 (ζ) ph (1 − ph ) 1 − p1 ζ

m = 2, . . . , K.

h=1

Then the same fixed-tilt certificate can be written as Rcert (T ; ∆1 , ζ) = T

K X

γm exp{−∆1 ϱm (ζ)} + (K − 1)∆1 .

m=2

This is exactly the certificate in the previous subsection after the one-to-one change of variable ∆1 = αχ1 (ζ). ⋆ (T ; ζ) := Let ∆⋆1 (T, ζ) ∈ arg min∆1 >0 Rcert (T ; ∆1 , ζ), and define the profiled certificate by Rcert

Rcert (T ; ∆⋆1 (T, ζ), ζ). ⋆ (T ; ζ) Proposition I.2 (Tilt monotonicity of the profiled certificate). The profiled certificate Rcert

is nonincreasing in ζ ∈ [0, 1/p1 ). If the arm means contain at least three distinct values, then it is strictly decreasing: d ⋆ R (T ; ζ) = ∂ζ Rcert (T ; ∆⋆1 (T, ζ), ζ) < 0. dζ cert If the arm means contain only two distinct values, then the profiled certificate is flat in ζ under the ∆1 -parametrization. Proof. For each arm h, d 1 − ph ζ −ph (1 − p1 ζ) + p1 (1 − ph ζ) p1 − p h = = . 2 dζ 1 − p1 ζ (1 − p1 ζ) (1 − p1 ζ)2 This derivative is nonnegative for every h, and it is strictly positive exactly when ph < p1 . Since ϱm (ζ) =

m X h=1

2δhm 1 − ph ζ , ph (1 − ph ) 1 − p1 ζ

and all coefficients 2δhm /[ph (1 − ph )] are nonnegative, we have ϱ′m (ζ) ≥ 0,

m = 2, . . . , K.

If the arm means contain at least three distinct values, there exist indices h < m such that p1 > ph > pm . For this pair, p1 − ph > 0,

δhm = ph − pm > 0,

so ϱ′m (ζ) > 0. Moreover, pm < p1 implies γm > 0. For fixed ∆1 > 0, differentiating the ∆1 -parametrized certificate gives ∂ζ Rcert (T ; ∆1 , ζ) = −T ∆1

K X

γm ϱ′m (ζ) exp{−∆1 ϱm (ζ)}.

m=2

Since T > 0, ∆1 > 0, and both γm and ϱ′m (ζ) are nonnegative, the partial derivative is nonpositive. If the arm means contain at least three distinct values, there exists an index m for which γm ϱ′m (ζ) > 0, so the partial derivative is strictly negative. At the interior optimizer, ∂∆1 Rcert (T ; ∆⋆1 (T, ζ), ζ) = 0. Therefore, by the envelope theorem, d ⋆ d∆⋆ (T, ζ) Rcert (T ; ζ) = ∂∆1 Rcert (T ; ∆⋆1 (T, ζ), ζ) 1 + ∂ζ Rcert (T ; ∆⋆1 (T, ζ), ζ) dζ dζ = ∂ζ Rcert (T ; ∆⋆1 (T, ζ), ζ). If the arm means contain only two distinct values, then for every m and h ≤ m, either ph = p1 , so that p1 − ph = 0, or ph = pm , so that δhm = ph − pm = 0. Therefore, every summand in ϱ′m (ζ) =

m X h=1

2(p1 − ph ) δhm ph (1 − ph )(1 − p1 ζ)2

vanishes, and hence ϱ′m (ζ) = 0

for every m.

Thus the certificate is independent of ζ under the ∆1 -parametrization, and so is its profiled value.

Proposition I.2 shows that the certificate prefers larger tilts, and when the arm means contain at least three distinct values, it strictly prefers tilts closer to the feasibility boundary 1/p1 . The boundary itself is not admissible, and taking the backoff too small is incompatible with the scaling behind the certificate. Let ζ = 1/p1 − ϵ◦ . Then χ1 (ζ) = p1 ϵ◦ ,

∆1 = αp1 ϵ◦ .

If ϵ◦ → 0 while ∆1 is treated as the regularization scale, then α = ∆1 /(p1 ϵ◦ ) becomes much larger than ∆1 , and the same issue appears for β = ζα. Moreover, for i ≥ 2 with pi < p1 , ∆i 1 − pi ζ 1 − pi /p1 + pi ϵ◦ = = , ∆1 1 − p1 ζ p1 ϵ◦

which diverges as ϵ◦ → 0. Thus an asymptotically vanishing backoff would violate the scaling conditions α = Θ(∆1 ), β = O(∆1 ), and ∆i = Θ(∆1 ). For this reason, the implemented calibration uses a fixed moderate backoff. We set ζϵ◦ := 1/p1 − ϵ◦ with ϵ◦ fixed, for example ϵ◦ = 0.2. The calibrated pair is then αϵ⋆◦ (T ) ∈ arg min Rcert (T ; α, ζϵ◦ ), α>0

βϵ⋆◦ (T ) = ζϵ◦ αϵ⋆◦ (T ).

With estimated inputs, the same rule is applied after replacing p1 and the ordered arm means by their current design estimates. The role of ϵ◦ is to keep the tilt close to the certificate-preferred boundary while preserving a regularization scale compatible with the asymptotic derivation.

Record · ID 422266 · SHA-256 3a22b10b11f88c58
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.