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.

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.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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