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.

Finite-MDP Bellman operators are gamma contractions with unique fixed points

Statement

Let a finite MDP and a discount $0 \leq γ < 1$ be fixed. For $U \in R^{S}$ , define $∥ U ∥_{\infty} = 0$ if $S = \emptyset$ , and $∥ U ∥_{\infty} = \max_{s \in S} ∣ U (s) ∣$ otherwise. For every stationary policy $π$ and all $V, W \in R^{S}$ ,

$∥ T^{π} V - T^{π} W ∥_{\infty} \leq γ ∥ V - W ∥_{\infty} .$

The Bellman optimality operator satisfies the same inequality. Each of $T^{π}$ and $T^{*}$ has exactly one fixed point in $R^{S}$ . The contraction constant is the nonnegative number $γ$ .

Statement references

Sutton and Barto, Reinforcement Learning: An Introduction.

Kaelbling, Littman, and Cassandra, Brown Technical Report CS-96-08.

Facts & Assumptions

Given: A finite MDP, $0 \leq γ < 1$ , a stationary policy $π$ , and $V, W \in R^{S}$ .

[F1]

Finite Markov decision process with joint reward-transition law: $π (\cdot ∣ s)$ and $P (\cdot ∣ s, a)$ are probability distributions, and $r (s, a)$ is finite.

[F2]

Policy Bellman operator: $T^{π} V$ is the policy-weighted finite average of $r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})$ .

[F3]

Bellman optimality operator: $T^{*} V (s)$ is the maximum of those one-step action values over finite nonempty $A (s)$ .

[F4]

Completeness of the sup metric on finite-state value functions: the metric $d_{\infty}$ on $R^{S}$ is complete.

[F5]

A contraction of a nonempty complete metric space into itself has exactly one fixed point, the limit of the iterates from any starting point: a self-map of a nonempty complete metric space with contraction constant $q$ satisfying $0 \leq q < 1$ has exactly one fixed point.

Proof

1.1givenF1F2F3

The finite sums in [F2] and [F3] are real, so both formulas define self-maps of $R^{S}$ ; when $S = \emptyset$ they are the unique empty self-maps.

1.2givenF1F2algebra

For each state $s$ , probability weights and the triangle inequality give $∣ (T^{π} V) (s) - (T^{π} W) (s) ∣ \leq \sum_{a} π (a ∣ s) γ \sum_{s^{'}} P (s^{'} ∣ s, a) ∣ V (s^{'}) - W (s^{'}) ∣ \leq γ ∥ V - W ∥_{\infty} .$ Taking the maximum over $s$ proves the policy-operator contraction inequality; when $S = \emptyset$ , both sides are $0$ .

1.3givenF1F3algebra

Put $Q_{V} (s, a) = r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) V (s^{'})$ . For every action, [F1] gives $∣ Q_{V} (s, a) - Q_{W} (s, a) ∣ \leq γ ∥ V - W ∥_{\infty}$ . For two finite lists $(u_{a})$ and $(v_{a})$ , each $u_{a} \leq v_{a} + \max_{b} ∣ u_{b} - v_{b} ∣$ , so $\max_{a} u_{a} \leq \max_{a} v_{a} + \max_{b} ∣ u_{b} - v_{b} ∣$ ; exchanging the lists gives $∣ \max_{a} u_{a} - \max_{a} v_{a} ∣ \leq \max_{a} ∣ u_{a} - v_{a} ∣$ . Applying this at each $s$ proves the same contraction inequality for $T^{*}$ .

2.1step 1.1step 1.2step 1.3F4F5construct∎

The zero function belongs to $R^{S}$ , so the common domain is nonempty; [F4] makes its metric complete. By definition, $d_{\infty} (V, W) = ∥ V - W ∥_{\infty}$ . Steps 1.2 and 1.3 show that each operator is a self-map with contraction constant $q = γ$ , and the hypothesis $0 \leq γ < 1$ is exactly [F5]'s required range. Applying [F5] separately to $T^{π}$ and $T^{*}$ gives one fixed point for each and uniqueness for each.

Remarks

The proof uses $γ$ itself as the contraction constant. No absolute-value reinterpretation is needed because the discounted domain already assumes $0 \leq γ < 1$ .

Depends on

Used by

Dependency tree · two levels

41 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)
Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra, Planning and Acting in Partially Observable Stochastic Domains, Brown CS-96-08 (standard reference, not scraped)