ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-generatedjudge pass (gpt-6-luna)

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.

Self-normalization and clipping can introduce finite-sample bias

Example

Assume AC and take horizon $H = 1$ , discount $γ = \frac{1}{2}$ , states $s_{0}, z$ , actions $a, b$ at $s_{0}$ , and action $c$ at $z$ . Every action moves to $z$ ; action $a$ gives reward $0$ , action $b$ gives reward $1$ , and action $c$ gives reward $0$ . The target policy chooses $b$ at $s_{0}$ ; both policies choose $c$ at $z$ . The behavior policy chooses $a$ and $b$ each with probability $\frac{1}{2}$ . For $n \geq 1$ independent behavior trajectories, let $W_{i}$ be the ordinary trajectory weight and $G_{i}$ the return. The ordinary estimate is $n^{- 1} \sum_{i} W_{i} G_{i}$ . The self-normalized estimate is $\sum_{i} W_{i} G_{i} / \sum_{i} W_{i}$ when its denominator is positive and $0$ when it is zero. The clipped estimate at threshold $1$ is $n^{- 1} \sum_{i} \min {W_{i}, 1} G_{i}$ . The target value is $1$ ; the ordinary estimator has expectation $1$ , the self-normalized estimator has expectation $1 - 2^{- n}$ , and the clipped estimator has expectation $\frac{1}{2}$ .

Example references

The finite-horizon trajectory data and target-value conventions.

Ordinary and self-normalized trajectory importance-sampling formulas.

Sutton and Barto, Reinforcement Learning: An Introduction, 2nd ed.

Jiang and Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Facts & Assumptions

Given: AC, the horizon-one MDP and policies in the Example, $n$ independent behavior trajectories, and the stated estimator conventions.

[F1]

Finite-horizon offline reinforcement-learning dataset and coverage: the target value is the expectation of the finite-horizon return, and the logged trajectories are independent with the behavior-policy law.

[F2]

Ordinary, per-decision, and weighted trajectory importance sampling: an ordinary trajectory weight is the product of the action-propensity ratios; WIS returns $0$ when its normalizing denominator is zero.

Verification

1.1givenF1F2algebra

For one trajectory, $W_{i} = 2$ and $G_{i} = 1$ when action $b$ is observed, an event of probability $\frac{1}{2}$ ; when action $a$ is observed, $W_{i} = 0$ and $G_{i} = 0$ . Thus $W_{i} G_{i}$ equals $2$ or $0$ with equal probability and has expectation $1$ . Linearity gives expectation $1$ for the ordinary sample average.

2.1givenF1F2step 1.1algebra

Let $K$ be the number of $b$ actions in the $n$ independent episodes. If $K > 0$ , the WIS numerator is $2 K$ and its denominator is $2 K$ , so the estimate is $1$ ; if $K = 0$ , its estimate is $0$ by convention. Independence gives $P (K = 0) = 2^{- n}$ . Hence its expectation is $1 - 2^{- n}$ , and its bias relative to target value $1$ is $- 2^{- n}$ .

3.1givenF1F2algebra∎

For each trajectory, $\min {W_{i}, 1} G_{i}$ equals $1$ when $b$ is observed and $0$ when $a$ is observed. Its expectation is $\frac{1}{2}$ , so the clipped sample average also has expectation $\frac{1}{2}$ by linearity. Its bias is $- \frac{1}{2}$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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)
Nan Jiang and Lihong Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (standard reference, not scraped)