[Updated on 2018-06-30: add two new policy gradient methods, SAC and D4PG.]
[Updated on 2018-09-30: add a new policy gradient method, TD3.]
[Updated on 2019-02-09: add SAC with automatically adjusted temperature].
[Updated on 2019-06-26: Thanks to Chanseok, we have a version of this post in Korean].
[Updated on 2019-09-12: add a new policy gradient method SVPG.]
[Updated on 2019-12-22: add a new policy gradient method IMPALA.]
[Updated on 2020-10-15: add a new policy gradient method PPG & some new discussion in PPO.]
[Updated on 2021-09-19: Thanks to Wenhao & 爱吃猫的鱼, we have this post in Chinese1 & Chinese2].

What is Policy Gradient

Policy gradient is one approach for solving reinforcement learning problems. If you are new to reinforcement learning, start with “A (Long) Peek into Reinforcement Learning » Key Concepts” for the problem formulation and core terminology.

Notations

The following notation list is provided to make the equations in this post easier to read.

Policy Gradient

In reinforcement learning, the objective is to discover an optimal behavior strategy for an agent so that it can obtain optimal rewards. Policy gradient methods focus on representing and optimizing the policy directly. The policy is typically modeled as a parameterized function with respect to $\theta$, $\pi_\theta(a \vert s)$. The reward (objective) function is determined by this policy, and a variety of algorithms can then be used to optimize $\theta$ to achieve the best reward.

The reward function is defined as:

where $d^\pi(s)$ denotes the stationary distribution of the Markov chain for $\pi_\theta$ (the on-policy state distribution under $\pi$). For brevity, the parameter $\theta$ is omitted for the policy $\pi_\theta$ when the policy appears as a subscript of other functions. For example, $d^{\pi}$ and $Q^\pi$ should be $d^{\pi_\theta}$ and $Q^{\pi_\theta}$ when written in full.

Intuitively, if you move along the states of a Markov chain indefinitely, then as time goes on the probability of being in a particular state eventually stops changing. That limiting probability is the stationary probability for $\pi_\theta$. $d^\pi(s) = \lim_{t \to \infty} P(s_t = s \vert s_0, \pi_\theta)$ is the probability that $s_t=s$ when starting from $s_0$ and following policy $\pi_\theta$ for t steps. In fact, the existence of a stationary distribution for a Markov chain is one key reason the PageRank algorithm works. For additional background, see this.

It is natural to expect policy-based methods to be more useful in continuous spaces. In continuous spaces, there are infinitely many actions and (or) states for which values would need to be estimated, making value-based approaches computationally prohibitively expensive. For example, in generalized policy iteration, the policy improvement step $\arg\max_{a \in \mathcal{A}} Q^\pi(s, a)$ requires an exhaustive scan over the action space and thus suffers from the curse of dimensionality.

With gradient ascent, we can move $\theta$ in the direction indicated by the gradient $\nabla_\theta J(\theta)$, searching for the best $\theta$ for $\pi_\theta$ that yields the highest return.

Policy Gradient Theorem

Directly computing the gradient $\nabla_\theta J(\theta)$ is challenging because it depends on both action selection (which is directly determined by $\pi_\theta$) and the stationary state distribution induced by the target behavior (which is indirectly determined by $\pi_\theta$). Because the environment is generally unknown, estimating how a policy update changes the state distribution is difficult.

Fortunately, the policy gradient theorem provides a convenient reformulation: it rewrites the derivative of the objective so that it does not involve the derivative of the state distribution $d^\pi(.)$, substantially simplifying the gradient computation $\nabla_\theta J(\theta)$.

Proof of Policy Gradient Theorem

This section is fairly dense. Here, we walk through the proof (Sutton & Barto, 2017; Sec. 13.1) to understand why the policy gradient theorem holds.

We begin with the derivative of the state-value function:

From this, we obtain:

This expression has a clean recursive structure (see the red parts). The future state-value function $V^\pi(s’)$ can be repeatedly unrolled by applying the same relation.

Consider the following visitation sequence. Let the probability of transitioning from state s to state x under policy $\pi_\theta$ after k steps be denoted as $\rho^\pi(s \to x, k)$.

• When k = 0: $\rho^\pi(s \to s, k=0) = 1$.
• When k = 1, we enumerate all possible actions and sum the transition probabilities to the target state: $\rho^\pi(s \to s’, k=1) = \sum_a \pi_\theta(a \vert s) P(s’ \vert s, a)$.
• Suppose the goal is to move from state s to x in k+1 steps while following policy $\pi_\theta$. One can first travel from s to an intermediate state s’ (any state may serve as an intermediate point, $s’ \in \mathcal{S}$) in k steps, and then transition to x in the final step. This yields a recursive update of the visitation probability: $\rho^\pi(s \to x, k+1) = \sum_{s’} \rho^\pi(s \to s’, k) \rho^\pi(s’ \to x, 1)$.

Next, we return to the unrolled recursive representation of $\nabla_\theta V^\pi(s)$. Let $\phi(s) = \sum_{a \in \mathcal{A}} \nabla_\theta \pi_\theta(a \vert s)Q^\pi(s, a)$ to simplify the maths. If we continue extending $\nabla_\theta V^\pi(.)$ indefinitely, it becomes straightforward to see that, within this unrolling process, we can transition from the starting state s to any state in any number of steps. By summing all visitation probabilities, we obtain $\nabla_\theta V^\pi(s)$.

This rewrite conveniently removes the derivative of the Q-value function, $\nabla_\theta Q^\pi(s, a)$. Substituting into the objective function $J(\theta)$ yields:

In the episodic setting, the proportionality constant ($\sum_s \eta(s)$) is the average episode length. In the continuing setting, it is 1 (Sutton & Barto, 2017; Sec. 13.2). The gradient can be rewritten further as:

Here, $\mathbb{E}_\pi$ refers to $\mathbb{E}_{s \sim d_\pi, a \sim \pi_\theta}$ when both the state and action distributions follow policy $\pi_\theta$ (on policy).

The policy gradient theorem provides the theoretical basis for many policy gradient algorithms. This vanilla policy gradient update is unbiased but exhibits high variance. Many subsequent methods aim to reduce variance while leaving the bias unchanged.

The following is a helpful summary of a general form of policy gradient methods, borrowed from the GAE (general advantage estimation) paper (Schulman et al., 2016). This post provides a thorough discussion of multiple components in GAE and is highly recommended.

Policy Gradient Algorithms

A large number of policy gradient algorithms have been proposed in recent years, and it is not feasible to cover them exhaustively. Here, I introduce several that I have encountered and read about.

REINFORCE

REINFORCE (Monte-Carlo policy gradient) uses an estimated return computed via Monte-Carlo methods. It updates the policy parameter $\theta$ using episodic samples. REINFORCE works because the expected value of the sample gradient equals the true gradient:

Therefore, we can measure $G_t$ from real sample trajectories and use it to update the policy. Because it depends on complete trajectories, it is a Monte-Carlo method.

The procedure is straightforward:

1. Randomly initialize the policy parameter $\theta$.
2. Generate one on-policy trajectory $\pi_\theta$: $S_1, A_1, R_2, S_2, A_2, \dots, S_T$.
3. For t=1, 2, … , T:
   1. Estimate the return $G_t$;
   2. Update the policy parameters: $\theta \leftarrow \theta + \alpha \gamma^t G_t \nabla_\theta \ln \pi_\theta(A_t \vert S_t)$

A common variation of REINFORCE subtracts a baseline value from the return $G_t$ in order to reduce the variance of gradient estimation while keeping the bias unchanged (a desirable property whenever it is achievable). For example, a frequently used baseline subtracts the state value from the action value; in that case, the gradient ascent update uses the advantage $A(s, a) = Q(s, a) - V(s)$. This post explains why baselines reduce variance and also reviews a set of policy gradient fundamentals.

Actor-Critic

Two primary elements in policy gradient methods are the policy model and the value function. It is often beneficial to learn a value function alongside the policy, since the value function can support the policy update, for example, by reducing gradient variance in vanilla policy gradients. This is precisely the motivation behind the Actor-Critic approach.

Actor-critic methods use two models, which may optionally share parameters:

• Critic: updates the value function parameters w. Depending on the specific algorithm, this value function may be the action-value $Q_w(a \vert s)$ or the state-value $V_w(s)$.
• Actor: updates the policy parameters $\theta$ for $\pi_\theta(a \vert s)$, following the direction recommended by the critic.

