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.

Changing a tied greedy action can cycle, while retention stops

Example

Let $S = {s}$ , $A (s) = {a, b}$ , $γ = 1 / 2$ , and let both actions give reward $0$ and return deterministically to $s$ . Start exact policy iteration from the deterministic policy $π_{0} (s) = a$ . The policy value is $0$ , and both actions are greedy. The tie-retaining procedure keeps $a$ and stops after its first evaluation; a rule that always switches to the other maximizing action alternates forever between $a$ and $b$ .

Example references

The one-state MDP and its two action laws.

The exact policy evaluation map.

The greedy action-value formula.

The exact policy-iteration tie-retention rule.

Sutton and Barto, Reinforcement Learning: An Introduction.

Facts & Assumptions

Given: The one-state MDP, $γ = 1 / 2$ , and initial deterministic policy $π_{0} (s) = a$ in the example.

[F1]

Finite Markov decision process with joint reward-transition law: both one-step laws return to $s$ with reward $0$ .

[F2]

Policy Bellman operator: for either deterministic policy, $T^{π} v (s) = \frac{1}{2} v (s)$ .

[F3]

Exact finite policy iteration with retained greedy actions: policy evaluation is exact, and the current action is retained whenever it maximizes the one-step action value.

[F4]

Bellman optimality operator: greedy actions maximize $r (s, a) + γ \sum_{s^{'}} P (s^{'} ∣ s, a) v (s^{'})$ .

[F5]

Finite-MDP Bellman operators are gamma contractions with unique fixed points: each policy Bellman map has a unique fixed point.

Verification

1.1givenF1F2F5algebra

Under either action the policy Bellman equation is $v (s) = \frac{1}{2} v (s)$ by [F1] and [F2], so the unique evaluated value is $v (s) = 0$ , consistently with [F5].

2.1step 1.1F3F4

At this value, [F4] gives $Q (s, a) = 0 = Q (s, b)$ ; both actions maximize. The procedure [F3] retains the current action $a$ , so the policy is unchanged and the stop condition is met.

2.2step 1.1F4algebra

In the variant that always switches to a different maximizing action, both $a$ and $b$ remain maximizing after every evaluation because the model and value $0$ are unchanged. Thus each update sends $a$ to $b$ and $b$ to $a$ , so the procedure never reaches a stable policy.

3.1step 2.1step 2.2∎

The displayed MDP therefore distinguishes the tie-retaining rule from the explicitly defined switching rule, without asserting that every arbitrary tie rule cycles.

Remarks

The diagram uses a circle for the state and rectangles for the available action nodes. Arrows from the state to each action show the available choices, not a single policy; arrows back to the state show each deterministic transition, labeled with probability and reward. The example separately specifies the initial policy and the alternative switching rule, and the verification does not rely on the drawing.

diagram failed to render:
\begin{tikzpicture}[>=stealth]
  \node[circle,draw] (s) at (0,0) {$s$};
  \node[rectangle,draw] (a) at (-2,1.4) {$a$};
  \node[rectangle,draw] (b) at (2,1.4) {$b$};
  \draw[->] (s) -- node[above left] {choose $a$} (a);
  \draw[->] (a) to[bend left=22] node[left] {$p(s,0\mid s,a)=1$} (s);
  \draw[->] (s) -- node[above right] {choose $b$} (b);
  \draw[->] (b) to[bend right=22] node[right] {$p(s,0\mid s,b)=1$} (s);
\end{tikzpicture}

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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