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 bootstrapped critic can bias the first actor update

Example

Let $S = {s, x_{0}, x_{1}, d}$ , terminal set $S_{†} = {d}$ , reward set $R = {0}$ , $A (s) = {0, 1}$ , and $A (x_{0}) = A (x_{1}) = A (d) = {*}$ . From $(s, 0)$ transition deterministically to $(x_{0}, 0)$ ; from $(s, 1)$ transition deterministically to $(x_{1}, 0)$ ; from either $x_{i}$ transition to $(d, 0)$ ; and from $d$ transition to $(d, 0)$ . All unlisted joint masses are zero. Start at $s$ and use discount $γ = 1 / 2$ . For $θ \in (0, 1)$ , let $π_{θ} (1 ∣ s) = θ$ , $π_{θ} (0 ∣ s) = 1 - θ$ , and choose the only available action at every other state. Run the algorithm from initial actor parameter $θ_{0} = 1 / 2$ . Use open critic-parameter domain $W = R^{4}$ , with coordinate order $(w_{s}, w_{x_{0}}, w_{x_{1}}, w_{d})$ , and differentiable critic ${\hat{V}}_{w} (z) = w_{z}$ at initial vector $(w_{s}, w_{x_{0}}, w_{x_{1}}, w_{d}) = (0, 0, 1, 0)$ . With actor step size $α = 1 / 4$ , critic step size $β = 0$ , and the one-step actor update $Δ θ = α I_{0} δ_{0} \nabla_{θ} \log π_{θ} (A_{0} ∣ S_{0})$ , where $I_{0} = 1$ and $δ_{0} = R_{1} + γ {\hat{V}}_{w} (S_{1}) - {\hat{V}}_{w} (S_{0})$ , the true start-state objective is $J (θ) = 0$ for every $θ$ , but the expected first actor increment is $1 / 8$ . Each possible first actor update remains in $(0, 1)$ . The episode reaches $d$ after two decisions; at its second decision the only action at $x_{0}$ or $x_{1}$ has score zero, and $β = 0$ leaves the critic unchanged, so all updates remain in $U = (0, 1)$ and $W$ . Thus this bootstrapped critic produces a biased first actor update.

Example references

The one-step actor–critic procedure with discounted actor trace and bootstrapped TD error.

The finite MDP joint transition-reward convention.

Facts & Assumptions

Given: The finite MDP and policies in the Example, $θ = 1 / 2$ , the stated critic values, and the one-step actor-critic update.

[F1]

Finite Markov decision process with joint reward-transition law: each state has its specified finite nonempty action set, and each joint next-state/reward law is a probability distribution.

[F2]

Differentiable stationary stochastic policies and score vectors: on the common positive support, $ψ_{θ} (s, a) = \nabla_{θ} \log π_{θ} (a ∣ s)$ .

[F3]

Episodic returns, temporal-difference errors, and policy support: the episode ends at its first terminal state and its discounted return sums rewards only up to that time.

[F4]

One-step episodic actor–critic with a bootstrapped critic: at time $t$ , the actor increment is $α I_{t} δ_{t} \nabla_{θ} \log π_{θ} (A_{t} ∣ S_{t})$ with $I_{0} = 1$ and $δ_{t} = R_{t + 1} + γ {\hat{V}}_{w} (S_{t + 1}) - {\hat{V}}_{w} (S_{t})$ , setting the terminal continuation to zero; proposed updates are required to stay in the open parameter domains.

[F5]

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

[F6]

The total (Fréchet) derivative $D f (a)$ as the linear first-order approximation with $o (∥ h ∥_{2})$ remainder: a constant scalar function has total derivative the zero linear map, since its first-order remainder is identically zero.

Verification

Given: The Example data and facts above.

1.1givenF1F3F6algebra

Every reward in this MDP is zero and the episode reaches $d$ in two decisions, so its total return is zero for every sampled action sequence. Hence $J (θ) = 0$ for every $θ \in (0, 1)$ and $\nabla_{θ} J (1 / 2) = 0$ by [F6].

1.2givenF2F5algebra

At $θ = 1 / 2$ , the score at $s$ is $\nabla_{θ} \log θ = 2$ for action $1$ and $\nabla_{θ} \log (1 - θ) = - 2$ for action $0$ , by [F2] and [F5].

2.1givenF4step 1.2algebra

If $A_{0} = 0$ , then $S_{1} = x_{0}$ and $δ_{0} = 0 + (1 / 2) \cdot 0 - 0 = 0$ , so the first actor increment is zero. If $A_{0} = 1$ , then $S_{1} = x_{1}$ and $δ_{0} = 0 + (1 / 2) \cdot 1 - 0 = 1 / 2$ , so the first increment is $(1 / 4) \cdot 1 \cdot (1 / 2) \cdot 2 = 1 / 4$ by [F4] and step 1.2. Both proposed values, $1 / 2$ and $3 / 4$ , are in the policy domain $(0, 1)$ . At the second decision the unique action at $x_{i}$ has score zero, and $β = 0$ leaves the critic unchanged; the second updates therefore remain in $(0, 1) \times W$ and the next state is terminal $d$ . This verifies within-episode admissibility and finite termination.

3.1givenstep 1.1step 2.1algebra∎

The two actions each have probability $1 / 2$ , so the expected first actor increment is $(1 / 2) \cdot 0 + (1 / 2) \cdot (1 / 4) = 1 / 8$ . This differs from the true gradient $0$ in step 1.1, proving the stated bias.

Remarks

[A1] Axiom of Choice: every family of nonempty sets has a choice function; the referenced general episodic path-law algorithm assumes AC.

Remarks references

The Axiom of Choice.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

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