深入理解强化学习——多臂赌博机：梯度赌博机算法的数学证明

赌博机：梯度赌博机算法的数学证明"/>

深入理解强化学习——多臂赌博机：梯度赌博机算法的数学证明

分类目录：《深入理解强化学习》总目录

通过将梯度赌博机算法理解为梯度上升的随机近似，我们可以深人了解这一算法的本质。在精确的梯度上升算法中，每一个动作的偏好函数 H t ( a ) H_t(a) Ht​(a)与增量对性能的影响成正比：
H t + 1 ( a ) = H t ( a ) + α ∂ E [ R t ] ∂ H t ( a ) H_{t+1}(a)=H_t(a)+\alpha\frac{\partial E[R_t]}{\partial H_t(a)} Ht+1​(a)=Ht​(a)+α∂Ht​(a)∂E[Rt​]​

这里性能的衡量指标定义为总体的期望收益：
E [ R t ] = ∑ x π t ( x ) q ∗ ( x ) E[R_t]=\sum_x\pi_t(x)q_*(x) E[Rt​]=x∑​πt​(x)q∗​(x)

而增量产生的影响就是上述性能衡量指标对动作偏好的偏导数。当然，我们不可能真的实现精确的梯度上升，因为真实的 q ∗ ( x ) q_*(x) q∗​(x)是不知道的。但是事实上，前面的更新公式采用期望价值时是等价的，即随机梯度上升方法的一个实例。对这个关系的证明只需要用初等的微积分推导几步。首先，我们仔细分析一下精确的性能梯度的定义：
∂ E [ R t ] ∂ H t ( a ) = ∂ ∂ H t ( a ) ∑ x π t ( x ) q ∗ ( x ) = ∑ x q ∗ ( x ) ∂ π t ( x ) ∂ H t ( a ) = ∑ x ( q ∗ ( x ) − B t ) ∂ π t ( x ) ∂ H t ( a ) \begin{aligned} \frac{\partial E[R_t]}{\partial H_t(a)}&=\frac{\partial}{\partial H_t(a)}\sum_x\pi_t(x)q_*(x)\\ &=\sum_xq_*(x)\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ &=\sum_x(q_*(x)-B_t)\frac{\partial \pi_t(x)}{\partial H_t(a)} \end{aligned} ∂Ht​(a)∂E[Rt​]​​=∂Ht​(a)∂​x∑​πt​(x)q∗​(x)=x∑​q∗​(x)∂Ht​(a)∂πt​(x)​=x∑​(q∗​(x)−Bt​)∂Ht​(a)∂πt​(x)​​

其中， B t B_t Bt​被称为“基准项”，可以是任何不依赖于 x x x的标量。我们可以把它加进来，因为所有动作的梯度加起来为0， ∑ x ∂ π t ( x ) ∂ H t ( a ) \sum_x\frac{\partial \pi_t(x)}{\partial H_t(a)} ∑x​∂Ht​(a)∂πt​(x)​，即随着 H t ( a ) H_t(a) Ht​(a)的变化，一些动作的概率会增加或者减少，但是这些变化的总和为0，因为概率之和必须是1。然后我们将求和公式中的每项都乘以 π t ( x ) π t ( x ) \frac{\pi_t(x)}{\pi_t(x)} πt​(x)πt​(x)​，等式保持不变：
∂ E [ R t ] ∂ H t ( a ) = ∑ x π t ( x ) ( q ∗ ( x ) − B t ) ∂ π t ( x ) ∂ H t ( a ) 1 π t ( x ) = E [ ( q ∗ ( A t ) − B t ) ∂ π t ( A t ) ∂ H t ( a ) 1 π t ( A t ) ] = E [ ( R t − R ˉ t ) ∂ π t ( A t ) ∂ H t ( a ) 1 π t ( A t ) ] = E [ ( R t − R ˉ t ) π t ( A t ) ( I ( a = A t ) − π t ( a ) ) 1 π t ( A t ) ] = E [ ( R t − R ˉ t ) ( I ( a = A t ) − π t ( a ) ) ] \begin{aligned} \frac{\partial 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)}\frac{1}{\pi_t(x)}\\ &=E[(q_*(A_t)-B_t)\frac{\partial \pi_t(A_t)}{\partial H_t(a)}\frac{1}{\pi_t(A_t)}]\\ &=E[(R_t-\bar{R}_t)\frac{\partial \pi_t(A_t)}{\partial H_t(a)}\frac{1}{\pi_t(A_t)}]\\ &=E[(R_t-\bar{R}_t)\pi_t(A_t)(\mathbb{I}(a=A_t)-\pi_t(a))\frac{1}{\pi_t(A_t)}]\\ &=E[(R_t-\bar{R}_t)(\mathbb{I}(a=A_t)-\pi_t(a))] \end{aligned} ∂Ht​(a)∂E[Rt​]​​=x∑​πt​(x)(q∗​(x)−Bt​)∂Ht​(a)∂πt​(x)​πt​(x)1​=E[(q∗​(At​)−Bt​)∂Ht​(a)∂πt​(At​)​πt​(At​)1​]=E[(Rt​−Rˉt​)∂Ht​(a)∂πt​(At​)​πt​(At​)1​]=E[(Rt​−Rˉt​)πt​(At​)(I(a=At​)−πt​(a))πt​(At​)1​]=E[(Rt​−Rˉt​)(I(a=At​)−πt​(a))]​

