Offline reinforcement learning and off-policy evaluation: Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Full action support permits reweighting while missing support does not

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}$ , and both policies choose $c$ at $z$ . With behavior probabilities $μ (a ∣ s_{0}) = μ (b ∣ s_{0}) = \frac{1}{2}$ , full trajectory coverage holds: the single-trajectory ordinary importance-sampling score is $2$ when action $b$ is observed and $0$ when action $a$ is observed, and its expectation is the target value $1$ . If instead $μ (a ∣ s_{0}) = 1$ , the target action has no behavior support. Two processes that agree on the logged action $a$ and its reward $0$ , but give action $b$ rewards $1$ and $- 1$ , respectively, have identical logged-data laws and different target values; the behavior data cannot identify which value is correct.

Example references

Finite-horizon trajectory laws and the target-value convention.

Ordinary trajectory importance sampling and its weight formula.

A proof that logged data can fail to identify value without coverage.

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, one behavior trajectory at a time, and the corresponding target value.

[F1]

Finite-horizon offline reinforcement-learning dataset and coverage: $P_{H}^{σ}$ is the finite-horizon path law and the target value is the expectation of the discounted return.

[F2]

Ordinary, per-decision, and weighted trajectory importance sampling: for $H = 1$ , the ordinary score is the observed return multiplied by $π (A_{0} ∣ s_{0}) / μ (A_{0} ∣ s_{0})$ .

[F3]

Without trajectory coverage, logged data need not identify policy value: two behavior-indistinguishable finite MDPs can have different target values when the target action is absent from behavior support.

Verification

1.1givenF1F2algebra

Under $μ (b ∣ s_{0}) = \frac{1}{2}$ , the ratio for an observed $b$ is $1 / (\frac{1}{2}) = 2$ ; its return is $1$ . The ratio for an observed $a$ is $0 / (\frac{1}{2}) = 0$ ; its return is $0$ . Thus the OIS score is $2$ with probability $\frac{1}{2}$ and $0$ with probability $\frac{1}{2}$ , so its expectation is $1$ , equal to the target value. Since $H = 1$ , PDIS has the same score.

2.1givenF1F3algebra∎

Under $μ (a ∣ s_{0}) = 1$ , the target trajectory taking $b$ has target probability $1$ and behavior probability $0$ , so the full-coverage premise fails and its likelihood ratio is undefined. The two reward choices $r (b) = 1$ and $r (b) = - 1$ yield the same deterministic logged trajectory but target values $1$ and $- 1$ .

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

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.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

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

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Correct ratios and a correct value model give separate DR identities

Example

Assume AC and take a one-step MDP with states $s_{0}, z$ , actions $a, b$ at $s_{0}$ , action $c$ at $z$ , horizon $H = 1$ , and discount $γ = \frac{1}{2}$ . 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}$ and $c$ at $z$ , so its value from $s_{0}$ is $1$ .

In the first evaluation case, behavior chooses $a$ and $b$ each with probability $\frac{1}{2}$ at $s_{0}$ , the action ratios are exact, and the fitted Q values are ${\hat{Q}}_{0} (s_{0}, a) = {\hat{Q}}_{0} (s_{0}, b) = {\hat{Q}}_{0} (z, c) = 0$ . The DR score is $2$ on a logged $b$ trajectory and $0$ on a logged $a$ trajectory, so its expectation is $1$ although the Q model is wrong at $b$ .

In the second evaluation case, behavior chooses $a$ at $s_{0}$ with probability $1$ , so the target action has no behavior support. The fitted model is exact: ${\hat{Q}}_{0} (s_{0}, a) = 0$ , ${\hat{Q}}_{0} (s_{0}, b) = 1$ , and ${\hat{Q}}_{0} (z, c) = 0$ , with ${\hat{V}}_{1} = 0$ and ${\hat{V}}_{0} (s_{0}) = 1$ . Use the finite multipliers ${\hat{ρ}}_{0} (s_{0}, a) = {\hat{ρ}}_{0} (s_{0}, b) = {\hat{ρ}}_{0} (z, c) = 1$ . Every behavior trajectory has zero residual, so its DR score is $1$ , equal to the target value despite missing support and incorrect action ratios.

