Regret-based Characterization, Information Limits, and the Sample Complexity of Auditing Adaptive Policies

Introduction

Learned policies set portfolio weights, prices, bids, inventory orders, and treatment assignments. A principal or regulator who evaluates such a policy usually sees only its inputs and outputs, but wants to know whether the policy creates value by using information or merely by how it behaves on average. The second kind of value can be replicated by a fixed rule; the first cannot. This paper studies the problem of separating the two, which we call auditing adaptivity, from three angles: an exact characterization, an information-theoretic limit, and the sample complexity of estimation.

The benchmark. Fix a Markov policy $\pi=(\pi_1,\ldots,\pi_H)$ in a finite-horizon MDP and let $d_t^\pi$ be its state distribution at step $t$. Its open-loop marginal $\nu=\nu^\pi$ is the policy that, at step $t$, ignores the state and draws $a_t$ from

Thus $\nu$ uses each action exactly as often as $\pi$ does on average at each step, but uses no information. The quantity $\Delta(\pi):=J(\pi)-J(\nu)$, where $J$ denotes expected total cost, is the value that $\pi$ adds (if negative) or destroys (if positive) by conditioning on the state. In finance, this is the classical split of active returns into a ”timing” (covariance) component and a ”static allocation” (means) component [9, 19]; in stochastic optimization, $\min_\nu J(\nu)-\min_\pi J(\pi)$ is the additive adaptivity gap [10, 13]. Recent work by Aldridge [2, 3] observed that, for stochastic linear programs and portfolio policies, expected regret equals the covariance between costs and decisions when the policy is mean-unbiased. We show that this phenomenon is exact in far greater generality and develop its quantitative theory.

Results

1. Exact characterization (§ 3). In every finite-horizon MDP and for every Markov policy $\pi$,

where $P_t$ is the joint law of $(s_t,a_t)$ under $\pi$ and $P_t^S\otimes P_t^A$ is the product of its marginals (Theorem 3.4). The identity holds under fully endogenous dynamics; the feedback from actions to states is absorbed by evaluating the covariance under $\pi$’s state distribution and pairing actions with the $Q$-function of $\nu$. Pathwise and with no probability model at all, the regret of any online linear optimization algorithm against the best fixed action in hindsight equals a sample covariance plus a non-negative static gap (Theorem 3.1). Regret to the optimal policy splits as adaptivity plus static allocation plus the problem’s adaptivity gap, and the adaptivity gap is at most the covariance magnitude of any optimal policy (Theorem 3.7). The $Q^\nu$ in (1) cannot be replaced by immediate costs: the resulting “myopic audit” can report value destruction for a policy that creates value, with unbounded error (Theorem 3.8).

2. Information limits (§ 4). The right-hand form of (1) compares a joint law to the product of its marginals. The KL divergence between them is the mutual information $I(s_t;a_t)$, so Pinsker’s inequality yields:

Informal statement (Theorems 4.2 and 4.3). $\left|J(\pi)-J(\nu)\right|\leq\sum_t \operatorname{span}_t(\pi)\sqrt{I(s_t;a_t)/2}$, where $\operatorname{span}_t$ is the largest per-state range of $Q_t^\nu$ across actions. The constant $1/\sqrt{2}$ cannot be improved.

Two consequences follow. The additive adaptivity gap of an MDP is at most $\sum_t\operatorname{span}_t\sqrt{I_t/2}$ evaluated at any optimal policy, so problems whose optimal policies need few bits have small adaptivity gaps (Theorem 4.4). And with costs in $[0,1]$, a policy whose actions carry at most $R$ units of mutual information between state and action per step (a.k.a. $R$ ”nats”) cannot beat the best open-loop policy by more than $\frac{H(H+1)}{2}\sqrt{R/2}$ (Theorem 4.5). This is a rate–value tradeoff in the spirit of rational inattention [24, 25].

