Instance-dependent sequential limits as an exact information ledger

Akshay Balsubramani

cs.LGOct 30, 2026

Instance-dependent sequential limits as an exact information ledger

Authors: Akshay Balsubramani

Abstract

Instance-dependent limits for bandit regret, sequential tests, best-arm identification and Markov decision processes are proved by one chain. It runs from a divergence decomposition through data processing to a statistic, a testing step that turns a class guarantee into a requirement on the history, and optimization over alternatives and allocations. Only the first step is an identity. This work writes the chain as an exact ledger. By the chain rule, data processing loses exactly a conditional divergence, which vanishes for arms in natural exponential families at the per-arm counts and reward sums. A one-parameter family of martingale identities extends the decomposition to every tilt between two instances. The classical limits follow by relaxations with named defects. All defects but the asymptotic step's can be computed from an algorithm's own runs, the uniform quantification's only when the class guarantee is a number. On seven published sources, from movie ratings to engine replacement, the ledger locates the difference between standard algorithms and the classical limits. For identification among trained models and for Wald's test the largest term is usually the uniform quantification's.

Figures & tables

Result	Setting	Relaxations	Statement
Divergence decomposition [ 42 ]	any algorithm, stopping time	none (identity)	Thm. 3.1
Divergence decomposition on a Markov decision process [ 50 ]	any algorithm, stopping time	none (identity)	Prop. A.30
Fundamental inequality [ 24 ] ; transportation lemma [ 37 ]	statistic in $[0,1]$ , or an event	process	Lem. A.1 (b)
Le Cam, Bretagnolle–Huber [ 10 ] and Pinsker bounds [ 42 , Chapter 14]	two instances, fixed horizon	process , test ; Pinsker: process , binary	Prop. A.2 , Lem. A.3
Best-split bound [ 19 , 8 ]	an event, through its error sum	process , binary	Prop. A.4
Chernoff’s exponent and its converse [ 15 , 54 ]	two instances, fixed horizon, deterministic counts, mutually absolutely continuous laws	test	Lem. A.5

Table 1: Each of 34 results is an exact quantity or follows from one by named relaxations. Each row names a result and its source, its setting, the relaxations its proof applies (defined in Section 11 and listed in the order given there) and where the paper states it. Appendix C.8 proves the appendix statements.

Figure 1: On MovieLens arms, the asymptotic regret limit overstates what asymptotically optimal algorithms need at

T=20{,}000

. (a, b) Regret against

c^{\star}(\nu)\log t

, for the liked-or-not and the five-star instances. The

95\%

intervals have half-widths of at most

2\%

of the regret. UCB1 leaves both panels; it reaches

643

and

746

T=20{,}000

. On the five-star instance KL-UCB and Thompson sampling treat each arm as Bernoulli, so they are not asymptotically optimal there. They incur

1.5

2.4

times the limit at

T=20{,}000

. (c) The regret of each asymptotically optimal algorithm relative to the limit, split along the chain of Proposition A.6 with the normalized count and the closest alternatives. Terms above the line at

1

add to the regret ratio and terms below it subtract. Markers show the measured regret ratio, which the line at

1

plus the four signed terms reproduce exactly; its

95\%

interval is narrower than the marker.

Figure 2: Under adaptive play the path factor falls from the per-pull factor toward one as the horizon grows. (a) The path factor

D_{T}/(2C_{T}(1/2))

of KL-UCB and Thompson sampling on four one-armed reductions of MovieLens arms,

\xi=0.01

. The gray band marks the per-pull factors, which every fixed allocation attains. (b) At the same

\xi

, the expected pulls of the perturbed arm under the tilted law

Q_{1/2}

, relative to

P_{\nu}

. At

T=3{,}000

this ratio lies between

2.9

and

5.9

. All values are exact.

Figure 3: Among trained models, the largest term of the excess over the best-arm identification limit is the uniform quantification over the class, for every adaptive algorithm tested under a

\delta

-correct stopping threshold. Each bar splits the expected sample size relative to

T^{\star}(\nu)\mathrm{kl}(\delta,1-\delta)

into the uniform term, the process term of data processing to the recommendation and the allocation term; markers show the measured ratio to the limit with a

95\%

