Alphabeta Math
ExampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generated
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.

An unseen target action cannot be importance sampled from behavior data

Example

Assume the Axiom of Choice for the policy path laws and fix 0≤γ<1. Let the state set be {s,d}, with A(s)={a,b} and A(d)={c}. Action a at s gives reward 0 and transitions to terminal state d; action b gives reward 1 and also transitions to d. At d, action c gives reward 0 and returns to d, but episodes stop upon first reaching d. Let the behavior policy choose a with probability 1 at s and the target policy choose b with probability 1. The formal ordinary first-visit importance-sampling estimator is evaluated here outside the Monte Carlo algorithm's target-support admissibility condition, to show why that condition is needed. Every behavior episode observes a, whose action ratio is π(a∣s)/μ(a∣s)=0, so the estimate is always 0, while the target value is 1. The target-support condition fails because μ(b∣s)=0<π(b∣s).

Facts & Assumptions

Given: The one-decision finite MDP, its terminal set, 0≤γ<1, the Axiom of Choice for the policy path laws, the deterministic behavior and target policies, and the formal ordinary first-visit estimator evaluated as stated in the Example.

[F1]

Finite Markov decision process with joint reward-transition law: the two actions have the deterministic reward and terminal-transition laws stated in the Example.

[F2]

Episodic returns, temporal-difference errors, and policy support: the observed-path likelihood ratio is the product of target action probabilities divided by behavior action probabilities, and target support is needed for the ratio identity.

[F3]

First-visit Monte Carlo policy evaluation: the ordinary estimator averages the likelihood-ratio-weighted first-visit returns over observed visits.

Proof

1.1givenF1F2F3algebra

Every behavior episode has the single action a, reward 0, and a first visit to s at time 0. Its ratio is 0/1=0 by [F2], so each weighted return is zero and the ordinary estimate in [F3] equals 0 for every positive sample count.

2.1givenF1step 1.1algebra∎

The target policy instead chooses b with probability 1, receives reward 1, and terminates immediately; hence its return and value at s are 1. The ordinary behavior estimate is therefore not the target value. The failed premise is exactly target support, since π(b∣s)=1 but μ(b∣s)=0.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 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