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 small expected cost can coexist with frequent finite-horizon violations

Example

Consider a one-state CMDP with actions safe and risky, deterministic self-transition, zero reward, discount $γ = 1 / 10$ , cost $0$ for safe, cost $1$ for risky, and cost threshold $b = 1 / 8$ . The stationary policy chooses risky with probability $1 / 10$ at every decision, with independent action draws in the first seven decisions. Its expected discounted cost is $1 / 9 < 1 / 8$ , so it is feasible, while the probability of at least one cost during those seven decisions is $5,217,031 / 10,000,000 > 1 / 2$ .

Example references

The finite transition model, bounded cost signal, and stationary randomized policy.

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

Facts & Assumptions

Given: One state $s$ , two actions, deterministic self-transition, $γ = 1 / 10$ , cost $c (s, safe, 0, s) = 0$ , cost $c (s, risky, 0, s) = 1$ , threshold $b = 1 / 8$ , and policy probability $1 / 10$ for risky at each step.

[F1]

Finite discounted constrained Markov decision process: a finite CMDP's transition/reward masses and bounded transition-cost signals determine finite-time state and transition masses.

[F2]

Expected discounted-cost feasibility constraint: $J_{c}^{π} (μ)$ is the discounted sum of the finite-time expected costs, and feasibility means $J_{c}^{π} (μ) \leq b$ .

[F3]

For $∣ r ∣ < 1$ , $\sum_{k \geq 0} r^{k} = 1 / (1 - r)$ , and for $∣ r ∣ \geq 1$ the series diverges: for $0 \leq r < 1$ , $\sum_{t = 0}^{\infty} r^{t} = 1 / (1 - r)$ .

Verification

1.1F1F2F3givenalgebra

At every time $t$ , the state is $s$ and the expected one-step cost is $1 / 10$ . Thus by [F2] and [F3], $J_{c}^{π} (μ) = \sum_{t = 0}^{\infty} (1 / 10)^{t} (1 / 10) = (1 / 10) / (1 - 1 / 10) = 1 / 9$ .

2.1F2step 1.1algebra

Since $1 / 9 < 1 / 8 = b$ , the policy is feasible under the expected discounted-cost constraint.

3.1givenalgebra∎

The probability that all seven independent action draws are safe is $(9 / 10)^{7} = 4,782,969 / 10,000,000$ . Hence the probability of at least one cost is $1 - (9 / 10)^{7} = 5,217,031 / 10,000,000 > 1 / 2$ , as claimed.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

17 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.