ExampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generated

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 state-action pair that is never visited keeps its initialization

Example

Consider the continuing finite MDP with one state $s$ , actions $a, b$ , discount $γ = 0$ , and deterministic transitions back to $s$ . Action $a$ always gives reward $1$ and action $b$ always gives reward $0$ . Initialize $Q_{0} (s, a) = 0$ and $Q_{0} (s, b) = - 1$ , and let the behavior rule choose $a$ at every time. Under tabular Q-learning, the pair $(s, b)$ is never visited, so its estimate remains $- 1$ forever, although the optimal action values are $Q^{*} (s, a) = 1$ and $Q^{*} (s, b) = 0$ .

Example references

The finite state-action and reward-transition model.

The optimal action-value Bellman equation.

The one-coordinate Q-learning update.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.

Facts & Assumptions

Given: The one-state MDP, its deterministic rewards, $γ = 0$ , the initial table, behavior rule, and Q-learning updates in the Example.

[F1]

Finite Markov decision process with joint reward-transition law: each state-action pair has the stated joint next-state/reward probability mass.

[F2]

Tabular Q-learning: only the visited state-action coordinate is changed by an update.

[F3]

Optimal action-value Bellman operator: $(H Q) (s, a) = \sum_{s^{'}, ρ} p (s^{'}, ρ ∣ s, a) [ρ + γ \max_{b} Q (s^{'}, b)]$ .

Proof

1.1givenF2induction

The behavior rule always selects $a$ , so no update ever changes coordinate $(s, b)$ . By [F2] and induction on $n$ , $Q_{n} (s, b) = Q_{0} (s, b) = - 1$ for every $n$ .

2.1givenF1F3step 1.1algebra∎

At $γ = 0$ , [F3] gives $(H Q) (s, a) = 1$ and $(H Q) (s, b) = 0$ for every table $Q$ , because the two rewards are deterministic. Thus the unique Bellman fixed point has $Q^{*} (s, b) = 0$ , while step 1.1 shows the learned coordinate is always $- 1$ . The unvisited coordinate is not identified by these data.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 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)
Han-Dong Yang, Optimal Control and Reinforcement Learning, Chapter 2: Value-based Reinforcement Learning (standard reference, not scraped)