Policy gradients, REINFORCE, and actor–critic

Let a finite Markov decision process have nonempty finite state set $S$ and finite nonempty action set $A(s)$ at each state. Let $U\subseteq {\mathbb{R}}^d$ be open, with $d\ge 1$. A differentiable stationary policy family on $U$ is a family of probabilities ${\pi }_{\theta }(a\mid s)$, indexed by $\theta \in U$, $s\in S$, and $a\in A(s)$, such that ${\sum }_{a\in A(s)}{\pi }_{\theta }(a\mid s)=1$, each map $\theta \mapsto {\pi }_{\theta }(a\mid s)$ is totally differentiable, and for each $s$ there is a fixed nonempty support $B(s)\subseteq A(s)$ with ${\pi }_{\theta }(a\mid s)>0$ for every $a\in B(s)$ and $\theta \in U$, while ${\pi }_{\theta }(a\mid s)=0$ for every $a\mathrm{\notin }B(s)$ and $\theta \in U$. The score vector at a supported state-action pair is

${\psi }_{\theta }(s,a):={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a\mid s),a\in B(s),$

where the gradient is the Euclidean vector of partial derivatives. The fixed-support condition makes this logarithm defined throughout $U$ on every action that can be sampled.

A finite state set, finite nonempty state-dependent action sets, and stationary policies given by normalized action probabilities.

Total differentiability is the linear first-order approximation with a remainder of smaller order.

The gradient of a scalar-valued map is the vector of its coordinate partial derivatives.

The total derivative of a composition is the composition of the total derivatives.

The logarithm is differentiable at positive arguments with derivative equal to their reciprocal.

