Pipeline-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.

Tabular prediction and control by interaction — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

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.

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

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.

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

An unseen target action cannot be importance sampled from behavior data

Example

Assume the Axiom of Choice for the policy path laws and fix $0 \leq γ < 1$ . Let the state set be ${s, d}$ , with $A (s) = {a, b}$ and $A (d) = {c}$ . Action $a$ at $s$ gives reward $0$ and transitions to terminal state $d$ ; action $b$ gives reward $1$ and also transitions to $d$ . At $d$ , action $c$ gives reward $0$ and returns to $d$ , but episodes stop upon first reaching $d$ . Let the behavior policy choose $a$ with probability $1$ at $s$ and the target policy choose $b$ with probability $1$ . The formal ordinary first-visit importance-sampling estimator is evaluated here outside the Monte Carlo algorithm's target-support admissibility condition, to show why that condition is needed. Every behavior episode observes $a$ , whose action ratio is $π (a ∣ s) / μ (a ∣ s) = 0$ , so the estimate is always $0$ , while the target value is $1$ . The target-support condition fails because $μ (b ∣ s) = 0 < π (b ∣ s)$ .

Example references

The finite joint reward-transition model.

The behavior-to-target action ratio and support condition.

The ordinary first-visit importance-sampling estimator.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.

Facts & Assumptions

Given: The one-decision finite MDP, its terminal set, $0 \leq γ < 1$ , the Axiom of Choice for the policy path laws, the deterministic behavior and target policies, and the formal ordinary first-visit estimator evaluated as stated in the Example.

[F1]

Finite Markov decision process with joint reward-transition law: the two actions have the deterministic reward and terminal-transition laws stated in the Example.

[F2]

Episodic returns, temporal-difference errors, and policy support: the observed-path likelihood ratio is the product of target action probabilities divided by behavior action probabilities, and target support is needed for the ratio identity.

[F3]

First-visit Monte Carlo policy evaluation: the ordinary estimator averages the likelihood-ratio-weighted first-visit returns over observed visits.

Proof

1.1givenF1F2F3algebra

Every behavior episode has the single action $a$ , reward $0$ , and a first visit to $s$ at time $0$ . Its ratio is $0 / 1 = 0$ by [F2], so each weighted return is zero and the ordinary estimate in [F3] equals $0$ for every positive sample count.

2.1givenF1step 1.1algebra∎

The target policy instead chooses $b$ with probability $1$ , receives reward $1$ , and terminates immediately; hence its return and value at $s$ are $1$ . The ordinary behavior estimate is therefore not the target value. The failed premise is exactly target support, since $π (b ∣ s) = 1$ but $μ (b ∣ s) = 0$ .

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

Ordinary importance sampling can have infinite variance under full support

Example

Let the state set be ${s, d}$ with actions $A (s) = {a, b}$ and $A (d) = {c}$ . The reward alphabet is ${0, 1}$ and the discount is $γ = 9 / 10$ . At $s$ , action $a$ gives reward $0$ and returns to $s$ , while action $b$ gives reward $1$ and transitions to terminal state $d$ . At $d$ , action $c$ gives reward $0$ and returns to $d$ , but episodes stop upon first reaching $d$ . The behavior policy chooses $a, b$ at $s$ with probabilities $1 / 10, 9 / 10$ , respectively; the target policy chooses them with probabilities $1 / 2, 1 / 2$ . Both policies choose $c$ at $d$ . Starting from $s$ , both policies terminate almost surely and target support holds. If $N$ is the number of $a$ actions before $b$ , the ordinary importance-sampling return $X = Λ_{0 : T - 1} G_{0}$ has mean $10 / 11$ and infinite variance.

Example references

The finite joint reward-transition model.

The discounted episodic return and action likelihood ratio.

The ordinary importance-sampling mean identity under support.

The ordinary first-visit estimator.

Choice used by the path-space construction.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.

Facts & Assumptions

Given: The two-state finite MDP, its terminal state, $γ = 9 / 10$ , the stationary behavior and target policies, and AC for the path laws.

[A1]

The Axiom of Choice: the policy path laws exist under the Axiom of Choice.

[F1]

Finite Markov decision process with joint reward-transition law: the joint reward-transition masses at $s$ are deterministic for $a, b$ as stated, and the two actions have the stated policy probabilities.

[F2]

A finite MDP policy generates action-state-reward trajectories: a finite action-state-reward trajectory has probability equal to the product of its policy action probabilities and MDP transition-reward masses.

[F3]

Episodic returns, temporal-difference errors, and policy support: $G_{0} = \sum_{k = 0}^{T - 1} γ^{k} R_{k + 1}$ and $Λ_{0 : T - 1}$ is the product of target-to-behavior action-probability ratios.

[F4]

Finite-episode importance sampling has the target-policy mean under support: with target support and almost-sure termination under both policies, the ordinary weighted return has target-policy mean.

[F5]

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: $\sum_{n = 0}^{\infty} r^{n} = 1 / (1 - r)$ for $∣ r ∣ < 1$ and diverges for $∣ r ∣ \geq 1$ .

[F6]

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

[F7]

Probability measures and probability spaces and Expectation of a nonnegative or integrable random variable: trajectory probabilities form a probability measure and nonnegative expectations are their Lebesgue integrals.

[F8]

Monotone convergence for the integral: expectations of increasing nonnegative truncations converge to the expectation of their pointwise limit.

Proof

1.1givenA1F1F2F6

Under $μ$ , the event ${N \geq n}$ consists of $n$ successive choices of $a$ and has probability $(1 / 10)^{n}$ by [F2]. Under $π$ it has probability $(1 / 2)^{n}$ . These events decrease to the event of never choosing $b$ ; [F6] shows that this event has probability zero under either policy. Since both actions have positive probability under both policies, target support holds.