To make the idea concrete, consider a simple action-value actor-critic algorithm.

1. Initialize $s, \theta, w$ at random; sample $a \sim \pi_\theta(a \vert s)$.
2. For $t = 1 \dots T$:
   1. Sample reward $r_t \sim R(s, a)$ and next state $s’ \sim P(s’ \vert s, a)$;
   2. Then sample the next action $a’ \sim \pi_\theta(a’ \vert s’)$;
   3. Update the policy parameters: $\theta \leftarrow \theta + \alpha_\theta Q_w(s, a) \nabla_\theta \ln \pi_\theta(a \vert s)$;
   4. Compute the correction (TD error) for action-value at time t:
      $\delta_t = r_t + \gamma Q_w(s’, a’) - Q_w(s, a)$
      and use it to update the parameters of the action-value function:
      $w \leftarrow w + \alpha_w \delta_t \nabla_w Q_w(s, a)$
   5. Update $a \leftarrow a’$ and $s \leftarrow s’$.

Two learning rates, $\alpha_\theta$ and $\alpha_w$, are specified in advance for updating the policy parameters and the value function parameters, respectively.

Off-Policy Policy Gradient

REINFORCE and the vanilla actor-critic method are both on-policy: training samples are collected using the target policy, meaning the same policy that is being optimized. Off-policy methods, however, provide several additional advantages:

1. Off-policy training does not require full trajectories and can reuse past episodes (via “experience replay”), leading to substantially improved sample efficiency.
2. Because samples are collected under a behavior policy that differs from the target policy, the method can achieve improved exploration.

Next, we examine how off-policy policy gradients are computed. The behavior policy used for data collection is a known policy (defined in advance, much like a hyperparameter) and is labeled $\beta(a \vert s)$. The objective sums rewards over the state distribution induced by this behavior policy:

where $d^\beta(s)$ is the stationary distribution under the behavior policy $\beta$; recall that $d^\beta(s) = \lim_{t \to \infty} P(S_t = s \vert S_0, \beta)$; and $Q^\pi$ is the action-value function estimated with respect to the target policy $\pi$ (not the behavior policy).

Because the training observations are sampled by $a \sim \beta(a \vert s)$, we can rewrite the gradient as:

where $\frac{\pi_\theta(a \vert s)}{\beta(a \vert s)}$ is the importance weight. Since $Q^\pi$ is a function of the target policy and therefore a function of the policy parameter $\theta$, the product rule implies that we should also differentiate $\nabla_\theta Q^\pi(s, a)$. However, computing $\nabla_\theta Q^\pi(s, a)$ is extremely difficult in practice. Fortunately, if we approximate the gradient by ignoring the gradient of Q, we still guarantee policy improvement and ultimately reach the true local minimum. This is justified in the proof here (Degris, White & Sutton, 2012).

In short, in the off-policy setting, policy gradient can be adjusted using a weighted sum, where the weight is the ratio between the target policy and the behavior policy, $\frac{\pi_\theta(a \vert s)}{\beta(a \vert s)}$.

A3C

[paper|code]

Asynchronous Advantage Actor-Critic (Mnih et al., 2016), abbreviated as A3C, is a well-known policy gradient method with an emphasis on parallel training.

In A3C, critics learn the value function while multiple actors train in parallel and periodically synchronize with global parameters. As a result, A3C is structured to perform well in parallel training environments.

Using the state-value function as an example, the value loss minimizes the mean squared error, $J_v(w) = (G_t - V_w(s))^2$, and gradient descent can be used to find the optimal w. This state-value function is then used as the baseline for the policy gradient update.

The algorithm outline is as follows:

1. Maintain global parameters, $\theta$ and $w$, along with analogous thread-specific parameters, $\theta’$ and $w’$.

2. Initialize the time step $t = 1$.

3. While $T \leq T_\text{MAX}$:

   1. Reset the gradients: $\mathrm{d}\theta = 0$ and $\mathrm{d}w = 0$.
   2. Synchronize thread-specific parameters with the global parameters: $\theta’ = \theta$ and $w’ = w$.
   3. Set $t_\text{start}$ = t and sample an initial state $s_t$.
   4. While ($s_t$ != TERMINAL) and $t - t_\text{start} \leq t_\text{max}$:
      1. Select action $A_t \sim \pi_{\theta’}(A_t \vert S_t)$ and observe reward $R_t$ and the next state $s_{t+1}$.
      2. Update $t = t + 1$ and $T = T + 1$.
   5. Initialize the variable that stores the return estimate.
   $ R = \begin{cases} 0 & \text{if } s_t \text{ is TERMINAL} \\ V_{w'}(s_t) & \text{otherwise} \end{cases} $
   6. For $i = t-1, \dots, t\_\text{start}$: 1. $R \leftarrow \gamma R + R\_i$; here R is a MC measure of $G\_i$. 2. Accumulate gradients w.r.t. $\theta'$: $d\theta \leftarrow d\theta + \nabla\_{\theta'} \log \pi\_{\theta'}(a\_i \vert s\_i)(R - V\_{w'}(s\_i))$;
   Accumulate gradients w.r.t. w': $dw \leftarrow dw + 2 (R - V\_{w'}(s\_i)) \nabla\_{w'} (R - V\_{w'}(s\_i))$.
   7. Update asynchronously $\theta$ using $\mathrm{d}\theta$, and $w$ using $\mathrm{d}w$.

A3C makes parallelism possible during multi-agent training. The gradient accumulation in step (6.2) can be viewed as a parallelized reformulation of minibatch stochastic gradient updates: $w$ or $\theta$ are each adjusted slightly in the direction contributed independently by each training thread.

A2C

[paper|code]

A2C is a synchronous, deterministic counterpart to A3C. Accordingly, it is named “A2C” by removing the leading “A” (for “asynchronous”). In A3C, each agent communicates with the global parameters independently. As a result, thread-specific agents may sometimes act using policies from different versions, and the aggregated update can therefore be suboptimal. To address this inconsistency, A2C introduces a coordinator that waits for all parallel actors to complete their work before updating the global parameters. In the next iteration, all parallel actors then begin from the same policy. This synchronized gradient update makes training more coherent and can potentially speed up convergence.

A2C has been shown to use GPUs more efficiently and to work better with large batch sizes, while achieving the same or better performance than A3C.

DPG

[paper|code]

In the methods described above, the policy function $\pi(. \vert s)$ is modeled as a probability distribution over actions $\mathcal{A}$ given the current state, meaning it is stochastic. In contrast, deterministic policy gradient (DPG) models the policy as a deterministic decision: $a = \mu(s)$. At first glance, this may seem puzzling: if the policy outputs a single action, how can we compute a gradient with respect to an action probability? The derivation becomes clear when we work through it step by step.

To support the discussion, here is a quick refresher on several notations:

• $\rho_0(s)$: The initial distribution over states
• $\rho^\mu(s \to s’, k)$: Starting from state s, the visitation probability density at state s’ after moving k steps by policy $\mu$.
• $\rho^\mu(s’)$: Discounted state distribution, defined as $\rho^\mu(s’) = \int_\mathcal{S} \sum_{k=1}^\infty \gamma^{k-1} \rho_0(s) \rho^\mu(s \to s’, k) ds$.

The objective function to optimize is:

Deterministic policy gradient theorem: We now compute the gradient. By the chain rule, we first take the gradient of Q with respect to the action a, and then take the gradient of the deterministic policy function $\mu$ with respect to $\theta$:

One way to view a deterministic policy is as a special case of a stochastic policy, where the probability distribution assigns a single extreme non-zero value to one action. In the DPG paper, the authors show that if the stochastic policy $\pi_{\mu_\theta, \sigma}$ is re-parameterized by a deterministic policy $\mu_\theta$ and a variation variable $\sigma$, then the stochastic policy becomes equivalent to the deterministic case when $\sigma=0$. Relative to the deterministic policy, the stochastic policy is expected to require more samples, because it integrates data over the full state and action space.

The deterministic policy gradient theorem can be incorporated into standard policy gradient frameworks.

As an example, consider an on-policy actor-critic algorithm to illustrate the workflow. In each iteration of on-policy actor-critic, two actions are taken deterministically $a = \mu_\theta(s)$, and the SARSA update on policy parameters uses the new gradient derived above:

However, unless the environment provides sufficient noise, it is difficult to ensure adequate exploration because the policy is deterministic. Two common options are to inject noise into the policy (which, somewhat ironically, makes it non-deterministic) or to learn off-policy by using a different stochastic behavior policy to collect samples.

For example, in the off-policy setting, training trajectories are generated by a stochastic policy $\beta(a \vert s)$, so the state distribution follows the corresponding discounted state density $\rho^\beta$:

Note that, because the policy is deterministic, we only need $Q^\mu(s, \mu_\theta(s))$ rather than $\sum_a \pi(a \vert s) Q^\pi(s, a)$ as the estimated reward for a given state s. In off-policy learning with a stochastic policy, importance sampling is often used to correct the mismatch between behavior and target policies, as described above. However, because the deterministic policy gradient removes the integral over actions, importance sampling can be avoided.

DDPG

[paper|code]

DDPG (Lillicrap, et al., 2015), short for Deep Deterministic Policy Gradient, is a model-free off-policy actor-critic algorithm that combines DPG with DQN. Recall that DQN (Deep Q-Network) stabilizes Q-function learning through experience replay and a frozen target network. While the original DQN is designed for discrete spaces, DDPG extends the approach to continuous spaces using an actor-critic framework while learning a deterministic policy.

To improve exploration, DDPG constructs an exploration policy $\mu’$ by adding noise $\mathcal{N}$:

DDPG also performs soft updates (referred to as “conservative policy iteration”) for the parameters of both the actor and critic, with $\tau \ll 1$: $\theta’ \leftarrow \tau \theta + (1 - \tau) \theta’$. This constrains the target network values to evolve gradually, rather than using DQN’s approach of holding the target network frozen for a fixed period.

A detail from the paper that is especially valuable for robotics concerns normalization across low-dimensional features with different physical units. For instance, a model may learn a policy using robot positions and velocities as inputs. These physical quantities differ intrinsically, and even quantities of the same type can vary substantially across different robots. To address this, batch normalization is applied by normalizing each dimension across samples within a minibatch.

D4PG

[paper|code (Search “github d4pg” and you will see a few.)]

Distributed Distributional DDPG (D4PG) introduces several enhancements to DDPG to support distributional learning.

(1) Distributional Critic: Instead of estimating only an expected Q value, the critic models the return as a random variable, that is, a distribution $Z_w$ parameterized by $w$, and therefore $Q_w(s, a) = \mathbb{E} Z_w(x, a)$. The distribution parameters are learned by minimizing a distance between two distributions, that is, the distributional TD error: $L(w) = \mathbb{E}[d(\mathcal{T}_{\mu_\theta}, Z_{w’}(s, a), Z_w(s, a)]$, where $\mathcal{T}_{\mu_\theta}$ is the Bellman operator.

The deterministic policy gradient update becomes:

(2) $N$-step returns: When computing the TD error, D4PG uses a $N$-step TD target rather than a one-step target, incorporating rewards further into the future. The revised TD target is:

(3) Multiple Distributed Parallel Actors: D4PG uses $K$ independent actors to collect experience in parallel and feed it into a shared replay buffer.

(4) Prioritized Experience Replay (PER): The final modification applies non-uniform sampling from a replay buffer of size $R$, with probability $p_i$. Under this scheme, a sample $i$ is selected with probability $(Rp_i)^{-1}$, and the associated importance weight is $(Rp_i)^{-1}$.

MADDPG

[paper|code]

Multi-agent DDPG (MADDPG) (Lowe et al., 2017) extends DDPG to environments in which multiple agents coordinate to complete tasks using only local information. From the perspective of any single agent, the environment becomes non-stationary because other agents’ policies are updated rapidly and are not directly observable. MADDPG is an actor-critic approach redesigned specifically to cope with this evolving environment and with agent-to-agent interactions.

The setting can be formalized as a multi-agent extension of an MDP, often referred to as Markov games. MADDPG is proposed for partially observable Markov games. Suppose there are N agents with a state set $\mathcal{S}$. Each agent has an action set $\mathcal{A}_1, \dots, \mathcal{A}_N$ and an observation set $\mathcal{O}_1, \dots, \mathcal{O}_N$. The state transition function spans the state, action, and observation spaces $\mathcal{T}: \mathcal{S} \times \mathcal{A}_1 \times \dots \mathcal{A}_N \mapsto \mathcal{S}$. Each agent’s stochastic policy depends only on its own observation and action, $\pi_{\theta_i}: \mathcal{O}_i \times \mathcal{A}_i \mapsto [0, 1]$ (a probability distribution over actions given its own observation), or it may use a deterministic policy: $\mu_{\theta_i}: \mathcal{O}_i \mapsto \mathcal{A}_i$.

Let $\vec{o} = {o_1, \dots, o_N}$, $\vec{\mu} = {\mu_1, \dots, \mu_N}$, and let the policies be parameterized by $\vec{\theta} = {\theta_1, \dots, \theta_N}$.

In MADDPG, the critic learns a centralized action-value function $Q^\vec{\mu}_i(\vec{o}, a_1, \dots, a_N)$ for the i-th agent, where $a_1 \in \mathcal{A}_1, \dots, a_N \in \mathcal{A}_N$ denotes the actions of all agents. Each $Q^\vec{\mu}_i$ is learned separately for $i=1, \dots, N$, enabling agents to have arbitrary reward structures, including conflicting rewards in competitive scenarios. Meanwhile, multiple actors (one per agent) explore and update their own policy parameters $\theta_i$.

Actor update:

where $\mathcal{D}$ is the experience replay memory buffer, which contains multiple episode samples $(\vec{o}, a_1, \dots, a_N, r_1, \dots, r_N, \vec{o}’)$: given the current observation $\vec{o}$, agents take action $a_1, \dots, a_N$ and receive rewards $r_1, \dots, r_N$, producing the next observation $\vec{o}’$.

Critic update:

where $\vec{\mu}’$ are the target policies with delayed, softly updated parameters.

If the policies $\vec{\mu}$ are unknown during the critic update, each agent can be instructed to learn and update its own approximation of the other agents’ policies. With these approximations, MADDPG can still learn efficiently, even when the inferred policies are imperfect.

To reduce the high variance caused by interactions among competing or cooperating agents, MADDPG introduces an additional component: policy ensembles:

1. Train K policies for one agent;
2. Select a random policy for episode rollouts;
3. Use an ensemble of these K policies for the gradient update.

In summary, MADDPG adds three key ingredients on top of DDPG to adapt it to multi-agent environments:

• A centralized critic with decentralized actors;
• Actors that can learn using estimated policies of other agents;
• Policy ensembling to reduce variance.

TRPO

[paper|code]

To improve training stability, parameter updates that alter the policy too aggressively in a single step should be avoided. Trust region policy optimization (TRPO) (Schulman, et al., 2015) operationalizes this principle by applying a KL divergence constraint on the magnitude of each policy update.

Consider off-policy RL, where the policy $\beta$ used to collect trajectories on rollout workers differs from the policy $\pi$ being optimized. The objective in an off-policy formulation measures the total advantage over the state visitation distribution and actions, and it compensates for the mismatch between the training data distribution and the true on-policy state distribution using an importance sampling estimator:

where $\theta_\text{old}$ are the policy parameters before the update (and are therefore known); $\rho^{\pi_{\theta_\text{old}}}$ is defined in the same manner as above; $\beta(a \vert s)$ is the behavior policy used to collect trajectories. Note that an estimated advantage $\hat{A}(.)$ is used rather than the true advantage function $A(.)$, because the true rewards are often unknown.

In on-policy training, the data-collection policy is theoretically the same as the policy being optimized. However, if rollout workers and optimizers run asynchronously in parallel, the behavior policy can become stale. TRPO accounts for this nuance by denoting the behavior policy as $\pi_{\theta_\text{old}}(a \vert s)$, yielding the objective:

TRPO seeks to maximize the objective function $J(\theta)$ subject to a trust region constraint, which requires the distance between the old and new policies, measured by KL-divergence, to remain sufficiently small, bounded by a parameter δ:

When this hard constraint is satisfied, the old and new policies are prevented from diverging excessively. Even so, TRPO can guarantee monotonic improvement over policy iteration (Neat, right?). If you are interested, see the proof in the paper :)

PPO

[paper|code]

While TRPO is relatively complex, it is often desirable to enforce a similar constraint with a simpler implementation. Proximal policy optimization (PPO) does so by using a clipped surrogate objective, while maintaining comparable performance.