interval. The boundary between the uniform and process terms in each bar is set by an estimate whose logarithm is biased low (Section 12.3 ). Hatching marks the algorithm and its stopping threshold: TaS is Track-and-Stop, GK the threshold of Garivier and Kaufmann and KK that of Kaufmann and Koolen. Bars that leave the axis show their value in white. Cross-fitting, in which the most confusing alternative is chosen on each half of the runs and evaluated on the other half, makes the allocation estimate run low where two alternatives are about equally confusing. The uniform and process terms together then run high by the same amount. A negative estimate is drawn as zero. Round-robin sampling reaches

11

88

times the limit and is omitted. Track-and-Stop with the heuristic threshold at

\delta=10^{-4}

on the CIFAR-10 instance is omitted too: one of its

400

runs had not stopped after

237\,T^{\star}(\nu)

pulls.

Figure 4: From

\delta=10^{-1}

10^{-6}

the information that the identification algorithms collect beyond

\mathrm{kl}(\delta,1-\delta)

changes little, while

\mathrm{kl}(\delta,1-\delta)

itself grows nearly

8

-fold. In each row the excess of the expected sample size over the limit,

\mathbb{E}_{\nu}[\tau]/T^{\star}(\nu)-\mathrm{kl}(\delta,1-\delta)

, is split into two terms in nats. The uniform and process terms together are

\langle n,k(\lambda^{\star})\rangle-\mathrm{kl}(\delta,1-\delta)

, the information collected against the most confusing alternative

\lambda^{\star}

beyond

\mathrm{kl}(\delta,1-\delta)

(two-colored markers). The allocation term is

\mathbb{E}_{\nu}[\tau]/T^{\star}(\nu)-\langle n,k(\lambda^{\star})\rangle

(green markers). The value of

\mathrm{kl}(\delta,1-\delta)

is marked by the dotted lines. The best-arm rows are the CIFAR-10 and MMLU instances of Figure 3 and the oat variety trial of Appendix B.7 . The top-

3

rows use

T^{\star}_{m}(\nu)

with

m=3

(Appendices B.6 and B.7 ). TaS is Track-and-Stop. KK marks the threshold of Kaufmann and Koolen. Every other row uses the first

\delta

-correct threshold: that of Garivier and Kaufmann on CIFAR-10 and MMLU, with a union over the swap pairs for the top

3

, and a Gaussian calibration of Kaufmann and Koolen on the oat trial. Under these thresholds the uniform -plus- process term is

14

22

nats at both risks, and under KK it is

36

45

nats. Between the two risks it changes by at most

5.4

nats, while

\mathrm{kl}(\delta,1-\delta)

grows from

1.8

13.8

nats. The allocation term is at most

10.3

nats, below every uniform -plus- process term, except for Track-and-Stop on the oat trial, where it is

21

88

nats. The alternative

\lambda^{\star}

is chosen on one half of the runs and evaluated on the other. The allocation term is nonnegative. Its cross-fitted estimate runs low where two alternatives are about equally confusing. The uniform -plus- process estimate then runs high by the same amount. For T3C on MMLU the allocation estimate is

-0.9

and

-0.8

nats at the two risks, against

0.03

and

0.17

nats when

\lambda^{\star}

is chosen and evaluated on all runs. A negative estimate is drawn as zero, as in Figure 3 , and every interval is cut at zero. The axis is linear between

0

and

1

nat and logarithmic above. Error bars are

95\%

percentile bootstrap intervals, with the runs resampled within each half and

\lambda^{\star}

chosen again in every resample; where none shows, the interval is narrower than the marker. Round-robin sampling, whose allocation term is

58

249

nats, is omitted. So is Track-and-Stop on the CIFAR-10 top-

3

problem, where

7

of its

200

runs at each risk reached the step cap.

Figure 5: Both the sequential tests and Chernoff’s rule run above their classical limits, by

2\%

62\%

for the tests and by

1.3

2.6

times for Chernoff’s rule next to the Proficient cut. (a, b) The sequential A/B tests on both metrics of the Hillstrom experiment. In each bar the expected sample size relative to the limit is split into the uniform term and the process term, computed from

\mathbb{E}_{\nu}[L_{\tau}]

. For the mixture test the

\log 2

of its two-sided decision is drawn apart from the rest of the process term, and its uniform term uses the error rate at the barycentre null of Appendix B.8 . For Wald’s SPRT the uniform term is the largest part of the excess at every

