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 value-iteration model attains the Bellman error bound

Example

Let $S = {s}$ , $A (s) = {a}$ , $γ = 1 / 2$ , with a deterministic self-loop reward $1$ , and initialize $V_{0} (s) = 0$ . Then $V^{*} (s) = 2$ and $V_{m} (s) = 2 (1 - 2^{- m})$ , so

$∥ V_{m} - V^{*} ∥_{\infty} = 2^{1 - m} = γ^{m} ∥ V_{0} - V^{*} ∥_{\infty}$

for every $m \geq 0$ ; the general value-iteration error bound is attained at every iteration.

Example references

The one-state deterministic MDP data.

The one-state Bellman backup.

The finite-iterate value-iteration procedure.

The general contraction error estimate.

Sutton and Barto, Reinforcement Learning: An Introduction.

Facts & Assumptions

Given: The one-state MDP, $γ = 1 / 2$ , and $V_{0} (s) = 0$ in the example.

[F1]

Finite Markov decision process with joint reward-transition law: the sole state transitions to itself with reward $1$ .

[F2]

Bellman optimality operator and Exact value iteration for the Bellman optimality operator: the optimality backup is applied exactly at every iteration.

[F3]

Finite-MDP Bellman operators are gamma contractions with unique fixed points: the Bellman optimality operator has a unique fixed point.

[L1]

Integer powers $a^{m}$ : for $n \geq 1$ , $a^{- n} = (a^{n})^{- 1}$ when $a \neq 0$ ; in particular $2^{- 1} = 1 / 2$ .

[F4]

Laws of integer exponents: for nonzero $a$ , $a^{m + n} = a^{m} a^{n}$ for all integers $m, n$ . Setting $a = 2$ , $m = - (m + 1)$ , and $n = 1$ gives $2^{- m} = 2^{- (m + 1)} 2$ ; since $2^{- 1} = 1 / 2$ , this yields $2^{- (m + 1)} = \frac{1}{2} 2^{- m}$ .

[F5]

The principle of mathematical induction: if a property holds at $0$ and is preserved by each successor, then it holds for every natural number.

[F6]

Value iteration converges at the Bellman contraction rate: the exact value-iteration error is at most $γ^{m} ∥ V_{0} - V^{*} ∥_{\infty}$ for every $m \geq 0$ .

Verification

1.1givenF1F2F3algebra

The one-state optimality map is $(T^{*} v) (s) = 1 + \frac{1}{2} v (s)$ by [F1] and [F2]. Its fixed-point equation gives $v (s) = 2$ , and [F3] identifies this as $V^{*}$ .

1.2givenL1base

At $m = 0$ , $V_{0} (s) = 0 = 2 (1 - 2^{- 0})$ . Thus the claimed iterate formula holds at the base index.

2.1step 1.2F1F2F4L1ihalgebra

Fix $m \in N$ and assume $V_{m} (s) = 2 (1 - 2^{- m})$ . The exact backup in [F2] gives $V_{m + 1} (s) = 1 + \frac{1}{2} V_{m} (s) = 1 + (1 - 2^{- m}) = 2 - 2^{- m} = 2 (1 - 2^{- (m + 1)})$ by [L1].

3.1step 1.1step 1.2step 2.1F5F6inductiondischarge-induction: step 2.1algebra∎

By [F5], the base case in step 1.2 and successor step 2.1 establish $V_{m} (s) = 2 (1 - 2^{- m})$ for every $m \geq 0$ . Using $V^{*} (s) = 2$ from step 1.1 gives $∥ V_{m} - V^{*} ∥_{\infty} = 2^{1 - m}$ ; also $γ^{m} ∥ V_{0} - V^{*} ∥_{\infty} = 2^{- m} \cdot 2 = 2^{1 - m}$ . This equals the general error bound in [F6], so it is attained at every iteration.

Remarks

The diagram shows the one-state model used by the value-iteration calculation. The circle is the state, the rectangle is its sole action, and the labeled return arrow is the deterministic transition with reward $1$ . The discount and initial value are specified in the example statement; the verification does not rely on the diagram.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

36 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)