The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs

Rui Wang

cs.LGOct 17, 2026

The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs

Authors: Rui Wang

Organizations: Microsoft Vancouver, BC, Canada

Abstract

Before a new policy replaces a deployed one, we often want a certificate, computed from logged episodes, that it is better. We ask how many episodes such a certificate needs when the logging policy is known but history-dependent, and the error probability must stay below $δ$ in every environment consistent with the logs. The answer is an exponent $K^\star$ : the smallest KL divergence from the logged law to a law with the same logged action probabilities under which the target does not improve. No sound certifier stops in fewer than $\log(1/δ)/K^\star$ expected episodes, at any $δ$ , and whenever $0<K^\star<\infty$ a plug-in Kelly certifier attains this rate to first order as $δ\to0$ . Coverage, computed by one backward induction, decides whether certification is impossible ( $K^\star=0$ ), possible at a finite rate, or possible in a constant number of episodes ( $K^\star=\infty$ ). By convex duality, the optimal certificate bets on the importance-weighted advantage and also places fair bets on the logged actions, so doubly robust control variates act as hedges rather than estimators. As a consequence, no choice of off-policy estimator changes $K^\star$ , a coverage ceiling explains the curse of memory, and structural assumptions can be priced in exponent units. A cushion certifier extends the approach to trees too large to enumerate. In experiments the plug-in's median stopping time is 1.13-1.43x the lower bound on memory tasks, 1.13-1.51x on Tiger ( $H\le5$ ) and 1.17-1.64x on random trees. The best scalar betting baselines need up to 2.65x (memory) and 4.1x (Tiger) the plug-in's episodes; only on a few shallow random trees is a doubly robust bet faster, by at most 18%.

Figures & tables

Figure 1: Setting and main object. (a) A logged outcome tree (the memory task with

d=0

). Environment nodes (circles) have kernels left free by the null; at action nodes (squares) the logger

\mu

is known. Thick edges are the actions of the target

\pi

. The grey leaf has zero logged probability but remains in the outcome space

\mathcal{J}

, so every certificate must stay nonnegative on it. (b) Schematic, not to scale, of Theorem 4.3 .

\mathcal{Q}

is the set of action-neutral laws and

\mathcal{Q}_{0}

its part with

\mathbb{E}_{q}X\leq 0

K^{\star}(P)

is the divergence from

P

\mathcal{Q}_{0}

, attained at

q^{\star}

, and the optimal certificate

P/q^{\star}

is affine in the payoff

X

and the fair bets

B

. The scalar exponent

K_{\mathrm{scal}}

is the divergence to the larger set

\{q:\mathbb{E}_{q}X\leq 0\}

, so

K_{\mathrm{scal}}\leq K^{\star}

instance	CV-Kelly	hedged	scalar Kelly	mixture (MC)	$K^{\star}/K_{\mathrm{scal}}$
cue $d=0$ , $p=0.2$	1.16 [1.08, 1.21]	1.13 [1.03, 1.18]	1.72 [1.55, 1.85]	1.39 [1.28, 1.51]	1.57
cue $d=1$ , $p=0.2$	1.10 [1.00, 1.19]	1.21 [1.08, 1.31]	2.39 [2.17, 2.68]	21.8 [9.4, $\infty$ ]	2.47
random, depth 2	1.10 [0.98, 1.25]	1.08 [0.93, 1.20]	3.19 [2.84, 3.46]	—	2.70
Tiger $H=3$ , $\epsilon=0.2$	1.17 [1.05, 1.29]	1.02 [0.92, 1.12]	4.22 [3.74, 4.64]	—	4.05

Table 1: Slope of the median stopping time against

\log(1/\delta)

, in units of

1/K^{\star}

(theory:

1

for CV-Kelly and the hedge by its plug-in component,

K^{\star}/K_{\mathrm{scal}}

for scalar Kelly; no finite-sample bound for the MC mixture). Brackets are 95% percentile-bootstrap intervals over 2000 resamples of the 100 runs per

