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

Introduction

Suppose a team has trained a new dialogue policy $\pi$ offline and holds a log of conversations produced by the deployed policy $\mu$. The decision to replace $\mu$ by $\pi$ is binary, and a wrong replacement is costly. The team therefore wants a sound rule: if $\pi$ is not better than $\mu$, it is deployed with probability at most $\delta$. Logged episodes arrive one at a time, so the rule should be sequential and stop as soon as the evidence suffices. This is the goal of high-confidence off-policy evaluation and safe policy improvement (Thomas et al., 2015a,b; Laroche et al., 2019), and of gated deployment with anytime-valid confidence sequences [16, 39]. The practical question is how many episodes such a rule must wait for.

Memory makes this question hard. Recurrent policies, dialogue agents and controllers for partially observable environments choose actions based on the whole history. The importance weight that reweights a logged episode towards $\pi$ is then a product of per-step ratios, and it can be enormous on the few episodes that $\pi$ would have produced. Recent lower bounds show that this cost is sometimes unavoidable: under history-dependent logging, evaluation can require exponentially many episodes in the horizon [40, 11, 24]. Worst-case bounds, however, say little about a particular log. Some instances can be certified from a handful of episodes, and others cannot be certified at all.

Existing certifiers compress each episode to a scalar, such as an importance-sampling (IS), per-decision IS or doubly robust (DR) estimate of the advantage, and then apply a concentration inequality [34] or a betting confidence sequence (Waudby-Smith and Ramdas, 2024) to the resulting stream. Better estimators and tighter inequalities shorten the wait. It is unclear, though, whether these refinements approach a limit, and whether a certifier that looks at more than one scalar per episode could do fundamentally better. This leaves a basic question open: for a given instance, how many logged episodes does the best possible sound certifier need, and what does it look like? We answer it in the expected-stopping-time sense of sequential testing [8].

Our approach views certification as a betting game [32, 28]. The certifier starts with unit wealth, places a bet on each logged episode and certifies once its wealth reaches $1/\delta$. The bets must be fair or unfavourable under every environment in the null, so that by Ville’s inequality wealth rarely reaches $1/\delta$ when $\pi$ is not better. The null is large: it contains every environment in which $\pi$ does not improve on $\mu$, including environments that differ from the true one on histories the log never reaches. Because $\mu$ is known, however, no environment can change how the logged actions were chosen. The bettor therefore has two kinds of admissible bets: a stake on the importance-weighted advantage $X$, which pays off when $\pi$ is better, and fair bets on the logged actions themselves, at the odds $\mu$ assigned to them. Fair bets earn nothing on average under any null environment, but they can offset the losses of the advantage bet on bad outcomes, which lets the bettor stake more while keeping its wealth nonnegative. We show that the optimal bettor combines both, and that its wealth grows at rate $K^\star$, the KL divergence from the logged law to the nearest null law that leaves the logged action probabilities unchanged. The control variates of DR estimators are fair bets of this kind, chosen heuristically. They therefore act as hedges rather than as better estimators, which explains both why they help and why no estimator can beat the optimal combination. How far the bettor can lever its stake is limited by coverage, that is, by how much of $\pi$’s behaviour the log reveals. The largest safe stake is a superhedging price, computed by backward induction over the tree. Figure 1 illustrates the setting and the geometry of $K^\star$.

Informally, our main result is as follows. For every logged law $P$ under which $\pi$ improves on $\mu$, every $\delta$-sound certifier needs at least $\log(1/\delta)/K^\star(P)$ episodes in expectation, at every $\delta$. A plug-in Kelly certifier attains this bound to first order as $\delta\to0$ when $0 < K^\star(P) < \infty$. Coverage decides whether $K^\star(P)$ is zero, finite or infinite.

Contributions. We model an episode as a path through a finite outcome tree whose action nodes are controlled by the known logger $\mu$. The null hypothesis contains every environment on the tree under which $\pi$ does not improve on $\mu$.

1. In Section 4 we define the certification exponent $K^\star(P) = \inf\{\mathrm{KL}(P\mathbin\Vert q) : q$ action-neutral, $\mathbb{E}_q X \le0\}$, where $X = (W - 1)R$ is the importance-weighted advantage