3. Sample complexity of auditing (§ 5). An auditor observes $\pi$’s own logs and must estimate $\Delta(\pi)$. Under full information, the problem is easy. Under bandit feedback, it reduces to off-policy evaluation of the open-loop marginal $\nu^\pi$, and the right complexity parameter is

the average $\chi^2$-divergence from the marginal to the conditional action distributions.

Informal statement (Theorems 5.2 to 5.4). A median-of-means IPW auditor estimates $\Delta(\pi)$ within $\pm\delta$ with probability $1-\eta$ from $O(\bar{\chi}^{2}\log(1/\eta)/\delta^{2})$ logged rounds, for every policy and instance. Conversely, for every value $\Gamma\geq1/3$ there is a policy with $\bar{\chi}^{2}=\Gamma$ and two instances on which every auditor needs $\Omega(\Gamma\log(1/\eta)/\delta^{2})$ rounds. If $\pi$ never plays some action that $\nu^\pi$ plays, on a set of contexts of positive measure, then $\Delta(\pi)$ is not identifiable. In particular, a deterministic non-constant policy cannot be audited from its own logs.

For episodic MDPs, an importance-sampling auditor over whole trajectories needs a number of episodes

(Theorem 5.6).

Techniques

The characterization rests on two observations. First, the open-loop marginal is the unique state-independent policy whose value function satisfies $V_t^\nu(s)=\langle Q_t^\nu(s,\cdot),\bar p_t\rangle$ with the same $\bar p_t$ as $\pi$’s marginal. Plugging this into the performance-difference lemma [16] turns each advantage term into a centered inner product, which is a covariance. Second, a covariance between a function of the state and a function of the action is $\mathbb{E}_{P}f-\mathbb{E}_{P_S\otimes P_A}f$, so any divergence bound between a joint law and its product applies. The identity is invariant to adding any function of the state to $Q_t^\nu$, and choosing the per-state midpoint replaces the global oscillation of $Q_t^\nu$ by the much smaller per-state action range. For auditing, the key observation is that $\mathbb{E}[\ell_t(a_t)]$ under $\pi$ is directly observable, so all statistical difficulty lies in evaluating $\nu^\pi$ off-policy. The variance of the natural estimator is exactly bounded by $\bar\chi^2$. The lower bound plants a cost perturbation on the context–action pair that $\pi$ plays with probability $p$ but $\nu^\pi$ plays with probability $1/2$, and applies the Bretagnolle–Huber inequality.

Related work

Online learning and regret. Regret against the best fixed action is the standard benchmark of online learning [7, 14]. Theorem 3.1 is an elementary identity, but it provides a structural reading of regret: negative regret (beating the best fixed action) is possible only with negative sample covariance, and every no-regret algorithm has sample covariance of at most its regret. Applied to stochastic bandit algorithms such as Thompson sampling, whose regret is near-optimal [1], the decomposition separates an algorithm’s static exposure to suboptimal arms (the static gap) from the timing of its exploration (the covariance).

Adaptivity gaps. The benefit of adaptivity is studied as a multiplicative ratio for stochastic knapsack [10], stochastic probing [13] and submodular maximization [4]. Our bounds are additive and problem-agnostic: Theorem 4.4 bounds the gap by the information used by an optimal policy, and Theorem 3.7 identifies the policy-level quantity, a covariance, whose extremum the gap is.

Information-theoretic bounds. Bounding the covariance between a selection and a quantity by mutual information through a change of measure underlies information-theoretic analyzes of adaptive data analysis [23], generalization [29], and Thompson sampling [22]. Theorem 4.2 applies this technique to the value of adaptivity in MDPs. Evaluating the bound on continuous-state data requires estimating mutual information, for which efficient $k$-nearest-neighbour entropy estimators are available [5]. Two ingredients specific to this setting are the reduction to $Q^\nu$ through Theorem 3.4 and the state-baseline invariance that yields the per-state span. Information-constrained decision-making is studied as rational inattention [24] and in information-theoretic RL [25].

