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.

One-step Bernoulli REINFORCE has the exact expected gradient

Example

Let $S = {s, d}$ , terminal set $S_{†} = {d}$ , reward set $R = {0, 1}$ , $A (s) = {0, 1}$ , and $A (d) = {*}$ . From $(s, 1)$ transition deterministically to $(d, 1)$ ; from $(s, 0)$ transition deterministically to $(d, 0)$ ; from $(d, *)$ transition deterministically to $(d, 0)$ . All unlisted joint masses are zero. Start at $s$ and use discount $0 \leq γ < 1$ . For $θ \in (0, 1)$ , let $π_{θ} (1 ∣ s) = θ$ , $π_{θ} (0 ∣ s) = 1 - θ$ , and choose the only action at $d$ . An episode has one decision, $G_{0} = R_{1}$ , and $J (θ) = E_{θ} [G_{0}]$ . The unscaled sample direction used by frozen-policy REINFORCE for this episode is $Z = γ^{0} G_{0} \nabla_{θ} \log π_{θ} (A_{0} ∣ s)$ . For every $θ \in (0, 1)$ , $E_{θ} [Z] = \nabla_{θ} J (θ) = 1$ .

Example references

The frozen-policy episodic REINFORCE update.

The finite MDP joint transition-reward convention.

Facts & Assumptions

Given: The finite one-decision MDP, $θ \in (0, 1)$ , the policy family, and the estimator $Z$ in the Example.

[F1]

Finite Markov decision process with joint reward-transition law: each joint next-state/reward mass is nonnegative and the masses for a fixed state-action pair sum to one.

[F2]

Differentiable stationary stochastic policies and score vectors: $π_{θ}$ has fixed positive support on ${0, 1}$ and its score is the gradient of the log action probability.

[F3]

Episodic returns, temporal-difference errors, and policy support: the episode return is the discounted sum from the current time to the terminal time.

[F4]

Episodic REINFORCE with a frozen episode policy: the policy is held fixed while an episode is sampled, and the unscaled sample direction is $\sum_{t < T} γ^{t} G_{t} \nabla_{θ} \log π_{θ} (A_{t} ∣ S_{t})$ ; the parameter increment multiplies this direction by the chosen step size.

[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: the derivative of the identity map $θ \mapsto θ$ is the identity linear map.

Verification

Given: The Example data and facts above.

1.1givenF1F3F6algebra

Action $1$ occurs with probability $θ$ and gives reward $1$ , while action $0$ occurs with probability $1 - θ$ and gives reward $0$ . By [F3], this one-decision episode has $G_{0} = R_{1}$ , so its expected return is $J (θ) = θ$ and $\nabla_{θ} J (θ) = 1$ by [F1] and [F6].

1.2givenF2F5algebra

By [F2] and [F5], the score is $1 / θ$ when $A_{0} = 1$ and $- 1 / (1 - θ)$ when $A_{0} = 0$ .

2.1givenstep 1.1step 1.2F4algebra∎

When $A_{0} = 1$ , $Z = 1 / θ$ ; when $A_{0} = 0$ , $Z = 0$ . Hence $E_{θ} [Z] = θ (1 / θ) + (1 - θ) 0 = 1$ , which equals the gradient from step 1.1.

Remarks

[A1] Axiom of Choice: every family of nonempty sets has a choice function; the referenced general 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

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