\delta

Figure 2: Median stopping time against

\log(1/\delta)

for

\delta

from

10^{-8}

10^{-2}

; 100 runs per point, bars are 95% order-statistic intervals, and points are offset horizontally for legibility. Dashed: the lower bound

\log(1/\delta)/K^{\star}

on the expected stopping time ( Theorem 4.1 ). Dotted:

\log(1/\delta)/K_{\mathrm{scal}}

, the asymptote of scalar Kelly. The plotted mixture uses 300 fixed sampled points, not the exact integral in Theorem 5.5 . Arrows: median above the plotted range or censored at

30\log(1/\delta)/K^{\star}

; at

d=1

the mixture certified in only 47–62% of runs. Fitted slopes are in Table 1 .

instance	$\frac{\log(1/\delta)}{K^{\star}}$	CV-Kelly	hedged	scalar	WSR-PDIS	WSR-DR	mixture	DR fit	DR orc	LS	EB	HCOPE
cue $d{=}0$ $p{=}0.2$	25	31	37	52	57.5	114.5	47.5	72.5	83	1024	512	1024 (.91)
cue $d{=}0$ $p{=}0.02$	34	49	49	51.5	73	1337 (.98)	99.5 (.90)	582.5	862	1024	$\infty$	2048
cue $d{=}1$ $p{=}0.2$	60	75.5	86	182	182.5	252.5	703.5 (.63)	159	179	1024	2048	2048 (.87)
cue $d{=}1$ $p{=}0.02$	70	79.5	103.5	210.5	222	2168	347 (.79)	772	1726	2048	$\infty$	4096
cue $d{=}2$ $p{=}0.2$	151	200	194.5	441.5	391.5	545.5	$\infty$	387	377	2048	4096	4096
cue $d{=}2$ $p{=}0.02$	178	239	242.5	507.5	550	2852	$\infty$	908.5	3429	2048	$\infty$	4096

Table 2: Median stopping time (episodes) at

\delta=10^{-3}

, 100 runs per cell.

\log(1/\delta)/K^{\star}

is the lower bound of Theorem 4.1 (i) on the expected stopping time of every

\delta

-sound certifier. WSR: the betting confidence sequence of Waudby-Smith and Ramdas (2024) on the PDIS or DR payoff (hedged aGRAPA/ONS bettor). The mixture column uses 300 sampled points. A number in parentheses is the certification rate when below one.

Figure 3: Median stopping time at

\delta=10^{-3}

divided by the lower bound

\log(1/\delta)/K^{\star}

(dashed line at 1); 100 runs per cell. The mixture uses 300 sampled points. Horizontal bars are 95% intervals for the median, truncated at the censoring level

60\log(1/\delta)/K^{\star}

. Points in the shaded

\infty

column: the median run was censored. Circled points: certified in fewer than 100% of runs. (a) The instances of Table 2 . (b) The Tiger POMDP at

\epsilon=0.2

( Table 5 ).

	median $/$ lower bound			median $/$ CV-Kelly
certifier	min	median	max	min	median	max	faster	finite
CV-Kelly	1.17	1.38	1.64	—	—	—	—	24
scalar Kelly	1.52	2.80	4.46	1.16	1.89	3.82	0	24
WSR-PDIS	1.64	3.07	5.03	1.25	2.20	4.30	0	24
WSR-DR	1.47	9.91	$\infty$	0.93	6.96	$\infty$	1	23
DR fit	1.53	7.39	$\infty$	0.96	5.21	$\infty$	1	23

Table 3: 24 random trees (depth 2–3),

\delta=10^{-3}

, 100 runs per tree and certifier. Left: minimum, median and maximum over trees of the median stopping time divided by

\log(1/\delta)/K^{\star}

. Middle: the same for the ratio to CV-Kelly’s median on the same tree. “faster”: trees on which the median is below CV-Kelly’s. “finite”: trees on which the median run certified within the horizon

