CounterexampleConstruction: 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.

An arbitrary baseline requires the old-policy residual

Statement refuted

For every finite discounted CMDP with immediate reward signal $r (s, a, ρ, s^{'}) = ρ$ , bounded function $f : S \to R$ , and stationary policies $π, π^{'}$ , define

$δ_{f} (s, a, ρ, s^{'}) : = ρ + γ f (s^{'}) - f (s), {\overset{ˉ}{δ}}_{f}^{σ} (s) : = \sum_{a \in A (s)} \sum_{ρ \in R} \sum_{s^{'} \in S} σ (a ∣ s) p (s^{'}, ρ ∣ s, a) δ_{f} (s, a, ρ, s^{'}), σ \in {π, π^{'}},$

$ϵ_{f} : = \max_{s \in S} ∣ {\overset{ˉ}{δ}}_{f}^{π^{'}} (s) ∣, L_{π, f} (π^{'}) : = \frac{1}{1 - γ} \sum_{s \in S} d^{π} (s) {\overset{ˉ}{δ}}_{f}^{π^{'}} (s),$

and

$D_{π, f}^{\pm} (π^{'}) : = L_{π, f} (π^{'}) \pm \frac{2 γ ϵ_{f}}{(1 - γ)^{2}} \sum_{s \in S} d^{π} (s) {TV}_{s} (π^{'}, π), {TV}_{s} (π^{'}, π) : = \frac{1}{2} \sum_{a \in A (s)} ∣ π^{'} (a ∣ s) - π (a ∣ s) ∣,$

where $d^{π}$ is the normalized discounted state occupancy. Then always

$D_{π, f}^{-} (π^{'}) \leq J_{r}^{π^{'}} (μ) - J_{r}^{π} (μ) \leq D_{π, f}^{+} (π^{'}) .$

Statement references

The finite discounted CMDP interface.

The normalized discounted occupancy.

The unnormalized discounted transition-signal return.

Facts & Assumptions

Given: A one-state CMDP $S = {s}$ with one action, deterministic self-transition and reward $1$ , one identically zero cost signal, initial law $μ (s) = 1$ , discount $γ = 0$ , baseline $f (s) = 0$ , and identical policies $π^{'} = π$ choosing the only action with probability one. Powers at time zero have the convention $γ^{0} = 1$ , including $γ = 0$ .

[F1]

Finite discounted constrained Markov decision process: a finite CMDP has a nonempty finite state set, normalized finite transition masses, and bounded transition reward and cost signals.

[F2]

Normalized discounted state occupancy: $d^{π} (s) = (1 - γ) \sum_{t \geq 0} γ^{t} μ_{t}^{π} (s)$ .

[F3]

Expected discounted-cost feasibility constraint: for bounded signal $g$ , $J_{g}^{π} (μ)$ is the unnormalized discounted sum of its finite-time expectations.

Counterexample

Given: The one-state model above and the definitions in the refuted statement.

1.1givenF1F2F3algebra

The deterministic transition and policy masses are normalized, and both the reward and cost are bounded, so this is a finite CMDP. By [F2] its occupancy has $d^{π} (s) = d^{π^{'}} (s) = 1$ at $γ = 0$ . By [F3] both reward returns satisfy $J_{r}^{π} (μ) = J_{r}^{π^{'}} (μ) = 1$ , so $J_{r}^{π^{'}} (μ) - J_{r}^{π} (μ) = 0$ .

2.1givenstep 1.1algebra∎

Since $f = 0$ and the reward is $1$ , the residual is $δ_{f} = 1$ and $ϵ_{f} = 1$ . The stated surrogate is $L_{π, f} (π^{'}) = 1$ . Identical policies have statewise total variation zero, so $D_{π, f}^{-} (π^{'}) = D_{π, f}^{+} (π^{'}) = 1$ . The asserted lower inequality is $1 \leq 0$ , which is false by step 1.1. Subtracting the old-policy residual expectation instead gives the corrected surrogate $1 - 1 = 0$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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