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.

A finite sample can report cost satisfaction while the policy violates its expected-cost limit

Example

In a one-state CMDP with $γ = 0$ , cost $1$ for risky and $0$ for safe, let a stationary policy choose risky with probability $1 / 10$ and impose the expected-cost limit $b = 1 / 20$ . The true expected discounted cost is $1 / 10 > b$ . In ten independent one-step rollouts, the empirical mean cost is zero whenever every action is safe, an event of probability $(9 / 10)^{10} = 3,486,784,401 / 10,000,000,000$ .

Example references

A finite CMDP includes bounded transition costs and stationary randomized policies.

Expected discounted-cost feasibility constraint: Expected discounted-cost feasibility is defined by the population objective $J_{c}^{π} (μ) \leq b$ .

Facts & Assumptions

Given: One state, two actions, cost $1$ for risky and $0$ for safe, discount $γ = 0$ , policy probability $1 / 10$ for risky, and threshold $b = 1 / 20$ .

[F1]

Finite discounted constrained Markov decision process: the one-step transition law and cost signal determine the expected cost at each time.

[F2]

Expected discounted-cost feasibility constraint: at $γ = 0$ , the expected discounted cost equals the initial expected one-step cost.

Verification

1.1F1F2givenalgebra

The policy's expected one-step cost is $(1 / 10) \cdot 1 + (9 / 10) \cdot 0 = 1 / 10$ . Since $γ = 0$ , [F2] gives $J_{c}^{π} (μ) = 1 / 10 > 1 / 20 = b$ .

2.1givenstep 1.1algebra∎

Each of the ten independent rollouts is safe with probability $9 / 10$ , so the probability all ten are safe is $(9 / 10)^{10} = 3,486,784,401 / 10,000,000,000$ . On this event the empirical mean is $0 \leq b$ , despite step 1.1 showing that the population constraint is violated.

Depends on

Used by

Nothing in the library uses this result yet.

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.