Policy gradient的表示

A value function may still be used to learn the policy parameter, but is not required for action selection. We use the notation $\theta \in \mathbb{R}^{d^{\prime}}$ for the policy’s parameter vector. Thus we write $\pi(a \mid s, \boldsymbol{\theta})=\operatorname{Pr}\left{A_t=a \mid S_t=s, \boldsymbol{\theta}_t=\boldsymbol{\theta}\right}$ for the probability that action $a$ is taken at time $t$ given that the environment is in state $s$ at time $t$ with parameter $\boldsymbol{\theta}$. If a method uses a learned value function as well, then the value function’s weight vector is denoted $\mathbf{w} \in \mathbb{R}^d$ as usual, as in $\hat{v}(s, \mathbf{w})$.

Policy gradient method和action-value method最大的不同是其直接将一个策略给参数化，一般用$\theta$表示，写作
$$
\begin{equation}
\pi(a|s,\pmb{\theta}) = Pr{A_t=a|S_t=s,\theta_t=\theta}
\end{equation}
$$
可以直观地理解为，策略$\pi$是在状态$s$下动作$a$的函数，$\pmb{\theta}$是其表现形式，是一个矢量。总的来说，策略梯度方法就是将策略给参数化，然后通过找到参数$\theta$对策略优化的梯度，不断地更新策略，从而使策略达到最优的状态。

  • 对于策略的具体参数化可以以任何形式进行，只要策略函数相对于其参数是可微分的，即$\nabla_{\theta} \pi(a \mid s, \boldsymbol{\theta})$ 是存在的。

  • 一种常用的指数softmax参数化可表示为：
    $$
    \begin{equation}
    \pi(a \mid s, \boldsymbol{\theta}) \doteq \frac{e^{h(s, a, \boldsymbol{\theta})}}{\sum_b e^{h(s, b, \boldsymbol{\theta})}}
    \end{equation}
    $$

其中：
$$
\begin{equation}
h(s, a, \boldsymbol{\theta})=\boldsymbol{\theta}^{\top} \mathbf{x}(s, a)
\end{equation}
$$
$\mathbf{x(s,a)}$: 关于状态和动作的特征向量

那么首先需要定义一个被优化的目标函数，和随机梯度一样称为效用目标函数$J(\pmb{\theta})$,该函数是参数$\pmb{\theta}$的函数，是一个标量，但是$J(\pmb{\theta})$,在不同的情况下的定义是不一样的，如在episodic和continuing的情况下需要被分别对待。

然后根据目标函数的梯度，对目标函数使用梯度上升的方法进行优化
$$
\boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_t+\alpha \widehat{\nabla J(\boldsymbol{\theta}_t)}
$$
其中有一种actor-critic的方法，‘actor’是指习得的策略，‘critic’是指学习的价值函数，通常是状态价值函数。

Episodic 情况下(离散)的效用目标函数

假设每个episode都从一个随机状态$s_0$开始，那么episodic情况下的目标函数有如下形式:
$$
J(\boldsymbol{\theta}) \doteq v_{\pi_{\boldsymbol{\theta}}}\left(s_0\right)
$$

如何更新$\pmb{\theta}$

那么如何改变参数$\theta$ 的值，使得目标函数得到优化的时候策略也可以提升呢？首先需要明确的意义是所谓的策略效能performance不仅仅取决于选择的动作，而且还取决于做出选择的时候环境状态的概率分布，即影响策略效用的两个因素：

  1. 策略的动作选取：选取不同的动作会产生不同的状态-动作值，继而影响策略的效能
  2. 动作选取后环境的状态分布：选取不同的动作会产生不同的状态分布，比如围棋游戏，不同的状态分布等同于不同的棋面，进入不同的棋面的概率不同在该局也就对胜负产生影响

由此引发出下一个问题，即动作的选择可以直接由参数化的策略进行控制，即在不同状态选取不同动作时使用参数化的方法来确定每个动作的选取概率，但是环境的状态分布却往往是未知的，也就是说没办法预先知道某个策略对环境状态分布所产生的影响，如下围棋时，由于对手策略是未知的（假设没有任何关于对手的先验经验），那么同样的出手策略面对不同的对手时，可能得到的环境状态分布是完全不同的（出棋动作相同，得到不同的后续棋面）。因此，如何在策略对环境产生未知影响的作用下得到策略的梯度是一个问题，因为往往实际中采取策略做某个决策时，对环境状态的分布是缺乏先验知识的。