Off-policy evaluation. Our auditing results are an instance of off-policy evaluation (OPE), with the twist that the target policy $\nu^\pi$ is defined by the behavior policy itself. Importance sampling and doubly robust estimators [11, 15, 21] and minimax analyses for contextual bandits [17, 27] are the closest antecedents. The lower bound of Theorem 5.4 is in the spirit of [17], specialized for targets of the form $\nu^\pi$. Marginalized importance sampling [18, 28, 31] suggests routes to polynomial-in-horizon auditing.

Auditing LLM agents. Agentic systems built on large language models raise the same question at the level of tool calls and workflow steps. Systems working on agent evaluation ask when and how to inspect an agent’s execution mid-trajectory [30]. Our results supply a complementary statistical criterion. Logging the agent’s action propensities and states is enough to estimate its adaptive value against its own open-loop marginal (Theorem 5.6). Without exploration, however, a deterministic agent cannot be audited from its own logs (Theorem 5.2).

Finance and predict-then-optimize. The decomposition $\mathbb{E}[c^\top z] = \mathbb{E}[c]^\top\mathbb{E}[z] + \operatorname{tr}\operatorname{Cov}(c,z)$ is classical in performance attribution [9, 19] and related to decision-focused learning [12]. Aldridge [2, 3] uses it as a regret characterization for stochastic linear programs and AI investment strategies under a mean-unbiasedness condition. The present paper removes that condition, extends the identity to endogenous dynamics, and supplies information and sample-complexity theory.

Model

MDPs and policies. A finite-horizon MDP is a tuple $M = (\mathcal{S}, \mathcal{A}, H, (P_t)_{t \le H}, (\ell_t)_{t \le H}, \rho)$ with finite state and action sets, transition kernels $P_t(\cdot\mid s,a) \in\Delta(\mathcal{S})$, bounded costs $\ell_t: \mathcal{S} \times\mathcal{A} \to\mathbb{R}$, and initial distribution $\rho\in\Delta(\mathcal{S})$. A (randomized, time-dependent) Markov policy is $\pi= (\pi_t)_{t \le H}$ with $\pi_t(\cdot\mid s) \in\Delta(\mathcal{A})$. Running $\pi$ generates $s_1 \sim\rho$, $a_t \sim\pi_t(\cdot\mid s_t)$, $s_{t+1} \sim P_t(\cdot\mid s_t,a_t)$. Write $d_t^\pi\in\Delta(\mathcal{S})$ for the law of $s_t$, $J(\pi) = \mathbb{E}^\pi[\sum_{t=1}^H \ell_t(s_t,a_t)]$ for expected total cost, and

for the action-value and value functions of a Markov policy $\mu$. Costs, rather than rewards, maintain the sign convention of regret.

Definition 2.1 (Open-loop marginal). For a Markov policy $\pi$, let $\bar{p}_t^\pi(a) = \sum_s d_t^\pi(s)\pi_t(a \mid s)$. The open-loop marginal of $\pi$ is the policy $\nu^\pi$ with $\nu_t^\pi(\cdot\mid s) = \bar{p}_t^\pi$ for all $s$. A policy is open-loop if $\mu_t(\cdot\mid s)$ does not depend on $s$ for every $t$.

We write $\nu= \nu^\pi$ and $\bar{p}_t = \bar{p}_t^\pi$ when $\pi$ is clear, and call $\Delta(\pi) := J(\pi) - J(\nu^\pi)$ the adaptivity cost of $\pi$; $-\Delta(\pi)$ is its adaptive value. Let $\pi^*$ be an optimal policy and $\nu^*$ an optimal open-loop policy (both exist by finiteness and compactness). The (additive) adaptivity gap of $M$ is $\operatorname{Gap}(M) := J(\nu^*) - J(\pi^*) \ge0$.