2.1givenF2F3F4F5F7F8step 1.1algebra

Under $π$ , $P_{π} (N = n) = 2^{- (n + 1)}$ and the return on that episode is $(9 / 10)^{n}$ . Summing first over $N \leq m$ and then letting $m \to \infty$ , [F7]–[F8] and [F5] give $V^{π} (s) = \sum_{n = 0}^{\infty} 2^{- (n + 1)} (9 / 10)^{n} = \frac{1}{2} \sum_{n = 0}^{\infty} (9 / 20)^{n} = \frac{10}{11} .$ For the episode with $N = n$ , the likelihood ratio is $5^{n} (5 / 9)$ and hence $X_{n} = (5 / 9) (9 / 2)^{n}$ . By [F4] and the support and termination verified in step 1.1, $E_{μ} [X] = V^{π} (s) = 10 / 11$ .

3.1givenF5F7F8step 2.1algebra∎

The behavior probability of $N = n$ is $(9 / 10) (1 / 10)^{n}$ . Therefore $E_{μ} [X^{2}] = \sum_{n = 0}^{\infty} \frac{9}{10} {(\frac{1}{10})}^{n} {[\frac{5}{9} {(\frac{9}{2})}^{n}]}^{2} = \frac{5}{18} \sum_{n = 0}^{\infty} {(\frac{81}{40})}^{n} = + \infty,$ where [F7]–[F8] justify the nonnegative path sum and [F5] gives divergence because $81 / 40 > 1$ . Let $m = 10 / 11$ . Since $X_{n} \to \infty$ , there is $n_{0}$ such that $X_{n} \geq 2 m$ for all $n \geq n_{0}$ , and then $(X_{n} - m)^{2} \geq X_{n}^{2} / 4$ . The tail second moment is infinite, so $E_{μ} [(X - m)^{2}] = + \infty$ . Together with the finite mean from step 2.1, this proves that $X$ has infinite variance.

ExampleConstruction: Literature-sourcedVerification: AI-generatedOpen item page →

A one-sample weighted importance-sampling estimate can be biased

Example

Assume the Axiom of Choice for the policy path laws. Let the state set be ${s, d}$ , with actions $A (s) = {a, b}$ and $A (d) = {c}$ . The discount is $γ = 0$ , and episodes stop on first reaching terminal state $d$ . At $s$ , both actions transition to $d$ ; action $a$ gives reward $1$ and action $b$ gives reward $0$ . At $d$ , action $c$ returns to $d$ with reward $0$ . Let the target policy choose $(a, b)$ with probabilities $(3 / 4, 1 / 4)$ and the behavior policy choose them with probabilities $(1 / 4, 3 / 4)$ ; both choose $c$ at $d$ . Target support holds. For one behavior episode, the self-normalized weighted importance-sampling estimate is the observed reward, so its expectation is $1 / 4$ , whereas the target value is $3 / 4$ . Its finite-sample bias is $- 1 / 2$ .

Example references

The finite joint reward-transition model.

The episodic return, target support, and likelihood ratio.

The self-normalized first-visit importance-sampling estimator.

Expectation as a finite probability-weighted sum in this example.

Sutton and Barto, Reinforcement Learning: An Introduction.

Yang, Optimal Control and Reinforcement Learning, Chapter 2.

Facts & Assumptions

Given: The one-decision finite MDP, its terminal state, $γ = 0$ , the Axiom of Choice for the policy path laws, target and behavior action probabilities, and the one-sample weighted estimator.

[F1]

Finite Markov decision process with joint reward-transition law: action $a$ produces reward $1$ and action $b$ produces reward $0$ , with both transitioning to $d$ .

[F2]

Episodic returns, temporal-difference errors, and policy support: the likelihood ratio for the one-step episode is $π (A_{0} ∣ s) / μ (A_{0} ∣ s)$ ; both possible behavior actions have positive target probability.

[F3]

First-visit Monte Carlo policy evaluation: the weighted estimate is $\sum_{i} W_{i} G_{i} / \sum_{i} W_{i}$ when the denominator is positive.

[F4]

Expectation of a nonnegative or integrable random variable: for a finite-valued variable, expectation is the sum of its values weighted by their probabilities.

Proof

1.1givenF2F3algebra

If the observed action is $a$ , its importance weight is $(3 / 4) / (1 / 4) = 3$ and its return is $1$ ; if it is $b$ , its weight is $(1 / 4) / (3 / 4) = 1 / 3$ and its return is $0$ . In either case the one-sample weighted estimator in [F3] reduces to $W_{1} G_{1} / W_{1} = G_{1}$ , and the denominator is strictly positive.

2.1givenF1F4step 1.1algebra∎

Under behavior, action $a$ occurs with probability $1 / 4$ and action $b$ with probability $3 / 4$ , so [F4] and step 1.1 give expected one-sample estimate $E_{μ} [G_{1}] = (1 / 4) 1 + (3 / 4) 0 = 1 / 4$ . Under the target policy, the state value is $V^{π} (s) = (3 / 4) 1 + (1 / 4) 0 = 3 / 4$ . Their difference is $1 / 4 - 3 / 4 = - 1 / 2$ , proving finite-sample bias.

Tabular prediction and control by interaction — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

A state-action pair that is never visited keeps its initialization

Example

Example references

Facts & Assumptions

Proof

A constant Q-learning step size can preserve persistent reward noise

Example

Example references

Facts & Assumptions

Proof

An unseen target action cannot be importance sampled from behavior data

Example

Example references

Facts & Assumptions

Proof

Ordinary importance sampling can have infinite variance under full support

Example

Example references

Facts & Assumptions

Proof

A one-sample weighted importance-sampling estimate can be biased

Example

Example references

Facts & Assumptions

Proof

Sources