\alpha

and on both metrics. For the mixture SPRT most of the excess is the process term. Markers show the measured ratio to the limit, computed from

\mathbb{E}_{\nu}[\tau]

, with a

95\%

interval from the normal approximation. The two agree in expectation by Theorem 3.1 , and in the data their largest difference is

1.9

times its standard error. Solid bars show the purchase rate and hatched bars the site-visit rate. Panels (a) and (b) have different vertical scales. (c, d) Sequential design on NAEP science items (Section 12.5 ), with every rule at the

\delta

-correct threshold. (c) Two achievement levels, the state just above the Proficient cut (scale score

179

): the expected test length relative to the limit

T^{\star}_{\Theta}(\nu)\,\mathrm{kl}(\delta,1-\delta)

(solid) and relative to the bound at the rule’s own error rates (dashed), for Chernoff’s rule and maximum Fisher information at the cut. Chernoff’s rule sits at most

15\%

above that bound at every risk. (d) At

\delta=10^{-4}

, Chernoff’s expected test length relative to the limit at the six states next to a cut, split into the uniform , process and allocation terms. The uniform term is the largest of the three at every state. At the three-level state of score

179

the split rests on change-of-measure weights with effective sample sizes of

31

and

14

in the two halves of the runs. Error bars in (c, d) are

95\%

bootstrap intervals over runs; where none shows, the interval is narrower than the marker.

Figure 6: On both models the asymptotic regret limit overstates what IMED-RL needs at the horizons reached. (a–c) The machine-maintenance problem of Section 12.6 . (d–f) Rust’s engine-replacement model, fitted to fleet data (Appendix B.11 ). (a, d) Regret in count form,

\sum_{x,a}\mathbb{E}_{\nu}[N_{x,a}(t)]\,\Delta_{x,a}

, with

95\%

intervals, against

c^{\star}_{\Phi}(\nu)\log t

. In (a) UCRL2 exceeds the limit by a factor of

83

T=10^{5}

. The gray lines in (d) are the exact regret of two policies that never learn. The one that replaces from bin

16

crosses above the limit at

t=7.9\times 10^{5}

, and the one that keeps until forced, which PSRL and UCRL2 follow, at

t=1.8\times 10^{5}

. (b, e) The transported fraction

I_{x,a}(t)/\log t

of each suboptimal pair with finite

\mathcal{K}_{\inf}(x,a)

, with

95\%

intervals: doing nothing at major deterioration in (b), and keeping the engine in bin

15

16

in (e), where UCRL2 coincides with PSRL. (c, f) The regret relative to the limit at the last horizon, split along the chain of Proposition A.31 with the closest alternative. In (c) its margin is

\xi_{\Delta}=0.02

of the Bellman gap, and the statistic is the fraction of visits to major deterioration at which nothing is done. UCRL2 is omitted from (c): its ratio of

84

there leaves the shared scale. The split in (c) comes from a further

1{,}000

runs per algorithm, on which the regret ratio of PSRL is

0.44

, against

0.42

in (a). In (f) the split is that of IMED-RL, at the margins

\xi_{\Delta}=0.02

and

1

. The statistic of each pair is the fraction of visits to its bin at which the engine is kept. Terms above the line at

1

add to the ratio and terms below it subtract. Markers show the measured regret ratio, which the line at

1

plus the five signed terms reproduce exactly, with its

95\%

interval; where no bar shows, the interval is narrower than the marker. Panels (c) and (f) share one scale.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning	Defined in
Instances and histories
$\nu$ , $\lambda$	the instance $(\nu_{a})_{a\in[K]}$ and an alternative instance	Sec. 2
$[K]$ , $a$ , $b$	the arms; $b$ a suboptimal arm singled out	Sec. 2 , 2.1
$\mu_{a}(\lambda)$ , $\mu_{a}$	mean of arm $a$ under $\lambda$ ; under $\nu$	Sec. 2.1
$\mu^{\star}$ , $a^{\star}$	optimal mean; an optimal arm	Sec. 2.1
$\Delta_{a}(\lambda)$ , $\Delta_{a}$	gap of arm $a$ under $\lambda$ ; under $\nu$	Sec. 2.1

Appendix