tage of an episode. A trade-off inequality shows that any stopping time with finite mean under $P$ stops under a null $q$ with probability at least $\exp(-\mathbb{E}_{P}[\tau]\operatorname{KL}(P\mathbin{\|}q))$. Hence every $\delta$-sound sequential certifier has $\mathbb{E}_{P}[\tau_{\delta}] \ge\log(1/\delta)/K^{\star}$, non-asymptotically and without a power condition (Theorem 4.1). By duality, $K^{\star}$ is the optimal growth rate of a bettor holding a claim $\lambda X$ who may also place fair bets on every logged action at odds $\mu$ (Theorem 4.3). The maximal leverage is a superhedging price computed by backward induction (Proposition 4.4).

2. Section 5 gives matching certifiers. A predictable Kelly certifier attains $\mathbb{E}_{P}[\tau_{\delta}] = (1 + o(1))\log(1/\delta)/K^{\star}$ (Theorem 5.1). When $K^{\star} < \infty$ it also satisfies the non-asymptotic bound $\mathbb{E}_{P}[\tau_{\delta}] \le\log(1/\delta)/K^{\star} + O(\sqrt{\log(1/\delta)}\log\log(1/\delta))$, with constants given in terms of $K^{\star}$, the support of $P$ and the least-favourable law (Theorem 5.2). The plug-in fits its bet to the maximum-likelihood logged-law projection of the empirical law, which exploits the known $\mu$; without the projection it overfits and is 15× slower in our experiments. When the null contains a full-support law, a universal-portfolio mixture has finite-sample tail and expectation bounds (Theorem 5.5). Its exact form sharpens the expected-time remainder to $(d/K^{\star})\log\log(1/\delta) + C_{P}$ (Theorem 5.5(v)); with Theorem 4.1, this pins the first-order constant from both sides. Averaging the two wealths keeps both guarantees at a cost of $\log2$ (Corollary 5.7).

3. We show that coverage decides the regime (§ 4.3). The advantage $\Delta$ and the superhedging price $m$ place each instance in one of three regimes. If $K^{\star} = 0$, no $\delta$-sound certifier certifies with probability above $\delta$. The case $0 < K^{\star} < \infty$ is equivalent to the null containing a full-support law. If $K^{\star} = \infty$, an arbitrage certifier is exactly sound and stops after $1/P(G > 0)$ episodes in expectation (Proposition 4.9). Without positivity of $\mu$, certification is possible if and only if $\pi$ beats $\mu$ after every unlogged action of $\pi$ is assigned the worst reward, even when $V(\pi) > V(\mu)$ (Proposition 4.10). Non-asymptotically, $K^{\star}$ lies between two multiples of $\Delta^{2}/2\sigma_{\mathrm{eff}}^{2}$ (Proposition 4.12).

4. We derive several consequences of the exponent (§ 6). Replacing $X$ by any DR or per-decision IS payoff leaves $K^{\star}$ unchanged, and every sound certificate built on a per-episode statistic $S$ needs at least $\log(1/\delta)/K_{S}$ episodes in expectation, with $K_{S} \le K^{\star}$ (Theorem 6.1). As the advantage vanishes, $K^{\star}$ tends to the semiparametric efficiency bound $\Delta^{2}/2\sigma_{\mathrm{eff}}^{2}$, under regularity conditions on $P$ alone (Theorem 4.11). Away from that limit the ratio $K^{\star}/(\Delta^{2}/2\sigma_{\mathrm{eff}}^{2})$ ranges from 0.014 to 19.4 on random trees, so the efficiency bound can be off by more than an order of magnitude in either direction. The coverage ceiling $K^{\star} \le P(A)\log\frac{V(\pi)-r_{A}}{V(\mu)-r_{A}}$, where $A$ is the event that $\pi$ could have produced the logged actions (Theorem 6.2), recovers the exponential rates of Jajoo [11] and Luo et al. [24] for one-sided certification. Structural assumptions are linear constraints whose value $K_{F}^{\star}/K^{\star}$ is computable. Any certifier that turns an assumption into a speed-up certifies falsely at the least-favourable law with probability about $\delta^{K^{\star}/K_{F}^{\star}} \gg\delta$ (Theorem H.2).

