Abstract: In this post, we are going to look deep into policy gradient, why it works, and many new policy gradient algorithms proposed in recent years: vanilla policy gradient, actor-critic, off-policy actor-critic, A3C, A2C, DPG, DDPG, D4PG, MADDPG, TRPO, PPO, ACER, ACTKR, SAC and TD3.

[Updated on 2018-06-30: Two new policy gradient methods, Soft AC and D4PG.]
[Updated on 2018-09-30: an new policy gradient method, TD3.]

Policy gradient is an approach to solve reinforcement learning problems. If you haven’t looked into the field of reinforcement learning, please first read the section “A (Long) Peek into Reinforcement Learning » Key Concepts” for the problem definition and key concepts.

### Notations

Symbol Meaning
s∈Ss∈S States.
a∈Aa∈A Actions.
r∈Rr∈R Rewards.
St,At,RtSt,At,Rt State, action, and reward at time step t of one trajectory. I may occasionally use st,at,rtst,at,rt as well.
γγ Discount factor; penalty to uncertainty of future rewards; 0<γ≤10<γ≤1.
GtGt Return; or discounted future reward; Gt=∑∞k=0γkRt+k+1Gt=∑k=0∞γkRt+k+1.
P(s′,r|s,a)P(s′,r|s,a) Transition probability of getting to the next state s’ from the current state s with action a and reward r.
π(a|s)π(a|s) Stochastic policy (agent behavior strategy); πθ(.)πθ(.) is a policy parameterized by θ.
μ(s)μ(s) Deterministic policy; we can also label this as π(s)π(s), but using a different letter gives better distinction so that we can easily tell when the policy is stochastic or deterministic without further explanation. Either ππ or μμ is what a reinforcement learning algorithm aims to learn.
V(s)V(s) State-value function measures the expected return of state s; Vw(.)Vw(.) is a value function parameterized by w.
Vπ(s)Vπ(s) The value of state s when we follow a policy π; Vπ(s)=Ea∼π[Gt|St=s]Vπ(s)=Ea∼π[Gt|St=s].
Q(s,a)Q(s,a) Action-value function is similar to V(s)V(s), but it assesses the expected return of a pair of state and action (s, a); Qw(.)Qw(.) is a action value function parameterized by w.
Qπ(s,a)Qπ(s,a) Similar to Vπ(.)Vπ(.), the value of (state, action) pair when we follow a policy π; Qπ(s,a)=Ea∼π[Gt|St=s,At=a]Qπ(s,a)=Ea∼π[Gt|St=s,At=a].
A(s,a)A(s,a) Advantage function, A(s,a)=Q(s,a)−V(s)A(s,a)=Q(s,a)−V(s); it can be considered as another version of Q-value with lower variance by taking the state-value off as the baseline.

The goal of reinforcement learning is to find an optimal behavior strategy for the agent to obtain optimal rewards. The policy gradient methods target at modeling and optimizing the policy directly. The policy is usually modeled with a parameterized function respect to θ, πθ(a|s)πθ(a|s). The value of the reward (objective) function depends on this policy and then various algorithms can be applied to optimize θ for the best reward.

The reward function is defined as:

J(θ)=∑s∈Sdπ(s)Vπ(s)=∑s∈Sdπ(s)∑a∈Aπθ(a|s)Qπ(s,a)J(θ)=∑s∈Sdπ(s)Vπ(s)=∑s∈Sdπ(s)∑a∈Aπθ(a|s)Qπ(s,a)

where dπ(s)dπ(s) is the stationary distribution of Markov chain for πθπθ (on-policy state distribution under π). For simplicity, the θ parameter would be omitted for the policy πθπθ when the policy is present in the subscript of other functions; for example, dπ and Qπ should be dπθdπθ and QπθQπθ if written in full. Imagine that you can travel along the Markov chain’s states forever, and eventually, as the time progresses, the probability of you ending up with one state becomes unchanged — this is the stationary probability for πθπθ. dπ(s)=limt→∞P(st=s|s0,πθ)dπ(s)=limt→∞P(st=s|s0,πθ) is the probability that st=sst=s when starting from s0s0 and following policy πθπθ for t steps. Actually, the existence of the stationary distribution of Markov chain is one main reason for why PageRank algorithm works. If you want to read more, check this.

It is natural to expect policy-based methods are more useful in the continuous space. Because there is an infinite number of actions and (or) states to estimate the values for and hence value-based approaches are way too expensive computationally in the continuous space. For example, in generalized policy iteration, the policy improvement step argmaxa∈AQπ(s,a)arg⁡maxa∈AQπ(s,a) requires a full scan of the action space, suffering from the curse of dimensionality.

Using gradient ascent, we can move θ toward the direction suggested by the gradient ∇θJ(θ)∇θJ(θ) to find the best θ for πθπθ that produces the highest return.

Computing the gradient ∇θJ(θ)∇θJ(θ) is tricky because it depends on both the action selection (directly determined by πθπθ) and the stationary distribution of states following the target selection behavior (indirectly determined by πθπθ). Given that the environment is generally unknown, it is difficult to estimate the effect on the state distribution by a policy update.

Luckily, the policy gradient theorem comes to save the world! Woohoo! It provides a nice reformation of the derivative of the objective function to not involve the derivative of the state distribution dπ(.)dπ(.) and simplify the gradient computation ∇θJ(θ)∇θJ(θ) a lot.

∇θJ(θ)=∇θ∑s∈Sdπ(s)∑a∈AQπ(s,a)πθ(a|s)∝∑s∈Sdπ(s)∑a∈AQπ(s,a)∇θπθ(a|s)∇θJ(θ)=∇θ∑s∈Sdπ(s)∑a∈AQπ(s,a)πθ(a|s)∝∑s∈Sdπ(s)∑a∈AQπ(s,a)∇θπθ(a|s)

### Proof of Policy Gradient Theorem

This session is pretty dense, as it is the time for us to go through the proof (Sutton & Barto, 2017; Sec. 13.1) and figure out why the policy gradient theorem is correct.

=====∇θVπ(s)∇θ(∑a∈Aπθ(a|s)Qπ(s,a))∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∇θQπ(s,a))∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∇θ∑s′,rP(s′,r|s,a)(r+Vπ(s′)))∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′,rP(s′,r|s,a)∇θVπ(s′))∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′P(s′|s,a)∇θVπ(s′)); Derivative product rule.; Extend Qπ with future state value.P(s′,r|s,a) or r is not a func of θ; Because P(s′|s,a)=∑rP(s′,r|s,a)∇θVπ(s)=∇θ(∑a∈Aπθ(a|s)Qπ(s,a))=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∇θQπ(s,a)); Derivative product rule.=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∇θ∑s′,rP(s′,r|s,a)(r+Vπ(s′))); Extend Qπ with future state value.=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′,rP(s′,r|s,a)∇θVπ(s′))P(s′,r|s,a) or r is not a func of θ=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′P(s′|s,a)∇θVπ(s′)); Because P(s′|s,a)=∑rP(s′,r|s,a)

