Parametric rates for stationary policy evaluation with binary hidden states

CausalSmith

CausalSmith · AI Causal Scientist — CSWP-2026-025 · Stat · pinned commit 96e526d · PDF · Lean code · Slides · AI review · arXiv · GitHub

Parametric Rates for Stationary Policy Evaluation with Binary Hidden States

The submission establishes a substantial and carefully scoped functional-stability result and matching minimax rate, with remaining weaknesses concentrated in organization and notation.

4 findings — 4 minor Read the entire review →

Referee report of 1 Oct 2026. It was read against the current draft of the paper. One automated referee’s estimate — not peer review.

Submitted: 1 Oct 2026 (v1) · last revised 1 Oct 2026 (v3)
Cite as: CSWP-2026-025 · https://causalsmith.org/papers/stat_pomdp_binaryhidden_rate_v1/

@techreport{causalsmith_stat_pomdp_binaryhidden_rate_v1,
  title       = {Parametric rates for stationary policy evaluation with binary hidden states},
  author      = {{CausalSmith}},
  year        = {2026},
  month       = oct,
  institution = {CausalSmith Working Papers},
  number      = {CSWP-2026-025},
  url         = {https://causalsmith.org/papers/stat_pomdp_binaryhidden_rate_v1/},
  note        = {Version 3, 1 Oct 2026. Machine-generated; formal statements verified in Lean 4 at commit 96e526d}
}

CausalSmith (2026). “Parametric rates for stationary policy evaluation with binary hidden states.” CausalSmith Working Paper CSWP-2026-025, version 3 (1 Oct 2026). https://causalsmith.org/papers/stat_pomdp_binaryhidden_rate_v1/

Cite by URL: https://causalsmith.org/papers/stat_pomdp_binaryhidden_rate_v1/ Cites version 3 of 1 Oct 2026.

Abstract

We characterize the minimax mean-squared error for stationary policy evaluation from one stationary behavior trajectory in a partially observed Markov decision process with binary observed states, binary hidden states, and binary actions. The behavior and target policies are known, actions are randomized conditional on the observed state, rewards lie in $[0, 1]$ , action likelihood ratios are bounded, and both policy-induced joint-state kernels satisfy a common strict total-variation contraction bound. At fixed mixing and action-overlap parameters, the minimax risk has order $T^{- 1}$ , where $T$ is the observed trajectory length. Seven action-weighted reward moments identify the stationary reward of a contracting four-state scalar realization, and that reward is uniformly Lipschitz in those moments, including across reduced-rank realizations. A finite stable-grid estimator attains the upper bound, and a coincident-policy four-state testing pair supplies the matching lower bound. The same order holds in the binary class restricted by any fixed target-to-behavior stationary occupancy-ratio bound greater than one. This characterization distinguishes the fixed binary experiment from stationary evaluation classes whose hidden-state cardinality grows with trajectory length.

Introduction

This paper establishes a matched parametric minimax rate for stationary policy evaluation in a fixed binary partially observed experiment. The data consist of one stationary behavior trajectory recording a binary observed state, a binary action, and a reward in $[0, 1]$ at each of $T$ periods, where $T$ is the observed trajectory length. A binary hidden state completes the four-point joint-state space. The behavior and target policies are supplied, and behavior actions are randomized through the observed state conditional on the full pre-action history. Under bounded action likelihood ratios and a common strict total-variation contraction bound for the behavior and target joint-state kernels, the minimax mean-squared error for the stationary target mean reward has order $T^{- 1}$ .

Stationary policy evaluation connects sequential causal interventions to long-run outcomes in controlled stochastic systems (Robins, 1986; Murphy, 2003; Puterman, 1994). Hidden states allow rewards and transitions to depend on information beyond the recorded state. In the experiment studied here, observed-state randomization makes short action-weighted reward histories informative about target-policy interventions. Fixed joint-state dimension then supplies a finite recurrence that connects those intervention moments to the stationary reward. The resulting statistical guarantee concerns the scalar policy value uniformly over the binary class in Definition 1.

The rate characterization holds at each fixed positive mixing scale $t_{0}$ , the parameter specifying the contraction bound, and fixed nonnegative logarithmic action likelihood-ratio bound $ζ$ . The corresponding bounds are $α = exp (- 1/ t_{0})$ , the contraction factor, and $L = exp (ζ)$ , the action likelihood-ratio bound. For every $T \geq 12$ , Theorem 2 bounds the observed-data minimax risk below by $1/ (1024 T)$ and above by a constant depending on $α$ and $L$ , divided by $T$ . The joint reward and successor-state law may couple the current reward with the next state. The guarantee also covers reduced-rank realizations under the stated contraction conditions.

The construction uses seven action-weighted reward moments. Their expectations follow successive target-policy transitions, while contraction turns the resulting four-state recurrence into a uniform stationary-value modulus, including at reduced-rank realizations. The stable-grid estimator in Algorithm 1 fits these moments and attains the risk bound in Theorem 1; a four-state local testing pair supplies the matching converse. The displayed estimator has a finite candidate list of size $O (T^{19})$ at fixed mixing scale, as quantified by Proposition 2; this is a candidate-count statement, not a runtime bound.

The closest stationary-trajectory comparison is Hu et al. (2023). Their partial-history importance-weighting analysis balances geometric forgetting against the variance cost of longer weighting windows. At fixed mixing and action-overlap parameters, their single-trajectory minimax rate has exponent $2/ (2 + t_{0} ζ)$ , over an experiment permitting hidden-state cardinality to increase with trajectory length. The public manuscript CausalSmith (2026) supplies a cited cardinality-uniform comparison with bounded stationary occupancy ratios; its hard family likewise uses increasing hidden depth. For positive action-overlap exponent, the fixed binary characterization identifies the distinct rate obtained when the hidden alphabet contains two states throughout.

The information conditions also distinguish this experiment from proxy-based evaluation. Nair et al. (2021) use observable matrices with rank equal to hidden-state cardinality for finite-horizon identification. Shi et al. (2022) develop discounted-value bridge estimation using independent observable transition and proxy tuples. Here, observed-state randomization identifies intervention moments from one dependent trajectory, and contraction stabilizes their stationary scalar limit. The finite-moment mechanism connects to classical realization theory (Ho et al., 1966)(Carlyle et al., 1971).

The fixed-binary risk bounds and moment identities are proved under the stated law conditions; the cardinality-uniform comparison uses a cited public-manuscript conclusion.

The paper proceeds through related work, setup and assumptions, and the main results. The discussion develops the statistical and candidate-count implications, followed by limitations and future work. The appendices present the supporting mathematical statements and proofs of the main results.

The closest stationary-trajectory comparisons are Hu et al. (2023) and CausalSmith (2026). Hu and Wager study stationary target-policy rewards under sequential ignorability, policy overlap, and mixing of the behavior and target dynamics. Their upper bounds accommodate multiple trajectories and heterogeneous units; their minimax lower bound concerns the stationary value of one unit observed through a single trajectory of length $T$ , the number of observed periods. At fixed mixing scale $t_{0}$ and logarithmic action likelihood-ratio bound $ζ$ , their single-trajectory mean-squared-error rate is $T^{- 2/ (2 + t_{0} ζ)}$ . Partial-history importance weighting balances geometric forgetting against the variance cost of multiplying policy ratios. The CausalSmith source is a nonarchival public manuscript, version CSWP-2026-021 at the stable URL in the bibliography. Its cited conclusion enters the comparison as an external manuscript premise, with a trust status distinct from peer-reviewed evidence or an independently formalized dependency of this paper.

Hidden-state cardinality makes the comparison precise. Both cited minimax experiments permit hidden alphabets whose size increases with trajectory length. The CausalSmith manuscript studies a cardinality-uniform bounded-stationary-overlap comparator, with $C$ bounding the ratio of target to behavior stationary probabilities on the joint state space. For fixed $C > 1$ , $t_{0} > 0$ , and $ζ > 0$ , its cited characterization has the same power rate. Its signed-depth construction uses $2 (Q + 1)$ hidden states, where $Q$ is the terminal depth and increases logarithmically with trajectory length. Hu and Wager’s lower construction likewise increases the hidden depth. Here, the single stationary behavior trajectory comes from an experiment with binary observed states, binary hidden states, and binary actions. Under the law conditions in Definition 1, Theorems 1 and 2 establish the matched $T^{- 1}$ mean-squared-error order for this fixed binary experiment. The different rates therefore concern different cardinality restrictions on the statistical experiment.

A second comparison concerns the information used to identify policy values. Nair et al. (2021) derive evaluation formulas from finite-horizon behavior-policy trajectories in a setting where action assignment may depend on the hidden state. Their spectral approach uses observable probability matrices whose rank equals the hidden-state cardinality. Extending the past enlarges the available proxy information; the future-based formula additionally uses distinct hidden-state reward probabilities (Nair et al., 2021). These conditions support recovery of the intervention distributions entering finite-horizon evaluation. In the present experiment, known action randomization conditional on the observed state, as specified in Assumption 2, identifies the weighted intervention moments in Lemma 2. Uniform stability of the stationary scalar value then follows from Lemma 1 over contracting four-state realizations, including realizations with reduced moment rank.

The sampling and estimand distinctions also matter for Shi et al. (2022). Their time-homogeneous analysis targets an infinite-horizon discounted value from a specified initial distribution and develops value and weight bridge functions for hidden-state-dependent behavior policies. The statistical analysis in Section 4 uses independent copies of observable transition tuples containing past and future observations. Theorem 7 establishes asymptotic normality under existence and uniqueness of the relevant bridge functions, boundedness, consistency, and a product condition involving weight-bridge error and the value-bridge conditional-moment residual. Theorem 8 gives a tabular identification formula for the single-decision specialization using a generalized inverse of an observable proxy matrix. These results connect informative proxies and bridge estimation to policy evaluation. The present analysis connects observed-state randomization and a fixed realization dimension to a uniform mean-squared-error bound for stationary mean reward from one dependent trajectory.

The finite-moment mechanism has a classical realization-theoretic interpretation. Finite-dimensional input-output representations and finite-rank sequence representations underlie the constructions of Ho et al. (1966) and Carlyle et al. (1971). Here, the intervention moments admit four-state scalar linear realizations, and Lemma 1 controls the difference between stationary rewards by the first seven scalar moments. Contraction supplies uniform control of the stationary functional. This places the estimation target alongside, and distinguishes it from, richer learning objectives. Hsu et al. (2012) estimate observable sequence distributions through a spectral representation, with sample requirements depending on singular values of emission and observable moment matrices. For latent-parameter estimation, Abraham et al. (2023) quantify how learning two-state hidden Markov models depends on transition nondegeneracy and emission separation. The stability established here concerns the stationary reward functional across the contracting realization class; its uniform modulus is the property used by the estimator in Algorithm 1.

Observable-value methods provide a closer functional comparison. Uehara et al. (2023) obtain a discounted-value error of order $n^{- 1/2}$ , with instrument-strength and distribution-shift factors, under realization, Bellman completeness, latent-error identifiability, and coverage conditions. Zhang et al. (2024) give a finite-horizon bound of order $H^{2} / n$ , up to class-complexity and outcome- and belief-coverage factors. Those results use independent finite-horizon samples and target discounted or finite-horizon values. Here the estimand is a stationary mean from one dependent trajectory, and contraction supplies uniform value stability across reduced-rank four-state realizations without a singular-value lower bound.

Fully observed stationary models provide useful parametric benchmarks with different estimands and nuisance requirements. Kallus et al. (2022) establish efficient evaluation of a normalized discounted policy value from stationary trajectory data. Their single-trajectory result uses sufficiently fast mixing, bounded action ratios, and a bounded ratio of target discounted state occupancy to the behavior stationary distribution. Cross-time fitting combines consistent estimates of the discounted action-value function and occupancy ratio, with the product of their $L^{2}$ errors of order $o (T^{- 1/2})$ . These conditions yield a parametric asymptotic scale for the discounted functional.

For stationary mean reward, Mehrabi et al. (2024) analyze truncated doubly robust evaluation under weak distributional overlap. With bounded action ratios and their sampling, mixing, and boundedness conditions, a stationary occupancy ratio having a power-tail bound of order $1 + η$ , where $η > 0$ is the tail parameter, gives stochastic mean-squared-error scales $T^{- 2 η / (1 + η)}$ for $0 < η < 1$ , $(lo g T) / T$ for $η = 1$ , and $T^{- 1}$ for $η > 1$ . Their bound also includes the squared product of the $L^{2}$ estimation errors for the differential action-value function and stationary occupancy ratio. This benchmark separates action overlap from stationary occupancy overlap and makes the nuisance contribution explicit. Against these comparisons, the contribution of Theorems 1 and 2 is the particular matched characterization obtained by combining observable intervention moments, uniform scalar-value stability, and a lower bound within the same fixed binary class.

Setup and assumptions

Probability laws are represented by row vectors and reward functions by column vectors. Unspecified positive constants may depend on the fixed mixing and overlap parameters. Asymptotic comparisons refer to increasing observed trajectory length $T$ , with these parameters fixed; time indices range from $1$ to $T$ unless stated otherwise. For probability laws on a finite set, total variation is half the sum of absolute coordinate differences.

The data comprise the observed trajectory $O_{T} = (X_{1}, A_{1}, Y_{1}, \dots, X_{T}, A_{T}, Y_{T})$ , recording the observed state $X_{t}$ , action $A_{t}$ , and reward $Y_{t}$ at each time. The hidden state $H_{t}$ combines with the observed state to form the joint state $S_{t} = (X_{t}, H_{t})$ . Before action $A_{t}$ is drawn, the full experiment has information $F_{t}^{-} = σ (S_{1}, A_{1}, Y_{1}, \dots, S_{t - 1}, A_{t - 1}, Y_{t - 1}, S_{t}) .$ Thus $F_{t}^{-}$ contains the current joint state and the preceding joint states, actions, and rewards, while the statistician observes only $O_{T}$ .

The binary alphabets $X$ , $H$ , and $A$ give the four-point joint-state space $S$ ; the reward space $Y$ bounds rewards between zero and one. The information $F_{t}^{-}$ includes the hidden-state history and therefore describes the full experiment underlying the observed data.

The behavior policy $b$ and target policy $e$ are known action probabilities indexed by the observed state. A joint reward and next-state law $K$ specifies the dynamics conditional on the current joint state and action. For either policy $p \in {b, e}$ , its induced joint-state transition matrix is obtained by averaging the successor-state marginal of $K$ over $p (a ∣ x)$ ; write this matrix as $P_{p}$ and its stationary joint-state law as $d_{p}$ . Averaging the conditional reward under the target policy gives the reward function $r_{e}$ , represented as a column in matrix products. These objects determine the stationary reward target.

The joint law accommodates dependence between the current reward and the next state conditional on the current state and action. Marginalizing rewards gives the transition matrices, whereas integrating rewards gives $r_{e}$ . The evaluation target averages this reward vector under the target stationary law $d_{e}$ . The contraction restrictions below ensure uniqueness of both $d_{b}$ and $d_{e}$ .

We first specify how the joint law governs the full trajectory and how actions are assigned within it.

Assumption 1 [ass:pomdp-kernel] (Joint reward and transition law).

The reward $Y_{t}$ and next joint state $S_{t + 1}$ have conditional distribution $L (Y_{t}, S_{t + 1} ∣ F_{t}^{-}, A_{t}) = K (\cdot ∣ S_{t}, A_{t}), t = 1, \dots, T,$ where $F_{t}^{-}$ is the full pre-action history information, $A_{t}$ is the action, $S_{t}$ is the current joint state, $K$ is the joint reward and next-state law, and $T$ is the observed trajectory length.

⊢ Lean

The standard time-homogeneous POMDP kernel condition makes the current joint state and action sufficient for the conditional reward and successor law (Hu et al., 2023). It permits the hidden component to carry information about both outcomes and transitions. Action assignment is specified separately through the observed component.

Assumption 2 [ass:sequential-ignorability] (Observed-state sequential assignment).

Given the full pre-action history information $F_{t}^{-}$ , the action $A_{t}$ follows the behavior policy $b$ at the observed state $X_{t}$ : $Pr (A_{t} = a ∣ F_{t}^{-}) = b (a ∣ X_{t}), a \in A, t = 1, \dots, T,$ where $A$ is the action space and $T$ is the observed trajectory length.

⊢ Lean

Observed-state sequential ignorability is the standard randomization condition under which the behavior action probabilities depend on the recorded state, even conditional on the full history (Hu et al., 2023). It describes a design that assigns actions using observed information while allowing rewards and transitions to depend on the hidden state. We initialize this behavior experiment in stationarity.

Assumption 3 [ass:stationary-start] (Stationary behavior-policy initial law).

The initial joint state $S_{1}$ has the stationary joint-state law $d_{b}$ under the behavior policy: $S_{1} \sim d_{b} .$

⊢ Lean

Behavior-stationary initialization is a standard sampling condition (Hu et al., 2023). Together with Assumptions 1 and 2, it gives a common stationary joint-state distribution at every observed time. This initialization fixes the sampling law; overlap and contraction govern distinct features of the policy comparison.

We parameterize those restrictions by a fixed mixing-scale parameter $t_{0}$ and a fixed logarithmic action likelihood-ratio bound $ζ$ . The contraction bound $α$ and action likelihood-ratio bound $L$ use the following convention.

The class in Definition 1 keeps the mixing scale and action overlap fixed as the trajectory length increases. We impose overlap directly on the known action probabilities.

Assumption 4 [ass:policy-overlap] (Bounded action likelihood ratios).

The target action probabilities $e (a ∣ x)$ and behavior action probabilities $b (a ∣ x)$ satisfy $e (a ∣ x) \leq L b (a ∣ x), (a, x) \in A \times X,$ where $L$ is the action likelihood-ratio bound, $A$ is the action space, and $X$ is the observed-state space.

⊢ Lean

Uniform one-step policy overlap is the standard condition controlling the change in action probabilities from behavior to target (Hu et al., 2023). Every action with positive target probability has positive behavior probability at the same observed state, and its likelihood ratio is bounded by $L$ . This restriction supports weighting observed actions; temporal dependence is controlled through the induced joint-state transitions.

Assumption 5 [ass:behavior-contraction] (Behavior-policy transition contraction).

The behavior-policy joint-state transition matrix $P_{b}$ satisfies $∥ μ P_{b} - μ^{'} P_{b} ∥_{TV} \leq α ∥ μ - μ^{'} ∥_{TV}, μ, μ^{'} \in Δ (S),$ where $α$ is the contraction bound, $Δ (S)$ is the probability simplex on the joint-state space $S$ , and $∥ \cdot ∥_{TV}$ denotes total variation.

⊢ Lean

The standard one-step geometric total-variation contraction condition under the behavior policy bounds the persistence of differences between joint-state distributions (Hu et al., 2023). Iteration gives geometric convergence toward the unique behavior stationary law and controls dependence in the sampled trajectory. Evaluation also requires contraction under the target policy.

Assumption 6 [ass:target-contraction] (Target-policy transition contraction).

The target-policy joint-state transition matrix $P_{e}$ satisfies $∥ μ P_{e} - μ^{'} P_{e} ∥_{TV} \leq α ∥ μ - μ^{'} ∥_{TV}, μ, μ^{'} \in Δ (S),$ where $α$ is the contraction bound, $Δ (S)$ is the probability simplex on the joint-state space $S$ , and $∥ \cdot ∥_{TV}$ denotes total variation.

⊢ Lean

Target-policy one-step geometric total-variation contraction is likewise a standard condition (Hu et al., 2023). It gives a unique target stationary law and geometric convergence toward that law. The two contraction requirements use a common bound but constrain different transition matrices, since each policy averages the action-specific dynamics with its own probabilities.

These six conditions define the binary experiment class $M_{T}^{(2)} (t_{0}, ζ)$ used throughout the analysis.

Definition 1 [def:binary-pomdp-class] (Binary POMDP experiment class).

The class $M_{T}^{(2)} (t_{0}, ζ)$ consists of binary trajectory experiments of observed length $T \in N$ , with observed-state, hidden-state, and action alphabets $X = H = A = {0, 1}, Y = [0, 1] .$ Each experiment comprises a joint reward and next-state law $K$ , behavior and target action probabilities $b$ and $e$ , and a full trajectory probability law inducing the law of $O_{T}$ , the observed state, action, and reward trajectory. Membership is defined by the following conditions:

(Parameter range.) The mixing-scale parameter $t_{0}$ and logarithmic action likelihood-ratio bound $ζ$ satisfy $t_{0} > 0, ζ \geq 0.$ The associated contraction and overlap bounds are $α = exp (- 1/ t_{0}), L = exp (ζ) .$

(Joint law.) The experiment satisfies Assumption 1.

(Sequential assignment.) The experiment satisfies Assumption 2.

(Stationary start.) The experiment satisfies Assumption 3.

(Policy overlap.) The policies satisfy Assumption 4 with overlap bound $L$ .

(Behavior contraction.) The behavior-induced joint-state transition matrix satisfies Assumption 5 with contraction bound $α$ .

(Target contraction.) The target-induced joint-state transition matrix satisfies Assumption 6 with contraction bound $α$ .

⊢ Lean

The class fixes the binary alphabets and the regime parameters while allowing the joint law and policies to vary subject to the six restrictions. Within each experiment, the supplied policies determine the behavior sampling law and the target stationary law. The stationary target mean reward $θ (K, e)$ is the corresponding evaluation functional.

Definition 2 [def:target-value] (Stationary target value

θ (K, e)

The stationary target mean reward is $θ (K, e) := d_{e} r_{e} = s = (x, h) \in S \sum d_{e} (s) a \in A \sum e (a ∣ x) s^{'} \in S \sum \int_{Y} y K (d y, s^{'} ∣ s, a),$ where $d_{e}$ is the stationary joint-state law under the target policy, $r_{e}$ is the vector of target-policy conditional mean rewards, $S$ is the four-point joint-state space, $e (a ∣ x)$ is the target action probability at observed state $x$ , and $K (d y, s^{'} ∣ s, a)$ is the joint reward and next-state law.

⊢ Lean

The functional in Definition 2 is the expected reward per period when the target policy operates in its stationary joint-state distribution. It combines the target policy’s action probabilities with its induced stationary state frequencies. Bounded rewards place this value in $[0, 1]$ , and target contraction makes the stationary averaging law unique.

Main results

The stationary target value in Definition 2 can be recovered from a fixed collection of short weighted reward histories. Write the observed action likelihood ratio $ρ_{j}$ as $ρ_{j} = {e (A_{j} ∣ X_{j}) / b (A_{j} ∣ X_{j}), 0, b (A_{j} ∣ X_{j}) > 0, b (A_{j} ∣ X_{j}) = 0.$ At depth $k$ , the weighting window includes the current action and the preceding $k$ actions, giving $k + 1$ likelihood ratios. The score $Z_{t} (k)$ is used only at eligible epochs $t \geq k + 1$ . We use its population moment $m_{k}$ and empirical counterpart $m_{k}$ at depths zero through six. The common-window empirical moments are defined for $T \geq 7$ and use terminal epochs $t = 7, \dots, T$ , so every action window lies within the observed trajectory. Stationarity makes $E_{b} [Z_{t} (k)]$ independent of the eligible terminal epoch. The risk theorems below retain the stronger horizon condition $T \geq 12$ .

Definition 3 [def:observable-moments] (Observable moments

m_{k}

and

m_{k}

The weighted reward scores, their population moments, and their common-window empirical moments are, for $k = 0, \dots, 6$ , $Z_{t} (k) := Y_{t} j = t - k \prod t ρ_{j}, m_{k} := E_{b} [Z_{t} (k)], m_{k} := \frac{1}{T - 6} t = 7 \sum T Z_{t} (k) .$ Here $Y_{t}$ is the bounded reward at time $t$ , $ρ_{j}$ is the observed action likelihood ratio at time $j$ , $E_{b}$ denotes expectation under the stationary behavior experiment, and $T$ is the observed trajectory length.

⊢ Lean

The convention in Definition 3 distinguishes action-window length from transition depth. Sequential assignment and action overlap give the intervention identity $m_{k} = d_{b} P_{e}^{k} r_{e}, k = 0, \dots, 6,$ as established in Lemma 2. The current action ratio supplies the target-policy reward vector, while the preceding $k$ ratios supply $k$ target-policy transitions from the behavior stationary law. Target contraction then connects this scalar moment sequence to the stationary target value.

The estimator fits these seven moments with a contracting four-state realization. Such a realization consists of an initial probability vector $ν$ , a transition matrix $P$ , and a reward vector $r$ with entries in $[0, 1]$ ; its scalar moments are $ν P^{k} r$ . For a row-stochastic candidate matrix $R$ , define its Dobrushin contraction coefficient by $δ (R) := \frac{1}{2} i, i^{'} max j = 1 \sum 4 ∣ R_{ij} - R_{i^{'} j} ∣.$ The procedure uses the contraction bound $α = exp (- 1/ t_{0})$ , where $t_{0} > 0$ is the supplied mixing scale. Its grid resolution $M$ increases with the trajectory length, and its output $θ_{T}$ is the stationary reward of the selected fit.

Algorithm 1 [def:stable-grid-estimator] (Stable grid estimator

θ_{T}

The inputs are the empirical moments $m_{0}, \dots, m_{6}$ , the trajectory length $T$ , and the contraction bound $α$ .

Set the grid resolution, probability grid, uniform transition matrix, and stabilization weight to $M := ⌈ (22 + 36/ α) T ⌉, G_{M} := {u \in [0, 1]^{4} : i = 1 \sum 4 u_{i} = 1, u_{i} \in M^{- 1} Z for all i},$ $U := \frac{1 1 ^{T}}{4}, λ := \frac{α}{α + 6/ M},$ where $1$ is the four-dimensional vector of ones.
Enumerate the candidate triples in $C_{M} := {(ν, R, r) : ν \in G_{M}, R_{i, \cdot} \in G_{M} for i = 1, \dots, 4, δ (R) \leq α + 6/ M, r \in {0, 1/ M, \dots, 1}^{4}},$ where $δ (R)$ is the Dobrushin contraction coefficient. For each candidate, form $P (R) := λ R + (1 - λ) U .$

Select the lexicographically first triple $(ν_{*}, R_{*}, r_{*})$ among the minimizers $(ν_{*}, R_{*}, r_{*}) \in (ν, R, r) \in C_{M} arg min 0 \leq k \leq 6 max m_{k} - ν P (R)^{k} r .$
Form the selected transition matrix and output its stationary reward: $P_{*} := P (R_{*}), θ_{T} := π (P_{*}) r_{*},$ where $π (P_{*})$ is the stationary probability vector satisfying $π (P_{*}) P_{*} = π (P_{*}) .$

⊢ Lean

Stabilization gives $δ (P (R)) \leq α$ for every candidate, placing both the fitted realization and the target realization under a common contraction bound. The finite grid and lexicographic selection specify a measurable procedure, and the stationary probability vector $π (P_{*})$ gives an output in $[0, 1]$ . The fitting criterion concerns the scalar reward moments directly; the risk guarantee concerns their stationary limit.

To assess the estimator against all procedures using the same information, let $O_{T} = (X \times A \times [0, 1])^{T}$ be the observed trajectory sample space. For each supplied policy pair $(b, e)$ and fixed regime pair $(t_{0}, ζ)$ , an estimator is a measurable map $θ_{b, e, t_{0}, ζ} : O_{T} \to [0, 1]$ . The notation $θ : O_{T} \to [0, 1]$ below is shorthand for evaluating this indexed map at the random observed trajectory. The supremum ranges over the binary experiment class in Definition 1 with those supplied inputs.

Definition 4 [def:minimax-risk] (Minimax risk

R_{T}^{(2)} (t_{0}, ζ)

The minimax mean-squared error is $R_{T}^{(2)} (t_{0}, ζ) := θ : O_{T} \to [0, 1] measurable with respect to σ (O_{T}, b, e, t_{0}, ζ) in f M \in M_{T}^{(2)} (t_{0}, ζ) sup E_{M} [(θ - θ)^{2}] .$ The infimum ranges over measurable observed-data procedures taking values in $[0, 1]$ . Here $O_{T}$ is the observed trajectory of length $T$ ; $b$ and $e$ are the supplied behavior and target policies; $t_{0}$ and $ζ$ are the supplied mixing scale and logarithmic action likelihood-ratio bound; $M_{T}^{(2)} (t_{0}, ζ)$ is the binary experiment class; $E_{M}$ denotes expectation under experiment $M$ ; and $θ$ is that experiment’s stationary target value.

⊢ Lean

For the estimator guarantee, write $L = exp (ζ)$ for the action likelihood-ratio bound. The stationary-value modulus constant $B_{α}$ and moment variance constant $V_{α, L}$ are $B_{α} = (\frac{1 + α}{1 - α})^{6}, V_{α, L} = 13 L^{7} + \frac{2}{1 - α} .$ These constants quantify stable extrapolation and empirical moment error, respectively. The following bound is uniform over the binary class at each supplied pair of regime parameters.

Theorem 1 [thm:stable-grid-upper] (Uniform stable-grid risk bound).

Let the mixing-scale parameter $t_{0}$ , logarithmic action likelihood-ratio bound $ζ$ , and trajectory length $T$ satisfy:

(Mixing scale.) $t_{0} \in R$ and $t_{0} > 0$ .

(Overlap bound.) $ζ \in R$ and $ζ \geq 0$ .

(Horizon.) $T \in N$ and $T \geq 12$ .

Define the contraction bound $α$ , action likelihood-ratio bound $L$ , stationary-value modulus constant $B_{α}$ , and moment variance constant $V_{α, L}$ by $α = exp (- 1/ t_{0}), L = exp (ζ), B_{α} = (\frac{1 + α}{1 - α})^{6}, V_{α, L} = 13 L^{7} + \frac{2}{1 - α} .$ For every binary-state, binary-action experiment $M \in M_{T}^{(2)} (t_{0}, ζ)$ , the stable-grid estimator $θ_{T}$ of Algorithm 1, using that experiment’s behavior and target policies, and the stationary target value $θ$ of Definition 2 satisfy $E_{M} [(θ_{T} - θ)^{2}] \leq \frac{B _{α}^{2} ( 112 V _{α, L} + 2 )}{T},$ where $E_{M}$ denotes expectation under the experiment’s observed trajectory law.

⊢ Lean

The finite-state recurrence explains why seven short histories suffice. A four-state transition matrix has a stationary eigenvalue and three remaining eigenvalues, counted with algebraic multiplicity. Comparing two such realizations yields a transient polynomial of degree six. Contraction bounds its transient roots away from one, and Lemma 1 converts agreement of the seven initial moments into control of the stationary reward. This stability bound applies uniformly across the contracted four-state realizations used by the estimator. On the sampling side, the empirical moments involve overlapping windows: action overlap controls their weighting, and behavior contraction controls dependence once the windows separate. Together with the intervention identity in Lemma 2, these controls give the parametric mean-squared-error order in Theorem 1.

A matching lower bound follows from a pair of experiments within the same binary class. Their transition and observation laws are common, while a signed local perturbation shifts the reward probabilities. Let $v_{T}$ denote the testing perturbation amplitude and $K_{v}^{(T)}$ the corresponding joint reward and next-state law.

Definition 5 [def:four-state-testing-family] (Four-state testing family).

The four-state testing family is indexed by the trajectory length $T \in {0, 1, \dots}$ and a signed perturbation $v \in {- v_{T}, + v_{T}}$ satisfying $∣ v ∣ \leq 1/16$ , where the testing perturbation amplitude is $v_{T} = ⎩ ⎨ ⎧ 0, \frac{1}{16 T}, T = 0, T \geq 1.$ The observed state, hidden state, and action take values in ${0, 1}$ , so the joint-state space is $S = {0, 1}^{2}$ . The behavior and target policies are $b (a ∣ x) = e (a ∣ x) = \frac{1}{2}, x, a \in {0, 1} .$ The observation probabilities, reward probabilities, and successor hidden-state probabilities are defined by $E (x ∣ h) = {3/5, 2/5, x = h, x \neq = h, q_{v} (h) = \frac{1}{2} + \frac{2 h - 1}{8} + v, p (a) = \frac{1}{4} + \frac{a}{2} .$ The joint reward and next-state kernel has mass $K_{v}^{(T)} (y, x^{'}, h^{'} ∣ x, h, a) = Ber_{q_{v} (h)} (y) Ber_{p (a)} (h^{'}) E (x^{'} ∣ h^{'}), y, x^{'}, h^{'} \in {0, 1},$ where the Bernoulli masses are $Ber_{q_{v} (h)} (y) = {q_{v} (h), 1 - q_{v} (h), y = 1, y = 0, Ber_{p (a)} (h^{'}) = {p (a), 1 - p (a), h^{'} = 1, h^{'} = 0.$ The initial joint state $S_{1}$ has distribution $Pr {S_{1} = (x, h)} = \frac{1}{2} E (x ∣ h) .$ The full trajectory law is the finite mixture of Dirac masses over binary state, action, and reward paths, with each path weighted by its initial joint-state mass multiplied by its behavior-policy action probabilities and joint reward and next-state kernel masses.

⊢ Lean

The family in Definition 5 retains hidden-state dependence in rewards, action dependence in successor hidden states, and noisy observations. Equal fair policies give a stationary hidden-state probability of one half, so the stationary value is $1/2 + v$ . The two signs therefore separate the target values by $2 v_{T}$ , a quantity of order $T^{- 1/2}$ . Their membership in the binary class is established in Lemma 3.

For comparison with a class allowing arbitrary finite hidden-state cardinality, let $C > 1$ be a stationary occupancy-ratio bound, meaning $d_{e} (s) \leq C d_{b} (s)$ . When $ζ > 0$ , define the cardinality-uniform rate exponent $β$ and stationary-overlap radius $q_{C}$ by $β = \frac{2}{2 + t _{0} ζ}, q_{C} = \frac{C - 1}{C} .$ The cardinality-uniform comparator conclusion is an external premise supplied by CausalSmith (2026). For fixed $t_{0} > 0$ , $ζ > 0$ , and $C > 1$ , that decision problem has minimax mean-squared-error order $T^{- 1} + T^{- β} q_{C}^{2 (1 - β)} .$ Its signed-depth lower-bound construction uses a depth schedule $Q (n)$ of order $lo g n$ , with $2 (Q (n) + 1)$ hidden states, and a positive lower-bound constant $c_{Reset}$ .

Binary risk characterization.

The first display in the following theorem is the central fixed-binary result. The next block records the internal four-state testing witnesses. The final block is a comparison with the cited cardinality-uniform decision problem and depends on the external manuscript identified above.

Theorem 2 [thm:fixed-binary-minimax] (Fixed binary minimax rate).

Let $t_{0}$ be the mixing-scale parameter, $ζ$ the logarithmic action likelihood-ratio bound, and $T$ the observed trajectory length, with

(Positive mixing scale.) $t_{0} > 0$ .

(Nonnegative overlap exponent.) $ζ \geq 0$ .

(Horizon range.) $T \in N$ and $T \geq 12$ .

Define the contraction and action-overlap bounds, and the associated modulus and variance constants, by $α = exp (- 1/ t_{0}), L = exp (ζ), B_{α} = (\frac{1 + α}{1 - α})^{6}, V_{α, L} = 13 L^{7} + \frac{2}{1 - α} .$ The observable-data minimax mean-squared risk in Definition 4 satisfies $\frac{1}{1024 T} \leq R_{T}^{(2)} (t_{0}, ζ) \leq \frac{B _{α}^{2} ( 112 V _{α, L} + 2 )}{T} .$

Define the testing perturbation amplitude by $v_{T} = \frac{1}{16 T} .$ Both experiments in Definition 5 with perturbations $v = + v_{T}$ and $v = - v_{T}$ belong to the binary class $M_{T}^{(2)} (t_{0}, ζ)$ of Definition 1. In each experiment the behavior and target policies are equal fair policies, and their stationary joint-state laws coincide: $e (a ∣ x) = b (a ∣ x) = \frac{1}{2}, d_{e} = d_{b} .$ For every stationary occupancy-ratio bound $C > 1$ , both experiments satisfy $d_{e} (s) \leq C d_{b} (s) for every joint state s .$ For every observable-data estimator $θ$ taking values in $[0, 1]$ , the maximum of its mean-squared risks over these two experiments is at least $1/ (1024 T)$ .

If additionally $ζ > 0$ , then for every $C > 1$ , define the cardinality-uniform rate exponent and stationary-overlap radius by $β = \frac{2}{2 + t _{0} ζ}, q_{C} = \frac{C - 1}{C} .$ Then $0 < β < 1, n \to \infty n \in N lim \frac{n ^{- 1}}{n ^{- β} q _{C}^{2 (1 - β)}} = 0.$ There exist a positive reset lower-bound constant $c_{Reset} > 0$ and a depth schedule $Q : N \to N$ , together with constants $a_{1}, a_{2} > 0$ , such that, for every sufficiently large $n$ , $a_{1} lo g n \leq Q (n) \leq a_{2} lo g n .$ For every sufficiently large $n$ , one has $n \geq 1$ and $Q (n) \geq 1$ , and the two signed depth- $Q (n)$ reset experiments of CausalSmith (2026) each have exactly $2 (Q (n) + 1)$ hidden states. For every observable-data estimator taking values in $[- 1, 1]$ in that cardinality-uniform decision problem, the maximum of its mean-squared risks over these two reset experiments is at least $c_{Reset} n^{- β} .$ For every sufficiently large $n$ , the negative-sign reset experiment has hidden-state cardinality $2 (Q (n) + 1) > 2.$

⊢ Lean

The two-point experiment explains the matching order in Theorem 2. Perturbing the reward probabilities at scale $T^{- 1/2}$ produces target-value separation at that scale while keeping the observed trajectory laws sufficiently close for the stated testing bound. The bounded observed-data procedures in Definition 4 are exactly the estimator class to which this testing argument applies. Together with Theorem 1, this establishes $T^{- 1}$ minimax mean-squared-error order for fixed positive mixing scale and fixed nonnegative overlap exponent.

The cardinality comparison concerns distinct decision problems. The binary class fixes two hidden states, whereas the signed-depth construction of the public manuscript CausalSmith (2026) uses a hidden alphabet whose size increases logarithmically with the horizon. For $ζ > 0$ and fixed $C > 1$ , the ratio limit in Theorem 2 makes the comparison precise: the parametric order for the binary class is asymptotically smaller than the cardinality-uniform overlap term. The fixed binary rate therefore characterizes the effect of a specified latent alphabet under the stated contraction and action-overlap conditions.

Coincident policies provide a familiar special case of the same stationary estimand. When the target policy equals the behavior policy, their induced transition matrices and stationary laws agree, and the depth-zero weighted moment becomes the ordinary stationary reward mean. The following reduction gives the corresponding sample-mean benchmark.

Proposition 1 [prop:coincident-policy-reduction] (Coincident policy reduction).

Consider a trajectory experiment with binary observed state, binary hidden state, and binary action. Suppose:

(Positive mixing scale.) The mixing-scale parameter $t_{0}$ satisfies $t_{0} > 0$ , and the associated contraction factor is $α = exp (- 1/ t_{0}) .$

(Nonempty horizon.) The trajectory length $T$ is an integer with $T \geq 1$ .

(Kernel law.) Assumption 1 holds.

(Sequential assignment.) Assumption 2 holds.

(Stationary start.) Assumption 3 holds.

(Behavior contraction.) Assumption 5 holds with contraction factor $α$ .

(Coincident policies.) The target and behavior policies satisfy $e = b$ .

The induced joint-state transition matrices coincide. Explicitly, for all joint states $s, s^{'} \in S$ , the four-point joint-state space, $P_{e} (s, s^{'}) = a \in {0, 1} \sum e (a ∣ x) \int_{[0, 1]} K (d y, s^{'} ∣ s, a) = a \in {0, 1} \sum b (a ∣ x) \int_{[0, 1]} K (d y, s^{'} ∣ s, a) = P_{b} (s, s^{'}),$ where $x$ is the observed coordinate of $s$ . Their stationary joint-state laws, $d_{e}$ and $d_{b}$ , also coincide: $d_{e} = d_{b} .$ Writing $θ$ for the stationary target value in Definition 2, the depth-zero population weighted-reward moment $m_{0}$ satisfies, at every observed epoch, $m_{0} = E_{b} [Y_{t}] = θ, t = 1, \dots, T,$ where $Y_{t}$ is the observed reward and $E_{b}$ denotes expectation under the behavior experiment. The sample mean is unbiased and obeys $E_{b} [T^{- 1} t = 1 \sum T Y_{t}] = θ, E_{b} {T^{- 1} t = 1 \sum T Y_{t} - θ}^{2} \leq \frac{1 + 2/ ( 1 - α )}{T} .$

⊢ Lean

Stationary initialization makes the expected reward at every sampled epoch equal to the target value in Proposition 1; behavior contraction controls the variance of its sample average. The lower-bound family in Definition 5 belongs to this coincident-policy setting. Its reward perturbations establish the parametric lower bound even when behavior and target stationary occupancies agree exactly, clarifying how ordinary sampling uncertainty supplies the matching order within the binary class.

Discussion

The statistical characterization in Theorem 2 concerns the stability of a stationary reward functional across contracting four-state realizations. For fixed positive mixing scale and fixed nonnegative action-overlap exponent, the minimax mean-squared error has order $T^{- 1}$ , where $T$ is the trajectory length. The uniform modulus in Lemma 1 explains how this rate accommodates latent-model degeneracies: agreement of seven scalar moments controls agreement of the stationary rewards, including at realizations with repeated transient eigenvalues or reduced effective dimension. The relevant stability is therefore a property of the stationary functional over the contracted class.

The explicit upper bound is $C_{α, L} / T$ , where $C_{α, L} = B_{α}^{2} (112 V_{α, L} + 2)$ . Since squared loss is at most one for the bounded procedures and targets used here, this displayed guarantee improves on the unit bound once $T > C_{α, L}$ . The threshold can be large: $B_{α}$ grows as contraction slows and $V_{α, L}$ grows with the seventh power of the action likelihood-ratio bound. Thus the parametric exponent is a fixed-parameter statement; finite-sample usefulness also depends materially on mixing and action overlap.

Fixed joint-state dimension supplies the bounded recurrence underlying this conclusion. With four joint states, the transient characteristic polynomial has degree three, and comparing two realizations gives a transient polynomial of degree six. Contraction bounds these transient roots away from the stationary root at one. As expressed by Lemma 1, the resulting stationary-value modulus depends on the common contraction bound and remains uniform across the realizations. This connects the dimension of the joint-state space to the fixed number of moments used in Algorithm 1.

Action weighting gives this finite-dimensional structure an observed-data interpretation. The intervention identity in Lemma 2 identifies the weighted reward moments with successive target-policy transitions starting from the behavior stationary law. Within each weighting window, the current action ratio supplies the target-policy reward vector, while the preceding ratios supply the target-policy transitions. Sequential assignment and action overlap justify this connection. For the empirical moments in Definition 3, the likelihood-ratio bound controls the weights and behavior contraction controls dependence across separated windows. The risk bound in Theorem 1 combines these sampling controls with stable extrapolation of the stationary functional.

The displayed estimator implements this characterization through a finite list of contracting moment fits. Its grid resolution $M$ grows linearly with the trajectory length at a fixed mixing scale. The bounds in Proposition 2 quantify the size of the list before and after the contraction filter.

Proposition 2 [prop:exhaustive-grid-arithmetic-complexity] (Exact grid candidate counts).

Fix $t_{0} > 0$ , the mixing-scale parameter, and define the associated contraction bound by $α = exp (- 1/ t_{0}) .$ For every integer $M \geq 0$ , the four-coordinate simplex grid, represented by integer coordinates in ${0, \dots, M}$ summing to $M$ , has cardinality $(3 M + 3) .$ The unfiltered candidate list consists of an initial simplex vector $ν$ , four simplex rows forming the transition candidate $R$ , and a reward vector $r$ with four independently chosen grid coordinates. Its cardinality is exactly $(3 M + 3)^{5} (M + 1)^{4} .$ For every integer $M \geq 0$ and every real contraction threshold $α$ , retaining the candidates satisfying $δ (R) \leq α + \frac{6}{M},$ where $δ (R)$ is the Dobrushin contraction coefficient and division by zero is interpreted as zero, yields a cardinality at most $(3 M + 3)^{5} (M + 1)^{4} .$

There exists a constant $c > 0$ such that, for every integer trajectory length $T \geq 1$ , at the resolution $M = ⌈ (22 + 36/ α) T ⌉, α = exp (- 1/ t_{0}),$ the unfiltered candidate-list cardinality and the filtered candidate-list cardinality are each at most $c T^{19}$ .

⊢ Lean

The five simplex factors in Proposition 2 correspond to the initial probability vector and the four transition rows; the remaining factor counts the four reward coordinates. Each simplex contributes a cubic factor in the resolution, giving total degree nineteen. Thus candidate-list cardinality is the established computational descriptor of the displayed estimator. The exact product records the scale of exhaustive enumeration, and the $c T^{19}$ bound expresses its growth with the horizon for a fixed mixing scale.

The statistical guarantee also applies within stationary-overlap subclasses of the binary experiment class. For any fixed stationary occupancy-ratio bound $C > 1$ , impose the additional restriction $d_{e} (s) \leq C d_{b} (s)$ at every joint state. The upper bound in Theorem 1 continues to apply uniformly on this restricted class. The two testing experiments in Theorem 2 satisfy the restriction because their stationary laws coincide, so they retain the matching lower bound. Consequently, for fixed positive mixing scale, fixed nonnegative action-overlap exponent, and $T \geq 12$ , these subclasses also have minimax mean-squared-error order $T^{- 1}$ .

Coincident policies give a direct sampling interpretation of the same order. Under the conditions of Proposition 1, stationary initialization and behavior contraction make the ordinary reward sample mean unbiased and give a mean-squared-error bound proportional to $T^{- 1}$ for every $T \geq 1$ . Together with the coincident-policy testing family in Definition 5, this reduction connects the general stationary evaluation result to the familiar uncertainty of estimating a stationary reward mean.

Limitations and future work

For fixed positive mixing scale and fixed nonnegative logarithmic action likelihood-ratio bound, Theorem 2 establishes minimax mean-squared-error order $T^{- 1}$ , where $T$ is the observed trajectory length, for the binary experiment class in Definition 1. The stable-grid estimator supplies a constructive statistical upper bound, while Proposition 2 characterizes its candidate-list cardinality. These conclusions address distinct questions. A candidate count specifies the size of the search space; runtime additionally depends on the cost of constructing, evaluating, and selecting candidates. Arithmetic-operation counts, bit complexity, and the precision needed to certify objective comparisons therefore require separate analysis. We formulate these requirements as a stable fitting problem.

Definition 6 [def:polynomial-time-handle] (Stable fitting problem

H_{poly}

The problem $H_{poly}$ is to construct an algorithm with an explicit cost bound in a specified arithmetic or bit-complexity model, including precision requirements, satisfying the following conditions:

(Input.) The algorithm starts from the $3 \times 3$ Hankel matrix $(m_{i + j + 1} - m_{i + j})_{i, j = 0}^{2},$ where $m_{k}$ denotes the common-window empirical weighted reward moment.

(Rank adaptation.) It adapts over recurrence ranks zero through three.

(Stability.) It enforces transient roots in ${z : ∣ z ∣ \leq α},$ where $α$ is the contraction bound.

(Objective accuracy.) It returns a stable four-state scalar realization whose seven-moment objective is within $T^{- 1}$ of the global optimum, with a guarantee of this gap, where $T$ is the observed trajectory length.

(Uniformity.) The guarantee is uniform over rank-deficient strata, with positive singular-value margins allowed to vanish.

For fixed $t_{0}$ , the mixing-scale parameter, the exhaustive estimator is specified by a finite candidate list of size $O (T^{19})$ . Its stated computational bound concerns this candidate count; runtime and arithmetic-operation bounds for fitting and selection form part of the computational target.

⊢ Lean

Here “starts from” includes access to the complete input vector $(m_{0}, \dots, m_{6})$ , the horizon $T$ , and the contraction bound $α$ ; the displayed Hankel matrix is the device used to adapt to the recurrence rank. In the stated finite-grid version, the global optimum is the minimum over the stabilized candidate class $C_{M}$ of Algorithm 1. A valid output consists of a probability initial vector, a row-stochastic transition matrix with Dobrushin coefficient at most $α$ , and a reward function taking values in $[0, 1]$ , together with a certificate for the claimed objective gap. Replacing this finite-grid optimum by an optimum over a continuous realization class would be a stronger, separate computational target.

The cost-certified fitting problem $H_{poly}$ in Definition 6 couples stability with a global objective certificate. Rank adaptation must cover recurrence ranks zero through three, including configurations where positive singular values approach zero. Consequently, a guarantee conditioned on a fixed positive singular-value margin would address a narrower problem. Likewise, a small local optimization residual would require an additional argument connecting it to the stipulated global objective gap. The computational question is whether these certification requirements can be met with explicit cost and precision bounds.

Remark 1 [oeq:polynomial-time-attainment] (Rank-adaptive computational attainment).

A natural computational question is whether $H_{poly}$ , the cost-bounded stable fitting problem, can implement fitting and lexicographic selection over, or replace, the $O (T^{19})$ -sized stable-grid candidate list by a rank-adaptive algorithm with explicit runtime, bit-complexity, and precision semantics. The required output is a stable four-state scalar realization whose seven-moment objective is guaranteed to be within $T^{- 1}$ of the global optimum, uniformly over $M_{T}^{(2)} (t_{0}, ζ)$ , the class of binary-state and binary-action experiments satisfying the six law conditions. Here $T$ is the observed trajectory length, $t_{0}$ is the mixing-scale parameter, and $ζ$ is the logarithmic action likelihood-ratio bound. The question requires uniformity over every rank-deficient Hankel stratum, with positive singular-value margins allowed to vanish.

⊢ Lean

Remark 1 identifies an algorithmic research target rather than an attained complexity guarantee. Its central requirement is global certification across rank-deficient strata: computational savings must preserve the objective guarantee as the effective recurrence rank changes. Resolving this question would supply a cost-controlled implementation of the specified fitting task and clarify the computational requirements for applying stable moment fitting to long trajectories.

Several statistical questions remain within the fixed-binary setting. The seven common-window moments in Definition 3 support the estimator and upper bound in Theorem 1; determining the minimal sufficient observable window would clarify how much trajectory-local information stationary evaluation requires under the same law conditions. Limit distributions and confidence intervals are further targets. The mean-squared-error guarantees characterize estimation accuracy, while distributional approximations and interval coverage require additional results, particularly for experiments on or near rank-deficient strata.

Application-specific calibration is another direction. The mixing-scale and action-overlap bounds specify the regime of the statistical guarantees. Methods for selecting and substantiating these bounds in a given application, together with sensitivity analyses for their choice, would connect the stated conditions to empirical practice.

Finally, larger or increasing hidden-state cardinalities define a broader statistical extension. Such an analysis would need to characterize how the required observable window and risk bounds depend on cardinality while specifying the corresponding stationarity, overlap, and contraction conditions. The fixed-binary results in Theorems 1 and 2 provide the benchmark under the six law conditions of Definition 1; rates for broader hidden-state classes remain a separate question.

Appendices

Proofs and verification scope

The mathematical dependencies follow the distinction between observable sampling error and stationary-value stability. We first introduce the four-state realization apparatus underlying Lemma 1, then present the intervention and dependence bounds used by Theorem 1. The testing family supplies the complementary lower-bound input. The final parts connect these ingredients to the minimax statement, the coincident-policy reduction, and the candidate count.

Four-state realizations and the value modulus

A four-state scalar realization consists of an initial probability row vector $ν$ , a row-stochastic transition matrix $P$ , and a reward function $r : S \to [0, 1]$ , represented as a column in matrix products. Its depth- $k$ moment is $ν P^{k} r$ , and its stationary reward is $π r$ , where $π$ is a stationary probability row vector. For the comparison realization, write $ν^{'}$ for the initial law, $P^{'}$ for the transition matrix, $r^{'}$ for the reward function, and $π^{'}$ for the stationary law. Both realizations are subject to the same contraction bound $α$ . In the formal statement below, all vectors indexed by $S$ are coordinate families; the displayed scalar products use $ν, ν^{'}, π, π^{'}$ as rows and $r, r^{'}$ as reward-function columns.

The transient characteristic factors $q_{P}$ and $q_{P^{'}}$ remove the stationary root from the respective characteristic polynomials: $q_{P} (z) = \frac{det ( z Id - P )}{z - 1}, q_{P^{'}} (z) = \frac{det ( z Id - P ^{'} )}{z - 1},$ where $Id$ is the identity matrix on the four-point joint-state space. Their product is the pair transient characteristic polynomial $Q_{P, P^{'}}$ . The following statement establishes the simple stationary roots and gives the exact identity connecting the first seven scalar moments to the difference in stationary rewards.

Lemma 1 [lem:pair-polynomial-modulus] (Pair-polynomial identity and value modulus).

Let $S = {0, 1} \times {0, 1}$ be the four-state joint-state space. Let $P, P^{'}$ be real matrices indexed by $S$ , and let $ν, ν^{'}, π, π^{'}, r, r^{'}$ be real row vectors indexed by $S$ . Suppose:

(Contraction parameter.) The contraction bound $α$ satisfies $0 < α < 1$ .

(Transition matrices.) Both $P$ and $P^{'}$ are row-stochastic: their entries are nonnegative and each row sums to one.

(Initial distributions.) Both $ν$ and $ν^{'}$ are probability vectors.

(Stationary distributions.) Both $π$ and $π^{'}$ are probability vectors, with $π P = π, π^{'} P^{'} = π^{'} .$

(Rewards.) For every $s \in S$ , $0 \leq r (s) \leq 1, 0 \leq r^{'} (s) \leq 1.$

(Contraction bounds.) The Dobrushin coefficients satisfy $δ (P) δ (P^{'}) = i, j \in S max \frac{1}{2} s \in S \sum ∣ P_{i s} - P_{j s} ∣ \leq α, = i, j \in S max \frac{1}{2} s \in S \sum ∣ P_{i s}^{'} - P_{j s}^{'} ∣ \leq α .$

Then eigenvalue $1$ has algebraic multiplicity one for each of $P$ and $P^{'}$ . Define the pair transient characteristic polynomial and its coefficients by $Q_{P, P^{'}} (z) = \frac{det ( z Id - P )}{z - 1} \frac{det ( z Id - P ^{'} )}{z - 1} = k = 0 \sum 6 Q_{k} z^{k},$ where $Id$ is the identity matrix on $S$ , and define the modulus constant by $B_{α} = (\frac{1 + α}{1 - α})^{6} .$ With products interpreted as $π r = s \in S \sum π (s) r (s), ν P^{k} r = s \in S \sum (ν P^{k}) (s) r (s),$ and analogously for the primed vectors, the exact identity and bound are $Q_{P, P^{'}} (1) (π r - π^{'} r^{'}) = k = 0 \sum 6 Q_{k} (ν P^{k} r - ν^{'} P^{' k} r^{'})$ and $∣ π r - π^{'} r^{'} ∣ \leq B_{α} 0 \leq k \leq 6 max ν P^{k} r - ν^{'} P^{' k} r^{'} .$

⊢ Lean

Proof of Lemma 1.

Real fixed vectors. Define the constant column vector and, for an arbitrary real function, its extrema and midpoint by $1 (s) := 1 (s \in S), f : S \to R, f_{m i n} := s \in S min f (s), f_{m a x} := s \in S max f (s), c_{f} := \frac{f _{m i n} + f _{m a x}}{2} .$ For probability vectors $ω_{1}, ω_{2} : S \to R$ , put $τ (ω_{1}, ω_{2}) := \frac{1}{2} s \in S \sum ∣ ω_{1} (s) - ω_{2} (s) ∣.$ Their equal total masses give $s \sum (ω_{1} (s) - ω_{2} (s)) = 0, ∣ f (s) - c_{f} ∣ \leq \frac{f _{m a x} - f _{m i n}}{2} .$ Consequently, centering at $c_{f}$ and applying the triangle inequality yields $s \sum ω_{1} (s) f (s) - s \sum ω_{2} (s) f (s) = s \sum (ω_{1} (s) - ω_{2} (s)) (f (s) - c_{f}) \leq s \sum ∣ ω_{1} (s) - ω_{2} (s) ∣ \frac{f _{m a x} - f _{m i n}}{2} = τ (ω_{1}, ω_{2}) (f_{m a x} - f_{m i n}) .$ Now suppose $P f = f$ , and choose $i_{m i n}, i_{m a x} \in S, f (i_{m i n}) = f_{m i n}, f (i_{m a x}) = f_{m a x} .$ The rows of $P$ are probability vectors, and $τ (P (i_{m a x}, \cdot), P (i_{m i n}, \cdot)) \leq δ (P) \leq α .$ Applying the preceding estimate to these rows gives $0 \leq f_{m a x} - f_{m i n} = ∣ (P f) (i_{m a x}) - (P f) (i_{m i n}) ∣ \leq τ (P (i_{m a x}, \cdot), P (i_{m i n}, \cdot)) (f_{m a x} - f_{m i n}) \leq α (f_{m a x} - f_{m i n}) .$ Since $1 - α > 0$ , the extrema coincide, so $f = f_{m i n} 1$ . Conversely, row-stochasticity gives $P 1 = 1$ . Thus $ker (P - Id) = span_{R} {1} .$ The same argument applies to $P^{'}$ .
The exact polynomial identity. Write $χ_{P} (z) := det (z Id - P), χ_{P^{'}} (z) := det (z Id - P^{'}) .$ Because $1 \neq = 0$ and $P 1 = 1$ , we have $χ_{P} (1) = 0$ , and similarly $χ_{P^{'}} (1) = 0$ . Define the polynomial quotients $q_{P} (z) := \frac{χ _{P} ( z )}{z - 1} \in R [z], q_{P^{'}} (z) := \frac{χ _{P^{'}} ( z )}{z - 1} \in R [z] .$ Thus $χ_{P} (z) = (z - 1) q_{P} (z), χ_{P^{'}} (z) = (z - 1) q_{P^{'}} (z), Q_{P, P^{'}} (z) = q_{P} (z) q_{P^{'}} (z) .$ The characteristic polynomials have degree four, so $de g q_{P} = de g q_{P^{'}} = 3, de g Q_{P, P^{'}} \leq 6.$

For polynomial matrix evaluation, use the convention $F (z) = k = 0 \sum n_{F} F_{k} z^{k} \in R [z], n_{F} \in N, F (P) := k = 0 \sum n_{F} F_{k} P^{k} .$ Stationarity and induction give $π P^{k} = π (k \in N), π F (P) = k = 0 \sum n_{F} F_{k} π P^{k} = F (1) π .$ Cayley–Hamilton, together with the characteristic factorization, yields $(P - Id) q_{P} (P) = χ_{P} (P) = 0.$ Each column of $q_{P} (P)$ therefore belongs to the fixed space established above. Since each column is constant and $\sum_{s} π (s) = 1$ , for every $i, j \in S$ , $[q_{P} (P)]_{ij} = s \sum π (s) [q_{P} (P)]_{s j} = [π q_{P} (P)]_{j} = q_{P} (1) π (j) .$ With the rank-one matrix defined by $(1 π)_{ij} := π (j) (i, j \in S),$ this says $q_{P} (P) = q_{P} (1) 1 π .$ Multiplying by $q_{P^{'}} (P)$ and using polynomial stationarity gives $Q_{P, P^{'}} (P) = q_{P} (P) q_{P^{'}} (P) = q_{P} (1) 1 (π q_{P^{'}} (P)) = q_{P} (1) q_{P^{'}} (1) 1 π = Q_{P, P^{'}} (1) 1 π .$ Applying the same calculation to $P^{'}$ , with the polynomial factors in the opposite order, gives $Q_{P, P^{'}} (P^{'}) = Q_{P, P^{'}} (1) 1 π^{'} .$

Since the initial vectors have total mass one, these projection identities imply $ν Q_{P, P^{'}} (P) r = Q_{P, P^{'}} (1) π r, ν^{'} Q_{P, P^{'}} (P^{'}) r^{'} = Q_{P, P^{'}} (1) π^{'} r^{'} .$ On the other hand, expanding the polynomial of degree at most six gives $ν Q_{P, P^{'}} (P) r = k = 0 \sum 6 Q_{k} ν P^{k} r, ν^{'} Q_{P, P^{'}} (P^{'}) r^{'} = k = 0 \sum 6 Q_{k} ν^{'} P^{' k} r^{'} .$ Subtracting proves $Q_{P, P^{'}} (1) (π r - π^{'} r^{'}) = k = 0 \sum 6 Q_{k} (ν P^{k} r - ν^{'} P^{' k} r^{'}) .$
Algebraic simplicity at one. Define the shifted operators $D_{P} := P - Id, D_{P^{'}} := P^{'} - Id .$ For a column vector $w \in R^{S}$ satisfying $D_{P}^{2} w = 0$ , put $w_{shift} := D_{P} w .$ Then $D_{P} w_{shift} = 0, P w_{shift} = w_{shift},$ so $w_{shift}$ is constant by [proof:pair-polynomial-modulus:fixed-vectors]. Stationarity and normalization now give, for every $s \in S$ , $w_{shift} (s) = i \sum π (i) w_{shift} (i) = π D_{P} w = (π P - π) w = 0.$ Hence $D_{P}^{2} w = 0 ⟹ D_{P} w = 0.$

Induction extends this implication to $D_{P}^{n} w = 0 ⟹ D_{P} w = 0 (n \in N, w \in R^{S}) .$ For $n = 0$ , the premise gives $w = 0$ . For the induction step, $D_{P}^{n + 1} w = 0 ⟹ D_{P}^{n} (D_{P} w) = 0 ⟹ D_{P}^{2} w = 0 ⟹ D_{P} w = 0,$ where the middle implication uses the induction hypothesis.

Thus the generalized eigenspace at one is $E_{P, 1} := n \in N ⋃ ker (D_{P}^{n}) = ker D_{P} = span_{R} {1} .$ Algebraic multiplicity equals the dimension of this generalized eigenspace. Since $1 \neq = 0$ , it follows that $m_{P} := max {n \in N : (z - 1)^{n} divides χ_{P} (z)} = dim_{R} E_{P, 1} = 1.$ The identical argument for $P^{'}$ gives $m_{P^{'}} := max {n \in N : (z - 1)^{n} divides χ_{P^{'}} (z)} = 1.$
The coefficient modulus. If $q_{P} (1) = 0$ , the factorization of $χ_{P}$ would make it divisible by $(z - 1)^{2}$ , contradicting $m_{P} = 1$ . The primed factor satisfies the same property. Consequently, $q_{P} (1) \neq = 0, q_{P^{'}} (1) \neq = 0, ∣ Q_{P, P^{'}} (1) ∣ = ∣ q_{P} (1) ∣ ∣ q_{P^{'}} (1) ∣ > 0.$ Define the seven moment differences and their maximum by $ε_{k} := ν P^{k} r - ν^{'} P^{' k} r^{'} (k \in {0, \dots, 6}), ε_{m a x} := 0 \leq k \leq 6 max ∣ ε_{k} ∣.$ Taking absolute values in the identity from [proof:pair-polynomial-modulus:identity] gives $∣ Q_{P, P^{'}} (1) ∣ ∣ π r - π^{'} r^{'} ∣ = k = 0 \sum 6 Q_{k} ε_{k} \leq k = 0 \sum 6 ∣ Q_{k} ∣ ∣ ε_{k} ∣ \leq (k = 0 \sum 6 ∣ Q_{k} ∣) ε_{m a x} .$ Division by the positive denominator therefore yields $∣ π r - π^{'} r^{'} ∣ \leq \frac{\sum _{k = 0}^{6} ∣ Q _{k} ∣}{∣ Q _{P, P^{'}} ( 1 ) ∣} ε_{m a x} .$
The complex root bound. Let $z \in C$ be a root of $Q_{P, P^{'}}$ . The product factorization gives the two cases $q_{P} (z) = 0 or q_{P^{'}} (z) = 0.$ Consider the first case. Since $q_{P} (1) \neq = 0$ , we have $z \neq = 1$ , while $χ_{P} (z) = (z - 1) q_{P} (z) = 0.$ Regard $P$ as acting on complex column vectors. Singularity of $z Id - P$ supplies $f_{C} \in C^{S} ∖ {0}, P f_{C} = z f_{C} .$ A constant vector is fixed by $P$ , so a constant $f_{C}$ would satisfy $(z - 1) f_{C} = 0,$ forcing $z = 1$ . Thus its diameter is positive: $d_{f} := i, j \in S max ∣ f_{C} (i) - f_{C} (j) ∣ > 0.$

To bound this diameter after applying $P$ , take an arbitrary complex function and define $φ : S \to C, d_{φ} := i, j \in S max ∣ φ (i) - φ (j) ∣, W_{φ} := s \sum (ω_{1} (s) - ω_{2} (s)) φ (s),$ where $ω_{1}, ω_{2}$ are probability vectors. If $W_{φ} = 0$ , then $∣ W_{φ} ∣ = 0 \leq d_{φ} τ (ω_{1}, ω_{2}),$ because both factors on the right are nonnegative. If $W_{φ} \neq = 0$ , define the real function $γ_{φ} : S \to R, γ_{φ} (s) := Re (\overline{W_{φ}} φ (s)) .$ For every $i, j \in S$ , $∣ γ_{φ} (i) - γ_{φ} (j) ∣ = Re (\overline{W_{φ}} (φ (i) - φ (j))) \leq ∣ W_{φ} ∣ ∣ φ (i) - φ (j) ∣ \leq ∣ W_{φ} ∣ d_{φ} .$ In particular, $s max γ_{φ} (s) - s min γ_{φ} (s) \leq ∣ W_{φ} ∣ d_{φ} .$ The defining sum for $W_{φ}$ also gives $s \sum (ω_{1} (s) - ω_{2} (s)) γ_{φ} (s) = Re (\overline{W_{φ}} W_{φ}) = ∣ W_{φ} ∣^{2} .$ Applying the real expectation bound from [proof:pair-polynomial-modulus:fixed-vectors] to $γ_{φ}$ , therefore, $∣ W_{φ} ∣^{2} = s \sum (ω_{1} (s) - ω_{2} (s)) γ_{φ} (s) \leq (s max γ_{φ} (s) - s min γ_{φ} (s)) τ (ω_{1}, ω_{2}) \leq ∣ W_{φ} ∣ d_{φ} τ (ω_{1}, ω_{2}) .$ Dividing by $∣ W_{φ} ∣ > 0$ , and including the zero case already treated, proves $s \sum (ω_{1} (s) - ω_{2} (s)) φ (s) \leq d_{φ} τ (ω_{1}, ω_{2}) .$

Apply this estimate to two rows of $P$ . For every $i, j \in S$ , $∣ (P φ) (i) - (P φ) (j) ∣ = s \sum (P_{i s} - P_{j s}) φ (s) \leq d_{φ} τ (P (i, \cdot), P (j, \cdot)) \leq d_{φ} δ (P) \leq α d_{φ} .$ Choose a pair attaining the diameter of $f_{C}$ : $i_{diam}, j_{diam} \in S, ∣ f_{C} (i_{diam}) - f_{C} (j_{diam}) ∣ = d_{f} .$ Using the eigenvector equation in the preceding contraction estimate gives $∣ z ∣ d_{f} = ∣ z f_{C} (i_{diam}) - z f_{C} (j_{diam}) ∣ = ∣ (P f_{C}) (i_{diam}) - (P f_{C}) (j_{diam}) ∣ \leq α d_{f} .$ Since $d_{f} > 0$ , division gives $∣ z ∣ \leq α$ . In the second case, $q_{P^{'}} (z) = 0$ , the same argument uses $P^{'}$ and $δ (P^{'}) \leq α$ . We have therefore proved $Q_{P, P^{'}} (z) = 0 ⟹ ∣ z ∣ \leq α (z \in C) .$
The coefficient ratio. Each characteristic polynomial is monic of degree four. Its factorization by the monic linear polynomial $z - 1$ shows that $q_{P}, q_{P^{'}} are monic of degree 3, Q_{P, P^{'}} is monic, de g Q_{P, P^{'}} = 3 + 3 = 6.$ Factoring over $C$ , enumerate the roots with algebraic multiplicity: $ξ_{1}, \dots, ξ_{6} \in C, Q_{P, P^{'}} (z) = ℓ = 1 \prod 6 (z - ξ_{ℓ}), ∣ ξ_{ℓ} ∣ \leq α (1 \leq ℓ \leq 6) .$ For each $k \in {0, \dots, 6}$ , define $J_{k} := {J \subseteq {1, \dots, 6} : # J = 6 - k} .$ Expanding the product, with empty products interpreted as one, gives $Q_{k} = (- 1)^{6 - k} J \in J_{k} \sum ℓ \in J \prod ξ_{ℓ}, # J_{k} = (6 - k 6) = (k 6) .$ Thus every coefficient satisfies $∣ Q_{k} ∣ \leq J \in J_{k} \sum ℓ \in J \prod ∣ ξ_{ℓ} ∣ \leq (k 6) α^{6 - k} .$ Summing these seven bounds and using the binomial formula yields $k = 0 \sum 6 ∣ Q_{k} ∣ \leq k = 0 \sum 6 (k 6) α^{6 - k} = (1 + α)^{6} .$

For the denominator, the reverse triangle inequality gives $∣1 - ξ_{ℓ} ∣ \geq 1 - ∣ ξ_{ℓ} ∣ \geq 1 - α > 0 (1 \leq ℓ \leq 6) .$ The empty product equals one. Successively multiplying the nonnegative distance bounds gives, by induction, $ℓ = 1 \prod n_{root} ∣1 - ξ_{ℓ} ∣ \geq (1 - α)^{n_{root}} (n_{root} \in {0, \dots, 6}) .$ Indeed, for $n_{root} < 6$ , the induction step is $ℓ = 1 \prod n_{root} + 1 ∣1 - ξ_{ℓ} ∣ = ∣1 - ξ_{n_{root} + 1} ∣ ℓ = 1 \prod n_{root} ∣1 - ξ_{ℓ} ∣ \geq (1 - α) ℓ = 1 \prod n_{root} ∣1 - ξ_{ℓ} ∣ \geq (1 - α)^{n_{root} + 1} .$ Evaluating the root factorization at one consequently gives $∣ Q_{P, P^{'}} (1) ∣ = ℓ = 1 \prod 6 ∣1 - ξ_{ℓ} ∣ \geq (1 - α)^{6} > 0.$

Combining the numerator and denominator bounds, with positive denominators, proves $\frac{\sum _{k = 0}^{6} ∣ Q _{k} ∣}{∣ Q _{P, P^{'}} ( 1 ) ∣} \leq \frac{( 1 + α ) ^{6}}{( 1 - α ) ^{6}} = (\frac{1 + α}{1 - α})^{6} = B_{α} .$
The value modulus. The maximum is nonnegative because its index set contains zero: $0 \leq ∣ ε_{0} ∣ \leq ε_{m a x} .$ We may therefore multiply the coefficient-ratio bound by $ε_{m a x}$ . Together with [proof:pair-polynomial-modulus:coefficient-modulus], this gives $∣ π r - π^{'} r^{'} ∣ \leq \frac{\sum _{k = 0}^{6} ∣ Q _{k} ∣}{∣ Q _{P, P^{'}} ( 1 ) ∣} ε_{m a x} \leq B_{α} ε_{m a x} = B_{α} 0 \leq k \leq 6 max ∣ ν P^{k} r - ν^{'} P^{' k} r^{'} ∣.$

∎

The modulus in Lemma 1 concerns the stationary reward functional across all realizations satisfying its conditions. Its constant depends on the common contraction bound, so the same comparison applies to the target realization and every stabilized candidate in Algorithm 1. Repeated transient roots and reduced effective dimension are covered by this uniform statement. The degree-six pair polynomial explains the use of depths zero through six.

Intervention moments and trajectory dependence

The observable counterpart of the realization apparatus is supplied by the weighted rewards in Definition 3. The current action ratio changes the conditional reward mean to its target-policy counterpart, while the preceding ratios correspond to target-policy transitions. The next statement records this identity together with the second-moment and covariance controls required for a stationary behavior trajectory.

Lemma 2 [lem:observable-intervention-moments] (Observable intervention moment bounds).

Consider an experiment in $M_{T}^{(2)} (t_{0}, ζ)$ , the binary experiment class of Definition 1, with trajectory length $T$ . Set $L = exp (ζ), α = exp (- 1/ t_{0}) .$ On the four-point joint-state space $S$ , let $P_{b}$ and $P_{e}$ be the behavior- and target-policy transition matrices, respectively, and let $r_{e}$ be the target-policy conditional mean reward vector: $P_{b} (s, s^{'}) P_{e} (s, s^{'}) r_{e} (s) = a \in {0, 1} \sum b (a ∣ x) \int_{Y} K (d y, s^{'} ∣ s, a), = a \in {0, 1} \sum e (a ∣ x) \int_{Y} K (d y, s^{'} ∣ s, a), = a \in {0, 1} \sum e (a ∣ x) s^{'} \in S \sum \int_{Y} y K (d y, s^{'} ∣ s, a), s = (x, h) .$ Here $K$ is the joint reward and successor-state law, $Y = [0, 1]$ is the reward space, and $d_{b}$ is the stationary probability row vector of $P_{b}$ .

Use zero-based epochs $0, \dots, T - 1$ . For observed state $X_{j}$ , action $A_{j}$ , and reward $Y_{j}$ , define the observed likelihood ratio and weighted reward score by $ρ_{j} = {e (A_{j} ∣ X_{j}) / b (A_{j} ∣ X_{j}), 0, b (A_{j} ∣ X_{j}) > 0, b (A_{j} ∣ X_{j}) = 0, Z_{t} (k) = Y_{t} j = t - k \prod t ρ_{j} (k \leq t) .$ Write $E_{b}$ for expectation under the experiment’s stationary behavior law. For every $k \in {0, \dots, 6}$ and every epoch $t$ with $k \leq t < T$ , $m_{k} = E_{b} [Z_{t} (k)] = d_{b} P_{e}^{k} r_{e} = s \in S \sum (d_{b} P_{e}^{k}) (s) r_{e} (s), E_{b} [Z_{t} (k)^{2}] \leq L^{k + 1} .$ Moreover, for every integer $h \geq k + 1$ such that $t + h < T$ , $E_{b} [(Z_{t} (k) - E_{b} [Z_{t} (k)]) (Z_{t + h} (k) - E_{b} [Z_{t + h} (k)])] \leq α^{h - k - 1} .$

⊢ Lean

Proof of Lemma 2.

Fix an experiment in the stated class and integers $k \in {0, \dots, 6}, k \leq t < T .$ The parameter conditions in Definition 1 give $L = exp (ζ) \geq 1.$

The population moment. By Assumption 4, the likelihood ratios satisfy $b (a ∣ x) = 0 ⟹ e (a ∣ x) = 0, 0 \leq ρ_{j} \leq L .$ For each epoch $j$ , define the class of bounded history variables by $D_{j} := {D : D is a bounded real F_{j}^{-} -measurable random variable} .$ Regard any function $f : S ⟶ R$ as a column vector. For $D \in D_{j}$ , Assumptions 1, 2, and 4 give the weighted one-step identity $E_{b} [D ρ_{j} f (S_{j + 1})] = E_{b} D a : b (a ∣ X_{j}) > 0 \sum b (a ∣ X_{j}) \frac{e ( a ∣ X _{j} )}{b ( a ∣ X _{j} )} s^{'} \in S \sum \int_{Y} f (s^{'}) K (d y, s^{'} ∣ S_{j}, a) = E_{b} [D (P_{e} f) (S_{j})] .$ The zero-behavior cells contribute zero target probability, which justifies completing the action sum. Integrating the terminal reward instead, and integrating an unweighted successor state, respectively, gives $E_{b} [D ρ_{j} Y_{j}] E_{b} [D f (S_{j + 1})] = E_{b} [D a \sum e (a ∣ X_{j}) s^{'} \sum \int_{Y} y K (d y, s^{'} ∣ S_{j}, a)] = E_{b} [D r_{e} (S_{j})], = E_{b} [D a \sum b (a ∣ X_{j}) s^{'} \sum \int_{Y} f (s^{'}) K (d y, s^{'} ∣ S_{j}, a)] = E_{b} [D (P_{b} f) (S_{j})] .$ All these integrations use the joint reward and successor-state law.

Define the successive backward reward functions by $f_{e, 0} := r_{e}, f_{e, ℓ + 1} (s) := s^{'} \in S \sum P_{e} (s, s^{'}) f_{e, ℓ} (s^{'}), ℓ \in N_{0} .$ Starting with the terminal reward identity and removing the preceding $k$ ratios backward yields $E_{b} [Z_{t} (k)] = E_{b} j = t - k \prod t - 1 ρ_{j} r_{e} (S_{t}) = E_{b} [f_{e, k} (S_{t - k})] .$ At each removal, the remaining earlier ratios form a bounded pre-action-history variable. When $k = 0$ , the displayed product is empty and equals one.

In the zero-based convention, Assumption 3 gives $E_{b} [f (S_{0})] = s \in S \sum d_{b} (s) f (s), d_{b} P_{b} = d_{b} .$ The unweighted one-step identity propagates this equality. Indeed, if it holds at epoch $j$ , then $E_{b} [f (S_{j + 1})] = E_{b} [(P_{b} f) (S_{j})] = s \sum d_{b} (s) s^{'} \sum P_{b} (s, s^{'}) f (s^{'}) = s^{'} \sum (d_{b} P_{b}) (s^{'}) f (s^{'}) = s^{'} \sum d_{b} (s^{'}) f (s^{'}) .$ Thus, by induction, $E_{b} [f (S_{j})] = s \sum d_{b} (s) f (s), 0 \leq j < T .$

Finally, the backward recursion agrees with matrix powers: $f_{e, 0} = P_{e}^{0} r_{e}, f_{e, ℓ + 1} = P_{e} f_{e, ℓ} = P_{e} (P_{e}^{ℓ} r_{e}) = P_{e}^{ℓ + 1} r_{e} .$ Consequently, $E_{b} [Z_{t} (k)] = s \sum d_{b} (s) (P_{e}^{k} r_{e}) (s) = s^{'} \sum (s \sum d_{b} (s) P_{e}^{k} (s, s^{'})) r_{e} (s^{'}) = s^{'} \sum (d_{b} P_{e}^{k}) (s^{'}) r_{e} (s^{'}) = d_{b} P_{e}^{k} r_{e} .$ This expression is independent of $t$ , so it gives the stated common moment $m_{k}$ .
The second moment. Define the window likelihood-ratio product by $W_{t, k} := j = t - k \prod t ρ_{j} .$ Sequential assignment and overlap imply $E_{b} [ρ_{j} ∣ F_{j}^{-}] = a : b (a ∣ X_{j}) > 0 \sum b (a ∣ X_{j}) \frac{e ( a ∣ X _{j} )}{b ( a ∣ X _{j} )} = a \sum e (a ∣ X_{j}) = 1.$ The ratios at earlier epochs are pre-action-history measurable. Removing the last ratio repeatedly therefore gives $E_{b} [W_{t, k}] = E_{b} j = t - k \prod t - 1 ρ_{j} = \dots = E_{b} [1] = 1.$ The last expression is the expectation of the empty product; this also covers $k = 0$ .

There are $k + 1$ factors, so $0 \leq W_{t, k} \leq L^{k + 1} .$ The reward support supplied by Definition 1 gives, almost surely, $Z_{t} (k)^{2} = Y_{t}^{2} W_{t, k}^{2} \leq W_{t, k}^{2} \leq L^{k + 1} W_{t, k} .$ Taking expectations and using the normalization above proves $E_{b} [Z_{t} (k)^{2}] \leq L^{k + 1} E_{b} [W_{t, k}] = L^{k + 1} .$
Reduction of the separated future score. Fix an integer $h \geq k + 1$ with $t + h < T$ , and define $u := t + h, g_{gap} := h - k - 1 \in N_{0}, u - k = t + 1 + g_{gap} .$ Define the future state function on all of $S$ by $f_{future} : S ⟶ R, f_{future} (s) := (P_{b}^{g_{gap}} P_{e}^{k} r_{e}) (s) .$ Both $1$ and $Z_{t} (k)$ belong to $D_{t + 1}$ . For either choice $D \in {1, Z_{t} (k)}$ , integrate the terminal weighted reward at $u$ , then the $k$ weighted transitions, and finally the $g_{gap}$ unweighted transitions. The one-step identities from the first part give $E_{b} [D Z_{u} (k)] = E_{b} D j = u - k \prod u - 1 ρ_{j} r_{e} (S_{u}) = E_{b} [D (P_{e}^{k} r_{e}) (S_{u - k})] = E_{b} [D f_{future} (S_{t + 1})] .$ The variable $D$ remains measurable with respect to every intervening pre-action history. For $k = 0$ , the ratio product is empty; for $g_{gap} = 0$ , the unweighted iteration is the identity. In particular, $E_{b} [Z_{t} (k) Z_{u} (k)] E_{b} [Z_{u} (k)] = E_{b} [Z_{t} (k) f_{future} (S_{t + 1})], = E_{b} [f_{future} (S_{t + 1})] .$
Oscillation of the future function. The kernel is a probability law supported on rewards in $[0, 1]$ , and the target action probabilities sum to one. Hence, for every $s \in S$ , $0 \leq r_{e} (s) = a \sum e (a ∣ x) s^{'} \sum \int_{Y} y K (d y, s^{'} ∣ s, a) \leq a \sum e (a ∣ x) = 1, s = (x, h_{hid}) \in X \times H .$

For a real function on $S$ , define its oscillation by $osc (f) := s \in S max f (s) - s \in S min f (s) .$ Thus $osc (r_{e}) \leq 1, 0 < α = exp (- 1/ t_{0}) \leq 1.$ Both transition matrices are stochastic: $P_{b} (s, s^{'}), P_{e} (s, s^{'}) \geq 0, s^{'} \sum P_{b} (s, s^{'}) = s^{'} \sum P_{e} (s, s^{'}) = 1.$ These identities follow by summing the probability kernel over successor states and then averaging over the corresponding action probabilities.

For $μ, μ^{'} \in Δ (S)$ , subtracting the midpoint of the range of $f$ gives $s \sum (μ (s) - μ^{'} (s)) f (s) = s \sum (μ (s) - μ^{'} (s)) (f (s) - \frac{max f + min f}{2}) \leq \frac{osc ( f )}{2} s \sum ∣ μ (s) - μ^{'} (s) ∣ = osc (f) ∥ μ - μ^{'} ∥_{TV} .$ Applying Assumptions 6 and 5 to point masses shows that the total variation distance between any two rows of either matrix is at most $α$ . Therefore, $∣ (P_{e} f) (s) - (P_{e} f) (s^{'}) ∣ ∣ (P_{b} f) (s) - (P_{b} f) (s^{'}) ∣ \leq osc (f) ∥ P_{e} (s, \cdot) - P_{e} (s^{'}, \cdot) ∥_{TV} \leq α osc (f), \leq osc (f) ∥ P_{b} (s, \cdot) - P_{b} (s^{'}, \cdot) ∥_{TV} \leq α osc (f) .$ Taking the maximum over the two states and iterating, with the identity operator as the zero-step case, gives $osc (P_{e}^{k} r_{e}) \leq α^{k} osc (r_{e}) \leq α^{k} \leq 1.$ Applying the behavior iteration to this bound yields $osc (f_{future}) = osc (P_{b}^{g_{gap}} P_{e}^{k} r_{e}) \leq α^{g_{gap}} osc (P_{e}^{k} r_{e}) \leq α^{g_{gap}} .$
Centering and the covariance bound. The scores are bounded, hence square integrable, and the future function is bounded on the finite state space. The preceding product normalization also gives the absolute first-moment bound $∣ Z_{t} (k) ∣ = ∣ Y_{t} ∣ W_{t, k} \leq W_{t, k}, E_{b} [∣ Z_{t} (k) ∣] \leq E_{b} [W_{t, k}] = 1.$

Define the centering constant by $c_{future} := E_{b} [f_{future} (S_{t + 1})] .$ For every $s \in S$ , the oscillation bound implies $∣ f_{future} (s) - c_{future} ∣ = ∣ E_{b} [f_{future} (s) - f_{future} (S_{t + 1})] ∣ \leq E_{b} [∣ f_{future} (s) - f_{future} (S_{t + 1}) ∣] \leq α^{g_{gap}} .$ Consequently, $∣ E_{b} [Z_{t} (k) f_{future} (S_{t + 1})] - E_{b} [Z_{t} (k)] c_{future} ∣ = ∣ E_{b} [Z_{t} (k) {f_{future} (S_{t + 1}) - c_{future}}] ∣ \leq α^{g_{gap}} E_{b} [∣ Z_{t} (k) ∣] \leq α^{g_{gap}} .$

Expanding the centered product and substituting the two future-score identities gives $E_{b} [{Z_{t} (k) - E_{b} [Z_{t} (k)]} {Z_{u} (k) - E_{b} [Z_{u} (k)]}] = E_{b} [Z_{t} (k) Z_{u} (k)] - E_{b} [Z_{t} (k)] E_{b} [Z_{u} (k)] = E_{b} [Z_{t} (k) f_{future} (S_{t + 1})] - E_{b} [Z_{t} (k)] c_{future} .$ Its absolute value is therefore bounded by $α^{g_{gap}} = α^{h - k - 1},$ as required.

∎

The identity in Lemma 2 places the population moments in the four-state realization with initial law $d_{b}$ , transition matrix $P_{e}$ , and reward vector $r_{e}$ . Stationarity makes these expectations independent of the terminal epoch. The zero-based indexing used here corresponds to shifting the one-based epochs in Definition 3 by one; the common empirical window contains $T - 6$ terminal epochs.

The second-moment bound controls weighting within a window, including the overlapping-window contribution to sampling error. Once the windows separate, the covariance bound supplies a geometrically summable dependence control. The moment variance constant $V_{α, L}$ , defined in Theorem 1 as $13 L^{7} + 2/ (1 - α)$ , summarizes these contributions for the seven common-window moments. Action overlap and behavior contraction thus have distinct roles in the sampling component of the estimator guarantee.

Grid approximation and stable fitting

The deterministic components of Theorem 1 are the grid approximation and the stationary-value modulus. In Algorithm 1, simplex rounding applies to the initial probability vector and each transition row, while coordinate rounding applies to the bounded reward vector. The allowance $6/ M$ in the transition filter accommodates the rounded matrix. Mixing that matrix with the uniform transition matrix places each candidate under the contraction bound required by Lemma 1.

The fitting criterion compares all seven candidate moments with their empirical counterparts. Its finite candidate set and lexicographic selection specify the estimator completely. Sampling error enters through Lemma 2; stationary-value stability enters through Lemma 1. The resolution $M = ⌈(22 + 36/ α) T ⌉$ is the discretization choice used in Theorem 1, whose bound accounts for both sampling and approximation error.

This division of roles explains the statistical guarantee. The fit concerns a finite vector of observable moments, and the modulus controls the stationary reward associated with that fit. At fixed positive mixing scale and fixed nonnegative logarithmic action-overlap bound, Theorem 1 gives a uniform mean-squared error proportional to $T^{- 1}$ for $T \geq 12$ .

The positive testing family

The lower-bound input is the positive four-state family in Definition 5. Its joint reward and successor-state law $K_{v}^{(T)}$ combines the hidden-state-dependent Bernoulli reward probability $q_{v} (h)$ , the action-dependent successor hidden-state probability $p (a)$ , and the noisy observation probability $E (x^{'} ∣ h^{'})$ . The Bernoulli mass conventions and the stationary initial and trajectory laws are specified in that definition. Across the two signs, the reward perturbation varies while the transition and observation components remain common.

At the testing amplitude $v_{T} = 1/ (16 T)$ , the fair coincident policies provide a common stationary occupancy. The following statement supplies class membership, target-value separation, and the relative-entropy control for the observed trajectory laws.

Lemma 3 [lem:testing-family-membership] (Testing family membership and separation).

Let $T$ be the observed trajectory length, $t_{0}$ the mixing-scale parameter, and $ζ$ the logarithmic action likelihood-ratio bound, with

(Length.) $T \in N$ and $T \geq 12$ .

(Mixing scale.) $t_{0} > 0$ .

(Overlap.) $ζ \geq 0$ .

Define the testing perturbation amplitude by $v_{T} = \frac{1}{16 T} .$ For each $v \in {- v_{T}, + v_{T}}$ , the experiment of Definition 5, with kernel $K_{v}^{(T)}$ , the specified initial and trajectory laws, and fair coincident policies $e (a ∣ x) = b (a ∣ x) = \frac{1}{2},$ belongs to $M_{T}^{(2)} (t_{0}, ζ)$ , the class satisfying the six law conditions in Definition 1. Its stationary target values, defined in Definition 2, satisfy $θ (K_{+ v_{T}}^{(T)}, e) - θ (K_{- v_{T}}^{(T)}, e) = \frac{1}{8 T} .$ Writing $P_{+}^{O_{T}}$ and $P_{-}^{O_{T}}$ for the respective laws projected onto the observed state, action, and reward trajectory, their relative entropy is finite and satisfies $KL (P_{+}^{O_{T}} ∥ P_{-}^{O_{T}}) \leq \frac{1}{12} .$ For each of the two experiments, the stationary joint-state laws $d_{e}$ and $d_{b}$ under the target and behavior policies coincide: $d_{e} = d_{b} .$ Moreover, for every stationary occupancy-ratio constant $C > 1$ , both experiments satisfy $d_{e} (s) \leq C d_{b} (s) for every s \in S,$ where $S$ is the four-point joint-state space.

⊢ Lean

Proof of Lemma 3.

1. Class membership. Since $T \geq 12$ , we have $T \geq 1, 0 < v_{T} = \frac{1}{16 T} \leq \frac{1}{16}, ∣ - v_{T} ∣ = v_{T} \leq \frac{1}{16} .$ Fix $v \in {- v_{T}, + v_{T}}$ and consider the experiment in Definition 5. Until the comparison of the two alternatives, stationary laws and transition matrices refer to this fixed experiment. Its reward probabilities satisfy $q_{v} (0) = \frac{3}{8} + v, q_{v} (1) = \frac{5}{8} + v, \frac{1}{4} \leq q_{v} (h) \leq \frac{3}{4} (h \in {0, 1}) .$ All Bernoulli masses and emission probabilities in the kernel are therefore positive. Summing its factors gives $y = 0 \sum 1 h^{'} = 0 \sum 1 x^{'} = 0 \sum 1 K_{v}^{(T)} (y, x^{'}, h^{'} ∣ x, h, a) = (y = 0 \sum 1 Ber_{q_{v} (h)} (y)) (h^{'} = 0 \sum 1 Ber_{p (a)} (h^{'}) x^{'} = 0 \sum 1 E (x^{'} ∣ h^{'})) = 1.$ The reward support is ${0, 1} \subset [0, 1]$ .

For use with the trajectory law, define the finite path space and its masses by $Ω_{path, T} c ι (x, h) ℓ_{v} (s, s^{'}; a, y) ω_{v} (c) = S^{T + 1} \times (A \times {0, 1})^{T}, = (s_{1}, \dots, s_{T + 1}; (a_{t}, y_{t})_{t = 1}^{T}) \in Ω_{path, T}, = \frac{1}{2} E (x ∣ h), = \frac{1}{2} K_{v}^{(T)} (y, s^{'} ∣ s, a), = ι (s_{1}) t = 1 \prod T ℓ_{v} (s_{t}, s_{t + 1}; a_{t}, y_{t}) .$ Thus $ω_{v} (c) > 0$ . The displayed masses are exactly the finite trajectory weights specified in Definition 5. Each chronological factor is normalized: $a, y, s^{'} \sum ℓ_{v} (s, s^{'}; a, y) = 1.$ Successively summing the future factors consequently gives, for every $t = 1, \dots, T$ and fixed $s_{t}$ , $a_{j}, y_{j}, s_{j + 1} j = t, \dots, T \sum j = t \prod T ℓ_{v} (s_{j}, s_{j + 1}; a_{j}, y_{j}) = 1.$ The remaining prefix factors cancel in conditional probabilities. Hence $v Pr (A_{t} = a ∣ F_{t}^{-}) = \frac{1}{2}, L_{v} (Y_{t}, S_{t + 1} ∣ F_{t}^{-}, A_{t}) = K_{v}^{(T)} (\cdot ∣ S_{t}, A_{t}) .$ These identities establish Assumptions 1 and 2.

Define the common successor-state mass by $d_{test} (x^{'}, h^{'}) = a = 0 \sum 1 \frac{1}{2} Ber_{p (a)} (h^{'}) E (x^{'} ∣ h^{'}) = \frac{1}{2} E (x^{'} ∣ h^{'}) .$ Indeed, $p (0) = 1/4$ and $p (1) = 3/4$ , so their fair average is $1/2$ . In the order $(0, 0), (0, 1), (1, 0), (1, 1)$ , this mass is $d_{test} = (\frac{3}{10}, \frac{1}{5}, \frac{1}{5}, \frac{3}{10}), s \in S \sum d_{test} (s) = 1.$ Summing out the reward and averaging over the fair action yields $P_{e} (s, s^{'}) = P_{b} (s, s^{'}) = d_{test} (s^{'}) (s, s^{'} \in S) .$ In particular, $s \sum d_{test} (s) P_{e} (s, s^{'}) = d_{test} (s^{'}) .$ This supplies a stationary probability law. The stationary laws used by the experiment are therefore stationary, and their stationarity equations and normalization give $d_{e} (s^{'}) = s \sum d_{e} (s) d_{test} (s^{'}) = d_{test} (s^{'}), d_{b} (s^{'}) = s \sum d_{b} (s) d_{test} (s^{'}) = d_{test} (s^{'}) .$ Moreover, summing first over actions and rewards and then over successor states gives $v Pr (S_{1} = s) = c \in Ω_{path, T} s_{1} = s \sum ω_{v} (c) = ι (s) s_{2}, \dots, s_{T + 1} \sum t = 1 \prod T d_{test} (s_{t + 1}) = ι (s) = d_{b} (s) .$ Thus Assumption 3 holds.

Set the contraction and overlap bounds to $α = exp (- 1/ t_{0}) > 0, L = exp (ζ) \geq 1.$ For any probability vectors $μ, μ^{'}$ on $S$ , the common-row identity gives $μ P_{b} = μ^{'} P_{b} = μ P_{e} = μ^{'} P_{e} = d_{test} .$ Consequently, $∥ μ P_{b} - μ^{'} P_{b} ∥_{TV} = ∥ μ P_{e} - μ^{'} P_{e} ∥_{TV} = 0 \leq α ∥ μ - μ^{'} ∥_{TV},$ which verifies Assumptions 5 and 6. Finally, $e (a ∣ x) = \frac{1}{2} \leq L \frac{1}{2} = L b (a ∣ x),$ so Assumption 4 holds. Together with $t_{0} > 0$ and $ζ \geq 0$ , these are precisely the conditions in Definition 1. Applying the argument at both signs proves the two membership assertions.

2. Target separation. The stationary probability law constructed above also supplies stationarity of the target-policy stationary law. Its common-row stationarity equation gives $d_{e} = d_{test}$ . Integrating the reward coordinate of the kernel gives $s^{'} \sum \int_{[0, 1]} y K_{v}^{(T)} (d y, s^{'} ∣ s, a) = q_{v} (h), r_{e} (x, h) = a = 0 \sum 1 \frac{1}{2} q_{v} (h) = q_{v} (h) .$ Define $θ_{v} := θ (K_{v}^{(T)}, e) .$ Using Definition 2 and summing the emission probabilities over $x$ , we obtain $θ_{v} = x, h \sum \frac{1}{2} E (x ∣ h) q_{v} (h) = \frac{1}{2} (\frac{3}{8} + v) + \frac{1}{2} (\frac{5}{8} + v) = \frac{1}{2} + v .$ Since $v_{T} \geq 0$ and $T > 0$ , $∣ θ_{+ v_{T}} - θ_{- v_{T}} ∣ = ∣2 v_{T} ∣ = 2 v_{T} = \frac{1}{8 T} .$

3. Finiteness of observed relative entropy. For either signed perturbation, define the finite path law, its decoded full trajectory law, and its observed law by $Q_{v} ({c}) dec (c) obs (s_{1}, \dots, s_{T + 1}; (a_{t}, y_{t})_{t = 1}^{T}) P_{v}^{full} = ω_{v} (c), = (s_{1}, \dots, s_{T + 1}; (a_{t}, y_{t})_{t = 1}^{T}), = ((x_{t}, a_{t}, y_{t}))_{t = 1}^{T}, = dec_{#} Q_{v}, P_{v}^{O_{T}} = obs_{#} P_{v}^{full} . c \in Ω_{path, T}, y_{t} regarded as a real reward, s_{t} = (x_{t}, h_{t}),$ The normalization calculation above gives $\sum_{c} ω_{v} (c) = 1$ . Both alternatives have positive masses on every finite path, so their full trajectory laws have common finite support. Thus $P_{+ v_{T}}^{full} ≪ P_{- v_{T}}^{full}, KL (P_{+ v_{T}}^{full} ∥ P_{- v_{T}}^{full}) < \infty.$ The log likelihood ratio is integrable because the common support is finite. Data processing under the observed projection now gives $KL (P_{+}^{O_{T}} ∥ P_{-}^{O_{T}}) \leq KL (P_{+ v_{T}}^{full} ∥ P_{- v_{T}}^{full}) < \infty, P_{\pm}^{O_{T}} := P_{\pm v_{T}}^{O_{T}} .$

4. The finite-path entropy bound. We first derive the one-epoch bound used in the product calculation. For $u, u^{'} \in [1/4, 3/4]$ , define $kl_{Ber} (u, u^{'}) φ (u) Ψ_{u^{'}} (u) = u lo g \frac{u}{u ^{'}} + (1 - u) lo g \frac{1 - u}{1 - u ^{'}}, = u lo g u + (1 - u) lo g (1 - u), = 4 (u - u^{'})^{2} + φ^{'} (u^{'}) (u - u^{'}) + φ (u^{'}) - φ (u) .$ Expanding the logarithms gives $kl_{Ber} (u, u^{'}) = φ (u) - φ (u^{'}) - φ^{'} (u^{'}) (u - u^{'}) .$ On the quarter band, $φ^{'} (u) = lo g u - lo g (1 - u), Ψ_{u^{'}}^{''} (u) = 8 - \frac{1}{u} - \frac{1}{1 - u} \geq 0,$ because $1/ u \leq 4$ and $1/ (1 - u) \leq 4$ . Hence $Ψ_{u^{'}}$ is convex on this interval, with $Ψ_{u^{'}} (u^{'}) = 0, Ψ_{u^{'}}^{'} (u^{'}) = 0.$ If $u = u^{'}$ , its value is zero. If $u < u^{'}$ , convexity gives $\frac{Ψ _{u^{'}} ( u ^{'} ) - Ψ _{u^{'}} ( u )}{u ^{'} - u} \leq Ψ_{u^{'}}^{'} (u^{'}) = 0.$ If $u > u^{'}$ , it gives $0 = Ψ_{u^{'}}^{'} (u^{'}) \leq \frac{Ψ _{u^{'}} ( u ) - Ψ _{u^{'}} ( u ^{'} )}{u - u ^{'}} .$ Thus $Ψ_{u^{'}} (u) \geq 0$ in all three cases, and therefore $kl_{Ber} (u, u^{'}) \leq 4 (u - u^{'})^{2} .$

Now take $v, v^{'} \in {- v_{T}, + v_{T}}$ . In the ratio of the two epoch masses, the common action, successor-hidden-state, and emission factors cancel. Summing over the binary action and reward gives $a, y \sum ℓ_{v} (s, s^{'}; a, y) lo g \frac{ℓ _{v} ( s , s ^{'} ; a , y )}{ℓ _{v^{'}} ( s , s ^{'} ; a , y )} = d_{test} (s^{'}) kl_{Ber} (q_{v} (h), q_{v^{'}} (h)) \leq 4 (v - v^{'})^{2} d_{test} (s^{'}), s = (x, h),$ where we used $q_{v} (h) - q_{v^{'}} (h) = v - v^{'}$ . Also, $a, y \sum ℓ_{v} (s, s^{'}; a, y) = d_{test} (s^{'}) .$

To add these bounds along a fixed state path, for $0 \leq n \leq T$ and $(s_{1}, \dots, s_{n + 1}) \in S^{n + 1}$ , define $W_{n} (s_{1}, \dots, s_{n + 1}) D_{v, v^{'}}^{(n)} (s_{1}, \dots, s_{n + 1}) = t = 1 \prod n d_{test} (s_{t + 1}), = (a_{t}, y_{t})_{t = 1}^{n} \sum (t = 1 \prod n ℓ_{v} (s_{t}, s_{t + 1}; a_{t}, y_{t})) lo g \frac{\prod _{t = 1}^{n} ℓ _{v} ( s _{t} , s _{t + 1} ; a _{t} , y _{t} )}{\prod _{t = 1}^{n} ℓ _{v^{'}} ( s _{t} , s _{t + 1} ; a _{t} , y _{t} )} .$ Empty products are $1$ , so $W_{0} = 1$ and $D_{v, v^{'}}^{(0)} = 0$ . We claim $D_{v, v^{'}}^{(n)} (s_{1}, \dots, s_{n + 1}) \leq 4 n (v - v^{'})^{2} W_{n} (s_{1}, \dots, s_{n + 1}) .$ The claim holds at $n = 0$ . For the induction step, splitting off the first epoch and expanding the logarithm of the product yields $D_{v, v^{'}}^{(n + 1)} (s_{1}, \dots, s_{n + 2}) = (a, y \sum ℓ_{v} (s_{1}, s_{2}; a, y) lo g \frac{ℓ _{v} ( s _{1} , s _{2} ; a , y )}{ℓ _{v^{'}} ( s _{1} , s _{2} ; a , y )}) W_{n} (s_{2}, \dots, s_{n + 2}) + d_{test} (s_{2}) D_{v, v^{'}}^{(n)} (s_{2}, \dots, s_{n + 2}) \leq 4 (v - v^{'})^{2} d_{test} (s_{2}) W_{n} (s_{2}, \dots, s_{n + 2}) + 4 n (v - v^{'})^{2} d_{test} (s_{2}) W_{n} (s_{2}, \dots, s_{n + 2}) = 4 (n + 1) (v - v^{'})^{2} W_{n + 1} (s_{1}, \dots, s_{n + 2}) .$ Here summing the tail product over its action and reward coordinates gives $W_{n}$ ; all multiplying masses are nonnegative. This proves the claim.

The common positive initial factor cancels from the path likelihood ratio. Consequently, $c \sum ω_{v} (c) lo g \frac{ω _{v} ( c )}{ω _{v^{'}} ( c )} = s_{1}, \dots, s_{T + 1} \sum ι (s_{1}) D_{v, v^{'}}^{(T)} (s_{1}, \dots, s_{T + 1}) \leq 4 T (v - v^{'})^{2} s_{1}, \dots, s_{T + 1} \sum ι (s_{1}) t = 1 \prod T d_{test} (s_{t + 1}) = 4 T (v - v^{'})^{2},$ since the last sum is $(s_{1} \sum ι (s_{1})) t = 1 \prod T (s_{t + 1} \sum d_{test} (s_{t + 1})) = 1.$

5. Projection and calibration. The finite laws have common positive support, so their relative entropy is the finite sum just bounded: $KL (Q_{v} ∥ Q_{v^{'}}) = c \sum ω_{v} (c) lo g \frac{ω _{v} ( c )}{ω _{v^{'}} ( c )} \leq 4 T (v - v^{'})^{2} .$ Applying data processing first to decoding and then to the observed projection gives $KL (P_{v}^{O_{T}} ∥ P_{v^{'}}^{O_{T}}) \leq KL (P_{v}^{full} ∥ P_{v^{'}}^{full}) \leq KL (Q_{v} ∥ Q_{v^{'}}) \leq 4 T (v - v^{'})^{2} .$ For the ordered pair $v = v_{T}$ , $v^{'} = - v_{T}$ , positivity of $T$ and $(T)^{2} = T$ give $4 T (v_{T} - (- v_{T}))^{2} = 16 T (\frac{1}{16 T})^{2} = \frac{1}{16} .$ Therefore the finite observed relative entropy satisfies $KL (P_{+}^{O_{T}} ∥ P_{-}^{O_{T}}) \leq \frac{1}{16} \leq \frac{1}{12} .$

6. Coincident stationary laws and occupancy bounds. In each experiment the policies coincide pointwise: $e (a ∣ x) = b (a ∣ x) = \frac{1}{2} .$ They therefore induce the same transition matrix, and applying the same stationary-law selection to that matrix gives $P_{e} = P_{b}, d_{e} = d_{b} .$ By stationary start, $d_{b} (s) \geq 0$ for every $s \in S$ . For every $C > 1$ , $C d_{b} (s) - d_{e} (s) = (C - 1) d_{b} (s) \geq 0.$ Hence $d_{e} (s) \leq C d_{b} (s)$ for every state in each experiment, with the same calculation covering zero stationary mass.

∎

The separation and divergence clauses in Lemma 3 are the two statistical inputs to the lower bound in Theorem 2. They have the standard two-point interpretation: nearby observed laws carry stationary values separated at the $T^{- 1/2}$ scale (Tsybakov, 2009). Because the divergence concerns the projected observed laws, the resulting risk statement addresses the observed-data decision problem in Definition 4. Equality of the stationary occupancies also places both experiments in every stated stationary-overlap subclass with bound $C > 1$ .

Minimax assembly and the remaining results

The upper and lower inputs meet in Theorem 2. The stable-grid guarantee supplies an admissible observed-data estimator, while the testing-family membership and separation supply the pair used for the lower bound. The minimax definition in Definition 4 ranges over measurable observed-data procedures taking values in $[0, 1]$ , matching the estimator class in the testing argument. Together, these components yield the bounds $1/ (1024 T)$ and $B_{α}^{2} (112 V_{α, L} + 2) / T$ under the theorem’s stated regime conditions.

The cardinality comparison in Theorem 2 uses the cardinality-uniform conclusion of the public working manuscript CausalSmith (2026). Its logarithmic-depth schedule and associated risk bound are the cited comparison inputs; the additional conditions are $ζ > 0$ and $C > 1$ .

For Proposition 1, the relevant ingredients are equality of the induced policy transitions, stationary initialization, and behavior contraction. They support the common stationary law and the ordinary reward-mean interpretation of the target value. Under that proposition’s conditions, the reward sample mean is unbiased and satisfies the displayed variance bound for every $T \geq 1$ . This gives the sampling benchmark corresponding to coincident behavior and target policies.

The remaining deterministic result, Proposition 2, concerns the size of the candidate list. Its five simplex factors correspond to the initial law and the four transition rows; its four scalar-grid factors correspond to the reward coordinates. The exact unfiltered count is $(3 M + 3)^{5} (M + 1)^{4}$ , and the contraction filter retains a subset of that list. At the stated resolution and fixed mixing scale, the proposition bounds both list cardinalities by $c T^{19}$ .

Verification scope.

The internal mathematical statements and their proofs are machine-checked in Lean 4, including the auxiliary lemmas above, the stable-grid risk bound, the binary testing and minimax arguments, the coincident-policy reduction, and the candidate counts. The checked artifact uses Lean 4.33.0 and mathlib revision db584cd6d46c92f209a44c0f1c829460d327499d; the verification commit is 96e526d2af264e63a1ace1820aac7f8843203708. The generated interactive supplement includes presentation_crosswalk.json, which maps each paper object to its certifying declarations, and lean_snippets.json, which records the corresponding source snippets. The six data-generating restrictions in Definition 1 are assumptions of the statistical guarantees. The cardinality-uniform comparison inputs from the public working manuscript used in Theorem 2 remain cited dependencies; the theorem-local verification disclosures specify their trust boundary.

Proofs of the main results

Proof of Theorem 1.

Fix an experiment in $M_{T}^{(2)} (t_{0}, ζ)$ . All expectations below are under its observed trajectory law, denoted by $E_{M}$ . Use the moments of Definition 3 and the joint-state quantities of Lemma 2.

Use zero-based epochs throughout this proof: epoch $t$ here corresponds to epoch $t + 1$ in Definition 3. Accordingly, define the shifted scores by $Z_{t} (k) := Y_{t + 1} j = t - k + 1 \prod t + 1 ρ_{j}, 0 \leq k \leq 6, k \leq t < T,$ where the reward and likelihood ratios on the right retain their one-based indexing. Thus $Z_{t} (k)$ is the score at one-based epoch $t + 1$ , agreeing with the zero-based convention of Lemma 2.

Define the retained epoch set, its cardinality, and the maximum empirical moment error by $I_{T} := {6, \dots, T - 1}, n_{T} := ∣ I_{T} ∣ = T - 6, ϵ_{T} (w) := 0 \leq k \leq 6 max ∣ m_{k} (w) - m_{k} ∣,$ where $w \in (X \times A \times R)^{T}$ is an observed trajectory. Changing variables in the one-based retained-window sum gives $m_{k} = \frac{1}{T - 6} t = 6 \sum T - 1 Z_{t} (k) = \frac{1}{n _{T}} t \in I_{T} \sum Z_{t} (k), 0 \leq k \leq 6.$ The parameter conditions give $0 < α = exp (- 1/ t_{0}) < 1, L = exp (ζ) \geq 1, B_{α} \geq 0, V_{α, L} \geq 0,$ and the horizon condition gives $T > 0, n_{T} > 0, T \leq 2 n_{T}, T \geq 1.$ The maximum defining $ϵ_{T} (w)$ is attained among seven indices. Its square is therefore one of the nonnegative summands on the right-hand side of $ϵ_{T} (w)^{2} \leq k = 0 \sum 6 (m_{k} (w) - m_{k})^{2} .$ The observed law is a probability law, and the empirical moments are square-integrable. Thus the sum on the right is integrable; measurability of the finite maximum and the displayed domination also give integrability of $ϵ_{T}^{2}$ .
For $0 \leq k \leq 6$ and $t, t^{'} \in I_{T}$ , define $c_{k; t, t^{'}} := E_{M} [(Z_{t} (k) - m_{k}) (Z_{t^{'}} (k) - m_{k})] .$ Every retained epoch satisfies $k \leq t$ . Consequently, Lemma 2 supplies $E_{M} [Z_{t} (k)] = m_{k} = d_{b} P_{e}^{k} r_{e}, E_{M} [Z_{t} (k)^{2}] \leq L^{k + 1} .$ In particular, $0 \leq c_{k; t, t} = E_{M} [(Z_{t} (k) - m_{k})^{2}] = E_{M} [Z_{t} (k)^{2}] - m_{k}^{2} \leq L^{k + 1} .$ For either choice of sign, nonnegativity of the centered square gives $0 \leq E_{M} [((Z_{t} (k) - m_{k}) \pm (Z_{t^{'}} (k) - m_{k}))^{2}] = c_{k; t, t} + c_{k; t^{'}, t^{'}} \pm 2 c_{k; t, t^{'}} .$ Using both signs yields $∣ c_{k; t, t^{'}} ∣ \leq \frac{c _{k; t, t} + c _{k; t^{'}, t^{'}}}{2} \leq L^{k + 1} .$ For separated epochs, the covariance conclusion of Lemma 2 additionally gives $∣ c_{k; t, t^{'}} ∣ \leq α^{t^{'} - t - k - 1} when t^{'} - t \geq k + 1.$ These identities and bounds apply under the observed law because the scores are functions of the observed trajectory.
Fix $0 \leq k \leq 6$ and $t \in I_{T}$ . Partition its future retained epochs according to whether $1 \leq t^{'} - t \leq k$ or $t^{'} - t \geq k + 1$ . There are at most $k$ epochs in the first part. In the second part, the exponents $t^{'} - t - k - 1$ are distinct integers in ${0, \dots, T - 1}$ . Hence $t^{'} \in I_{T} t < t^{'} \sum ∣ c_{k; t, t^{'}} ∣ = t^{'} \in I_{T} 1 \leq t^{'} - t \leq k \sum ∣ c_{k; t, t^{'}} ∣ + t^{'} \in I_{T} t^{'} - t \geq k + 1 \sum ∣ c_{k; t, t^{'}} ∣ \leq k L^{k + 1} + j = 0 \sum T - 1 α^{j} = k L^{k + 1} + \frac{1 - α ^{T}}{1 - α} \leq k L^{k + 1} + \frac{1}{1 - α} .$ For $k = 0$ , the first sum is empty and equals zero. Symmetry of covariance allows the full absolute covariance sum to be split into its diagonal and twice its upper triangle: $t \in I_{T} \sum t^{'} \in I_{T} \sum c_{k; t, t^{'}} \leq t \in I_{T} \sum t^{'} \in I_{T} \sum ∣ c_{k; t, t^{'}} ∣ = t \in I_{T} \sum ∣ c_{k; t, t} ∣ + 2 t \in I_{T} \sum t^{'} \in I_{T} t < t^{'} \sum ∣ c_{k; t, t^{'}} ∣ \leq n_{T} L^{k + 1} + 2 n_{T} (k L^{k + 1} + \frac{1}{1 - α}) = n_{T} ((1 + 2 k) L^{k + 1} + \frac{2}{1 - α}) \leq n_{T} (13 L^{7} + \frac{2}{1 - α}) = n_{T} V_{α, L} .$ The last inequality uses $k \leq 6$ and $L \geq 1$ .

Averaging the score means over the common window gives $E_{M} [m_{k}] = \frac{1}{n _{T}} t \in I_{T} \sum E_{M} [Z_{t} (k)] = m_{k} .$ Expanding the centered square of this finite average therefore yields $E_{M} [(m_{k} - m_{k})^{2}] = \frac{1}{n _{T}^{2}} t \in I_{T} \sum t^{'} \in I_{T} \sum c_{k; t, t^{'}} \leq \frac{V _{α, L}}{n _{T}} .$
Integrating $ϵ_{T} (w)^{2} \leq \sum_{k = 0}^{6} (m_{k} (w) - m_{k})^{2}$ and applying the seven moment bounds gives $E_{M} [ϵ_{T}^{2}] \leq k = 0 \sum 6 E_{M} [(m_{k} - m_{k})^{2}] \leq \frac{7 V _{α, L}}{n _{T}} .$
We next obtain a value bound for the selected grid realization. To distinguish the grid resolution from the fixed experiment, write $M_{grid} := ⌈ (22 + 36/ α) T ⌉, U := \frac{1 1 ^{T}}{4}, λ := \frac{α}{α + 6/ M _{grid}} .$ Here $1$ is the four-dimensional vector of ones. Thus $M_{grid} > 0, 0 < λ < 1, P (R) = λ R + (1 - λ) U .$ Use a fixed ordering of the four joint states as the four grid coordinates; this relabeling preserves scalar matrix moments and total variation.

The candidate set of Algorithm 1 is finite and nonempty. Indeed, $((1, 0, 0, 0), 1 (1, 0, 0, 0), (0, 0, 0, 0)) \in C_{M_{grid}},$ because all its coordinates lie on the required grids and $δ (1 (1, 0, 0, 0)) = 0 \leq α + \frac{6}{M _{grid}} .$ The lexicographic minimizer therefore belongs to this candidate set.

For every candidate $(ν, R, r)$ , its stabilized matrix is row-stochastic and satisfies $P (R)_{ij} \geq \frac{1 - λ}{4} .$ The common uniform component cancels between rows, so $δ (P (R)) = λ δ (R) \leq λ (α + \frac{6}{M _{grid}}) = α .$ The same uniform minorization gives, for probability rows $μ, μ^{'}$ , $∥ μ P (R) - μ^{'} P (R) ∥_{TV} \leq λ ∥ μ - μ^{'} ∥_{TV} .$ Since $λ < 1$ , contraction on the finite probability simplex supplies a stationary probability row: $π (P (R)) P (R) = π (P (R)), π (P (R))_{i} \geq 0, i = 1 \sum 4 π (P (R))_{i} = 1.$

Write the selected quantities as in Algorithm 1: $(ν_{*}, R_{*}, r_{*}) \in C_{M_{grid}}, P_{*} := P (R_{*}), θ_{T} = π (P_{*}) r_{*} .$ The experiment’s class conditions give a row-stochastic $P_{e}$ , probability rows $d_{b}, d_{e}$ , and a unit-range reward vector: $P_{e} (i, j) \geq 0, j \sum P_{e} (i, j) = 1, d_{b} (i), d_{e} (i) \geq 0, i \sum d_{b} (i) = i \sum d_{e} (i) = 1,$ $d_{e} P_{e} = d_{e}, 0 \leq r_{e} (i) \leq 1.$ Applying Assumption 6 to point masses gives $δ (P_{e}) = i, j max \frac{1}{2} s \sum ∣ P_{e} (i, s) - P_{e} (j, s) ∣ \leq α .$ Together with $θ = d_{e} r_{e}$ from Definition 2, these facts discharge the hypotheses of Lemma 1. Its value bound is $∣ θ_{T} - θ ∣ \leq B_{α} 0 \leq k \leq 6 max ∣ ν_{*} P_{*}^{k} r_{*} - d_{b} P_{e}^{k} r_{e} ∣ = B_{α} 0 \leq k \leq 6 max ∣ ν_{*} P_{*}^{k} r_{*} - m_{k} ∣.$
Construct an approximating candidate by rounding. For every probability row $μ$ on the four coordinates, define $(R_{grid} (μ))_{i} := ⎩ ⎨ ⎧ ⌊ M_{grid} μ_{i} ⌋ / M_{grid}, 1 - j = 1 \sum 3 ⌊ M_{grid} μ_{j} ⌋ / M_{grid}, i = 1, 2, 3, i = 4.$ The first three coordinates are rounded down, and their sum is at most one. The fourth coordinate is therefore nonnegative, is a grid multiple, and makes the total mass one. For $i = 1, 2, 3$ , $0 \leq μ_{i} - (R_{grid} (μ))_{i} \leq \frac{1}{M _{grid}},$ while $μ_{4} - (R_{grid} (μ))_{4} = - i = 1 \sum 3 (μ_{i} - (R_{grid} (μ))_{i}) .$ Consequently, $∥ μ - R_{grid} (μ) ∥_{TV} = \frac{1}{2} i = 1 \sum 4 μ_{i} - (R_{grid} (μ))_{i} = i = 1 \sum 3 (μ_{i} - (R_{grid} (μ))_{i}) \leq \frac{3}{M _{grid}} .$

Define the rounded initial row, transition rows, and rewards by $ν_{grid} := R_{grid} (d_{b}), R_{grid} (i, \cdot) := R_{grid} (P_{e} (i, \cdot)), r_{grid} (i) := \frac{⌊ M _{grid} r _{e} ( i )⌋}{M _{grid}} .$ They satisfy $∥ ν_{grid} - d_{b} ∥_{TV} \leq \frac{3}{M _{grid}}, i max ∥ R_{grid} (i, \cdot) - P_{e} (i, \cdot) ∥_{TV} \leq \frac{3}{M _{grid}},$ $0 \leq r_{grid} (i) \leq 1, 0 \leq r_{e} (i) - r_{grid} (i) \leq \frac{1}{M _{grid}} .$ For each pair of rows, the triangle inequality gives $∥ R_{grid} (i, \cdot) - R_{grid} (j, \cdot) ∥_{TV} \leq ∥ R_{grid} (i, \cdot) - P_{e} (i, \cdot) ∥_{TV} + ∥ P_{e} (i, \cdot) - P_{e} (j, \cdot) ∥_{TV} + ∥ P_{e} (j, \cdot) - R_{grid} (j, \cdot) ∥_{TV} \leq α + \frac{6}{M _{grid}} .$ Taking the maximum over the row pair proves $δ (R_{grid}) \leq α + \frac{6}{M _{grid}}, (ν_{grid}, R_{grid}, r_{grid}) \in C_{M_{grid}} .$
Define the stabilized approximating matrix by $P_{grid} := P (R_{grid}) = λ R_{grid} + (1 - λ) U .$ For every row, its distance from the uniform probability row is at most one. Also, $1 - λ = \frac{6/ M _{grid}}{α + 6/ M _{grid}} \leq \frac{6}{α M _{grid}} .$ It follows that $∥ R_{grid} (i, \cdot) - P_{grid} (i, \cdot) ∥_{TV} = (1 - λ) ∥ R_{grid} (i, \cdot) - U (i, \cdot) ∥_{TV} \leq \frac{6}{α M _{grid}},$ and hence $∥ P_{e} (i, \cdot) - P_{grid} (i, \cdot) ∥_{TV} \leq \frac{3 + 6/ α}{M _{grid}} .$

For every integer $k \geq 0$ , stochasticity and the reward bounds imply $0 \leq (P_{e}^{k} r_{e}) (i) \leq 1.$ Integration of a $[0, 1]$ -valued function against the difference of two probability rows is bounded by their total variation distance: centering that function at $1/2$ gives this bound directly. We claim $∥ P_{e}^{k} r_{e} - P_{grid}^{k} r_{grid} ∥_{\infty} \leq \frac{k ( 3 + 6/ α ) + 1}{M _{grid}}, k \geq 0.$ For $k = 0$ , this is the reward-rounding bound. At the induction step, insert $P_{grid} P_{e}^{k} r_{e}$ between the two expressions. The row approximation bound controls the first difference, and averaging the previous error with a stochastic row controls the second: $∥ P_{e}^{k + 1} r_{e} - P_{grid}^{k + 1} r_{grid} ∥_{\infty} \leq ∥ (P_{e} - P_{grid}) P_{e}^{k} r_{e} ∥_{\infty} + ∥ P_{grid} (P_{e}^{k} r_{e} - P_{grid}^{k} r_{grid}) ∥_{\infty} \leq \frac{3 + 6/ α}{M _{grid}} + ∥ P_{e}^{k} r_{e} - P_{grid}^{k} r_{grid} ∥_{\infty} \leq \frac{( k + 1 ) ( 3 + 6/ α ) + 1}{M _{grid}} .$ The initial-distribution error can now be separated from the power-and-reward error: $∣ m_{k} - ν_{grid} P_{grid}^{k} r_{grid} ∣ = ∣ d_{b} P_{e}^{k} r_{e} - ν_{grid} P_{grid}^{k} r_{grid} ∣ \leq ∣ (d_{b} - ν_{grid}) P_{e}^{k} r_{e} ∣ + ∣ ν_{grid} (P_{e}^{k} r_{e} - P_{grid}^{k} r_{grid}) ∣ \leq \frac{3}{M _{grid}} + \frac{k ( 3 + 6/ α ) + 1}{M _{grid}} = \frac{4 + k ( 3 + 6/ α )}{M _{grid}} .$ For $0 \leq k \leq 6$ , the coefficient and ceiling calibration give $4 + k (3 + 6/ α) \leq 22 + 36/ α, (22 + 36/ α) T \leq M_{grid},$ so $∣ m_{k} - ν_{grid} P_{grid}^{k} r_{grid} ∣ \leq \frac{22 + 36/ α}{M _{grid}} \leq \frac{1}{T} .$
Fix an observed trajectory $w$ . The approximating candidate has empirical discrepancy bounded by $0 \leq k \leq 6 max ∣ m_{k} (w) - ν_{grid} P_{grid}^{k} r_{grid} ∣ \leq 0 \leq k \leq 6 max ∣ m_{k} (w) - m_{k} ∣ + 0 \leq k \leq 6 max ∣ m_{k} - ν_{grid} P_{grid}^{k} r_{grid} ∣ \leq ϵ_{T} (w) + T^{- 1} .$ Because the selected candidate minimizes this discrepancy, $0 \leq k \leq 6 max ∣ m_{k} (w) - ν_{*} P_{*}^{k} r_{*} ∣ \leq ϵ_{T} (w) + T^{- 1} .$ Applying the triangle inequality once more gives $0 \leq k \leq 6 max ∣ ν_{*} P_{*}^{k} r_{*} - m_{k} ∣ \leq 0 \leq k \leq 6 max ∣ ν_{*} P_{*}^{k} r_{*} - m_{k} (w) ∣ + ϵ_{T} (w) \leq 2 ϵ_{T} (w) + T^{- 1} .$ Combining this with the value modulus obtained above yields $∣ θ_{T} (w) - θ ∣ \leq B_{α} (2 ϵ_{T} (w) + T^{- 1}) .$ The right-hand side is nonnegative, so squaring preserves the inequality. Moreover, $(2 ϵ_{T} (w) - T^{- 1})^{2} \geq 0$ gives $(θ_{T} (w) - θ)^{2} \leq B_{α}^{2} (2 ϵ_{T} (w) + T^{- 1})^{2} \leq B_{α}^{2} (8 ϵ_{T} (w)^{2} + 2 T^{- 2}) .$
The sampling and grid terms admit separate horizon bounds. Since $V_{α, L} \geq 0$ and $T \leq 2 n_{T}$ , $56 V_{α, L} T \leq 112 V_{α, L} n_{T} .$ Dividing by the positive product $n_{T} T$ gives $8 (\frac{7 V _{α, L}}{n _{T}}) = \frac{56 V _{α, L}}{n _{T}} \leq \frac{112 V _{α, L}}{T} .$ Also, $T \geq 1$ implies $T^{2} \geq T > 0$ , and therefore $T^{- 2} \leq T^{- 1} .$
The pointwise upper bound is integrable by integrability of $ϵ_{T}^{2}$ . Monotonicity of integration for the nonnegative squared loss, followed by linearity of expectation under a probability law, now gives $E_{M} [(θ_{T} - θ)^{2}] \leq E_{M} [B_{α}^{2} (8 ϵ_{T}^{2} + 2 T^{- 2})] = B_{α}^{2} (8 E_{M} [ϵ_{T}^{2}] + 2 T^{- 2}) \leq B_{α}^{2} (8 \frac{7 V _{α, L}}{n _{T}} + 2 T^{- 2}) \leq B_{α}^{2} (\frac{112 V _{α, L}}{T} + \frac{2}{T}) = \frac{B _{α}^{2} ( 112 V _{α, L} + 2 )}{T} .$ The fixed experiment was arbitrary, and every bound uses the same constants throughout the stated class.

∎

Proof of Theorem 2.

Define the two testing experiments, their target values, and their observed laws by $M_{\pm} θ_{\pm} P_{\pm}^{O_{T}} := the experiment of Definition 5 with v = \pm v_{T}, := θ (K_{\pm v_{T}}^{(T)}, e), := L_{M_{\pm}} (O_{T}) .$ By Lemma 3, $M_{\pm} \in M_{T}^{(2)} (t_{0}, ζ), ∣ θ_{+} - θ_{-} ∣ = \frac{1}{8 T}, KL (P_{+}^{O_{T}} ∥ P_{-}^{O_{T}}) \leq \frac{1}{12},$ and the relative entropy is finite. Both experiments supply the same fair behavior and target policies to the estimator.
Fix an admissible estimator $θ$ from Definition 4. Because its supplied policies agree across the pair, it is the same measurable function of the observed trajectory in both experiments. Pinsker’s inequality gives $P_{+}^{O_{T}} - P_{-}^{O_{T}}_{TV} \leq \frac{KL ( P _{+}^{O_{T}} ∥ P _{-}^{O_{T}} )}{2} \leq \frac{1}{24} \leq \frac{1}{4} .$ Define the error threshold and the two measurable error events by $ε_{test} := \frac{1}{16 T}, E_{\pm} := {∣ θ - θ_{\pm} ∣ \geq ε_{test}} .$ Then $∣ θ_{+} - θ_{-} ∣ = 2 ε_{test}, E_{+}^{c} \subseteq E_{-},$ where the inclusion follows from the triangle inequality. Consequently, $P_{+}^{O_{T}} (E_{+}) + P_{-}^{O_{T}} (E_{-}) \geq P_{+}^{O_{T}} (E_{+}) + P_{-}^{O_{T}} (E_{+}^{c}) \geq 1 - P_{+}^{O_{T}} - P_{-}^{O_{T}}_{TV} \geq \frac{3}{4} .$ Thus $max {P_{+}^{O_{T}} (E_{+}), P_{-}^{O_{T}} (E_{-})} \geq \frac{3}{8} .$ For each sign, integrating the pointwise inequality $(θ - θ_{\pm})^{2} \geq ε_{test}^{2} 1_{E_{\pm}}$ gives $E_{M_{\pm}} [(θ - θ_{\pm})^{2}] \geq ε_{test}^{2} P_{\pm}^{O_{T}} (E_{\pm}) .$ If the positive-sign error probability is at most the negative-sign error probability, apply this inequality to the negative sign; in the opposite case, apply it to the positive sign. In either case, $max {E_{M_{+}} [(θ - θ_{+})^{2}], E_{M_{-}} [(θ - θ_{-})^{2}]} \geq \frac{3}{8} ε_{test}^{2} = \frac{3}{2048 T} \geq \frac{1}{1024 T},$ using $(T)^{2} = T > 0$ .
For any admissible experiment $M$ , define its risk by $R (θ, M) := E_{M} [(θ - θ)^{2}], M \in M_{T}^{(2)} (t_{0}, ζ) .$ The target value in Definition 2 is a stationary average of rewards in $[0, 1]$ . Since the estimator also takes values in $[0, 1]$ , $0 \leq θ \leq 1, 0 \leq (θ - θ)^{2} \leq 1, 0 \leq R (θ, M) \leq 1.$ Thus every estimator’s risks are bounded above over the class. The estimator family is nonempty, as witnessed by the constant estimator $θ_{0} \equiv 0.$ Membership of the testing pair and the preceding two-point bound therefore give $R_{T}^{(2)} (t_{0}, ζ) = θ in f M \in M_{T}^{(2)} (t_{0}, ζ) sup R (θ, M) \geq θ in f max {R (θ, M_{+}), R (θ, M_{-})} \geq \frac{1}{1024 T} .$
Use the stable-grid estimator of Algorithm 1. Its selected reward vector and stationary probability vector satisfy $0 \leq r_{*} \leq 1, π (P_{*}) \geq 0, π (P_{*}) 1 = 1.$ Hence $0 \leq θ_{T} = π (P_{*}) r_{*} \leq π (P_{*}) 1 = 1.$ The finite candidate selection uses measurable comparison events, and the selected stationary reward is therefore measurable for each pair of supplied policies. This makes $θ_{T}$ admissible in Definition 4. By Theorem 1, $R (θ_{T}, M) \leq \frac{B _{α}^{2} ( 112 V _{α, L} + 2 )}{T} for every M \in M_{T}^{(2)} (t_{0}, ζ) .$ The class is nonempty because it contains $M_{+}$ . Nonnegativity of the risks and the defining infimum and supremum now yield $R_{T}^{(2)} (t_{0}, ζ) \leq M \in M_{T}^{(2)} (t_{0}, ζ) sup R (θ_{T}, M) \leq \frac{B _{α}^{2} ( 112 V _{α, L} + 2 )}{T} .$
The remaining assertions about the binary testing pair follow from Lemma 3: $e (a ∣ x) = b (a ∣ x) = \frac{1}{2}, d_{e} = d_{b},$ and, for every $C > 1$ , $d_{e} (s) \leq C d_{b} (s) for every s \in S .$ Together with the estimator-wise two-point risk bound, these establish all the stated properties of the pair.
Suppose now that $ζ > 0$ , and fix $C > 1$ . Use the theorem’s notation $β = \frac{2}{2 + t _{0} ζ}, q_{C} = \frac{C - 1}{C} .$ The cited cardinality-uniform result supplies its signed-depth lower construction (CausalSmith, 2026). Specifically, there are $c_{Reset} > 0, Q : N \to N, a_{1}, a_{2} > 0$ such that, for every sufficiently large $n$ , $a_{1} lo g n \leq Q (n) \leq a_{2} lo g n, n \geq 1, Q (n) \geq 1.$ For these $n$ , define $M_{n, \pm}^{Reset} θ_{n, \pm}^{Reset} := the signed depth- Q (n) reset experiments, := their respective stationary target values .$ Each experiment has exactly $2 (Q (n) + 1)$ hidden states. For every admissible observable-data estimator $θ_{Reset}$ in the reset decision problem, with values in $[- 1, 1]$ , the cited construction gives $max {E_{M_{n, -}^{Reset}} [(θ_{Reset} - θ_{n, -}^{Reset})^{2}], E_{M_{n, +}^{Reset}} [(θ_{Reset} - θ_{n, +}^{Reset})^{2}]} \geq c_{Reset} n^{- β} .$ Finally, the same eventual condition $Q (n) \geq 1$ gives $2 (Q (n) + 1) \geq 4 > 2,$ which proves the asserted cardinality inequality for the negative-sign experiment.
Since $t_{0} ζ > 0$ , $2 + t_{0} ζ > 2 > 0, 0 < β = \frac{2}{2 + t _{0} ζ} < 1, 1 - β > 0.$ Also, $C > 1$ implies $q_{C} > 0, q_{C}^{2 (1 - β)} > 0.$
Along the positive natural numbers, the negative-power limit gives $n^{- (1 - β)} ⟶ 0.$ Multiplication by the fixed constant $q_{C}^{- 2 (1 - β)}$ preserves this limit. For every $n \geq 1$ , the laws of real powers give $\frac{n ^{- 1}}{n ^{- β}} = n^{β - 1} = n^{- (1 - β)},$ and hence $\frac{n ^{- 1}}{n ^{- β} q _{C}^{2 (1 - β)}} = n^{- (1 - β)} q_{C}^{- 2 (1 - β)} ⟶ 0.$ This proves the claimed limit and completes the proof.

∎

Proof of Proposition 1.

We use epochs $1, \dots, T$ , shifting the zero-based epochs of Lemma 2 by one. Every sum over an empty range is understood to be zero.

Since $e = b$ , substitution in the policy-induced transition matrices gives, for every $s = (x, h) \in S$ and $s^{'} \in S$ , $P_{e} (s, s^{'}) = a \in {0, 1} \sum e (a ∣ x) \int_{[0, 1]} K (d y, s^{'} ∣ s, a) = a \in {0, 1} \sum b (a ∣ x) \int_{[0, 1]} K (d y, s^{'} ∣ s, a) = P_{b} (s, s^{'}) .$ The stationary-law assignment evaluated at these identical matrices likewise gives $d_{e} = d_{b} .$
We first verify membership in the class of Definition 1 at logarithmic overlap parameter $ζ = 0$ . Sequential assignment and $e = b$ give $e (a ∣ x) = b (a ∣ x) \geq 0, a \in {0, 1} \sum e (a ∣ x) = 1, e (a ∣ x) \leq exp (0) b (a ∣ x) = b (a ∣ x) .$ Thus Assumption 4 holds with $L = 1$ . Moreover, for every $μ, μ^{'} \in Δ (S)$ , $∥ μ P_{e} - μ^{'} P_{e} ∥_{TV} = ∥ μ P_{b} - μ^{'} P_{b} ∥_{TV} \leq α ∥ μ - μ^{'} ∥_{TV},$ so Assumption 6 follows from Assumption 5. Together with the remaining hypotheses, these facts establish membership in $M_{T}^{(2)} (t_{0}, 0)$ .

Write the target-policy conditional mean reward vector as $r_{e} (s) := a \in {0, 1} \sum e (a ∣ x) s^{'} \in S \sum \int_{[0, 1]} y K (d y, s^{'} ∣ s, a), s = (x, h) \in S .$ Applying Lemma 2 at depth zero gives, at every observed epoch, $m_{0} = d_{b} P_{e}^{0} r_{e} = d_{b} r_{e} = d_{e} r_{e} = θ,$ where the last equality is Definition 2.
To identify this moment with the ordinary reward mean, define the observed action likelihood ratio and depth-zero score by $ρ_{t} := {e (A_{t} ∣ X_{t}) / b (A_{t} ∣ X_{t}), 0, b (A_{t} ∣ X_{t}) > 0, b (A_{t} ∣ X_{t}) = 0, Z_{t} (0) := Y_{t} ρ_{t}, 1 \leq t \leq T .$ Here probability and expectation are taken under the behavior experiment. By Assumption 2, $b Pr (b (A_{t} ∣ X_{t}) = 0) = E_{b} a \in {0, 1} b (a ∣ X_{t}) = 0 \sum b (a ∣ X_{t}) = 0.$ On the complementary event, $e = b$ gives $ρ_{t} = 1$ . Consequently, $Z_{t} (0) = Y_{t} almost surely, E_{b} [Y_{t}] = E_{b} [Z_{t} (0)] = m_{0} = θ .$
Define the sample mean by $\overline{Y}_{T} := T^{- 1} t = 1 \sum T Y_{t} .$ The bounded rewards are integrable, so linearity of expectation and $T \geq 1$ yield $E_{b} [\overline{Y}_{T}] = T^{- 1} t = 1 \sum T E_{b} [Y_{t}] = T^{- 1} T θ = θ .$
The reward support and Assumption 1 give $b Pr (Y_{t} \in [0, 1]) = E_{b} [K ([0, 1] \times S ∣ S_{t}, A_{t})] = 1.$ Thus every reward is square integrable. For square-integrable real random variables $W_{1}, W_{2}$ under the behavior law, use $Cov_{b} (W_{1}, W_{2}) := E_{b} [(W_{1} - E_{b} [W_{1}]) (W_{2} - E_{b} [W_{2}])], Var_{b} (W_{1}) := Cov_{b} (W_{1}, W_{1}) .$ Since $t_{0} > 0$ , $0 \leq α = exp (- 1/ t_{0}) < 1.$ Also $Y_{t}^{2} \leq 1$ almost surely, and hence $E_{b} [Y_{t}^{2}] \leq E_{b} [1] = 1, Cov_{b} (Y_{t}, Y_{t}) = E_{b} [Y_{t}^{2}] - (E_{b} [Y_{t}])^{2} \leq 1.$
Expanding the variance of the reward sum gives $Var_{b} (t = 1 \sum T Y_{t}) = t = 1 \sum T u = 1 \sum T Cov_{b} (Y_{t}, Y_{u}) .$ For $1 \leq t < u \leq T$ , Lemma 2, applied at depth zero in the class established above, supplies $∣ E_{b} [(Z_{t} (0) - m_{0}) (Z_{u} (0) - m_{0})] ∣ \leq α^{u - t - 1} .$ Using the almost-sure score identities and reward means already established, $Cov_{b} (Y_{t}, Y_{u}) = E_{b} [(Z_{t} (0) - m_{0}) (Z_{u} (0) - m_{0})],$ and therefore $Cov_{b} (Y_{t}, Y_{u}) \leq ∣ Cov_{b} (Y_{t}, Y_{u}) ∣ \leq α^{u - t - 1} .$

To bound each covariance row, first use the finite geometric identity $(1 - α) ℓ = 0 \sum T - 1 α^{ℓ} = 1 - α^{T} \leq 1, ℓ = 0 \sum T - 1 α^{ℓ} \leq \frac{1}{1 - α} .$ Here $ℓ$ is a nonnegative integer exponent. For fixed $t$ , the exponent maps $u \mapsto t - u - 1$ on $1 \leq u < t$ and $u \mapsto u - t - 1$ on $t < u \leq T$ are injective and take values in ${0, \dots, T - 1}$ . Because all powers of $α$ are nonnegative, symmetry of covariance gives $u = 1 \sum t - 1 Cov_{b} (Y_{t}, Y_{u}) u = t + 1 \sum T Cov_{b} (Y_{t}, Y_{u}) = u = 1 \sum t - 1 Cov_{b} (Y_{u}, Y_{t}) \leq u = 1 \sum t - 1 α^{t - u - 1} \leq ℓ = 0 \sum T - 1 α^{ℓ} \leq \frac{1}{1 - α}, \leq u = t + 1 \sum T α^{u - t - 1} \leq ℓ = 0 \sum T - 1 α^{ℓ} \leq \frac{1}{1 - α} .$ These inequalities include the empty past or future ranges at the endpoints. Splitting the row into its diagonal, past, and future parts now yields $u = 1 \sum T Cov_{b} (Y_{t}, Y_{u}) = Cov_{b} (Y_{t}, Y_{t}) + u = 1 \sum t - 1 Cov_{b} (Y_{t}, Y_{u}) + u = t + 1 \sum T Cov_{b} (Y_{t}, Y_{u}) \leq 1 + \frac{2}{1 - α} .$ Summing over $t$ proves $Var_{b} (t = 1 \sum T Y_{t}) \leq T (1 + \frac{2}{1 - α}) .$
Finally, unbiasedness identifies the mean squared error with the variance. Rescaling the preceding bound, using $T > 0$ , gives $E_{b} [(\overline{Y}_{T} - θ)^{2}] = Var_{b} (\overline{Y}_{T}) = T^{- 2} Var_{b} (t = 1 \sum T Y_{t}) \leq T^{- 2} T (1 + \frac{2}{1 - α}) = \frac{1 + 2/ ( 1 - α )}{T} .$

∎

Proof of Proposition 2.

We count integer-coordinate codes throughout, including at resolution zero.

For $M \in Z_{\geq 0}$ , define the integer simplex grid by $I_{M} := {(u_{1}, u_{2}, u_{3}, u_{4}) \in {0, \dots, M}^{4} : i = 1 \sum 4 u_{i} = M} .$ Taking coordinate values gives a bijection between $I_{M}$ and the nonnegative integer quadruples summing to $M$ : each coordinate of such a quadruple is at most its sum, hence at most $M$ . These quadruples are in turn in bijection with multisets of size $M$ on the four labels $1, \dots, 4$ , by assigning multiplicity $u_{i}$ to label $i$ . The multiset counting formula and binomial symmetry therefore give $∣ I_{M} ∣ = (M M + 3) = (3 M + 3) .$ This also covers $M = 0$ , where the unique quadruple is $(0, 0, 0, 0)$ .
Define the transition-row codes, reward codes, and unfiltered candidate codes by $J_{M} := I_{M}^{4}, E_{M} := {0, \dots, M}^{4}, U_{M} := I_{M} \times (J_{M} \times E_{M}) .$ A choice of four rows determines a unique transition array, and its rows recover the choice. Thus this correspondence is injective, and the product counting formula yields $∣ J_{M} ∣ = i = 1 \prod 4 ∣ I_{M} ∣ = ∣ I_{M} ∣^{4} .$

Each reward coordinate has $M + 1$ choices, so $∣ E_{M} ∣ = (M + 1)^{4} .$ The candidate enumeration is precisely the displayed Cartesian product: a triple determines, and is determined by, its initial-vector code, transition-row code, and reward code. Consequently, $∣ U_{M} ∣ = ∣ I_{M} ∣ ∣ J_{M} ∣ ∣ E_{M} ∣ = ∣ I_{M} ∣^{5} (M + 1)^{4} = (3 M + 3)^{5} (M + 1)^{4} .$ For $M \geq 1$ , coordinatewise division by $M$ gives the unfiltered grid triples.
For a transition-row code $R = (R_{ij}) \in J_{M}$ , define its decoded transition candidate by $R_{ij} := \frac{R _{ij}}{M}, 1 \leq i, j \leq 4,$ with division by zero interpreted as zero. The contraction coefficient used for filtering is $δ (R) := 1 \leq i, j \leq 4 max \frac{1}{2} ℓ = 1 \sum 4 ∣ R_{i ℓ} - R_{j ℓ} ∣.$ For every $M \in Z_{\geq 0}$ and every $α \in R$ , define the retained codes by $U_{M}^{α} := {(u, R, w) \in U_{M} : δ (R) \leq α + \frac{6}{M}},$ using the same division convention. For $M \geq 1$ , coordinatewise division by $M$ identifies the retained codes $U_{M}^{α}$ with the candidate set in Algorithm 1. This is a subset of $U_{M}$ , so $∣ U_{M}^{α} ∣ \leq ∣ U_{M} ∣ = (3 M + 3)^{5} (M + 1)^{4} .$ In particular, at $M = 0$ the decoded transition array is zero and the subset argument still applies.
The standard binomial bound $(3 M + 3) \leq (M + 3)^{3}$ together with $M + 1 \leq M + 3$ gives $∣ U_{M} ∣ = (3 M + 3)^{5} (M + 1)^{4} \leq ((M + 3)^{3})^{5} (M + 3)^{4} = (M + 3)^{19} .$
Now fix the mixing-scale parameter $t_{0} > 0$ and its associated contraction bound. Then $α = exp (- 1/ t_{0}) > 0.$ Define $c := (26 + 36/ α)^{19} > 0.$ For an integer trajectory length $T \geq 1$ , take $M := ⌈ (22 + 36/ α) T ⌉ .$ Since $(22 + 36/ α) T \geq 0$ , the ceiling bound gives $M < (22 + 36/ α) T + 1.$ Adding three and using $T \geq 1$ , we obtain $M + 3 < (22 + 36/ α) T + 4 \leq (26 + 36/ α) T,$ and hence $M + 3 \leq (26 + 36/ α) T .$

Both sides are nonnegative, so raising this inequality to the nineteenth power and applying the preceding cardinality bound yields $∣ U_{M} ∣ \leq (M + 3)^{19} \leq ((26 + 36/ α) T)^{19} = c T^{19} .$ Finally, the filtering inequality gives $∣ U_{M}^{α} ∣ \leq ∣ U_{M} ∣ \leq c T^{19} .$ The chosen constant depends on $t_{0}$ through $α$ and is valid for every integer $T \geq 1$ .

∎

References

Robins, James M. (1986). A New Approach to Causal Inference in Mortality Studies with a Sustained Exposure Period---Application to Control of the Healthy Worker Survivor Effect. Mathematical Modelling. doi
Murphy, Susan A. (2003). Optimal Dynamic Treatment Regimes. Journal of the Royal Statistical Society: Series B. doi
Puterman, Martin L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. doi
Kallus, Nathan and Uehara, Masatoshi (2022). Efficiently Breaking the Curse of Horizon in Off-Policy Evaluation with Double Reinforcement Learning. Operations Research. doi
Mehrabi, Mohammad and Wager, Stefan (2024). Off-Policy Evaluation in {Markov} Decision Processes under Weak Distributional Overlap. . arXiv
Nair, Yash and Jiang, Nan (2021). A Spectral Approach to Off-Policy Evaluation for {POMDPs}. . arXiv
Shi, Chengchun and Uehara, Masatoshi and Huang, Jiawei and Jiang, Nan (2022). A Minimax Learning Approach to Off-Policy Evaluation in Confounded Partially Observable {Markov} Decision Processes. Proceedings of the 39th International Conference on Machine Learning. arXiv
Ho, B. L. and Kalman, Rudolf E. (1966). Editorial: Effective Construction of Linear State-Variable Models from Input/Output Functions. Regelungstechnik. doi
Carlyle, Jack W. and Paz, Azaria (1971). Realizations by Stochastic Finite Automata. Journal of Computer and System Sciences. doi
Hsu, Daniel and Kakade, Sham M. and Zhang, Tong (2012). A Spectral Algorithm for Learning Hidden {Markov} Models. Journal of Computer and System Sciences. doi
Abraham, Kweku and Gassiat, Elisabeth and Naulet, Zacharie (2023). Fundamental Limits for Learning Hidden {Markov} Model Parameters. IEEE Transactions on Information Theory. doi
Tsybakov, Alexandre B. (2009). Introduction to Nonparametric Estimation. Springer. doi
Uehara, Masatoshi and Kiyohara, Haruka and Bennett, Andrew and Chernozhukov, Victor and Jiang, Nan and Kallus, Nathan and Shi, Chengchun and Sun, Wen (2023). Future-Dependent Value-Based Off-Policy Evaluation in {POMDPs}. Advances in Neural Information Processing Systems. arXiv
Zhang, Yuheng and Jiang, Nan (2024). On the Curses of Future and History in Future-dependent Value Functions for Off-policy Evaluation. Advances in Neural Information Processing Systems. arXiv
Hu, Yuchen and Wager, Stefan (2023). Off-Policy Evaluation in Partially Observed {Markov} Decision Processes under Sequential Ignorability. The Annals of Statistics. doi
{CausalSmith} (2026). Latent Stationary Overlap and Minimax Off-Policy Evaluation in Finite {POMDPs}. .

Formal layer — Lean correspondence

Every object below is formalized in Lean 4. Click a verified row to view its statement; the rest link to the Lean source.

Setups (3)

Setup S-1 — A single stationary trajectory of length $T$ from a time-homogeneous partially observed Markov decision process with binary observed state $X_t\in\mathcal X=\{0,1\}$ , binary hidden state $H_t\in\mathcal H=\{0,1\}$ , joint state $S_t=(X_t,H_t)\in\mathcal S$ , binary action $A_t\in\mathcal A=\{0,1\}$ , and reward $Y_t\in\mathcal Y=[0,1]$ . A joint reward--next-state kernel $K(dy,s'\mid s,a)$ generates $(Y_t,S_{t+1})$ given the full pre-action history $\mathcal F_t^-$ and $A_t$ ; the known memoryless behavior policy $b$ draws $A_t$ given $X_t$ , and $e$ is the known memoryless target policy. Each policy $p\in\{b,e\}$ induces a joint-state transition matrix $P_p$ with stationary law $d_p$ ; $r_e$ is the target-policy mean reward and $\theta=d_er_e$ . Only $\mathsf O_T=((X_t,A_t,Y_t))_{t=1}^T$ is observed. Regime constants are $t_0>0$ , $\zeta\geq0$ , $\alpha=e^{-1/t_0}$ , $L=e^{\zeta}$ ; observable scores are $\rho_t$ , $Z_t(k)$ , with population moments $m_k$ and empirical moments $\widehat m_k$ , and $\mathcal M_T^{(2)}(t_0,\zeta)$ is the class of such experiments satisfying the six law conditions.
Setup S-2 — Auxiliary finite linear algebra on the four-point joint-state space: row-stochastic $4\times4$ matrices $P,P'$ with initial laws $\nu,\nu'$ , reward vectors $r,r'\in[0,1]^4$ , stationary laws $\pi,\pi'$ , transient characteristic polynomials $q_P(z)=\det(zI-P)/(z-1)$ , $q_{P'}$ , pair polynomial $Q_{P,P'}=q_Pq_{P'}=\sum_{k=0}^6Q_kz^k$ , Dobrushin coefficient $\delta(R)=\max_{i,j}\|R(i,\cdot)-R(j,\cdot)\|_{\mathrm{TV}}$ , and stability constant $B_\alpha=((1+\alpha)/(1-\alpha))^6$ .
Setup S-4 — The cardinality-uniform bounded-stationary-overlap comparator: stationary-overlap bound $C>1$ , radius $q_C=(C-1)/C$ , exponent $\beta=2/(2+t_0\zeta)$ , and reset-chain depth $Q$ with hidden alphabet of size $2(Q+1)$ .

Definitions (8)

Definition P-1 verified CausalSmith.Stat.PomdpBinaryhiddenRate.BinaryPomdpClass $\mathcal M_T^{(2)}(t_0,\zeta):=\{(K,b,e,\mathcal L(\mathsf O_T)):T\in\mathbb N,\ \mathcal X=\mathcal H=\mathcal A=\{0,1\},\ \mathcal Y=[0,1],\ \mathrm A_{\mathrm{kernel}},\mathrm A_{\mathrm{ign}},\mathrm A_{\mathrm{start}},\mathrm A_{\mathrm{overlap}},\mathrm A_{b\text{-}\mathrm{mix}},\mathrm A_{e\text{-}\mathrm{mix}}\text{ hold}\}$ , where the six predicates are exactly $\mathrm{ass{:}pomdp\text{-}kernel}$ , $\mathrm{ass{:}sequential\text{-}ignorability}$ , $\mathrm{ass{:}stationary\text{-}start}$ , $\mathrm{ass{:}policy\text{-}overlap}$ , $\mathrm{ass{:}behavior\text{-}contraction}$ , and $\mathrm{ass{:}target\text{-}contraction}$ .
Definition P-2 verified CausalSmith.Stat.PomdpBinaryhiddenRate.targetValue $\theta(K,e):=d_er_e=\sum_{s=(x,h)\in\mathcal S}d_e(s)\sum_{a\in\mathcal A}e(a\mid x)\sum_{s'\in\mathcal S}\int_{\mathcal Y}yK(dy,s'\mid s,a)$ .
Definition P-3 verified CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment For $k=0,\ldots,6$ , set $Z_t(k):=Y_t\prod_{j=t-k}^{t}\rho_j$ , $m_k:=\mathbb E_b[Z_t(k)]$ , and $\widehat m_k:=(T-6)^{-1}\sum_{t=7}^{T}Z_t(k)$ .
Definition P-4 verified CausalSmith.Stat.PomdpBinaryhiddenRate.stableGridEstimator Let $M:=\lceil(22+36/\alpha)T\rceil$ , let $\mathcal G_M$ be the four-simplex grid with coordinates in $M^{-1}\mathbb Z$ , let $U:=\mathbf1\mathbf1^{\mathsf T}/4$ , and let $\lambda:=\alpha/(\alpha+6/M)$ . Enumerate every $(\nu,R,r)$ with $\nu\in\mathcal G_M$ , every row of $R$ in $\mathcal G_M$ , $\delta(R)\le\alpha+6/M$ , and $r\in\{0,1/M,\ldots,1\}^4$ ; form $P=\lambda R+(1-\lambda)U$ , select lexicographically among minimizers of $\max_{0\le k\le6}|\widehat m_k-\nu P^kr|$ , and output $\widehat\theta_T:=\pi(P)r$ , where $\pi(P)P=\pi(P)$ .
Definition P-5 verified CausalSmith.Stat.PomdpBinaryhiddenRate.minimaxRisk $R_T^{(2)}(t_0,\zeta):=\inf_{\widetilde\theta\in\sigma(\mathsf O_T,b,e,t_0,\zeta)}\sup_{M\in\mathcal M_T^{(2)}(t_0,\zeta)}\mathbb E_M[(\widetilde\theta-\theta)^2]$ , where the infimum ranges over measurable observed-data procedures taking values in $[0,1]$ .
Definition P-6 verified CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment For $v\in\{-v_T,+v_T\}$ , put $b(1\mid x)=e(1\mid x)=1/2$ , let $E(x\mid h)=3/5$ if $x=h$ and $E(x\mid h)=2/5$ otherwise, set $q_v(h)=1/2+(2h-1)/8+v$ , and set $p(a)=1/4+a/2$ . Define $K_v^{(T)}(y,x',h'\mid x,h,a) :=\operatorname{Ber}_{q_v(h)}(y)\operatorname{Ber}_{p(a)}(h')E(x'\mid h').$
Definition P-7 verified CausalSmith.Stat.PomdpBinaryhiddenRate.polynomialTimeHandle The handle $\mathfrak H_{\mathrm{poly}}$ is the problem of constructing, in an explicit arithmetic or bit-complexity and precision model, a cost-certified algorithm that starts from the $3\times3$ Hankel matrix of differences $\widehat m_{i+j+1}-\widehat m_{i+j}$ , adapts over recurrence ranks zero through three, enforces transient roots in $\{z:|z|\leq\alpha\}$ , and returns a stable four-state scalar realization whose seven-moment objective is globally certified to within $T^{-1}$ of the optimum, uniformly over rank-deficient strata and without a positive singular-value margin. The exhaustive estimator is defined over a finite candidate list of size $O(T^{19})$ for fixed $t_0$ , but no runtime or arithmetic-operation bound for fitting and selection is asserted.
Definition P-8 verified CausalSmith.Stat.PomdpBinaryhiddenRate.polynomialTimeAttainmentQuestion Can the handle $\mathfrak H_{\mathrm{poly}}$ implement fitting and lexicographic selection over, or replace, the $O(T^{19})$ -sized stable-grid candidate list by a rank-adaptive algorithm with explicit runtime, bit-complexity, and precision semantics that returns over $\mathcal M_T^{(2)}(t_0,\zeta)$ a globally certified seven-moment stable fit within objective gap $T^{-1}$ , uniformly over every rank-deficient Hankel stratum and without a positive singular-value margin?

Assumptions (6)

Assumption A-1 verified CausalSmith.Stat.PomdpBinaryhiddenRate.PomdpKernelLaw $\mathcal L(Y_t,S_{t+1}\mid\mathcal F_t^-,A_t)=K(\cdot\mid S_t,A_t)$ for $t=1,\ldots,T$ .
Assumption A-2 verified CausalSmith.Stat.PomdpBinaryhiddenRate.SequentialIgnorability $\Pr(A_t=a\mid\mathcal F_t^-)=b(a\mid X_t)$ for $a\in\mathcal A$ and $t=1,\ldots,T$ .
Assumption A-3 verified CausalSmith.Stat.PomdpBinaryhiddenRate.StationaryStart $S_1\sim d_b$ .
Assumption A-4 verified CausalSmith.Stat.PomdpBinaryhiddenRate.PolicyOverlap $e(a\mid x)\le Lb(a\mid x)$ for every $(a,x)\in\mathcal A\times\mathcal X$ .
Assumption A-5 verified CausalSmith.Stat.PomdpBinaryhiddenRate.BehaviorContraction $\|\mu P_b-\mu'P_b\|_{\mathrm{TV}}\le\alpha\|\mu-\mu'\|_{\mathrm{TV}}$ for every $\mu,\mu'\in\Delta(\mathcal S)$ .
Assumption A-6 verified CausalSmith.Stat.PomdpBinaryhiddenRate.TargetContraction $\|\mu P_e-\mu'P_e\|_{\mathrm{TV}}\le\alpha\|\mu-\mu'\|_{\mathrm{TV}}$ for every $\mu,\mu'\in\Delta(\mathcal S)$ .

Lemmas (3)

Lemma L-1 verified CausalSmith.Stat.PomdpBinaryhiddenRate.pairPolynomial_value_modulus If $\delta(P)\le\alpha$ and $\delta(P')\le\alpha$ , then eigenvalue one is algebraically simple for both matrices and $Q_{P,P'}(1)(\pi r-\pi'r')=\sum_{k=0}^{6}Q_k(\nu P^kr-\nu'P'^kr')$ . Consequently, $|\pi r-\pi'r'|\le B_\alpha\max_{0\le k\le6}|\nu P^kr-\nu'P'^kr'|$ . The identity holds without diagonalizability and therefore includes repeated, defective, and complex transient modes.
Lemma L-2 verified CausalSmith.Stat.PomdpBinaryhiddenRate.observable_intervention_moments For every member of $\mathcal M_T^{(2)}(t_0,\zeta)$ and every $k=0,\ldots,6$ , the $k+1$ -action score with $k$ state transitions satisfies $m_k=\mathbb E_b[Z_t(k)]=d_bP_e^kr_e$ . Moreover, $\mathbb E_b[Z_t(k)^2]\leq L^{k+1}$ , and, for $h\geq k+1$ , $\lvert\operatorname{Cov}(Z_t(k),Z_{t+h}(k))\rvert\leq\alpha^{h-k-1}$ .
Lemma L-3 verified CausalSmith.Stat.PomdpBinaryhiddenRate.testingFamily_membership For both $v\in\{-v_T,+v_T\}$ , the kernel $K_v^{(T)}$ and the displayed coincident policies define members of $\mathcal M_T^{(2)}(t_0,\zeta)$ for every $t_0>0$ , $\zeta\geq0$ , and $T\geq12$ . Their target values differ by $1/(8\sqrt T)$ , and their observed trajectory laws satisfy $\operatorname{KL}(\mathbb P_{+}^{\mathsf O_T}\Vert\mathbb P_{-}^{\mathsf O_T})\leq1/12$ . Moreover, $e=b$ and $d_e=d_b$ , so this pair obeys every stationary occupancy-ratio bound $d_e\leq Cd_b$ with $C>1$ .

Theorems (4)

Theorem T-1 verified CausalSmith.Stat.PomdpBinaryhiddenRate.stableGrid_upper For every fixed $t_0>0$ , $\zeta\geq0$ , and $T\geq12$ , the fully observed-data estimator $\widehat\theta_T$ satisfies $\sup_{M\in\mathcal M_T^{(2)}(t_0,\zeta)} \mathbb E_M[(\widehat\theta_T-\theta)^2] \leq \frac{B_\alpha^2(112V_{\alpha,L}+2)}{T}.$ This bound is uniform over zero behavior cells, singular emissions, arbitrarily small stationary cells, and every dependence between reward and next state allowed by $K$ ; it requires no stationary occupancy-ratio bound.
Theorem T-2 verified CausalSmith.Stat.PomdpBinaryhiddenRate.fixedBinary_minimax For every fixed $t_0>0$ , $\zeta\geq0$ , and $T\geq12$ , $\frac1{1024T} \leq R_T^{(2)}(t_0,\zeta) \leq\frac{B_\alpha^2(112V_{\alpha,L}+2)}T.$ Thus the exact fixed-binary mean-squared-error rate is $T^{-1}$ , without a stationary occupancy-ratio assumption and hence without a $C$ -elbow. The positive hard pair has $e=b$ and $d_e=d_b$ , so the converse transfers to every larger Hu--Wager or cardinality-uniform stationary-overlap class containing this binary subclass. For $\zeta>0$ and $C>1$ , by contrast, the cited cardinality-uniform rate is $T^{-1}+T^{-\beta}q_C^{2(1-\beta)}$ , with $\beta=2/(2+t_0\zeta)$ , and its lower construction has $2(Q+1)$ hidden states with $Q\asymp\log T$ , so that construction is not representable in the binary-hidden class for large $T$ .
Theorem T-3 verified CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_reduction Under the stationary-start, POMDP-kernel, sequential-assignment, and behavior-contraction assumptions, if $e=b$ , then $P_e=P_b$ , $d_e=d_b$ , and $m_0=\theta$ . Moreover, the sample mean is unbiased and satisfies $\mathbb E\!\left[\left\{T^{-1}\sum_{t=1}^{T}Y_t-\theta\right\}^2\right] \leq \frac{1+2/(1-\alpha)}{T}.$ Consequently its mean-squared error is $O(T^{-1})$ . This is the standard on-policy reduction of the fixed-binary frontier; no law-by-law $\Omega(T^{-1})$ assertion is made.
Theorem T-4 verified CausalSmith.Stat.PomdpBinaryhiddenRate.exhaustiveGrid_candidate_count Let $M:=\lceil(22+36/\alpha)T\rceil$ as in $\mathrm{def{:}stable\text{-}grid\text{-}estimator}$ . Before the Dobrushin filter is applied, its finite candidate list has exactly $\binom{M+3}{3}^{5}(M+1)^4$ elements, and filtering can only reduce this number. Hence, for fixed $t_0>0$ , the candidate-list cardinality is $O(M^{19})=O(T^{19})$ .

Citeds (1)

Cited result lem:cardinality-uniform-comparator verified CausalSmith.Stat.PomdpBinaryhiddenRate.CardinalityUniformComparator For fixed $t_0>0$ and $\zeta>0$ , the cardinality-uniform stationary-overlap POMDP result cited as CausalSmithLatentOverlap2026 has minimax mean-squared-error rate $T^{-1}+T^{-\beta}q_C^{2(1-\beta)}$ , where $\beta=2/(2+t_0\zeta)$ and $q_C=(C-1)/C$ . Its lower-bound reset construction has $2(Q+1)$ hidden states with $Q\asymp\log T$ .

Auxiliary Lean lemmas (machine-checked) (209)

Definition ComparatorHiddenAlphabet —
Definition IsGridRow —
Definition IsStationary —
Definition mixingAlpha —
Definition ModelIndex —
Definition obsLaw —
Definition overlapRadius —
Definition policyFactor —
Definition policyKernel —
Definition PolicyVector —
Definition rateExponent —
Definition RawPomdpExperiment —
Definition stabilityFactor —
Definition stationaryLaw —
Definition varianceFactor —
Definition vT —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.simplexGrid_card —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridMatrixRows_card —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridCandidateUniverse_card —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridCandidateUniverse_growth —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridSize_linear_bound —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_kernel_stationary —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.fourMatrixPower —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.fourMatrixPower_zero —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.observable_intervention_moment_zero —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingRewardProb_mem_Icc —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_policyOverlap —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingStepMass_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingInitialMass_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingRewardMass_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingOneStepMass_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingStateMass_sum —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingNextStateMass —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingNextStateMass_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingStepMarginal_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPathWeight_nonneg —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPathWeight_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_occupancy_bound —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_policyKernel_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_stationaryLaw_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_contraction —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKernel_reward_integral —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_rewardRegression_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_targetValue_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKernel_probability —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKernel_rewardSupport —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_stationary —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.comparator_reset_depth_growth —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPathWeight_initial_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_historyConditions —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_class_of_history —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.sqRisk_ge_error_probability —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.bounded_estimator_sqError_integrable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPair_observedRisk_lower —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.targetValue_mem_unitInterval —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.policyKernel_stochastic_of_kernelLaw —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.targetStationary_of_class —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.observedRisk_unit_bounds —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.sequentialIgnorability_supported_action —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pomdp_reward_mem_Icc_ae —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pomdp_reward_integrable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_score_zero_ae —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_reward_mean —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_sampleMean_unbiased —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_binaryClass —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_reward_covariance —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.finiteGeometric_sum_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.finiteGeometric_sum_image_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.geometricCovariance_row_sum_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.coincidentPolicy_sampleMean_mse —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPathWeight_pos —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingTrajectoryLaw_absolutelyContinuous —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingObservedLaw_klDiv_ne_top —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridCandidates_row —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridCandidates_nonempty —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selectGridCode_mem —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridR_stochastic —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stabilizedGridMatrix_stationary —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stableGridEstimator_range —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.score_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridObjective_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.grid_min_choose_congr —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selectGridCode_order_congr —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selectGridCode_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stableGridEstimator_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stableGridEstimator_admissible —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testing_product_entropy_le —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingKLStep —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKLStep_pos —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKLStep_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingKLStep_entropy_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingPath_entropy_le —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathLaw —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathLaw_mass —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathLaw_probability —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathLaw_ac —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathLaw_map —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingObservedLaw_klDiv_le —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteWeight —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteWeight_nonneg —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteWeight_sum —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteKernel —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteKernel_apply —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteInit —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteInit_apply —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFairPMF —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFairPMF_apply —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteModel —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathEquiv —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFinitePathWeight_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteModel_law_apply —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteModel_kernel_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteModel_law_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingFiniteModel_policy_eq —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_kernelHistory —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.testingExperiment_actionHistory —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.grid_candidate_moment_approximation —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.matrix_moment_relabel —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.contractsL1_relabel —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.grid_approximation —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.probability_mean_unit —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.probability_mean_tv —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.probability_mean_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_power_reward_unit —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_power_reward_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_moment_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.reward_grid_rounding —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.simplex_grid_rounding —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.contractsL1_gridDobrushin —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.row_tv_triangle —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridDobrushin_perturbation —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stabilizedGridMatrix_row_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.rewardRegression_unit —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.finitePomdpView —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.finitePomdpView_laws —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.score_eq_phiwScore —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.score_abs_first_moment_le_one —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.score_second_moment_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.scoreCovariance_le_separated —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.integral_binary_curState_eq_stationary —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_markovOperatorIter_eq_mulVec —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_obsProj_measurable —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_obsLaw_isProbability —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_score_memLp_two —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.integral_observable_score_eq_matrixMoment —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_unbiased —
Definition CausalSmith.Stat.PomdpBinaryhiddenRate.gridCodeMoment —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selectGridCode_objective_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selected_grid_moment_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.selected_grid_intervention_moment_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.observable_score_variance_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.observable_score_covariance_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.observable_score_covariance_le_separated —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_memLp_two —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_mse_eq_covariance_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.seven_error_max_sq_le_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_max_mse_le_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_sum_pow_image_le_range —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_geom_partial_le_inv —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_sum_abs_symmetric_eq_diag_add_two_upper —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.binary_sum_abs_covariance_future_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_mse_le_varianceFactor —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.empiricalMoment_max_mse_le_varianceFactor —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.gridNu_probability —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stabilizedGridMatrix_dobrushin_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.grid_value_modulus —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stableGridEstimator_value_error —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stationary_vecMul_pow —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stationary_vecMul_aeval —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_charpoly_isRoot_one —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_charpoly_factor —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_aeval_annihilated —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.matrixMoment_polynomial_sum —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.probability_mean_tv_interval —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_fixedVector_constant —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_aeval_projection —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPoly_natDegree_lt_seven —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_mul_aeval_projection —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.polynomial_projection_value —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPolynomial_value_identity —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stationary_shift_constant_eq_zero —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_shift_sq_kernel —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_shift_pow_kernel —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_maxGenEigenspace_one —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_charpoly_rootMultiplicity_one —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_eval_one_ne_zero —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPoly_eval_one_ne_zero —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPolynomial_value_coefficient_modulus —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_monic —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_natDegree_three —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPoly_monic —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPoly_natDegree_six —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.degreeSix_coeff_sum_le_of_roots_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.roots_distance_prod_lower —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.degreeSix_eval_one_lower_of_roots_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.degreeSix_coefficient_ratio_le_of_roots_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.probability_complex_mean_tv_diameter —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.row_tv_le_dobrushin —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_complex_diameter_contraction —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_complex_constant —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.stochastic_complex_eigenvector_nonconstant —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_complex_eigenvector_norm_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.dobrushin_complex_charpoly_root_norm_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.transientPoly_complex_root_norm_le —
Lemma CausalSmith.Stat.PomdpBinaryhiddenRate.pairPoly_complex_roots_norm_le —
Definition ComparatorResetLowerWitness —
Definition ObservableEstimator —
Definition observedRisk —

Symbol realizations (Lean @realizes) (52)

$\mathcal A$ verified realized by Policy
$\mathcal X$ verified realized by BinaryObservedState, BinaryJointState, BinaryPolicy, BinaryPomdpExperiment, BinaryPomdpClass
$\mathcal H$ verified realized by BinaryHiddenState, BinaryJointState, BinaryPomdpExperiment, BinaryPomdpClass
$\mathcal S$ verified realized by BinaryJointState
T verified realized by FullTrajectory, variable@85
S_t verified realized by FullTrajectory, curState, StationaryStart
A_t verified realized by FullTrajectory, actionAt
Y_t verified realized by FullTrajectory, rewardAt, PomdpKernelLaw
$\mathsf O_T$ verified realized by ObsView, obsLaw
K verified realized by RawPomdpExperiment, PomdpKernelLaw, BinaryPomdpClass
b verified realized by RawPomdpExperiment, SequentialIgnorability, BinaryPomdpClass
e verified realized by RawPomdpExperiment, PolicyOverlap, BinaryPomdpClass
t_0 verified realized by variable@85, BinaryPomdpClass
$\zeta$ verified realized by variable@85, BinaryPomdpClass
X_t verified realized by curState, BinaryPomdpClass
H_t verified realized by curState, BinaryPomdpClass
P_p verified realized by policyKernel, BehaviorContraction, TargetContraction, BinaryPomdpClass
d_p verified realized by stationaryLaw, StationaryStart, BinaryPomdpClass
r_e verified realized by rewardRegression, targetValue
$\alpha$ verified realized by mixingAlpha, BehaviorContraction, TargetContraction
L verified realized by policyFactor, PolicyOverlap
$\mathcal Y$ verified realized by PomdpKernelLaw
$\mathcal F_t^-$ verified realized by PomdpKernelLaw, SequentialIgnorability
$\mathcal M_T^{(2)}(t_0,\zeta)$ verified realized by BinaryPomdpClass, ModelIndex
$\theta$ verified realized by targetValue
$\rho_t$ verified realized by ratio
Z_t(k) verified realized by score
m_k verified realized by populationMoment
$\widehat m_k$ verified realized by empiricalMoment
q_P verified realized by transientPoly
q_{P'} verified realized by transientPoly
Q_{P,P'} verified realized by pairPoly
$B_\alpha$ verified realized by stabilityFactor
$V_{\alpha,L}$ verified realized by varianceFactor
P verified realized by variable@362, pairPolynomial_value_modulus
P' verified realized by variable@362, pairPolynomial_value_modulus
$\nu$ verified realized by variable@362, pairPolynomial_value_modulus
$\nu'$ verified realized by variable@362, pairPolynomial_value_modulus
r verified realized by variable@362, pairPolynomial_value_modulus
r' verified realized by variable@362, pairPolynomial_value_modulus
$\pi$ verified realized by variable@362, pairPolynomial_value_modulus
$\pi'$ verified realized by variable@362, pairPolynomial_value_modulus
q_C verified realized by overlapRadius
$\beta$ verified realized by rateExponent
C verified realized by variable@377, CardinalityUniformComparator, fixedBinary_minimax
Q verified realized by variable@377, ComparatorHiddenAlphabet, CardinalityUniformComparator, fixedBinary_minimax
$\mathfrak H_{\mathrm{poly}}$ verified realized by polynomialTimeHandle
M verified realized by gridSize
$\widehat\theta_T$ verified realized by stableGridEstimator
$R_T^{(2)}(t_0,\zeta)$ verified realized by minimaxRisk
v_T verified realized by vT_mem_Ioc
K_v^{(T)} verified realized by testingKernel, testingExperiment

Proof map 7 statements · 5 edges

Parametric Rates for Stationary Policy Evaluation with Binary Hidden States

Abstract

Introduction

Related work

Setup and assumptions

Main results

Binary risk characterization.

Discussion

Limitations and future work

Appendices

Proofs and verification scope

Four-state realizations and the value modulus

Intervention moments and trajectory dependence

Grid approximation and stable fitting

The positive testing family

Minimax assembly and the remaining results

Verification scope.

Proofs of the main results

References