cs.LGOct 30, 2026
SaveInstance-dependent sequential limits as an exact information ledger
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 , 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 . (a, b) Regret against , for the liked-or-not and the five-star instances. The intervals have half-widths of at most of the regret. UCB1 leaves both panels; it reaches and at . On the five-star instance KL-UCB and Thompson sampling treat each arm as Bernoulli, so they are not asymptotically optimal there. They incur to times the limit at . (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 add to the regret ratio and terms below it subtract. Markers show the measured regret ratio, which the line at plus the four signed terms reproduce exactly; its 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 of KL-UCB and Thompson sampling on four one-armed reductions of MovieLens arms, . The gray band marks the per-pull factors, which every fixed allocation attains. (b) At the same , the expected pulls of the perturbed arm under the tilted law , relative to . At this ratio lies between and . 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 -correct stopping threshold. Each bar splits the expected sample size relative to 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 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 to times the limit and is omitted. Track-and-Stop with the heuristic threshold at on the CIFAR-10 instance is omitted too: one of its runs had not stopped after pulls.
Figure 4: From to the information that the identification algorithms collect beyond changes little, while itself grows nearly -fold. In each row the excess of the expected sample size over the limit, , is split into two terms in nats. The uniform and process terms together are , the information collected against the most confusing alternative beyond (two-colored markers). The allocation term is (green markers). The value of 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- rows use with (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 -correct threshold: that of Garivier and Kaufmann on CIFAR-10 and MMLU, with a union over the swap pairs for the top , and a Gaussian calibration of Kaufmann and Koolen on the oat trial. Under these thresholds the uniform -plus- process term is to nats at both risks, and under KK it is to nats. Between the two risks it changes by at most nats, while grows from to nats. The allocation term is at most nats, below every uniform -plus- process term, except for Track-and-Stop on the oat trial, where it is to nats. The alternative 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 and nats at the two risks, against and nats when 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 and nat and logarithmic above. Error bars are percentile bootstrap intervals, with the runs resampled within each half and chosen again in every resample; where none shows, the interval is narrower than the marker. Round-robin sampling, whose allocation term is to nats, is omitted. So is Track-and-Stop on the CIFAR-10 top- problem, where of its runs at each risk reached the step cap.
Figure 5: Both the sequential tests and Chernoff’s rule run above their classical limits, by to for the tests and by to 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 . For the mixture test the 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 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 , with a interval from the normal approximation. The two agree in expectation by Theorem 3.1 , and in the data their largest difference is 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 -correct threshold. (c) Two achievement levels, the state just above the Proficient cut (scale score ): the expected test length relative to the limit (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 above that bound at every risk. (d) At , 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 the split rests on change-of-measure weights with effective sample sizes of and in the two halves of the runs. Error bars in (c, d) are 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, , with intervals, against . In (a) UCRL2 exceeds the limit by a factor of at . The gray lines in (d) are the exact regret of two policies that never learn. The one that replaces from bin crosses above the limit at , and the one that keeps until forced, which PSRL and UCRL2 follow, at . (b, e) The transported fraction of each suboptimal pair with finite , with intervals: doing nothing at major deterioration in (b), and keeping the engine in bin or 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 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 there leaves the shared scale. The split in (c) comes from a further runs per algorithm, on which the regret ratio of PSRL is , against in (a). In (f) the split is that of IMED-RL, at the margins and . The statistic of each pair is the fraction of visits to its bin at which the engine is kept. Terms above the line at add to the ratio and terms below it subtract. Markers show the measured regret ratio, which the line at plus the five signed terms reproduce exactly, with its 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 | ||
| , | the instance and an alternative instance | Sec. 2 |
| , , | the arms; a suboptimal arm singled out | Sec. 2 , 2.1 |
| , | mean of arm under ; under | Sec. 2.1 |
| , | optimal mean; an optimal arm | Sec. 2.1 |
| , | gap of arm under ; under | Sec. 2.1 |
Table 2: Each symbol of the paper names one object, defined at the site listed. The groups follow the parts of the paper. Writing as a subscript or an argument gives the same object under the alternative.
Figure 7: On exact one-armed reductions at , the law of the pull count keeps at least of at , while the regret form of the finite-horizon regret bound certifies none of it. (a, b) Lower bounds on , divided by , at . 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 together with the round of the last pull of arm . Lines and markers are medians over the four arms, and the bars right of the last round give the range at . The dotted line is the asymptotic requirement , which is not a bound at a finite horizon. A value below zero certifies nothing. (c) Four of the same bounds at , as medians, with KL-UCB solid and Thompson sampling dashed. (d) The bound of Corollary A.8 at the best of , with 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 with its 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 | – | – |
| Kaufmann and Koolen | – | – |
| heuristic | – | – |
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 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 for Wald’s SPRT and for the mixture SPRT, against up to and over their limits. Each marker divides the expected sample size 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 of Proposition A.13 at the exact realized error rates and the limit . 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 at its one-sided rejection rate before the cap, , at the barycentre null, and the limit . Bars give intervals. At on the purchase metric no direct value of exists, and the bound is not drawn.
Figure 9: The exact top- limit is to times the explicit bound. Under the union threshold of Garivier and Kaufmann the adaptive algorithms that stop every run cost to times the limit at . Expected sample sizes relative to the limit , with 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 ; diamonds mark the own stopping rules of LUCB and KL-LUCB at . (b) The four problems at (open markers) and (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 on the MMLU instance with , 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 of T3C’s. (a) Best-arm identification under the first -correct threshold. The expected sample size of T3C and of Track-and-Stop is divided by the limit (filled markers, solid) and by , with taken at (open, dashed). The second ratio equals . Neither ratio uses an estimate of . (b) At , the excess over the limit in nats, split into (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 to 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 , on the one-armed reductions at and on four fixed allocations (black). (d) On SD Titan at , four lower bounds as a share of : the error-sum form of Proposition A.7 (circles), its value with both probabilities at their one-sided upper bounds where no run crossed (open triangles), the regret form (dashed) and the count of Corollary A.8 (dotted). Colors in (d) follow (c). Intervals are 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 to above the bound at its own error rates, while maximum information at the cut sits to above its bound. Three achievement levels, the Basic state just below the Proficient cut (scale score ). The expected test length is drawn relative to the limit (solid) and relative to the bound at the rule’s own error rates (dashed), for three item-selection rules at the -correct threshold. The three rules need to times the limit. Chernoff’s rule and maximum information at the cut keep their colors of Figure 5 (c). Error bars are bootstrap intervals over runs; where none shows, the interval is narrower than the marker.