ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedprecheck pendingjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A small transition error accumulates over longer rollouts

Example

Let the states be $u$ (safe) and $v$ (failure), each with one action. Both true and learned rewards are $1$ at $u$ and $0$ at $v$ . The true model stays at $u$ with probability $1$ , while the learned model moves from $u$ to $v$ with probability $ϵ$ and stays at $u$ with probability $1 - ϵ$ , where $0 < ϵ < 1$ ; both models keep $v$ absorbing. Starting at $u$ and following the only policy for horizon $H$ , the true return is $H$ and the learned return is $\sum_{t = 0}^{H - 1} (1 - ϵ)^{t}$ .

The diagram compares the true transition model on the left with the learned transition model on the right. Nodes are states, and arrows carry transition probabilities; each state label gives its reward. The dashed arrow is present only in the learned model.

\begin{center} \begin{tikzpicture}[>=stealth, node distance=25mm] \node[circle,draw] (u1) { $u, r = 1$ }; \node[circle,draw,right of=u1] (v1) { $v, r = 0$ }; \draw[->] (u1) to[loop above] node[above] { $1$ } (u1); \draw[->] (v1) to[loop right] node[right] { $1$ } (v1); \node at (1.25,-0.8) {true}; \begin{scope}[xshift=7cm] \node[circle,draw] (u2) at (0,0) { $u, r = 1$ }; \node[circle,draw] (v2) at (2.8,0) { $v, r = 0$ }; \draw[->] (u2) to[loop above] node[above] { $1 - ϵ$ } (u2); \draw[->,dashed] (u2) to[bend left=12] node[above] { $ϵ$ } (v2); \draw[->] (v2) to[loop right] node[right] { $1$ } (v2); \node at (1.4,-0.8) {learned}; \end{scope} \end{tikzpicture} \end{center}

Example references

The learned transition error is total variation on each state-action pair.

The fixed-policy return discrepancy is controlled by horizon and reachable transition error.

Facts & Assumptions

Given: The two-state models, initial state, policy, error parameter, and horizon in the Example.

[F1]

Finite learned transition and reward models: each model has probability transition rows and rewards in $[0, 1]$ ; transition error is total variation.

[F2]

Finite-horizon simulation bound for one fixed policy: a fixed policy with zero reward error and transition error at most $ϵ$ on its reachable pairs has return discrepancy at most $(\binom{H}{2}) ϵ$ from a common initial state.

Verification

Given: The finite model pair and policy in the Example.

1.1givenF1algebra

Under the true model, the state remains $u$ , so each of the $H$ rewards is $1$ and $J_{H} = H$ . Under the learned model, the probability of occupying $u$ at time $t$ is $(1 - ϵ)^{t}$ , by induction from the transition row, and the only positive reward is received at $u$ . Hence ${\hat{J}}_{H} = \sum_{t = 0}^{H - 1} (1 - ϵ)^{t}$ .

2.1givenF1F2step 1.1algebra∎

The reward error is zero. At $u$ , the total variation between the true row $(1, 0)$ and learned row $(1 - ϵ, ϵ)$ is $\frac{1}{2} (ϵ + ϵ) = ϵ$ ; at $v$ the rows agree. Every reachable pair therefore satisfies the hypotheses of [F2], and $H - {\hat{J}}_{H} \leq (\binom{H}{2}) ϵ$ . The exact difference from step 1.1 is $\sum_{t = 0}^{H - 1} [1 - (1 - ϵ)^{t}]$ , which is nondecreasing in $H$ and is positive for $H \geq 2$ . Thus even a fixed, small one-step transition error can produce a larger return discrepancy on longer rollouts, within the finite-horizon bound.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

12 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.