Covariances. For random vectors $q,z \in\mathbb{R}^{\mathcal{A}}$ with finite second moments, $\operatorname{Cov}(q,z) = \mathbb{E}\langle q,z\rangle- \langle\mathbb{E}q,\mathbb{E}z\rangle= \mathbb{E}\langle q-\mathbb{E}q,z-\mathbb{E}z\rangle$. Throughout, $q_t := Q_t^\nu(s_t,\cdot)$ and $z_t := \pi_t(\cdot\mid s_t)$ with $s_t \sim d_t^\pi$, so that $\mathbb{E}z_t = \bar{p}_t$.

Information quantities. Under $\pi$, let $P_t(s,a) = d_t^\pi(s)\pi_t(a \mid s)$ be the joint law of $(s_t,a_t)$, with marginals $P_t^S = d_t^\pi$ and $P_t^A = \bar{p}_t$. The mutual information is $I_t(\pi) := I(s_t;a_t) = \operatorname{KL}(P_t \,\|\, P_t^S \otimes P_t^A)$, in units of information, nats. For distributions $p,q$ on $\mathcal{A}$, $\chi^2(p\|q) = \sum_a p(a)^2/q(a) - 1$, with the convention $\chi^2 = \infty$ if $p \not\ll q$.

Exact characterization

Pathwise: online linear optimization

Corollary 3.2. For every online algorithm and every adversary, $\widehat{C}_{T}\leq\operatorname{Regret}_{T}$, with equality if and only if $\bar{z}$ is a best fixed action in hindsight. In particular, $\operatorname{Regret}_{T}<0$ implies $\widehat{C}_{T}<0$, and every algorithm with $\operatorname{Regret}_{T}\leq\rho(T)$ has $\widehat{C}_{T}\leq\rho(T)$.

Theorem 3.1 requires no stochastic assumptions; it is the accounting identity the auditor computes on a realized path. The rest of the paper concerns the expected, endogenous-dynamics analogue.

The MDP covariance identity

Proof. With action-independent transitions, $Q_t^\nu(s,a)=\ell_t(s,a)+g_t(s)$ with $g_t(s)=\mathbb{E}[V_{t+1}^\nu(s_{t+1})\mid s_t=s]$. Apply the invariance in Theorem 3.4.

Decomposing regret to the optimum

Proof. Add and subtract $J(\nu^\pi)$ and $J(\nu^{\pi^*})$, and apply Theorem 3.4. The middle term is non-negative because $\nu^{\pi^*}$ is open-loop. Setting $\pi=\pi^*$ gives the second statement.

Myopic audits fail

A tempting shortcut is to audit with immediate costs, $\sum_t\operatorname{tr}\operatorname{Cov}(\ell_t(s_t,\cdot),z_t)$, which by Theorem 3.6 is correct when dynamics are exogenous. Under endogenous dynamics it can be arbitrarily wrong.

Proof. Let $s_1\sim\operatorname{Bernoulli}(1/2)$ and $\mathcal{A}=\{0,1\}$ (“wait”, “invest”). Set $\ell_1(s,0)=0$ and $\ell_1(s,1)=1+s$. The step-2 state records $(s_1,a_1)$, and $\ell_2$ is action-independent with $\ell_2((s,1),\cdot)=-ms$ and $\ell_2((s,0),\cdot)=0$. Let $\pi_1(1\mid s)=s$ (invest exactly when $s=1$); $\pi_2$ is arbitrary. Then $\bar p_1=(1/2,1/2)$.

Myopic term. At $t=1$, $\operatorname{tr}\operatorname{Cov}(\ell_1(s,\cdot),z_1)=\operatorname{Cov}(1+s,s)=\operatorname{Var}(s)=1/4$, since the $a=0$ coordinate is constant. At $t=2$, the cost vector is constant across actions, so its covariance with $z_2$ vanishes because $\langle\mathbf{1},z_2-\bar p_2\rangle=0$.