In the diagram, vertices are states; an edge labeled $a : r$ means action $a$ produces reward $r$ and moves deterministically to the arrow endpoint. The proof uses the transition/reward values stated in prose, not the drawing.

Example references

The finite-horizon return and behavior-data law.

The DR score and finite-horizon terminal convention.

The separate exact-ratio and exact-model unbiasedness branches.

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

Facts & Assumptions

Given: AC, the one-step MDP, both behavior policies, the target policy, the stated Q functions and multipliers, and $H = 1$ , $γ = \frac{1}{2}$ .

[F1]

Finite-horizon offline reinforcement-learning dataset and coverage: the target value is the expected finite-horizon return, and behavior trajectories use the behavior policy with the same transition/reward law.

[F2]

Finite-horizon doubly robust off-policy value evaluation: with $H = 1$ , $V_{1} = 0$ , the DR score is ${\hat{V}}_{0} (s_{0}) + {\hat{ρ}}_{0} (S_{0}, A_{0}) (R_{1} - {\hat{Q}}_{0} (S_{0}, A_{0}))$ .

[F3]

Doubly robust evaluation is unbiased under either exact component: exact ratios with trajectory coverage or a correct finite-horizon value model with the zero terminal convention suffices for unbiasedness.

Verification

1.1givenF1F2algebra

In the first case, ${\hat{V}}_{0} (s_{0}) = \frac{1}{2} {\hat{Q}}_{0} (s_{0}, a) + \frac{1}{2} {\hat{Q}}_{0} (s_{0}, b) = 0$ , ${\hat{ρ}}_{0} (s_{0}, a) = 0$ , and ${\hat{ρ}}_{0} (s_{0}, b) = 2$ . A logged $a$ has score $0 + 0 (0 - 0) = 0$ ; a logged $b$ has score $0 + 2 (1 - 0) = 2$ . Since each occurs with probability $\frac{1}{2}$ , the mean DR score is $1$ , the target value, although ${\hat{Q}}_{0} (s_{0}, b) = 0 \neq 1$ .

1.2givenF1F2F3algebra

In the second case, the exact finite-horizon model has $Q_{0}^{π} (s_{0}, a) = 0$ , $Q_{0}^{π} (s_{0}, b) = 1$ , and $Q_{0}^{π} (z, c) = 0$ ; its target-policy value is ${\hat{V}}_{0} (s_{0}) = 1$ and its terminal value is $0$ . The behavior policy always logs $a$ , so each observed residual is $0 + \frac{1}{2} \cdot 0 - 0 = 0$ , regardless of the supplied multiplier $1$ . Every DR score is therefore $1$ , and its expectation is the target value despite the absent target action in behavior data.

2.1step 1.1step 1.2F2F3algebra∎

The first calculation verifies the exact-ratio branch with a misspecified Q function; the second verifies the exact-model branch with missing support and incorrect multipliers. Both use the terminal convention ${\hat{V}}_{1} = 0$ from [F2].

Offline reinforcement learning and off-policy evaluation — Examples

2 · Logical flowchart

3 · Definitions, theorems and proofs

4 · Examples, counterexamples and false statements

Full action support permits reweighting while missing support does not

Example

Example references

Facts & Assumptions

Verification

Trajectory importance weights can grow exponentially with horizon

Example

Example references

Facts & Assumptions

Verification

Self-normalization and clipping can introduce finite-sample bias

Example

Example references

Facts & Assumptions

Verification

Correct ratios and a correct value model give separate DR identities

Example

Example references

Facts & Assumptions

Verification

Sources