Introduction
Sequential experimental design was developed in the context of industrial quality control with roots in Wald’s sequential analysis [59 ] . Box and Wilson (1951) introduced response surface methodology, in which each round of experiments chooses factor levels based on the results so far. Parallel to that optimization-focused approach, sequential data monitoring and adaptive sampling ideas subsequently became central to the clinical trial literature [2 , 3 ] . More recently, software-generated alternatives have brought sequential design back to the fore: there are often many candidate models and only a limited budget for evaluating them [48 b] . Related problems of measurement and learning arise in fields such as network monitoring [38 , 64 ] and consumer studies [13 , 7 ] .
Consider n n n independent, but not necessarily identical, rested Bayesian arms with known priors and a horizon T T T . A policy π \pi π plays one arm at each step, observes its outcome, and updates the posteriors. At the end of the horizon, the policy selects an arm with the largest posterior utility. For posterior-mean as the utility, let θ i \theta_i θ i denote the latent mean reward of arm i i i , and let F T π \mathcal{F}^{\pi}_T F T π denote the information available after exploration. Define the value of the optimum policy O P T T \mathrm{OPT}_T OPT T as follows
V T ( π ) = E [ max i E [ θ i ∣ F T π ] ] , O P T T = sup π V T ( π ) , V_T(\pi)=\mathbb{E}\left[\max_i\mathbb{E}[\theta_i\mid\mathcal{F}^{\pi}_T]\right], \qquad\mathrm{OPT}_T=\sup_{\pi}V_T(\pi), V T ( π ) = E [ i max E [ θ i ∣ F T π ] ] , OPT T = π sup V T ( π ) ,
where the supremum is over policies satisfying the exploration budget. Rewards obtained during exploration do not contribute to this objective and standard cumulative regret is a very different optimization. Simple regret [12 , 4 ] compares the selected arm with the best arm under the true means [11 Section 7.2] ; averaged over the prior it is E [ max i θ i ] − V T ( A L G ) \mathbb{E}[\max_i\theta_i]-V_T(\mathrm{ALG}) E [ max i θ i ] − V T ( ALG ) , which splits into E [ max i θ i ] − O P T T \mathbb{E}[\max_i\theta_i]-\mathrm{OPT}_T E [ max i θ i ] − OPT T , the least regret achievable with the budget, and O P T T − V T ( A L G ) \mathrm{OPT}_T-V_T(\mathrm{ALG}) OPT T − V T ( ALG ) , the loss from the chosen policy.
Consider n = 2 T n=2T n = 2 T independent, identically distributed arms, each with θ i = 1 \theta_i=1 θ i = 1 with probability 1 / n 1/n 1/ n and θ i = 0 \theta_i=0 θ i = 0 otherwise, where one play reveals θ i \theta_i θ i . This is a needle-in-a-haystack example with non-vanishing expected reward where the perfect-information value tends to 1 − e − 1 1-e^{-1} 1 − e − 1 , whereas O P T T = 1 − ( 1 − 1 / n ) T + 1 → 1 − e − 1 / 2 \mathrm{OPT}_T=1-(1-1/n)^{T+1}\to1-e^{-1/2} OPT T = 1 − ( 1 − 1/ n ) T + 1 → 1 − e − 1/2 . The extra term in the exponent accounts for selecting an uninspected arm after T T T unsuccessful inspections. The budget thus allows substantial value, but even the optimal policy has limiting simple regret e − 1 / 2 − e − 1 > 0 e^{-1/2}-e^{-1}>0 e − 1/2 − e − 1 > 0 . If instead T = o ( n ) T=o(n) T = o ( n ) with the same success probability 1 / n 1/n 1/ n , O P T T → 0 \mathrm{OPT}_T\to0 OPT T → 0 . The optimal policy and a policy inspecting only one arm then have the same limiting simple regret 1 − e − 1 1-e^{-1} 1 − e − 1 , although the latter obtains only an O ( 1 / T ) O(1/T) O ( 1/ T ) fraction of O P T T \mathrm{OPT}_T OPT T . Measuring policies against O P T T \mathrm{OPT}_T OPT T distinguishes policy quality from this unavoidable informational loss.
The Gittins index [61 , 24 ] is optimal for discounted cumulative reward, but not for a fixed exploration budget followed by a single terminal choice. The problem can be formulated as a Markov decision process and solved by dynamic programming [6 , 9 ] over the joint product state space of the arms. This computation is exponential in general, and no exact algorithm is known that runs in time polynomial in the sum of the single-arm state spaces. Madani et al. (2004a) show that the problem is NP-hard when plays of different arms have different costs, and leave the unit-cost case, studied here, open. We focus on efficient algorithms guaranteeing V T ( A L G ) ≥ f ⋅ O P T T V_T(\mathrm{ALG}) \ge f \cdot\mathrm{OPT}_T V T ( ALG ) ≥ f ⋅ OPT T , where A L G \mathrm{ALG} ALG denotes the algorithm under consideration (by convention, for maximization problems, the factor f ≤ 1 f \le1 f ≤ 1 , larger is better). Our upper bounds on O P T T \mathrm{OPT}_T OPT T come from linear programming relaxations with optimal value L P ≥ O P T T \mathrm{LP} \ge\mathrm{OPT}_T LP ≥ OPT T ; the ratio L P / O P T T \mathrm{LP}/\mathrm{OPT}_T LP / OPT T is the integrality gap.
The budgeted problem was posed by Madani et al. (2004b), and Guha and Munagala (2007, 2008) gave the first constant-factor approximations through LP relaxations. In their consolidated treatment, Guha and Munagala (2013, Section 7) (abbreviated GM13 henceforth) obtain a 1/3 approximation by balancing a Lagrangian bound and executing the resulting policies. Ma (2018, Section 1.3) gives an LP-based 4/27 guarantee for a more general Markovian model that does not require exchangeability. We show that these guarantees are tight for the corresponding algorithms, even when their relaxations are asymptotically exact (Propositions 2.4 and 2.6 ). We then provide a better algorithm achieving a factor $(1-e^{-2})/2 \approx 0.43 ({xref}Section 2.1`).
Our main technical tool is selection-preserving truncation for Bayesian arms with exchangeable observations in [ 0 , 1 ] [0,1] [ 0 , 1 ] (§ 4 ). The local policies of an optimal LP solution can be truncated to depth k = O ( log ( n / ( ϵ L P ) ) / ( ϵ 2 L P ) ) k = O(\log(n/(\epsilon\mathrm{LP}))/(\epsilon^2\mathrm{LP})) k = O ( log ( n / ( ϵ LP )) / ( ϵ 2 LP )) , with no explicit dependence on T T T , while preserving each arm’s selection probability, not increasing its expected play count, and losing at most 4 ϵ L P 4\epsilon\mathrm{LP} 4 ϵ LP reward in aggregate (Corollary 4.3). The short-policy result of § 3 then incurs little additional loss beyond the selection-only factor 1 − e − 1 1-e^{-1} 1 − e − 1 . Together these give a ( 1 − e − 1 − o ( 1 ) ) (1-e^{-1}-o(1)) ( 1 − e − 1 − o ( 1 )) approximation against LP when T ⋅ L P ≫ log ( n / L P ) T \cdot\mathrm{LP} \gg\log(n/\mathrm{LP}) T ⋅ LP ≫ log ( n / LP ) , and establish the tight asymptotic integrality gap 1 / ( 1 − e − 1 ) 1/(1-e^{-1}) 1/ ( 1 − e − 1 ) (Corollary 4.5). We call this the non-vanishing regime : for n ≥ 2 n \ge2 n ≥ 2 , u = log ( n / L P ) / ( T ⋅ L P ) → 0 u = \log(n/\mathrm{LP})/(T \cdot\mathrm{LP}) \to0 u = log ( n / LP ) / ( T ⋅ LP ) → 0 , so the LP value does not vanish on the scale log ( n / L P ) / T \log(n/\mathrm{LP})/T log ( n / LP ) / T . The regime allows L P → 0 \mathrm{LP} \to0 LP → 0 and n > T n > T n > T . The condition implies that the truncation depth k k k is o ( T ) o(T) o ( T ) , so the scheduling loss vanishes with the parameters set in Corollary 4.5. Outside it, two guarantees remain: Theorem 2.1 gives 0.43 on every instance, and for one-play revelations Theorem 3.3 with k = 1 k=1 k = 1 gives ( 1 − e − 1 − O ( log T / T ) ) L P (1-e^{-1}-O(\sqrt{\log T/T}))\mathrm{LP} ( 1 − e − 1 − O ( log T / T )) LP even when O P T → 0 \mathrm{OPT} \to0 OPT → 0 , as in the needle family with T = o ( n ) T=o(n) T = o ( n ) . Over all exchangeable instances, the worst-case integrality gap of LP is therefore at least 1 / ( 1 − e − 1 ) 1/(1-e^{-1}) 1/ ( 1 − e − 1 ) and at most 2 / ( 1 − e − 2 ) 2/(1-e^{-2}) 2/ ( 1 − e − 2 ) ; we do not know whether instances outside the regime can exceed 1 / ( 1 − e − 1 ) 1/(1-e^{-1}) 1/ ( 1 − e − 1 ) .
Section 5 uses the dual of the truncated LP as a computable, instance-specific upper bound on the value of further evaluation. This gives a stopping rule with a simple-regret guarantee, and variants for switching, setup and movement budgets. Section 6 treats terminal utilities, satisficing, and joint selection and prediction objectives.
Related work
Budgeted learning and model selection. Budgeted learning of naive-Bayes classifiers purchases attribute values of labelled examples under a hard budget [46 ] . Proposals for this problem include Biased Robin and single-feature lookahead [46 , 40 ] , reinforcement learning [41 ] , and purchase rules derived from bandit algorithms [17 , 18 ] . Without a hard budget, the related problem is active feature-value acquisition [54 ] . A bounded active classifier also pays for attributes used at prediction time [28 ] ; its budgeted learning therefore ends with a subset choice [39 ] . Modern model selection likewise allocates limited evaluation to many candidate configurations [44 ] , or evaluates pre-trained classifiers under a labelling budget [42 ] . The latter considers dependence outside our independent-arm model.
Optimization formulations. § 2.4 separates selectable martingale payoffs from the late payoffs in general Markov models [34 ] (Ma 2018); the latter require time-indexed relaxations. Goel et al. (2009) proposed a ratio index for budgeted learning.1 When one inspection resolves an alternative and inspections are priced, Pandora’s box optimizes expected selected value minus inspection costs [60 ] . LP relaxations of adaptive policies are also used for stochastic knapsack [15 ] and stochastic probing [27 , 33 ] .
Pure exploration, selection, and stopping. Bayesian ranking and selection uses the expected largest posterior mean after a measurement budget; the knowledge gradient chooses each measurement by its one-step value (Frazier et al., 2008). Sampling and stopping are already coupled in this literature. Frazier and Powell [22 ] jointly design them with a myopic measurement-cost objective. Eckman and Henderson [19 ] give computationally efficient checks of posterior selection probability and expected opportunity cost. Hay et al. [35 ] analyze the value of further sampling, including perfect-information bounds and finite sampling bounds for one Bernoulli arm with measurement costs. In Bayesian optimization, Ishibashi et al. [37 ] use changes in an expected simple-regret criterion, Wilson [62 ] certifies posterior probability of near-optimality, and Xie et al. [63 ] study cost-adjusted simple regret and expected-budget guarantees.
Resource constraints and switching. Bandits with knapsacks add resource budgets to online reward maximization [5 ] . Their LP bounds and primal-dual resource prices provide an optimization perspective on learning under limited supply; Agrawal and Devanur [1 ] extend the model to concave rewards and convex constraints. These objectives value outcomes during learning, whereas here observations precede a terminal choice. In pure exploration, Li and Cheung [45 ] study best-arm identification with resource consumption on each pull, distinguishing deterministic and stochastic consumption. Resource use can also depend on the order of evaluation: Hong and Nelson [36 ] explicitly trade sampling against switching in indifference-zone selection, and Mwai et al. [50 ] constrain the expected switching rate in fixed-confidence exploration. For cumulative regret, Simchi-Levi and Xu [57 ] study hard switching budgets and characterize phase transitions in the minimax rate; Koren et al. [43 ] study adversarial losses with metric movement penalties.
Policies and relaxations
There are n n n independent rested arms. Arm i i i has root ρ i \rho_i ρ i , states u ∈ S i u \in\mathcal{S}_i u ∈ S i , and transitions u → v u \to v u → v with probabilities p u v p_{uv} p uv . Each transition consumes one play. Local depth is included in the state and is at most T T T . The arm can be selected at any state for a known nonnegative payoff r u r_u r u . Until Section 2.4, we assume
r u ≥ ∑ v : u → v p u v r v . (1) r_u \ge\sum_{v:u\to v} p_{uv}r_v. \tag*{(1)} r u ≥ v : u → v ∑ p uv r v . (1)
Equality is the martingale case. Only the terminal selection contributes to the objective. A global policy uses at most T T T plays and selects at most one arm. For the Bayesian model used in Section 4, each arm has a fixed latent reward distribution on [ 0 , 1 ] [0,1] [ 0 , 1 ] , drawn independently from its prior. Conditional on this distribution, observations are iid and immediately available. Its mean is θ i \theta_i θ i , and r u = E [ θ i ∣ u ] r_u = \mathbb{E}[\theta_i \mid u] r u = E [ θ i ∣ u ] . Thus observations are exchangeable, and (1) holds with equality.
Local policies. A single-arm policy P P P terminates by selecting or quitting, and uses at most T T T plays. Following GM13, let R ~ ( P ) \widetilde{R}(P) R ( P ) be its expected selected payoff, I ( P ) I(P) I ( P ) its selection probability, and W ( P ) W(P) W ( P ) its expected play count. For a fixed policy P i P_i P i write
R i = R ~ ( P i ) , q i = I ( P i ) , w i = W ( P i ) . R_i = \widetilde{R}(P_i), \quad q_i = I(P_i), \quad w_i = W(P_i). R i = R ( P i ) , q i = I ( P i ) , w i = W ( P i ) .
For each P i P_i P i , consider its complete local execution from its root to its own terminal decision, without the shared play budget. Let τ i \tau_i τ i be its random duration, I i I_i I i its selection indicator, and Y i = r u i I i Y_i = r_{u_i} I_i Y i = r u i I i its selected payoff, with Y i = 0 Y_i = 0 Y i = 0 if it quits. Hence R i = E Y i R_i = \mathbb{E}Y_i R i = E Y i , q i = E I i q_i = \mathbb{E}I_i q i = E I i , and w i = E τ i w_i = \mathbb{E}\tau_i w i = E τ i . Use independent transitions and local randomization across arms, so ( τ i , I i , Y i ) (\tau_i, I_i, Y_i) ( τ i , I i , Y i ) are independent across i i i . To analyze a global execution, use these same outcomes and local decisions whenever it runs P i P_i P i . The variables above describe the complete local execution, even if the global execution never starts P i P_i P i or interrupts it before its terminal decision. The null policy quits immediately without playing or selecting; its duration, selection indicator, and selected payoff are all zero.
Two constraints. The relaxations are standard:
L P = max { P i } { ∑ i R i : ∑ i q i ≤ 1 , ∑ i w i ≤ T } . (2) \mathrm{LP}=\max_{\{\mathcal{P}_i\}}\left\{\sum_i R_i:\sum_i q_i\le1,\ \sum_i w_i\le T\right\}. \tag*{(2)} LP = { P i } max { i ∑ R i : i ∑ q i ≤ 1 , i ∑ w i ≤ T } . (2)
L P B u d = max { P i } { ∑ i R i : ∑ i ( q i + w i / T ) ≤ 2 } . (3) \mathrm{LPBud}=\max_{\{\mathcal{P}_i\}}\left\{\sum_i R_i:\sum_i(q_i+w_i/T)\le2\right\}. \tag*{(3)} LPBud = { P i } max { i ∑ R i : i ∑ ( q i + w i / T ) ≤ 2 } . (3)
The LPBud formulation was introduced in Guha and Munagala [32 ] . Marginalizing a feasible global policy over all other arms gives feasible local flows for (2). Adding the two constraints gives
O P T ≤ L P ≤ L P B u d . (4) \mathrm{OPT}\le\mathrm{LP}\le\mathrm{LPBud}. \tag*{(4)} OPT ≤ LP ≤ LPBud . (4)
For completeness, the local flow variables are reach z u z_u z u , play x u x_u x u , and selection s u s_u s u , satisfying
z ρ i = 1 , z v = ∑ u : u → v p u v x u , x u + s u ≤ z u , z u , x u , s u ≥ 0. (5) z_{\rho_i}=1,\qquad z_v=\sum_{u:u\to v}p_{uv}x_u,\qquad x_u+s_u\le z_u,\qquad z_u,x_u,s_u\ge0. \tag*{(5)} z ρ i = 1 , z v = u : u → v ∑ p uv x u , x u + s u ≤ z u , z u , x u , s u ≥ 0. (5)
where the equation for z v z_v z v applies only to nonroot states v ≠ ρ i v\ne\rho_i v = ρ i , and x u = 0 x_u=0 x u = 0 at depth T T T . Then R i = ∑ u r u s u R_i=\sum_u r_us_u R i = ∑ u r u s u , q i = ∑ u s u q_i=\sum_u s_u q i = ∑ u s u , and w i = ∑ u x u w_i=\sum_u x_u w i = ∑ u x u . The unused mass quits. Dividing play and selection flows by reach probabilities implements the local policy.
Prices and computation. With selection price η \eta η and play price λ \lambda λ , the single-arm surplus is
G i ( u ; η , λ ) = max { 0 , r u − η , − λ + ∑ v p u v G i ( v ; η , λ ) } . (6) G_i(u;\eta,\lambda)=\max\left\{0,\ r_u-\eta,\ -\lambda+\sum_v p_{uv}G_i(v;\eta,\lambda)\right\}. \tag*{(6)} G i ( u ; η , λ ) = max { 0 , r u − η , − λ + v ∑ p uv G i ( v ; η , λ ) } . (6)
The play option is omitted at depth T T T . Finite LP duality gives
L P = min η , λ ≥ 0 { η + λ T + ∑ i G i ( ρ i ; η , λ ) } . (7) \mathrm{LP}=\min_{\eta,\lambda\ge0}\left\{\eta+\lambda T+\sum_iG_i(\rho_i;\eta,\lambda)\right\}. \tag*{(7)} LP = η , λ ≥ 0 min { η + λ T + i ∑ G i ( ρ i ; η , λ ) } . (7)
L P B u d = min ν ≥ 0 { 2 ν + ∑ i G i ( ρ i ; ν , ν / T ) } . (8) \mathrm{LPBud}=\min_{\nu\ge0}\left\{2\nu+\sum_iG_i(\rho_i;\nu,\nu/T)\right\}. \tag*{(8)} LPBud = ν ≥ 0 min { 2 ν + i ∑ G i ( ρ i ; ν , ν / T ) } . (8)
Computation is polynomial in the supplied finite state spaces and rational input encoding. For succinct or continuous priors, state-space construction or an equivalent local optimization oracle is an additional computational assumption.
A (1-exp(-2))/2 approximation
Fix local policies feasible for (3). Discard zero-reward policies and let
b i = q i + w i / T , d i = R i / b i , β = ∑ i b i ≤ 2 , R = ∑ i R i . (9) b_i=q_i+w_i/T,\qquad d_i=R_i/b_i,\qquad\beta=\sum_i b_i\le2,\qquad\mathcal{R}=\sum_iR_i. \tag*{(9)} b i = q i + w i / T , d i = R i / b i , β = i ∑ b i ≤ 2 , R = i ∑ R i . (9)
Order the arms by nonincreasing d i d_i d i . Their policies run contiguously, moving to the next when an arm quits. At a local selection, select that arm and stop. If the budget interrupts a policy, select the currently active arm. If the list is exhausted without a selection, choose an arm with the largest currently selectable payoff r u i r_{u_i} r u i . Make the same choice if the budget is exhausted just as a policy quits. Selection at a root does not use a play.
Theorem 2.1. Let local policies be feasible for (3), with b i b_i b i , β \beta β and R \mathcal{R} R as in (9), and execute them as above. Under (1), A L G ≥ ϕ ( β ) R \mathrm{ALG}\ge\phi(\beta)\mathcal{R} ALG ≥ ϕ ( β ) R where ϕ ( x ) = 1 − e − x x \phi(x)=\frac{1-e^{-x}}{x} ϕ ( x ) = x 1 − e − x with ϕ ( 0 ) = 1 \phi(0)=1 ϕ ( 0 ) = 1 . For an optimal solution of (3), this gives A L G ≥ ( 1 − e − 2 ) L P B u d / 2 \mathrm{ALG}\ge(1-e^{-2})\mathrm{LPBud}/2 ALG ≥ ( 1 − e − 2 ) LPBud /2 .
Proof. Let A i A_i A i be the event that policy i i i starts, and define α i = P ( A i ) \alpha_i = \mathbb{P}(A_i) α i = P ( A i ) . Whether P i P_i P i starts depends only on the outcomes and decisions of earlier policies, so A i A_i A i is independent of ( τ i , I i , Y i ) (\tau_i, I_i, Y_i) ( τ i , I i , Y i ) and E [ 1 A i Y i ] = α i R i \mathbb{E}[1_{A_i}Y_i] = \alpha_i R_i E [ 1 A i Y i ] = α i R i .
Let H \mathcal{H} H be the final execution history, including the observed outcomes and policy randomization. Write V e x e c V_{\mathrm{exec}} V exec for the selected payoff, so A L G = E [ V e x e c ] \mathrm{ALG} = \mathbb{E}[V_{\mathrm{exec}}] ALG = E [ V exec ] . Every admitted policy except possibly the last has completed. A policy that quits has Y i = 0 Y_i = 0 Y i = 0 ; a policy that selects has Y i = r u Y_i = r_u Y i = r u , which the execution obtains before stopping. If the budget interrupts the last policy at state u u u , then (1) and bounded optional stopping give
E [ Y i ∣ H ] ≤ E [ r u τ i ∣ H ] ≤ r u . \mathbb{E}[Y_i \mid\mathcal{H}] \le\mathbb{E}[r_{u_{\tau_i}} \mid\mathcal{H}] \le r_u. E [ Y i ∣ H ] ≤ E [ r u τ i ∣ H ] ≤ r u .
The first inequality uses Y i = 0 ≤ r u τ i Y_i = 0 \le r_{u_{\tau_i}} Y i = 0 ≤ r u τ i when P i P_i P i quits. Selecting the current arm obtains r u r_u r u , which therefore dominates its expected unfinished payoff. If execution ends after all started policies have quit, every corresponding Y i Y_i Y i is zero, and the arm selected by the terminal rule has payoff max i r u i ≥ 0 \max_i r_{u_i} \ge0 max i r u i ≥ 0 by the model assumption. In each case,
V e x e c ≥ E [ ∑ i 1 A i Y i ∣ H ] . V_{\mathrm{exec}} \ge\mathbb{E}\left[\left.\sum_i 1_{A_i}Y_i \right| \mathcal{H}\right]. V exec ≥ E [ i ∑ 1 A i Y i H ] .
Taking expectations gives the required lower bound:
A L G ≥ ∑ i E [ 1 A i Y i ] = ∑ i α i R i . (10) \mathrm{ALG} \ge\sum_i \mathbb{E}[1_{A_i}Y_i] = \sum_i \alpha_i R_i. \tag*{(10)} ALG ≥ i ∑ E [ 1 A i Y i ] = i ∑ α i R i . (10)
To bound admission probabilities, set Z i = I i + τ i / T Z_i = I_i + \tau_i/T Z i = I i + τ i / T , so that E Z i = b i \mathbb{E}Z_i = b_i E Z i = b i , and define
H k = ∑ i ≤ k α i b i , X k = ∑ i ≤ k b i . H_k = \sum_{i\le k} \alpha_i b_i,\qquad X_k = \sum_{i\le k} b_i. H k = i ≤ k ∑ α i b i , X k = i ≤ k ∑ b i .
with H 0 = X 0 = 0 H_0 = X_0 = 0 H 0 = X 0 = 0 . Policy k + 1 k+1 k + 1 is blocked only if execution has already stopped at a started policy j ≤ k j \le k j ≤ k , either by a local selection (I j = 1 I_j = 1 I j = 1 ) or by exhausting the budget. In the latter case, the complete local durations of the started policies sum to at least T T T . Thus either reason for blocking implies ∑ i ≤ k 1 A i Z i ≥ 1 \sum_{i\le k}1_{A_i}Z_i \ge1 ∑ i ≤ k 1 A i Z i ≥ 1 , and independence of A i A_i A i and Z i Z_i Z i shows that this sum has expectation H k H_k H k . Denote ( x ) + = max { 0 , x } (x)^+ = \max\{0,x\} ( x ) + = max { 0 , x } . Markov's inequality gives
1 − α k + 1 ≤ H k , H k ≥ H k − 1 + b k ( 1 − H k − 1 ) + . 1-\alpha_{k+1} \le H_k,\qquad H_k \ge H_{k-1}+b_k(1-H_{k-1})^+. 1 − α k + 1 ≤ H k , H k ≥ H k − 1 + b k ( 1 − H k − 1 ) + .
It follows that
H k ≥ 1 − ∏ i ≤ k ( 1 − b i ) + ≥ 1 − e − X k ≥ ϕ ( β ) X k . (11) H_k \ge1-\prod_{i\le k}(1-b_i)^+ \ge1-e^{-X_k} \ge\phi(\beta)X_k. \tag*{(11)} H k ≥ 1 − i ≤ k ∏ ( 1 − b i ) + ≥ 1 − e − X k ≥ ϕ ( β ) X k . (11)
Since q i ≤ 1 q_i \le1 q i ≤ 1 and w i / T ≤ 1 w_i/T \le1 w i / T ≤ 1 , a single load b i b_i b i can lie in ( 1 , 2 ] (1,2] ( 1 , 2 ] . Then ( 1 − b i ) + = 0 (1-b_i)^+ = 0 ( 1 − b i ) + = 0 , and the recurrence gives H k ≥ 1 H_k \ge1 H k ≥ 1 ; the positive part records this case. Set d n + 1 = 0 d_{n+1}=0 d n + 1 = 0 . The density order is used only in the next step:
∑ i α i R i = ∑ k ( d k − d k + 1 ) H k ≥ ϕ ( β ) ∑ k ( d k − d k + 1 ) X k \sum_i \alpha_iR_i=\sum_k(d_k-d_{k+1})H_k\ge\phi(\beta)\sum_k(d_k-d_{k+1})X_k i ∑ α i R i = k ∑ ( d k − d k + 1 ) H k ≥ ϕ ( β ) k ∑ ( d k − d k + 1 ) X k
which is ϕ ( β ) R \phi(\beta)R ϕ ( β ) R . The theorem follows. □ \square □
At a selection or an interruption, choosing instead an arm with the largest currently selectable payoff (the largest posterior mean in the Bayesian model) can only increase the payoff and uses no plays, so the guarantee still holds.
Tightness of both relaxations
The following examples distinguish a loss in the relaxation from a loss in executing its local policies.
General martingale signals
Proposition 2.2. There are instances with independent Markov arms, whose nonnegative payoffs are martingales selectable at every state, such that LPBud = LP = 2, while both OPT and ALGc u r _{\mathrm{cur}} cur (the execution of Theorem 2.1) tend to 1 − e − 2 1-e^{-2} 1 − e − 2 . Thus this execution is asymptotically optimal on these instances, while both LP gaps approach 2 / ( 1 − e − 2 ) 2/(1-e^{-2}) 2/ ( 1 − e − 2 ) .
Proof. Fix n ≥ 3 n \ge3 n ≥ 3 , set T = n 2 T=n^2 T = n 2 , and define
p = 1 n + 1 , a = 1 n − p T , z = 1 − a − p = ( 1 − 1 / n ) 2 , h = 1 + 1 T a . p=\frac{1}{n+1}, \qquad a=\frac{1}{n}-\frac{p}{T}, \qquad z=1-a-p=(1-1/n)^2, \qquad h=1+\frac{1}{Ta}. p = n + 1 1 , a = n 1 − T p , z = 1 − a − p = ( 1 − 1/ n ) 2 , h = 1 + T a 1 . There are n n n identical independent arms, each with prior mean μ = 2 / n \mu=2/n μ = 2/ n . The first play reveals a known value h h h with probability a a a , a continuation of posterior mean one with probability p p p , and a known zero with probability z z z .
On the continuation branch, the latent value is T T T with probability 1 / T 1/T 1/ T and zero otherwise. The next T − 2 T-2 T − 2 plays reveal no information. The following play, at local depth T T T , reveals the latent value. Every intermediate state can be selected for its posterior mean one. Since a h + p = 2 / n ah+p=2/n ah + p = 2/ n , the payoffs satisfy the martingale identity at the root as well as throughout the continuation.2
The LP values. For each arm, play once; select the known h h h , quit at zero, and complete a continuation, selecting only its positive terminal. The local quantities are
q = a + p / T = 1 / n , R = a h + p = 2 / n , w = 1 + p ( T − 1 ) = T / n . q=a+p/T=1/n,\qquad R=ah+p=2/n,\qquad w=1+p(T-1)=T/n. q = a + p / T = 1/ n , R = ah + p = 2/ n , w = 1 + p ( T − 1 ) = T / n . Across all arms, selection mass is one, expected work is T T T , and expected selected reward is two. These policies are feasible for both LPs and attain value two. Conversely, nonnegativity and optional stopping imply R i ≤ r ρ i R_i\le r_{\rho_i} R i ≤ r ρ i for every single-arm policy. Hence
∑ i R i ≤ ∑ i r ρ i = n ( 2 / n ) = 2. \sum_i R_i\le\sum_i r_{\rho_i}=n(2/n)=2. i ∑ R i ≤ i ∑ r ρ i = n ( 2/ n ) = 2. Thus LPBud = LP = 2.
Analysis. All these policies have density R / ( q + w / T ) = 1 R/(q+w/T)=1 R / ( q + w / T ) = 1 , so their order is immaterial. The execution passes through zero branches until it meets an h h h branch or a continuation. It selects h h h immediately in the former case. If a continuation belongs to the first arm, it can finish and has expected reward one. If it belongs to a later arm, the deadline interrupts it before revelation, and selecting its current state gives reward one. Therefore
A L G c u r ≥ ( a h + p ) ∑ j = 0 n − 1 z j = 2 n 2 n − 1 [ 1 − ( 1 − 1 / n ) 2 n ] ⟶ 1 − e − 2 . \mathrm{ALG}_{\mathrm{cur}}\ge(ah+p)\sum_{j=0}^{n-1}z^j=\frac{2n}{2n-1}\left[1-(1-1/n)^{2n}\right]\longrightarrow1-e^{-2}. ALG cur ≥ ( ah + p ) j = 0 ∑ n − 1 z j = 2 n − 1 2 n [ 1 − ( 1 − 1/ n ) 2 n ] ⟶ 1 − e − 2 . Selecting the largest currently selectable payoff at termination can only improve this value and requires no additional plays.
Feasible policies. Without a completed revelation, only first plays provide information. Observing all n n n roots fits within the budget and maximizes the expected largest selectable payoff among such policies: further root observations cannot decrease this expectation. The maximum after observing every root is at most h h h , and is zero when all roots are zero. Its expectation is therefore at most h ( 1 − z n ) h(1-z^n) h ( 1 − z n ) .
A full revelation requires all T T T plays on one arm, so it can occur only when the first arm enters continuation, an event of probability p p p . Conditional on this event, completing the arm has expected reward at most 1 + μ 1+\mu 1 + μ : if the revealed value is zero, an unplayed arm can be selected for its prior payoff μ \mu μ . Even crediting this entire contribution in addition to the root-observation bound gives
A L G c u r ≤ O P T ≤ h ( 1 − z n ) + p ( 1 + μ ) . \mathrm{ALG}_{\mathrm{cur}}\le\mathrm{OPT}\le h(1-z^n)+p(1+\mu). ALG cur ≤ OPT ≤ h ( 1 − z n ) + p ( 1 + μ ) . Since h → 1 h\to1 h → 1 , z n → e − 2 z^n\to e^{-2} z n → e − 2 , and p ( 1 + μ ) → 0 p(1+\mu)\to0 p ( 1 + μ ) → 0 , the upper bound also tends to 1 − e − 2 1-e^{-2} 1 − e − 2 . This proves both the LP gap and the asymptotic optimality of our execution.
These arms are martingale signals rather than conditionally iid reward observations. For exchangeable observations, the next example separates the two relaxations.
Exchangeable one-play observations
Proposition 2.3. There are exchangeable one-play instances with T = n 2 T=n^2 T = n 2 for which
L P B u d = 2 − 1 / n , L P = 1 , O P T = 1 − ( 1 − 1 / n ) 2 n . \mathrm{LPBud}=2-1/n,\qquad\mathrm{LP}=1,\qquad\mathrm{OPT}=1-(1-1/n)^{2n}. LPBud = 2 − 1/ n , LP = 1 , OPT = 1 − ( 1 − 1/ n ) 2 n . Thus the L P B u d \mathrm{LPBud} LPBud gap still approaches 2 / ( 1 − e − 2 ) 2/(1-e^{-2}) 2/ ( 1 − e − 2 ) .
Proof. For n ≥ 3 n\ge3 n ≥ 3 , each arm has latent mean θ i ∈ { 0 , 1 } \theta_i\in\{0,1\} θ i ∈ { 0 , 1 } with p = P ( θ i = 1 ) = 2 / n − 1 / n 2 p=\mathbb{P}(\theta_i=1)=2/n-1/n^2 p = P ( θ i = 1 ) = 2/ n − 1/ n 2 . Each observation is Bernoulli(θ i \theta_i θ i ), so one play reveals the mean. Playing every arm once and selecting on a positive observation gives q i = R i = p q_i=R_i=p q i = R i = p , w i = 1 w_i=1 w i = 1 , and total combined load two. The sum of prior means bounds the sum of local selected rewards, so L P B u d = n p = 2 − 1 / n \mathrm{LPBud}=np=2-1/n LPBud = n p = 2 − 1/ n .
For the separate constraints, every selected payoff is at most one, so L P ≤ 1 \mathrm{LP}\le1 LP ≤ 1 . Play each arm once and select a positive observation with probability 1 / ( n p ) 1/(np) 1/ ( n p ) ; this attains one with selection mass one and work n ≤ T n\le T n ≤ T . Finally, all arms can be observed, and the optimum equals the probability that at least one is positive: 1 − ( 1 − p ) n = 1 − ( 1 − 1 / n ) 2 n 1-(1-p)^n=1-(1-1/n)^{2n} 1 − ( 1 − p ) n = 1 − ( 1 − 1/ n ) 2 n . The execution of Theorem 2.1 on the policies above selects the first positive arm and obtains OPT. □
GM13’s algorithm is tight at 1/3
GM13 balances ∑ i G i ( ρ i ; ν , ν / T ) = ν \sum_i G_i(\rho_i;\nu,\nu/T)=\nu ∑ i G i ( ρ i ; ν , ν / T ) = ν , obtaining the dual bound 3 ν 3\nu 3 ν , and executes in an arbitrary arm order until the first local selection [32 Section 7] .
Proposition 2.4. There are exchangeable one-play instances on which GM13’s balanced-price algorithm satisfies A L G / O P T → 1 / 3 \mathrm{ALG}/\mathrm{OPT}\to1/3 ALG / OPT → 1/3 under every arm ordering, including density ordering, while L P / O P T → 1 \mathrm{LP}/\mathrm{OPT}\to1 LP / OPT → 1 and L P B u d / O P T → 1 \mathrm{LPBud}/\mathrm{OPT}\to1 LPBud / OPT → 1 . Every local decision at the balanced price is strict.
Proof. Let T = n ≥ 4 T=n\ge4 T = n ≥ 4 . The n n n arms are independent and identically distributed, with
p n = 2 n 2 , ℓ n = n − 1 n 2 − 2 , P ( θ i = 1 ) = p n , P ( θ i = ℓ n ) = 1 − p n . p_n=\frac{2}{n^2},\qquad\ell_n=\frac{n-1}{n^2-2},\qquad\mathbb{P}(\theta_i=1)=p_n,\qquad\mathbb{P}(\theta_i=\ell_n)=1-p_n. p n = n 2 2 , ℓ n = n 2 − 2 n − 1 , P ( θ i = 1 ) = p n , P ( θ i = ℓ n ) = 1 − p n .
Conditional on θ i \theta_i θ i , every reward observation equals θ i \theta_i θ i . These are bounded exchangeable observations, and one play reveals the mean completely. The prior mean is m n = p n + ( 1 − p n ) ℓ n = ( n + 1 ) / n 2 m_n=p_n+(1-p_n)\ell_n=(n+1)/n^2 m n = p n + ( 1 − p n ) ℓ n = ( n + 1 ) / n 2 . At ν = 1 / n \nu=1/n ν = 1/ n we have 0 < ℓ n < ν < m n < 1 0<\ell_n<\nu<m_n<1 0 < ℓ n < ν < m n < 1 . After a revealing play, the unique optimal local decision is to select a high arm and quit a low arm; further plays only incur cost. Thus the root alternatives have surpluses
quit: 0 , select: m n − ν = 1 n 2 , play: p n ( 1 − ν ) − ν n = 1 − 2 / n n 2 . \text{quit: }0,\qquad\text{select: }m_n-\nu=\frac{1}{n^2},\qquad\text{play: }p_n(1-\nu)-\frac{\nu}{n}=\frac{1-2/n}{n^2}. quit: 0 , select: m n − ν = n 2 1 , play: p n ( 1 − ν ) − n ν = n 2 1 − 2/ n .
Immediate selection is strictly optimal, with advantage 2 / n 3 2/n^3 2/ n 3 over playing. Since every arm has surplus 1 / n 2 1/n^2 1/ n 2 , the balance ∑ i G i ( ρ i ; ν , ν / T ) = ν \sum_i G_i(\rho_i;\nu,\nu/T)=\nu ∑ i G i ( ρ i ; ν , ν / T ) = ν holds exactly. Its solution is unique because total surplus is nonincreasing in ν \nu ν and the right-hand side is strictly increasing. Every ordering therefore stops at its first root and obtains A L G = m n \mathrm{ALG}=m_n ALG = m n . Choosing the largest available posterior at this stopping time has the same value.
Finite price search. The binary search in Guha and Munagala [32 ] uses the lower balancing endpoint, hence a price 0 < ν ^ ≤ 1 / n 0<\hat{\nu}\le1/n 0 < ν ^ ≤ 1/ n . Immediate selection is strictly optimal throughout this interval. For ν ^ ≤ ℓ n \hat{\nu}\le\ell_n ν ^ ≤ ℓ n , a revealing play selects either outcome but pays the extra cost ν ^ / n \hat{\nu}/n ν ^ / n . For ℓ n < ν ^ ≤ 1 / n \ell_n<\hat{\nu}\le1/n ℓ n < ν ^ ≤ 1/ n , the advantage of immediate selection over playing is
m n − p n − ν ^ ( 1 − p n − 1 / n ) ≥ 2 / n 3 > 0. m_n-p_n-\hat{\nu}(1-p_n-1/n)\ge2/n^3>0. m n − p n − ν ^ ( 1 − p n − 1/ n ) ≥ 2/ n 3 > 0.
The root selection surplus is positive in both cases. Consequently the loss does not depend on exact price computation or on local tie-breaking.
Optimum and relaxation values. Observing all n n n arms is feasible and reveals all latent means, so it attains the perfect-information upper bound:
O P T = 1 − ( 1 − ℓ n ) ( 1 − p n ) n = 3 n + O ( n − 2 ) . \mathrm{OPT}=1-(1-\ell_n)(1-p_n)^n=\frac{3}{n}+O(n^{-2}). OPT = 1 − ( 1 − ℓ n ) ( 1 − p n ) n = n 3 + O ( n − 2 ) .
The expansion follows from ℓ n = 1 / n + O ( n − 2 ) \ell_n=1/n+O(n^{-2}) ℓ n = 1/ n + O ( n − 2 ) and 1 − ( 1 − 2 / n 2 ) n = 2 / n + O ( n − 2 ) 1-(1-2/n^2)^n=2/n+O(n^{-2}) 1 − ( 1 − 2/ n 2 ) n = 2/ n + O ( n − 2 ) . At the balanced price, (8) gives
O P T ≤ L P ≤ L P B u d ≤ 3 ν = 3 / n . \mathrm{OPT}\leq\mathrm{LP}\leq\mathrm{LPBud}\leq3\nu=3/n. OPT ≤ LP ≤ LPBud ≤ 3 ν = 3/ n .
This proves L P / O P T → 1 \mathrm{LP}/\mathrm{OPT}\to1 LP / OPT → 1 , L P B u d / O P T → 1 \mathrm{LPBud}/\mathrm{OPT}\to1 LPBud / OPT → 1 , and A L G / O P T → 1 / 3 \mathrm{ALG}/\mathrm{OPT}\to1/3 ALG / OPT → 1/3 .
The balancing equation does not minimize the dual objective. Indeed, for this instance the immediate-selection and revealing-play surplus branches meet at
ν min = n − 1 ( n − 2 ) ( n + 1 ) > 1 n , L P B u d = 3 n + 1 n ( n + 1 ) . \nu_{\min}=\frac{n-1}{(n-2)(n+1)}>\frac{1}{n},\qquad\mathrm{LPBud}=\frac{3n+1}{n(n+1)}. ν m i n = ( n − 2 ) ( n + 1 ) n − 1 > n 1 , LPBud = n ( n + 1 ) 3 n + 1 .
Both branches are positive there. The convex dual objective has slope 2 − n < 0 2-n<0 2 − n < 0 immediately below this point and 1 − 2 / n > 0 1-2/n>0 1 − 2/ n > 0 immediately above it, proving the displayed optimum. At the balanced price, however, its unique local maximizers all select immediately: their aggregate combined load is n n n . Thus even an asymptotically accurate dual bound can be paired with local policies whose execution loses a factor of three. No ordering of these policies recovers the missing exploration; the execution of Section 2.1 instead starts from local policies that satisfy the load constraint.
Distinct prior means. Symmetry is not essential. Keep p n p_n p n fixed and replace each low mean by
ℓ i = m n + η i − p n 1 − p n , η i = 2 i − n − 1 4 n 4 , i = 1 , … , n . \ell_i=\frac{m_n+\eta_i-p_n}{1-p_n},\qquad\eta_i=\frac{2i-n-1}{4n^4},\qquad i=1,\ldots,n. ℓ i = 1 − p n m n + η i − p n , η i = 4 n 4 2 i − n − 1 , i = 1 , … , n .
The prior means m n + η i m_n+\eta_i m n + η i are distinct, ∑ i η i = 0 \sum_i\eta_i=0 ∑ i η i = 0 , and ∣ η i ∣ < 1 / ( 4 n 3 ) |\eta_i|<1/(4n^3) ∣ η i ∣ < 1/ ( 4 n 3 ) . All low means remain in ( 0 , 1 / n ) (0,1/n) ( 0 , 1/ n ) . At ν = 1 / n \nu=1/n ν = 1/ n the root selection surplus is 1 / n 2 + η i 1/n^2+\eta_i 1/ n 2 + η i , whereas the revealing-play surplus is unchanged. The selection advantage is still positive, and the total surplus remains 1 / n 1/n 1/ n . The same finite-search argument applies. Every ordering obtains m n + η i = 1 / n + O ( n − 2 ) m_n+\eta_i=1/n+O(n^{-2}) m n + η i = 1/ n + O ( n − 2 ) for its first arm, while observing all arms obtains 1 − ( 1 − max i ℓ i ) ( 1 − p n ) n = 3 / n + O ( n − 2 ) 1-(1-\max_i\ell_i)(1-p_n)^n=3/n+O(n^{-2}) 1 − ( 1 − max i ℓ i ) ( 1 − p n ) n = 3/ n + O ( n − 2 ) . The dual sandwich and all limiting ratios therefore persist, including for the now strict density ordering. Selecting the largest current posterior also leaves the limiting ratio unchanged.
Model boundaries and Ma’s rounding
The supermartingale condition (1) lets selection of an interrupted arm cover its expected remaining selected payoff; exchangeability is not needed.
Bounding the selected payoff of an interrupted policy
Let Γ i ( u ) = G i ( u ; 0 , 0 ) \Gamma_i(u)=G_i(u;0,0) Γ i ( u ) = G i ( u ; 0 , 0 ) be the value of the best single-arm policy from u u u when plays are free. For a local policy P P P with terminal state u τ u_\tau u τ , write Y P = r u τ 1 { P selects } Y_P=r_{u_\tau}\mathbf{1}\{P\text{ selects}\} Y P = r u τ 1 { P selects } . The following equivalence identifies the exact property used to bound an interrupted policy’s remaining payoff in Theorem 2.1.
Proposition 2.5. For nonnegative payoffs, the following are equivalent: (i) (1) holds at every state; (ii) r u ≥ E [ Y P ∣ u ] r_u\geq\mathbb{E}[Y_P\mid u] r u ≥ E [ Y P ∣ u ] for every state u u u and every single-arm policy P P P started at u u u ; (iii) Γ i ( u ) = r u \Gamma_i(u)=r_u Γ i ( u ) = r u at every state.
Proof. (i)⇒ \Rightarrow ⇒ (ii) is optional stopping for the nonnegative supermartingale sequence r u t r_{u_t} r u t . (ii)⇒ \Rightarrow ⇒ (iii) holds because selecting at u u u attains r u r_u r u , and (iii)⇒ \Rightarrow ⇒ (i) because (6) with η = λ = 0 \eta=\lambda=0 η = λ = 0 gives r u = Γ i ( u ) ≥ ∑ v p u v Γ i ( v ) = ∑ v p u v r v r_u=\Gamma_i(u)\geq\sum_v p_{uv}\Gamma_i(v)=\sum_v p_{uv}r_v r u = Γ i ( u ) ≥ ∑ v p uv Γ i ( v ) = ∑ v p uv r v .
The broader Markov models of Gupta et al. [34 ] and Ma (2018) allow late payoffs. For example, take n = ⌊ T / 2 ⌋ n=\lfloor T/2\rfloor n = ⌊ T /2 ⌋ arms whose first play enters, with probability 1 / T 1/T 1/ T , a chain requiring T − 1 T-1 T − 1 more plays to earn one. All earlier payoffs are zero. Then L P B u d = L P = n / T \mathrm{LPBud}=\mathrm{LP}=n/T LPBud = LP = n / T but O P T = 1 / T \mathrm{OPT}=1/T OPT = 1/ T . The time-indexed relaxations of Gupta et al. [34 ] and Ma (2018) are designed for such late payoffs.
Ma's time-indexed rounding
Proposition 2.6. There are three-arm unit-play Markov instances and optimal solutions of Ma’s time-indexed LP for which his C = 3 C = 3 C = 3 rounding, under every priority tie-breaking rule, has
ALG M a / OPT → 4 / 27 , LP M a / OPT → 1. \operatorname{ALG}_{\mathrm{Ma}}/\operatorname{OPT} \to4/27,\qquad\operatorname{LP}_{\mathrm{Ma}}/\operatorname{OPT} \to1. ALG Ma / OPT → 4/27 , LP Ma / OPT → 1.
Proof. We use the unit-play rounding of Ma (2018, Sections 4.1–4.2). It independently activates each arm with its LP root-play mass divided by C = 3 C = 3 C = 3 , and attaches an LP time label to every subsequent play. It starts an arm with smallest label and continues until the next label t t t satisfies t ≥ 2 depth ( u ) t \ge2\operatorname{depth}(u) t ≥ 2 depth ( u ) , then chooses again. We give an instance and an optimal LP solution for which the loss holds for every priority tie-breaking rule and every valid local flow decomposition.
Instance and feasible optimum. For an integer m ≥ 3 m \ge3 m ≥ 3 , set
T = 2 m , p = 1 / m , δ = m − 3 , q = m − 1 m + 1 . T = 2m,\qquad p = 1/m,\qquad\delta= m^{-3},\qquad q = \frac{m-1}{m+1}. T = 2 m , p = 1/ m , δ = m − 3 , q = m + 1 m − 1 .
The valuable arm’s first play goes to a dead state with probability 1 − p 1-p 1 − p , and otherwise begins a deterministic chain of m m m further plays whose last play earns one. Each of two blocking arms is a deterministic chain of m + 1 m+1 m + 1 plays earning δ \delta δ only on its last play. Arms terminate after earning their reward. Thus any positive payoff requires m + 1 m+1 m + 1 plays on its arm, and T < 2 ( m + 1 ) T < 2(m+1) T < 2 ( m + 1 ) permits at most one such payoff. Equivalently, give an unfinished arm selectable payoff zero and a completed arm its earned payoff; maximizing the terminal choice has the same value.
Testing the valuable arm first, completing it on success, and otherwise completing one blocker attains
OPT = p + ( 1 − p ) δ . (12) \operatorname{OPT} = p + (1-p)\delta. \tag*{(12)} OPT = p + ( 1 − p ) δ . (12)
This is optimal: on the valuable arm’s good outcome no policy can earn more than one, and on its bad outcome no policy can earn more than δ \delta δ .
A feasible time-indexed solution. Play the valuable root at time label one with mass one. On success, assign its m m m continuation plays the labels m + 1 , m + 2 , … , 2 m m+1,m+2,\ldots,2m m + 1 , m + 2 , … , 2 m . Its expected work is 1 + m p = 2 1+mp=2 1 + m p = 2 and its objective contribution is p p p .
Each blocker has root-play mass q q q and completes whenever played. Conditional on activation, choose m + 1 m+1 m + 1 distinct time labels from { 2 , … , 2 m } \{2,\ldots,2m\} { 2 , … , 2 m } , in increasing order. The marginal probability of using each of the first m − 1 m-1 m − 1 labels is 1 / ( 2 q ) 1/(2q) 1/ ( 2 q ) and of using each of the last m m m labels is ( 1 − p ) / ( 2 q ) (1-p)/(2q) ( 1 − p ) / ( 2 q ) . Such a distribution exists explicitly: choose an integer J J J supported on the floor and ceiling of ( m + 1 ) / 2 (m+1)/2 ( m + 1 ) /2 with that mean; choose J J J labels uniformly from the first group and m + 1 − J m+1-J m + 1 − J uniformly from the second group. For m ≥ 3 m \ge3 m ≥ 3 , 1 ≤ J ≤ m − 1 1 \le J \le m-1 1 ≤ J ≤ m − 1 and 1 ≤ m + 1 − J ≤ m 1 \le m+1-J \le m 1 ≤ m + 1 − J ≤ m . The required marginals follow from
q E J m − 1 = 1 2 , q m + 1 − E J m = 1 − p 2 . q\frac{\mathbb{E}J}{m-1}=\frac{1}{2},\qquad q\frac{m+1-\mathbb{E}J}{m}=\frac{1-p}{2}. q m − 1 E J = 2 1 , q m m + 1 − E J = 2 1 − p .
These increasing label sequences induce feasible single-arm flows in Ma’s time-indexed relaxation. At label one the valuable root uses all capacity. At each of the next m − 1 m-1 m − 1 labels the blockers use 1 / 2 + 1 / 2 = 1 1/2+1/2=1 1/2 + 1/2 = 1 ; at each of the final m m m labels they use ( 1 − p ) / 2 + ( 1 − p ) / 2 (1-p)/2+(1-p)/2 ( 1 − p ) /2 + ( 1 − p ) /2 , and the valuable continuation use p p p . Every time constraint is therefore met with equality. The value is
LP M a = p + 2 q δ . (13) \operatorname{LP}_{\mathrm{Ma}}=p+2q\delta. \tag*{(13)} LP Ma = p + 2 q δ . (13)
To prove optimality, let a a a be the valuable arm’s total root-play mass, v v v its completion mass, and s s s the sum of blocker completion masses in any feasible LP solution. Flow conservation and total time capacity imply
v ≤ p a ≤ p , a + m v + ( m + 1 ) s ≤ T . v \leq pa \leq p,\qquad a+mv+(m+1)s \leq T. v ≤ p a ≤ p , a + m v + ( m + 1 ) s ≤ T .
Its reward is consequently at most
v + δ s ≤ δ T m + 1 + v ( 1 − δ m m + 1 ) − δ a m + 1 ≤ δ T m + 1 + v ( 1 − δ ( m + 1 / p ) m + 1 ) ≤ p + δ ( T − 1 − m p ) m + 1 = p + 2 q δ . v+\delta s \leq\frac{\delta T}{m+1}+v\left(1-\frac{\delta m}{m+1}\right)-\frac{\delta a}{m+1}
\leq\frac{\delta T}{m+1}+v\left(1-\frac{\delta(m+1/p)}{m+1}\right)
\leq p+\frac{\delta(T-1-mp)}{m+1}=p+2q\delta. v + δ s ≤ m + 1 δ T + v ( 1 − m + 1 δ m ) − m + 1 δ a ≤ m + 1 δ T + v ( 1 − m + 1 δ ( m + 1/ p ) ) ≤ p + m + 1 δ ( T − 1 − m p ) = p + 2 q δ .
The coefficient of v v v is positive, so the last step uses v ≤ p v \leq p v ≤ p . Together with the feasible solution, this proves (13).
The rounding loss, independent of ties. The valuable arm is activated with probability 1 / 3 1/3 1/3 , and each blocker independently with probability q / 3 q/3 q /3 . All the flow mass of an activated blocker reaches its last play: each depth has the same total LP flow q q q , so any valid flow decomposition abandons it with probability zero. Its labels increase strictly and are at most T T T . Consequently, its first m m m plays have labels strictly below T T T , under every such decomposition.
Conditional on activation and a good first outcome, the valuable arm has its next play at depth j j j and label m + j m+j m + j , for j = 1 , … , m j=1,\ldots,m j = 1 , … , m . Since m + j ≥ 2 j m+j \ge2j m + j ≥ 2 j , the execution returns to the priority comparison after each play. In particular, its final play is compared at depth m m m with label T = 2 m T=2m T = 2 m . Before this final play can be executed, every active blocker must have made its first m m m plays: otherwise its next label is strictly below T T T and precedes the valuable arm’s final play. Even one active blocker would force at least
m + ( m + 1 ) = 2 m + 1 > T m+(m+1)=2m+1>T m + ( m + 1 ) = 2 m + 1 > T
plays before the valuable reward is earned. Therefore the valuable arm completes if and only if it is activated, its first outcome is good, and neither blocker is activated. Its contribution is exactly p ( 1 − q / 3 ) 2 / 3 p(1-q/3)^2/3 p ( 1 − q /3 ) 2 /3 . There is at most one blocker payoff, giving
ALG M a = p 3 ( 1 − q 3 ) 2 + O ( δ ) . \operatorname{ALG}_{\mathrm{Ma}}=\frac{p}{3}\left(1-\frac{q}{3}\right)^2+O(\delta). ALG Ma = 3 p ( 1 − 3 q ) 2 + O ( δ ) .
Since q → 1 q\to1 q → 1 and δ / p → 0 \delta/p\to0 δ / p → 0 , equations (12) –(13) prove both limits in Proposition 2.6 . More generally, activating each arm with its root-play mass times a fixed factor x ∈ [ 0 , 1 ] x\in[0,1] x ∈ [ 0 , 1 ] gives limiting ratio x ( 1 − x ) 2 x(1-x)^2 x ( 1 − x ) 2 , whose maximum is 4 / 27 4/27 4/27 at x = 1 / 3 x=1/3 x = 1/3 .
Short policies avoid interruption and therefore also permit late payoffs (Theorem 3.3 ).
Short policies
The construction follows the stochastic-packing execution framework of Guha and Munagala [29 ] , also developed in Guha and Munagala [30 ] . Bounded policy durations let us treat the selection constraint and the play budget separately.
The stronger, standalone selection constraint in LP can be analyzed once the deadline is unlikely to interfere with the local policies. Throughout this section, fix independent local policies with nonnegative selected rewards satisfying ∑ i q i ≤ 1 \sum_i q_i\le1 ∑ i q i ≤ 1 and ∑ i w i ≤ T \sum_i w_i\le T ∑ i w i ≤ T , and write R = ∑ i R i \mathcal{R}=\sum_i R_i R = ∑ i R i . Let f ⋆ = 1 − e − 1 f^\star=1-e^{-1} f ⋆ = 1 − e − 1 . Work means the number of plays: τ i \tau_i τ i is the realized play count and w i = E [ τ i ] w_i=\mathbb{E}[\tau_i] w i = E [ τ i ] its expectation. Lemma 3.1 first ignores the deadline and bounds the loss from stopping at the first selection. Theorem 3.3 then restores the hard budget for policies of duration at most k k k , using random thinning to create slack and reserving k k k plays before starting a policy. Figure 1 separates these two arguments.
Figure 1. A bounded-duration refinement of the stochastic-packing execution framework of Guha and Munagala [29 ] ; see also Guha and Munagala [30 ] . Thinning scales rewards and selection probabilities equally, preserving the order R i / q i R_i/q_i R i / q i . Lemma 3.1 bounds the loss from stopping at the first selection, ignoring the deadline. Theorem 3.3 adds capacity slack and a k k k -play reserve: every started policy finishes, while the probability of exclusion by the budget is at most δ \delta δ .
Lemma 3.1 (Selection-only order). Order by nonincreasing R i / q i R_i/q_i R i / q i , omitting q i = 0 q_i=0 q i = 0 . With s i = ∏ j < i ( 1 − q j ) s_i=\prod_{j<i}(1-q_j) s i = ∏ j < i ( 1 − q j ) and Q = ∑ i q i Q=\sum_iq_i Q = ∑ i q i , we have ∑ i R i s i ≥ ϕ ( Q ) R ≥ f ⋆ R \sum_iR_is_i\ge\phi(Q)R\ge f^\star R ∑ i R i s i ≥ ϕ ( Q ) R ≥ f ⋆ R .
Proof. Let P k = 1 − ∏ i ≤ k ( 1 − q i ) P_k=1-\prod_{i\le k}(1-q_i) P k = 1 − ∏ i ≤ k ( 1 − q i ) and Q k = ∑ i ≤ k q i Q_k=\sum_{i\le k}q_i Q k = ∑ i ≤ k q i . Then P k − P k − 1 = q k s k P_k-P_{k-1}=q_ks_k P k − P k − 1 = q k s k and P k ≥ 1 − e − Q k ≥ ϕ ( Q ) Q k P_k\ge1-e^{-Q_k}\ge\phi(Q)Q_k P k ≥ 1 − e − Q k ≥ ϕ ( Q ) Q k . Summation by parts with the nonincreasing densities R i / q i R_i/q_i R i / q i proves the result, exactly as in (11).
Corollary 3.2 (One-play revelation). If one play resolves each arm’s selectable payoff and n ≤ T n\le T n ≤ T , selection-only ordering obtains at least f ⋆ f^\star f ⋆ LP. The gap 1 / f ⋆ 1/f^\star 1/ f ⋆ against LP is tight.
Proof. An optimal local policy can be reduced to at most one play, because further observations do not change the selectable value; its remaining selection decision can be replaced by a coin. Every policy can finish within the global budget if necessary, so its admission probability is exactly s i s_i s i . Apply Lemma 3.1.
For tightness, recall the needle instance of Guha and Munagala [30 ] : n n n independent arms with P ( θ i = 1 ) = 1 / n \mathbb{P}(\theta_i=1)=1/n P ( θ i = 1 ) = 1/ n . With T = n T=n T = n , L P = 1 \mathrm{LP}=1 LP = 1 and O P T = 1 − ( 1 − 1 / n ) n → f ⋆ \mathrm{OPT}=1-(1-1/n)^n\to f^\star OPT = 1 − ( 1 − 1/ n ) n → f ⋆ . With T = n 2 T=n^2 T = n 2 the same instance has u = log n / n 2 → 0 u=\log n/n^2\to0 u = log n / n 2 → 0 , so the gap persists in the non-vanishing regime (Corollary 4.5).
:::
When n ≤ T n \le T n ≤ T , inspecting every arm is optimal, so the content of Corollary 3.2 is the integrality gap. When n > T n > T n > T , one-play revelation is closely related to the adaptive ProbeMax problem, which keeps the best of a bounded number of probed values; approximation schemes against the optimum are known for ProbeMax ([23 , 56 ] ). Against LP, Theorem 3.3 with k = 1 k = 1 k = 1 gives ( f ⋆ − O ( log T / T ) ) L P (f^\star-O(\sqrt{\log T/T}))\mathrm{LP} ( f ⋆ − O ( log T / T )) LP ; see the remark after it.
Theorem 3.3 (Short policies). Suppose τ i ≤ k \tau_i \le k τ i ≤ k almost surely, where 1 ≤ k ≤ T 1 \le k \le T 1 ≤ k ≤ T , and let 0 < δ < f ⋆ 0 < \delta< f^\star 0 < δ < f ⋆ . Define
γ = k + 2 k T log ( 1 / δ ) + ( 2 k / 3 ) log ( 1 / δ ) T . (14) \gamma= \frac{k+\sqrt{2kT\log(1/\delta)}+(2k/3)\log(1/\delta)}{T}. \tag*{(14)} γ = T k + 2 k T log ( 1/ δ ) + ( 2 k /3 ) log ( 1/ δ ) . (14) If γ < 1 \gamma< 1 γ < 1 , there is a feasible contiguous execution with
A L G ≥ ( f ⋆ − δ ) ( 1 − γ ) R . (15) \mathrm{ALG} \ge(f^\star-\delta)(1-\gamma)\mathcal{R}. \tag*{(15)} ALG ≥ ( f ⋆ − δ ) ( 1 − γ ) R . (15) This theorem does not require (1).
Proof. Omit policies with q i = 0 q_i = 0 q i = 0 , whose selected reward is zero, and fix the order by nonincreasing R i / q i R_i/q_i R i / q i . Independently replace each policy by the null policy with probability γ \gamma γ . If B i B_i B i is its retention indicator, then the modified local variables are
( τ ˉ i , I ˉ i , Y ˉ i ) = B i ( τ i , I i , Y i ) , P ( B i = 1 ) = 1 − γ . (16) (\bar{\tau}_i,\bar{I}_i,\bar{Y}_i)=B_i(\tau_i,I_i,Y_i),\qquad\mathbb{P}(B_i=1)=1-\gamma. \tag*{(16)} ( τ ˉ i , I ˉ i , Y ˉ i ) = B i ( τ i , I i , Y i ) , P ( B i = 1 ) = 1 − γ . (16)
The B i B_i B i are independent of all local executions and of each other. Write R ˉ i = E Y ˉ i \bar{R}_i=\mathbb{E}\bar{Y}_i R ˉ i = E Y ˉ i and q ˉ i = E I ˉ i \bar{q}_i=\mathbb{E}\bar{I}_i q ˉ i = E I ˉ i . Expected total play count is now at most ( 1 − γ ) T (1-\gamma)T ( 1 − γ ) T , and rewards and selection probabilities are scaled by 1 − γ 1-\gamma 1 − γ , preserving the fixed order. Run each admitted policy to completion and stop at its selection. Start a new policy only when the number of plays already used is at most T − k T-k T − k . Thus every admitted policy finishes within T T T plays. If no policy selects, choose an arm maximizing its currently selectable payoff r u i r_{ui} r u i , which is nonnegative.
Let A i A_i A i be the event that policy i i i starts and α i = P ( A i ) \alpha_i=\mathbb{P}(A_i) α i = P ( A i ) . In terms of the complete local variables, A i A_i A i occurs exactly when every earlier I ˉ j \bar{I}_j I ˉ j is zero and ∑ j < i τ ˉ j ≤ T − k \sum_{j<i}\bar{\tau}_j\le T-k ∑ j < i τ ˉ j ≤ T − k . Therefore
α i ≥ ∏ j < i ( 1 − q ˉ j ) − P ( ∑ j < i τ ˉ j > T − k ) . \alpha_i \ge\prod_{j<i}(1-\bar{q}_j)-\mathbb{P}\left(\sum_{j<i}\bar{\tau}_j>T-k\right). α i ≥ j < i ∏ ( 1 − q ˉ j ) − P ( j < i ∑ τ ˉ j > T − k ) .
Since 0 ≤ τ ˉ j ≤ k 0\le\bar{\tau}_j\le k 0 ≤ τ ˉ j ≤ k , the variance of the sum is at most k ∑ j E τ ˉ j ≤ k T k\sum_j\mathbb{E}\bar{\tau}_j\le kT k ∑ j E τ ˉ j ≤ k T . Put h = log ( 1 / δ ) h=\log(1/\delta) h = log ( 1/ δ ) and a = 2 k T h + 2 k h / 3 a=\sqrt{2kTh}+2kh/3 a = 2 k T h + 2 k h /3 . The sum has mean at most ( 1 − γ ) T (1-\gamma)T ( 1 − γ ) T , and (14) gives γ T − k = a \gamma T-k=a γ T − k = a , so exceeding T − k T-k T − k requires a deviation of more than a a a above the mean. Bernstein’s inequality gives
P ( ∑ j < i τ ˉ j > T − k ) ≤ exp ( − a 2 2 k T + 2 k a / 3 ) ≤ δ . \mathbb{P}\left(\sum_{j<i}\bar{\tau}_j>T-k\right)\leq\exp\left(-\frac{a^2}{2kT+2ka/3}\right)\leq\delta. P ( j < i ∑ τ ˉ j > T − k ) ≤ exp ( − 2 k T + 2 k a /3 a 2 ) ≤ δ .
The event A i A_i A i depends only on earlier policies, so it is independent of Y ˉ i \bar{Y}_i Y ˉ i . Every admitted policy finishes, and at most one selects. The terminal rule therefore obtains expected reward at least ∑ i E [ 1 A i Y ˉ i ] = ∑ i α i R ˉ i \sum_i\mathbb{E}[1_{A_i}\bar{Y}_i]=\sum_i\alpha_i\bar{R}_i ∑ i E [ 1 A i Y ˉ i ] = ∑ i α i R ˉ i . Apply Lemma 3.1 and ∑ i R ˉ i = ( 1 − γ ) R \sum_i\bar{R}_i=(1-\gamma)R ∑ i R ˉ i = ( 1 − γ ) R .
Since γ ≥ 2 k log ( 1 / δ ) / T \gamma\geq\sqrt{2k\log(1/\delta)/T} γ ≥ 2 k log ( 1/ δ ) / T , the scheduling loss γ \gamma γ vanishes if and only if k log ( 1 / δ ) = o ( T ) k\log(1/\delta)=o(T) k log ( 1/ δ ) = o ( T ) . For k = 1 k=1 k = 1 and δ = 1 / T \delta=1/T δ = 1/ T , this yields ( f ⋆ − O ( log T / T ) ) L P (f^\star-O(\sqrt{\log T/T}))\mathrm{LP} ( f ⋆ − O ( log T / T )) LP for one-play revelations, regardless of whether n ≤ T n\leq T n ≤ T .
Several plays or selections
Several plays per step model parallel evaluations on M M M machines. Choosing up to L L L attributes for a classifier at test time [39 ] (assuming independent features for the present analysis), or retaining up to L L L independent factors in a response-surface model, motivates allowing multiple selections. At most M M M distinct arms may be played per step and at most L L L arms selected at the end, with the sum of their selectable payoffs as the objective. If exactly L L L selections are required, additional arms can be selected without reducing the value because payoffs are nonnegative.
Interrupted policies. This paragraph concerns the execution of Section 2.1, which may interrupt a policy at the deadline. At a stopping history, let V j V_j V j be the conditional expected remaining selected payoff of an unfinished policy j j j and r j r_j r j its current payoff. Under (1), V j ≤ r j V_j\leq r_j V j ≤ r j at every observed history. With U ≤ M U\leq M U ≤ M unfinished policies, selecting all of them covers ∑ j = 1 U V j \sum_{j=1}^{U}V_j ∑ j = 1 U V j . Selecting only L < U L<U L < U of them guarantees merely
∑ largest L r j ≥ ∑ largest L V j ≥ L U ∑ j = 1 U V j , \sum_{\text{largest }L}r_j\geq\sum_{\text{largest }L}V_j\geq\frac{L}{U}\sum_{j=1}^{U}V_j, largest L ∑ r j ≥ largest L ∑ V j ≥ U L j = 1 ∑ U V j ,
and the factor L / U L/U L / U is attained when all V j V_j V j and r j r_j r j equal a common value. Completed selections can also use up selection capacity. Reducing the analysis to L = 1 L=1 L = 1 while several policies are unfinished therefore loses exactly the property behind (10) : at most one policy is unfinished or has selected when that execution stops.
Short (and deferred) policies. Short policies avoid interruption, so selection can be deferred to the end. Let L P M , L \mathrm{LP}_{M,L} LP M , L be (2) with ∑ i q i ≤ L \sum_iq_i\leq L ∑ i q i ≤ L and ∑ i w i ≤ M T \sum_iw_i\leq MT ∑ i w i ≤ M T . Each arm is played at most once per step, so marginalizing a feasible global policy again gives feasible local flows, and O P T ≤ L P M , L \mathrm{OPT}\leq\mathrm{LP}_{M,L} OPT ≤ LP M , L . Write P o x \mathrm{Po}_x Po x for a Poisson variable of mean x x x , ψ L ( x ) = E min { L , P o x } \psi_L(x)=\mathbb{E}\min\{L,\mathrm{Po}_x\} ψ L ( x ) = E min { L , Po x } , and c L = ψ L ( L ) / L = 1 − L L / ( L ! e L ) c_L=\psi_L(L)/L=1-L^L/(L!e^L) c L = ψ L ( L ) / L = 1 − L L / ( L ! e L ) , so that c 1 = f ⋆ c_1=f^\star c 1 = f ⋆ .
Proposition 3.4. Let independent local policies with nonnegative selected rewards satisfy τ i ≤ k \tau_i\leq k τ i ≤ k , ∑ i q i ≤ L \sum_iq_i\leq L ∑ i q i ≤ L and ∑ i w i ≤ M T \sum_iw_i\leq MT ∑ i w i ≤ M T , and put R = ∑ i R i R=\sum_iR_i R = ∑ i R i . For 0 < δ < c L 0<\delta<c_L 0 < δ < c L let
γ M = M k + 2 k M T log ( 1 / δ ) + ( 2 k / 3 ) log ( 1 / δ ) M T . \gamma_M=\frac{Mk+\sqrt{2kMT\log(1/\delta)}+(2k/3)\log(1/\delta)}{MT}. γ M = M T M k + 2 k M T log ( 1/ δ ) + ( 2 k /3 ) log ( 1/ δ ) . which is (14) when M = 1 M=1 M = 1 . If γ M < 1 \gamma_M<1 γ M < 1 , there is a feasible execution with A L G ≥ ( c L − δ ) ( 1 − γ M ) R \mathrm{ALG}\geq(c_L-\delta)(1-\gamma_M)R ALG ≥ ( c L − δ ) ( 1 − γ M ) R .
Proof. Fix any order of the policies and replace each independently by the null policy with probability γ M \gamma_M γ M . Define ( τ ˉ i , I ˉ i , Y ˉ i ) (\bar{\tau}_i,\bar{I}_i,\bar{Y}_i) ( τ ˉ i , I ˉ i , Y ˉ i ) as in (16) , now with retention probability 1 − γ M 1-\gamma_M 1 − γ M . At each step, every started and unfinished policy makes one play of its own arm. While fewer than M M M policies are running, start the next listed policy, but only at steps t ≤ T − k + 1 t\leq T-k+1 t ≤ T − k + 1 . A policy that selects or quits without a play frees its slot immediately. Every started policy therefore finishes by step T T T , and at most M M M arms are played per step. Selection is deferred: a completed local selection nominates its arm for the final decision. After step T T T , select the up to L L L nominated arms with the largest payoffs, selecting all nominees if there are fewer than L L L and none if there are no nominees. Admission probability. If policy i i i has not started by an eligible step t ≤ T − k + 1 t \le T-k+1 t ≤ T − k + 1 , then at every step up to t t t , M M M policies listed before i i i were running. Hence i i i starts by step T − k + 1 T-k+1 T − k + 1 whenever ∑ j < i τ ˉ j ≤ M ( T − k ) \sum_{j<i}\bar{\tau}_j \le M(T-k) ∑ j < i τ ˉ j ≤ M ( T − k ) . The event A i A_i A i that i i i starts depends only on the outcomes and decisions of earlier policies. The sum has mean at most ( 1 − γ M ) M T (1-\gamma_M)MT ( 1 − γ M ) M T and variance at most k M T kMT k M T , and γ M M T − M k = 2 k M T h + 2 k h / 3 \gamma_MMT-Mk=\sqrt{2kMTh}+2kh/3 γ M M T − M k = 2 k M T h + 2 k h /3 with h = log ( 1 / δ ) h=\log(1/\delta) h = log ( 1/ δ ) . Bernstein’s inequality, as in the proof of Theorem 3.3 , bounds the probability that the event fails by δ \delta δ .
Poissonization. The variables Y ˉ i \bar{Y}_i Y ˉ i describe the complete local executions, whether or not the schedule starts those policies. They are independent and nonnegative, with ∑ i P ( Y ˉ i > 0 ) ≤ L \sum_i\mathbb{P}(\bar{Y}_i>0)\le L ∑ i P ( Y ˉ i > 0 ) ≤ L . Pad the list with zeros when necessary. The sum of its L L L largest values is ∫ 0 ∞ min { L , C v } d v \int_0^\infty\min\{L,C_v\}\,dv ∫ 0 ∞ min { L , C v } d v , where C v = # { i : Y ˉ i > v } C_v=\#\{i:\bar{Y}_i>v\} C v = # { i : Y ˉ i > v } is a sum of independent indicators with mean μ v ≤ L \mu_v\le L μ v ≤ L .
Splitting one indicator into two independent indicators with the same total mean can only lower E min { L , C v } \mathbb{E}\min\{L,C_v\} E min { L , C v } : only the event that the other indicators sum to L − 1 L-1 L − 1 is affected, and there the probability of at least one success drops from p + p ′ p+p' p + p ′ to p + p ′ − p p ′ p+p'-pp' p + p ′ − p p ′ .
Splitting repeatedly gives E min { L , C v } ≥ ψ L ( μ v ) \mathbb{E}\min\{L,C_v\}\ge\psi_L(\mu_v) E min { L , C v } ≥ ψ L ( μ v ) ([14 proof of Lemma 3.2] ).
ψ L \psi_L ψ L is concave with ψ L ( 0 ) = 0 \psi_L(0)=0 ψ L ( 0 ) = 0 , since ψ L ′ ( x ) = P ( Pois x ≤ L − 1 ) \psi'_L(x)=\mathbb{P}(\operatorname{Pois}_x\le L-1) ψ L ′ ( x ) = P ( Pois x ≤ L − 1 ) is nonincreasing. Hence ψ L ( μ v ) ≥ c L μ v \psi_L(\mu_v)\ge c_L\mu_v ψ L ( μ v ) ≥ c L μ v for μ v ≤ L \mu_v\le L μ v ≤ L .
Integrating over v v v , the L L L largest values of Y ˉ i \bar{Y}_i Y ˉ i have expected sum at least c L ∑ i E Y ˉ i = c L ( 1 − γ M ) R c_L\sum_i\mathbb{E}\bar{Y}_i=c_L(1-\gamma_M)\mathcal{R} c L ∑ i E Y ˉ i = c L ( 1 − γ M ) R . For L = 1 L=1 L = 1 the first two steps are not needed: P ( C v ≥ 1 ) ≥ 1 − e − μ v \mathbb{P}(C_v\ge1)\ge1-e^{-\mu_v} P ( C v ≥ 1 ) ≥ 1 − e − μ v directly, as in Lemma 3.1.
Unstarted policies. The schedule obtains the sum of the L L L largest values of 1 A i Y ˉ i \mathbf{1}_{A_i}\bar{Y}_i 1 A i Y ˉ i , padded with zeros. Removing the values for unstarted policies lowers this sum by at most ∑ i ( 1 − 1 A i ) Y ˉ i \sum_i(1-\mathbf{1}_{A_i})\bar{Y}_i ∑ i ( 1 − 1 A i ) Y ˉ i . Since A i A_i A i is independent of Y ˉ i \bar{Y}_i Y ˉ i and P ( A i c ) ≤ δ \mathbb{P}(A_i^c)\le\delta P ( A i c ) ≤ δ , the expected loss is at most
∑ i P ( A i c ) E Y ˉ i ≤ δ ∑ i E Y ˉ i = δ ( 1 − γ M ) R . \sum_i\mathbb{P}(A_i^c)\mathbb{E}\bar{Y}_i\le\delta\sum_i\mathbb{E}\bar{Y}_i=\delta(1-\gamma_M)\mathcal{R}. i ∑ P ( A i c ) E Y ˉ i ≤ δ i ∑ E Y ˉ i = δ ( 1 − γ M ) R .
Combining the two bounds proves the proposition.
For M = L = 1 M=L=1 M = L = 1 this recovers Theorem 3.3 with a different execution: no density order, but no stop at the first selection either. § 4.3 gives the corresponding truncation for the Bayesian model.
Selection-preserving truncation
We return to M = L = 1 M=L=1 M = L = 1 : one play per step and one terminal selection. For Bayesian arms with exchangeable observations in [ 0 , 1 ] [0,1] [ 0 , 1 ] , this section constructs the short policies that § 3 can schedule. We retain each experiment’s prefix and replace its continuation by a coin matching its eventual selection probability. This preserves the LP’s selection constraint exactly and reduces its play count. Concentration bounds the selected payoff lost by the replacement; Theorem 3.3 then gives the feasible execution. Figure 2 shows the local transformation.
Figure 2. Selection-preserving truncation at an active cutoff state u u u . The coin uses the conditional selection probability χ k \chi_k χ k from (17); all earlier decisions remain the same. Selection probability is preserved exactly and play count does not increase, while the following lemmas control selected-payoff loss.
Replace continuation by a selection coin
For the analysis of one arm, define X 1 , … , X T X_1,\ldots,X_T X 1 , … , X T to be iid observations conditional on its latent distribution, even if the policy does not take all of them. Let F t \mathcal{F}_t F t contain the first t t t observations and the policy’s local randomization through that depth. The actual policy sees X t X_t X t only if it makes its t t t th play. For a local policy terminating at τ \tau τ , the tower property gives E [ r τ 1 s e l ] = E [ θ 1 s e l ] \mathbb{E}[r_\tau\mathbf{1}_{\mathrm{sel}}]=\mathbb{E}[\theta\mathbf{1}_{\mathrm{sel}}] E [ r τ 1 sel ] = E [ θ 1 sel ] . Follow a policy P P P until termination or k k k observations. If still active at depth k k k , replace all remaining actions by an independent selection coin of probability
χ k = P ( P eventually selects ∣ F k ) . (17) \chi_k=\mathbb{P}(P\text{ eventually selects}\mid\mathcal{F}_k). \tag*{(17)} χ k = P ( P eventually selects ∣ F k ) . (17)
Select the current arm on a positive coin and otherwise quit; call this policy P [ k ] P^{[k]} P [ k ] . The coin is independent of future observations and future randomization of P P P , conditional on F k \mathcal{F}_k F k .
Let C C C be the event that P P P is still active when the cutoff is reached, let S = C ∩ { P eventually selects } S=C\cap\{P\text{ eventually selects}\} S = C ∩ { P eventually selects } be the part of the selection event that the cutoff affects, and set Z = χ k 1 C = E [ 1 S ∣ F k ] Z=\chi_k1_C=\mathbb{E}[1_S\mid\mathcal{F}_k] Z = χ k 1 C = E [ 1 S ∣ F k ] . Before the cutoff, P P P and P [ k ] P^{[k]} P [ k ] make the same selections.
Let θ ^ k \hat{\theta}_k θ ^ k be the empirical mean of the first k k k observations; it is F k \mathcal{F}_k F k -measurable. Then
I ( P [ k ] ) = I ( P ) , W ( P [ k ] ) ≤ W ( P ) , τ ( P [ k ] ) ≤ k , E [ θ ^ k Z ] = E [ θ ^ k 1 S ] . (18) I(P^{[k]})=I(P),\qquad W(P^{[k]})\leq W(P),\qquad\tau(P^{[k]})\leq k,\qquad\mathbb{E}[\hat{\theta}_kZ]=\mathbb{E}[\hat{\theta}_k1_S]. \tag*{(18)} I ( P [ k ] ) = I ( P ) , W ( P [ k ] ) ≤ W ( P ) , τ ( P [ k ] ) ≤ k , E [ θ ^ k Z ] = E [ θ ^ k 1 S ] . (18)
For k ≥ 1 k\geq1 k ≥ 1 , the event of making a first play is also unchanged. The coin is used only in the analysis; the algorithm solves the depth-k k k LP directly.
Charge reward loss to selection mass
Lemma 4.1. For 0 < ϵ < 1 / 4 0<\epsilon<1/4 0 < ϵ < 1/4 , a 0 > 0 a_0>0 a 0 > 0 , and any fixed latent distribution of mean θ \theta θ ,
P ( ∣ θ ^ k − θ ∣ > ϵ max { θ , a 0 } ) ≤ ζ : = 2 e − k ϵ 2 a 0 / 3 . \mathbb{P}\left(\left|\hat{\theta}_k-\theta\right|>\epsilon\max\{\theta,a_0\}\right)\leq\zeta:=2e^{-k\epsilon^2a_0/3}. P ( θ ^ k − θ > ϵ max { θ , a 0 } ) ≤ ζ := 2 e − k ϵ 2 a 0 /3 .
Proof. Conditional variance of an observation is at most θ \theta θ . Apply the two-sided Bernstein bound at t = ϵ max { θ , a 0 } t=\epsilon\max\{\theta,a_0\} t = ϵ max { θ , a 0 } . If θ ≥ a 0 \theta\geq a_0 θ ≥ a 0 , its exponent k t 2 / ( 2 θ + 2 t / 3 ) kt^2/(2\theta+2t/3) k t 2 / ( 2 θ + 2 t /3 ) is at least k ϵ 2 θ / 3 k\epsilon^2\theta/3 k ϵ 2 θ /3 . If θ < a 0 \theta<a_0 θ < a 0 , it is at least k ϵ 2 a 0 / 3 k\epsilon^2a_0/3 k ϵ 2 a 0 /3 . Both statements use ϵ < 1 / 4 \epsilon<1/4 ϵ < 1/4 , which gives 2 θ + 2 ϵ max { θ , a 0 } / 3 ≤ 3 max { θ , a 0 } 2\theta+2\epsilon\max\{\theta,a_0\}/3\leq3\max\{\theta,a_0\} 2 θ + 2 ϵ max { θ , a 0 } /3 ≤ 3 max { θ , a 0 } .
Lemma 4.2 (Reward preservation). Under the conditions of Lemma 4.1, every local policy P P P and its truncation P [ k ] P^{[k]} P [ k ] satisfy
R ~ ( P [ k ] ) ≥ ( 1 − ϵ ) R ~ ( P ) − 2 ϵ a 0 I ( P ) − 2 ζ 1 + ϵ . (19) \widetilde{R}(P^{[k]})\geq\frac{(1-\epsilon)\widetilde{R}(P)-2\epsilon a_0I(P)-2\zeta}{1+\epsilon}. \tag*{(19)} R ( P [ k ] ) ≥ 1 + ϵ ( 1 − ϵ ) R ( P ) − 2 ϵ a 0 I ( P ) − 2 ζ . (19)
Proof. On the concentration event, ( 1 − ϵ ) θ − ϵ a 0 ≤ θ ^ k ≤ ( 1 + ϵ ) θ + ϵ a 0 (1-\epsilon)\theta-\epsilon a_0\leq\hat{\theta}_k\leq(1+\epsilon)\theta+\epsilon a_0 ( 1 − ϵ ) θ − ϵ a 0 ≤ θ ^ k ≤ ( 1 + ϵ ) θ + ϵ a 0 . All means and weights lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , so these pointwise bounds give the unconditional inequalities
E [ θ ^ k Z ] ≤ ( 1 + ϵ ) E [ θ Z ] + ϵ a 0 P ( S ) + ζ , \mathbb{E}[\hat{\theta}_kZ]\leq(1+\epsilon)\mathbb{E}[\theta Z]+\epsilon a_0\mathbb{P}(S)+\zeta, E [ θ ^ k Z ] ≤ ( 1 + ϵ ) E [ θ Z ] + ϵ a 0 P ( S ) + ζ ,
E [ θ ^ k 1 S ] ≥ ( 1 − ϵ ) E [ θ 1 S ] − ϵ a 0 P ( S ) − ζ . \mathbb{E}[\hat{\theta}_k1_S]\geq(1-\epsilon)\mathbb{E}[\theta1_S]-\epsilon a_0\mathbb{P}(S)-\zeta. E [ θ ^ k 1 S ] ≥ ( 1 − ϵ ) E [ θ 1 S ] − ϵ a 0 P ( S ) − ζ .
Equate the left sides using (18), then use tower property on the latent mean. The policies agree before the cutoff, and P ( S ) ≤ I ( P ) \mathbb{P}(S)\leq I(P) P ( S ) ≤ I ( P ) , giving (19).
Corollary 4.3 (Two LP error bounds). Let L P ( k ) \mathrm{LP}^{(k)} LP ( k ) restrict (2) to depth-k k k policies. If L P > 0 \mathrm{LP}>0 LP > 0 and 0 < ϵ < 1 / 4 0<\epsilon<1/4 0 < ϵ < 1/4 , then
L P ( k ) ≥ ( 1 − 3 ϵ ) L P − 4 n e − k ϵ 2 L P / 6 . (20) \mathrm{LP}^{(k)}\geq(1-3\epsilon)\mathrm{LP}-4ne^{-k\epsilon^2\mathrm{LP}/6}. \tag*{(20)} LP ( k ) ≥ ( 1 − 3 ϵ ) LP − 4 n e − k ϵ 2 LP /6 . (20)
For every z > 0 z>0 z > 0 , including when L P = 0 \mathrm{LP}=0 LP = 0 ,
0 ≤ L P − L P ( k ) ≤ 2 z + 2 n e − 2 k z 2 . (21) 0\le\mathrm{LP}-\mathrm{LP}^{(k)}\le2z+2n e^{-2kz^2}. \tag*{(21)} 0 ≤ LP − LP ( k ) ≤ 2 z + 2 n e − 2 k z 2 . (21)
The two LPs coincide when k ≥ T k\ge T k ≥ T .
Proof. The truncated optimal policies remain feasible by (18) . Sum (19) with a 0 = L P / 2 a_0=\mathrm{LP}/2 a 0 = LP /2 and ∑ i I ( P i ) ≤ 1 \sum_i I(P_i)\le1 ∑ i I ( P i ) ≤ 1 to obtain (20) .
For one local policy use the notation of (18) : S S S is its selection event after reaching the cutoff, Z = E [ 1 S ∣ F k ] Z=\mathbb{E}[1_S\mid\mathcal{F}_k] Z = E [ 1 S ∣ F k ] , and θ ^ k \widehat{\theta}_k θ k is the empirical mean of the first k k k observations. The policies agree before the cutoff. The tower property applied to the latent mean and E [ θ ^ k ( 1 S − Z ) ] = 0 \mathbb{E}[\widehat{\theta}_k(1_S-Z)]=0 E [ θ k ( 1 S − Z )] = 0 give
R ~ ( P ) − R ~ ( P [ k ] ) = E [ ( θ − θ ^ k ) ( 1 S − Z ) ] . \widetilde{R}(P)-\widetilde{R}(P^{[k]})=\mathbb{E}[(\theta-\widehat{\theta}_k)(1_S-Z)]. R ( P ) − R ( P [ k ] ) = E [( θ − θ k ) ( 1 S − Z )] .
Conditional on the latent reward distribution, Hoeffding’s inequality gives P ( ∣ θ − θ ^ k ∣ > z ) ≤ 2 e − 2 k z 2 \mathbb{P}(|\theta-\widehat{\theta}_k|>z)\le2e^{-2kz^2} P ( ∣ θ − θ k ∣ > z ) ≤ 2 e − 2 k z 2 . On its complement, the integrand is at most z ( 1 S + Z ) z(1_S+Z) z ( 1 S + Z ) . On the exceptional event its absolute value is at most one, since θ , θ ^ k , Z ∈ [ 0 , 1 ] \theta,\widehat{\theta}_k,Z\in[0,1] θ , θ k , Z ∈ [ 0 , 1 ] . As E Z = P ( S ) ≤ I ( P ) \mathbb{E}Z=\mathbb{P}(S)\le I(P) E Z = P ( S ) ≤ I ( P ) ,
R ~ ( P [ k ] ) ≥ R ~ ( P ) − 2 z I ( P ) − 2 e − 2 k z 2 . \widetilde{R}(P^{[k]})\ge\widetilde{R}(P)-2zI(P)-2e^{-2kz^2}. R ( P [ k ] ) ≥ R ( P ) − 2 z I ( P ) − 2 e − 2 k z 2 .
Sum over optimal local policies of L P \mathrm{LP} LP . Their truncated versions remain feasible by (18) , and ∑ i I ( P i ) ≤ 1 \sum_i I(P_i)\le1 ∑ i I ( P i ) ≤ 1 , proving (21) . No local policy is shortened when k ≥ T k\ge T k ≥ T . □
The relative bound (20) is used for approximation below, and the additive bound (21) for the certificates of § 5 .
Short and schedulable
Recall f ⋆ = 1 − e − 1 f^\star=1-e^{-1} f ⋆ = 1 − e − 1 . Fix 0 < ϵ < 1 / 4 0<\epsilon<1/4 0 < ϵ < 1/4 , L P > 0 \mathrm{LP}>0 LP > 0 , and set
k = ⌈ 6 log ( 4 n / ( ϵ L P ) ) ϵ 2 L P ⌉ , δ = ϵ f ⋆ . (22) k=\left\lceil\frac{6\log(4n/(\epsilon\mathrm{LP}))}{\epsilon^2\mathrm{LP}}\right\rceil,\qquad\delta=\epsilon f^\star. \tag*{(22)} k = ⌈ ϵ 2 LP 6 log ( 4 n / ( ϵ LP )) ⌉ , δ = ϵ f ⋆ . (22)
Then Corollary 4.3 gives L P ( k ) ≥ ( 1 − 4 ϵ ) L P \mathrm{LP}^{(k)}\ge(1-4\epsilon)\mathrm{LP} LP ( k ) ≥ ( 1 − 4 ϵ ) LP . Solve this truncated LP once. Independently thin its local policies by the slack γ \gamma γ in (14) , then use the contiguous execution of Theorem 3.3 . Every admitted policy finishes within the horizon. Use Section 2.1 when γ ≥ 1 \gamma\ge1 γ ≥ 1 .
Theorem 4.4. Let k k k and δ \delta δ be as in (22) and γ \gamma γ as in (14) . If γ < 1 \gamma<1 γ < 1 , the algorithm above satisfies
A L G ≥ f ⋆ ( 1 − 5 ϵ − γ ) L P . (23) \mathrm{ALG}\ge f^\star(1-5\epsilon-\gamma)\mathrm{LP}. \tag*{(23)} ALG ≥ f ⋆ ( 1 − 5 ϵ − γ ) LP . (23)
Proof. Theorem 3.3 and Corollary 4.3 give A L G ≥ f ⋆ ( 1 − ϵ ) ( 1 − γ ) ( 1 − 4 ϵ ) L P \mathrm{ALG}\ge f^\star(1-\epsilon)(1-\gamma)(1-4\epsilon)\mathrm{LP} ALG ≥ f ⋆ ( 1 − ϵ ) ( 1 − γ ) ( 1 − 4 ϵ ) LP . Expanding the nonnegative factors proves the bound. □
Corollary 4.5. Let n ≥ 2 n\ge2 n ≥ 2 and u = log ( n / L P ) / ( T L P ) u=\log(n/\mathrm{LP})/(T\mathrm{LP}) u = log ( n / LP ) / ( T LP ) . As u → 0 u\to0 u → 0 , choosing ϵ = u 1 / 4 \epsilon=u^{1/4} ϵ = u 1/4 gives
A L G ≥ ( f ⋆ − O ( u 1 / 4 log ( 1 / u ) ) ) L P . \mathrm{ALG}\ge\left(f^\star-O\left(u^{1/4}\log(1/u)\right)\right)\mathrm{LP}. ALG ≥ ( f ⋆ − O ( u 1/4 log ( 1/ u ) ) ) LP . The limiting LP gap 1 / f ⋆ 1/f^\star 1/ f ⋆ is tight within this regime.
Proof. For small u u u , ϵ < 1 / 4 \epsilon<1/4 ϵ < 1/4 . Since L P ≤ 1 \mathrm{LP}\le1 LP ≤ 1 and n ≥ 2 n\ge2 n ≥ 2 , 1 / T ≤ 1 / ( T L P ) ≤ u / log 2 1/T\le1/(T\mathrm{LP})\le u/\log2 1/ T ≤ 1/ ( T LP ) ≤ u / log 2 , so with the ceiling k / T ≤ 6 ( log ( n / L P ) + log ( 4 / ϵ ) ) / ( ϵ 2 T L P ) + 1 / T = O ( u 1 / 2 log ( 1 / u ) ) k/T\le6(\log(n/\mathrm{LP})+\log(4/\epsilon))/(\epsilon^2T\mathrm{LP})+1/T=O(u^{1/2}\log(1/u)) k / T ≤ 6 ( log ( n / LP ) + log ( 4/ ϵ )) / ( ϵ 2 T LP ) + 1/ T = O ( u 1/2 log ( 1/ u )) . As log ( 1 / δ ) = O ( log ( 1 / u ) ) \log(1/\delta)=O(\log(1/u)) log ( 1/ δ ) = O ( log ( 1/ u )) , (14) gives γ = O ( u 1 / 4 log ( 1 / u ) ) < 1 \gamma=O(u^{1/4}\log(1/u))<1 γ = O ( u 1/4 log ( 1/ u )) < 1 ; apply Theorem 4.4 . Corollary 3.2’s needles with T = n 2 T=n^2 T = n 2 have L P = 1 \mathrm{LP}=1 LP = 1 and u = log n / n 2 → 0 u=\log n/n^2\to0 u = log n / n 2 → 0 . □
Planning uses only depth-k k k states, with no explicit horizon dependence beyond the LP value. For Beta–Bernoulli arms this is O ( n k 2 ) O(nk^2) O ( n k 2 ) states; more generally, a compact state space or local optimization oracle remains necessary.
Several plays or selections. For the model of § 3.1 , sum (19) with a 0 = L P M , L / ( 2 L ) a_0=\mathrm{LP}_{M,L}/(2L) a 0 = LP M , L / ( 2 L ) and ∑ i I ( P i ) ≤ L \sum_i I(P_i)\le L ∑ i I ( P i ) ≤ L . As in Corollary 4.3, depth k = ⌈ 6 L log ( 4 n / ( ϵ L P M , L ) ) / ( ϵ 2 L P M , L ) ⌉ k=\left\lceil6L\log(4n/(\epsilon\mathrm{LP}_{M,L}))/(\epsilon^2\mathrm{LP}_{M,L})\right\rceil k = ⌈ 6 L log ( 4 n / ( ϵ LP M , L )) / ( ϵ 2 LP M , L ) ⌉ , which does not depend on T T T , keeps ( 1 − 4 ϵ ) L P M , L (1-4\epsilon)\mathrm{LP}_{M,L} ( 1 − 4 ϵ ) LP M , L . With δ = ϵ c L \delta=\epsilon c_L δ = ϵ c L , Proposition 3.4 then gives
A L G ≥ c L ( 1 − 5 ϵ − γ M ) L P M , L . \mathrm{ALG}\ge c_L(1-5\epsilon-\gamma_M)\mathrm{LP}_{M,L}. ALG ≥ c L ( 1 − 5 ϵ − γ M ) LP M , L .
Here γ M = k / T + O ( k log ( 1 / δ ) / ( M T ) ) \gamma_M=k/T+O\left(\sqrt{k\log(1/\delta)/(MT)}\right) γ M = k / T + O ( k log ( 1/ δ ) / ( M T ) ) : several plays per step divide the work, but not the k k k rounds of adaptivity within a local policy.
Choosing the cutoff without knowing the full LP
The full optimal policies are used only to prove that the depth-k k k LP has nearly their value. They need not be constructed. If LP is unknown, double k k k until
k ≥ 6 log ( 4 n / ( ϵ L P ( k ) ) ) ϵ 2 L P ( k ) . k\ge\frac{6\log(4n/(\epsilon\mathrm{LP}^{(k)}))}{\epsilon^2\mathrm{LP}^{(k)}}. k ≥ ϵ 2 LP ( k ) 6 log ( 4 n / ( ϵ LP ( k ) )) .
The right side is decreasing in L P ( k ) > 0 \mathrm{LP}^{(k)}>0 LP ( k ) > 0 , and L P ( k ) ≤ L P \mathrm{LP}^{(k)}\le\mathrm{LP} LP ( k ) ≤ LP . So this test implies (22) ’s sufficient cutoff condition. Stop also when k = T k=T k = T , where the full LP is reached and no truncation error remains, including when L P = 0 \mathrm{LP}=0 LP = 0 . Let k 0 k_0 k 0 be the cutoff in (22) and ϵ ≤ 1 / 8 \epsilon\le1/8 ϵ ≤ 1/8 . Since L P ( k ) \mathrm{LP}^{(k)} LP ( k ) is nondecreasing in k k k , every k ≥ k 0 k\ge k_0 k ≥ k 0 has L P ( k ) ≥ ( 1 − 4 ϵ ) L P \mathrm{LP}^{(k)}\ge(1-4\epsilon)\mathrm{LP} LP ( k ) ≥ ( 1 − 4 ϵ ) LP , and then the right side above is at most 4 k 0 4k_0 4 k 0 . The test therefore succeeds for every k ≥ 4 k 0 k\ge4k_0 k ≥ 4 k 0 , and doubling stops with k < 8 k 0 k<8k_0 k < 8 k 0 after O ( log k 0 ) O(\log k_0) O ( log k 0 ) LP solutions.
Alternatively, any positive lower bound L P ‾ ≤ L P \underline{\mathrm{LP}}\le\mathrm{LP} LP ≤ LP can replace LP in the cutoff formula. Use a 0 = L P ‾ / 2 a_0=\underline{\mathrm{LP}}/2 a 0 = LP /2 in (19) . The term 2 ϵ a 0 I ( P ) 2\epsilon a_0I(P) 2 ϵ a 0 I ( P ) , summed over arms, is at most ϵ L P ‾ ≤ ϵ L P \epsilon\underline{\mathrm{LP}}\le\epsilon\mathrm{LP} ϵ LP ≤ ϵ LP and the exponential term is at most ϵ L P \epsilon\mathrm{LP} ϵ LP . Thus the same ( 1 − 4 ϵ ) L P (1-4\epsilon)\mathrm{LP} ( 1 − 4 ϵ ) LP retention bound follows. The largest prior mean supplies such a lower bound whenever it is positive.
Certificates for sequential evaluation
The preceding sections use the LP to design policies and control their execution loss. The LP answers a decision question: how much can further evaluation improve the current choice? This certificate can accompany any sampling rule. Local truncation makes it computable without exploring the full remaining horizon, while the dual bounds every feasible adaptive continuation.
Throughout this section, observations and latent means lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , as in § 4 , and arms are independent. In particular, evaluations that share data across arms, such as scoring several models on the same test examples, are outside this model. At history H H H , let B B B be the remaining budget, b ( H ) = max i E [ θ i ∣ H ] ∈ [ 0 , 1 ] b(H)=\max_i\mathbb{E}[\theta_i\mid H]\in[0,1] b ( H ) = max i E [ θ i ∣ H ] ∈ [ 0 , 1 ] the value of stopping, and M ( H ) = E [ max i θ i ∣ H ] M(H)=\mathbb{E}[\max_i\theta_i\mid H] M ( H ) = E [ max i θ i ∣ H ] the perfect-information value. The expected simple regret of stopping decomposes as
M ( H ) − b ( H ) = [ M ( H ) − O P T B ( H ) ] + [ O P T B ( H ) − b ( H ) ] . M(H)-b(H)=[M(H)-\mathrm{OPT}_B(H)]+[\mathrm{OPT}_B(H)-b(H)]. M ( H ) − b ( H ) = [ M ( H ) − OPT B ( H )] + [ OPT B ( H ) − b ( H )] .
The first term is the least regret achievable under the remaining budget; the second is the improvement still available through evaluation. A large posterior regret can therefore coexist with little attainable improvement. The perfect-information gap M ( H ) − b ( H ) M(H)-b(H) M ( H ) − b ( H ) , used among other bounds by Hay et al. [35 ] , bounds the second term but ignores the remaining budget; the LP bounds it directly.
For fixed η , λ ≥ 0 \eta,\lambda\ge0 η , λ ≥ 0 let D B , k ( H ) = η + λ B + ∑ i G i , H ( k ) ( η , λ ) D_{B,k}(H)=\eta+\lambda B+\sum_iG_{i,H}^{(k)}(\eta,\lambda) D B , k ( H ) = η + λ B + ∑ i G i , H ( k ) ( η , λ ) : the objective of (7) with T T T replaced by B B B , each arm re-rooted at its state under H H H , and at most min { k , B } \min\{k,B\} min { k , B } further plays per arm.
For 0 < ϵ < 1 0<\epsilon<1 0 < ϵ < 1 , the explicit additive depth is
k ϵ = ⌈ 8 ϵ 2 log 4 n ϵ ⌉ . (24) k_\epsilon=\left\lceil\frac{8}{\epsilon^2}\log\frac{4n}{\epsilon}\right\rceil. \tag*{(24)} k ϵ = ⌈ ϵ 2 8 log ϵ 4 n ⌉ . (24)
Setting z = ϵ / 4 z=\epsilon/4 z = ϵ /4 in (21) makes each error term at most ϵ / 2 \epsilon/2 ϵ /2 at this depth, so L P ≤ L P ( k ϵ ) + ϵ \mathrm{LP}\le\mathrm{LP}^{(k_\epsilon)}+\epsilon LP ≤ LP ( k ϵ ) + ϵ . When k ≥ B k\ge B k ≥ B , no continuation is shortened.
Proposition 5.1 (Certificate for stopping). Consider independent Bayesian arms with exchangeable observations in [ 0 , 1 ] [0,1] [ 0 , 1 ] . Let 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1 and k ≥ k ϵ k \ge k_{\epsilon} k ≥ k ϵ , with k ϵ k_{\epsilon} k ϵ as in (24) . At every history H H H ,
OPT B ( H ) ≤ UB B , k ( H ) : = min { 1 , D B , k ( H ) + ϵ } . (25) \operatorname{OPT}_{B}(H) \le\operatorname{UB}_{B,k}(H) := \min\{1,D_{B,k}(H)+\epsilon\}. \tag*{(25)} OPT B ( H ) ≤ UB B , k ( H ) := min { 1 , D B , k ( H ) + ϵ } . (25)
Let π \pi π be any feasible policy and r > 0 r>0 r > 0 . Let π s t o p \pi_{\mathrm{stop}} π stop follow π \pi π until the first history H H H with UB B , k ( H ) − b ( H ) ≤ r \operatorname{UB}_{B,k}(H)-b(H)\le r UB B , k ( H ) − b ( H ) ≤ r , and then stop and select an arm of largest posterior mean. If no test succeeds before π \pi π terminates, make the same terminal selection as π \pi π . Let SR ( π ) = E [ max i θ i − θ J π ] \operatorname{SR}(\pi)=\mathbb{E}[\max_i\theta_i-\theta_{J_{\pi}}] SR ( π ) = E [ max i θ i − θ J π ] and J π J_{\pi} J π be the arm selected by π \pi π , then
SR ( π s t o p ) ≤ SR ( π ) + r , (26) \operatorname{SR}(\pi_{\mathrm{stop}})\le\operatorname{SR}(\pi)+r, \tag*{(26)} SR ( π stop ) ≤ SR ( π ) + r , (26)
:::
Proof. The bound applies to every collection of independent posteriors, with the same k ϵ k_{\epsilon} k ϵ . Conditioning on an adaptively collected history preserves the product posterior in this model: the action probabilities do not depend on the latent distributions once the observed history is fixed, and the observation likelihood factors by arm. Thus one can re-root the model at any history and apply Corollary 4.3. For k = k ϵ k=k_{\epsilon} k = k ϵ from (24) , the resulting depth-k k k dual gives
D B , k ( H ) = η + λ B + ∑ i G i , H ( k ) ( η , λ ) , η , λ ≥ 0 , D_{B,k}(H)=\eta+\lambda B+\sum_i G_{i,H}^{(k)}(\eta,\lambda),\qquad\eta,\lambda\ge0, D B , k ( H ) = η + λ B + i ∑ G i , H ( k ) ( η , λ ) , η , λ ≥ 0 ,
where the local recursions allow at most min { k , B } \min\{k,B\} min { k , B } further plays. Weak duality and Corollary 4.3 imply (25) . Any pair of nonnegative prices is valid; optimizing the dual tightens the bound. The error is zero when B ≤ k B\le k B ≤ k , or whenever the truncated and full LPs coincide. For Bernoulli observations with a predictive-probability oracle there are O ( n k 2 ) O(nk^2) O ( n k 2 ) additional count states.
At a fixed history H H H , stopping has conditional expected simple regret M ( H ) − b ( H ) M(H)-b(H) M ( H ) − b ( H ) ; the best continuation has regret M ( H ) − OPT B ( H ) M(H)-\operatorname{OPT}_{B}(H) M ( H ) − OPT B ( H ) . Their difference is OPT B ( H ) − b ( H ) ≤ UB B , k ( H ) − b ( H ) ≤ r \operatorname{OPT}_{B}(H)-b(H)\le\operatorname{UB}_{B,k}(H)-b(H)\le r OPT B ( H ) − b ( H ) ≤ UB B , k ( H ) − b ( H ) ≤ r .
For the policy statement, let τ \tau τ be the first time t < T t<T t < T at which the test succeeds while π \pi π is still running, and set τ = T \tau=T τ = T if there is no such time. Couple π \pi π and π s t o p \pi_{\mathrm{stop}} π stop until this test succeeds or π \pi π terminates. On { τ < T } \{\tau<T\} { τ < T } , conditional on H τ H_{\tau} H τ , the continuation of π \pi π is feasible for budget T − τ T-\tau T − τ , so E [ θ J π ∣ H τ ] ≤ OPT T − τ ( H τ ) ≤ b ( H τ ) + r \mathbb{E}[\theta_{J_{\pi}}\mid H_{\tau}]\le\operatorname{OPT}_{T-\tau}(H_{\tau})\le b(H_{\tau})+r E [ θ J π ∣ H τ ] ≤ OPT T − τ ( H τ ) ≤ b ( H τ ) + r , whatever selection rule π \pi π uses. The stopped policy has E [ θ J s t o p ∣ H τ ] = b ( H τ ) \mathbb{E}[\theta_{J_{\mathrm{stop}}}\mid H_{\tau}]=b(H_{\tau}) E [ θ J stop ∣ H τ ] = b ( H τ ) . If no early stop occurs, the two policies select the same arm. Taking expectations gives E [ θ J π ] − E [ θ J s t o p ] ≤ r P ( τ < T ) ≤ r \mathbb{E}[\theta_{J_{\pi}}]-\mathbb{E}[\theta_{J_{\mathrm{stop}}}]\le r\mathbb{P}(\tau<T)\le r E [ θ J π ] − E [ θ J stop ] ≤ r P ( τ < T ) ≤ r , and subtracting both from E max i θ i \mathbb{E}\max_i\theta_i E max i θ i gives (26) . The certificate holds at every history, so repeated checking introduces no additional error. □
What the certificate establishes. For any continuation with certified conditional reward lower bound V ( H ) V(H) V ( H ) , its deficit from the best budget-feasible continuation is at most UB B , k ( H ) − V ( H ) \operatorname{UB}_{B,k}(H)-V(H) UB B , k ( H ) − V ( H ) . The same certificate proves inf π SR ( π ∣ H ) ≥ [ M ( H ) − UB B , k ( H ) ] + \inf_{\pi}\operatorname{SR}(\pi\mid H)\ge[M(H)-\operatorname{UB}_{B,k}(H)]^{+} inf π SR ( π ∣ H ) ≥ [ M ( H ) − UB B , k ( H ) ] + : it can establish that the available budget cannot achieve a specified regret target. Thus evaluation can report both an achievable value and a ceiling on further improvement. A loose relaxation can only delay stopping.
Switch-aware continuation certificates
Fix an observed history H H H , an initially configured arm j j j , and nonnegative integer budgets B B B and S S S for future plays and changes of evaluation arm. Final recommendation itself does not require another evaluation. The joint relaxation is
LP B , S ( H ) = max { ∑ i R i : ∑ i q i ≤ 1 , ∑ i w i ≤ B , ∑ i ≠ j a i ≤ S } , a i = P ( τ i ≥ 1 ) . \operatorname{LP}_{B,S}(H)=\max\left\{\sum_i R_i:\sum_i q_i\le1,\ \sum_i w_i\le B,\ \sum_{i\ne j}a_i\le S\right\},\qquad a_i=\mathbb{P}(\tau_i\ge1). LP B , S ( H ) = max ⎩ ⎨ ⎧ i ∑ R i : i ∑ q i ≤ 1 , i ∑ w i ≤ B , i = j ∑ a i ≤ S ⎭ ⎬ ⎫ , a i = P ( τ i ≥ 1 ) .
Use local depth at most B B B in the full LP and min { k , B } \min\{k,B\} min { k , B } in LP B , S ( k ) ( H ) \operatorname{LP}_{B,S}^{(k)}(H) LP B , S ( k ) ( H ) . Every distinct nonconcurrent arm played by a global continuation requires at least one switch, so the pathway count of such arms is at most S S S . Marginalization gives the expected activation constraint above, in addition to the usual play and selection constraints. Thus OPT B , S ( H ) ≤ LP B , S ( H ) \operatorname{OPT}_{B,S}(H)\le\operatorname{LP}_{B,S}(H) OPT B , S ( H ) ≤ LP B , S ( H ) . Repeated returns consume switches that this relaxation ignores.
In the dual, let G i ( u ; η , λ ) G_i(u;\eta,\lambda) G i ( u ; η , λ ) be the ordinary depth-restricted recursion after the first future play. At the re-rooted state u i u_i u i , use
G i , H ( k ) ( η , λ , κ ) = max { 0 , r u i − η , − λ − κ 1 i ≠ j + ∑ v p u i v G i ( v ; η , λ ) } . G_{i,H}^{(k)}(\eta,\lambda,\kappa)=\max\left\{0,r_{u_i}-\eta,-\lambda-\kappa\mathbf{1}_{i\ne j}+\sum_v p_{u_i v}G_i(v;\eta,\lambda)\right\}. G i , H ( k ) ( η , λ , κ ) = max { 0 , r u i − η , − λ − κ 1 i = j + v ∑ p u i v G i ( v ; η , λ ) } .
The play option is omitted when no plays remain. The price κ \kappa κ is charged only on the first future play. Weak duality gives
D B , S , k ( H ) = η + λ B + κ S + ∑ i G i , H ( k ) ( η , λ , κ ) . (27) D_{B,S,k}(H)=\eta+\lambda B+\kappa S+\sum_i G_{i,H}^{(k)}(\eta,\lambda,\kappa). \tag*{(27)} D B , S , k ( H ) = η + λ B + κ S + i ∑ G i , H ( k ) ( η , λ , κ ) . (27)
At k ≥ 1 k\ge1 k ≥ 1 , truncation agrees with the original policy until its first play or its earlier terminal decision, so it preserves a i a_i a i as well as q i q_i q i , and does not increase w i w_i w i . The proof of (21) therefore applies unchanged to this extra-constrained LP. Consequently
OPT B , S ( H ) ≤ min { 1 , D B , S , k ( H ) + ϵ } for k = k ϵ . \operatorname{OPT}_{B,S}(H)\le\min\{1,D_{B,S,k}(H)+\epsilon\}\quad\text{for }k=k_\epsilon. OPT B , S ( H ) ≤ min { 1 , D B , S , k ( H ) + ϵ } for k = k ϵ .
The product posterior is preserved on conditioning on H H H , as above. Coupling any switch-feasible policy to its early-stopped version now proves (26) under both budgets.
A resource-sensitive illustration. A known, currently configured arm has mean b b b . Each of the other n − 1 n-1 n − 1 arms is uninspected and independently has mean one with probability p ≤ b p\le b p ≤ b and zero otherwise, revealed by one play. Let n ˉ = min { B , S , n − 1 } \bar n=\min\{B,S,n-1\} n ˉ = min { B , S , n − 1 } and assume n ˉ p ≤ 1 \bar n p\le1 n ˉ p ≤ 1 . Every arm is resolved by at most one play, so depth one incurs no truncation loss, and the certificate holds with ϵ = 0 \epsilon=0 ϵ = 0 :
OPT B , S ≤ LP B , S ( 1 ) = b + ( 1 − b ) n ˉ p . \operatorname{OPT}_{B,S}\le\operatorname{LP}_{B,S}^{(1)}=b+(1-b)\bar n p. OPT B , S ≤ LP B , S ( 1 ) = b + ( 1 − b ) n ˉ p .
For the dual, a i = w i a_i=w_i a i = w i for uncertain arms, so they share a total inspection-mass constraint ∑ i a i ≤ n ˉ \sum_i a_i\le\bar n ∑ i a i ≤ n ˉ . Use η = b \eta=b η = b and assign price ( 1 − b ) p (1-b)p ( 1 − b ) p to whichever of B B B and S S S equals n ˉ \bar n n ˉ , with zero price on the other. Every local surplus is zero: playing an uncertain arm yields expected surplus ( 1 − b ) p (1-b)p ( 1 − b ) p before this price, and selecting it unobserved yields p − b ≤ 0 p-b\le0 p − b ≤ 0 . If instead n ˉ = n − 1 < min { B , S } \bar n=n-1<\min\{B,S\} n ˉ = n − 1 < min { B , S } , take η = b \eta=b η = b and zero resource prices; each uncertain local surplus is ( 1 − b ) p (1-b)p ( 1 − b ) p , yielding the same bound.
To attain this LP value, choose n ˉ \bar n n ˉ uncertain arms. Each plays once and selects exactly when its revealed mean is one; all other uncertain arms quit at the root. The known arm selects at its root with probability 1 − n ˉ p 1-\bar n p 1 − n ˉ p and otherwise quits. These local policies have total selection probability n ˉ p + ( 1 − n ˉ p ) = 1 \bar n p+(1-\bar n p)=1 n ˉ p + ( 1 − n ˉ p ) = 1 , expected work and noncurrent activation mass both equal to n ˉ \bar n n ˉ , and reward n ˉ p + b ( 1 − n ˉ p ) = b + ( 1 − b ) n ˉ p \bar n p+b(1-\bar n p)=b+(1-b)\bar n p n ˉ p + b ( 1 − n ˉ p ) = b + ( 1 − b ) n ˉ p . They are feasible because n ˉ ≤ min { B , S , n − 1 } \bar n\le\min\{B,S,n-1\} n ˉ ≤ min { B , S , n − 1 } and n ˉ p ≤ 1 \bar n p\le1 n ˉ p ≤ 1 , proving equality for the LP. The actual optimum is b + ( 1 − b ) [ 1 − ( 1 − p ) n ˉ ] b+(1-b)[1-(1-p)^{\bar n}] b + ( 1 − b ) [ 1 − ( 1 − p ) n ˉ ] , because each inspected arm has the same independent chance of success and further inspection helps only before the first success.
For b = 0.6 b=0.6 b = 0.6 , p = 0.001 p=0.001 p = 0.001 , n − 1 = 10,000 n-1=10{,}000 n − 1 = 10 , 000 , B = 1,000 B=1{,}000 B = 1 , 000 , and S = 10 S=10 S = 10 , the certified gain is at most 0.004 0.004 0.004 , so r = 0.005 r=0.005 r = 0.005 permits stopping. Yet M = ( 1 − b ) [ 1 − ( 1 − p ) n − 1 ] ≈ 0.4 M=(1-b)[1-(1-p)^{n-1}]\approx0.4 M = ( 1 − b ) [ 1 − ( 1 − p ) n − 1 ] ≈ 0.4 . With ten switches, most of this uncertainty cannot be resolved, however large B B B is.
Scheduling short policies with setup costs
Recall f ⋆ = 1 − e − 1 f^\star=1-e^{-1} f ⋆ = 1 − e − 1 . Let c i ≥ 0 c_i\ge0 c i ≥ 0 be the cost of configuring arm i i i upon entry from another arm. The initially configured arm j j j can be evaluated without a setup cost. Observations cost one, and a hard combined budget T T T includes observations and setups. Setup costs consume this budget; the terminal payoff remains r u r_u r u . For local policies write a i = P ( τ i ≥ 1 ) a_i=\mathbb{P}(\tau_i\ge1) a i = P ( τ i ≥ 1 ) , c j = 0 c_j=0 c j = 0 in the relaxation, and impose
∑ i q i ≤ 1 , ∑ i ( w i + c i a i ) ≤ T . \sum_i q_i\le1,\qquad\sum_i(w_i+c_i a_i)\le T. i ∑ q i ≤ 1 , i ∑ ( w i + c i a i ) ≤ T .
This is a relaxation of all policies in the setup-cost model: every other visited arm incurs at least one setup, and repeated entries only increase actual cost. Root selection or quitting requires no evaluation setup.
Proposition 5.2. For independent local policies of depth at most k k k , let c max = max i c i c_{\max}=\max_i c_i c m a x = max i c i , k c = k + c max k_c=k+c_{\max} k c = k + c m a x , and R 0 = ∑ i R i R_0=\sum_i R_i R 0 = ∑ i R i . For 0 < δ < f ⋆ 0<\delta<f^\star 0 < δ < f ⋆ , define
γ c = k c + 2 k c T log ( 1 / δ ) + ( 2 k c / 3 ) log ( 1 / δ ) T . \gamma_c=\frac{k_c+\sqrt{2k_cT\log(1/\delta)}+(2k_c/3)\log(1/\delta)}{T}. γ c = T k c + 2 k c T log ( 1/ δ ) + ( 2 k c /3 ) log ( 1/ δ ) . If γ c < 1 \gamma_c<1 γ c < 1 , a feasible schedule with no returns obtains at least ( f ⋆ − δ ) ( 1 − γ c ) R 0 (f^\star-\delta)(1-\gamma_c)R_0 ( f ⋆ − δ ) ( 1 − γ c ) R 0 .
Proof. Fix an order with the current arm first and the others in any order. Independently replace each policy by the null policy with probability γ c \gamma_c γ c , and define ( τ ˉ i , I ˉ i , Y ˉ i ) (\bar{\tau}_i,\bar{I}_i,\bar{Y}_i) ( τ ˉ i , I ˉ i , Y ˉ i ) as in (16) , with retention probability 1 − γ c 1-\gamma_c 1 − γ c . Run each admitted policy to completion in one contiguous block, admitting only while cost already used is at most T − k c T-k_c T − k c . A completed local selection nominates its arm; continue evaluation without returning to any completed arm. Finally select an arm with the largest currently selectable payoff r u i r_{u_i} r u i , including when no arm was nominated. This payoff is nonnegative and is at least the payoff of every nominee. Each arm is evaluated in at most one block. Its complete local block cost is C i = τ i + c i 1 τ i ≥ 1 ≤ k c C_i=\tau_i+c_i\mathbf{1}_{\tau_i\ge1}\le k_c C i = τ i + c i 1 τ i ≥ 1 ≤ k c , and its cost after thinning is C ˉ i = B i C i \bar{C}_i=B_iC_i C ˉ i = B i C i . Initial execution of arm j j j has no setup fee because c j = 0 c_j=0 c j = 0 .
The variables C ˉ i \bar{C}_i C ˉ i are independent, have total mean at most ( 1 − γ c ) T (1-\gamma_c)T ( 1 − γ c ) T and total variance at most k c T k_cT k c T . Bernstein’s inequality bounds the probability that any given policy is not admitted by δ \delta δ , exactly as in Theorem 3.3 . Let A i A_i A i be the event that policy i i i is admitted. It depends only on earlier policies, so it is independent of Y ˉ i \bar{Y}_i Y ˉ i .
The variables Y ˉ i \bar{Y}_i Y ˉ i are independent nonnegative selected payoffs from the complete local executions. For every v ≥ 0 v\ge0 v ≥ 0 , put μ v = ∑ i P ( Y ˉ i > v ) ≤ ∑ i q ˉ i ≤ 1 \mu_v=\sum_i\mathbb{P}(\bar{Y}_i>v)\le\sum_i\bar{q}_i\le1 μ v = ∑ i P ( Y ˉ i > v ) ≤ ∑ i q ˉ i ≤ 1 , where q ˉ i = E I ˉ i \bar{q}_i=\mathbb{E}\bar{I}_i q ˉ i = E I ˉ i . Hence
P ( max i Y ˉ i > v ) ≥ 1 − e − μ v ≥ f ⋆ μ v . \mathbb{P}\left(\max_i\bar{Y}_i>v\right)\ge1-e^{-\mu_v}\ge f^\star\mu_v. P ( i max Y ˉ i > v ) ≥ 1 − e − μ v ≥ f ⋆ μ v .
Integrating gives E max i Y ˉ i ≥ f ⋆ ∑ i E Y ˉ i = f ⋆ ( 1 − γ c ) R 0 \mathbb{E}\max_i\bar{Y}_i\ge f^\star\sum_i\mathbb{E}\bar{Y}_i=f^\star(1-\gamma_c)R_0 E max i Y ˉ i ≥ f ⋆ ∑ i E Y ˉ i = f ⋆ ( 1 − γ c ) R 0 . The schedule’s selected payoff is at least max i 1 A i Y ˉ i \max_i\mathbf{1}_{A_i}\bar{Y}_i max i 1 A i Y ˉ i . Removing values for unadmitted policies lowers the maximum by at most ∑ i ( 1 − 1 A i ) Y ˉ i \sum_i(1-\mathbf{1}_{A_i})\bar{Y}_i ∑ i ( 1 − 1 A i ) Y ˉ i , whose expectation is
∑ i P ( A i c ) E Y ˉ i ≤ δ ∑ i E Y ˉ i = δ ( 1 − γ c ) R 0 . \sum_i\mathbb{P}(A_i^c)\mathbb{E}\bar{Y}_i\le\delta\sum_i\mathbb{E}\bar{Y}_i=\delta(1-\gamma_c)R_0. i ∑ P ( A i c ) E Y ˉ i ≤ δ i ∑ E Y ˉ i = δ ( 1 − γ c ) R 0 .
Combining these bounds proves the proposition. □ \square □
For k ≥ 1 k\ge1 k ≥ 1 , the selection coin preserves activation and reduces work, so Corollary 4.3 also holds for the setup-cost LP. Solve its truncated version and apply Proposition 5.2 . In particular, the relative cutoff of (22) gives A L G ≥ f ⋆ ( 1 − 5 ϵ − γ c ) L P s e t u p \mathrm{ALG}\ge f^\star(1-5\epsilon-\gamma_c)\mathrm{LP}_{\mathrm{setup}} ALG ≥ f ⋆ ( 1 − 5 ϵ − γ c ) LP setup with δ = ϵ f ⋆ \delta=\epsilon f^\star δ = ϵ f ⋆ . Schedulability now requires the entire block, including setup, to be short relative to the resource budget.
Metric movement and routing certificates
Let evaluation arms have a fixed metric d d d , current location j j j , and a remaining hard movement budget Δ \Delta Δ , separate from the remaining play budget B B B . Let Q Δ ⊆ [ 0 , 1 ] n \mathcal{Q}_\Delta\subseteq[0,1]^n Q Δ ⊆ [ 0 , 1 ] n be a compact convex set that contains, for every walk from j j j of length at most Δ \Delta Δ , the incidence vector of the set of arms the walk visits. Define its support function by
σ Q Δ ( κ ) = max z ∈ Q Δ ∑ i κ i z i . \sigma_{\mathcal{Q}_\Delta}(\kappa)=\max_{z\in\mathcal{Q}_\Delta}\sum_i\kappa_i z_i. σ Q Δ ( κ ) = z ∈ Q Δ max i ∑ κ i z i .
For an exact visitation relaxation this is the rooted orienteering objective, as in [31 ] ; an outer relaxation can instead give an efficiently computable upper bound. The movement budget couples arms through routing, while their latent distributions remain independent.
Proposition 5.3. In the bounded exchangeable Bayesian model, take nonnegative prices η \eta η , λ \lambda λ , and κ \kappa κ . Let G i , H ( κ ) ( η , λ , κ i ) G^{(\kappa)}_{i,H}(\eta,\lambda,\kappa_i) G i , H ( κ ) ( η , λ , κ i ) be the local surplus over at most min { κ , B } \min\{\kappa,B\} min { κ , B } future observations, charging κ i \kappa_i κ i on the first future play. For κ = κ ϵ \kappa=\kappa_\epsilon κ = κ ϵ ,
OPT B , Δ ( H ) ≤ min { 1 , D B , Δ , κ ( H ) + ϵ } , \operatorname{OPT}_{B,\Delta}(H)\le\min\{1,D_{B,\Delta,\kappa}(H)+\epsilon\}, OPT B , Δ ( H ) ≤ min { 1 , D B , Δ , κ ( H ) + ϵ } , where
D B , Δ , κ ( H ) = η + λ B + σ Q Δ ( κ ) + ∑ i G i , H ( κ ) ( η , λ , κ i ) . (28) D_{B,\Delta,\kappa}(H)=\eta+\lambda B+\sigma_{\mathcal{Q}_\Delta}(\kappa)+\sum_iG^{(\kappa)}_{i,H}(\eta,\lambda,\kappa_i). \tag*{(28)} D B , Δ , κ ( H ) = η + λ B + σ Q Δ ( κ ) + i ∑ G i , H ( κ ) ( η , λ , κ i ) . (28) Consequently the early-stopping guarantee of Proposition 5.1 holds under both budgets.
Proof. For each feasible adaptive continuation, let z i z_i z i be the probability that its movement walk visits arm i i i , and a i a_i a i the probability of making at least one future play of that arm. Then a i ≤ z i a_i \le z_i a i ≤ z i and z ∈ Q Δ z \in Q_\Delta z ∈ Q Δ , by convexity and the hard movement constraint. Marginalizing gives feasible local policies for the relaxation with selection mass at most one, expected work at most B B B , and a ≤ z ∈ Q Δ a \le z \in Q_\Delta a ≤ z ∈ Q Δ . For any such feasible collection,
∑ i R i ≤ η + λ B + ∑ i κ i z i + ∑ i ( R i − η q i − λ w i − κ i a i ) . (29) \sum_i R_i \le\eta+ \lambda B + \sum_i \kappa_i z_i + \sum_i (R_i - \eta q_i - \lambda w_i - \kappa_i a_i). \tag*{(29)} i ∑ R i ≤ η + λ B + i ∑ κ i z i + i ∑ ( R i − η q i − λ w i − κ i a i ) . (29)
Maximizing each local term and the routing term gives (28) as a valid dual upper bound for the depth-k k k relaxation. Truncation preserves a i a_i a i and q i q_i q i , reduces w i w_i w i , and can keep the same routing vector z z z . Hence the additive calculation of Corollary 4.3 bounds the full relaxation by its truncated value plus ϵ \epsilon ϵ . This proves the continuation bound. Conditioning at the first successful stopping test, as in Proposition 5.1, proves the regret claim.
Any certified upper bound on σ Q Δ ( κ ) \sigma_{Q_\Delta}(\kappa) σ Q Δ ( κ ) may replace it in (28). When Q Δ Q_\Delta Q Δ is the exact visitation convex hull, an α \alpha α -approximate orienteering route of value V ≥ σ Q Δ ( κ ) / α V \ge\sigma_{Q_\Delta}(\kappa)/\alpha V ≥ σ Q Δ ( κ ) / α gives the upper bound α V \alpha V α V . For an outer relaxation, one must instead upper-bound that relaxation’s support value.
Guha and Munagala (2009, Lemma 1 and Corollary 1) obtain the no-return transformation and the orienteering formulation for their Lagrangian objective, with hard distance control. What is added here is truncation that preserves both selection and activation probabilities, so that the remaining-budget certificate can be evaluated on short local state spaces.
Beyond posterior means: Terminal utilities and prediction
Sequential experiments can support many terminal decisions besides choosing the largest posterior mean. Expected utility, threshold satisfaction, and prediction under a specified loss are established decision-theoretic criteria. The value of information for such decisions is classical [8 , 16 ] . This section explains which of the preceding approximation arguments apply to these criteria and bounds the loss from shortening the local experiments they induce.
Keep one play per step and one terminal selection. At a final history H H H , arm i i i has a known nonnegative score ψ i ( H ) \psi_i(H) ψ i ( H ) , determined by its local observations. The objective is E [ max i ψ i ( H ) ] \mathbb{E}[\max_i \psi_i(H)] E [ max i ψ i ( H )] . In the LPs and algorithms, replace r u r_u r u by the terminal score at state u u u and compare those scores at the final choice. Observations collected during exploration do not themselves contribute to the objective.
For one Bayesian arm, let t t t count its local observations and let F t \mathcal{F}_t F t be its local filtration, as in Section 4. Observations lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] and are iid given a latent distribution D D D with mean θ \theta θ . Write μ t = E [ θ ∣ F t ] \mu_t = \mathbb{E}[\theta\mid\mathcal{F}_t] μ t = E [ θ ∣ F t ] and v t = Var ( θ ∣ F t ) v_t = \operatorname{Var}(\theta\mid\mathcal{F}_t) v t = Var ( θ ∣ F t ) .
Established terminal decision criteria
Expected utility and satisficing. For a bounded nonnegative utility g g g , use ψ t = E [ g ( θ ) ∣ F t ] \psi_t = \mathbb{E}[g(\theta) \mid\mathcal{F}_t] ψ t = E [ g ( θ ) ∣ F t ] ; examples include g ( θ ) = θ g(\theta) = \sqrt{\theta} g ( θ ) = θ and g ( θ ) = θ 2 g(\theta) = \theta^2 g ( θ ) = θ 2 . A function f ( μ t ) f(\mu_t) f ( μ t ) instead evaluates the reported posterior mean and generally differs from E [ f ( θ ) ∣ F t ] \mathbb{E}[f(\theta) \mid\mathcal{F}_t] E [ f ( θ ) ∣ F t ] .
Satisficing uses an aspiration level rather than insisting on exact maximization [58 ] . In bandits, Reverdy et al. (2017) study satisfaction thresholds for both mean and realized rewards, and Russo and Van Roy (2022) study time-sensitive learning of satisfactory actions. Related PAC selection and stopping guarantees seek an approximately optimal arm with prescribed confidence [20 ] . Here we use a fixed-budget Bayesian terminal criterion. For a quality threshold θ 0 ∈ [ 0 , 1 ] \theta_0 \in[0,1] θ 0 ∈ [ 0 , 1 ] , set
g ( θ ) = 1 { θ ≥ θ 0 } , ψ t = P ( θ ≥ θ 0 ∣ F t ) . g(\theta) = \mathbf{1}\{\theta\ge\theta_0\}, \qquad\psi_t = \mathbb{P}(\theta\ge\theta_0 \mid\mathcal{F}_t). g ( θ ) = 1 { θ ≥ θ 0 } , ψ t = P ( θ ≥ θ 0 ∣ F t ) .
For the arm J J J selected at the final history H H H , the tower property gives E [ ψ J ( H ) ] = P ( θ J ≥ θ 0 ) \mathbb{E}[\psi_J(H)] = \mathbb{P}(\theta_J \ge\theta_0) E [ ψ J ( H )] = P ( θ J ≥ θ 0 ) . Thus the objective maximizes the probability that the final choice meets the threshold. A prescribed posterior-confidence requirement would additionally need a constraint.
Selection accompanied by a prediction. Under squared-error loss, the posterior mean is the classical Bayes prediction. Savage [55 ] characterizes losses whose expected value is minimized by reporting the mean; Gneiting (2011, Section 3.1) gives a modern treatment of this connection between the prediction and its loss.
As a concrete terminal decision, suppose that selecting an arm also requires a prediction x ∈ [ 0 , 1 ] x \in[0,1] x ∈ [ 0 , 1 ] of θ \sqrt{\theta} θ , with payoff θ − a ( θ − x ) 2 \theta-a(\sqrt{\theta}-x)^2 θ − a ( θ − x ) 2 , where 0 ≤ a ≤ 1 0 \le a \le1 0 ≤ a ≤ 1 . Put κ t = E [ θ ∣ F t ] \kappa_t = \mathbb{E}[\sqrt{\theta}\mid\mathcal{F}_t] κ t = E [ θ ∣ F t ] and σ t 2 = Var ( θ ∣ F t ) = μ t − κ t 2 \sigma_t^2 = \operatorname{Var}(\sqrt{\theta}\mid\mathcal{F}_t)=\mu_t-\kappa_t^2 σ t 2 = Var ( θ ∣ F t ) = μ t − κ t 2 . Then
E [ θ − a ( θ − x ) 2 ∣ F t ] = μ t − a [ σ t 2 + ( κ t − x ) 2 ] . \mathbb{E}[\theta-a(\sqrt{\theta}-x)^2\mid\mathcal{F}_t]=\mu_t-a\left[\sigma_t^2+(\kappa_t-x)^2\right]. E [ θ − a ( θ − x ) 2 ∣ F t ] = μ t − a [ σ t 2 + ( κ t − x ) 2 ] .
The optimal prediction is x = κ t x=\kappa_t x = κ t , and its optimized value is
h t = μ t − a Var ( θ ∣ F t ) = ( 1 − a ) μ t + a κ t 2 ∈ [ 0 , 1 ] . (30) h_t=\mu_t-a\operatorname{Var}(\sqrt{\theta}\mid\mathcal{F}_t)=(1-a)\mu_t+a\kappa_t^2\in[0,1]. \tag*{(30)} h t = μ t − a Var ( θ ∣ F t ) = ( 1 − a ) μ t + a κ t 2 ∈ [ 0 , 1 ] . (30)
This optimized conditional expectation is the selectable payoff. The penalty is the Bayes prediction risk for the latent quantity θ \sqrt{\theta} θ . Predicting θ \theta θ itself under squared error gives the analogous value μ t − a v t \mu_t-av_t μ t − a v t . These variances describe posterior uncertainty about the latent mean, rather than the variability of individual future observations.
At a = 1 a=1 a = 1 , h t = κ t 2 h_t=\kappa_t^2 h t = κ t 2 is also the certainty equivalent for square-root utility: its square root is the posterior expected utility κ t \kappa_t κ t (Pratt, [51 ] ). Using this certainty equivalent differs from using κ t \kappa_t κ t itself. For example, an arm known to have θ = 1 / 2 \theta=1/2 θ = 1/2 and an arm equally likely to have θ = 0 \theta=0 θ = 0 or 1 1 1 have the same posterior mean, but their values in (30) are 1 / 2 1/2 1/2 and 1 / 2 − a / 4 1/2-a/4 1/2 − a /4 , respectively.
Value of information and policy execution
The relevant martingale properties are consequences of classical value-of-information arguments ([8 , 16 ] ). For either squared-error prediction problem above, let B t B_t B t denote its minimum conditional expected loss. A prediction chosen at time t t t remains available after the next observation; reoptimizing can only improve on that prediction. Hence
E [ B t + 1 ∣ F t ] ≤ B t . \mathbb{E}[B_{t+1}\mid\mathcal{F}_t]\le B_t. E [ B t + 1 ∣ F t ] ≤ B t .
Thus posterior Bayes risk is a supermartingale. A posterior expected utility for a fixed terminal action is a martingale; optimizing over the available terminal actions gives a submartingale. We record the following particular cases to identify which execution argument is applicable.
Conditional total variance gives
E [ v t + 1 ∣ F t ] = v t − E [ ( μ t + 1 − μ t ) 2 ∣ F t ] . (31) \mathbb{E}[v_{t+1}\mid\mathcal{F}_t]=v_t-\mathbb{E}[(\mu_{t+1}-\mu_t)^2\mid\mathcal{F}_t]. \tag*{(31)} E [ v t + 1 ∣ F t ] = v t − E [( μ t + 1 − μ t ) 2 ∣ F t ] . (31)
Consequently:
E [ g ( θ ) ∣ F t ] \mathbb{E}[g(\theta)\mid\mathcal{F}_t] E [ g ( θ ) ∣ F t ] is a martingale for every bounded nonnegative g g g . This includes posterior threshold probabilities, κ t \kappa_t κ t , and E [ θ 2 ∣ F t ] = μ t 2 + v t \mathbb{E}[\theta^2\mid\mathcal{F}_t]=\mu_t^2+v_t E [ θ 2 ∣ F t ] = μ t 2 + v t . Conditional Jensen makes a nonnegative concave function of μ t \mu_t μ t a supermartingale, and a nonnegative convex function a submartingale.
For a ≥ 0 a\ge0 a ≥ 0 , μ t + a v t \mu_t+av_t μ t + a v t is a nonnegative supermartingale, as is μ t + a v t \mu_t+a\sqrt{v_t} μ t + a v t , since E [ v t + 1 ∣ F t ] ≤ E [ v t + 1 ∣ F t ] ≤ v t \mathbb{E}[\sqrt{v_{t+1}}\mid\mathcal{F}_t]\le\sqrt{\mathbb{E}[v_{t+1}\mid\mathcal{F}_t]}\le\sqrt{v_t} E [ v t + 1 ∣ F t ] ≤ E [ v t + 1 ∣ F t ] ≤ v t .
E [ h t + 1 ∣ F t ] − h t = a E [ ( κ t + 1 − κ t ) 2 ∣ F t ] ≥ 0. \mathbb{E}[h_{t+1}\mid\mathcal{F}_t]-h_t=a\mathbb{E}[(\kappa_{t+1}-\kappa_t)^2\mid\mathcal{F}_t]\ge0. E [ h t + 1 ∣ F t ] − h t = a E [( κ t + 1 − κ t ) 2 ∣ F t ] ≥ 0.
This is the value of improving the terminal prediction, with the arm held fixed.
When interruption is allowed. If the terminal score is nonnegative and a supermartingale, its current value bounds the expected selected score of an interrupted local policy. Theorem 2.1 therefore applies with r u r_u r u replaced by that score. This covers fixed-utility posteriors, including the satisficing probabilities above, nonnegative concave functions of μ t \mu_t μ t , and the two positive variance adjustments just listed. Supermartingale selectable utilities already occur in the budgeted learning framework of Gruha and Munagala (2008, Section 6).
When the local policy must finish. For submartingale values such as h t h_t h t or μ t − a v t \mu_t-a v_t μ t − a v t , the current value need not bound what a continuation would obtain. The interruption step of Theorem 2.1 is then unavailable. Theorem 3.3 instead completes every admitted local policy and requires only nonnegative terminal payoffs. To use it, we need short local policies whose selected scores approximate those of the full policies. The next subsection supplies this comparison for expected utilities E [ g ( θ ) ∣ F t ] \mathbb{E}[g(\theta)\mid\mathcal{F}_t] E [ g ( θ ) ∣ F t ] with uniformly continuous g g g , Lipschitz functions of μ t \mu_t μ t , μ t ± a v t \mu_t\pm a v_t μ t ± a v t , and the prediction score h t h_t h t .
Loss from stopping a local experiment after k k k observations
Use exactly the operation from Section 4: follow a local policy P P P until it terminates or reaches depth k k k ; if still active, select with its conditional eventual-selection probability χ k \chi_k χ k from (17), and otherwise quit. The resulting policy P [ k ] P^{[k]} P [ k ] preserves selection probability and uses no more plays; only its terminal score can change. As in Corollary 4.3, we charge that change to the selection probability, using the empirical mean θ ^ k \hat{\theta}_k θ ^ k of the first k k k observations as an F k \mathcal{F}_k F k -measurable comparator. Since a posterior mean minimizes conditional mean squared error, for every stopping time τ ≥ k \tau\geq k τ ≥ k ,
v τ ≤ E [ ( θ − θ ^ k ) 2 ∣ F τ ] , σ k 2 ≤ E [ ( θ − θ ^ k ) 2 ∣ F k ] . (32) v_\tau\leq\mathbb{E}[(\theta-\hat{\theta}_k)^2\mid\mathcal{F}_\tau],\qquad\sigma_k^2\leq\mathbb{E}[(\sqrt{\theta}-\sqrt{\hat{\theta}_k})^2\mid\mathcal{F}_k]. \tag*{(32)} v τ ≤ E [( θ − θ ^ k ) 2 ∣ F τ ] , σ k 2 ≤ E [( θ − θ ^ k ) 2 ∣ F k ] . (32)
Let C C C be the event that P P P is still active at the cutoff, and S = C ∩ { P eventually selects } S=C\cap\{P\text{ eventually selects}\} S = C ∩ { P eventually selects } . Set τ = max { τ ( P ) , k } \tau=\max\{\tau(P),k\} τ = max { τ ( P ) , k } , so that k ≤ τ ≤ T k\leq\tau\leq T k ≤ τ ≤ T and it agrees with the original stopping time on S S S . For a local score process ψ t \psi_t ψ t , write R ~ ψ ( P ) = E [ ψ τ ( P ) 1 { P selects } ] \widetilde{R}_{\psi}(P)=\mathbb{E}[\psi_{\tau(P)}1\{P\text{ selects}\}] R ψ ( P ) = E [ ψ τ ( P ) 1 { P selects }] . For g : [ 0 , 1 ] → [ 0 , 1 ] g:[0,1]\to[0,1] g : [ 0 , 1 ] → [ 0 , 1 ] , let ω g ( z ) = sup { ∣ g ( x ) − g ( y ) ∣ : x , y ∈ [ 0 , 1 ] , ∣ x − y ∣ ≤ z } \omega_g(z)=\sup\{|g(x)-g(y)|:x,y\in[0,1],\ |x-y|\leq z\} ω g ( z ) = sup { ∣ g ( x ) − g ( y ) ∣ : x , y ∈ [ 0 , 1 ] , ∣ x − y ∣ ≤ z } be its modulus of continuity.
Lemma 6.1. Let ( ψ t ) t = 0 T (\psi_t)_{t=0}^{T} ( ψ t ) t = 0 T be an integrable process adapted to ( F t ) (\mathcal{F}_t) ( F t ) , and let 1 ≤ k ≤ T 1\leq k\leq T 1 ≤ k ≤ T . Then
R ~ ψ ( P ) − R ~ ψ ( P [ k ] ) = E [ ( ψ τ − ψ k ) 1 S ] , \widetilde{R}_{\psi}(P)-\widetilde{R}_{\psi}(P^{[k]})=\mathbb{E}[(\psi_\tau-\psi_k)1_S], R ψ ( P ) − R ψ ( P [ k ] ) = E [( ψ τ − ψ k ) 1 S ] , while I ( P [ k ] ) = I ( P ) I(P^{[k]})=I(P) I ( P [ k ] ) = I ( P ) and W ( P [ k ] ) ≤ W ( P ) W(P^{[k]})\leq W(P) W ( P [ k ] ) ≤ W ( P ) . For the bounded conditionally iid observations considered here and every 0 < z ≤ 1 0<z\leq1 0 < z ≤ 1 ,
R ~ E [ g ( θ ) ∣ ⋅ ] ( P [ k ] ) ≥ R ~ E [ g ( θ ) ∣ ⋅ ] ( P ) − 2 ω g ( z ) I ( P ) − 2 e − 2 k z 2 , (33) \widetilde{R}_{\mathbb{E}[g(\theta)\mid\cdot]}(P^{[k]})\geq\widetilde{R}_{\mathbb{E}[g(\theta)\mid\cdot]}(P)-2\omega_g(z)I(P)-2e^{-2kz^2}, \tag*{(33)} R E [ g ( θ ) ∣ ⋅ ] ( P [ k ] ) ≥ R E [ g ( θ ) ∣ ⋅ ] ( P ) − 2 ω g ( z ) I ( P ) − 2 e − 2 k z 2 , (33) R ~ f ( μ ) ( P [ k ] ) ≥ R ~ f ( μ ) ( P ) − 2 K z I ( P ) − 4 K e − 2 k z 2 , (34) \widetilde{R}_{f(\mu)}(P^{[k]})\geq\widetilde{R}_{f(\mu)}(P)-2KzI(P)-4Ke^{-2kz^2}, \tag*{(34)} R f ( μ ) ( P [ k ] ) ≥ R f ( μ ) ( P ) − 2 K z I ( P ) − 4 K e − 2 k z 2 , (34) R ~ μ ± a v ( P [ k ] ) ≥ R ~ μ ± a v ( P ) − ( 2 z + a z 2 ) I ( P ) − 2 ( 1 + a ) e − 2 k z 2 , (35) \widetilde{R}_{\mu\pm av}(P^{[k]})\geq\widetilde{R}_{\mu\pm av}(P)-(2z+az^2)I(P)-2(1+a)e^{-2kz^2}, \tag*{(35)} R μ ± a v ( P [ k ] ) ≥ R μ ± a v ( P ) − ( 2 z + a z 2 ) I ( P ) − 2 ( 1 + a ) e − 2 k z 2 , (35) R ~ h ( P [ k ] ) ≥ R ~ h ( P ) − ( 2 + a ) z I ( P ) − 2 ( 1 + a ) e − 2 k z 2 , (36) \widetilde{R}_{h}(P^{[k]})\geq\widetilde{R}_{h}(P)-(2+a)zI(P)-2(1+a)e^{-2kz^2}, \tag*{(36)} R h ( P [ k ] ) ≥ R h ( P ) − ( 2 + a ) z I ( P ) − 2 ( 1 + a ) e − 2 k z 2 , (36) where g g g maps [ 0 , 1 ] [0,1] [ 0 , 1 ] to [ 0 , 1 ] [0,1] [ 0 , 1 ] , f f f is K K K -Lipschitz, a ≥ 0 a\geq0 a ≥ 0 in (34), and h h h is (29) with 0 ≤ a ≤ 1 0\leq a\leq1 0 ≤ a ≤ 1 .
Proof. The policies agree off C C C . On C C C , the new selection coin is independent of the future conditional on F k \mathcal{F}_k F k , and Z = χ k 1 C = E [ 1 S ∣ F k ] Z=\chi_k1_C=\mathbb{E}[1_S\mid\mathcal{F}_k] Z = χ k 1 C = E [ 1 S ∣ F k ] . The replacement obtains E [ ψ k Z ] = E [ ψ k 1 S ] \mathbb{E}[\psi_kZ]=\mathbb{E}[\psi_k1_S] E [ ψ k Z ] = E [ ψ k 1 S ] , whereas P P P obtains E [ ψ τ 1 S ] \mathbb{E}[\psi_\tau1_S] E [ ψ τ 1 S ] on S S S . This proves the identity; selection probability and work satisfy (by construction).
For the bounds, let G = { ∣ θ ^ k − θ ∣ ≤ z } G=\{|\hat{\theta}_k-\theta|\leq z\} G = { ∣ θ ^ k − θ ∣ ≤ z } . Conditional on D D D , Hoeffding’s inequality gives P ( G c ) ≤ 2 e − 2 k z 2 \mathbb{P}(G^c)\leq2e^{-2kz^2} P ( G c ) ≤ 2 e − 2 k z 2 . Every F k \mathcal{F}_k F k -measurable X X X satisfies E [ X 1 S ] = E [ X Z ] \mathbb{E}[X1_S]=\mathbb{E}[XZ] E [ X 1 S ] = E [ X Z ] , and E Z = P ( S ) ≤ I ( P ) \mathbb{E}Z=\mathbb{P}(S)\leq I(P) E Z = P ( S ) ≤ I ( P ) . The event S S S is determined by time τ \tau τ .
Expected utility. For ψ t = E [ g ( θ ) ∣ F t ] \psi_t=\mathbb{E}[g(\theta)\mid\mathcal{F}_t] ψ t = E [ g ( θ ) ∣ F t ] , the tower property gives E [ ψ τ 1 S ] = E [ g ( θ ) 1 S ] \mathbb{E}[\psi_\tau1_S]=\mathbb{E}[g(\theta)1_S] E [ ψ τ 1 S ] = E [ g ( θ ) 1 S ] and E [ ψ k 1 S ] = E [ g ( θ ) Z ] \mathbb{E}[\psi_k1_S]=\mathbb{E}[g(\theta)Z] E [ ψ k 1 S ] = E [ g ( θ ) Z ] . Since E [ g ( θ ^ k ) ( 1 S − Z ) ] = 0 \mathbb{E}[g(\hat{\theta}_k)(1_S-Z)]=0 E [ g ( θ ^ k ) ( 1 S − Z )] = 0 ,
E [ ( ψ τ − ψ k ) 1 S ] = E [ ( g ( θ ) − g ( θ ^ k ) ) ( 1 S − Z ) ] . \mathbb{E}[(\psi_\tau-\psi_k)1_S]=\mathbb{E}[(g(\theta)-g(\hat{\theta}_k))(1_S-Z)]. E [( ψ τ − ψ k ) 1 S ] = E [( g ( θ ) − g ( θ ^ k )) ( 1 S − Z )] .
On G G G the integrand is at most ω g ( z ) ( 1 S + Z ) \omega_g(z)(1_S+Z) ω g ( z ) ( 1 S + Z ) in absolute value, and off G G G at most one. This gives (32). With g ( θ ) = θ g(\theta)=\theta g ( θ ) = θ , ψ t = μ t \psi_t=\mu_t ψ t = μ t and ω g ( z ) = z \omega_g(z)=z ω g ( z ) = z ; this is the bound in the proof of Corollary 4.3.
Lipschitz functions of the mean. Since ∣ μ τ − θ ^ k ∣ ≤ E [ ∣ θ − θ ^ k ∣ ∣ F τ ] |\mu_\tau-\hat{\theta}_k|\leq\mathbb{E}[|\theta-\hat{\theta}_k|\mid\mathcal{F}_\tau] ∣ μ τ − θ ^ k ∣ ≤ E [ ∣ θ − θ ^ k ∣ ∣ F τ ] and ∣ μ k − θ ^ k ∣ ≤ E [ ∣ θ − θ ^ k ∣ ∣ F k ] |\mu_k-\hat{\theta}_k|\leq\mathbb{E}[|\theta-\hat{\theta}_k|\mid\mathcal{F}_k] ∣ μ k − θ ^ k ∣ ≤ E [ ∣ θ − θ ^ k ∣ ∣ F k ] ,
E [ ∣ μ τ − μ k ∣ 1 S ] ≤ E [ ∣ θ − θ ^ k ∣ 1 S ] + E [ ∣ θ − θ ^ k ∣ Z ] ≤ 2 z P ( S ) + 2 P ( G c ) , \mathbb{E}[|\mu_\tau-\mu_k|1_S]\leq\mathbb{E}[|\theta-\hat{\theta}_k|1_S]+\mathbb{E}[|\theta-\hat{\theta}_k|Z]\leq2z\mathbb{P}(S)+2\mathbb{P}(G^c), E [ ∣ μ τ − μ k ∣ 1 S ] ≤ E [ ∣ θ − θ ^ k ∣ 1 S ] + E [ ∣ θ − θ ^ k ∣ Z ] ≤ 2 z P ( S ) + 2 P ( G c ) ,
which gives (33). Variance adjustments. The increment of μ + a v \mu+ av μ + a v is at most ( μ τ − μ k ) + a v τ (\mu_\tau- \mu_k) + av_\tau ( μ τ − μ k ) + a v τ , and that of μ − a v \mu- av μ − a v is at most ( μ τ − μ k ) + a v k (\mu_\tau- \mu_k) + av_k ( μ τ − μ k ) + a v k . The mean part is (33) with g ( θ ) = θ g(\theta) = \theta g ( θ ) = θ . By (32) , E [ v τ 1 S ] ≤ E [ ( θ − θ ^ k ) 2 1 S ] ≤ z 2 P ( S ) + P ( G c ) \mathbb{E}[v_\tau1_S] \le\mathbb{E}[(\theta- \hat{\theta}_k)^2 1_S] \le z^2 \mathbb{P}(S) + \mathbb{P}(G^c) E [ v τ 1 S ] ≤ E [( θ − θ ^ k ) 2 1 S ] ≤ z 2 P ( S ) + P ( G c ) , and likewise E [ v k 1 S ] = E [ v k Z ] ≤ E [ ( θ − θ ^ k ) 2 Z ] ≤ z 2 P ( S ) + P ( G c ) \mathbb{E}[v_k 1_S] = \mathbb{E}[v_k Z] \le\mathbb{E}[(\theta- \hat{\theta}_k)^2 Z] \le z^2 \mathbb{P}(S) + \mathbb{P}(G^c) E [ v k 1 S ] = E [ v k Z ] ≤ E [( θ − θ ^ k ) 2 Z ] ≤ z 2 P ( S ) + P ( G c ) .
Prediction score. The increment of h h h is ( μ τ − μ k ) − a σ τ 2 + a σ k 2 ≤ ( μ τ − μ k ) + a σ k 2 (\mu_\tau- \mu_k) - a\sigma_\tau^2 + a\sigma_k^2 \le(\mu_\tau- \mu_k) + a\sigma_k^2 ( μ τ − μ k ) − a σ τ 2 + a σ k 2 ≤ ( μ τ − μ k ) + a σ k 2 . By (32) and ( x − y ) 2 ≤ ∣ x − y ∣ (\sqrt{x} - \sqrt{y})^2 \le|x-y| ( x − y ) 2 ≤ ∣ x − y ∣ ,
E [ σ k 2 1 S ] = E [ σ k 2 Z ] ≤ E [ ( θ − θ ^ k ) 2 Z ] ≤ z P ( S ) + P ( G c ) . \mathbb{E}[\sigma_k^2 1_S] = \mathbb{E}[\sigma_k^2 Z] \le\mathbb{E}[(\sqrt{\theta} - \sqrt{\hat{\theta}_k})^2 Z] \le z\mathbb{P}(S) + \mathbb{P}(G^c). E [ σ k 2 1 S ] = E [ σ k 2 Z ] ≤ E [( θ − θ ^ k ) 2 Z ] ≤ z P ( S ) + P ( G c ) .
Adding the mean part gives (36) .
Summed over arms with ∑ i I ( P i ) ≤ 1 \sum_i I(P_i) \le1 ∑ i I ( P i ) ≤ 1 , the expected-utility bound (33) gives aggregate loss at most 2 ω g ( z ) + 2 n e − 2 k z 2 2\omega_g(z) + 2ne^{-2kz^2} 2 ω g ( z ) + 2 n e − 2 k z 2 . Choosing z z z with ω g ( z ) ≤ ϵ / 4 \omega_g(z) \le\epsilon/4 ω g ( z ) ≤ ϵ /4 and then k ≥ ( 2 z 2 ) − 1 log ( 4 n / ϵ ) k \ge(2z^2)^{-1}\log(4n/\epsilon) k ≥ ( 2 z 2 ) − 1 log ( 4 n / ϵ ) makes it at most ϵ \epsilon ϵ . The required depth depends on the modulus of g g g : for g ( x ) = x g(x) = \sqrt{x} g ( x ) = x , ω g ( z ) = z \omega_g(z) = \sqrt{z} ω g ( z ) = z , so z = ϵ 2 / 16 z = \epsilon^2/16 z = ϵ 2 /16 and k k k is of order ϵ − 4 log ( n / ϵ ) \epsilon^{-4}\log(n/\epsilon) ϵ − 4 log ( n / ϵ ) . In (34) –(36) the loss is a constant times z z z plus O ( n e − 2 k z 2 ) O(ne^{-2kz^2}) O ( n e − 2 k z 2 ) , so z z z of order ϵ \epsilon ϵ and k k k of order ϵ − 2 log ( n / ϵ ) \epsilon^{-2}\log(n/\epsilon) ϵ − 2 log ( n / ϵ ) suffice. In every case the cutoff depends on n n n only through log n \log n log n , as in § 4 . For the satisficing utility 1 { θ ≥ θ 0 } 1\{\theta\ge\theta_0\} 1 { θ ≥ θ 0 } with 0 < θ 0 ≤ 1 0 < \theta_0 \le1 0 < θ 0 ≤ 1 , ω g ( z ) = 1 \omega_g(z) = 1 ω g ( z ) = 1 for every z > 0 z > 0 z > 0 , and (33) gives no vanishing bound; that criterion is a martingale and is covered by Theorem 2.1.
A corollary for joint selection and prediction
We now combine Lemma 6.1 with Theorem 3.3 for the prediction score. Allocate at most T T T observations, then select an arm J J J and report a prediction x x x to maximize
E [ θ J − a ( θ J − x ) 2 ] . \mathbb{E}[\theta_J - a(\sqrt{\theta_J} - x)^2]. E [ θ J − a ( θ J − x ) 2 ] .
At the final history H H H , the best prediction for a chosen arm is x = E [ θ J ∣ H ] x = \mathbb{E}[\sqrt{\theta_J}\mid H] x = E [ θ J ∣ H ] . Optimizing also over J J J makes this objective exactly E [ max i h i ( H ) ] \mathbb{E}[\max_i h_i(H)] E [ max i h i ( H )] .
Let L P 2 , h \mathrm{LP}_{2,h} LP 2 , h be the two-constraint relaxation (2) with terminal coefficient h u h_u h u in place of r u r_u r u . It upper-bounds the optimal value of this joint decision problem.
Corollary 6.2 (Joint selection and prediction). Let 0 ≤ a ≤ 1 0 \le a \le1 0 ≤ a ≤ 1 , 0 < ϵ < 1 0 < \epsilon< 1 0 < ϵ < 1 , 0 < δ < f ⋆ 0 < \delta< f^\star 0 < δ < f ⋆ , and
k = min { T , ⌈ 18 ϵ − 2 log ( 8 n / ϵ ) ⌉ } . k = \min\{T,\lceil18\epsilon^{-2}\log(8n/\epsilon)\rceil\}. k = min { T , ⌈ 18 ϵ − 2 log ( 8 n / ϵ )⌉} . If γ < 1 \gamma< 1 γ < 1 in (14) , solving the depth-k k k relaxation with terminal values h u h_u h u , then applying Theorem 3.3 and using the Bayes prediction for the selected arm, gives
A L G h ≥ ( f ⋆ − δ ) ( 1 − γ ) [ L P 2 , h − ϵ ] + . (37) \mathrm{ALG}_h \ge(f^\star- \delta)(1-\gamma)[\mathrm{LP}_{2,h} - \epsilon]^+. \tag*{(37)} ALG h ≥ ( f ⋆ − δ ) ( 1 − γ ) [ LP 2 , h − ϵ ] + . (37) If L P 2 , h \mathrm{LP}_{2,h} LP 2 , h is bounded below by a positive constant and log n = o ( T ) \log n = o(T) log n = o ( T ) , choosing ϵ \epsilon ϵ and δ \delta δ that vanish sufficiently slowly gives a limiting approximation factor f ⋆ = 1 − e − 1 f^\star= 1-e^{-1} f ⋆ = 1 − e − 1 .
Proof. Apply the selection-preserving stopping operation to each optimal local policy of L P 2 , h \mathrm{LP}_{2,h} LP 2 , h . If k = T k = T k = T , no policy is shortened. Otherwise set z = ϵ / ( 2 ( 2 + a ) ) z = \epsilon/(2(2+a)) z = ϵ / ( 2 ( 2 + a )) in (36) and sum with ∑ i I ( P i ) ≤ 1 \sum_i I(P_i) \le1 ∑ i I ( P i ) ≤ 1 . The total loss is at most ( 2 + a ) z + 2 ( 1 + a ) n e − 2 k z 2 = ϵ / 2 + 2 ( 1 + a ) n e − 2 k z 2 (2+a)z + 2(1+a)ne^{-2kz^2} = \epsilon/2 + 2(1+a)ne^{-2kz^2} ( 2 + a ) z + 2 ( 1 + a ) n e − 2 k z 2 = ϵ /2 + 2 ( 1 + a ) n e − 2 k z 2 . Since 2 ( 2 + a ) 2 ≤ 18 2(2+a)^2 \le18 2 ( 2 + a ) 2 ≤ 18 , we have 2 k z 2 ≥ k ϵ 2 / 18 ≥ log ( 8 n / ϵ ) 2kz^2 \ge k\epsilon^2/18 \ge\log(8n/\epsilon) 2 k z 2 ≥ k ϵ 2 /18 ≥ log ( 8 n / ϵ ) , so the second term is at most 4 n ⋅ ϵ / ( 8 n ) = ϵ / 2 4n\cdot\epsilon/(8n) = \epsilon/2 4 n ⋅ ϵ / ( 8 n ) = ϵ /2 . By Lemma 6.1 the shortened policies satisfy both resource constraints, and their total utility is nonnegative because h u ≥ 0 h_u \ge0 h u ≥ 0 . The depth-k k k LP therefore has value at least [ L P 2 , h − ϵ ] + [\mathrm{LP}_{2,h}-\epsilon]^+ [ LP 2 , h − ϵ ] + , and Theorem 3.3 , which completes every admitted policy, gives (37) . For the limit, take δ = ϵ \delta= \epsilon δ = ϵ . Then k log ( 1 / δ ) = O ( ϵ − 2 ( log n + log ( 1 / ϵ ) ) log ( 1 / ϵ ) ) k\log(1/\delta) = O(\epsilon^{-2}(\log n+\log(1/\epsilon))\log(1/\epsilon)) k log ( 1/ δ ) = O ( ϵ − 2 ( log n + log ( 1/ ϵ )) log ( 1/ ϵ )) , which is o ( T ) o(T) o ( T ) when log n = o ( T ) \log n = o(T) log n = o ( T ) and ϵ → 0 \epsilon\to0 ϵ → 0 slowly enough. Hence γ → 0 \gamma\to0 γ → 0 , and dividing (37) by L P 2 , h \mathrm{LP}_{2,h} LP 2 , h proves the limit.
The same composition applies to the other criteria of Lemma 6.1 with nonnegative scores. For nonnegative Lipschitz functions of μ t \mu_t μ t and for μ t ± a v t \mu_t \pm av_t μ t ± a v t , with 0 ≤ a ≤ 1 0 \le a \le1 0 ≤ a ≤ 1 for the minus sign, only the constants in the choice of z z z change. For an expected utility with uniformly continuous g g g , choose z z z with ω g ( z ) ≤ ϵ / 4 \omega_g(z) \le\epsilon/4 ω g ( z ) ≤ ϵ /4 and k ≥ ( 2 z 2 ) − 1 log ( 4 n / ϵ ) k \ge(2z^2)^{-1}\log(4n/\epsilon) k ≥ ( 2 z 2 ) − 1 log ( 4 n / ϵ ) , as after Lemma 6.1. The depth then grows faster than ϵ − 2 \epsilon^{-2} ϵ − 2 when ω g ( z ) \omega_g(z) ω g ( z ) is not O ( z ) O(z) O ( z ) , but it still depends on n n n only through log n \log n log n . For a fixed such g g g , the limiting factor f ⋆ f^\star f ⋆ therefore holds when the corresponding LP value is bounded below by a positive constant and log n = o ( T ) \log n = o(T) log n = o ( T ) . The bound is additive in ϵ \epsilon ϵ ; we do not pursue a relative version, as in Lemma 4.2, for these criteria.
AI Use Statement
Multiple generative AI tools were used in this work for improving the writing and generating tight examples. We have reviewed all AI-assisted work.