First, define the probability ratio between the new and old policies as:

Then the TRPO objective (on-policy) can be written as:

Without constraining the distance between $\theta_\text{old}$ and $\theta$, maximizing $J^\text{TRPO} (\theta)$ can cause instability, due to excessively large parameter updates and large policy ratios. PPO enforces a constraint by keeping $r(\theta)$ within a small interval around 1, specifically $[1-\epsilon, 1+\epsilon]$, where $\epsilon$ is a hyperparameter.

The function $\text{clip}(r(\theta), 1 - \epsilon, 1 + \epsilon)$ clips the ratio so that it is at most $1+\epsilon$ and at least $1-\epsilon$. PPO’s objective takes the minimum of the unclipped and clipped forms, removing the incentive to push policy updates to extreme values in pursuit of higher rewards.

When PPO is applied to a network architecture that shares parameters between the policy (actor) and value (critic) functions, the objective is extended beyond the clipped reward term. It also includes a value estimation error term (formula in red) and an entropy term (formula in blue) to encourage adequate exploration.

where Both $c_1$ and $c_2$ are hyperparameter constants.

PPO has been evaluated on a set of benchmark tasks and shown to deliver strong results with substantially greater simplicity.

In a later paper by Hsu et al., 2020, two common PPO design choices are revisited: (1) the clipped probability ratio for policy regularization and (2) parameterizing the policy action space using either a continuous Gaussian distribution or a discrete softmax distribution. The authors identify three failure modes in PPO and propose replacements for these two design elements.

The failure modes are:

1. In continuous action spaces, standard PPO can be unstable when rewards vanish outside bounded support.
2. In discrete action spaces with sparse high rewards, standard PPO often becomes stuck at suboptimal actions.
3. The policy can be sensitive to initialization when locally optimal actions lie close to the initialization.

Discretizing the action space or using a Beta distribution helps avoid failure modes 1 and 3 associated with a Gaussian policy. Using KL regularization (with the same motivation as in TRPO) as an alternative surrogate objective helps address failure modes 1 and 2.

PPG

[paper|code]

Sharing parameters between the policy and value networks offers clear benefits and notable drawbacks. On the positive side, both the policy and the value function can leverage shared learned representations. However, this coupling can also introduce interference between competing objectives, and it typically requires training both networks on the same data at the same time.

Phasic Policy Gradient (PPG; Cobbe, et al 2020) adapts the standard on-policy actor-critic policy gradient method, specifically PPO, by separating optimization into distinct phases for the policy and the value function. Training alternates between two phases:

1. The policy phase: update the policy network by optimizing the PPO objective $L^\text{CLIP} (\theta)$;
2. The auxiliary phase: optimize an auxiliary objective together with a behavioral cloning loss. In the paper, the auxiliary objective is solely the value function error, but the formulation is more general and can incorporate other auxiliary loss terms.

$ \begin{aligned} L^\text{joint} &= L^\text{aux} + \beta_\text{clone} \cdot \mathbb{E}_t[\text{KL}[\pi_{\theta_\text{old}}(\cdot\mid s_t), \pi_\theta(\cdot\mid s_t)]] \\ L^\text{aux} &= L^\text{value} = \mathbb{E}_t \big[\frac{1}{2}\big( V_w(s_t) - \hat{V}_t^\text{targ} \big)^2\big] \end{aligned} $

Here, $\beta_\text{clone}$ is a hyperparameter that controls how strongly we prevent the policy from drifting too far from its original behavior while optimizing auxiliary objectives.

where:

• $N_\pi$ is the number of policy update iterations performed during the policy phase. Note that the policy phase runs multiple update iterations per auxiliary phase.
• $E_\pi$ and $E_V$ determine sample reuse (that is, the number of training epochs over data in the replay buffer) for the policy and value functions, respectively. Because this occurs within the policy phase, $E_V$ influences learning of the true value function, not the auxiliary value function.
• $E_\text{aux}$ specifies sample reuse in the auxiliary phase. In PPG, value function optimization can tolerate substantially higher sample reuse. For example, in the paper’s experiments, $E_\text{aux} = 6$ while $E_\pi = E_V = 1$.

Compared to PPO, PPG yields a substantial improvement in sample efficiency.

ACER

[paper|code]

ACER, short for actor-critic with experience replay (Wang, et al., 2017), is an off-policy actor-critic method that incorporates experience replay. This design substantially improves sample efficiency and reduces correlation in the training data. A3C provides the foundation for ACER but is on-policy, whereas ACER can be viewed as A3C’s off-policy counterpart. The primary challenge in turning A3C into an off-policy method is maintaining the stability of the off-policy estimator. ACER addresses this challenge through three key design choices:

• Retrace Q-value estimation
• Truncation of importance weights with bias correction
• An efficient TRPO-style constraint

Retrace Q-value Estimation

Retrace is an off-policy, return-based method for Q-value estimation. It provides a strong convergence guarantee for any target and behavior policy pair $(\pi, \beta)$, while also achieving good data efficiency.

Recall the TD learning procedure for prediction:

1. Compute the TD error: $\delta_t = R_t + \gamma \mathbb{E}_{a \sim \pi} Q(S_{t+1}, a) - Q(S_t, A_t)$; the term $r_t + \gamma \mathbb{E}_{a \sim \pi} Q(s_{t+1}, a) $ is referred to as the “TD target.” The expectation $\mathbb{E}_{a \sim \pi}$ is used because, for future steps, the best estimate available is the return obtained by following the current policy $\pi$.
2. Update the value estimate by correcting in the direction of the target: $Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \delta_t$. Equivalently, the incremental Q update is proportional to the TD error: $\Delta Q(S_t, A_t) = \alpha \delta_t$.

If the rollout is off-policy, importance sampling must be applied to the Q update:

$ \Delta Q^\text{imp}(S_t, A_t) = \gamma^t \prod_{1 \leq \tau \leq t} \frac{\pi(A_\tau \vert S_\tau)}{\beta(A_\tau \vert S_\tau)} \delta_t $

The product of importance weights can be intimidating because it can lead to extremely high variance and even divergence. Retrace modifies $\Delta Q$ by truncating the importance weights to be no larger than a constant $c$:

$ \Delta Q^\text{ret}(S_t, A_t) = \gamma^t \prod_{1 \leq \tau \leq t} \min(c, \frac{\pi(A_\tau \vert S_\tau)}{\beta(A_\tau \vert S_\tau)}) \delta_t $

In ACER, the critic is trained using $Q^\text{ret}$ as the target by minimizing the L2 error: $(Q^\text{ret}(s, a) - Q(s, a))^2$.

Importance weights truncation

To reduce the high variance of the policy gradient $\hat{g}$, ACER clips the importance weights at a constant c and adds a correction term. The notation $\hat{g}_t^\text{acer}$ refers to the ACER policy gradient at time t.

$ \begin{aligned} \hat{g}_t^\text{acer} = & \omega_t \big( Q^\text{ret}(S_t, A_t) - V_{\theta_v}(S_t) \big) \nabla_\theta \ln \pi_\theta(A_t \vert S_t) & \scriptstyle{\text{; Let }\omega_t=\frac{\pi(A_t \vert S_t)}{\beta(A_t \vert S_t)}} \\ = & \color{blue}{\min(c, \omega_t) \big( Q^\text{ret}(S_t, A_t) - V_w(S_t) \big) \nabla_\theta \ln \pi_\theta(A_t \vert S_t)} \\ & + \color{red}{\mathbb{E}_{a \sim \pi} \big[ \max(0, \frac{\omega_t(a) - c}{\omega_t(a)}) \big( Q_w(S_t, a) - V_w(S_t) \big) \nabla_\theta \ln \pi_\theta(a \vert S_t) \big]} & \scriptstyle{\text{; Let }\omega_t (a) =\frac{\pi(a \vert S_t)}{\beta(a \vert S_t)}} \end{aligned} $

Here, $Q_w(.)$ and $V_w(.)$ are value functions predicted by the critic with parameters w. The first (blue) term includes the clipped importance weight. Clipping reduces variance, and subtracting the state value function $V_w(.)$ serves as a baseline. The second (red) term provides a correction that restores unbiasedness.

Efficient TRPO

ACER also incorporates the central idea of TRPO, with an adjustment for computational efficiency. Instead of directly measuring the KL divergence between the policy before and after a single update, ACER maintains a running average of past policies and constrains the updated policy to remain close to that average.

