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

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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