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

Oct 15, 2026

Coverage Cliffs in Off-Policy Quantile Certification

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.

Pauline Bourigault, Emmanuelle Bourigault

Off-Policy Evaluation Contextual Bandits

Ask PDF

Sep 16, 2026

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

Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon

H \ge 3

, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of

H

. Nevertheless, evaluating a known deterministic target policy to accuracy

1/8

requires

Θ((3/2)^H \log(1/δ))

logged episodes at confidence

1-δ

, for

0 < δ\le 1/4

, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.

Pranaya Jajoo

University of Alberta

Off-Policy Evaluation Sample Complexity Partially Observable Markov Decision Processes

Ask PDF

Sep 8, 2026

Nous: Learning and Certifying Memory Decisions Before Source Calibration

Agent memory systems update state decisions from reports whose reliability may be unknown. Existing analyses of source estimation do not determine when a policy can be learned or its improvement certified without identifying the reporting channel. We study these three tasks using the same observed records. For a specified hidden Markov family with continuous source uncertainty, decision learning and powered certification have quadratic sample complexity, whereas fixed-precision source estimation has quartic complexity. We characterize a sharp identified interval for policy gain under an unknown shared-background channel and derive finite-sample certificates under bounded history dependence and conditional copying. Independently trained witness regions support general history spaces, and disagreement-conditioned auditing improves power for sparse revisions. For dependent histories, prediction-count-preserving batches cancel the unknown reporting background and admit conditional certificates. A MultiWOZ 2.4 evaluation uses text-processing policies on 1,000 human-written test dialogues with simulated audits. Balanced batches retain 2.26 percentage points of the full candidate's 7.34 percentage-point mean gain and obtain more positive certificates under weak audits. These results establish task-specific information requirements and provide an auditable policy-revision framework for Nous.

Pranav Singh

Department of Mathematics, Indian Institute of Technology Ropar

Memory-Augmented Agents

Ask PDF

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