The ACER paper is quite dense and includes many equations. With prior familiarity with TD learning, Q-learning, importance sampling, and TRPO, the paper should be somewhat easier to follow :)

ACTKR

[paper|code]

ACKTR (actor-critic using Kronecker-factored trust region) (Yuhuai Wu, et al., 2017) proposes using Kronecker-factored approximate curvature (K-FAC) to update gradients for both the actor and the critic. K-FAC improves the computation of the natural gradient, which differs substantially from the standard gradient. For an accessible explanation, see Here. A concise summary is:

“we first consider all combinations of parameters that result in a new network a constant KL divergence away from the old network. This constant value can be viewed as the step size or learning rate. Out of all these possible combinations, we choose the one that minimizes our loss function.”

ACTKR is included here primarily for completeness. I will not go into details, because it requires substantial theoretical background in natural gradients and optimization. If you are interested, review the following papers and posts before reading the ACKTR paper:

• Amari. Natural Gradient Works Efficiently in Learning. 1998
• Kakade. A Natural Policy Gradient. 2002
• A intuitive explanation of natural gradient descent
• Wiki: Kronecker product
• Martens & Grosse. Optimizing neural networks with kronecker-factored approximate curvature. 2015.

The following is a high-level summary from the K-FAC paper:

“This approximation is built in two stages. In the first, the rows and columns of the Fisher are divided into groups, each of which corresponds to all the weights in a given layer, and this gives rise to a block-partitioning of the matrix. These blocks are then approximated as Kronecker products between much smaller matrices, which we show is equivalent to making certain approximating assumptions regarding the statistics of the network’s gradients.

In the second stage, this matrix is further approximated as having an inverse which is either block-diagonal or block-tridiagonal. We justify this approximation through a careful examination of the relationships between inverse covariances, tree-structured graphical models, and linear regression. Notably, this justification doesn’t apply to the Fisher itself, and our experiments confirm that while the inverse Fisher does indeed possess this structure (approximately), the Fisher itself does not.”

SAC

[paper|code]

Soft Actor-Critic (SAC) (Haarnoja et al. 2018) integrates a policy entropy term into the reward signal to promote exploration. The goal is to learn a policy that remains as random as possible while still achieving the task. SAC is an off-policy actor-critic method within the maximum entropy reinforcement learning framework. A predecessor is Soft Q-learning.

SAC has three core components:

• An actor-critic architecture with separate policy and value networks
• An off-policy formulation that reuses previously collected data for improved efficiency
• Entropy maximization for stability and exploration

The policy is trained to maximize both expected return and entropy:

$ J(\theta) = \sum_{t=1}^T \mathbb{E}_{(s_t, a_t) \sim \rho_{\pi_\theta}} [r(s_t, a_t) + \alpha \mathcal{H}(\pi_\theta(.\vert s_t))] $

where $\mathcal{H}(.)$ measures entropy and $\alpha$ controls the weight of the entropy term (the temperature parameter). Entropy maximization tends to produce policies that (1) explore more effectively and (2) represent multiple modes of near-optimal behavior (for example, when several actions are similarly good, the policy should assign them similar probability).

More concretely, SAC learns three functions:

• A policy parameterized by $\theta$, $\pi_\theta$.
• A soft Q-value function parameterized by $w$, $Q_w$.
• A soft state value function parameterized by $\psi$, $V_\psi$; in theory, $V$ can be inferred given $Q$ and $\pi$, but in practice it helps stabilize training.

The soft Q-value and soft state value are defined as:

$ \begin{aligned} Q(s_t, a_t) &= r(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim \rho_{\pi}(s)} [V(s_{t+1})] & \text{; according to Bellman equation.}\\ \text{where }V(s_t) &= \mathbb{E}_{a_t \sim \pi} [Q(s_t, a_t) - \alpha \log \pi(a_t \vert s_t)] & \text{; soft state value function.} \end{aligned} $

$ \text{Thus, } Q(s_t, a_t) = r(s_t, a_t) + \gamma \mathbb{E}_{(s_{t+1}, a_{t+1}) \sim \rho_{\pi}} [Q(s_{t+1}, a_{t+1}) - \alpha \log \pi(a_{t+1} \vert s_{t+1})] $

$\rho_\pi(s)$ and $\rho_\pi(s, a)$ denote the state and state-action marginals of the state distribution induced by the policy $\pi(a \vert s)$; see the analogous definitions in the DPG section.

The soft state value function is trained by minimizing a mean squared error:

$ \begin{aligned} J_V(\psi) &= \mathbb{E}_{s_t \sim \mathcal{D}} [\frac{1}{2} \big(V_\psi(s_t) - \mathbb{E}[Q_w(s_t, a_t) - \log \pi_\theta(a_t \vert s_t)] \big)^2] \\ \text{with gradient: }\nabla_\psi J_V(\psi) &= \nabla_\psi V_\psi(s_t)\big( V_\psi(s_t) - Q_w(s_t, a_t) + \log \pi_\theta (a_t \vert s_t) \big) \end{aligned} $

where $\mathcal{D}$ is the replay buffer.

The soft Q function is trained by minimizing the soft Bellman residual:

$ \begin{aligned} J_Q(w) &= \mathbb{E}_{(s_t, a_t) \sim \mathcal{D}} [\frac{1}{2}\big( Q_w(s_t, a_t) - (r(s_t, a_t) + \gamma \mathbb{E}_{s_{t+1} \sim \rho_\pi(s)}[V_{\bar{\psi}}(s_{t+1})]) \big)^2] \\ \text{with gradient: } \nabla_w J_Q(w) &= \nabla_w Q_w(s_t, a_t) \big( Q_w(s_t, a_t) - r(s_t, a_t) - \gamma V_{\bar{\psi}}(s_{t+1})\big) \end{aligned} $

where $\bar{\psi}$ is the target value function, updated as an exponential moving average (or updated periodically via a “hard” update), similar to how the target Q-network is handled in DQN to stabilize training.

SAC updates the policy by minimizing the KL-divergence:

$ \begin{aligned} \pi_\text{new} &= \arg\min_{\pi' \in \Pi} D_\text{KL} \Big( \pi'(.\vert s_t) \| \frac{\exp(Q^{\pi_\text{old}}(s_t, .))}{Z^{\pi_\text{old}}(s_t)} \Big) \\[6pt] &= \arg\min_{\pi' \in \Pi} D_\text{KL} \big( \pi'(.\vert s_t) \| \exp(Q^{\pi_\text{old}}(s_t, .) - \log Z^{\pi_\text{old}}(s_t)) \big) \\[6pt] \text{objective for update: } J_\pi(\theta) &= \nabla_\theta D_\text{KL} \big( \pi_\theta(. \vert s_t) \| \exp(Q_w(s_t, .) - \log Z_w(s_t)) \big) \\[6pt] &= \mathbb{E}_{a_t\sim\pi} \Big[ - \log \big( \frac{\exp(Q_w(s_t, a_t) - \log Z_w(s_t))}{\pi_\theta(a_t \vert s_t)} \big) \Big] \\[6pt] &= \mathbb{E}_{a_t\sim\pi} [ \log \pi_\theta(a_t \vert s_t) - Q_w(s_t, a_t) + \log Z_w(s_t) ] \end{aligned} $

where $\Pi$ is the set of tractable policy families used to model the policy. For example, $\Pi$ may be a family of Gaussian mixture distributions, which is expensive but expressive while remaining tractable. $Z^{\pi_\text{old}}(s_t)$ is the partition function that normalizes the distribution. It is typically intractable, but it does not affect the gradient. The method for minimizing $J_\pi(\theta)$ depends on the chosen $\Pi$.

This update guarantees that $Q^{\pi_\text{new}}(s_t, a_t) \geq Q^{\pi_\text{old}}(s_t, a_t)$. For the proof of this lemma, see Appendix B.2 in the original paper.

Once the objectives and gradients for the soft state-action value, the soft state value, and the policy network are specified, the soft actor-critic procedure is straightforward:

SAC with Automatically Adjusted Temperature

[paper|code]

SAC is sensitive to the temperature parameter. Unfortunately, selecting or tuning temperature is difficult because entropy can change unpredictably across tasks and during training, particularly as the policy improves. An extension to SAC casts the problem as constrained optimization: while maximizing expected return, the policy must satisfy a minimum entropy constraint:

$ \max_{\pi_0, \dots, \pi_T} \mathbb{E} \Big[ \sum_{t=0}^T r(s_t, a_t)\Big] \text{s.t. } \forall t\text{, } \mathcal{H}(\pi_t) \geq \mathcal{H}_0 $

where $\mathcal{H}_0$ is a predefined minimum entropy threshold for the policy.

The expected return $\mathbb{E} \Big[ \sum_{t=0}^T r(s_t, a_t)\Big]$ can be written as the sum of rewards across all time steps. Because the policy $\pi_t$ at time t does not affect the policy at the earlier time step $\pi_{t-1}$, we can maximize the return backward in time by optimizing step by step, which is essentially DP.

$ \underbrace{\max_{\pi_0} \Big( \mathbb{E}[r(s_0, a_0)]+ \underbrace{\max_{\pi_1} \Big(\mathbb{E}[...] + \underbrace{\max_{\pi_T} \mathbb{E}[r(s_T, a_T)]}_\text{1st maximization} \Big)}_\text{second but last maximization} \Big)}_\text{last maximization} $

where we consider $\gamma=1$.

Accordingly, optimization begins at the final timestep $T$:

$ \text{maximize } \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) ] \text{ s.t. } \mathcal{H}(\pi_T) - \mathcal{H}_0 \geq 0 $

First, define the following functions:

$ \begin{aligned} h(\pi_T) &= \mathcal{H}(\pi_T) - \mathcal{H}_0 = \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [-\log \pi_T(a_T\vert s_T)] - \mathcal{H}_0\\ f(\pi_T) &= \begin{cases} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) ], & \text{if }h(\pi_T) \geq 0 \\ -\infty, & \text{otherwise} \end{cases} \end{aligned} $

The optimization then becomes:

$ \text{maximize } f(\pi_T) \text{ s.t. } h(\pi_T) \geq 0 $

To solve a maximization problem with an inequality constraint, we can form a Lagrangian expression using a Lagrange multiplier (also called a “dual variable”) $\alpha_T$:

$ L(\pi_T, \alpha_T) = f(\pi_T) + \alpha_T h(\pi_T) $

Consider the case in which we minimize $L(\pi_T, \alpha_T)$ with respect to $\alpha_T$ for a fixed value $\pi_T$:

• If the constraint is satisfied ($h(\pi_T) \geq 0$), then the best we can do is set $\alpha_T=0$, since we cannot control the value of $f(\pi_T)$. Therefore, $L(\pi_T, 0) = f(\pi_T)$.
• If the constraint is violated ($h(\pi_T) < 0$), then we can achieve $L(\pi_T, \alpha_T) \to -\infty$ by taking $\alpha_T \to \infty$. Therefore, $L(\pi_T, \infty) = -\infty = f(\pi_T)$.

In either case, we obtain:

$ f(\pi_T) = \min_{\alpha_T \geq 0} L(\pi_T, \alpha_T) $

Simultaneously, we want to maximize $f(\pi_T)$:

$ \max_{\pi_T} f(\pi_T) = \min_{\alpha_T \geq 0} \max_{\pi_T} L(\pi_T, \alpha_T) $

Therefore, to maximize $f(\pi_T)$, the associated dual problem is:

$ \begin{aligned} \max_{\pi_T} \mathbb{E}[ r(s_T, a_T) ] &= \max_{\pi_T} f(\pi_T) \\ &= \min_{\alpha_T \geq 0} \max_{\pi_T} L(\pi_T, \alpha_T) \\ &= \min_{\alpha_T \geq 0} \max_{\pi_T} f(\pi_T) + \alpha_T h(\pi_T) \\ &= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) ] + \alpha_T ( \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [-\log \pi_T(a_T\vert s_T)] - \mathcal{H}_0) \\ &= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) - \alpha_T \log \pi_T(a_T\vert s_T)] - \alpha_T \mathcal{H}_0 \\ &= \min_{\alpha_T \geq 0} \max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) + \alpha_T \mathcal{H}(\pi_T) - \alpha_T \mathcal{H}_0 ] \end{aligned} $

Note that to ensure $\max_{\pi_T} f(\pi_T)$ is properly maximized and does not become $-\infty$, the constraint must be satisfied.

We can iteratively compute the optimal $\pi_T$ and $\alpha_T$. Given the current $\alpha_T$, first compute the best policy $\pi_T^{*}$ that maximizes $L(\pi_T^{*}, \alpha_T)$. Next, plug in $\pi_T^{*}$ and compute $\alpha_T^{*}$ that minimizes $L(\pi_T^{*}, \alpha_T)$. If we parameterize the policy and the temperature with separate neural networks, this iterative procedure aligns naturally with standard parameter update routines during training.

$ \begin{aligned} \pi^{*}_T &= \arg\max_{\pi_T} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi}} [ r(s_T, a_T) + \alpha_T \mathcal{H}(\pi_T) - \alpha_T \mathcal{H}_0 ] \\ \color{blue}{\alpha^{*}_T} &\color{blue}{=} \color{blue}{\arg\min_{\alpha_T \geq 0} \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi^{*}}} [\alpha_T \mathcal{H}(\pi^{*}_T) - \alpha_T \mathcal{H}_0 ]} \end{aligned} $

$ \text{Thus, }\max_{\pi_T} \mathbb{E} [ r(s_T, a_T) ] = \mathbb{E}_{(s_T, a_T) \sim \rho_{\pi^{*}}} [ r(s_T, a_T) + \alpha^{*}_T \mathcal{H}(\pi^{*}_T) - \alpha^{*}_T \mathcal{H}_0 ] $

Now return to the soft Q-value function:

$ \begin{aligned} Q_{T-1}(s_{T-1}, a_{T-1}) &= r(s_{T-1}, a_{T-1}) + \mathbb{E} [Q(s_T, a_T) - \alpha_T \log \pi(a_T \vert s_T)] \\ &= r(s_{T-1}, a_{T-1}) + \mathbb{E} [r(s_T, a_T)] + \alpha_T \mathcal{H}(\pi_T) \\ Q_{T-1}^{*}(s_{T-1}, a_{T-1}) &= r(s_{T-1}, a_{T-1}) + \max_{\pi_T} \mathbb{E} [r(s_T, a_T)] + \alpha_T \mathcal{H}(\pi^{*}_T) & \text{; plug in the optimal }\pi_T^{*} \end{aligned} $

Taking one more step backward in time to timestep $T-1$, the expected return becomes:

$ \begin{aligned} &\max_{\pi_{T-1}}\Big(\mathbb{E}[r(s_{T-1}, a_{T-1})] + \max_{\pi_T} \mathbb{E}[r(s_T, a_T] \Big) \\ &= \max_{\pi_{T-1}} \Big( Q^{*}_{T-1}(s_{T-1}, a_{T-1}) - \alpha^{*}_T \mathcal{H}(\pi^{*}_T) \Big) & \text{; should s.t. } \mathcal{H}(\pi_{T-1}) - \mathcal{H}_0 \geq 0 \\ &= \min_{\alpha_{T-1} \geq 0} \max_{\pi_{T-1}} \Big( Q^{*}_{T-1}(s_{T-1}, a_{T-1}) - \alpha^{*}_T \mathcal{H}(\pi^{*}_T) + \alpha_{T-1} \big( \mathcal{H}(\pi_{T-1}) - \mathcal{H}_0 \big) \Big) & \text{; dual problem w/ Lagrangian.} \\ &= \min_{\alpha_{T-1} \geq 0} \max_{\pi_{T-1}} \Big( Q^{*}_{T-1}(s_{T-1}, a_{T-1}) + \alpha_{T-1} \mathcal{H}(\pi_{T-1}) - \alpha_{T-1}\mathcal{H}_0 \Big) - \alpha^{*}_T \mathcal{H}(\pi^{*}_T) \end{aligned} $

Similarly to the previous step:

$ \begin{aligned} \pi^{*}_{T-1} &= \arg\max_{\pi_{T-1}} \mathbb{E}_{(s_{T-1}, a_{T-1}) \sim \rho_\pi} [Q^{*}_{T-1}(s_{T-1}, a_{T-1}) + \alpha_{T-1} \mathcal{H}(\pi_{T-1}) - \alpha_{T-1} \mathcal{H}_0 ] \\ \color{green}{\alpha^{*}_{T-1}} &\color{green}{=} \color{green}{\arg\min_{\alpha_{T-1} \geq 0} \mathbb{E}_{(s_{T-1}, a_{T-1}) \sim \rho_{\pi^{*}}} [ \alpha_{T-1} \mathcal{H}(\pi^{*}_{T-1}) - \alpha_{T-1}\mathcal{H}_0 ]} \end{aligned} $

The update equation for $\alpha_{T-1}$ in green has the same form as the update equation for $\alpha_{T-1}$ in blue above. Repeating this procedure yields an optimal temperature at each step by minimizing the same objective:

$ J(\alpha) = \mathbb{E}_{a_t \sim \pi_t} [-\alpha \log \pi_t(a_t \mid s_t) - \alpha \mathcal{H}_0] $

The final algorithm matches SAC, except that it explicitly learns $\alpha$ by optimizing the objective $J(\alpha)$ (see Fig. 7):

TD3

[paper|code]

Q-learning is well known to suffer from overestimation in the value function. Such overestimation can compound across training iterations and degrade the learned policy. This issue directly motivated Double Q-learning and Double DQN, which decouple action selection from Q-value estimation by using two value networks.

Twin Delayed Deep Deterministic (TD3; Fujimoto et al., 2018) introduces several modifications to DDPG to mitigate Q-function overestimation:

(1) Clipped Double Q-learning: In Double Q-learning, action selection and Q-value estimation are handled by two separate networks. In the DDPG setting, given two deterministic actors $(\mu_{\theta_1}, \mu_{\theta_2})$ with corresponding critics $(Q_{w_1}, Q_{w_2})$, the Double Q-learning Bellman targets are:

$ \begin{aligned} y_1 &= r + \gamma Q_{w_2}(s', \mu_{\theta_1}(s'))\\ y_2 &= r + \gamma Q_{w_1}(s', \mu_{\theta_2}(s')) \end{aligned} $

