ExampleConstruction: AI-generatedVerification: 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 common reward shift moves every one-state Bellman value equally

Example

Let $S = {s}$ , $A (s) = {a, b}$ , and $γ = 1 / 2$ . Both actions return deterministically to $s$ , with reward $1$ under $a$ and reward $3$ under $b$ . View the deterministic policies choosing $a$ and $b$ as stationary policies assigning probability one to those actions; their unique policy Bellman fixed points are $2$ and $6$ , respectively. More generally, for a stationary policy with $θ : = π (b ∣ s) \in [0, 1]$ , its fixed point is $2 + 4 θ$ . After adding $2$ to both rewards, the deterministic-policy fixed points are $6$ and $10$ , and the fixed point for the same stochastic policy is $6 + 4 θ$ . Thus every policy value shifts by $2 / (1 - γ) = 4$ , the difference between the two deterministic-policy values remains $4$ , and $b$ maximizes the Bellman optimality backup at the optimal fixed point in both models.

Example references

The one-state joint reward-transition model.

The policy evaluation formula.

The greedy action-value formula.

Uniqueness of the displayed Bellman fixed points.

Sutton and Barto, Reinforcement Learning: An Introduction.

Facts & Assumptions

Given: The one-state MDP and $γ = 1 / 2$ in the example.

[F1]

Finite Markov decision process with joint reward-transition law: a deterministic self-loop with reward $ρ$ has $r (s, a) = ρ$ and $P (s ∣ s, a) = 1$ .

[F2]

Policy Bellman operator and Bellman optimality operator: the policy and optimality maps use $r (s, a) + γ P (s ∣ s, a) V (s)$ .

[F3]

Finite-MDP Bellman operators are gamma contractions with unique fixed points: each policy operator and the Bellman optimality operator have unique fixed points.

Verification

1.1givenF1F2F3algebra

Under the point-mass stationary policy choosing $a$ , [F1] and [F2] give $T^{a} (v) = 1 + \frac{1}{2} v$ , whose fixed point solves $v = 1 + \frac{1}{2} v$ , hence is $v = 2$ . Under the point-mass stationary policy choosing $b$ , the equation is $v = 3 + \frac{1}{2} v$ , hence its unique fixed point is $v = 6$ .

1.2givenF1F2F3algebra

For a stationary policy with $π (b ∣ s) = θ$ , the expected one-step reward is $(1 - θ) \cdot 1 + θ \cdot 3 = 1 + 2 θ$ , so $T^{π} (v) = 1 + 2 θ + \frac{1}{2} v$ and its unique fixed point is $v = 2 + 4 θ$ .

2.1step 1.2F1F2F3algebra

Adding $2$ to each reward changes the deterministic maps to $T^{a, +} (v) = 3 + \frac{1}{2} v$ and $T^{b, +} (v) = 5 + \frac{1}{2} v$ , whose fixed points are $6$ and $10$ . For the stochastic policy, the expected one-step reward becomes $3 + 2 θ$ , so $T^{π, +} (v) = 3 + 2 θ + \frac{1}{2} v$ and the unique fixed point is $6 + 4 θ$ . All these policy values increase by $4$ , and the difference between the deterministic values remains $4$ .

3.1step 1.1step 2.1F2F3algebra∎

At $v = 6$ , the original action values are $1 + \frac{1}{2} \cdot 6 = 4$ and $3 + \frac{1}{2} \cdot 6 = 6$ , so $T^{*} 6 = 6$ and $b$ is greedy; [F3] makes $6$ the unique optimal fixed point. After the shift, at $v = 10$ the action values are $3 + \frac{1}{2} \cdot 10 = 8$ and $5 + \frac{1}{2} \cdot 10 = 10$ , so the shifted optimality operator fixes $10$ and $b$ is greedy there; [F3] again gives uniqueness.

Remarks

The diagram shows the original MDP only: circles are states, rectangles are actions, state-to-action arrows show the two action choices, and return arrows are labeled by their joint transition masses. The shifted MDP changes the two reward labels from $1, 3$ to $3, 5$ while leaving both transition probabilities equal to one. The verification does not rely on the diagram.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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