但是幸运的是policy gradient理论给出如下证明：

Policy gradient theorem for episodic case：

可以证明的是，在episodic情况下的效用目标函数的梯度和策略梯度、状态分布、以及状态动作值有如下关系：
$$
\begin{equation}\label{PolicyGradient}
\nabla J(\boldsymbol{\theta}) \propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla \pi(a \mid s, \boldsymbol{\theta})
\end{equation}
$$
其中：

$\nabla J(\boldsymbol{\theta})$ ：是效用目标函数梯度，表示$\theta$的进化方向

$\mu(s)$ ：表示状态分布概率, 在离散情况下通常是以停留在某个状态的时间占比表示，连续情况下则是稳态概率分布

$q_\pi(s, a) $ ：表示策略$\pi$下的状态-动作值函数

$\nabla \pi(a \mid s, \boldsymbol{\theta})$ ：表示使用$\theta$参数化的策略梯度

$\propto $ : 是正比符号，表示效用目标函数梯度正比于右边各项的乘积

上式的证明如下：

$$
\begin{aligned}
\nabla v_\pi(s)
&=\nabla\left[\sum_a \pi(a \mid s) q_\pi(s, a)\right], \quad \text { for all } s \in \mathcal{S} \
&=\sum_a\left[\nabla \pi(a \mid s) q_\pi(s, a)+\pi(a \mid s) \nabla q_\pi(s, a)\right] \quad \text { (product rule of calculus) } \
&=\sum_a\left[\nabla \pi(a \mid s) q_\pi(s, a)+\pi(a \mid s) \nabla \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right)\left(r+v_\pi\left(s^{\prime}\right)\right)\right] \
&=\sum_a\left[\nabla \pi(a \mid s) q_\pi(s, a)+\pi(a \mid s) \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) \nabla v_\pi\left(s^{\prime}\right)\right] \
&=\sum_a\left[\nabla \pi(a \mid s) q_\pi(s, a)+\pi(a \mid s) \sum_{s^{\prime}} p\left(s^{\prime} \mid s, a\right) \quad\right. \text { (unrolling) } \
&\left.\sum_{a^{\prime}}\left[\nabla \pi\left(a^{\prime} \mid s^{\prime}\right) q_\pi\left(s^{\prime}, a^{\prime}\right)+\pi\left(a^{\prime} \mid s^{\prime}\right) \sum_{s^{\prime \prime}} p\left(s^{\prime \prime} \mid s^{\prime}, a^{\prime}\right) \nabla v_\pi\left(s^{\prime \prime}\right)\right]\right] \
&=\sum_{x \in \mathcal{S}} \sum_{k=0}^{\infty} \operatorname{Pr}(s \rightarrow x, k, \pi) \sum_a \nabla \pi(a \mid x) q_\pi(x, a), \
&
\end{aligned}
$$
重复展开后可以得到：
$$
\begin{aligned}
\nabla J(\boldsymbol{\theta}) &=\nabla v_\pi\left(s_0\right) \
&=\sum_s\left(\sum_{k=0}^{\infty} \operatorname{Pr}\left(s_0 \rightarrow s, k, \pi\right)\right) \sum_a \nabla \pi(a \mid s) q_\pi(s, a) \
&=\sum_s \eta(s) \sum_a \nabla \pi(a \mid s) q_\pi(s, a) \
&=\sum_{s^{\prime}} \eta\left(s^{\prime}\right) \sum_s \frac{\eta(s)}{\sum_{s^{\prime}} \eta\left(s^{\prime}\right)} \sum_a \nabla \pi(a \mid s) q_\pi(s, a) \
&=\sum_{s^{\prime}} \eta\left(s^{\prime}\right) \sum_s \mu(s) \sum_a \nabla \pi(a \mid s) q_\pi(s, a) \
& \propto \sum_s \mu(s) \sum_a \nabla \pi(a \mid s) q_\pi(s, a)
\end{aligned}
$$
上式主要是证明了目标梯度函数与状态分布和策略梯度以及动作-状态值函数的关系，具体推导内容比较繁杂，也没啥大用。

Remark

