AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-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.

Ordinary, per-decision, and weighted trajectory importance sampling

Definition

Assume AC for the policy-induced trajectory laws. Input a finite-horizon logged dataset of $n \geq 1$ independent behavior trajectories, a target policy $π$ , the true behavior propensities $μ (a ∣ s)$ , horizon $H$ , and discount $0 \leq γ \leq 1$ . Require full horizon coverage $P_{H}^{π} ≪ P_{H}^{μ}$ . For trajectory $i$ , compute $ρ_{i, t} = π (A_{t}^{i} ∣ S_{t}^{i}) / μ (A_{t}^{i} ∣ S_{t}^{i})$ for $0 \leq t < H$ , and $W_{i, t} = \prod_{k = 0}^{t} ρ_{i, k}$ ; set $W_{i, - 1} = 1$ . If an observed pair has $μ (A_{t}^{i} ∣ S_{t}^{i}) = 0 < π (A_{t}^{i} ∣ S_{t}^{i})$ , return status unsupported; if both probabilities are zero, set that ratio to zero. Let $G_{i} = \sum_{t = 0}^{H - 1} γ^{t} R_{t + 1}^{i}$ . Return the ordinary trajectory estimator

${\hat{J}}_{O I S} = \frac{1}{n} \sum_{i = 1}^{n} W_{i, H - 1} G_{i},$

the per-decision estimator

${\hat{J}}_{P D I S} = \frac{1}{n} \sum_{i = 1}^{n} \sum_{t = 0}^{H - 1} γ^{t} W_{i, t} R_{t + 1}^{i},$

and the self-normalized weighted estimator

${\hat{J}}_{W I S} = {\begin{cases} \frac{\sum_{i = 1}^{n} W_{i, H - 1} G_{i}}{\sum_{i = 1}^{n} W_{i, H - 1}}, & \sum_{i = 1}^{n} W_{i, H - 1} > 0, \\ 0, & \sum_{i = 1}^{n} W_{i, H - 1} = 0. \end{cases}$

The procedure specifies estimators; it includes no finite-sample unbiasedness assertion for the self-normalized output.

Definition references

Finite-horizon trajectory data, behavior propensities, return, and coverage.

The cumulative action-propensity product is the RN density on each finite trajectory prefix.

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

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

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

Depends on

Used by

Dependency tree · two levels

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