60\log(1/\delta)/K^{\star}

certifier	runs	pooled	worst	runs	pooled	worst
	$\delta=0.05$			$\delta=10^{-3}$
CV-Kelly	300	0.025 [0.021, 0.029]	0.040 [0.021, 0.069]	300	0/6300 [0, 5.9e-4]	0
CV-Kelly (raw plug-in)	300	0.030 [0.025, 0.034]	0.043 [0.023, 0.073]	300	2/6300 [3.8e-5, 1.1e-3]	0.003
hedged	300	0.033 [0.029, 0.038]	0.050 [0.028, 0.081]	300	1/6300 [4.0e-6, 8.8e-4]	0.003
mixture (MC)	300	0.032 [0.028, 0.037]	0.047 [0.026, 0.077]	300	1/6300 [4.0e-6, 8.8e-4]	0.003
scalar Kelly	1000	0.018 [0.016, 0.020]	0.031 [0.021, 0.044]	2000	12/42000 [1.5e-4, 5.0e-4]	0.001

Table 4: False certification under the least-favourable law

q^{\star}

of 21 instances (1 memory tree, 16 random trees, 4 Tiger trees), horizon 1000. “runs”: per instance. Pooled: rate over all instances with 95% Clopper–Pearson interval. Worst: the largest per-instance rate, with its interval at

\delta=0.05

. The four exact-program certifiers used 300 runs per instance, so at

\delta=10^{-3}

a single certification gives a per-instance rate of

0.003

Figure 4: Soundness. (a) False certification rate at

\delta=0.05

under 22 null laws: for each of a memory tree and a random tree,

q^{\star}

(filled diamonds) and 10 vertices of

\mathcal{Q}_{0}

(open circles), with 1000 runs per law and a horizon of 1000 episodes. Points are jittered horizontally. Black bars: the worst law for each certifier with its 95% Clopper–Pearson interval. (b) Scalable certifiers at the DelayedCue boundary null (

\Delta=0

): the fraction of 400 wealth paths (80 null runs

\times

5 Kelly-type gamblers, horizon

2^{16}

) whose maximum reached

1/\alpha

. Ville’s inequality bounds it by

\alpha

(dashed). Grey band: 95% Clopper–Pearson interval for the pooled curve. Zero frequencies are drawn at the lower edge.

$H$	leaves	$K^{\star}$ ( $\epsilon{=}0.05$ )	$K^{\star}$ ( $\epsilon{=}0.2$ )
3	32	0.0289	0.0363
4	68	0.0266	0.0312
5	140	0.0087	0.0144
6	284	0.0080	0.0132
7	572	0.0058	0.0112
8	1148	0.0055	0.0109

Table 5: Tiger POMDP. Left: exact exponents for two logger exploration rates

\epsilon

. Right: median stopping time and 95% interval at

\epsilon=0.2

\delta=10^{-3}

, 100 runs per cell.

Figure 5: (a)

K^{\star}

of the memory task against the number of cue histories

k^{d}

(filled:

p=0.2

; open:

p=0.02

). Trees with equal

k^{d}

coincide, and

K^{\star}k^{d}

decreases to

0.151

p=0.2

(dashed), the

\Theta(k^{-d})

rate of Corollary 6.3 . (b) Exact exponents of the Tiger POMDP against the horizon

H

, for logger exploration

\epsilon=0.2

(solid) and

0.05

(dashed):

K^{\star}

, the cushion exponent

K_{\mathrm{loc}}