这里需要说明的是策略和状态分布的关系，首先一个环境（或者说Agent）的状态分布取决于某个策略，因为只有某个策略才会衍生出特定的状态概率，比如说在下围棋的时候采取进攻的策略和防守的策略，那么达到某个进攻性棋面的概率和防守性棋面的概率必然是不同的，因此往往在书写环境的状态概率的时候会加上策略的角标，比如上式中$v_{\pi}(s)$

同时，公式$\eqref{PolicyGradient}$因为右手边是状态$s$的**概率密度函数 **$\mu(s)$ 和项$\sum_a q_\pi(s, a) \nabla \pi(a \mid s, \boldsymbol{\theta})$ 的乘积的加和，因此对于离散概率分布而言，公式$\eqref{PolicyGradient}$ 就等同于求$\sum_a q_\pi(s, a) \nabla \pi(a \mid s, \boldsymbol{\theta})$ 的期望：
$$
\begin{aligned}
\nabla J(\boldsymbol{\theta}) & \propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla \pi(a \mid s, \boldsymbol{\theta}) \
&=\mathbb{E}_\pi\left[\sum_a q_\pi\left(S_t, a\right) \nabla \pi\left(a \mid S_t, \boldsymbol{\theta}\right)\right] .
\end{aligned}
$$
于是可以采用梯度上升策略求得对参数$\pmb{\theta}$ 的更新。

梯度上升：
$$
\boldsymbol{\theta}_{t+1}=\boldsymbol{\theta}_t+\alpha \widehat{\nabla J(\boldsymbol{\theta}_t)}
$$
则公式$\eqref{PolicyGradient}$中实际更新$\pmb{\theta}$ :

$$
\begin{equation}
\boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t+\alpha \sum_a \hat{q}\left(S_t, a, \mathbf{w}\right) \nabla \pi\left(a \mid S_t, \boldsymbol{\theta}\right)
\end{equation}
$$

$$
\begin{equation}
\begin{aligned}
\nabla J(\boldsymbol{\theta}) &=\mathbb{E}_\pi\left[\sum_a \pi\left(a \mid S_t, \boldsymbol{\theta}\right) q_\pi\left(S_t, a\right) \frac{\nabla \pi\left(a \mid S_t, \boldsymbol{\theta}\right)}{\pi\left(a \mid S_t, \boldsymbol{\theta}\right)}\right] \
&=\mathbb{E}_\pi\left[q_\pi\left(S_t, A_t\right) \frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}\right)}\right] \
&=\mathbb{E}_\pi\left[G_t \frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}\right)}\right]
\end{aligned}
\end{equation}
$$
其中第二步将动作$a$替换成了实际的样本值$\left( A_t \sim \pi \right)$ ，

第三步中可以将$q_{\pi}$替换成$G_t$是因为$\mathbb{E}_\pi\left[G_t \mid S_t, A_t\right]=q_\pi\left(S_t, A_t\right)$

REINFORCE 算法

综上可以得到REINFORCE算法的表达式来对参数$\theta$进行更新：
$$
\begin{equation}
\boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t+\alpha G_t \frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}
\end{equation}
$$
更新$\theta$是使用一个学习因子$\alpha$、return $G_t$ 以及一个向量构成：

$\alpha$:学习率

$G_t$: 从t时刻起完整的return

$\frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}$ ：采取实际行动的概率的梯度除以采取该行动的概率

第三项在参数空间上表示为最能够在未来在状态$S_t$上再使用动作$A_t$的方向，因此按照这个方向更新$\theta$可以增大该策略在未来重返状态$S_t$时使用动作$A_t$的概率。

“The vector is the direction in parameter space that most increases the probability of repeating the action At on future visits to state St.” (Sutton 和 Barto, 2018, p. 349)

image-20221115204720108

算法中最后的$\nabla \ln{\pi(A_t|S_t,\theta)}$ 等同于$\frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}$ ，原因是$\nabla \ln x=\frac{\nabla x}{x}$，该项成为eligibility vector

REINFORCE方法特点：

  1. 由于其使用了$t$步的return$G_t$，因此本质上还是属于一种蒙特卡洛算法，即需要跑完一个完整的episode然后回溯其回报。
  2. 蒙特卡洛方法的REINFORCE方法较慢，且具有较高的方差
  3. 具有较好的局部收敛性，因为是蒙特卡洛方法，所以有可能收敛到局部最优

