ExampleConstruction: Literature-sourcedVerification: 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 finite Baird-star update has exact expected weights

Example

Use the seven-state MDP with zero rewards, discount $γ = 0.99$ , dashed transitions uniform over the six upper states, solid transitions to the seventh state, behavior probabilities $6 / 7$ dashed and $1 / 7$ solid, target policy always solid, feature values $2 w_{i} + w_{8}$ at upper state $s_{i}$ and $w_{7} + 2 w_{8}$ at $s_{7}$ , and initial vector $w_{0} = (1, 1, 1, 1, 1, 1, 10, 1)$ . Under the uniform-state expected semi-gradient TD(0) update, with step size $α = 1 / 100$ , the first reduced weight vector $(a, b, c)$ , where $a = w_{1} = \dots = w_{6}$ , $b = w_{7}$ , and $c = w_{8}$ , is $(4486 / 4375, 174997 / 17500, 9413 / 8750)$ ; in particular, the first six weights and $w_{8}$ increase on this update.

Example references

For every positive step size, both stated expected update sequences diverge from the specified initial vector.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed., §11.2.

Facts & Assumptions

Given: The Baird seven-state model, feature values, policies, uniform state weighting, initial vector, and $α = 1 / 100$ in the Example.

[F1]

Expected off-policy TD(0) diverges in Baird’s seven-state example: for the specified behavior transitions, the expected semi-gradient TD(0) update is ${\overset{ˉ}{w}}^{+} = w + α E_{μ, b} [ρ δ ϕ (S)]$ , where $ρ = π (A ∣ S) / b (A ∣ S)$ and $δ = γ v_{w} (S^{'}) - v_{w} (S)$ .

Verification

1.1givenF1algebra

At $w_{0}$ , every upper-state value is $2 (1) + 1 = 3$ and the seventh-state value is $10 + 2 (1) = 12$ . Thus $q_{u} = 0.99 (12) - 3 = 222 / 25$ and $q_{7} = 0.99 (12) - 12 = - 3 / 25$ . The importance ratio is $7$ on solid and $0$ on dashed; because behavior selects solid with probability $1 / 7$ , at each fixed state the behavior-action expectation is its solid-action TD error. Uniformly averaging the seven state contributions gives increments per unit step size $2 q_{u} / 7$ , $q_{7} / 7$ , and $(6 q_{u} + 2 q_{7}) / 7$ : each upper feature contributes $2 q_{u}$ to its own coordinate and $q_{u}$ to the common eighth coordinate, while the seventh feature contributes $q_{7}$ and $2 q_{7}$ to its last two coordinates. By [F1] these values are $444 / 175$ , $- 3 / 175$ , and $1326 / 175$ .

2.1givenstep 1.1algebra∎

Multiplying these increments by $α = 1 / 100$ gives $a_{1} = 1 + 444 / 17500 = 4486 / 4375$ , $b_{1} = 10 - 3 / 17500 = 174997 / 17500$ , and $c_{1} = 1 + 1326 / 17500 = 9413 / 8750$ , exactly as claimed; the displayed fractions give $a_{1} > 1$ and $c_{1} > 1$ .

Depends on

Expected off-policy TD(0) diverges in Baird’s seven-state example

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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