TheoremStatement: Literature-sourcedProof: 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.

Without trajectory coverage, logged data need not identify policy value

Statement

There are two finite one-step Markov decision processes with the same logged-data law under one behavior policy, but different target-policy values and different uniquely optimal actions. A finite one-step Markov decision process here has a finite state set, finite nonempty action sets, a finite reward set, and a probability mass on the next-state/reward pair for every state/action pair. Let the state set be ${s_{0}, z}$ , the action sets be $A (s_{0}) = {a, b}$ and $A (z) = {c}$ , the reward set be ${- 1, 0, 1}$ , and the horizon be $H = 1$ . In both processes, action $a$ at $s_{0}$ gives reward $0$ and moves to $z$ , and action $c$ at $z$ gives reward $0$ and stays at $z$ . In process $M_{+}$ , action $b$ at $s_{0}$ gives reward $1$ and moves to $z$ ; in process $M_{-}$ , it gives reward $- 1$ and moves to $z$ . The behavior policy chooses $a$ at $s_{0}$ with probability $1$ , while the target policy chooses $b$ there with probability $1$ ; both policies choose $c$ at $z$ with probability $1$ . Every behavior-generated logged trajectory is $(s_{0}, a, 0, z)$ in both processes, so every sample size $n \geq 1$ has the same logged-data law in $M_{+}$ and $M_{-}$ . The target value is the expected one-step reward: it is $1$ in $M_{+}$ and $- 1$ in $M_{-}$ , and the unique value-maximizing initial action is $b$ in $M_{+}$ and $a$ in $M_{-}$ . An estimator here is a real-valued function of the logged dataset; it is unbiased for a target value when its expectation under the logged-data law equals that value. Consequently, no such estimator can be unbiased for the target value in both processes, and no data-based action selector can identify the unique optimal initial action with certainty in both.

Statement references

Expectation is the Lebesgue integral under a probability law.

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

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

Facts & Assumptions

Given: The one-step finite-MDP construction and the behavior and target policies in the Statement; estimator expectations are with respect to the logged-data law.

[F1]

Expectation of a nonnegative or integrable random variable: the expectation of a real integrable estimator is its Lebesgue integral under the logged-data probability law.

Proof

1.1givenconstructalgebra

In each process, every state-action pair has a valid reward/next-state probability row: the specified reward and next state occur with probability $1$ . Under the behavior policy the only possible one-step trajectory is $(s_{0}, a, 0, z)$ . Hence each size- $n$ logged dataset consists of the same fixed trajectory tuple in both processes, so its law is the same point mass for every $n \geq 1$ .

1.2givenF1algebra

The target policy chooses $b$ at $s_{0}$ , so its one-step expected return is $1$ in $M_{+}$ and $- 1$ in $M_{-}$ . Since action $a$ has value $0$ , the unique maximizing action is $b$ in $M_{+}$ and $a$ in $M_{-}$ . The behavior law gives zero probability to action $b$ , while the target law gives it probability $1$ ; thus full trajectory coverage fails.

2.1step 1.1step 1.2F1algebra∎

Let $T$ be any real-valued estimator of finite expectation computed from the logged dataset. Equality of the two dataset laws in step 1.1 implies $E_{M_{+}} T = E_{M_{-}} T$ by [F1]. Unbiasedness in both processes would require this common expectation to equal both $1$ and $- 1$ , which is impossible. A data-based action selector has the same output distribution in both processes; if it chooses $b$ with probability $q$ , its probability of being correct is $q$ in $M_{+}$ and $1 - q$ in $M_{-}$ , so it cannot identify the unique maximizing action with certainty in both.

Depends on

Expectation of a nonnegative or integrable random variable

Used by

Dependency tree · two levels

4 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

Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu, Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (standard reference, not scraped)
Nan Jiang and Lihong Li, Doubly Robust Off-policy Value Evaluation for Reinforcement Learning (standard reference, not scraped)