ExampleConstruction: AI-generatedVerification: 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.

Exact CPO cost feasibility can disagree with a sampled line-search cost check

Example

Assume the Axiom of Choice. In a one-state CMDP with discount $γ = 0$ , let the only costs be $0$ for safe and $1$ for risky, with threshold $b = 1 / 20$ . The old policy chooses risky with probability $1 / 100$ , and the proposed policy chooses it with probability $1 / 5$ . Its exact average KL is less than the radius $δ = 4$ , while its exact expected cost is $1 / 5 > b$ . The ideal single-cost CPO cost surrogate is $J_{c}^{π} + (1 - γ)^{- 1} E_{s \sim d^{π}, a \sim π^{'}} A_{c}^{π} (s, a) \leq b$ ; because $γ = 0$ , the performance theorem makes this surrogate equal to the proposed policy's exact expected cost, so the ideal constraint rejects the proposal. If a one-row rollout sample from the old policy observes safe and supplies zero baseline-cost and advantage estimates, the empirical line-search cost is zero and passes the threshold; this sample occurs with probability $99 / 100$ .

Example references

The finite CMDP and its cost signal.

The cost value and advantage used in the exact idealized constraint.

The empirical surrogate and backtracking sample-cost check.

The exact average-KL performance/cost comparison under AC.

Every family of nonempty sets has a choice function.

Facts & Assumptions

Given: One state $s$ , two actions, a self-transition, zero reward, discount $0$ , cost $c (s, safe, 0, s) = 0$ , cost $c (s, risky, 0, s) = 1$ , threshold $b = 1 / 20$ , old policy $π (risky ∣ s) = 1 / 100$ , and proposed policy $π^{'} (risky ∣ s) = 1 / 5$ .

[A1]

The Axiom of Choice: AC is assumed for the KL form of the policy-performance theorem.

[F1]

Finite discounted constrained Markov decision process: the discounted CMDP has finite transition laws and the stated bounded cost signal.

[F2]

Expected discounted-cost feasibility constraint: with $γ = 0$ , expected discounted cost is the one-step expected cost.

[F3]

Discounted value, action-value, and advantage functions: $V_{c}^{π} (s) = J_{c}^{π} (δ_{s})$ and $A_{c}^{π} (s, a) = Q_{c}^{π} (s, a) - V_{c}^{π} (s)$ .

[F4]

Kullback–Leibler divergence: for finite action probabilities, $D_{K L} (q ∥ p) = \sum_{a} q (a) \log (q (a) / p (a))$ when $q ≪ p$ , with natural logarithms.

[F5]

The natural logarithm has derivative 1/x and equals the integral from 1 to x of 1/t: $\log x = \int_{1}^{x} d t / t$ for $x > 0$ .

[F6]

Sample-based constrained policy optimization update: the sample line search tests the finite sample cost surrogate supplied with the on-policy batch; it does not test the exact population cost.

[F7]

Policy performance bound by average divergence: when $γ = 0$ , the total-variation remainder is zero, so the exact baseline cost surrogate equals the return difference.

Proof

1.1F1F2givenalgebra

The old expected cost is $J_{c}^{π} (μ) = 1 / 100$ , while the proposed expected cost is $J_{c}^{π^{'}} (μ) = 1 / 5$ . Since $1 / 5 > 1 / 20$ , the exact cost constraint rejects $π^{'}$ .

1.2A1F4F5givenalgebra

By [F4], the average KL at the single state is $K = (1 / 5) \log 20 + (4 / 5) \log (80 / 99)$ . The second logarithm is negative. Also [F5] gives $\log 20 = \int_{1}^{20} d t / t < 19 < 20$ , so $K < (1 / 5) 20 = 4 = δ$ . Thus the proposal satisfies the exact average-KL radius despite violating the exact cost limit.

2.1F2F3F7step 1.1algebra

The ideal CPO cost advantage under $π$ is $A_{c}^{π} (s, risky) = 1 - 1 / 100 = 99 / 100$ and $A_{c}^{π} (s, safe) = 0 - 1 / 100 = - 1 / 100$ . Its exact surrogate is therefore $J_{c}^{π} + (1 - γ)^{- 1} E_{a \sim π^{'}} A_{c}^{π} (s, a) = 1 / 100 + (1 / 5) (99 / 100) + (4 / 5) (- 1 / 100) = 1 / 5 > 1 / 20$ . By [F7], this is the proposed policy's exact expected cost at $γ = 0$ .

3.1F2F6givenstep 1.1algebra∎

Under $π$ , one sampled action is safe with probability $99 / 100$ . On that event the observed cost is zero; choosing the corresponding supplied baseline-cost estimate and cost-advantage estimate as zero makes the sample cost surrogate at $π^{'}$ equal zero. Since $0 \leq b$ , the line search in [F6] accepts this sample check if $π^{'}$ is proposed, even though step 1.1 gives its exact expected cost $1 / 5$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

42 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

Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel, Constrained Policy Optimization, PMLR 70 (2017) (standard reference, not scraped)