TheoremStatement: AI-adaptedProof: 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.

Monotone improvement and finite termination of exact Howard iteration

Statement

For exact policy evaluations, every strict switch in Finite-budget Howard policy iteration for a discounted generator Bellman system weakly increases the policy value at every state and strictly increases it at each switched state. No deterministic policy can recur after a strict switch. With budget $P = \prod_{i} ∣ A_{i} ∣$ , the algorithm terminates within $P$ policy evaluations at the unique solution of the Bellman system in Finite-state discounted generator Bellman system. A smaller budget may return budget_exhausted without a solution claim.

Facts & Assumptions

Given: A finite nonempty state set, finite ordered nonempty action sets, generator rows, rewards, $c > 0$ , exact policy solves, and the iteration of Finite-budget Howard policy iteration for a discounted generator Bellman system.

[F1]

At each nonterminal policy $π_{k}$ , the algorithm solves $A^{π_{k}} V^{k} = r^{π_{k}}$ and changes only states where another action has strictly greater Bellman row value; at such states it chooses a maximizing action (Finite-budget Howard policy iteration for a discounted generator Bellman system).

[F2]

Every policy matrix inverse is entrywise nonnegative with strictly positive diagonal (Inverse positivity of discounted finite-state policy matrices).

[F3]

The policy set has exactly $P = \prod_{i} ∣ A_{i} ∣$ possible deterministic policies; every finite nonempty set of real values attains its extrema (Finite-state discounted generator Bellman system, Every nonempty finite set of reals has a maximum and a minimum).

Proof

1.1F1givenalgebra

Let $π_{k + 1}$ follow a strict-improvement step from $π_{k}$ . At an unchanged state $i$ , $π_{k + 1} (i) = π_{k} (i)$ , so $(r^{π_{k + 1}} - A^{π_{k + 1}} V^{k})_{i} = 0$ by [F1]. At a switched state $i$ , the new action has $\sum_{j} q_{i j}^{π_{k + 1} (i)} V_{j}^{k} + r_{i}^{π_{k + 1} (i)} > c V_{i}^{k}$ , while the old policy equation gives $\sum_{j} q_{i j}^{π_{k} (i)} V_{j}^{k} + r_{i}^{π_{k} (i)} = c V_{i}^{k}$ . Therefore the vector $z = r^{π_{k + 1}} - A^{π_{k + 1}} V^{k}$ is nonnegative and is strictly positive at every switched state.

2.1F2step 1.1algebra

The new exact policy solve gives $A^{π_{k + 1}} (V^{k + 1} - V^{k}) = r^{π_{k + 1}} - A^{π_{k + 1}} V^{k} = z .$ Multiplying by the nonnegative inverse in [F2] yields $V^{k + 1} - V^{k} = (A^{π_{k + 1}})^{- 1} z \geq 0$ . At a switched state $i$ , the $i$ th coordinate is at least $(A^{π_{k + 1}})_{i i}^{- 1} z_{i} > 0$ , so the value increase is strict there.

3.1F1F3step 2.1algebra

If a policy recurred after at least one strict switch, exact evaluation of that same nonsingular policy matrix would reproduce its unique value vector, contradicting the componentwise nondecrease and the strict increase at each intervening switch from step 2.1. Thus all evaluated policies are distinct. There are only $P$ policies by [F3], so after at most $P$ evaluations the strict-improvement set is empty; the budget- $P$ algorithm cannot exhaust first.

4.1F3step 3.1algebra∎

At termination, no action row exceeds the current policy row at any state. The policy equation says that the current row equals $c V_{i}$ ; hence $c V_{i} = \max_{a} (\sum_{j} q_{i j}^{a} V_{j} + r_{i}^{a})$ at every state, so $V$ solves the Bellman system. For uniqueness, suppose $V, W$ are two solutions and let $d = V - W$ . Choose a state $i$ where $d_{i} = \max_{j} d_{j}$ , which exists by [F3]. For every action, $\sum_{j} q_{i j}^{a} d_{j} = \sum_{j \neq i} q_{i j}^{a} (d_{j} - d_{i}) \leq 0$ by the generator signs and row sum. The difference of the two maxima is at most the maximum of the rowwise differences, so $c d_{i} \leq \max_{a} \sum_{j} q_{i j}^{a} d_{j} \leq 0$ , whence $d_{i} \leq 0$ . Thus $\max_{j} (V_{j} - W_{j}) \leq 0$ . Interchanging $V, W$ gives the reverse inequality, so $V = W$ .

Depends on

Used by

A two-state switching example for discounted Howard iteration Example

Dependency tree · two levels

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