True value. $Q_1^\nu(s,0)=0$ and $Q_1^\nu(s,1)=1+s-ms$. By Theorem 3.4, $J(\pi)-J(\nu)=\operatorname{Cov}(1+(1-m)s,s)=(1-m)/4$; the step-2 term vanishes for the same reason as before.

The ratio between the two quantities, $(1-m)$, is unbounded as $m\to\infty$. Swapping the roles of the costs gives the reverse failure: a myopic audit that certifies value for a policy that destroys it.

Information limits of adaptivity

Proof. Fix $t$ and write $P = P_t$ and $\widetilde{P} = P_t^s \otimes P_t^a$. If $d_t^\pi(s) > 0$ and $\pi_t(a \mid s) > 0$ then $\bar{p}_t(a) \ge d_t^\pi(s)\pi_t(a \mid s) > 0$, so both $P$ and $\widetilde{P}$ are supported on $\Omega= \operatorname{supp} d_t^\pi\times\operatorname{supp} \bar{p}_t$. For $s \in\operatorname{supp} d_t^\pi$ let $g(s)$ be the midpoint of $\{Q_t^\nu(s,a) : a \in\operatorname{supp} \bar{p}_t\}$, and set $f(s,a) = Q_t^\nu(s,a) - g(s)$. Then $f$ takes values in $[-\operatorname{span}_t/2,\operatorname{span}_t/2]$ on $\Omega$. By Theorem 3.4, the $t$-th summand equals $\mathbb{E}_P f - \mathbb{E}_{\widetilde{P}}f$. For any $f$ with values in an interval of length $L$, $|\mathbb{E}_P f - \mathbb{E}_{\widetilde{P}}f| \le L \cdot\operatorname{TV}(P,\widetilde{P})$. By Pinsker’s inequality [8],

Sum over $t$ and use the triangle inequality.

Proof. Let $H = 1$, $s \sim\operatorname{Uniform}\{0,1\}$, $\mathcal{A} = \{0,1\}$, $\ell(s,a) = \mathbf{1}\{a \ne s\}$, and $\pi(a = s \mid s) = (1+\epsilon)/2$ for $\epsilon\in(0,1)$. Then $\bar{p} = (1/2,1/2)$, $Q^\nu= \ell$, and $\operatorname{span}_1 = 1$. Moreover, $J(\pi) = (1-\epsilon)/2$ and $J(\nu) = 1/2$, so $|J(\pi)-J(\nu)| = \epsilon/2$. The mutual information is that of a binary symmetric channel with uniform input:

Hence $\sqrt{I/2} = \frac{\epsilon}{2}(1+O(\epsilon^2))$, and the ratio tends to 1 as $\epsilon\to0$.

Proof. Combine Theorem 3.7 ($\operatorname{Gap}(M) \le-\Delta(\pi^*) \le|\Delta(\pi^*)|$) with Theorem 4.2.

Proof. $Q_t^\nu\in[0,H-t+1]$, so $\operatorname{span}_t \le H-t+1$. By Theorem 4.2, $J(\pi) \ge J(\nu^\pi)-\sum_t(H-t+1)\sqrt{R_t/2}$, and $J(\nu^\pi) \ge J(\nu^\star)$.

Remark 4.6 (Sub-Gaussian refinement). The proof of Theorem 4.2 only uses a change of measure between $P$ and $\widetilde{P}$. If $f=Q_t^\nu-g_t$ is $\sigma_t$-sub-Gaussian under $\widetilde{P}$, the Donsker–Varadhan argument of [23, 29] gives $\lvert\mathbb{E}_P f-\mathbb{E}_{\widetilde{P}}f\rvert\le\sigma_t\sqrt{2I(s_t;a_t)}$. This can be much tighter than the span bound when $Q_t^\nu$ has rare extreme action values.