为了解决REINFORCE方法的高方差的问题，可以在REINFORCE 方法的基础上，减去一个baseline来降低其方差：
$$
\begin{equation}
\nabla J(\boldsymbol{\theta}) \propto \sum_s \mu(s) \sum_a\left(q_\pi(s, a)-b(s)\right) \nabla \pi(a \mid s, \boldsymbol{\theta})
\end{equation}
$$

这个baseline对方法的收敛不产生影响，因为拆开来看，baseline $b(s)$ 和梯度的乘积为零：
$$
\begin{equation}
\sum_a b(s) \nabla \pi(a \mid s, \boldsymbol{\theta})=b(s) \nabla \sum_a \pi(a \mid s, \boldsymbol{\theta})=b(s) \nabla 1=0 .
\end{equation}
$$
则带baseline的 REINFORCE 方法为：
$$
\begin{equation}
\boldsymbol{\theta}_{t+1} \doteq \boldsymbol{\theta}_t+\alpha\left(G_t-b\left(S_t\right)\right) \frac{\nabla \pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}{\pi\left(A_t \mid S_t, \boldsymbol{\theta}_t\right)}
\end{equation}
$$
算法为：

image-20221115210708813

一般来说baselin的一个较好的选择为可微分的状态值函数 $\hat{v}\left(S_t, \mathbf{w}\right)$ ，参数 $\mathbf{w}$ 是状态值权重，一般使用神经网络中表示该状态值函数。

$a^{\mathbf{w}}$ : 可以设置为 $\alpha^{\mathbf{w}}=\frac{0.1 }{ \mathbb{E}\left[\left|\nabla \hat{v}\left(S_t, \mathbf{w}\right)\right|_\mu^2\right]}$

$a^{\pmb{\theta}}$ : 最佳值取决于奖励的变化范围和策略如何对策略进行参数化

Policy gradient for continuing problems 连续情况下的policy gradient

对于连续情况下的PG，首先要考虑连续情况下的reward，由于使用discount factor的设置容易在函数估计中出问题，因此使用average-reward，顾名思义，就是平均奖励，即agent同样关心当前和之后的回报，而不用像discount factor $\gamma$ 那样的方法对未来回报打连环折扣。

average reward：
$$
\begin{equation}\label{average_reward}
\begin{aligned}
r(\pi) & \doteq \lim {h \rightarrow \infty} \frac{1}{h} \sum{t=1}^h \mathbb{E}\left[R_t \mid S_0, A_{0: t-1} \sim \pi\right] \
&=\lim {t \rightarrow \infty} \mathbb{E}\left[R_t \mid S_0, A{0: t-1} \sim \pi\right] \
&=\sum_s \mu_\pi(s) \sum_a \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right) r
\end{aligned}
\end{equation}
$$
其中$\mu_{\pi}(s)$ 是稳定的状态概率分布，表示趋于无穷时状态的概率稳定分布，是与起始状态$S_0$是什么是无关的，在MDP中这一与初始状态无关的性质成为ergodicity，表达式为：
$$
\begin{equation}
\mu_\pi(s) \doteq \lim {t \rightarrow \infty} \operatorname{Pr}\left{S_t=s \mid A{0: t-1} \sim \pi\right}
\end{equation}
$$

状态的稳态分布概率值的ergodicity特点：

  1. 状态稳定分布概率与起始状态是什么无关，但是与策略是什么有关
  2. 只要遵循策略使用动作，则状态的稳态分布不会改变，但是如果有不是按照策略的动作在过程中出现，则稳态分布会改变。
  3. 达到稳态分布后继续按照策略进行动作，则结果还是稳态分布

$$
\begin{equation}
\sum_s \mu_\pi(s) \sum_a \pi(a \mid s) p\left(s^{\prime} \mid s, a\right)=\mu_\pi\left(s^{\prime}\right)
\end{equation}
$$

在连续情况下的return定义也发生变化，变成了单步reward$R_t$减去平均reward$r(\pi)$：
$$
\begin{equation}
G_t \doteq R_{t+1}-r(\pi)+R_{t+2}-r(\pi)+R_{t+3}-r(\pi)+\cdots
\end{equation}
$$

则连续情况下的效用目标函数也重新定义为平均reward,和公式$\eqref{average_reward}$ 完全相同：

