Off-Policy Actor-Critic Methods

The policy gradient methods that we have studied so far, including REINFORCE, QAC, and A2C, are all on-policy. The reason for this can be seen from the expression of the true gradient: θJ(θ)=ESη,Aπ[θlnπ(AS,θt)(qπ(S,A)vπ(S))].

To use samples to approximate this true gradient, we must generate the action samples by following π(θ). Hence, π(θ) is the behavior policy. Since π(θ) is also the target policy that we aim to improve, the policy gradient methods are on-policy.

In the case that we already have some samples generated by a given behavior policy, the policy gradient methods can still be applied to utilize these samples. To do that, we can employ a technique called importance sampling. It is a general technique for estimating expected values defined over one probability distribution using some samples drawn from another distribution.

Sources:

  1. Shiyu Zhao. Chapter 10: Actor-Critic Methods. Mathematical Foundations of Reinforcement Learning.

Importance sampling

We next introduce the importance sampling technique. Consider a random variable XX. Suppose that p0(X) is a probability distribution. Our goal is to estimate EXp0[X]. Suppose that we have some i.i.d. samples {xi}i=1n.

Suppose the samples {xi}i=1n are not generated by p0. Instead, they are generated by another distribution p1. Can we still use these samples to approximate EXp0[X] ? The answer is yes. EXp0[X] can be approximated based on the importance sampling technique.

In particular, EXp0[X] satisfies EXp0[X]=xXp0(x)x=xXp1(x)p0(x)p1(x)xf(x)=EXp1[f(X)].

Thus, estimating EXp0[X] becomes the problem of estimating EXp1[f(X)]. Let f¯1ni=1nf(xi)

Since f¯ can effectively approximate EXp1[f(X)], we obtain EXp0[X]=EXp1[f(X)]f¯=1ni=1nf(xi)=1ni=1np0(xi)p1(xi) importance  weight xi.

Here, p0(xi)p1(xi) is called the importance weight. When p1=p0, the importance weight is 1 and f¯ becomes x¯. When p0(xi)p1(xi),xi can be sampled more frequently by p0 but less frequently by p1. In this case, the importance weight, which is greater than one, emphasizes the importance of this sample.

You may ask that while p0(x) is required in (1)1ni=1np0(xi)p1(xi)xi, why do we not directly calculate EXp0[X] using its definition EXp0[X]=xXp0(x)x ?

The answer is as follows. To use the definition, we need to know either the analytical expression of p0 or the value of p0(x) for every xX. However, it is difficult to obtain the analytical expression of p0 when the distribution is represented by, for example, a neural network. It is also difficult to obtain the value of p0(x) for every xX when X is large. By contrast, (1) merely requires the values of p0(xi) for some samples and is much easier to implement in practice.

The off-policy policy gradient theorem

Algorithm 10.3

Like the previous on-policy case, we need to derive the policy gradient in the off-policy case.

  • Suppose β is the behavior policy that generates experience samples.

  • Our aim is to use these samples to update a target policy π that can minimize the metric J(θ)=sSdβ(s)vπ(s)=ESdβ[vπ(S)] where dβ is the stationary distribution under policy β and vπ is the state value under policy π.

The gradient of this metric is given in the following theorem.

Theorem 10.1 (Off-policy policy gradient theorem). In the discounted case where γ (0,1), the gradient of J(θ) is θJ(θ)=ESρ,Aβ[π(AS,θ)β(AS) importance  weight θlnπ(AS,θ)qπ(S,A)], where the state distribution ρ is ρ(s)sSdβ(s)Prπ(ss),sS, where Prπ(ss)=k=0γk[Pπk]ss=[(IγPπ)1]ss is the discounted total probability of transitioning from s to s under policy π.

The gradient θJ(θ) is similar to that in the on-policy case in Theorem 9.1, but there are two differences. The first difference is the importance weight. The second difference is that Aβ instead of Aπ. Therefore, we can use the action samples generated by following β to approximate the true gradient. The proof of the theorem is given in the appendix.

The off-policy policy gradient is also invariant to a baseline b(s). In particular, we have

θJ(θ)=ESρ,Aβ[π(AS,θ)β(AS)θlnπ(AS,θ)(qπ(S,A)b(S))] because E[π(AS,θ)β(AS)θlnπ(AS,θ)b(S)]=0.

To reduce the estimation variance, we select the baseline as b(S)=vπ(S) as in A2C and obtain θJ(θ)=E[π(AS,θ)β(AS)θlnπ(AS,θ)(qπ(S,A)vπ(S))]

The corresponding stochastic gradient-ascent algorithm is θt+1=θt+αθπ(atst,θt)β(atst)θlnπ(atst,θt)(qt(st,at)vt(st))

Similar to the on-policy case, qt(st,at)vt(st)rt+1+γvt(st+1)vt(st)δt(st,at)

Then, the algorithm becomes θt+1=θt+αθπ(atst,θt)β(atst)θlnπ(atst,θt)δt(st,at) and hence θt+1=θt+αθ(δt(st,at)β(atst))θπ(atst,θt)

Appendix

Proof of Theorem 10.1

Since dβ is independent of θ, the gradient of J(θ) satisfies θJ(θ)=θsSdβ(s)vπ(s)=sSdβ(s)θvπ(s).

According to Lemma 9.2, the expression of θvπ(s) is θvπ(s)=sSPrπ(ss)aAθπ(as,θ)qπ(s,a), where Prπ(ss)k=0γk[Pπk]ss=[(InγPπ)1]ss Substituting θvπ(s) into sSdβ(s)θvπ(s) yields θJ(θ)=sSdβ(s)θvπ(s)=sSdβ(s)sSPrπ(ss)aAθπ(as,θ)qπ(s,a)=sS(sSdβ(s)Prπ(ss))aAθπ(as,θ)qπ(s,a)sSρ(s)aAθπ(as,θ)qπ(s,a)=sSρ(s)aAθπ(as,θ)qπ(s,a) (change s to s ) =ESρ[aAθπ(aS,θ)qπ(S,a)],

where the 3rd equation is because ρ(s)sSdβ(s)Prπ(ss),sS.

By using the importance sampling technique, the above equation can be further rewritten as $$ ESρ[aAθπ(aS,θ)qπ(S,a)]=ESρ[aAβ(aS)π(aS,θ)β(aS)θπ(aS,θ)π(aS,θ)qπ(S,a)]=ESρ[aAβ(aS)π(aS,θ)β(aS)θlnπ(aS,θ)qπ(S,a)]=ESρ,Aβ[π(AS,θ)β(AS)θlnπ(AS,θ)qπ(S,A)].

$$

The proof is complete. The above proof is similar to that of Theorem 9.1.