Remark 4.7 (Estimating the bound from data). With finitely many states, $I(s_t;a_t)$ is a plug-in quantity. When states are continuous, as with prices, inventories or market signals, the auditor can write $I(s_t;a_t)=\sum_a\bar{p}_t(a)[h(s_t)-h(s_t\mid a_t=a)]$ in terms of differential entropies of the state. Each entropy can be estimated from logged states using the weighted $k$-nearest-neighbor estimator of [5], which is efficient in low dimensions. Because the action is discrete and its propensities are logged, only the entropies of the state distribution need to be estimated.

The sample complexity of auditing

Contextual bandits

Setting. Contexts $x_t\sim\mathcal{D}$ are i.i.d. on a measurable space $\mathcal{X}$; given $x_t$, a cost vector $\ell_t\in[0,1]^\mathcal{A}$ is drawn from a conditional law with mean $c(x_t)$; the policy draws $a_t\sim\pi(\mathord\cdot\mid x_t)$, independently of $\ell_t$ given $x_t$. The auditor observes the log $\{(x_t,\pi(\mathord\cdot\mid x_t),a_t,\ell_t(a_t))\}_{t=1}^T$ (bandit feedback with logged propensities) and knows $\bar{p}=\mathbb{E}_x\pi(\mathord\cdot\mid x)$. The target is the per-round adaptivity cost

the $H=1$ case of Theorem 3.6. An auditor is $(\delta,\eta)$-accurate on an instance if its output $\widehat{\Delta}$ satisfies $\mathbb{P}(\lvert\widehat{\Delta}-\Delta(\pi)\rvert<\delta)\ge1-\eta$. Let $\bar{\chi}^2(\pi)=\mathbb{E}_x[\chi^2(\bar{p}\mathbin\Vert\pi(\mathord\cdot\mid x))]\in[0,\infty]$.

Remark 5.1 (Knowing $\bar{p}$). $\bar{p}$ depends only on $\pi$ and $\mathcal{D}$, not on costs, so it can be estimated to any accuracy from unlabelled contexts, which are cheap in most applications. We treat it as known to isolate the cost of missing counterfactual costs.

Proof. Take any instance with $c_a(x)\le1/2$, and modify it by adding $1/2$ to the mean of $\ell(a)$ for $x\in\mathcal{X}'$. The log never contains $\ell_t(a)$ for $x_t\in\mathcal{X}'$, so its law is unchanged. The first term of $\Delta(\pi)$ is unchanged because $\pi(a\mid x)=0$ on $\mathcal{X}'$; the second changes by $\bar{p}(a)\mathcal{D}(\mathcal{X}')/2\ne0$. For a deterministic policy with a non-constant action, pick $a$ with $0<\bar{p}(a)<1$ and $\mathcal{X}'=\{x:\pi(x)\ne a\}$, which has measure $1-\bar{p}(a)>0$.

Proof. Unbiasedness. Conditioning on $x$ and using independence of $a$ and $\ell$ given $x$,

Here $\bar\chi^2<\infty$ ensures $\pi(a\mid x)>0$ whenever $\bar p(a)>0$, for $\mathcal{D}$-almost every $x$. Taking expectations gives $\mathbb{E}Y_t=\Delta(\pi)$.

Variance. Since $\ell_t\in[0,1]$, $\operatorname{Var}(Y_t)\leq\mathbb{E}Y_t^2\leq\mathbb{E}(1-w_t)^2=\mathbb{E}w_t^2-2\mathbb{E}w_t+1$. Now $\mathbb{E}[w_t\mid x]=\sum_a\bar p(a)=1$ and $\mathbb{E}[w_t^2\mid x]=\sum_a\bar p(a)^2/\pi(a\mid x)=1+\chi^2(\bar p\Vert\pi(\cdot\mid x))$, so $\operatorname{Var}(Y_t)\leq\bar\chi^2(\pi)$.