5. We extend certification to trees that cannot be enumerated (§ 7). Feasibility of a bet reduces to a sequence of local conditions driven by the superhedging price (Theorem 7.1). Any supersolution of the price recursion, including a closed form

that needs only per-step ratio bounds (Lemma 7.3), gives a sound certifier that costs $O(T|A|)$ per episode for arbitrary observation spaces (Proposition 7.4).

6. We test the theory (Section 8) on memory tasks, the Tiger POMDP (Kaelbling et al. [13]), random trees and the published hard instances. The strongest baselines are scalar betting certificates: scalar Kelly and the betting confidence sequence of Waudby-Smith and Ramdas (2024) on the PDIS and DR payoffs. The best of them needs 1.05–2.65× the plug-in’s episodes on memory trees and 2.8–4.1× on Tiger ($H \le5$). On shallow random trees a fitted DR bet can be faster than the plug-in (Section 8.3). Doubling-grid certificates in the style of HCOPE, logarithmic smoothing and empirical Bernstein need 9–52× more episodes, or fail. We check soundness at the least-favourable null on 21 instances, report the wall-clock and memory cost of every certifier (Section 8.4), and split the scalable certifier’s gap to $K^\star$ into supersolution, gambler-class and online-learning factors (Table 12).

The rest of the paper is organized as follows. Section 2 reviews related work, and Section 3 introduces logged trees, action-neutral laws and soundness. Section 4 proves the lower bound and the duality, classifies instances by coverage (Section 4.3) and relates $K^\star$ to the efficiency bound. Section 5 gives matching certifiers. Section 6 derives estimator invariance, the coverage ceiling and the price of structural assumptions. Section 7 develops the scalable cushion certifier, Section 8 reports experiments, and Section 9 concludes. Proofs and additional experiments are in the appendix.

Related work

Our work draws on sequential testing, testing by betting and off-policy evaluation. Relative to these literatures, the new ingredient is the null class: with a known logger, the action-neutral laws form a polytope, and this structure produces the fair bets $B$ and the superhedging price $m$ from which our results follow. In particular, HCOPE (Thomas et al. [34]) applies a scalar concentration bound to $X$ and, in our terms, targets the scalar exponent $K_{\mathrm{scal}}$ rather than $K^\star$.

Sequential testing and instance-optimal lower bounds. Theorem 4.1 uses the change-of-measure argument of Garivier and Kaufmann [8] and Kaufmann et al. [18]. $K_{\mathrm{scal}}$ is the KL$_{\mathrm{inf}}$ of Honda and Takemura [10] applied to $X$. Sethi et al. [31] characterize optimal sequential tests with Markovian data under the same KL direction, but without an action layer or a value inequality. Our contribution is the alternative class of action-neutral laws, which may change any environment kernel, including kernels at unvisited histories, but never the logged action conditionals, and its consequences. The explicit plug-in bound of Theorem 5.2 follows the good-event plus concentration template of track-and-stop analyses (Garivier and Kaufmann [8]) and of KL$_{\mathrm{inf}}$-based identification with nonparametric arms (Agrawal et al. [1]); what is specific here is that the plug-in is a logged-law projection and its loss is controlled by a sandwich in $\ell_1$ that holds without any interior assumption.

Coverage and partial identification. Without positivity the value of the target is only partially identified, and the worst case sets uncovered rewards to the bottom of their range, as in the bounds of Manski [25]. Proposition 4.10 shows that this worst case is exactly what the sequential problem sees: the exponent is that of the identified lower value, and certification is impossible when that value does not exceed the logger’s. Proposition 4.9 separates the complementary regime, in which coverage is so strong that a single episode can be a certificate.