Table 2: Each symbol of the paper names one object, defined at the site listed. The groups follow the parts of the paper. Writing

\lambda

as a subscript or an argument gives the same object under the alternative.

Figure 7: On exact one-armed reductions at

\xi=0.01

, the law of the pull count keeps at least

82\%

D_{T}

T=3{,}000

, while the regret form of the finite-horizon regret bound certifies none of it. (a, b) Lower bounds on

D_{T}=\mathbb{E}_{\nu}[N_{b}(T)]\,\mathrm{KL}(\nu_{b}\,\|\,\lambda_{b})

, divided by

D_{T}

, at

\xi=0.01

. Each color is one bound, named in the key below the panels. The three regret-bound curves are the error-sum and regret forms of Proposition A.7 and its class-level form. The markers show

N_{b}(t)

together with the round of the last pull of arm

b

. Lines and markers are medians over the four arms, and the bars right of the last round give the range at

T=3{,}000

. The dotted line is the asymptotic requirement

\log t\,\mathrm{KL}(\nu_{b}\,\|\,\lambda_{b})/d(\mu_{b},\mu^{\star})

, which is not a bound at a finite horizon. A value below zero certifies nothing. (c) Four of the same bounds at

\xi=0.03

, as medians, with KL-UCB solid and Thompson sampling dashed. (d) The bound of Corollary A.8 at the best of

\xi_{\Delta}\in\{0.1,0.5,1\}

, with

\Gamma T^{p}

replaced by the largest measured regret over seven instances of the neighborhood, over the measured regret on Gaussian reductions with the same standardized gaps. Gaussian UCB is solid and Gaussian Thompson sampling dashed. Lines are medians and bands ranges over the four arms. Markers give each arm’s value at

T=3{,}000

with its

95\%

percentile bootstrap interval, which is narrower than the marker. Values in (a) to (c) are exact.

threshold	sum of the two terms	low reading in the control
Garivier and Kaufmann	$14.6$ – $20.8$	$0.07$ – $1.98$
Kaufmann and Koolen	$38.6$ – $45.0$	$1.07$ – $1.32$
heuristic	$4.0$ – $6.5$	$0.15$ – $0.64$

Appendix

Table 3: The sum of the uniform and process terms of Figure 3 needs no estimate, while the estimate that splits them reads low in the exact control. Each row gives ranges in nats over the instances and risks at one stopping threshold. Track-and-Stop runs with all three thresholds; T3C with the threshold of Garivier and Kaufmann only. The columns give the sum of the two terms and the amount by which the estimate of

\log P_{\lambda^{\star}}(E)

reads low in the control reductions with an under-sampled challenger, at the same threshold and risks. At the heuristic threshold the sum covers nine configurations, since one run of the omitted configuration did not stop.

Figure 8: At the tests’ own error rates the expected sample size exceeds the bound by at most

0.8\%

for Wald’s SPRT and

9.1\%

for the mixture SPRT, against up to

14\%

and

62\%

over their limits. Each marker divides the expected sample size

\mathbb{E}_{\nu}[\tau]

on one metric of the Hillstrom experiment by one of two lower bounds: the bound at the test’s own error rates (blue) or the limit at the nominal level (vermillion). Filled markers and solid lines show the purchase rate, and open markers and dashed lines the site-visit rate. (a) Wald’s SPRT, with the bound

\mathrm{kl}(1-\beta^{\prime},\alpha^{\prime})/\mathrm{kl}(p_{1},p_{0})

of Proposition A.13 at the exact realized error rates and the limit

\mathrm{kl}(1-\alpha,\alpha)/\mathrm{kl}(p_{1},p_{0})

. All values are exact. The inset magnifies the ratios to the bound at the realized error rates over the same five levels. (b) The mixture SPRT, with the bound

\mathrm{kl}(P_{\nu}(E_{+}),\alpha^{\prime}_{+,\mathrm{cap}})/\mathcal{K}_{\inf}(\nu,\mathcal{H}_{0})

at its one-sided rejection rate before the cap,

\alpha^{\prime}_{+,\mathrm{cap}}

, at the barycentre null, and the limit

\log(1/\alpha)/\mathcal{K}_{\inf}(\nu,\mathcal{H}_{0})

. Bars give

95\%

intervals. At

\alpha=10^{-4}

