策略梯度

强化学习有3个组成部分：演员，环境，奖励

一轮游戏可以叫做一个回合（episode）或者试验（trial）

游戏最终的总奖励（total reward）

一个完整的轨迹可以写成：T={s1,a1,s2,a2,...,st,at}T = \{s_1, a_1, s_2, a_2, ..., s_t, a_t\}

该轨迹的概率：

pθ(τ)=p(s1)pθ(a1∣s1)p(s2∣s1,a1)pθ(a2∣s2)...=p(s1)∏t=1Tpθ(at∣st)p(st+1∣st,at)\begin{equation} \begin{aligned} p_{\theta}(\tau) &= p(s_1)p_{\theta}(a_1|s_1)p(s_2|s_1, a_1)p_{\theta}(a_2|s_2)...\\ &= p(s_1)\prod\limits_{t = 1}^T p_{\theta}(a_t|s_t)p(s_{t + 1}|s_t, a_t) \end{aligned} \end{equation}

在一场游戏中我们希望总的reward最大，而由于R是一个变量，因此我们希望它的期望越大越好。因此先求R的期望：

Rθ‾=∑τR(τ)pθ(τ)=Eτ∼pθ(τ)[R(τ)]\begin{equation} \begin{aligned} \overline{R_{\theta}} = \sum\limits_{\tau}R(\tau)p_{\theta}(\tau) = E_{\tau \sim p_{\theta}(\tau)}[R(\tau)] \end{aligned} \end{equation}

为了让reward期望最大，要做梯度上升。因此要对reward的期望求导：

▽Rθ‾=∑τR(τ)▽pθ(τ)=∑τR(τ)pθ(τ)▽pθ(τ)pθ(τ)=∑τR(τ)pθ(τ)▽log⁡pθ(τ)=Eτ∼pθ[R(τ)▽log⁡pθ(τ)]≈1N∑n=1NR(τn)▽log⁡pθ(τn)=1N∑n=1NR(τn)▽∑(log⁡p(s1)+∑t=1T(log⁡pθ(at∣st)+log⁡p(st+1∣st,at)))=1N∑n=1N∑t=1TR(τn)▽log⁡pθ(at∣st)\begin{equation} \begin{aligned} \triangledown \overline{R_{\theta}} &= \sum\limits_{\tau} R(\tau)\triangledown p_{\theta}(\tau) = \sum\limits_{\tau}R(\tau)p_{\theta}(\tau)\frac{\triangledown p_{\theta}(\tau)}{p_{\theta}(\tau)}\\ &= \sum\limits_{\tau} R(\tau) p_{\theta}(\tau) \triangledown \log p_{\theta}(\tau)\\ &= E_{\tau \sim p_{\theta}}[R(\tau)\triangledown \log p_{\theta}(\tau)]\\ &\approx \frac{1}{N}\sum\limits_{n = 1}^N R(\tau^n)\triangledown \log p_{\theta}(\tau^n)\\ &= \frac{1}{N} \sum\limits_{n = 1}^N R(\tau^n) \triangledown \sum (\log p(s_1) + \sum\limits_{t = 1}^T(\log p_{\theta}(a_t|s_t) + \log p(s_{t + 1}|s_t, a_t)))\\ &= \frac{1}{N} \sum\limits_{n = 1}^N \sum\limits_{t = 1}^T R(\tau^n) \triangledown \log p_{\theta}(a_t|s_t) \end{aligned} \end{equation}

如果用上述的导数进行梯度上升。可以注意到，如果reward是正的，那么该state下采取这个action的概率上升。如果reward是负的，则对应action的概率下降。

技巧

添加基线

在许多场景下所有的reward都是正的。本来理论上这种情况是不应该影响结果的，因为reward=0的情况的概率逐渐下降，reward越高概率增长越快。

但实际上，我们用采样的方式对期望做估计，这样没有被采样的情况的概率下降，其他情况概率都上升。但是没有被采样的情况中也可能有reward > 0 的情况。因此这种方式不合理。应该有一部分的概率降低，一部分升高。

采用一个基线b。可以让b=E[R(τ)]b = E[R(\tau)]

因此：

▽Rθ‾=1N∑n=1N∑t=1T(R(τn)−b)▽log⁡pθ(at∣st)\begin{equation} \begin{aligned} \triangledown \overline{R_{\theta}} = \frac{1}{N} \sum\limits_{n = 1}^N \sum\limits_{t = 1}^T (R(\tau^n) - b) \triangledown \log p_{\theta}(a_t|s_t) \end{aligned} \end{equation}

分配合适的分数

之前的方式是：只要这个回合的reward是正的，这个回合中的每一个采取的action的概率都会均等的上升。但是有一些action可能并没有给这个回合带来好的作用，只是被其他的action带来的reward给抵消掉了。它带来的总的回报只和后面的action带来的回报有关，与之前已经采取的aciton的reward无关。

如果采样的次数足够多，每一个state-action对 可以被分配到合适的分数，但是在大部分的情况下，采样次数都是不足的。因此需要找到合适的方式分配分数。应该给一个回合中的state-action对分配不同的reward。

因此用折扣的方式计算回报，越近的回报越和当前的action有关，而且当前的action来带的总回报只能在它后面体现：

Rt(τn)=∑t′=tTnγt−t′rt′n\begin{equation} R_t(\tau^n) = \sum\limits_{t' = t}^{T_n}\gamma^{t - t'} r^n_{t'} \end{equation}

也就是：

▽Rθ‾=1N∑n=1N∑t=1T(∑t′=tTnγt−t′rt′n−b)▽log⁡pθ(at∣st)\begin{equation} \begin{aligned} \triangledown \overline{R_{\theta}} = \frac{1}{N}\sum\limits_{n = 1}^N \sum\limits_{t = 1}^T (\sum\limits_{t' = t}^{T_n}\gamma^{t - t'}r_{t'}^n - b)\triangledown \log p_{\theta}(a_t|s_t) \end{aligned} \end{equation}

REINFORCE：蒙特卡罗策略

REINFORCE 是一个采用蒙特卡罗策略的方法，它是基于策略梯度的经典算法，直接学习策略而不学习价值函数。蒙特卡罗策略的方法会等到一个回合结束才更新，而时序差分的方法会一步一更新，更新频率高。

REINFORCE的方法，首先让蒙特卡罗走完一个回合，这样就能计算每一步骤的总收益（带折扣的）。再利用贝尔曼公式，对θ\theta 求导，得到更新公式（包含G），对θ\theta 进行更新。

它的损失的计算采用类似这种形式：∑tGt×softmax(At,π(At∣St))\sum\limits_t G_t \times softmax(A_t, \pi(A_t|S_t))

参数更新的具体过程，没有细看，如果李宏毅的课程中提及，后期会补充