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.

Trajectory importance weights can grow exponentially with horizon

Example

Assume AC. Fix a finite horizon $H \geq 1$ and a number $0 < ε < 1$ . Consider one state $s$ , actions $a, b$ , rewards $0, 1$ , and a transition back to $s$ after either action; action $a$ gives reward $0$ and action $b$ gives reward $1$ . Let $γ = 1$ , let the target policy choose $b$ with probability $1$ , and let the behavior policy choose $b$ with probability $ε$ and $a$ with probability $1 - ε$ . Full trajectory coverage holds because the only target action has positive behavior probability. The target return is $H$ . For one behavior trajectory, the ordinary trajectory importance-sampling score is $H ε^{- H}$ if all $H$ actions are $b$ , an event of probability $ε^{H}$ , and is $0$ otherwise. Thus the score has mean $H$ , second moment $H^{2} ε^{- H}$ , and variance $H^{2} (ε^{- H} - 1)$ , which grows exponentially in $H$ for fixed $ε$ .

Example references

The finite-horizon return and trajectory-law conventions.

The ordinary trajectory importance-sampling score.

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

Levine, Kumar, Tucker, and Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems

Facts & Assumptions

Given: AC, the one-state finite MDP, horizon $H$ , $γ = 1$ , target policy $b$ , behavior probability $ε$ for $b$ , and one trajectory sampled under behavior.

[F1]

Finite-horizon offline reinforcement-learning dataset and coverage: the return is the finite discounted reward sum and the logged trajectory law is generated by the behavior policy and the stated joint reward/next-state mass.

[F2]

Ordinary, per-decision, and weighted trajectory importance sampling: the ordinary score is $W_{0 : H - 1} G_{H}$ , with $W_{0 : H - 1}$ the product of the $H$ action-propensity ratios.

Verification

1.1givenF1F2algebra

Under the target policy all $H$ actions are $b$ , every reward is $1$ , and $γ = 1$ , so $G_{H} = H$ . Under behavior, the event that all $H$ actions are $b$ has probability $ε^{H}$ ; on that event every factor is $1 / ε$ , hence $W_{0 : H - 1} = ε^{- H}$ . If any action is $a$ , its target probability is zero, the product weight is zero, and the OIS score is zero.

2.1givenF1F2step 1.1algebra∎

The score $X = W_{0 : H - 1} G_{H}$ therefore equals $H ε^{- H}$ with probability $ε^{H}$ and $0$ otherwise. Thus $E_{μ} X = ε^{H} H ε^{- H} = H$ and $E_{μ} X^{2} = ε^{H} H^{2} ε^{- 2 H} = H^{2} ε^{- H}$ . Subtracting $(E_{μ} X)^{2} = H^{2}$ gives ${Var}_{μ} (X) = H^{2} (ε^{- H} - 1)$ . Since $ε^{- H}$ is exponential in $H$ , the variance grows exponentially although every finite-horizon score is finite.

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)
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (standard reference, not scraped)