AC A2C

Advantage Actor Critic(A2C)

Introduction

The policy gradient theorem can be generalized to include a comparison of the action value to an arbitrary basline $b(s)$:

$${\nabla }_{\theta }J(\theta )\propto \sum _s\mu (s)\sum _a(q_{\pi }(s,a)-b(s)){\nabla }_{\theta }\pi (a|s,\theta )$$

The baseline can be any function as long as it does not vary with $a$; the equation remains valid because the subtracted quantity is zero:

$$\begin{array}{rlrl}\sum _{a}b(s)\nabla \pi (a|s,\theta )& =b(s)\sum _a\nabla \pi (a|s,\theta )& & (\star )\\ & =b(s)\nabla \sum _a\pi (a|s,\theta )& & (\text{linearity of differentiation})\\ & =b(s)\nabla 1=0& & \end{array}$$

Baseline invariance

注意到

上面的Intro中对引入baseline的过程进行了简单的介绍（refer from Sutton&Batto 13.4）：引入一个和action无关的随机变量或者函数仍然可以使原来的policy gradient保持原有的equation，并不改变任何之前所证明过的东西；下面我们就baseline的不变性来分析一下。

Property: the policy gradient is invarient to an additional baseline:

$$\begin{array}{rl}{\nabla }_{\theta }J(\theta )& ={\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[q_{\pi }(S,A){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]\\ & ={\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[(q_{\pi }(S,A)-b(S)){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]\end{array}$$

Here the additional baseline $b(S)$ is a scalar function of $S$.

Why is it valid?

Cause:

$$\begin{array}{rl}& {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[(q_{\pi }(S,A)-b(S)){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]\\ =& {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[q_{\pi }(S,A){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]-\underset{0}{\underbrace{{\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[b(S){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]}}\end{array}$$

Details:

$$\begin{array}{rl}{\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[b(S){\nabla }_{\theta }\ln \pi (A|S,\theta )\right]& =\sum _s\mu (s)b(s)\sum _a\pi (a|s,\theta ){\nabla }_{\theta }\ln \pi (a|s,\theta )\\ & =\sum _s\mu (s)b(s)\sum _a{\nabla }_{\theta }\pi (a|s,\theta )\\ & =\sum _s\mu (s)b(s){\nabla }_{\theta }\sum _a\pi (a|s,\theta )\\ & =\sum _s\mu (s)b(s){\nabla }_{\theta }1=0\end{array}$$

Why is it useful?

The gradient is ${\nabla }_{\theta }J(\theta )=\mathbb{E}(X)$ where

$$X\doteq (q_{\pi }(S,A)-b(S)){\nabla }_{\theta }\ln \pi (A|S,\theta )$$

• we have $\mathbb{E}(X)$ is invarient to $b(S)$ from above
• we want that our $b(S)$ can minimize the $\mathrm{var}(X)$, usually, $b(S)=v_{\pi }(S)$ is a suboptimal baseline, see the derivation of the optimal baseline

为什么要引入baseline

1. 引入baseline不改变$\mathbb{E}$，即不改变原有的policy gradient的equation
2. 引入optimal baseline的目的是为了减小$\mathrm{var}(X)$，通常选择$v_{\pi }(S)$作为baseline，我希望采样到的每个$X$都尽可能的接近$\mathbb{E}(X)$，这样就可以减小$\mathrm{var}(X)$

Algorithm

The gradient-ascent algorithm is:

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha {\nabla }_{\theta }J({\theta }_t)\\ & ={\theta }_t+\alpha {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[(q_{\pi }(S,A)-b(S)){\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)\right]\\ & ={\theta }_t+\alpha {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[(q_{\pi }(S,A)-v_{\pi }(S)){\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)\right]\\ & ={\theta }_t+\alpha {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[{\delta }_{\pi }(S,A){\nabla }_{\theta }\ln \pi (A|S,{\theta }_t)\right]\end{array}$$

where ${\delta }_{\pi }(S,A)\doteq q_{\pi }(S,A)-v_{\pi }(S)$ is called the $\text{advantage function}$.

The stochasitic version is:

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha [q_t(s_t,a_t)-v_t(s_t)]{\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\\ & ={\theta }_t+\alpha {\delta }_t(s_t,a_t){\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\end{array}$$

Refer to TD methods, we can replace $q_{\pi }(s,a)$ by MC error or TD error:

$$\begin{array}{rl}& {\mathbb{E}}_{S\sim \mu ,A\sim \pi }\left[q_{\pi }(S,A)-v_{\pi }(S)|S=s_t,A=a_t\right]\\ =& \{\begin{array}{ll}\mathbb{E}\left[G-v_{\pi }(S)|S=s_t,A=a_t\right],& (\text{MC error})\\ \mathbb{E}\left[R+\gamma v_{\pi }(S^{\prime })-v_{\pi }(S)|S=s_t,A=a_t\right],& (\text{TD error})\end{array}\end{array}$$

So the algorithm can be written as TD version:

$$\begin{array}{rl}{\theta }_{t+1}& ={\theta }_t+\alpha (q_t(s_t,a_t)-v_t(s_t)){\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\\ & ={\theta }_t+\alpha (r_{t+1}+\gamma v_t(s_{t+1})-v_t(s_t)){\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\end{array}$$

Benifit: only need one network to approximate $v_{\pi }(s)$ rather than two networks for $q_{\pi }(s,a)$ and $v_{\pi }(s)$.

Analysis

Same as the analysis in the last lecture, we have ${\beta }_t={\delta }_t(s_t,a_t)/\pi (a_t|s_t,{\theta }_t)$ can well balance exploration and exploitation, but what matters here is the relative value(advantage value) ${\delta }_t$ rather than the absolute value(action value) $q_t$.

Implementation

The implementation is also simple, compared with Implementation.

$$\boxed{\begin{array}{rl}& \text{Algorithm}\text{Advantage Actor-Critic (A2C) with On-Policy TD}\\ & \text{Initialization: }\\ & \text{Policy parameters }{\theta }_0,\text{ value function parameters }{w}_0.{\alpha }_{\theta },{\alpha }_w>0.\\ & \text{For each episode, do:}\\ & \text{Initialize state }{s}_0.\\ & \text{Select action }{a}_0\sim \pi (a|s_0,{\theta }_0).\\ & \text{While }{s}_t\text{ is not terminal, do:}\\ & \text{Execute }{a}_t\text{, observe }{r}_{t+1},s_{t+1}.\\ & \text{Select }{a}_{t+1}\sim \pi (a|s_{t+1},{\theta }_t).\\ & \text{Advantage (TD Error):}\\ & {\delta }_t=r_{t+1}+\gamma v(s_{t+1},w_t)-v(s_t,w_t)\\ & \text{Actor (Policy Update):}\\ & {\theta }_{t+1}\leftarrow {\theta }_t+{\alpha }_{\theta }{\delta }_t{\nabla }_{\theta }\ln \pi (a_t|s_t,{\theta }_t)\\ & \text{Critic (Value Update):}\\ & w_{t+1}\leftarrow w_t+{\alpha }_w{\delta }_t{\nabla }_{w}v(s_t,w_t)\\ & s_t\leftarrow s_{t+1},a_t\leftarrow a_{t+1}\end{array}}$$

• on-policy
• $\pi$ is stochastic, no need to use $ϵ$-greedy

Later

on-policy ⇒ off-policy