with the ratio supersolution (crosses, on top of

K^{\star}

K_{\mathrm{scal}}

, the oracle DR exponent and the coverage ceiling of Theorem 6.2 .

$L$	$\Delta$	cushion0	linear	gru	average	scalar Kelly	EB	LS	HCOPE
5	0.02	14858	56080 (.60)	$\infty$ (.20)	18053	33977 (.83)	65536 (.67)	$\infty$ (0)	$\infty$ (0)
5	0.05	2462	7046	28608 (.93)	2552	5715	16384 (.70)	$\infty$ (.03)	$\infty$ (.23)
10	0.02	19502 (.93)	$\infty$ (.37)	$\infty$ (.03)	22694 (.93)	41110 (.87)	65536 (.53)	$\infty$ (0)	$\infty$ (0)
10	0.05	3510	6682	46493 (.83)	3470	6384	16384 (.77)	$\infty$ (.13)	$\infty$ (.37)
20	0.02	26996 (.87)	$\infty$ (.20)	$\infty$ (.17)	27440 (.83)	48838 (.70)	$\infty$ (.03)	$\infty$ (0)	$\infty$ (0)
20	0.05	6286	11804	8814 (.77)	5433	7648	$\infty$ (.40)	$\infty$ (.13)	$\infty$ (.23)

Table 6: Scalable certification on DelayedCue at

\delta=10^{-3}

: median episodes over 30 alternative runs (certification rate in parentheses when below one).

\infty

: censored at

2^{16}

. average is the mean of the three gamblers’ wealths ( Corollary 5.7 ).

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Result	Proof
Theorem 4.1 (lower bound)	Appendix B
Theorem 4.3 (duality)	Appendix C
Proposition 4.9 (coverage trichotomy)	Appendix D
Proposition 4.10 (positivity under partial coverage)	Appendix D
Theorem 4.11 (local expansion)	Appendix E
Proposition 4.12 (explicit local sandwich)	Appendix E

Appendix

Table 7: Where each result is proved.

Symbol	Meaning
Trees, policies and laws
$\tau$ , $h$ , $\mathcal{J}$	Episode, history (node), set of leaves (complete episodes)
$ha$ , $ho$ , $h\preceq j$	Child of $h$ by action $a$ or outcome $o$ ; node $h$ lies on the path to leaf $j$
$\mu$ , $\pi$	Logger (known, $\mu(a\mid h)>0$ ) and target policy
$R\in[0,b]$	Total reward of an episode
$W$ , $X$	$W(\tau)=\prod_{t}\pi(a_{t}\mid h_{t})/\mu(a_{t}\mid h_{t})$ and $X=(W-1)R$

Appendix

Table 8: Main notation. Definitions are in Section 3 unless another location is given.

$d$	$K^{\star}$	$K^{\star}_{F}$	gain	universal	restricted	restricted
				under $P$ (alternative)		under $q^{\star}$ (violates $F$ )
1	0.1155	0.2763	2.39	82.5 [70, 95]	35 [32, 38]	61.5 [54, 68], 100% false ( $\geq 1.4\%$ )
2	0.0458	0.2763	6.03	203 [184, 229]	35 [33, 37]	40.5 [36, 44], 100% false ( $\geq 19\%$ )
3	0.0207	0.2763	13.35	417.5 [374, 486]	35.5 [34, 38]	39 [35, 42], 100% false ( $\geq 47\%$ )

Appendix

Table 9: Value and risk of the assumption

F

(distractor actions are irrelevant),

\delta=10^{-3}

. Median episodes with 95% intervals; “false” is the false certification rate.

\leq 3.6\%

is the Clopper–Pearson limit for 0 of 100. In parentheses: the floor

\exp(-K^{\star}\mathbb{E}_{P}[\tau])

of Theorem H.2 (ii), evaluated at the restricted certifier’s mean stopping time under

P

, below which no certifier that fast can keep its false-certification rate under

q^{\star}

instance	CV-Kelly	hedged	scalar	mixture	DR fit	DR orc	grid
cue $d{=}0$ $p{=}0.2$	0.91 (18)	1.34	0.23	0.25	0.37	0.49	0.004
cue $d{=}0$ $p{=}0.02$	0.92 (20.5)	1.58	0.44	0.33	0.52	0.30	0.005
cue $d{=}1$ $p{=}0.2$	1.62 (24.5)	2.09	0.12	0.37	0.71	0.66	0.005
cue $d{=}1$ $p{=}0.02$	1.67 (25)	1.77	0.09	0.36	0.55	0.22	0.006
cue $d{=}2$ $p{=}0.2$	2.30 (32)	2.67	0.10	0.59	0.40	0.48	0.006
cue $d{=}2$ $p{=}0.02$	2.26 (32.5)	2.99	0.12	0.59	0.40	0.20	0.007

Appendix

Table 10: Wall-clock seconds per run at

\delta=10^{-3}

(median of 20 runs, one CPU thread). In parentheses: median number of leaf-constrained refits. A run lasts until it certifies or reaches the horizon of Table 2 . Grid: the slowest of LS, EB and HCOPE.

tree	leaves	$\operatorname{rank}(B)$	refit	MiB	$K^{\star}$	$K_{\mathrm{loc}}$
cue $d{=}2$	48	22	0.026	0.0	0.010	0.015
cue $d{=}4$	192	94	0.10	0.6	0.052	0.11
cue $d{=}6$	768	382	6.9	9.1	3.3	7.4
random, depth 4	512	170	1.6	2.9	1.1	–
DelayedCue $K{=}2$ , $L{=}2$	128	52	0.017	0.2	0.022	0.090
DelayedCue $K{=}2$ , $L{=}3$	512	212	1.9	3.9	0.32	2.6

Appendix

Table 11: Cost of one plug-in refit (logged-law projection plus Kelly program on an empirical law of 4096 episodes; median of 3) and of computing

K^{\star}

and

K_{\mathrm{loc}}(\bar{m})

once on the true law, in seconds, with the refit’s peak traced memory.

Figure 6: Cushion certifier on DelayedCue at

\delta=10^{-3}

with a horizon of

2^{16}

episodes and 30 runs per cell (the data of Table 6 ). (a, b) Median stopping time with 95% order-statistic intervals; points in the shaded band have a censored median. (c, d) Fraction of runs certified within

2^{16}

episodes, with 95% Clopper–Pearson intervals. Points are offset horizontally for legibility.

$(K,L)$	leaves	bound	$K_{\mathrm{loc}}$	cushion0	linear	cushion0	linear	cushion0	CV-Kelly	scalar
			exponent ratios $K^{\star}/\cdot$			online factor		median $/$ lower bound
$(2,1)$	32	542	1.000	1.36	1.32	1.26	3.07	1.71	1.56	6.08
$(2,2)$	128	552	1.000	1.33	1.25	1.63	3.20	2.17	1.83	4.99
$(2,3)$	512	562	1.000	1.36	1.24	1.54	3.20	2.09	3.17	5.26
$(4,1)$	512	1138	1.000	1.48	1.42	1.51	2.93	2.24	1.93	5.34

Appendix

Table 12: Matched DelayedCue instances at

\Delta=0.05

\delta=10^{-3}

, 30 runs. Exponent ratios are computed on the enumerated tree. Median stopping times are in units of the lower bound

\log(1/\delta)/K^{\star}

of Theorem 4.1 (shown in episodes). Online factor: median stopping time times

K_{\mathrm{class}}/\log(1/\delta)

Figure 7:

K^{\star}

and the semiparametric efficiency bound on 200 random trees. (a)

K^{\star}

against

\Delta^{2}/2\sigma^{2}_{\mathrm{eff}}

, each tree at its own advantage

\Delta

. (b) Histogram of the ratio

K^{\star}/(\Delta^{2}/2\sigma^{2}_{\mathrm{eff}})

on the 189 of the 200 trees with

\Delta>0.01

, stacked by depth; shaded: the 10–90% range. The filter removes trees where the ratio is numerically unstable (

\Delta\to 0

) and is unrelated to the 192 trees with zero price of locality in the text. Theorem 4.11 makes the ratio tend to 1 only as

\Delta\to 0

. At a fixed advantage it ranges from

0.014

19.4

, and it is below 1 on 47% of trees.

Figure 8: Certification pipeline. Each lane turns the past episodes into a predictable bet and evaluates it on the new episode

\tau_{t}

, giving an e-value

Y_{t}

. The product

M_{t}

is a nonnegative supermartingale under every null law, so stopping once

M_{t}\geq 1/\delta

\delta

-sound by Ville’s inequality. Top: for an enumerable tree, Algorithm 1 projects the empirical law onto

\mathcal{Q}

and solves the dual program of Theorem 4.3 . Bottom: when the tree cannot be enumerated, the cushion game of Theorem 7.1 with the closed-form supersolution of Lemma 7.3 evaluates the bet along the realized episode only ( Proposition 7.4 ).

family	$H$	leaves	$P(A)$	$V(\mu)$	$K^{\star}$	$K^{\star}/P(A)$	ceiling	$\mathrm{KL}_{2}$
Jajoo	3	18	0.2222	0.5556	0.02414	0.1086	0.09010	0.1221
Jajoo	4	54	0.1481	0.5370	0.01724	0.1164	0.06007	0.0814
Jajoo	5	162	0.0988	0.5247	0.01198	0.1213	0.04005	0.0543
Jajoo	6	486	0.0658	0.5165	0.00820	0.1245	0.02670	0.0362
Jajoo	7	1458	0.0439	0.5110	0.00556	0.1267	0.01780	0.0241
Jajoo	8	4374	0.0293	0.5073	0.00375	0.1280	0.01187	0.0161

Appendix

Table 13: Exact exponents on the published hard instances.

V(\pi)=3/4

throughout.

\mathrm{KL}_{2}=\mathrm{KL}(P_{1}\|P_{0})

is the exponent within each paper’s two-model class. The ceiling of Theorem 6.2 equals

P(A)\log(3/2)

exactly.

Sequential Hypothesis Testing

Sequential hypothesis testing makes decisions as evidence arrives, controlling errors while adapting how much data to collect and when to stop.

See all 60 papers

Coverage Cliffs in Off-Policy Quantile Certification
Oct 15, 2026Pauline Bourigault, Emmanuelle BourigaultOff-Policy Evaluation Contextual Bandits
Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging
Sep 16, 2026Pranaya JajooOff-Policy Evaluation Sample Complexity
University of Alberta
Nous: Learning and Certifying Memory Decisions Before Source Calibration
Sep 8, 2026Pranav SinghMemory-Augmented Agents
Department of Mathematics, Indian Institute of Technology Ropar

Oct 15, 2026J/K move · Enter open · S save

Coverage Cliffs in Off-Policy Quantile Certification

Pauline Bourigault, Emmanuelle Bourigault

Off-Policy Evaluation Contextual Bandits

Open paper AskPDF arXiv

We study when logged contextual-bandit data can certify an upper tail quantile for a policy selected from the same sample. We construct a PAC-Bayes Bernstein lower-confidence envelope for the target cumulative distribution function (CDF), simultaneous over a predeclared threshold grid and all data-dependent posteriors. The resulting procedure, TailCert, uses the envelope's first crossing of level p to return an atom-safe upper confidence bound on the selected posterior's pooled p-quantile (or inconclusive). It can also be used to select a policy under a certified tail constraint. The concentration ingredients are standard; the main theoretical contribution is a matched finite-class certification boundary comparing full logs with their joint weighted CDF indicators at a fixed threshold. On an explicit rare-action class, the required sample size grows linearly with the overlap factor W, logarithmically with policy-search and confidence complexity, and quadratically with the inverse CDF safety margin; the upper and lower bounds agree up to constants in the stated regime. On this class, the CDF reduction hides which actions exceeded the budget; retaining action counts restores the full-log rate. Simulations verify the predicted search-complexity shift, winner's-curse failure of naive reuse, and the power cost of splitting.

Abstract

Sequential Hypothesis Testing

Explore similar work

Coverage Cliffs in Off-Policy Quantile Certification

Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

Nous: Learning and Certifying Memory Decisions Before Source Calibration