on the purchase metric no direct value of

\alpha^{\prime}_{+,\mathrm{cap}}

exists, and the bound is not drawn.

Figure 9: The exact top-

m

limit is

1.65

1.72

times the explicit bound. Under the union threshold of Garivier and Kaufmann the adaptive algorithms that stop every run cost

2.2

2.7

times the limit at

\delta=10^{-6}

. Expected sample sizes relative to the limit

T^{\star}_{m}(\nu)\mathrm{kl}(\delta,1-\delta)

, with

95\%

intervals, most of them narrower than the markers. Dashed lines mark the explicit bound of Proposition A.21 . GK and KK are the thresholds of Garivier and Kaufmann and of Kaufmann and Koolen with a union over the swap pairs. (a) The MMLU instance with

m=3

; diamonds mark the own stopping rules of LUCB and KL-LUCB at

\delta=0.1

. (b) The four problems at

\delta=10^{-1}

(open markers) and

10^{-6}

(filled). On the CIFAR-10 instance some runs of Track-and-Stop reach the step cap at each risk, so its markers are lower bounds. (c) At

\delta=0.1

on the MMLU instance with

m=3

, the expected sample size split into the limit, the uniform -plus- process term and the allocation term, which add up to the measured ratio. In (c) TaS is Track-and-Stop. Every bar except the two own stopping rules uses the GK threshold.

Figure 10: On an oat variety trial, allocation accounts for most of Track-and-Stop’s excess over the identification limit and for at most

4\%

of T3C’s. (a) Best-arm identification under the first

\delta

-correct threshold. The expected sample size of T3C and of Track-and-Stop is divided by the limit

T^{\star}(\nu)\mathrm{kl}(\delta,1-\delta)

(filled markers, solid) and by

T^{\star}(\nu)D_{\tau}

, with

D_{\tau}

taken at

\lambda^{\star}

(open, dashed). The second ratio equals

T(\bar{w})/T^{\star}(\nu)

. Neither ratio uses an estimate of

P_{\lambda^{\star}}(E)

. (b) At

\delta=10^{-2}

, the excess over the limit in nats, split into

\textsc{uniform}+\textsc{process}

(open) and allocation (filled). Every row uses the first threshold except the one marked as using the second. Round-robin sampling, whose allocation term is

87

170

nats at this risk, is omitted. (c) The affinity bound of Theorem 7.1 (filled) and the Bretagnolle–Huber bound (open) against the minimum error sum

1-\mathrm{TV}(P_{\nu},P_{\lambda})

, on the

16

one-armed reductions at

T=3{,}000

and on four fixed allocations (black). (d) On SD Titan at

\xi_{\Delta}=1

, four lower bounds as a share of

D_{T}

: the error-sum form of Proposition A.7 (circles), its value with both probabilities at their one-sided

95\%

upper bounds where no run crossed

T/2

(open triangles), the regret form (dashed) and the count of Corollary A.8 (dotted). Colors in (d) follow (c). Intervals are

95\%

bootstrap intervals in (a, b), delta-method intervals in (c) and exact binomial intervals in (d).

Figure 11: At the Basic state where the maximin allocation mixes two items, Chernoff’s rule sits

25\%

31\%

above the bound at its own error rates, while maximum information at the cut sits

70\%

74\%

above its bound. Three achievement levels, the Basic state just below the Proficient cut (scale score

161

). The expected test length is drawn relative to the limit

T^{\star}_{\Theta}(\nu)\,\mathrm{kl}(\delta,1-\delta)

(solid) and relative to the bound at the rule’s own error rates (dashed), for three item-selection rules at the

\delta

-correct threshold. The three rules need

1.7

4.6

times the limit. Chernoff’s rule and maximum information at the cut keep their colors of Figure 5 (c). Error bars are

95\%

bootstrap intervals over runs; where none shows, the interval is narrower than the marker.

Bandit Learning

See all 57 papers

Aug 15, 2026

Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

Regret minimization (RM) and best-arm identification (BAI) are two fundamental objectives in multi-armed bandits. Among regret-minimizing algorithms,

1/2

-Tsallis-INF is a canonical best-of-both-worlds FTRL algorithm: it achieves logarithmic pseudo-regret in stochastic bandits while retaining minimax-optimal regret in adversarial bandits, without knowing the environment in advance. This raises a natural question: can the same algorithm, without additional exploration, also identify the best arm reliably? We study this question in stochastic bandits by analyzing the failure probability