However, because the policy changes slowly, the two networks may become too similar to behave independently. Clipped Double Q-learning instead takes the smaller of the two estimates, favoring underestimation bias, which is more difficult to amplify through training:

$ \begin{aligned} y_1 &= r + \gamma \min_{i=1,2}Q_{w_i}(s', \mu_{\theta_1}(s'))\\ y_2 &= r + \gamma \min_{i=1,2} Q_{w_i}(s', \mu_{\theta_2}(s')) \end{aligned} $

(2) Delayed update of Target and Policy Networks: In actor-critic methods, policy and value updates are tightly coupled. Value estimates can diverge via overestimation when the policy is poor, and the policy can degrade if the value estimate is inaccurate.

To reduce variance, TD3 updates the policy less frequently than the Q-function. The policy network is held fixed while the value function is updated several times, until the value error becomes sufficiently small. This mirrors how a periodically updated target network serves as a stable training target in DQN.

(3) Target Policy Smoothing: Because deterministic policies can overfit to narrow peaks in the value function, TD3 adds a smoothing regularization to the value target by injecting small, clipped random noise into the selected action and averaging over mini-batches:

$ \begin{aligned} y &= r + \gamma Q_w (s', \mu_{\theta}(s') + \epsilon) & \\ \epsilon &\sim \text{clip}(\mathcal{N}(0, \sigma), -c, +c) & \scriptstyle{\text{ ; clipped random noises.}} \end{aligned} $

This is reminiscent of the SARSA update and enforces that similar actions should yield similar values.

The complete algorithm is:

SVPG

[paper|code for SVPG]

Stein Variational Policy Gradient (SVPG; Liu et al, 2017) applies Stein variational gradient descent (SVGD; Liu and Wang, 2016) to update the policy parameters $\theta$.

Under maximum entropy policy optimization, $\theta$ is treated as a random variable $\theta \sim q(\theta)$, and the goal is to learn the distribution $q(\theta)$. If we assume a prior describing what $q$ should look like, $q_0$, we can guide learning so that $\theta$ does not deviate too far from $q_0$ by optimizing:

$ \hat{J}(\theta) = \mathbb{E}_{\theta \sim q} [J(\theta)] - \alpha D_\text{KL}(q\|q_0) $

where $\mathbb{E}_{\theta \sim q} [R(\theta)]$ is the expected reward given $\theta \sim q(\theta)$, and $D_\text{KL}$ is the KL divergence.

If no prior information is available, we can set $q_0$ to be uniform and set $q_0(\theta)$ to a constant. Under these assumptions, the objective reduces to SAC, where entropy regularization encourages exploration:

$ \begin{aligned} \hat{J}(\theta) &= \mathbb{E}_{\theta \sim q} [J(\theta)] - \alpha D_\text{KL}(q\|q_0) \\ &= \mathbb{E}_{\theta \sim q} [J(\theta)] - \alpha \mathbb{E}_{\theta \sim q} [\log q(\theta) - \log q_0(\theta)] \\ &= \mathbb{E}_{\theta \sim q} [J(\theta)] + \alpha H(q(\theta)) \end{aligned} $

Taking the derivative of $\hat{J}(\theta) = \mathbb{E}_{\theta \sim q} [J(\theta)] - \alpha D_\text{KL}(q|q_0)$ with respect to $q$ gives:

$ \begin{aligned} \nabla_q \hat{J}(\theta) &= \nabla_q \big( \mathbb{E}_{\theta \sim q} [J(\theta)] - \alpha D_\text{KL}(q\|q_0) \big) \\ &= \nabla_q \int_\theta \big( q(\theta) J(\theta) - \alpha q(\theta)\log q(\theta) + \alpha q(\theta) \log q_0(\theta) \big) \\ &= \int_\theta \big( J(\theta) - \alpha \log q(\theta) -\alpha + \alpha \log q_0(\theta) \big) \\ &= 0 \end{aligned} $

The optimal distribution is:

$ \log q^{*}(\theta) = \frac{1}{\alpha} J(\theta) + \log q_0(\theta) - 1 \text{ thus } \underbrace{ q^{*}(\theta) }_\textrm{"posterior"} \propto \underbrace{\exp ( J(\theta) / \alpha )}_\textrm{"likelihood"} \underbrace{q_0(\theta)}_\textrm{prior} $

The temperature $\alpha$ governs the tradeoff between exploitation and exploration. When $\alpha \rightarrow 0$, $\theta$ is updated only based on the expected return $J(\theta)$. When $\alpha \rightarrow \infty$, $\theta$ always follows the prior belief.

To estimate the target posterior $q(\theta)$ via SVGD, SVPG maintains a set of particles $\{\theta_i\}_{i=1}^n$ (independently trained policy agents). Each particle is updated as:

$ \theta_i \gets \theta_i + \epsilon \phi^{*}(\theta_i) \text{ where } \phi^{*} = \max_{\phi \in \mathcal{H}} \{ - \nabla_\epsilon D_\text{KL} (q'_{[\theta + \epsilon \phi(\theta)]} \| q) \text{ s.t. } \|\phi\|_{\mathcal{H}} \leq 1\} $

where $\epsilon$ is the learning rate and $\phi^{*}$ is the unit ball of an RKHS (reproducing kernel Hilbert space) $\mathcal{H}$ of $\theta$-shaped value vectors that most effectively decrease the KL divergence between the particles and the target distribution. $q’(.)$ is the distribution of $\theta + \epsilon \phi(\theta)$.

Comparing different gradient-based update methods:

Method	Update space
Plain gradient	$\Delta \theta$ on the parameter space
Natural gradient	$\Delta \theta$ on the search distribution space
SVGD	$\Delta \theta$ on the kernel function space (edited)

One estimation of $\phi^{*}$ has the following form. A positive definite kernel $k(\vartheta, \theta)$ (for example, a Gaussian radial basis function) measures similarity between particles.

$ \begin{aligned} \phi^{*}(\theta_i) &= \mathbb{E}_{\vartheta \sim q'} [\nabla_\vartheta \log q(\vartheta) k(\vartheta, \theta_i) + \nabla_\vartheta k(\vartheta, \theta_i)]\\ &= \frac{1}{n} \sum_{j=1}^n [\color{red}{\nabla_{\theta_j} \log q(\theta_j) k(\theta_j, \theta_i)} + \color{green}{\nabla_{\theta_j} k(\theta_j, \theta_i)}] & \scriptstyle{\text{;approximate }q'\text{ with current particle values}} \end{aligned} $

• The first term in red encourages $\theta_i$ to move toward high-probability regions of $q$ shared across similar particles, that is, to be similar to other particles.
• The second term in green repels particles from one another, thereby diversifying the policies, that is, to be dissimilar to other particles.

In practice, the temperature $\alpha$ commonly follows an annealing schedule, so training emphasizes exploration early and shifts toward exploitation later.

IMPALA

[paper|code]

To scale reinforcement learning training to very high throughput, the IMPALA framework (“Importance Weighted Actor-Learner Architecture”) decouples acting from learning within a standard actor-critic setup, and it learns from all collected trajectories using V-trace off-policy correction.

Multiple actors generate experience in parallel, while a learner optimizes the policy and value parameters using the aggregated experience. Actors periodically refresh their parameters by pulling the latest policy from the learner. Because acting and learning are separated, many actor machines can be added to generate far more trajectories per unit time. Since the behavior policy and the training policy are not perfectly synchronized, a gap emerges between them, which necessitates off-policy correction.

Let the value function $V_\theta$ be parameterized by $\theta$, and the policy $\pi_\phi$ be parameterized by $\phi$. The trajectories stored in the replay buffer are collected under a slightly older policy $\mu$.

At training time $t$, given $(s_t, a_t, s_{t+1}, r_t)$, the value parameters $\theta$ are learned by minimizing an L2 loss between the current value and a V-trace target. The $n$-step V-trace target is:

$ \begin{aligned} v_t &= V_\theta(s_t) + \sum_{i=t}^{t+n-1} \gamma^{i-t} \big(\prod_{j=t}^{i-1} c_j\big) \color{red}{\delta_i V} \\ &= V_\theta(s_t) + \sum_{i=t}^{t+n-1} \gamma^{i-t} \big(\prod_{j=t}^{i-1} c_j\big) \color{red}{\rho_i (r_i + \gamma V_\theta(s_{i+1}) - V_\theta(s_i))} \end{aligned} $

where the red portion $\delta_i V$ is the temporal difference for $V$. $\rho_i = \min\big(\bar{\rho}, \frac{\pi(a_i \vert s_i)}{\mu(a_i \vert s_i)}\big)$ and $c_j = \min\big(\bar{c}, \frac{\pi(a_j \vert s_j)}{\mu(a_j \vert s_j)}\big)$ are truncated importance sampling (IS) weights. The product $c_t, \dots, c_{i-1}$ measures how much the temporal difference $\delta_i V$ observed at time $i$ affects the value-function update at the earlier time $t$. In the on-policy setting, $\rho_i=1$ and $c_j=1$ (assuming $\bar{c} \geq 1$), so the V-trace target reduces to the on-policy $n$-step Bellman target.

$\bar{\rho}$ and $\bar{c}$ are truncation constants, with $\bar{\rho} \geq \bar{c}$. $\bar{\rho}$ affects the fixed point of the value function to which we converge, while $\bar{c}$ affects the convergence speed. When $\bar{\rho} =\infty$ (no truncation), we converge to the value function of the target policy $V^\pi$. When $\bar{\rho}$ approaches 0, we evaluate the value function of the behavior policy $V^\mu$. For intermediate values, we evaluate a policy between $\pi$ and $\mu$.

The value function parameters are updated in the direction:

$ \Delta\theta = (v_t - V_\theta(s_t))\nabla_\theta V_\theta(s_t) $

The policy parameters $\phi$ are updated using a policy gradient:

$ \begin{aligned} \Delta \phi &= \rho_t \nabla_\phi \log \pi_\phi(a_t \vert s_t) \big(r_t + \gamma v_{t+1} - V_\theta(s_t)\big) + \nabla_\phi H(\pi_\phi)\\ &= \rho_t \nabla_\phi \log \pi_\phi(a_t \vert s_t) \big(r_t + \gamma v_{t+1} - V_\theta(s_t)\big) - \nabla_\phi \sum_a \pi_\phi(a\vert s_t)\log \pi_\phi(a\vert s_t) \end{aligned} $

where $r_t + \gamma v_{t+1}$ is an estimated Q value with a state-dependent baseline $V_\theta(s_t)$ subtracted. $H(\pi_\phi)$ is an entropy bonus that encourages exploration.

In the experiments, IMPALA trains a single agent on multiple tasks, using two architectures: a shallow model (left) and a deep residual model (right).

Quick Summary

After reviewing the algorithms above, the following building blocks and principles appear repeatedly:

• Reduce variance while keeping bias unchanged to stabilize learning.
• Use off-policy learning to improve exploration and to reuse samples more efficiently.
• Use experience replay (sampling training data from a replay memory buffer).
• Use a target network that is periodically frozen or updated more slowly than the actively trained policy network.
• Use batch normalization.
• Use entropy-regularized reward.
• Allow the critic and actor to share lower-layer parameters, with two output heads for the policy and value functions.
• In some cases, learn with deterministic policies rather than stochastic ones.
• Constrain the divergence between policy updates.
• Adopt new optimization methods (such as K-FAC).
• Use entropy maximization to encourage exploration.
• Avoid overestimating the value function.
• Carefully consider whether the policy and value networks should share parameters.
• TBA more.

---

Cited as:

@article{weng2018PG,
  title   = "Policy Gradient Algorithms",
  author  = "Weng, Lilian",
  journal = "lilianweng.github.io",
  year    = "2018",
  url     = "https://lilianweng.github.io/posts/2018-04-08-policy-gradient/"
}

References

[1] jeremykun.com Markov Chain Monte Carlo Without all the Bullshit

[2] Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction; 2nd Edition. 2017.

[3] John Schulman, et al. “High-dimensional continuous control using generalized advantage estimation.” ICLR 2016.

[4] Thomas Degris, Martha White, and Richard S. Sutton. “Off-policy actor-critic.” ICML 2012.

[5] timvieira.github.io Importance sampling

[6] Mnih, Volodymyr, et al. “Asynchronous methods for deep reinforcement learning.” ICML. 2016.

[7] David Silver, et al. “Deterministic policy gradient algorithms.” ICML. 2014.

[8] Timothy P. Lillicrap, et al. “Continuous control with deep reinforcement learning.” arXiv preprint arXiv:1509.02971 (2015).

[9] Ryan Lowe, et al. “Multi-agent actor-critic for mixed cooperative-competitive environments.” NIPS. 2017.

[10] John Schulman, et al. “Trust region policy optimization.” ICML. 2015.

[11] Ziyu Wang, et al. “Sample efficient actor-critic with experience replay.” ICLR 2017.

[12] Rémi Munos, Tom Stepleton, Anna Harutyunyan, and Marc Bellemare. “Safe and efficient off-policy reinforcement learning” NIPS. 2016.

[13] Yuhuai Wu, et al. “Scalable trust-region method for deep reinforcement learning using Kronecker-factored approximation.” NIPS. 2017.

[14] kvfrans.com A intuitive explanation of natural gradient descent

[15] Sham Kakade. “A Natural Policy Gradient.”. NIPS. 2002.

[16] “Going Deeper Into Reinforcement Learning: Fundamentals of Policy Gradients.” - Seita’s Place, Mar 2017.

[17] “Notes on the Generalized Advantage Estimation Paper.” - Seita’s Place, Apr, 2017.

[18] Gabriel Barth-Maron, et al. “Distributed Distributional Deterministic Policy Gradients.” ICLR 2018 poster.

[19] Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. “Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor.” arXiv preprint arXiv:1801.01290 (2018).

[20] Scott Fujimoto, Herke van Hoof, and Dave Meger. “Addressing Function Approximation Error in Actor-Critic Methods.” arXiv preprint arXiv:1802.09477 (2018).

[21] Tuomas Haarnoja, et al. “Soft Actor-Critic Algorithms and Applications.” arXiv preprint arXiv:1812.05905 (2018).

[22] David Knowles. “Lagrangian Duality for Dummies” Nov 13, 2010.

[23] Yang Liu, et al. “Stein variational policy gradient.” arXiv preprint arXiv:1704.02399 (2017).

[24] Qiang Liu and Dilin Wang. “Stein variational gradient descent: A general purpose bayesian inference algorithm.” NIPS. 2016.

[25] Lasse Espeholt, et al. “IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures” arXiv preprint 1802.01561 (2018).

[26] Karl Cobbe, et al. “Phasic Policy Gradient.” arXiv preprint arXiv:2009.04416 (2020).

[27] Chloe Ching-Yun Hsu, et al. “Revisiting Design Choices in Proximal Policy Optimization.” arXiv preprint arXiv:2009.10897 (2020).