Assume the Axiom of Choice. Let $S$ be a nonempty finite state set, let each $A(s)$ be a finite nonempty action set, and let $p(s^{\mathrm{\prime }},r\mid s,a)$ be a fixed normalized joint law for the next state and reward. Fix an initial state and a terminal set $S_{†}\subseteq S$. Under a differentiable stationary policy family with a support that is fixed and strictly positive on that support throughout its open parameter domain, assume the induced episode terminates almost surely. For $t\ge 0$, let ${\mathcal{H}}_t=\sigma (S_0,A_0,R_1,\dots ,A_{t-1},R_t,S_t)$ be the information available just before the time-$t$ action, and let ${\psi }_t={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(A_t\mid S_t)$ when $t<T$, where $T$ is the first terminal time. Define ${\psi }_t=0$ when $t\ge T$. Then, coordinate by coordinate,

${\mathbb{E}}_{\theta }[{\psi }_t\mid {\mathcal{H}}_t]=0\text{almost surely for every }t\ge 0.$

Sutton and Barto, Reinforcement Learning: An Introduction, second-edition draft.

Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.

Assume the Axiom of Choice. Let a finite Markov decision process have nonempty finite state set $S$, finite nonempty action sets $A(s)$, finite reward set $\mathcal{R}$, and fixed joint transition-reward masses $p(s^{\mathrm{\prime }},r\mid s,a)$. Fix an initial state $s_0\in S$, a terminal set $S_{†}\subseteq S$, and $0\le \gamma <1$. Let $U\subseteq {\mathbb{R}}^d$ be open, let ${\theta }_0\in U$, and let ${\pi }_{\theta }$ be a differentiable stationary policy family with fixed common support on an open neighborhood $U_0$ of ${\theta }_0$. Suppose every episode from $s_0$ under ${\pi }_{\theta }$, for $\theta \in U_0$, reaches $S_{†}$ in finite time almost surely. Let $T$ be the first terminal time, let

$G_t={\sum }_{k=t}^{T-1}{\gamma }^{k-t}{R}_{k+1}(t<T),G_T=0,$

and set $J(\theta )=V^{{\pi }_{\theta }}(s_0)={\mathbb{E}}_{\theta }[{\sum }_{k=0}^{T-1}{\gamma }^k{R}_{k+1}]$. Let $\mathcal{T}$ be the set of finite trajectories that use only actions in the common policy support, have positive transition masses, and stop at their first terminal state. For $\tau =(s_0,a_0,r_1,s_1,\dots ,a_{m-1},r_m,s_m)\in \mathcal{T}$, define

$p_{\theta }(\tau )={\prod }_{t=0}^{m-1}{\pi }_{\theta }(a_t\mid s_t)p(s_{t+1},r_{t+1}\mid s_t,a_t),R_{\gamma }(\tau )={\sum }_{k=0}^{m-1}{\gamma }^k{r}_{k+1}\mathrm{.}$

Assume the trajectory masses $p_{\theta }(\tau )$ are totally differentiable at ${\theta }_0$, the linear map $h\mapsto {\sum }_{\tau \in \mathcal{T}}{R}_{\gamma }(\tau )D{p}_{{\theta }_0}(\tau )h$ is defined by an absolutely convergent sum, and there is a summable $H:\mathcal{T}\to [0,\mathrm{\infty })$ that dominates the return-weighted normalized remainders below and for which those remainders tend to zero pathwise:

$\frac{\mathrm{\mid }{R}_{\gamma }(\tau )\mathrm{\mid }\mathrm{\mid }{p}_{{\theta }_0+h}(\tau )-p_{{\theta }_0}(\tau )-D{p}_{{\theta }_0}(\tau )h\mathrm{\mid }}{\mathrm{\parallel }h{\mathrm{\parallel }}_2}\le H(\tau ),\frac{\mathrm{\mid }{R}_{\gamma }(\tau )\mathrm{\mid }\mathrm{\mid }{p}_{{\theta }_0+h}(\tau )-p_{{\theta }_0}(\tau )-D{p}_{{\theta }_0}(\tau )h\mathrm{\mid }}{\mathrm{\parallel }h{\mathrm{\parallel }}_2}⟶0$

for every $\tau \in \mathcal{T}$ as $h\to 0$, with ${\sum }_{\tau \in \mathcal{T}}H(\tau )<\mathrm{\infty }$.

Also assume

${\mathbb{E}}_{{\theta }_0}\text{\hspace{0.17em}⁣}[{\sum }_{t<T}{\sum }_{k<T}{\gamma }^k\mathrm{\parallel }{\psi }_{{\theta }_0}(S_t,A_t){\mathrm{\parallel }}_2\mathrm{\mid }{R}_{k+1}\mathrm{\mid }]<\mathrm{\infty },$

where ${\psi }_{\theta }(s,a)={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(a\mid s)$ on the common support. Then $J$ is totally differentiable at ${\theta }_0$ and

${\mathrm{\nabla }}_{\theta }J({\theta }_0)={\mathbb{E}}_{{\theta }_0}\text{\hspace{0.17em}⁣}[{\sum }_{t=0}^{T-1}{\gamma }^t{\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_0}(A_t\mid S_t)G_t]\mathrm{.}$

Sutton and Barto, Reinforcement Learning: An Introduction, second-edition draft.

Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.

The factor ${\gamma }^t$ is part of the identity for the discounted start-state objective and the return convention stated here. The result is episodic. A continuing average-reward policy-gradient statement uses a different objective and requires an existing stationary state distribution independent of the start state under the source's ergodicity premise. No convergence theorem for nonlinear or deep parameter updates is asserted here.

Inputs: a finite episodic MDP with nonempty finite state set $S$, finite nonempty action sets $A(s)$, finite reward set $\mathcal{R}$, joint transition-reward law $p$, terminal set $S_{†}\subseteq S$, and initial state $s_0\in S$; a discount $0\le \gamma <1$; a differentiable stationary policy family ${\pi }_{\theta }$ with fixed positive support on an open set $U\subseteq {\mathbb{R}}^d$; a value approximation ${\widehat{V}}_w:S\to \mathbb{R}$ differentiable in $w$ on an open set $W\subseteq {\mathbb{R}}^m$; initial parameters $({\theta }_0,w_0)\in U\times W$; and step sizes $\alpha ,\beta \ge 0$.

Admissible conditions: assume AC for the adaptive episode law; every proposed actor and critic update remains in $U$ and $W$, respectively, and the episode generated by this procedure, including its within-episode parameter updates, reaches $S_{†}$ after finitely many transitions almost surely.

For the sampling instruction, condition on the complete finite transition history and use the current parameters computed from that history. The successive-draw law uses these history-dependent kernels on discrete transition-record spaces, with a fixed stop symbol padding the records after termination.

Output: the final actor and critic parameters $({\theta }_{\mathrm{o}\mathrm{u}\mathrm{t}},w_{\mathrm{o}\mathrm{u}\mathrm{t}})$ after one episode.

Set $(\theta ,w)=({\theta }_0,w_0)$, $S=s_0$, and $I=1$. If $S\in S_{†}$, return $({\theta }_0,w_0)$. Otherwise, while $S\mathrm{\notin }{S}_{†}$, using the current pre-update parameters $(\theta ,w)$:

1. Sample $A\sim {\pi }_{\theta }(\cdot \mid S)$ and then sample $(S^{\mathrm{\prime }},R)$ with joint law $p(S^{\mathrm{\prime }},R\mid S,A)$.
2. Set $C=0$ if $S^{\mathrm{\prime }}\in S_{†}$ and $C={\widehat{V}}_w(S^{\mathrm{\prime }})$ otherwise. Compute the temporal-difference error $\delta =R+\gamma C-{\widehat{V}}_w(S)$.
3. Compute both updates from these pre-update parameters: ${\theta }^{\mathrm{\prime }}=\theta +\alpha I\delta {\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(A\mid S)$ and $w^{\mathrm{\prime }}=w+\beta \delta {\mathrm{\nabla }}_w{\widehat{V}}_w(S)$. Replace $(\theta ,w)$ by $({\theta }^{\mathrm{\prime }},w^{\mathrm{\prime }})$.
4. Set $I\leftarrow \gamma I$ and $S\leftarrow S^{\mathrm{\prime }}$.

When the loop ends, return the current $(\theta ,w)$ as $({\theta }_{\mathrm{o}\mathrm{u}\mathrm{t}},w_{\mathrm{o}\mathrm{u}\mathrm{t}})$.

The critic uses a one-step bootstrapped target; the actor uses the current TD error and the accumulated start-state discount $I={\gamma }^t$. The procedure itself asserts no convergence result.

The finite state-dependent action sets and joint reward-transition law.

The differentiable policy family and action-score vectors.

The terminal convention and discounted episodic TD-error notation.

Under AC, the law of successive draws with history-dependent probability kernels on finite discrete transition records.

The choice premise for the adaptive episode law.

The total derivatives used for policy and value-approximation parameters.

The coordinate gradient convention.

Replacing the full Monte Carlo return by a bootstrapped critic target can change the expected actor direction when the critic is inaccurate. This definition supplies no convergence guarantee for tabular, nonlinear, or deep function approximation.

Inputs: a finite episodic MDP with nonempty finite state set $S$, finite nonempty action sets $A(s)$, finite reward set $\mathcal{R}$, joint transition-reward law $p$, terminal set $S_{†}\subseteq S$, and initial state $s_0\in S$; a discount $0\le \gamma <1$; a differentiable stationary policy family ${\pi }_{\theta }$ with fixed positive support on an open set $U\subseteq {\mathbb{R}}^d$; an initial parameter ${\theta }_0\in U$; and a step size $\alpha \ge 0$.

Admissible conditions: the episode sampled from $s_0$ under the frozen policy ${\pi }_{{\theta }_0}$ reaches $S_{†}$ after finitely many transitions almost surely, and the proposed update remains in $U$.

Output: the updated policy parameter ${\theta }_1$ after one training round.

Hold $\theta ={\theta }_0$ fixed while sampling one episode $(S_0,A_0,R_1,\dots ,S_T)$ from $s_0$ until its first terminal state; if $s_0\in S_{†}$, take $T=0$. For each $t<T$, compute the return $G_t={\sum }_{k=t}^{T-1}{\gamma }^{k-t}{R}_{k+1}$ and score ${\psi }_t={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(A_t\mid S_t)$ using $\theta ={\theta }_0$. After the episode is complete, set

${\theta }_1={\theta }_0+\alpha {\sum }_{t=0}^{T-1}{\gamma }^t{G}_t{\psi }_t$

and return ${\theta }_1$. All returns, scores, and the full sum use the same parameter value ${\theta }_0$ that generated the episode; no policy update occurs while that episode is being sampled.

The finite state-dependent action sets and joint reward-transition law.

A differentiable policy family with fixed positive support and score vectors.

The almost-surely terminating episode and discounted return from each time step.

The action-state-reward trajectory law for a finite MDP policy under AC.

The expected discounted trajectory-score update under the stated differentiation and integrability hypotheses.

Under the theorem's assumptions, the sample direction ${\sum }_{t=0}^{T-1}{\gamma }^t{G}_t{\psi }_t$ has expectation ${\mathrm{\nabla }}_{\theta }J({\theta }_0)$, including the theorem's trajectory-differentiation and Axiom of Choice premises. The expected parameter increment is therefore $\alpha {\mathrm{\nabla }}_{\theta }J({\theta }_0)$. This identity does not imply convergence of repeated nonlinear or deep parameter updates.

The discounted episodic policy-gradient identity and its hypotheses.

Assume the hypotheses of the discounted episodic policy-gradient theorem at a fixed parameter ${\theta }_0$, including the Axiom of Choice, common support, almost-sure finite termination, dominated trajectory differentiation, and the stated integrability of discounted return-score products. Let $b:S\to \mathbb{R}$ be any fixed finite-valued function of the state, chosen independently of the actions in the episode. Then

${\mathbb{E}}_{{\theta }_0}\text{\hspace{0.17em}⁣}\left[{\sum }_{t=0}^{T-1}{\gamma }^t\right(G_t-b(S_t)){\mathrm{\nabla }}_{\theta }\log {\pi }_{{\theta }_0}(A_t\mid S_t)]={\mathrm{\nabla }}_{\theta }J({\theta }_0)\mathrm{.}$

The baseline is action-independent conditional on the state and past. This identity says that subtracting it preserves the expected update; it does not say that every baseline reduces variance.

Sutton and Barto, Reinforcement Learning: An Introduction, second-edition draft.

Williams, Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning.

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

Admissible conditions: the episode sampled from $s_0$ under the frozen policy ${\pi }_{{\theta }_0}$ reaches $S_{†}$ after finitely many transitions almost surely, and the proposed update remains in $U$.

Output: the updated policy parameter ${\theta }_1$ after one training round.

Hold $\theta ={\theta }_0$ fixed and select $b$ before sampling one complete episode from $s_0$ under ${\pi }_{{\theta }_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}{\gamma }^{k-t}{R}_{k+1}$, the score ${\psi }_t={\mathrm{\nabla }}_{\theta }\log {\pi }_{\theta }(A_t\mid S_t)$ using $\theta ={\theta }_0$, and the baseline-adjusted return $G_t-b(S_t)$. After termination, set

${\theta }_1={\theta }_0+\alpha {\sum }_{t=0}^{T-1}{\gamma }^t(G_t-b(S_t)){\psi }_t$

and return ${\theta }_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.

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.

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 $\alpha$. An action-independent baseline can reduce variance, but it need not do so for every choice of baseline.

The baseline identity preserving the expected gradient.