ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge 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 one-state on-policy linear TD(0) update contracts to zero

Example

Let the state set be ${s}$ with one available action, deterministic transition $s \to s$ , reward $0$ , and discount $0 \leq γ < 1$ . The unique behavior and target policies coincide, the state weighting is $μ (s) = 1$ , the feature is $ϕ (s) = 1$ , and the value estimate is $v_{w} (s) = w$ . For a fixed step size $0 < α \leq 1$ , apply the one-step TD(0) update $w_{n + 1} = w_{n} + α (0 + γ v_{w_{n}} (s) - v_{w_{n}} (s))$ from any $w_{0} \in R$ . Then $w_{n} \to 0$ .

Example references

The finite one-step transition/reward model and stationary policy.

The linear feature-value convention.

A geometric sequence with ratio of absolute value less than one tends to zero.

Tsitsiklis and Van Roy, “An Analysis of Temporal-Difference Learning with Function Approximation,” §IV.

Facts & Assumptions

Given: The one-state model, $0 \leq γ < 1$ , $0 < α \leq 1$ , and an arbitrary initial weight $w_{0}$ .

[F1]

Finite Markov decision process with joint reward-transition law: the unique action and deterministic self-transition define a finite MDP with reward zero.

[F2]

State-weighted Bellman error and projected Bellman error: for the feature $ϕ (s) = 1$ , the linear value estimate is $v_{w} (s) = w$ .

[F3]

For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ : if $∣ q ∣ < 1$ , then $q^{n} \to 0$ .

Verification

1.1givenF1F2algebra

The behavior and target policies are the same unique action, so the importance ratio is $1$ . The next state is always $s$ , hence the TD error at weight $w_{n}$ is $0 + γ w_{n} - w_{n} = - (1 - γ) w_{n}$ . Substitution in the update gives $w_{n + 1} = q w_{n}$ , where $q = 1 - α (1 - γ)$ .

2.1givenF3step 1.1inductionalgebra∎

Because $0 < α \leq 1$ and $0 \leq γ < 1$ , one has $γ \leq q < 1$ , so $∣ q ∣ < 1$ . Induction gives $w_{n} = q^{n} w_{0}$ for every $n$ , and [F3] implies $w_{n} \to 0$ .

Diagram

The circle is the sole state and the loop is its deterministic transition under the unique action; its reward is zero. The diagram only displays the model stated above and is not used in the calculation.

diagram failed to render:
\begin{tikzpicture}[>=stealth, every node/.style={font=\small}]
  \node[circle,draw] (s) at (0,0) {$s$};
  \draw[->] (s) to[loop above] node[above] {$a,\ r=0$} (s);
\end{tikzpicture}

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

34 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.

Sources

John N. Tsitsiklis and Benjamin Van Roy, An Analysis of Temporal-Difference Learning with Function Approximation (standard reference, not scraped)