注意，上面的公式其实是一个“求期望"的式子：对随机变量所有可能的取值进行函数求和，然后乘以对应取值的概率。在上面我们选择 B t = R ˉ t B_t=\bar{R}_t Bt​=Rˉt​，并且将 R ˉ t \bar{R}_t Rˉt​用 q ∗ ( A t ) q_*(A_t) q∗​(At​)代替。这个选择是可行的，因为 E [ R t ∣ A t ] = q ∗ ( A t ) E[R_t|A_t]=q_*(A_t) E[Rt​∣At​]=q∗​(At​)，而且 R t R_t Rt​在给定 A t A_t At​的情况下与任何其他东西都不相关。很快我们就可以确定 ∂ π t ( x ) ∂ H t ( a ) = π t ( x ) ( I ( a = A t ) − π t ( a ) ) \frac{\partial \pi_t(x)}{\partial H_t(a)}=\pi_t(x)(\mathbb{I}(a=A_t)-\pi_t(a)) ∂Ht​(a)∂πt​(x)​=πt​(x)(I(a=At​)−πt​(a))，表示如果 a = x a=x a=x就取1，否则取0。回想一下，我们的计划是把性能指标的梯度写为某个东西的期望，这样我们就可以在每个时刻进行采样，然后再进行与采样样本成比例地更新。将公式 H t + 1 ( a ) = H t ( a ) + α ∂ E [ R t ] ∂ H t ( a ) H_{t+1}(a)=H_t(a)+\alpha\frac{\partial E[R_t]}{\partial H_t(a)} Ht+1​(a)=Ht​(a)+α∂Ht​(a)∂E[Rt​]​中的性能指标的梯度用一个单独样本的期望值代替，可以得到：
H t + 1 ( a ) = H t ( a ) + α ( R t − R ˉ t ) ( I ( a = A t ) − π t ( a ) ) H_{t+1}(a)=H_t(a)+\alpha(R_t-\bar{R}_t)(\mathbb{I}(a=A_t)-\pi_t(a)) Ht+1​(a)=Ht​(a)+α(Rt​−Rˉt​)(I(a=At​)−πt​(a))

我们发现这和我们在文章《深入理解强化学习——多臂赌博机：梯度赌博机算法的基础知识》中给出的原始算法是一致的。现在我们只需要证明我们的假设 ∂ π t ( x ) ∂ H t ( a ) = π t ( x ) ( I ( a = A t ) − π t ( a ) ) \frac{\partial \pi_t(x)}{\partial H_t(a)}=\pi_t(x)(\mathbb{I}(a=A_t)-\pi_t(a)) ∂Ht​(a)∂πt​(x)​=πt​(x)(I(a=At​)−πt​(a))就可以了，在本文中就不详细阐述该假设的证明，但可以告诉大家这个假设是正确的。

上文我们已经证明了梯度赌博机算法的期望更新与期望收益的梯度是相等的，因此该算法是随机梯度上升算法的一种。这就保证了算法具有很强的收敛性。需要注意的的是，对于收益基准项，除了要求它不依赖于所选的动作之外，不需要其他任何的假设。例如，我们可以将其设置为0或1000，算法仍然是随机梯度上升算法的一个特例。基准项的选择不影响算法的预期更新，但它确实会影响更新值的方差，从而影响收敛速度。采用收益的平均值作为基准项可能不是最好的，但它很简单，并且在实践中很有效。

参考文献：
[1] 张伟楠, 沈键, 俞勇. 动手学强化学习[M]. 人民邮电出版社, 2022.
[2] Richard S. Sutton, Andrew G. Barto. 强化学习（第2版）[M]. 电子工业出版社, 2019
[3] Maxim Lapan. 深度强化学习实践（原书第2版）[M]. 北京华章图文信息有限公司, 2021
[4] 王琦, 杨毅远, 江季. Easy RL：强化学习教程 [M]. 人民邮电出版社, 2022