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 constant Q-learning step size can preserve persistent reward noise

Example

Consider a continuing MDP with one state $s$ , one action $a$ , discount $γ = 0$ , and a transition back to $s$ at every step. Conditional on the entire past, the reward is $+ 1$ or $- 1$ with probability $1 / 2$ each. Initialize $Q_{0} (s, a) = 0$ and use the constant Q-learning step size $α_{n} (s, a) = 1$ at every update. Then the optimal action value is $0$ , but the Q-learning iterates fail to converge almost surely.

Example references

The finite state-action reward-transition model.

The finite-prefix probabilities of action-state-reward trajectories.

The tabular Q-learning update.

Choice used by the path-space construction.

Sutton and Barto, Reinforcement Learning: An Introduction.

Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning.

Facts & Assumptions

Given: The one-state, one-action finite MDP, $γ = 0$ , the stated conditional reward law, the initial value, the constant step size, and AC for the path law.

[A1]

The Axiom of Choice: the path-space law is available under the Axiom of Choice.

[F1]

Finite Markov decision process with joint reward-transition law: conditional on the only state-action pair, the reward-transition probabilities assign mass $1 / 2$ to each reward and return to $s$ .

[F2]

A finite MDP policy generates action-state-reward trajectories: every finite action-state-reward path has probability equal to the product of its one-step kernel masses.

[F3]

Tabular Q-learning: the updated coordinate moves toward $R_{n + 1} + γ \max_{b} Q_{n} (S_{n + 1}, b)$ , with all other coordinates fixed.

[F4]

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

[F5]

Continuity from above when one set has finite measure: probabilities of decreasing measurable events of finite measure converge to the probability of their intersection.

[F6]

Finite and countable subadditivity of measures: a countable union has probability at most the sum of its event probabilities.

Proof

Given: The MDP and update in the Example, the path-law assumptions and measure suppliers in Facts & Assumptions, and the Axiom of Choice.

1.1givenF1F3F4algebra

There is only one state-action coordinate. Since $γ = 0$ and $α_{n} = 1$ , [F3] gives $Q_{n + 1} (s, a) = R_{n + 1}$ for every $n$ . By [F1] and [F4], $(H Q) (s, a) = \frac{1}{2} (+ 1) + \frac{1}{2} (- 1) = 0$ for every table $Q$ , so the optimal Bellman fixed point is $Q^{*} (s, a) = 0$ .

1.2givenA1F1F2F5F6

Fix $N \geq 1$ . For each $m \geq N$ , let $E_{m}^{+}$ be the event that $R_{N + 1}, \dots, R_{m}$ are all $+ 1$ . By [F2], $P (E_{m}^{+}) = 2^{- (m - N)}$ . These events decrease as $m$ increases; [F5] implies $P (⋂_{m \geq N} E_{m}^{+}) = 0$ . The same calculation gives probability zero for the event that all rewards from index $N + 1$ onward equal $- 1$ . Taking the countable union over $N$ and the two signs, [F6] shows that with probability one the reward sequence is not eventually constant.

2.1step 1.1step 1.2algebra∎

A convergent sequence taking values only in ${- 1, + 1}$ must be eventually constant: the Cauchy condition with tolerance $1$ forbids two different values in any sufficiently late tail. Step 1.2 therefore shows that $(R_{n})$ does not converge almost surely. Step 1.1 gives $Q_{n} (s, a) = R_{n}$ for every $n \geq 1$ , so the Q-learning iterates also fail to converge almost surely.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

32 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)
John N. Tsitsiklis, Asynchronous Stochastic Approximation and Q-Learning (standard reference, not scraped)