Now we have:

∇θVπ(s)=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′P(s′|s,a)∇θVπ(s′))∇θVπ(s)=∑a∈A(∇θπθ(a|s)Qπ(s,a)+πθ(a|s)∑s′P(s′|s,a)∇θVπ(s′))

This equation has a nice recursive form (see the red parts!) and the future state value function Vπ(s′)Vπ(s′) can be repeated unrolled by following the same equation.

Let’s consider the following visitation sequence and label the probability of transitioning from state s to state x with policy πθπθ after k step as ρπ(s→x,k)ρπ(s→x,k).

s−→−−−−a∼πθ(.|s)s′−→−−−−a∼πθ(.|s′)s′′−→−−−−−a∼πθ(.|s′′)…s→a∼πθ(.|s)s′→a∼πθ(.|s′)s″→a∼πθ(.|s″)…
• When k = 0: ρπ(s→s,k=0)=1ρπ(s→s,k=0)=1.
• When k = 1, we scan through all possible actions and sum up the transition probabilities to the target state: ρπ(s→s′,k=1)=∑aπθ(a|s)P(s′|s,a)ρπ(s→s′,k=1)=∑aπθ(a|s)P(s′|s,a).
• Imagine that the goal is to go from state s to x after k+1 steps while following policy πθπθ. We can first travel from s to a middle point s’ (any state can be a middle point, s′∈Ss′∈S) after k steps and then go to the final state x during the last step. In this way, we are able to update the visitation probability recursively: ρπ(s→x,k+1)=∑s′ρπ(s→s′,k)ρπ(s′→x,1)ρπ(s→x,k+1)=∑s′ρπ(s→s′,k)ρπ(s′→x,1).

Then we go back to unroll the recursive representation of ∇θVπ(s)∇θVπ(s)! Let ϕ(s)=∑a∈A∇θπθ(a|s)Qπ(s,a)ϕ(s)=∑a∈A∇θπθ(a|s)Qπ(s,a) to simplify the maths. If we keep on extending ∇θVπ(.)∇θVπ(.)infinitely, it is easy to find out that we can transition from the starting state s to any state after any number of steps in this unrolling process and by summing up all the visitation probabilities, we get ∇θVπ(s)∇θVπ(s)!

=========∇θVπ(s)ϕ(s)+∑aπθ(a|s)∑s′P(s′|s,a)∇θVπ(s′)ϕ(s)+∑s′∑aπθ(a|s)P(s′|s,a)∇θVπ(s′)ϕ(s)+∑s′ρπ(s→s′,1)∇θVπ(s′)ϕ(s)+∑s′ρπ(s→s′,1)∇θVπ(s′)ϕ(s)+∑s′ρπ(s→s′,1)[ϕ(s′)+∑s′′ρπ(s′→s′′,1)∇θVπ(s′′)]ϕ(s)+∑s′ρπ(s→s′,1)ϕ(s′)+∑s′′ρπ(s→s′′,2)∇θVπ(s′′) ; Consider s′ as the middle point for s→s′′ϕ(s)+∑s′ρπ(s→s′,1)ϕ(s′)+∑s′′ρπ(s→s′′,2)ϕ(s′′)+∑s′′′ρπ(s→s′′′,3)∇θVπ(s′′′)…; Repeatedly unrolling the part of ∇θVπ(.)∑x∈S∑k=0∞ρπ(s→x,k)ϕ(x)∇θVπ(s)=ϕ(s)+∑aπθ(a|s)∑s′P(s′|s,a)∇θVπ(s′)=ϕ(s)+∑s′∑aπθ(a|s)P(s′|s,a)∇θVπ(s′)=ϕ(s)+∑s′ρπ(s→s′,1)∇θVπ(s′)=ϕ(s)+∑s′ρπ(s→s′,1)∇θVπ(s′)=ϕ(s)+∑s′ρπ(s→s′,1)[ϕ(s′)+∑s″ρπ(s′→s″,1)∇θVπ(s″)]=ϕ(s)+∑s′ρπ(s→s′,1)ϕ(s′)+∑s″ρπ(s→s″,2)∇θVπ(s″) ; Consider s′ as the middle point for s→s″=ϕ(s)+∑s′ρπ(s→s′,1)ϕ(s′)+∑s″ρπ(s→s″,2)ϕ(s″)+∑s‴ρπ(s→s‴,3)∇θVπ(s‴)=…; Repeatedly unrolling the part of ∇θVπ(.)=∑x∈S∑k=0∞ρπ(s→x,k)ϕ(x)

The nice rewriting above allows us to exclude the derivative of Q-value function, ∇θQπ(s,a)∇θQπ(s,a). By plugging it into the objective function J(θ)J(θ), we are getting the following:

∇θJ(θ)=∇θVπ(s0)=∑s∑k=0∞ρπ(s0→s,k)ϕ(s)=∑sη(s)ϕ(s)=(∑sη(s))∑sη(s)∑sη(s)ϕ(s)∝∑sη(s)∑sη(s)ϕ(s)=∑sdπ(s)∑a∇θπθ(a|s)Qπ(s,a); Starting from a random state s0; Let η(s)=∑∞k=0ρπ(s0→s,k); Normalize η(s),s∈S to be a probability distribution.∑sη(s) is a constantdπ(s)=η(s)∑sη(s) is stationary distribution.∇θJ(θ)=∇θVπ(s0); Starting from a random state s0=∑s∑k=0∞ρπ(s0→s,k)ϕ(s); Let η(s)=∑k=0∞ρπ(s0→s,k)=∑sη(s)ϕ(s)=(∑sη(s))∑sη(s)∑sη(s)ϕ(s); Normalize η(s),s∈S to be a probability distribution.∝∑sη(s)∑sη(s)ϕ(s)∑sη(s) is a constant=∑sdπ(s)∑a∇θπθ(a|s)Qπ(s,a)dπ(s)=η(s)∑sη(s) is stationary distribution.

In the episodic case, the constant of proportionality (∑sη(s)∑sη(s)) is the average length of an episode; in the continuing case, it is 1 (Sutton & Barto, 2017; Sec. 13.2). The gradient can be further written as:

∇θJ(θ)∝∑s∈Sdπ(s)∑a∈AQπ(s,a)∇θπθ(a|s)=∑s∈Sdπ(s)∑a∈Aπθ(a|s)Qπ(s,a)∇θπθ(a|s)πθ(a|s)=Eπ[Qπ(s,a)∇θlnπθ(a|s)]; Because (lnx)′=1/x∇θJ(θ)∝∑s∈Sdπ(s)∑a∈AQπ(s,a)∇θπθ(a|s)=∑s∈Sdπ(s)∑a∈Aπθ(a|s)Qπ(s,a)∇θπθ(a|s)πθ(a|s)=Eπ[Qπ(s,a)∇θln⁡πθ(a|s)]; Because (ln⁡x)′=1/x

Where Eπ refers to Es∼dπ,a∼πθEs∼dπ,a∼πθ when both state and action distributions follow the policy πθπθ (on policy).

The policy gradient theorem lays the theoretical foundation for various policy gradient algorithms. This vanilla policy gradient update has no bias but high variance. Many following algorithms were proposed to reduce the variance while keeping the bias unchanged.

∇θJ(θ)=Eπ[Qπ(s,a)∇θlnπθ(a|s)]∇θJ(θ)=Eπ[Qπ(s,a)∇θln⁡πθ(a|s)]

Here is a nice summary of a general form of policy gradient methods borrowed from the GAE(general advantage estimation) paper (Schulman et al., 2016) and this post thoroughly discussed several components in GAE , highly recommended. Fig. 1. A general form of policy gradient methods. (Image source: Schulman et al., 2016)

Tons of policy gradient algorithms have been proposed during recent years and there is no way for me to exhaust them. I’m introducing some of them that I happened to know and read about.

### REINFORCE

REINFORCE (Monte-Carlo policy gradient) relies on an estimated return by Monte-Carlo methods using episode samples to update the policy parameter θθ. REINFORCE works because the expectation of the sample gradient is equal to the actual gradient:

∇θJ(θ)=Eπ[Qπ(s,a)∇θlnπθ(a|s)]=Eπ[Gt∇θlnπθ(At|St)]; Because Qπ(St,At)=Eπ[Gt|St,At]∇θJ(θ)=Eπ[Qπ(s,a)∇θln⁡πθ(a|s)]=Eπ[Gt∇θln⁡πθ(At|St)]; Because Qπ(St,At)=Eπ[Gt|St,At]

Therefore we are able to measure GtGt from real sample trajectories and use that to update our policy gradient. It relies on a full trajectory and that’s why it is a Monte-Carlo method.

The process is pretty straightforward:

1. Initialize the policy parameter θ at random.
2. Generate one trajectory on policy πθπθ: S1,A1,R2,S2,A2,…,STS1,A1,R2,S2,A2,…,ST.
3. For t=1, 2, … , T:

1. Estimate the the return GtGt;
2. Update policy parameters: θ←θ+αγtGt∇θlnπθ(At|St)θ←θ+αγtGt∇θln⁡πθ(At|St)

A widely used variation of REINFORCE is to subtract a baseline value from the return GtGt to reduce the variance of gradient estimation while keeping the bias unchanged (Remember we always want to do this when possible). For example, a common baseline is to subtract state-value from action-value, and if applied, we would use advantage A(s,a)=Q(s,a)−V(s)A(s,a)=Q(s,a)−V(s) in the gradient ascent update. This post nicely explained why a baseline works for reducing the variance, in addition to a set of fundamentals of policy gradient.

### Actor-Critic

Two main components in policy gradient are the policy model and the value function. It makes a lot of sense to learn the value function in addition to the policy, since knowing the value function can assist the policy update, such as by reducing gradient variance in vanilla policy gradients, and that is exactly what the Actor-Critic method does.

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

• Critic updates the value function parameters w and depending on the algorithm it could be action-value Qw(a|s)Qw(a|s) or state-value Vw(s)Vw(s).
• Actor updates the policy parameters θ for πθ(a|s)πθ(a|s), in the direction suggested by the critic.

Let’s see how it works in a simple action-value actor-critic algorithm.

1. Initialize s, θ, w at random; sample a∼πθ(a|s)a∼πθ(a|s).
2. For t=1…Tt=1…T:

1. Sample reward rt∼R(s,a)rt∼R(s,a) and next state s′∼P(s′|s,a)s′∼P(s′|s,a);
2. Then sample the next action a′∼πθ(a′|s′)a′∼πθ(a′|s′);
3. Update the policy parameters: θ←θ+αθQw(s,a)∇θlnπθ(a|s)θ←θ+αθQw(s,a)∇θln⁡πθ(a|s);
4. Compute the correction (TD error) for action-value at time t:
δt=rt+γQw(s′,a′)−Qw(s,a)δt=rt+γQw(s′,a′)−Qw(s,a)
and use it to update the parameters of action-value function:
w←w+αwδt∇wQw(s,a)w←w+αwδt∇wQw(s,a)
5. Update a←a′a←a′ and s←s′s←s′.

Two learning rates, αθαθ and αwαw, are predefined for policy and value function parameter updates respectively.

Both REINFORCE and the vanilla version of actor-critic method are on-policy: training samples are collected according to the target policy — the very same policy that we try to optimize for. Off policy methods, however, result in several additional advantages:

1. The off-policy approach does not require full trajectories and can reuse any past episodes (“experience replay”) for much better sample efficiency.
2. The sample collection follows a behavior policy different from the target policy, bringing better exploration.

Now let’s see how off-policy policy gradient is computed. The behavior policy for collecting samples is a known policy (predefined just like a hyperparameter), labelled as β(a|s)β(a|s). The objective function sums up the reward over the state distribution defined by this behavior policy:

J(θ)=∑s∈Sdβ(s)∑a∈AQπ(s,a)πθ(a|s)=Es∼dβ[∑a∈AQπ(s,a)πθ(a|s)]J(θ)=∑s∈Sdβ(s)∑a∈AQπ(s,a)πθ(a|s)=Es∼dβ[∑a∈AQπ(s,a)πθ(a|s)]

where dβ(s)dβ(s) is the stationary distribution of the behavior policy β; recall that dβ(s)=limt→∞P(St=s|S0,β)dβ(s)=limt→∞P(St=s|S0,β); and Qπ is the action-value function estimated with regard to the target policy π (not the behavior policy!).

Given that the training observations are sampled by a∼β(a|s)a∼β(a|s), we can rewrite the gradient as:

∇θJ(θ)=∇θEs∼dβ[∑a∈AQπ(s,a)πθ(a|s)]=Es∼dβ[∑a∈A(Qπ(s,a)∇θπθ(a|s)+πθ(a|s)∇θQπ(s,a))]≈(i)Es∼dβ[∑a∈AQπ(s,a)∇θπθ(a|s)]=Es∼dβ[∑a∈Aβ(a|s)πθ(a|s)β(a|s)Qπ(s,a)∇θπθ(a|s)πθ(a|s)]=Eβ[πθ(a|s)β(a|s)Qπ(s,a)∇θlnπθ(a|s)]; Derivative product rule.; Ignore the red part: πθ(a|s)∇θQπ(s,a).; The blue part is the importance weight.∇θJ(θ)=∇θEs∼dβ[∑a∈AQπ(s,a)πθ(a|s)]=Es∼dβ[∑a∈A(Qπ(s,a)∇θπθ(a|s)+πθ(a|s)∇θQπ(s,a))]; Derivative product rule.≈(i)Es∼dβ[∑a∈AQπ(s,a)∇θπθ(a|s)]; Ignore the red part: πθ(a|s)∇θQπ(s,a).=Es∼dβ[∑a∈Aβ(a|s)πθ(a|s)β(a|s)Qπ(s,a)∇θπθ(a|s)πθ(a|s)]=Eβ[πθ(a|s)β(a|s)Qπ(s,a)∇θln⁡πθ(a|s)]; The blue part is the importance weight.

where πθ(a|s)β(a|s)πθ(a|s)β(a|s) is the importance weight. Because Qπ is a function of the target policy and thus a function of policy parameter θ, we should take the derivative of ∇θQπ(s,a)∇θQπ(s,a) as well according to the product rule. However, it is super hard to compute ∇θQπ(s,a)∇θQπ(s,a) in reality. Fortunately if we use an approximated gradient with the gradient of Q ignored, we still guarantee the policy improvement and eventually achieve the true local minimum. This is justified in the proof here(Degris, White & Sutton, 2012).

In summary, when applying policy gradient in the off-policy setting, we can simple adjust it with a weighted sum and the weight is the ratio of the target policy to the behavior policy, πθ(a|s)β(a|s)πθ(a|s)β(a|s).

### A3C

[paper|code]

Asynchronous Advantage Actor-Critic (Mnih et al., 2016), short for A3C, is a classic policy gradient method with a special focus on parallel training.

In A3C, the critics learn the value function while multiple actors are trained in parallel and get synced with global parameters from time to time. Hence, A3C is designed to work well for parallel training.

Let’s use the state-value function as an example. The loss function for state value is to minimize the mean squared error, Jv(w)=(Gt−Vw(s))2Jv(w)=(Gt−Vw(s))2 and gradient descent can be applied to find the optimal w. This state-value function is used as the baseline in the policy gradient update.

Here is the algorithm outline:

1. We have global parameters, θ and w; similar thread-specific parameters, θ’ and w’.
2. Initialize the time step t=1t=1
3. While T<=TMAXT<=TMAX:

1. Reset gradient: dθ = 0 and dw = 0.
2. Synchronize thread-specific parameters with global ones: θ’ = θ and w’ = w.
3. tstarttstart = t and sample a starting state stst.
4. While (stst != TERMINAL) and t−tstart<=tmaxt−tstart<=tmax:

1. Pick the action At∼πθ′(At|St)At∼πθ′(At|St) and receive a new reward RtRt and a new state st+1st+1.
2. Update t = t + 1 and T = T + 1
5. Initialize the variable that holds the return estimation R={0Vw′(st)if st is TERMINALotherwiseR={0if st is TERMINALVw′(st)otherwise
6. For i=t−1,…,tstarti=t−1,…,tstart:

1. R←γR+RiR←γR+Ri; here R is a MC measure of GiGi.
2. Accumulate gradients w.r.t. θ’: dθ←dθ+∇θ′logπθ′(ai|si)(R−Vw′(si))dθ←dθ+∇θ′log⁡πθ′(ai|si)(R−Vw′(si));
7. Update synchronously θ using dθ, and w using dw.

A3C enables the parallelism in multiple agent training. The gradient accumulation step (6.2) can be considered as a parallelized reformation of minibatch-based stochastic gradient update: the values of w or θ get corrected by a little bit in the direction of each training thread independently.

### A2C

[paper|code]

A2C is a synchronous, deterministic version of A3C; that’s why it is named as “A2C” with the first “A” (“asynchronous”) removed. In A3C each agent talks to the global parameters independently, so it is possible sometimes the thread-specific agents would be playing with policies of different versions and therefore the aggregated update would not be optimal. To resolve the inconsistency, a coordinator in A2C waits for all the parallel actors to finish their work before updating the global parameters and then in the next iteration parallel actors starts from the same policy. The synchronized gradient update keeps the training more cohesive and potentially to make convergence faster.

A2C has been shown to be able to utilize GPUs more efficiently and work better with large batch sizes while achieving same or better performance than A3C. Fig. 2. The architecture of A3C versus A2C.

### DPG

[paper|code]

In methods described above, the policy function π(.|s)π(.|s) is always modeled as a probability distribution over actions AA given the current state and thus it is stochasticDeterministic policy gradient (DPG) instead models the policy as a deterministic decision: a=μ(s)a=μ(s). It may look bizarre — how can you calculate the gradient of the policy function when it outputs a single action? Let’s look into it step by step.

Refresh on a few notations to facilitate the discussion:

• ρ0(s)ρ0(s): The initial distribution over states
• ρμ(s→s′,k)ρμ(s→s′,k): Starting from state s, the visitation probability density at state s’ after moving k steps by policy μ.
• ρμ(s′)ρμ(s′): Discounted state distribution, defined as ρμ(s′)=∫S∑∞k=1γk−1ρ0(s)ρμ(s→s′,k)dsρμ(s′)=∫S∑k=1∞γk−1ρ0(s)ρμ(s→s′,k)ds.

The objective function to optimize for is listed as follows:

J(θ)=∫Sρμ(s)Q(s,μθ(s))dsJ(θ)=∫Sρμ(s)Q(s,μθ(s))ds

Deterministic policy gradient theorem: Now it is the time to compute the gradient! According to the chain rule, we first take the gradient of Q w.r.t. the action a and then take the gradient of the deterministic policy function μ w.r.t. θ:

∇θJ(θ)=∫Sρμ(s)∇aQμ(s,a)∇θμθ(s)|a=μθ(s)ds=Es∼ρμ[∇aQμ(s,a)∇θμθ(s)|a=μθ(s)]∇θJ(θ)=∫Sρμ(s)∇aQμ(s,a)∇θμθ(s)|a=μθ(s)ds=Es∼ρμ[∇aQμ(s,a)∇θμθ(s)|a=μθ(s)]

We can consider the deterministic policy as a special case of the stochastic one, when the probability distribution contains only one extreme non-zero value over one action. Actually, in the DPG paper, the authors have shown that if the stochastic policy πμθ,σπμθ,σ is re-parameterized by a deterministic policy μθμθ and a variation variable σσ, the stochastic policy is eventually equivalent to the deterministic case when σ=0σ=0. Compared to the deterministic policy, we expect the stochastic policy to require more samples as it integrates the data over the whole state and action space.

The deterministic policy gradient theorem can be plugged into common policy gradient frameworks.

Let’s consider an example of on-policy actor-critic algorithm to showcase the procedure. In each iteration of on-policy actor-critic, two actions are taken deterministically a=μθ(s)a=μθ(s) and the SARSAupdate on policy parameters relies on the new gradient that we just computed above:

δtwt+1θt+1=Rt+γQw(st+1,at+1)−Qw(st,at)=wt+αwδt∇wQw(st,at)=θt+αθ∇aQw(st,at)∇θμθ(s)|a=μθ(s); TD error in SARSA; Deterministic policy gradient theoremδt=Rt+γQw(st+1,at+1)−Qw(st,at); TD error in SARSAwt+1=wt+αwδt∇wQw(st,at)θt+1=θt+αθ∇aQw(st,at)∇θμθ(s)|a=μθ(s); Deterministic policy gradient theorem

However, unless there is sufficient noise in the environment, it is very hard to guarantee enough exploration due to the determinacy of the policy. We can either add noise into the policy (ironically this makes it nondeterministic!) or learn it off-policy-ly by following a different stochastic behavior policy to collect samples.

Say, in the off-policy approach, the training trajectories are generated by a stochastic policy β(a|s)β(a|s) and thus the state distribution follows the corresponding discounted state density ρβρβ:

Jβ(θ)∇θJβ(θ)=∫SρβQμ(s,μθ(s))ds=Es∼ρβ[∇aQμ(s,a)∇θμθ(s)|a=μθ(s)]Jβ(θ)=∫SρβQμ(s,μθ(s))ds∇θJβ(θ)=Es∼ρβ[∇aQμ(s,a)∇θμθ(s)|a=μθ(s)]

Note that because the policy is deterministic, we only need Qμ(s,μθ(s))Qμ(s,μθ(s)) rather than ∑aπ(a|s)Qπ(s,a)∑aπ(a|s)Qπ(s,a) as the estimated reward of a given state s. In the off-policy approach with a stochastic policy, importance sampling is often used to correct the mismatch between behavior and target policies, as what we have described above. However, because the deterministic policy gradient removes the integral over actions, we can avoid importance sampling.

### DDPG

[paper|code]

DDPG (Lillicrap, et al., 2015), short for Deep Deterministic Policy Gradient, is a model-free off-policy actor-critic algorithm, combining DPG with DQN. Recall that DQN (Deep Q-Network) stabilizes the learning of Q-function by experience replay and the frozen target network. The original DQN works in discrete space, and DDPG extends it to continuous space with the actor-critic framework while learning a deterministic policy.

In order to do better exploration, an exploration policy μ’ is constructed by adding noise NN:

μ′(s)=μθ(s)+Nμ′(s)=μθ(s)+N

In addition, DDPG does soft updates (“conservative policy iteration”) on the parameters of both actor and critic, with τ≪1τ≪1: θ′←τθ+(1−τ)θ′θ′←τθ+(1−τ)θ′. In this way, the target network values are constrained to change slowly, different from the design in DQN that the target network stays frozen for some period of time.

One detail in the paper that is particularly useful in robotics is on how to normalize the different physical units of low dimensional features. For example, a model is designed to learn a policy with the robot’s positions and velocities as input; these physical statistics are different by nature and even statistics of the same type may vary a lot across multiple robots. Batch normalization is applied to fix it by normalizing every dimension across samples in one minibatch. Fig 3. DDPG Algorithm. (Image source: Lillicrap, et al., 2015)

### D4PG

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

Distributed Distributional DDPG (D4PG) applies a set of improvements on DDPG to make it run in the distributional fashion.

(1) Distributional Critic: The critic estimates the expected Q value as a random variable ~ a distribution ZwZw parameterized by ww and therefore Qw(s,a)=EZw(x,a)Qw(s,a)=EZw(x,a). The loss for learning the distribution parameter is to minimize some measure of the distance between two distributions — distributional TD error: L(w)=E[d(Tμθ,Zw′(s,a),Zw(s,a)]L(w)=E[d(Tμθ,Zw′(s,a),Zw(s,a)], where TμθTμθ is the Bellman operator.

The deterministic policy gradient update becomes:

∇θJ(θ)≈Eρμ[∇aQw(s,a)∇θμθ(s)|a=μθ(s)]=Eρμ[E[∇aQw(s,a)]∇θμθ(s)|a=μθ(s)]; gradient update in DPG; expectation of the Q-value distribution.∇θJ(θ)≈Eρμ[∇aQw(s,a)∇θμθ(s)|a=μθ(s)]; gradient update in DPG=Eρμ[E[∇aQw(s,a)]∇θμθ(s)|a=μθ(s)]; expectation of the Q-value distribution.

(2) NN-step returns: When calculating the TD error, D4PG computes NN-step TD target rather than one-step to incorporate rewards in more future steps. Thus the new TD target is:

r(s0,a0)+E[∑n=1N−1r(sn,an)+γNQ(sN,μθ(sN))|s0,a0]r(s0,a0)+E[∑n=1N−1r(sn,an)+γNQ(sN,μθ(sN))|s0,a0]

(3) Multiple Distributed Parallel Actors: D4PG utilizes KK independent actors, gathering experience in parallel and feeding data into the same replay buffer.

(4) Prioritized Experience Replay (PER): The last piece of modification is to do sampling from the replay buffer of size RR with an non-uniform probability pipi. In this way, a sample ii has the probability (Rpi)−1(Rpi)−1 to be selected and thus the importance weight is (Rpi)−1(Rpi)−1. Fig. 4. D4PG algorithm (Image source: Barth-Maron, et al. 2018); Note that in the original paper, the variable letters are chosen slightly differently from what in the post; i.e. I use μ(.)μ(.) for representing a deterministic policy instead of π(.)π(.).

[paper|code]

Multi-agent DDPG (MADDPG) (Lowe et al., 2017)extends DDPG to an environment where multiple agents are coordinating to complete tasks with only local information. In the viewpoint of one agent, the environment is non-stationary as policies of other agents are quickly upgraded and remain unknown. MADDPG is an actor-critic model redesigned particularly for handling such a changing environment and interactions between agents.

The problem can be formalized in the multi-agent version of MDP, also known as Markov games. Say, there are N agents in total with a set of states SS. Each agent owns a set of possible action, A1,…,ANA1,…,AN, and a set of observation, O1,…,ONO1,…,ON. The state transition function involves all states, action and observation spaces T:S×A1×…AN↦ST:S×A1×…AN↦S. Each agent’s stochastic policy only involves its own state and action: πθi:Oi×Ai↦[0,1]πθi:Oi×Ai↦[0,1], a probability distribution over actions given its own observation, or a deterministic policy: μθi:Oi↦Aiμθi:Oi↦Ai.

Let o⃗ =o1,…,oNo→=o1,…,oN, μ⃗ =μ1,…,μNμ→=μ1,…,μN and the policies are parameterized by θ⃗ =θ1,…,θNθ→=θ1,…,θN.

The critic in MADDPG learns a centralized action-value function Qμ⃗ i(o⃗ ,a1,…,aN)Qiμ→(o→,a1,…,aN) for the i-th agent, where a1∈A1,…,aN∈ANa1∈A1,…,aN∈AN are actions of all agents. Each Qμ⃗ iQiμ→ is learned separately for i=1,…,Ni=1,…,N and therefore multiple agents can have arbitrary reward structures, including conflicting rewards in a competitive setting. Meanwhile, multiple actors, one for each agent, are exploring and upgrading the policy parameters θiθi on their own.

Actor update:

∇θiJ(θi)=Eo⃗ ,a∼D[∇aiQμ⃗ i(o⃗ ,a1,…,aN)∇θiμθi(oi)|ai=μθi(oi)]∇θiJ(θi)=Eo→,a∼D[∇aiQiμ→(o→,a1,…,aN)∇θiμθi(oi)|ai=μθi(oi)]

Where DD is the memory buffer for experience replay, containing multiple episode samples (o⃗ ,a1,…,aN,r1,…,rN,o⃗ ′)(o→,a1,…,aN,r1,…,rN,o→′) — given current observation o⃗ o→, agents take action a1,…,aNa1,…,aN and get rewards r1,…,rNr1,…,rN, leading to the new observation o⃗ ′o→′.

Critic update:

L(θi)where y=Eo⃗ ,a1,…,aN,r1,…,rN,o⃗ ′[(Qμ⃗ i(o⃗ ,a1,…,aN)−y)2]=ri+γQμ⃗ ′i(o⃗ ′,a′1,…,a′N)|a′j=μ′θj; TD target!L(θi)=Eo→,a1,…,aN,r1,…,rN,o→′[(Qiμ→(o→,a1,…,aN)−y)2]where y=ri+γQiμ→′(o→′,a1′,…,aN′)|aj′=μθj′; TD target!

where μ⃗ ′μ→′ are the target policies with delayed softly-updated parameters.

If the policies μ⃗ μ→ are unknown during the critic update, we can ask each agent to learn and evolve its own approximation of others’ policies. Using the approximated policies, MADDPG still can learn efficiently although the inferred policies might not be accurate.

To mitigate the high variance triggered by the interaction between competing or collaborating agents in the environment, MADDPG proposed one more element – policy ensembles:

1. Train K policies for one agent;
2. Pick a random policy for episode rollouts;
3. Take an ensemble of these K policies to do gradient update.

• Centralized critic + decentralized actors;
• Actors are able to use estimated policies of other agents for learning;
• Policy ensembling is good for reducing variance. Fig. 5. The architecture design of MADDPG. (Image source: Lowe et al., 2017)

### TRPO

[paper|code]

To improve training stability, we should avoid parameter updates that change the policy too much at one step. Trust region policy optimization (TRPO) (Schulman, et al., 2015) carries out this idea by enforcing a KL divergence constraint on the size of policy update at each iteration.

If off policy, the objective function measures the total advantage over the state visitation distribution and actions, while the rollout is following a different behavior policy β(a|s)β(a|s):

J(θ)=∑s∈Sρπθold∑a∈A(πθ(a|s)A^θold(s,a))=∑s∈Sρπθold∑a∈A(β(a|s)πθ(a|s)β(a|s)A^θold(s,a))=Es∼ρπθold,a∼β[πθ(a|s)β(a|s)A^θold(s,a)]; Importance samplingJ(θ)=∑s∈Sρπθold∑a∈A(πθ(a|s)A^θold(s,a))=∑s∈Sρπθold∑a∈A(β(a|s)πθ(a|s)β(a|s)A^θold(s,a)); Importance sampling=Es∼ρπθold,a∼β[πθ(a|s)β(a|s)A^θold(s,a)]

where θoldθold is the policy parameters before the update and thus known to us; ρπθoldρπθold is defined in the same way as above; β(a|s)β(a|s) is the behavior policy for collecting trajectories. Noted that we use an estimated advantage A^(.)A^(.) rather than the true advantage function A(.)A(.) because the true rewards are usually unknown.

If on policy, the behavior policy is πθold(a|s)πθold(a|s):

J(θ)=Es∼ρπθold,a∼πθold[πθ(a|s)πθold(a|s)A^θold(s,a)]J(θ)=Es∼ρπθold,a∼πθold[πθ(a|s)πθold(a|s)A^θold(s,a)]

TRPO aims to maximize the objective function J(θ)J(θ) subject to, trust region constraint which enforces the distance between old and new policies measured by KL-divergence to be small enough, within a parameter δ:

Es∼ρπθold[DKL(πθold(.|s)∥πθ(.|s)]≤δEs∼ρπθold[DKL(πθold(.|s)‖πθ(.|s)]≤δ

In this way, the old and new policies would not diverge too much when this hard constraint is met. While still, TRPO can guarantee a monotonic improvement over policy iteration (Neat, right?). Please read the proof in the paper if interested 🙂

### PPO

[paper|code]

Given that TRPO is relatively complicated and we still want to implement a similar constraint, proximal policy optimization (PPO) simplifies it by using a clipped surrogate objective while retaining similar performance.

First, let’s denote the probability ratio between old and new policies as:

r(θ)=πθ(a|s)πθold(a|s)r(θ)=πθ(a|s)πθold(a|s)

Then, the objective function of TRPO (on policy) becomes:

JTRPO(θ)=E[r(θ)A^θold(s,a)]JTRPO(θ)=E[r(θ)A^θold(s,a)]

Without a limitation on the distance between θoldθold and θθ, to maximize JTRPO(θ)JTRPO(θ) would lead to instability with extremely large parameter updates and big policy ratios. PPO imposes the constraint by forcing r(θ) to stay within a small interval around 1, precisely [1-ε, 1+ε], where ε is a hyperparameter.

JCLIP(θ)=E[min(r(θ)A^θold(s,a),clip(r(θ),1−ϵ,1+ϵ)A^θold(s,a))]JCLIP(θ)=E[min(r(θ)A^θold(s,a),clip(r(θ),1−ϵ,1+ϵ)A^θold(s,a))]

The function clip(r(θ),1−ϵ,1+ϵ)clip(r(θ),1−ϵ,1+ϵ) clips the ratio within [1-ε, 1+ε]. The objective function of PPO takes the minimum one between the original value and the clipped version and therefore we lose the motivation for increasing the policy update to extremes for better rewards.

When applying PPO on the network architecture with shared parameters for both policy (actor) and value (critic) functions, in addition to the clipped reward, the objective function is augmented with an error term on the value estimation (formula in red) and an entropy term (formula in blue) to encourage sufficient exploration.

JCLIP'(θ)=E[JCLIP(θ)−c1(Vθ(s)−Vtarget)2+c2H(s,πθ(.))]JCLIP'(θ)=E[JCLIP(θ)−c1(Vθ(s)−Vtarget)2+c2H(s,πθ(.))]

where Both c1c1 and c2c2 are two hyperparameter constants.

PPO has been tested on a set of benchmark tasks and proved to produce awesome results with much greater simplicity.

### ACER

[paper|code]

ACER, short for actor-critic with experience replay (Wang, et al., 2017), is an off-policy actor-critic model with experience replay, greatly increasing the sample efficiency and decreasing the data correlation. A3C builds up the foundation for ACER, but it is on policy; ACER is A3C’s off-policy counterpart. The major obstacle to making A3C off policy is how to control the stability of the off-policy estimator. ACER proposes three designs to overcome it:

• Use Retrace Q-value estimation;
• Truncate the importance weights with bias correction;
• Apply efficient TRPO.

Retrace Q-value Estimation

Retrace is an off-policy return-based Q-value estimation algorithm with a nice guarantee for convergence for any target and behavior policy pair (π, β), plus good data efficiency.

Recall how TD learning works for prediction:

1. Compute TD error: δt=Rt+γEa∼πQ(St+1,a)−Q(St,At)δt=Rt+γEa∼πQ(St+1,a)−Q(St,At); the term rt+γEa∼πQ(st+1,a)rt+γEa∼πQ(st+1,a) is known as “TD target”. The expectation Ea∼πEa∼π is used because for the future step the best estimation we can make is what the return would be if we follow the current policy π.
2. Update the value by correcting the error to move toward the goal: Q(St,At)←Q(St,At)+αδtQ(St,At)←Q(St,At)+αδt. In other words, the incremental update on Q is proportional to the TD error: ΔQ(St,At)=αδtΔQ(St,At)=αδt.

When the rollout is off policy, we need to apply importance sampling on the Q update:

ΔQimp(St,At)=γt∏1≤τ≤tπ(Aτ|Sτ)β(Aτ|Sτ)δtΔQimp(St,At)=γt∏1≤τ≤tπ(Aτ|Sτ)β(Aτ|Sτ)δt

The product of importance weights looks pretty scary when we start imagining how it can cause super high variance and even explode. Retrace Q-value estimation method modifies ΔQΔQ to have importance weights truncated by no more than a constant c:

ΔQret(St,At)=γt∏1≤τ≤tmin(c,π(Aτ|Sτ)β(Aτ|Sτ))δtΔQret(St,At)=γt∏1≤τ≤tmin(c,π(Aτ|Sτ)β(Aτ|Sτ))δt

ACER uses QretQret as the target to train the critic by minimizing the L2 error term: (Qret(s,a)−Q(s,a))2(Qret(s,a)−Q(s,a))2.

Importance weights truncation

To reduce the high variance of the policy gradient g^g^, ACER truncates the importance weights by a constant c, plus a correction term. The label g^acertg^tacer is the ACER policy gradient at time t.

g^acert==ωt(Qret(St,At)−Vθv(St))∇θlnπθ(At|St)min(c,ωt)(Qret(St,At)−Vw(St))∇θlnπθ(At|St)+Ea∼π[max(0,ωt(a)−cωt(a))(Qw(St,a)−Vw(St))∇θlnπθ(a|St)]; Let ωt=π(At|St)β(At|St); Let ωt(a)=π(a|St)β(a|St)g^tacer=ωt(Qret(St,At)−Vθv(St))∇θln⁡πθ(At|St); Let ωt=π(At|St)β(At|St)=min(c,ωt)(Qret(St,At)−Vw(St))∇θln⁡πθ(At|St)+Ea∼π[max(0,ωt(a)−cωt(a))(Qw(St,a)−Vw(St))∇θln⁡πθ(a|St)]; Let ωt(a)=π(a|St)β(a|St)

where Qw(.)Qw(.) and Vw(.)Vw(.) are value functions predicted by the critic with parameter w. The first term (blue) contains the clipped important weight. The clipping helps reduce the variance, in addition to subtracting state value function Vw(.)Vw(.) as a baseline. The second term (red) makes a correction to achieve unbiased estimation.

Efficient TRPO

Furthermore, ACER adopts the idea of TRPO but with a small adjustment to make it more computationally efficient: rather than measuring the KL divergence between policies before and after one update, ACER maintains a running average of past policies and forces the updated policy to not deviate far from this average.

The ACER paper is pretty dense with many equations. Hopefully, with the prior knowledge on TD learning, Q-learning, importance sampling and TRPO, you will find the paper slightly easier to follow 🙂

### ACTKR

[paper|code]

ACKTR (actor-critic using Kronecker-factored trust region) (Yuhuai Wu, et al., 2017) proposed to use Kronecker-factored approximation curvature (K-FAC) to do the gradient update for both the critic and actor. K-FAC made an improvement on the computation of natural gradient, which is quite different from our standard gradientHere is a nice, intuitive explanation of natural gradient. One sentence summary is probably:

“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.”

I listed ACTKR here mainly for the completeness of this post, but I would not dive into details, as it involves a lot of theoretical knowledge on natural gradient and optimization methods. If interested, check these papers/posts, before reading the ACKTR paper:

Here 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.”

### Soft Actor-Critic

[paper|code]

Soft Actor-Critic (SAC) (Haarnoja et al. 2018) incorporates the entropy measure of the policy into the reward to encourage exploration: we expect to learn a policy that acts as randomly as possible while it is still able to succeed at the task. It is an off-policy actor-critic model following the maximum entropy reinforcement learning framework. A precedent work is Soft Q-learning.

Three key components in SAC:

• An actor-critic architecture with separate policy and value function networks;
• An off-policy formulation that enables reuse of previously collected data for efficiency;
• Entropy maximization to enable stability and exploration.

The policy is trained with the objective to maximize the expected return and the entropy at the same time:

J(θ)=∑t=1TE(st,at)∼ρπθ[r(st,at)+αH(πθ(.|st))]J(θ)=∑t=1TE(st,at)∼ρπθ[r(st,at)+αH(πθ(.|st))]

where H(.)H(.) is the entropy measure and αα controls how important the entropy term is, known as temperature parameter. The entropy maximization leads to policies that can (1) explore more and (2) capture multiple modes of near-optimal strategies (i.e., if there exist multiple options that seem to be equally good, the policy should assign each with an equal probability to be chosen).

Precisely, SAC aims to learn three functions:

• The policy with parameter θθ, πθπθ.
• Soft Q-value function parameterized by ww, QwQw.
• Soft state value function parameterized by ψψ, Vψ; theoretically we can infer VV by knowing QQand ππ, but in practice, it helps stabilize the training.

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

Q(st,at)V(st)=r(st,at)+γEst+1∼ρπ(s)[V(st+1)]=Eat∼π[Q(st,at)−logπ(st,at)]; according to Bellman equation.Q(st,at)=r(st,at)+γEst+1∼ρπ(s)[V(st+1)]; according to Bellman equation.V(st)=Eat∼π[Q(st,at)−log⁡π(st,at)]

ρπ(s)ρπ(s) and ρπ(s,a)ρπ(s,a) denote the state and the state-action marginals of the state distribution induced by the policy π(a|s)π(a|s); see the similar definitions in DPG section.

The soft state value function is trained to minimize the mean squared error:

where DD is the replay buffer.

The soft Q function is trained to minimize the soft Bellman residual:

where ψ¯ψ¯ is the target value function which is the exponential moving average (or only gets updated periodically in a “hard” way), just like how the parameter of the target Q network is treated in DQN to stabilize the training.

SAC updates the policy to minimize the KL-divergence:

πnewobjective for update: Jπ(θ)=argminπ′∈ΠπoldDKL(π′(.|st)∥exp(Qπold(st,.)−logZπold(st)))=DKL(πθ(.|st)∥exp(Qw(st,.)−logZw(st)))πnew=arg⁡minπ′∈ΠπoldDKL(π′(.|st)‖exp⁡(Qπold(st,.)−log⁡Zπold(st)))objective for update: Jπ(θ)=DKL(πθ(.|st)‖exp⁡(Qw(st,.)−log⁡Zw(st)))

where ΠΠ is the set of potential policies that we can model our policy as to keep them tractable; for example, ΠΠ can be the family of Gaussian mixture distributions, expensive to model but highly expressive and still tractable. Zπold(st)Zπold(st) is the partition function. How to minimize Jπ(θ)Jπ(θ) depends our choice of ΠΠ.

This update guarantees that Qπnew(st,at)≥Qπold(st,at)Qπnew(st,at)≥Qπold(st,at), please check the proof on this lemma in the Appendix B.2 in the original paper.

Once we have defined the objective functions and gradients for soft action-state value, soft state value and the policy network, the soft actor-critic algorithm is straightforward: Fig. 6. The soft actor-critic algorithm.

### TD3

[paper|code]

The Q-learning algorithm is commonly known to suffer from the overestimation of the value function. This overestimation can propagate through the training iterations and negatively affect the policy. This property directly motivated Double Q-learning and Double DQN: the action selection and Q-value update are decoupled by using two value networks.

Twin Delayed Deep Deterministic (short for TD3Fujimoto et al., 2018) applied a couple of tricks on DDPG to prevent the overestimation of the value function:

(1) Clipped Double Q-learning: In Double Q-Learning, the action selection and Q-value estimation are made by two networks separately. In the DDPG setting, given two deterministic actors (μθ1,μθ2)(μθ1,μθ2) with two corresponding critics (Qw1,Qw2)(Qw1,Qw2), the Double Q-learning Bellman targets look like:

y1y2=r+γQw2(s′,μθ1(s′))=r+γQw1(s′,μθ2(s′))y1=r+γQw2(s′,μθ1(s′))y2=r+γQw1(s′,μθ2(s′))

However, due to the slow changing policy, these two networks could be too similar to make independent decisions. The Clipped Double Q-learning instead uses the minimum estimation among two so as to favor underestimation bias which is hard to propagate through training:

y1y2=r+γmini=1,2Qwi(s′,μθ1(s′))=r+γmini=1,2Qwi(s′,μθ2(s′))y1=r+γmini=1,2Qwi(s′,μθ1(s′))y2=r+γmini=1,2Qwi(s′,μθ2(s′))

(2) Delayed update of Target and Policy Networks: In the actor-critic model, policy and value updates are deeply coupled: Value estimates diverge through overestimation when the policy is poor, and the policy will become poor if the value estimate itself is inaccurate.

To reduce the variance, TD3 updates the policy at a lower frequency than the Q-function. The policy network stays the same until the value error is small enough after several updates. The idea is similar to how the periodically-updated target network stay as a stable objective in DQN.

(3) Target Policy Smoothing: Given a concern with deterministic policies that they can overfit to narrow peaks in the value function, TD3 introduced a smoothing regularization strategy on the value function: adding a small amount of clipped random noises to the selected action and averaging over mini-batches.

yϵ=r+γQw(s′,μθ(s′)+ϵ)∼clip(N(0,σ),−c,+c) ; clipped random noises.y=r+γQw(s′,μθ(s′)+ϵ)ϵ∼clip(N(0,σ),−c,+c) ; clipped random noises.

This approach mimics the idea of SARSA update and enforces that similar actions should have similar values.

Here is the final algorithm: Fig 7. TD3 Algorithm. (Image source: Fujimoto et al., 2018)

## Quick Summary

After reading through all the algorithms above, I list a few building blocks or principles that seem to be common among them:

• Try to reduce the variance and keep the bias unchanged to stabilize learning.
• Off-policy gives us better exploration and helps us use data samples more efficiently.
• Experience replay (training data sampled from a replay memory buffer);
• Target network that is either frozen periodically or updated slower than the actively learned policy network;
• Batch normalization;
• Entropy-regularized reward;
• The critic and actor can share lower layer parameters of the network and two output heads for policy and value functions.
• It is possible to learn with deterministic policy rather than stochastic one.
• Put constraint on the divergence between policy updates.
• New optimization methods (such as K-FAC).
• Entropy maximization of the policy helps encourage exploration.
• Try not to overestimate the value function.
• TBA more.

If you notice mistakes and errors in this post, don’t hesitate to contact me at [lilian dot wengweng at gmail dot com] and I would be very happy to correct them right away!

See you in the next post 😀

 jeremykun.com Markov Chain Monte Carlo Without all the Bullshit

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

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

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

 timvieira.github.io Importance sampling

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

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

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

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

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

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

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

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

 kvfrans.com A intuitive explanation of natural gradient descent