> 本文证明强化学习入门问题：K摇臂赌博机的梯度赌博机算法中，偏好函数更新公式：$H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \overline{R_t})(1-\pi_t(A_t))$的合理性。书上可能有些不太好理解，我用较为浅显的语言将每步证明的“why & how”描述出来。

> 引用自：强化学习（第2版）; [加拿大] Richard S. Sutton, [美国] Andrew G. Barto; 俞凯 译

### 前言

在**强化学习入门问题：K摇臂赌博机**的梯度赌博机算法中，提出了偏好函数。偏好函数本身的值并不重要，重要的是一个动作相比于另一个动作的偏好，因此，选择动作的概率分布使用softmax分布：

$$Pr_{A_t = a} = \frac{e^{H_t(a)}}{\sum_{b=1}^{k} e^{H_t(b)}} = \pi_t(a)$$

$\pi_t(a)$表示动作a在t时刻被选择的概率，所有偏好函数的初始值都相同（可为0）。

则，偏好函数更新遵守如下规则：

|$H_{t+1}(A_t) = H_t(A_t) + \alpha (R_t - \overline{R_t})(1-\pi_t(A_t))$|对于被选择的动作$A_t$| (1) |
|---|---|---|
|$H_{t+1}(a) = H_t(a) - \alpha (R_t - \overline(R_t) \pi_t(a))$|对于所有$a \not= A_t$| (2) |

其中，a是一个大于0的数，表示步长。$\overline{R_t}$是时刻t内所有收益的平均值，称为基准项。

**个人思考：为什么更新偏好函数时要考虑概率呢？** 答：对于(1)式，若本身概率较大，则$H_{t+1}$不会加太多，若本身概率$\pi_t=1$，则$H_{t+1}$不用更新。

上述思考有一定道理，**但是这个更新公式的合理性可以在数学上证明**。下面开始证明。

****

### 证明

在精确梯度上升算法中，有：

$$H_{t+1}(a)=H_t(a) + \alpha \frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)}$$

这里，用总体的期望收益定义为性能的衡量指标：

$$ \mathbb{E}[R_t] = \sum_x \pi_t (x) q_* (x)$$

真实的$q_* (x)$（每个动作的真实收益）是未知的，因此无法实现精确的梯度上升。但是可以使用随机梯度上升求近似。

即，开始推导$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)}$的近似：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \frac{\partial}{\partial H_t(a)}\left[ \sum_x \pi_t (x) q_* (x) \right]$$

因为$q_* (x)$客观存在，与$H_t (a)$值无关，所以：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \sum_x q_* (x)  \frac{\partial \pi_t (x)}{\partial H_t(a)}$$

因为$\sum_x \frac{\partial \pi_t (x)}{\partial H_t(a)}=0$（其证明在后文：[动作导数总和为0的证明](#1)），因此可以加入“基准项”$B_t$：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \sum_x (q_* (x) - B_t ) \frac{\partial \pi_t (x)}{\partial H_t(a)}$$

然后，乘以$\pi_t(x) / \pi_t(x)$，有：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \sum_x \pi_t(x) (q_* (x) - B_t ) \frac{\partial \pi_t (x)}{\partial H_t(a)} / \pi_t(x)$$

可以看出，上式实际上是对$\pi_t(x)$分布中的$(q_* (x) - B_t ) \frac{\partial \pi_t (x)}{\partial H_t(a)} / \pi_t(x)$进行期望求值，即：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \mathbb{E} \left[ (q_* (x) - B_t ) \frac{\partial \pi_t (x)}{\partial H_t(a)} / \pi_t(x) \right]$$

其中，变量为动作$x$，这里记为选择的动作$A_t$；并且，将$B_t$取值为$\overline{R_t}$；又有，选择$A_t$动作的回报的期望为$\mathbb{E}[R_t | A_t]$，即$q_* (x)=\mathbb{E}[R_t | A_t]$。因此，有：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \mathbb{E} \left[ (R_t - \overline{R_t} ) \frac{\partial \pi_t ( A_t)}{\partial H_t(a)} / \pi_t( A_t) \right]$$

又有，$\frac{\partial \pi_t (x)}{\partial H_t(a)}=\pi_t(x) (\mathbb{I}_{a=A_t} - \pi_t(a))$，$\mathbb{I}_{a=A_t}$表示，如果$a=x$就取1，否则取0。其证明在后文：[偏好函数导数的推导证明](#2)。

则带入$\frac{\partial \pi_t (x)}{\partial H_t(a)}=\pi_t(x) (\mathbb{I}_{a=A_t} - \pi_t(a))$，有：

$$\frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)} = \mathbb{E} \left[ (R_t - \overline{R_t} ) (\mathbb{I}_{a=A_t} - \pi_t(a)) \right]$$

将上式带入$H_{t+1}(a)=H_t(a) + \alpha \frac{\partial \mathbb{E}[R_t]}{\partial H_t (a)}$，即有

$$H_{t+1}(a)=H_t(a) + \alpha (R_t - \overline{R_t} ) (\mathbb{I}_{a=A_t} - \pi_t(a))$$

即此式子收敛于精确梯度上升。

Q.E.D

### 动作导数总和为0的证明
<span id="1"></span>

证明：$\sum_x \frac{\partial \pi_t (x)}{\partial H_t(a)}=0$：

因为$\sum_x \pi_t (x)=1$，即概率和为1，所以对每一项的$H_t(a)$求导，等式右边为0：

$$\sum_x \frac{\partial \pi_t (x)}{\partial H_t(a)}=0$$

Q.E.D

### 偏好函数导数的推导证明
<span id="2"></span>

证明：$\frac{\partial \pi_t (x)}{\partial H_t(a)}=\pi_t(x) (\mathbb{I}_{a=A_t} - \pi_t(a))$，$\mathbb{I}_{a=A_t}$表示，如果$a=x$就取1，否则取0。

其实，就是一道很简单的$(\frac{f(x)}{g(x)})^{'}$等应用。

简化一下$\frac{\partial \pi_t (x)}{\partial H_t(a)}$，将$H_t(x)$替换为$x$，并在证明中使用下式即可：

$$\pi_t (x) = \frac{e^{x}}{\sum_{i=1}^{k} e^i}$$

证明下式即可：

$$\frac{\partial \pi_t (x)}{\partial x} = \left\{
\begin{aligned}
\pi_t(x)(1-\pi_t(a)) & & x=a \\
-\pi_t(x) \pi_t(a) & & x\not= a \\
\end{aligned}
\right.$$

高中数学内容，应用公式$(\frac{f(x)}{g(x)})^{'} = \frac{f^{'}(x)g(x) - g^{'}(x)f(x)}{g(x)^{2}}$分类讨论，可轻松证明。