E-values, growth-rate optimality and betting. For an arbitrary composite null and a simple alternative, Larsson et al. [23] prove that a log-optimal (numeraire) e-variable exists and characterize it through the reverse information projection; Lardy et al. [21] extend this theory to cases where the infimal KL is infinite. Theorem 4.3 gives the closed-form instance of that theory for the polytope null $\mathcal{Q}_0$ induced by a known history-dependent logger. In this instance the optimal e-variable is affine, $1+\lambda X+B\nu$, with $\nu$ a vector of fair bets on logged actions, and its feasible set is the superhedging set of Proposition 4.4. This explicit form is what the plug-in, the invariance theorem and the cushion certifier use. Theorem 4.3 also specializes the growth-rate-optimal e-variables of Grünwald et al. [9], and Remark 4.6 explains why the bipolar gap of Ram and Ramdas [27] and the counterexamples of Kitamura et al. [20] do not arise. The specialization adds the explicit family of e-variables (Lemma 4.2), the superhedging recursion (Proposition 4.4) and the strong duality analysis including the infinite case (Section C). The recursion is the discrete-time superhedging price of an incomplete market [7], with the logged actions as the traded assets. Testing by betting is surveyed by Shafer [32] and Ramdas et al. [28]. Split and running-MLE likelihood-ratio tests [37] are also valid for composite nulls; on a finite tree their denominator is a likelihood maximization over $Q_0$, the same convex program the plug-in solves. The universal mixture is Cover’s universal portfolio [4], used as in Waudby-Smith and Ramdas (2024) and Orabona and Jun [26]; see Kaufmann and Koolen [17] for mixture martingales in sequential testing.

Anytime-valid off-policy evaluation. Karampatziakis et al. [16] and Waudby-Smith et al. [39] construct betting confidence sequences for off-policy values in contextual bandits, including doubly robust corrections. Karampatziakis et al. [15] use empirical likelihood, which is dual to a KL tilt, for bandit OPE. Sandoval et al. [30] prove Kelly optimality for multi-armed sequential testing. Our setting is multi-step and history-dependent, with a known logger. Our certifier’s rate is asymptotically instance-optimal against the action-neutral class, and the logged-law projection is what makes the plug-in practical.

Scalar high-confidence OPE and safe policy improvement. HCOPE and HCPI [34 b], logarithmic smoothing [29], universal OPE [3] and SPIBB [22] bound a scalar estimator or restrict policy updates to well-covered regions. Theorem 6.1 shows that any certificate based on a per-episode statistic of the same log has exponent at most $K^\star$, and § 8 measures the gap.

Semiparametric efficiency. Jiang and Li [12] and Kallus and Uehara [14] give the local efficiency theory of DR estimators. Theorem 4.11 identifies the efficiency bound as the small-advantage limit of $K^\star$. Empirical likelihood has a similar large-deviation optimality for moment restrictions [19], subject to the caveats of Kitamura et al. [20].

History-dependent OPE and the curse of memory. Tennenholtz et al. [33] study off-policy evaluation in partially observable environments. Zhang and Jiang [40] identify the curse of memory for history-dependent off-policy evaluation in POMDPs. Jajoo [11] and Luo et al. [24] prove worst-case exponential evaluation lower bounds under a known history-dependent logger. These works establish the phenomenon. Theorem 6.2 complements them with an instance-dependent ceiling for one-sided certification, and Table 13 computes $K^\star$ on their constructions.

Setting

We first fix the objects: the tree of possible episodes, the class of environments that could have generated the log, and what it means for a certifier to be sound.

Logged trees. An episode alternates environment outcomes and logged actions,

Rewards are part of the outcomes, and the total reward $R(\tau)$ lies in $[0,b]$. All possible episodes form a finite rooted tree. Its non-leaf nodes are environment nodes, where an outcome is drawn, and action nodes, where the logger acts. The tree includes every outcome the environment could produce, including outcomes that never appear in the logs. We write $\mathcal{J}$ for the set of leaves (complete episodes), $ha$ for the child of an action node $h$ reached by action $a$, and $h \preceq j$ if node $h$ lies on the path to leaf $j$. The logger $\mu(a \mid h) > 0$ is known and its propensities are recorded. The target $\pi(a \mid h)$ is fixed. Both may depend on the whole history. Let