Concentration. By Chebyshev’s inequality, each block mean deviates from $\Delta(\pi)$ by at least $\delta$ with probability at most $\bar\chi^2/(m\delta^2)\leq1/4$. The median fails only if at least $k/2$ of the $k$ independent blocks fail. By Hoeffding’s inequality this has probability at most $\exp(-2k(1/4)^2)=e^{-k/8}\leq\eta$ [20].

Proof. Instance. Let $\mathcal{X}=\{0,1\}$ with $\mathcal{D}$ uniform, $\mathcal{A}=\{1,2\}$, and for $p\in(0,1/4]$ let $\pi(\cdot\mid0)=(p,1-p)$ and $\pi(\cdot\mid1)=(1-p,p)$. Then $\bar p=(1/2,1/2)$ and

This is continuous and decreasing on $(0,1/4]$, takes the value $1/3$ at $p=1/4$, and diverges as $p\to0$. So for each $\Gamma\geq1/3$ there is $p$ with $\bar\chi^2=\Gamma$, and $\Gamma+1=1/(4p(1-p))\leq1/(3p)$.

For $\sigma\in\{+1,-1\}$ and $\epsilon=8\delta\leq1/4$, let instance $\sigma$ have $\ell(1)\sim\operatorname{Bern}(1/2)$ for both contexts, $\ell(2)\sim\operatorname{Bern}(1/2)$ when $x=0$, and $\ell(2)\sim\operatorname{Bern}(1/2+\sigma\epsilon)$ when $x=1$. Only action 2 has a context-dependent mean, so

and $|\Delta_+-\Delta_-|=\epsilon(1-2p)/2\geq\epsilon/4=2\delta$.

Divergence. The laws of $(x_t,\pi(\cdot\mid x_t),a_t)$ coincide under both instances, and the law of $\ell_t(a_t)$ differs only on the event $\{x_t=1,a_t=2\}$, which has probability $p/2$. On that event, using $\operatorname{KL}\leq\chi^2$,

By the chain rule and independence across rounds,

Testing. Given a $(\delta,\eta)$-accurate auditor, let $\psi=+$ if $|\widehat{\Delta}-\Delta_+|<\delta$ and $\psi=-$ otherwise. Since $|\Delta_+-\Delta_-|\geq2\delta$, $\mathbb{P}_+(\psi=-)\leq\eta$ and $\mathbb{P}_-(\psi=+)\leq\eta$. The Bretagnolle–Huber inequality [6, 26] gives $2\eta\geq\frac{1}{2}\exp(-\operatorname{KL})$, so

Using $1/p\geq3(\Gamma+1)$,

Theorems 5.3 and 5.4 together show that $\bar\chi^2(\pi)$ is the right complexity parameter: the uniform upper bound $O(\bar\chi^2\log(1/\eta)/\delta^2)$ is matched, up to constants, at every value of $\bar\chi^2\geq1/3$. Theorem 5.2 is the $\bar\chi^2=\infty$ endpoint. A practical reading for audit design is that a policy can be audited from its own logs only if it explores, and the cost of auditing grows inversely with its exploration probability on the actions it marginally uses.

Episodic MDPs

Now the auditor observes $n$ i.i.d. episodes $\tau=(s_1,a_1,\ell_1,\ldots,s_H,a_H,\ell_H)$ generated by $\pi$, with logged propensities, and knows $(\bar{p}_t)_{t\le H}$. Assume costs lie in $[0,1]$ and the following overlap condition.

Proof. Support. Every trajectory with positive probability under $\nu$ has positive probability under $\pi$. By induction on $t$: $s_1\sim\rho$ under both; if the prefix up to $s_t$ is $\pi$-possible, then $s_t\in\operatorname{supp}d_t^\pi$, and any $a_t$ with $\bar{p}_t(a_t)>0$ has $\pi_t(a_t\mid s_t)>0$ by Theorem 5.5, so $(s_t,a_t)$ and any $s_{t+1}$ in the support of $P_t(\cdot\mid s_t,a_t)$ are $\pi$-possible. The transition factors cancel in $dP^\nu/dP^\pi$, which therefore equals $W$. Hence $\mathbb{E}_{\pi}[LW]=\mathbb{E}_{\nu}L=J(\nu)$, $\mathbb{E}_{\pi}L=J(\pi)$, and $\mathbb{E}_{\pi}Y=J(\pi)-J(\nu)$.

