Policy gradients, REINFORCE, and actor–critic — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

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.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

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.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A state baseline can eliminate this estimator's variance

Example

Use the one-decision MDP with states ${s, d}$ , terminal state $d$ , actions ${0, 1}$ at $s$ , one action at $d$ , and deterministic transitions from $(s, 1)$ to $(d, 1)$ , from $(s, 0)$ to $(d, 0)$ , and from $d$ to $(d, 0)$ . All unlisted joint masses are zero. Choose discount $0 \leq γ < 1$ . For $θ \in (0, 1)$ , set $π_{θ} (1 ∣ s) = θ$ and $π_{θ} (0 ∣ s) = 1 - θ$ , and start at $s$ . At $θ = 1 / 2$ , the true objective is $J (θ) = θ$ with gradient $1$ . Let $Z = G_{0} \nabla_{θ} \log π_{θ} (A_{0} ∣ s)$ be the unscaled REINFORCE sample direction, and use the action-independent state baseline $b (s) = 1 / 2$ . Then $Z$ has variance $1$ , while $Z_{b} = (G_{0} - b (s)) \nabla_{θ} \log π_{θ} (A_{0} ∣ s)$ is identically $1$ and has variance $0$ ; both have expectation $1$ .

Example references

The frozen-policy episodic REINFORCE update.

The episodic state-baseline update.

A state-dependent action-independent baseline preserves the expected gradient.

Facts & Assumptions

Given: The stated finite one-decision MDP, $0 \leq γ < 1$ , $θ = 1 / 2$ , the REINFORCE estimator, and the fixed baseline $b (s) = 1 / 2$ .

[F1]

Finite Markov decision process with joint reward-transition law: each state-action pair has the specified normalized joint reward-transition law.

[F2]

Differentiable stationary stochastic policies and score vectors: the policy has fixed positive support and score $\nabla_{θ} \log π_{θ} (a ∣ s)$ on the support.

[F3]

Episodic returns, temporal-difference errors, and policy support: the one-step discounted return is $G_{0} = R_{1}$ .

[F4]

Episodic REINFORCE with a frozen episode policy and Episodic REINFORCE with a fixed state baseline: the unscaled sample directions are $G_{0} ψ_{0}$ and $(G_{0} - b (S_{0})) ψ_{0}$ respectively; each parameter increment multiplies its direction by the chosen step size.

[F5]

A state-dependent action-independent baseline preserves the gradient mean: the expected baseline-adjusted episodic update equals the policy gradient under its stated integrability and trajectory assumptions.

[F6]

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

[F7]

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.1givenF1F2F3F6F7algebra

At $θ = 1 / 2$ , the two actions have probability $1 / 2$ and scores $2$ and $- 2$ by [F2] and [F6]. The specified deterministic reward-transition law [F1] and return convention [F3] give $G_{0} = A_{0}$ and $J (θ) = θ$ , so the true gradient is $1$ by [F7].

2.1givenstep 1.1algebra

Without a baseline, $Z = 2$ when $A_{0} = 1$ and $Z = 0$ when $A_{0} = 0$ . Therefore $E [Z] = 1$ and $Var (Z) = \frac{1}{2} (2 - 1)^{2} + \frac{1}{2} (0 - 1)^{2} = 1$ .

2.2givenstep 1.1F4algebra

With $b (s) = 1 / 2$ , the baseline-adjusted value is $(1 - 1 / 2) 2 = 1$ when $A_{0} = 1$ and $(0 - 1 / 2) (- 2) = 1$ when $A_{0} = 0$ . Thus $Z_{b} = 1$ surely, so $E [Z_{b}] = 1$ and $Var (Z_{b}) = 0$ .

3.1step 1.1step 2.1step 2.2F5algebra∎

The two estimators have the same expectation, equal to the true gradient in step 1.1, while their variances are $1$ and $0$ by steps 2.1 and 2.2. This verifies variance reduction for this baseline and this MDP only.

Remarks

[A1] Axiom of Choice: every family of nonempty sets has a choice function; the referenced episodic algorithms and baseline lemma use the policy path law under AC.

Remarks references

The Axiom of Choice.

CounterexampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

Omitting the start-time discount changes the policy gradient

Statement refuted

For the fixed start-state discounted objective $J (θ) = v^{π_{θ}} (s_{0})$ and returns $G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1}$ , under episode termination, common-support differentiability, finite expected return/score products, and justified differentiation through the trajectory law, the identity

$\nabla J (θ) = E_{π_{θ}} [\sum_{t = 0}^{T - 1} \nabla_{θ} \log π_{θ} (A_{t} ∣ S_{t}) G_{t}]$

always holds.

Statement references

Finite MDP data and stationary policies.

Fixed positive policy support and score vectors.

Facts & Assumptions

Given: States $s_{0}, s_{1}, z$ , start $s_{0}$ , terminal set ${z}$ , discount $γ = 1 / 2$ , one action at $s_{0}$ leading to $s_{1}$ with reward $0$ , and actions $0, 1$ at $s_{1}$ leading to $z$ with reward equal to the action. At $z$ take one zero-reward self-transition action. For $θ \in (0, 1)$ , put $π_{θ} (1 ∣ s_{1}) = θ$ , $π_{θ} (0 ∣ s_{1}) = 1 - θ$ ; the single-action policies at the other states have probability one. The episode is the two-point probability space of terminal paths with masses $θ, 1 - θ$ .

[F1]

Finite Markov decision process with joint reward-transition law: finite normalized transition-reward masses and statewise normalized action probabilities specify a finite MDP and a stationary policy.

[F2]

Differentiable stationary stochastic policies and score vectors: the score on positive fixed support is the gradient of the logarithm of the policy mass.

[F3]

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

Counterexample

Given: The finite model and two-point episode law above, with $G_{t} = \sum_{k = t}^{T - 1} γ^{k - t} R_{k + 1}$ .

1.1givenF1F2algebra

Every episode has $T = 2$ , $R_{1} = 0$ and $R_{2} = A_{1}$ . The given deterministic transition masses are normalized, and the displayed policy probabilities are normalized and positive on fixed support for every $θ \in (0, 1)$ . Both terminal-path masses are affine in $θ$ , so differentiation through their finite sum is exact with identically zero remainders; all score-return products are finite at every fixed interior parameter. Thus all the asserted regularity and termination conditions hold.

2.1givenF2F3step 1.1algebra∎

The objective is $J (θ) = E_{θ} [R_{1} + γ R_{2}] = θ / 2$ , so $\nabla J (θ) = 1 / 2$ . The time-zero score is zero. At time one the score is $1 / θ$ on action $1$ and $- 1 / (1 - θ)$ on action $0$ , while $G_{1} = A_{1}$ . Hence the claimed right-hand side is $θ (1 / θ) + (1 - θ) 0 = 1 \neq 1 / 2$ . Including the missing factor $γ^{1}$ changes this expectation to $1 / 2$ , as required.