$$
\begin{equation*}
\begin{aligned}
J(\boldsymbol{\theta}) \doteq r(\pi) & \doteq \lim {h \rightarrow \infty} \frac{1}{h} \sum{t=1}^h \mathbb{E}\left[R_t \mid S_0, A_{0: t-1} \sim \pi\right] \
&=\lim {t \rightarrow \infty} \mathbb{E}\left[R_t \mid S_0, A{0: t-1} \sim \pi\right] \
&=\sum_s \mu(s) \sum_a \pi(a \mid s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r \mid s, a\right) r
\end{aligned}
\end{equation*}
$$

这也意味着效用目标函数的关系在连续情况下依然成立：
$$
\begin{aligned}
\nabla J(\boldsymbol{\theta}) & \propto \sum_s \mu(s) \sum_a q_\pi(s, a) \nabla \pi(a \mid s, \boldsymbol{\theta}) \
&=\mathbb{E}_\pi\left[\sum_a q_\pi\left(S_t, a\right) \nabla \pi\left(a \mid S_t, \boldsymbol{\theta}\right)\right] .
\end{aligned}
$$
证明过程参考Sutton第13章

证明过程

对于连续情况下的参数化，一般使用高斯分布作为策略函数参数化的代入载体，即使用$\pmb{\theta}$对高斯函数的两个控制变量$\sigma$(均方差)和均值$\mu$结合输入数据的特征进行参数化。
$$
\begin{equation}
\pi(a \mid s, \boldsymbol{\theta}) \doteq \frac{1}{\sigma(s, \boldsymbol{\theta}) \sqrt{2 \pi}} \exp \left(-\frac{(a-\mu(s, \boldsymbol{\theta}))^2}{2 \sigma(s, \boldsymbol{\theta})^2}\right)
\end{equation}
$$
其中均值$\mu(s,{\pmb{\theta}})$ 可以使用线性方程进行估计,即：
$$
\begin{equation}
\begin{aligned}
&\mu(s, \boldsymbol{\theta}) \doteq \boldsymbol{\theta}_\mu^{\top} \mathbf{x}_\mu(s) \quad \
& \text{且有：}\
&\mu: \mathcal{S} \times \mathbb{R}^{d^{\prime}} \rightarrow \mathbb{R}
\end{aligned}
\end{equation}
$$
标准差按照高斯分布必须是正值，因此一般使用指数函数进行估计：
$$
\begin{equation}
\begin{aligned}
&\sigma(s, \boldsymbol{\theta}) \doteq \exp \left(\boldsymbol{\theta}_\sigma^{\top} \mathbf{x}_\sigma(s)\right)\
& \text{且有：}\
&\mu: \mathcal{S} \times \mathbb{R}^{d^{\prime}} \rightarrow \mathbb{R}
\end{aligned}
\end{equation}
$$
这里区分开来了用于估计两个控制变量的两种$\pmb{\theta}$, 分别为$\boldsymbol{\theta}=\left[\boldsymbol{\theta}_\mu, \boldsymbol{\theta}\sigma\right]^{\top}$ , 一般来说，每个参数都可以使用神经网络来进行训练，再将结果代入高斯函数，形成针对于策略的神经网络形式的eligibiligy vector，即针对于$\pmb{\theta{\mu}}$
$$
\nabla \ln \pi\left(a \mid s, \boldsymbol{\theta}_\mu\right)=\frac{\nabla \pi\left(a \mid s, \boldsymbol{\theta}_\mu\right)}{\pi(a \mid s, \boldsymbol{\theta})}=\frac{(a-\mu(s, \boldsymbol{\theta})) }{\sigma(s, \boldsymbol{\theta})^2}\mathbf{x}\mu(s)
$$
和针对于$\pmb{\theta{\sigma}}$ 的eligibility vector：
$$
\begin{equation}
\begin{aligned}
\nabla \ln \pi\left(a \mid s, \boldsymbol{\theta}_\sigma\right)
=\frac{\nabla \pi\left(a \mid s, \boldsymbol{\theta}_\sigma\right)}{\pi(a \mid s, \boldsymbol{\theta})}
=\left(\frac{(a-\mu(s, \boldsymbol{\theta}))^2}{\sigma(s, \boldsymbol{\theta})^2}-1\right) \mathbf{x}_\sigma(s)
\end{aligned}
\end{equation}
$$