Variance. $L\in[0,H]$, so $\operatorname{Var}(Y)\le H^2\mathbb{E}_{\pi}(1-W)^2=H^2(\mathbb{E}_{\pi}W^2-1)=H^2\chi^2(P^\nu\mathbin\Vert P^\pi)$, using $\mathbb{E}_{\pi}W=1$.

Factorization. Let $w_t=\bar{p}_t(a_t)/\pi_t(a_t\mid s_t)$ and let $\mathcal{F}_t$ be generated by the history up to $s_t$. Then $\mathbb{E}_{\pi}[w_t^2\mid\mathcal{F}_t]=1+\chi^2(\bar{p}_t\mathbin\Vert\pi_t(\cdot\mid s_t))\le1+M_t$, where $M_t$ is the maximum in the statement. By the tower property, $\mathbb{E}_{\pi}\prod_{t\le H}w_t^2=\mathbb{E}_{\pi}\left[\prod_{t<H}w_t^2\mathbb{E}_{\pi}[w_H^2\mid\mathcal{F}_H]\right]\le(1+M_H)\mathbb{E}_{\pi}\prod_{t<H}w_t^2$. Induct.

Concentration. This is identical to Theorem 5.3, with variance bound $H^2\chi^2(P^\nu\mathbin\Vert P^\pi)$ in place of $\bar{\chi}^2$.

The product bound is exponential in $H$ unless the per-step divergences are $O(1/H)$. General OPE lower bounds for tree-structured MDPs are also exponential in $H$ [15]. Because the target $\nu^\pi$ is a very special policy. However, those lower bounds do not apply directly.

Numerical illustration

We illustrate the theorems on three small examples; the code is seeded and runs in seconds. (i) For the sharpness family of Theorem 4.3, the ratio in Theorem 4.2 is 0.978, 0.997, 0.9992 and 0.99999 at $\epsilon=0.5$, 0.2, 0.1, 0.01. (ii) On the lower-bound family of Theorem 5.4 with $\epsilon=0.1$ and $p\in\{0.2,0.1,0.05,0.02\}$ ($\bar{\chi}^2\in[0.56,11.8]$), the root-mean-squared error of the IPW mean, over 2,000 replications at $T\in\{10^3,10^4\}$, equals $(0.72$–$0.76)\sqrt{\bar{\chi}^2/T}$ in every configuration, matching the $\sqrt{\bar{\chi}^2/T}$ rate of Theorem 5.3. (iii) Table 1 reports a 20-step lost-sales inventory MDP (capacity 12, orders 0–6, Poisson(3) demand, order cost 1, holding cost 0.5, lost-sale penalty 6), computed exactly by dynamic programming. The covariance identity holds to $10^{-13}$. The myopic audit understates adaptive value by 22–78%, and the information bound holds with slack, as expected of a worst-case bound when $I(s_t;a_t)$ is large.

Policy	$J(\pi)$	$J(\nu^\pi)$	$\Delta(\pi)$	Myopic	$\sum_t I_t$	Info. bound on $|\Delta|$
Optimal (DP)	92.66	130.14	$-37.48$	$-29.36$	32.5	285.9
Base-stock 6	94.63	131.41	$-36.78$	$-21.43$	35.0	292.1
Noisy base-stock 6	98.99	136.10	$-37.11$	$-24.05$	11.2	172.8
Base-stock 9	121.63	134.68	$-13.06$	$-2.90$	35.1	286.8
Random closed-loop	137.87	140.51	$-2.64$	$-1.89$	5.5	112.7