ExampleConstruction: AI-adaptedVerification: AI-generatedPipeline-generatedprecheck passjudge 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 two-state switching example for discounted Howard iteration

Statement

Take states $S = {1, 2}$ and discount $c = 1$ . At state $1$ the ordered actions are stay, with generator row $(q_{11}, q_{12}) = (0, 0)$ and reward $0$ , then go, with row $(- 1, 1)$ and reward $0$ . At state $2$ the ordered actions are exit, tied-exit, and reset, with rows respectively $(q_{21}, q_{22}) = (0, 0)$ , $(0, 0)$ , and $(1, - 1)$ , and rewards $2, 2, 0$ . The least-index initial policy is (stay, exit). Howard iteration makes one strict switch at state $1$ , retains exit at state 2 despite its tie, and terminates with value $V = (1, 2)$ .

Facts & Assumptions

Given: The finite discounted generator system and the deterministic strict-improvement/tie rule of Finite-budget Howard policy iteration for a discounted generator Bellman system.

[F1]

A policy evaluation solves $(c I - Q^{π}) V = r^{π}$ , and a state changes policy only if another action row is strictly greater; ties retain the current action (Finite-state discounted generator Bellman system, Finite-budget Howard policy iteration for a discounted generator Bellman system).

[F2]

Every strict policy switch weakly increases all values and strictly increases each switched value; termination occurs within the finite policy budget (Monotone improvement and finite termination of exact Howard iteration).

Proof

1.1F1givenalgebra

Under (stay, exit), the policy equations are $V_{1} = 0$ and $V_{2} = 2$ , so $V = (0, 2)$ . At state $1$ , the stay row has value $0$ , while the go row has $- V_{1} + V_{2} = 2 > 0$ ; hence the strict-improvement set contains state $1$ . At state $2$ , both exit actions have value $2 = V_{2}$ and reset has value $V_{1} - V_{2} = - 2$ , so state $2$ is not switched.

2.1F1F2step 1.1algebra∎

The new policy (go, exit) solves $2 V_{1} - V_{2} = 0$ and $V_{2} = 2$ , hence $V = (1, 2)$ . At state $1$ , go has value $- 1 + 2 = 1 = V_{1}$ and stay has value $0$ ; at state $2$ , both exit rows remain tied at $2$ and reset has value $1 - 2 = - 1$ . No strict improvement remains, so the algorithm terminates. The duplicate exit tie is retained exactly as specified, and the strict switch increases state $1$ from $0$ to $1$ as [F2] requires.

Depends on

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

Wang He, Reinforcement Learning: A Mathematical Introduction, Chapter 10, Policy Improvement and Policy Iteration (standard reference, not scraped)
Kristian Debrabant and Espen R. Jakobsen, Semi-Lagrangian schemes for linear and fully non-linear Hamilton-Jacobi-Bellman equations (standard reference, not scraped)