AlgorithmAlgorithm: Literature-sourcedProof: Not applicablePipeline-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.

Episodic REINFORCE with a fixed state baseline

Definition

Inputs: a finite episodic MDP with nonempty finite state set $S$ , finite nonempty action sets $A (s)$ , finite reward set $R$ , joint transition-reward law $p$ , terminal set $S_{†} \subseteq S$ , and initial state $s_{0} \in S$ ; a discount $0 \leq γ < 1$ ; a differentiable stationary policy family $π_{θ}$ with fixed positive support on an open set $U \subseteq R^{d}$ ; an initial parameter $θ_{0} \in U$ ; a fixed finite-valued state function $b : S \to R$ chosen independently of the episode actions; and a step size $α \geq 0$ .

Admissible conditions: the episode sampled from $s_{0}$ under the frozen policy $π_{θ_{0}}$ reaches $S_{†}$ after finitely many transitions almost surely, and the proposed update remains in $U$ .

Output: the updated policy parameter $θ_{1}$ after one training round.

Hold $θ = θ_{0}$ fixed and select $b$ before sampling one complete episode from $s_{0}$ under $π_{θ_{0}}$ , stopping at its first terminal state; if $s_{0} \in S_{†}$ , take $T = 0$ . For each $t < T$ , compute $G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1}$ , the score $ψ_{t} = \nabla_{θ} \log π_{θ} (A_{t} ∣ S_{t})$ using $θ = θ_{0}$ , and the baseline-adjusted return $G_{t} - b (S_{t})$ . After termination, set

$θ_{1} = θ_{0} + α \sum_{t = 0}^{T - 1} γ^{t} (G_{t} - b (S_{t})) ψ_{t}$

and return $θ_{1}$ . The baseline is fixed throughout the episode and is not updated from it before the actor update; it depends on the state and is independent of each episode action conditional on the state and past.

Definition references

The frozen-policy episodic REINFORCE procedure.

The terminal convention and discounted return from each time step.

The policy family and score-vector convention.

The state baseline's expected score term is zero under the theorem's hypotheses.

Remarks

Under the baseline lemma's hypotheses, the baseline-adjusted sample direction has expectation equal to the discounted objective gradient, and the expected parameter increment is that gradient multiplied by $α$ . An action-independent baseline can reduce variance, but it need not do so for every choice of baseline.

Remarks references

The baseline identity preserving the expected gradient.

Depends on

Used by

A state baseline can eliminate this estimator's variance Example

Dependency tree · two levels

31 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

Richard S. Sutton and Andrew G. Barto, Reinforcement Learning: An Introduction, second-edition draft (standard reference, not scraped)
Ronald J. Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning, Machine Learning 8 (1992) (standard reference, not scraped)