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 unit reward on a self-loop has no finite undiscounted return

Example

Take the finite MDP with $S = {s}$ , $A (s) = {a}$ , reward alphabet $R = {1}$ , and $p (s, 1 ∣ s, a) = 1$ . At $γ = 1$ , the first $N$ terms of the return sum to $N$ , so the undiscounted return diverges. The formal backup $F : R \to R$ , $F (v) = 1 + v$ , has no real fixed point and is not a contraction with any constant $0 \leq q < 1$ in the usual metric $d_{R} (v, w) = ∣ v - w ∣$ .

Example references

The finite MDP data and joint reward-transition convention.

Sutton and Barto, Reinforcement Learning: An Introduction.

Facts & Assumptions

Given: $S = {s}$ , $A (s) = {a}$ , $p (s, 1 ∣ s, a) = 1$ , and the undiscounted parameter $γ = 1$ .

[F1]

Finite Markov decision process with joint reward-transition law: the sole transition keeps the state at $s$ and gives reward $1$ with probability $1$ .

[F2]

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: the series $\sum_{j \geq 0} r^{j}$ diverges when $∣ r ∣ \geq 1$ .

[F3]

The absolute value makes $R$ a metric space: $d (x, y) = ∣ x - y ∣$ is a metric, its open balls are the intervals $(x - r, x + r)$ , and it is unbounded: $d_{R} (v, w) = ∣ v - w ∣$ is the usual metric on $R$ .

[F4]

Lipschitz map, $α$ -Hölder map for rational $0 < α \leq 1$ , and contraction: a contraction with constant $q$ must satisfy $d (F (v), F (w)) \leq q d (v, w)$ for some $0 \leq q < 1$ .

Verification

1.1givenF1algebra

Every reward is $1$ , so the first $N$ summands are $1$ and their partial sum is $N$ . Since these partial sums are unbounded, the undiscounted return does not have a finite real sum.

1.2givenalgebra

The formal backup equation $F (v) = v$ would give $1 + v = v$ , hence $1 = 0$ , which is impossible in $R$ .

2.1givenF2F3F4algebra∎

For any distinct $v, w$ , $d_{R} (F (v), F (w)) = ∣ v - w ∣ = d_{R} (v, w)$ by [F3]. This contradicts the strict contraction bound required by [F4] for any $0 \leq q < 1$ . Also, [F2] with $r = 1$ confirms divergence of the corresponding geometric series.

Remarks

The diagram uses a circle for the state and a rectangle for the action. The arrow from the state to the action indicates the sole policy choice; the return arrow is the transition with joint mass $p (s, 1 ∣ s, a) = 1$ . The value of $γ$ is specified in the example statement and is not encoded by the graph. The verification does not rely on the diagram.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[circle,draw] (s) at (0,0) {$s$};
  \node[rectangle,draw] (a) at (2,0) {$a$};
  \draw[->] (s) -- node[above] {choose $a$} (a);
  \draw[->] (a) to[bend left=35] node[below] {$p(s,1\mid s,a)=1$} (s);
\end{tikzpicture}

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

42 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

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, 2nd ed. (standard reference, not scraped)