PG metric gradient

Gradient of the PG metric

Introduction

预告

这节将是笔者认为这个笔记最精彩的一节，会有很多证明，放心食用👀

• Given a metric, we next derive its gradient and then, apply gradient-based methods to optimize the metric.

Simply put, the unified gradient of the metric is given by

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

重要

赵老师PPT没有阐述的很清楚这个公式的推导，自己花了差不多一天时间来写的证明，用了matrix form的形式来证的，结合了很多Sutton书中的内容⇒ policy_gradient_proof

Turn into Expectation

$$\begin{array}{rlrl}{\nabla }_{\theta }J(\theta )& \propto \sum _s\mu (s)\sum _a{q}_{\pi }(s,a){\nabla }_{\theta }\pi (a|s,\theta )& & \\ & ={\mathbb{E}}_{S_t\sim \mu }\left[\sum _a{q}_{\pi }(S_t,a){\nabla }_{\theta }\pi (a|S_t,\theta )\right]& & (\text{replace s by the sample St∼μ})\\ & ={\mathbb{E}}_{S_t\sim \mu }\left[\sum _a\pi (a|S_t,\theta )q_{\pi }(S_t,a)\frac{{\nabla }_{\theta }\pi (a|S_t,\theta )}{\pi (a|S_t,\theta )}\right]& & \\ & ={\mathbb{E}}_{S_t\sim \mu ,A_t\sim \pi }\left[q_{\pi }(S_t,A_t)\frac{{\nabla }_{\theta }\pi (A_t|S_t,\theta )}{\pi (A_t|S_t,\theta )}\right]& & (\text{replace a by the sample At∼π})\\ & ={\mathbb{E}}_{S_t\sim \mu ,A_t\sim \pi }\left[G_t\frac{{\nabla }_{\theta }\pi (A_t|S_t,\theta )}{\pi (A_t|S_t,\theta )}\right]& & (q_{\pi }(S_t,A_t)\doteq \mathbb{E}\left[G_t|S_t,A_t\right])\\ & ={\mathbb{E}}_{S_t\sim \mu ,A_t\sim \pi }\left[G_t{\nabla }_{\theta }\ln \pi (A_t|S_t,\theta )\right]& & \end{array}$$

注意上面是如何把一个 ${\sum }_a$和${\sum }_s$逐渐提出来变成$\mathbb{E}$的

1. 我们首先提出来的是${\sum }_s\mu (s)$，为了清晰表示，这里在外面的$\mathbb{E}$加上了下标$S\sim \mu$说明是对哪个random variable做期望的，同时将所有小写s替换成大写S，也说明了S此时的分布(on-policy distribution)
2. 第二步提出来之前我们先凑出action probability，所以就又能把${\sum }_a\pi (a|S,\theta )$提出来，同时在外面的$\mathbb{E}$加上下标$A\sim \pi$，同时将所有小写a替换成大写A
3. 为什么要这样提出来变成一个期望形式？因为我们最终还是希望可以通过MC的方法去轻松采样到大量state-action pair的数据的，提出来之后我们就可以像之前一样update by samples

About the policy gradient

$$\begin{array}{rl}\pi (a|s,\theta )& =\frac{e^{h(s,a,\theta )}}{{\sum }_{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}}\\ h(s,a,\theta )& ={\theta }^T\varphi (s,a)\end{array}$$

where

• $\varphi (s,a)\in {\mathbb{R}}^d$ is the feature vector of state-action pair $(s,a)$
• $\theta \in {\mathbb{R}}^d$ is the parameter vector of the policy

$$\begin{array}{rl}{\nabla }_{\theta }\ln \pi (a|s,\theta )& ={\nabla }_{\theta }\ln \frac{e^{h(s,a,\theta )}}{{\sum }_{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}}\\ & ={\nabla }_{\theta }\left(h(s,a,\theta )-\ln \sum _{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}\right)\\ & ={\nabla }_{\theta }h(s,a,\theta )-{\nabla }_{\theta }\ln \sum _{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}\\ & =\varphi (s,a)-\frac{1}{{\sum }_{a^{\prime \prime }}{e}^{h(s,a^{\prime \prime },\theta )}}{\nabla }_{\theta }\sum _{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}\\ & =\varphi (s,a)-\frac{1}{{\sum }_{a^{\prime \prime }}{e}^{h(s,a^{\prime \prime },\theta )}}\sum _{a^{\prime }}{e}^{h(s,a^{\prime },\theta )}{\nabla }_{\theta }h(s,a^{\prime },\theta )\\ & =\varphi (s,a)-\sum _{a^{\prime }}\frac{e^{h(s,a^{\prime },\theta )}}{{\sum }_{a^{\prime \prime }}{e}^{h(s,a^{\prime \prime },\theta )}}\varphi (s,a^{\prime })\\ & =\varphi (s,a)-\sum _{a^{\prime }}\pi (a^{\prime }|s,\theta )\varphi (s,a^{\prime })\end{array}$$

Remarks:

• such a form based on the softmax function can be realized by a neural network
  • input is $s$, (continuous)
  • output is $a$, (discrete, $|\mathcal{A}|$ outputs)
  • the activation of the output layer is the softmax function
• $\pi (a|s,\theta )\in [0,1]$ for all $a\in \mathcal{A}$ and ${\sum }_a\pi (a|s,\theta )=1$
  • the parameterized policy is stochastic and hence exploratory

一些矩阵想法

按照之前的做法，我们这里看到也是可以写成矩阵形式的，由上面定义，我们知道

• $\varphi$ is a (n,m,k) tensor
• $\theta$ is a (k,1) vector
• $\pi =\mathrm{softmax}(\varphi \times \theta ,\dim =1)$ is a (n,m) matrix

我们可以直接写成下面这样子：

$$\underset{(n,m,k)}{\underbrace{{\nabla }_{\theta }\ln \pi }}=\underset{(n,m,k)}{\underbrace{\varphi }}-\underset{(n,1,m)}{\underbrace{\pi }}@\underset{(n,m,k)}{\underbrace{\varphi }}$$

但是我们的${\nabla }_{\theta }\ln \pi$的shape应该是(k,1)的，容易看出：在前向传播过程中，我们的$\theta$是和$\varphi$ (n,m,k)中的每一个(1,k)都做了向量dot-product-sum的操作（这里的广播操作），所以在反向传播过程中，就应该对我们最后得到的一个梯度(n,m,k)取mean(dim=0,dim=1)，这样就得到了一个(k,)的梯度；或者可以直接将上面的矩阵形式reshape成(k,n*m)的形式，然后再取mean(dim=1)即可;

TL;DR: 前向传播中的广播操作使得$\theta$复制了nxm份，所以在反向传播中，我们需要对nxm份的梯度取平均