TheoremStatement: Literature-sourcedProof: 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.

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

Statement

Let the states be $S = {s_{1}, \dots, s_{7}}$ and the two actions available at each state be $d a s h e d$ and $s o l i d$ . All rewards are zero and $γ = 0.99$ . Under $d a s h e d$ , the next state is each of $s_{1}, \dots, s_{6}$ with probability $1 / 6$ ; under $s o l i d$ , the next state is $s_{7}$ with probability $1$ . The behavior policy has $b (d a s h e d ∣ s) = 6 / 7$ and $b (s o l i d ∣ s) = 1 / 7$ at every state, and the target policy selects $s o l i d$ with probability $1$ . Use the uniform state weighting $μ (s) = 1 / 7$ . For standard basis vectors $e_{1}, \dots, e_{8}$ of $R^{8}$ , set $ϕ (s_{i}) = 2 e_{i} + e_{8}$ for $1 \leq i \leq 6$ and $ϕ (s_{7}) = e_{7} + 2 e_{8}$ , and define $v_{w} (s) = ϕ (s)^{T} w$ . For a behavior transition $(S, A, S^{'})$ , draw $S$ from $μ$ , draw $A$ from $b (\cdot ∣ S)$ , and draw $S^{'}$ from the stated action transition law. Put $ρ = π (A ∣ S) / b (A ∣ S)$ and $δ = γ v_{w} (S^{'}) - v_{w} (S)$ , and define the expected semi-gradient TD(0) update by ${\overset{ˉ}{w}}^{+} = w + α E_{μ, b} [ρ δ ϕ (S)]$ . Also define the synchronous expected dynamic-programming update by $w^{+} = w + \frac{α}{7} \sum_{s \in S} ((T^{π} v_{w}) (s) - v_{w} (s)) ϕ (s)$ . For every step size $α > 0$ , both deterministic update sequences starting at $w_{0} = (1, 1, 1, 1, 1, 1, 10, 1)$ have Euclidean norm $∥ w ∥_{2} = (\sum_{i = 1}^{8} w_{i}^{2})^{1 / 2}$ tending to infinity. This is a claim about the stated expected/deterministic updates; it asserts no probability-one divergence result for individual stochastic TD trajectories.

Statement references

The finite state/action transition model and stationary policies.

The fixed state weighting, feature map, and policy Bellman operator.

The expected discounted value of one policy-controlled transition.

An eigenvalue is a scalar with a nonzero eigenvector.

A positive geometric sequence with ratio greater than one diverges to infinity.

The Euclidean inner product satisfies Cauchy–Schwarz.

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

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

Facts & Assumptions

Given: The seven-state finite MDP, behavior and target policies, state weighting, feature values, step size, and initial vector in the Statement.

[F1]

Finite Markov decision process with joint reward-transition law: a finite joint transition/reward law induces the state-transition probabilities, and a stationary policy is a probability distribution over the available actions at each state.

[F2]

State-weighted Bellman error and projected Bellman error and Policy Bellman operator: $v_{w} (s) = ϕ (s)^{T} w$ , and $T^{π} v_{w}$ is the expected discounted one-step target under the target policy.

[F3]

Eigenvalues, eigenvectors, eigenspaces $E_{λ} (T) = \ker (T - λ I)$ , and the spectrum $σ_{F} (T)$ of an endomorphism: $λ$ is an eigenvalue of a real linear map when a nonzero vector $x$ satisfies $T (x) = λ x$ .

[F4]

Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation: for real vectors $x, y$ , $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ .

[F5]

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

Proof

1.1givenF1F2algebra

Write $ϕ_{i} = 2 e_{i} + e_{8}$ for $1 \leq i \leq 6$ and $ϕ_{7} = e_{7} + 2 e_{8}$ . The importance ratio is $7$ on solid and $0$ on dashed. Under behavior, every next-state probability is $1 / 7$ : each upper state is reached with probability $(6 / 7) (1 / 6)$ and $s_{7}$ with probability $1 / 7$ . Thus the expected TD update direction is $\frac{1}{7} \sum_{i = 1}^{7} ϕ_{i} (γ ϕ_{7}^{T} w - ϕ_{i}^{T} w)$ . The target Bellman value is $γ ϕ_{7}^{T} w$ at every state, so this also gives the synchronous expected DP direction. Both recurrences are $w^{+} = (I + α M) w$ , where $M = \frac{1}{7} \sum_{i} ϕ_{i} (γ ϕ_{7} - ϕ_{i})^{T}$ .

2.1givenstep 1.1algebra

The update preserves equality of the first six coordinates. Write their common value as $a$ , and put $b = w_{7}$ , $c = w_{8}$ . Set $q_{u} = γ (b + 2 c) - (2 a + c) = - 2 a + γ b + (2 γ - 1) c$ and $q_{7} = (γ - 1) (b + 2 c)$ . By step 1.1, each upper feature contributes $2 q_{u}$ to its own coordinate and $q_{u}$ to coordinate $8$ , while $ϕ_{7}$ contributes $q_{7}$ to coordinate $7$ and $2 q_{7}$ to coordinate $8$ , all with factor $α / 7$ . Thus $a^{+} = a + 2 α q_{u} / 7$ , $b^{+} = b + α q_{7} / 7$ , and $c^{+} = c + α (6 q_{u} + 2 q_{7}) / 7$ . Hence $y = (a, b, c)^{T}$ follows $y^{+} = (I + α B / 7) y$ , where $B = (\begin{array}{ccc} - 4 & 2 γ & 4 γ - 2 \\ 0 & γ - 1 & 2 γ - 2 \\ - 12 & 8 γ - 2 & 16 γ - 10 \end{array})$ and $y_{0} = (1, 10, 1)^{T}$ .

3.1givenstep 2.1algebra

At $γ = 99 / 100$ , let $q (t) = t^{2} - (183 / 100) t + 13 / 50$ . Its distinct roots are $t_{\pm} = (183 \pm \sqrt{23089}) / 200$ , both positive because $23089 < 183^{2}$ and their sum and product are positive. Put $t = t_{+}$ , $u = - 12 / (t + 4)$ , $v = (2 γ u + 8 γ - 2) / (t + 1 - γ)$ , and $ℓ = (u, v, 1)$ . By the definitions of $u$ and $v$ , the first two coordinates of $ℓ B = t ℓ$ hold.

4.1givenF3step 3.1algebra

For the third coordinate, substitution gives $(4 γ - 2) u + (2 γ - 2) v + (16 γ - 10) - t = \frac{- 5000 t q (t)}{50 (t + 4) (100 t + 1)} = 0$ ; the denominator is nonzero since $t > 0$ , and $q (t) = 0$ . Thus $ℓ B = t ℓ$ , so $(B / 7)^{T} ℓ^{T} = (t / 7) ℓ^{T}$ . Since $ℓ = (u, v, 1) \neq 0$ , [F3] makes $t / 7 > 0$ an eigenvalue of the transpose map.

4.2givenstep 3.1algebra

The quadratic in step 3.1 has $q (8 / 5) = - 27 / 250 < 0$ and $q (9 / 5) = 103 / 500 > 0$ . Since it has positive leading coefficient and two distinct roots, the first sign places $8 / 5$ between the roots, and the second places $9 / 5$ to the right of $t_{+}$ ; hence $8 / 5 < t < 9 / 5$ . Therefore $u = - 12 / (t + 4) > - 15 / 7$ . Using $γ = 99 / 100$ and $u > - 15 / 7$ gives $2 γ u + 8 γ - 2 > 2 (99 / 100) (- 15 / 7) + 8 (99 / 100) - 2 = 587 / 350$ . Also $0 < t + 1 - γ < 181 / 100$ , so $v > (587 / 350) / (181 / 100) = 58700 / 63350 > 9 / 10$ . It follows that $ℓ y_{0} = u + 10 v + 1 > - 15 / 7 + 10 = 55 / 7 > 0$ .

5.1givenF4F5step 1.1step 2.1step 4.1step 4.2inductionalgebra∎

For every $α > 0$ , $r = 1 + α t / 7 > 1$ , so [F5] gives $r^{n} \to + \infty$ . Induction using the recurrence in step 2.1 and the eigenrelation in step 4.1 yields $ℓ y_{n} = r^{n} ℓ y_{0} \to + \infty$ , since step 4.2 proves $ℓ y_{0} > 0$ . As $ℓ \neq 0$ , [F4] implies $∥ y_{n} ∥_{2} \geq ∣ ℓ y_{n} ∣ / ∥ ℓ ∥_{2} \to \infty$ . The first six full weights equal $a_{n}$ , so $∥ w_{n} ∥_{2}^{2} = 6 a_{n}^{2} + b_{n}^{2} + c_{n}^{2} \geq ∥ y_{n} ∥_{2}^{2}$ . Step 1.1 showed that the expected TD and synchronous DP recurrences coincide, proving both divergences.

Remarks

The “deadly triad” is used here only as an explanatory name for the interaction among off-policy sampling, bootstrapping, and function approximation. This example does not prove that every method using those ingredients diverges, and it gives no general convergence or divergence theorem for deep neural networks.

Diagram

In the diagram, each circle is an actual state. Solid-action transitions are shown as solid arrows to $s_{7}$ . The dashed box is a routing symbol, not a state: a two-segment dashed path represents one dashed-action transition, whose endpoint is chosen uniformly from the six upper states. All rewards are zero. The diagram restates the model; the proof uses the explicit transition probabilities and feature vectors above.

Depends on

Used by

A finite Baird-star update has exact expected weights Example

Dependency tree · two levels

47 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)
John N. Tsitsiklis and Benjamin Van Roy, An Analysis of Temporal-Difference Learning with Function Approximation (standard reference, not scraped)