\operatorname{Err}_t

, defined as the probability that the empirical best arm determined by the cumulative importance-weighted loss estimates of 1/2-Tsallis-INF differs from the true optimal arm. The main difficulty is that, at the logarithmic-regret scale, suboptimal arms are sampled with probability heuristically of order

1/t

. Consequently, importance weighting causes the cumulative estimator to fluctuate on the same linear scale as its mean separation. To overcome this obstacle, guided by a diffusion toy model, we construct a Lyapunov function for the gap process between the estimated cumulative loss of the optimal arm and that of the best competing arm. This leads to polynomial upper bounds on

\operatorname{Err}_t

: for learning rate

η_t=α/\sqrt t

\operatorname{Err}_t

decays at rate

t^{-2+α^2μ_{i_*}/4+ρ}

for any

ρ>0

, where

μ_{i_*}

denotes the mean loss of the true optimal arm. We also establish a lower bound

Ω(t^{-2-\varepsilon})

for any

\varepsilon>0

, showing that the exponent

2

is essentially tight.

Jingxin Zhan, Yuze Han, Zhihua Zhang

School of Mathematical Sciences, Peking University · Center for Applied Statistics and School of Statistics, Renmin University of China

Multi-Armed Bandits Best-Arm Identification

Ask PDF

Jul 13, 2026

Fundamental Limitations of Fixed-Budget Best-Arm Identification

In fixed-budget best-arm identification, also known as ranking and selection, an algorithm has a sampling budget to distribute across

K

arms. Each sample provides noisy feedback about that arm's mean, and the goal is to identify the arm with the largest mean. A common performance benchmark is the static oracle: a non-adaptive strategy that knows the means in advance and chooses fixed sampling proportions to maximize the exponential decay rate of the probability of incorrect identification. Several adaptive algorithms have been constructed such that their sampling proportions converge to the static oracle proportions. However, it has remained open whether any algorithm could match the static oracle's error decay rate uniformly across all problem instances. We answer this in the negative. For any

K\ge 3

and for rewards drawn from any one-parameter natural exponential family, we show that for any algorithm, there is at least one instance where the error decay rate is at most

\left(1 + \frac{\log(K)}{8}\right)^{-1}

times that of the static oracle. This also answers the open question posed by Qin (2022), showing that fixed-budget best-arm identification does not admit a complexity.

Motti Goldberger

Yale University

Multi-Armed Bandits Best-Arm Identification Information-Theoretic Lower Bounds

Ask PDF

Mar 18, 2026

Multi-Armed Sequential Hypothesis Testing by Betting

We consider a variant of sequential testing by betting where, at each time step, the statistician is presented with multiple data sources (arms) and obtains data by choosing one of the arms. We consider the composite global null hypothesis

\mathscr{P}

that all arms are null in a certain sense (e.g. all dosages of a treatment are ineffective) and we are interested in rejecting

\mathscr{P}

in favor of a composite alternative

\mathscr{Q}

where at least one arm is non-null (e.g. there exists an effective treatment dosage). We posit an optimality desideratum that we describe informally as follows: even if several arms are non-null, we seek

e

-processes and sequential tests whose performance are as strong as the ones that have oracle knowledge about which arm generates the most evidence against

\mathscr{P}

. Formally, we generalize notions of log-optimality and expected rejection time optimality to more than one arm, obtaining matching lower and upper bounds for both. A key technical device in this optimality analysis is a modified upper-confidence-bound-like algorithm for unobservable but sufficiently "estimable" rewards. In the design of this algorithm, we derive nonasymptotic concentration inequalities for optimal wealth growth rates in the sense of Kelly [1956]. These may be of independent interest.

Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. Jordan

University of California, Berkeley · École Normale Supérieure & Inria, Paris

Sequential Hypothesis Testing Statistical Hypothesis Testing Multi-Armed Bandits

Ask PDF

Abstract

Bandit Learning

Explore similar work

Does 1/2-Tsallis-INF Also Work Well for Best-Arm Identification?

Fundamental Limitations of Fixed-Budget Best-Arm Identification

Multi-Armed Sequential Hypothesis Testing by Betting