强化学习（一）动态规划、蒙特卡洛方法和时序差分

综述

强化学习是除监督学习、非监督学习的第三种学习方式，通过使代理执行动作去影响环境，从环境得到奖励，进而不断改善自己的动作选择，使得代理可以在完成任务的同时得到最大的奖励。强化学习有以下几个基本元素：
(1) 状态集合S，状态集合的每个状态是指环境的状态
(2) 动作集合A，动作集合指代理可以执行的动作
(3) 策略$\pi$，策略是指代理争对不同的环境状态选择各个动作的概率分布。策略满足马尔可夫性，即策略的概率分布$\pi(a|s)$只与当前状态有关
(4) 衰减率$\gamma$，在选择动作时，考虑的往往不只是当前的奖励，还会考虑后续可能得到的奖励，普遍认为当前的奖励会比后面的奖励重要些，所以后面第$t$步的奖励需要乘上衰减系数$\gamma^t$
(5) 动作状态转移分布$P_{s,a}^{s’}$，表示在环境状态为$s$时，代理执行动作$a$，环境状态变为$s’$的概率
(6) 环境奖励$R_t$，表示代理在第$t$步从环境中得到的奖励
(7) 探索率$\epsilon$，表示代理有可能会探索执行其他动作而不执行当前期望收益最大的动作，从而有一定概率跳出局部最优

除了上面七个要素，还有：
(8) 值函数$v_{\pi}(s)$，表示在策略$\pi$下，代理在环境状态为$s$的期望收益
(9) 动作状态值函数$q_{\pi}(s,a)$，表示在策略$\pi$下，代理在环境状态为$s$下执行动作$a$的期望收益

强化学习需要解决两个问题：
(1) 预测问题，需要根据已有策略计算出值函数
(2) 控制问题，在未知策略的情况下计算出最佳策略和最佳策略下的值函数

动态规划

动态规划解决强化学习，有以下几个前提：
(1) 环境奖励的形式是$R(s,a)$，即代理在环境状态$s$下执行动作$a$得到奖励
(2) 策略$\pi(a|s)$和动作状态转移分布$P_{s,a}^{s’}$满足马尔可夫性，即选取什么动作只与当前环境状态有关，得到什么状态只与当前环境状态和当前执行动作有关
(3) 已知动作状态转移分布$P_{s,a}^{s’}$

预测问题

在已知策略$\pi(a|s)$的情况下，值函数$v_{\pi}(s)$可列出方程：

$$v_{\pi}(s)=\sum_{a}\{\pi(a|s)[R(s,a)+\gamma\sum_{s'}P_{s,a}^{s'}v_{\pi}(s')]\}$$

可以通过解方程的方式得到值函数的解，但一般而言这个方程比较复杂，采用迭代法求解。首先随机设定一个值函数的初始状态，然后不断调用上面的方程迭代更新，直到收敛，收敛后就是值函数的解。

控制问题

首先定义动作状态值函数：

$$q_{\pi}(s,a)=R(s,a)+\gamma\sum_{s'}P_{s,a}^{s'}v_{\pi}(s')$$

在未知策略$\pi(a|s)$的情况下，首先随机设置一个策略，然后基于这个策略计算值函数，利用值函数采用贪心法更新策略：

$$\pi(a|s)=\begin{cases} 1,a=arg\max_a q_{\pi}(s,a)\\0,else \end{cases}$$

更新策略，继续利用策略计算值函数，利用值函数更新策略，直到收敛。此时就可以得到策略的解与值函数的解。

蒙特卡洛方法

动态规划的方法需要知道动作状态转移分布$P_{s,a}^{s’}$，但很多时候这个概率分布我们是不知道的，我们称已知这个分布的强化学习为基于模型的强化学习(model-base)，而不知道这个分布的强化学习为不基于模型的强化学习(model-free)。从动态规划求解强化学习问题中我们知道：

$$v_{\pi}(s)=\sum_{a}\pi(a|s)q_{\pi}(s,a)$$ $$q_{\pi}(s,a)=R(s,a)+\gamma\sum_{s'}P_{s,a}^{s'}v_{\pi}(s')=R(s,a)+\gamma E_{P_{s,a}^{s'}}[v_{\pi}(s')]$$

蒙特卡洛方法的思想就是通过从分布$P_{s,a}^{s’}$中采样$s’$，然后计算这些$v_{\pi}(s’)$的均值来近似期望$E_{P_{s,a}^{s’}}[v_{\pi}(s’)]$。虽然我们不知道$P_{s,a}^{s’}$的具体形式，但是我们在状态$s$下执行了动作$a$后环境总会到达一个状态$s’$，所以我们可以让代理根据当前策略不断采样动作直到到达目标状态，采样多次可以得到多条从起点到重点的链，从这些链中我们就可以近似$E_{P_{s,a}^{s’}}[v_{\pi}(s’)]$了。假设对于状态$s_t$，执行动作$a_t$，其出现的次数为$N(s_t,a_t)$，得到的$v_{\pi}(s’)$的和为$G(s_t,a_t)$，则可以更新$q_{\pi}(s_t,a_t)$为：

$$q_{\pi}(s_t,a_t)=R(s,a)+\gamma\frac{G(s_t,a_t)}{N(s_t,a_t)}$$

假设现在我们又得到一个$s’$，则更新公式为：

$$q_{\pi}^{new}(s_t,a_t)=R(s,a)+\gamma\frac{G(s_t,a_t)+v_{\pi}(s')}{N(s_t,a_t)+1} =q_{\pi}^{old}(s_t,a_t)+\frac{1}{N(s_t,a_t)+1}(R(s,a)+\gamma v_{\pi}(s')-q_{\pi}^{old}(s_t,a_t))$$

所以可以改用在线更新形式，即来一个数据就统计更新一个数据：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\frac{1}{N(s,a)+1}(R(s,a)+\gamma v_{\pi}(s')-q_{\pi}(s,a))$$

现在我们就可以使用上式很好地近似$q_{\pi}(s,a)$了，当我们有无穷多的数据，可以假设$N(s,a)$的作用近似为系数$\alpha$，这个系数$\alpha$表示平均下来每一项加法的作用，所以有：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma v_{\pi}(s')-q_{\pi}(s,a))$$

上面的式子求$q_{\pi}(s,a)$需要用到$v_{\pi}(s)$，求$v_{\pi}(s)$需要用到$q_{\pi}(s,a)$。我们发现策略也是一个概率分布，当可选动作很多时，我们是不可能全部遍历一遍求期望的，所以也可以使用蒙特卡洛的方法去近似，即在求$v_{\pi}(s)$时采样$q_{\pi}(s,a)$求期望得到近似结果，得到下面两个式子：

$$v_{\pi}(s)=v_{\pi}(s)+\alpha(R(s,a)+\gamma v_{\pi}(s')-v_{\pi}(s))$$ $$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma q_{\pi}(s',a')-q_{\pi}(s,a))$$

现在我们就得到了蒙特卡洛方法的近似公式了，对于预测和控制问题，蒙特卡洛方法和动态规划方法的求解思路是一样的，只是蒙特卡洛方法使用统计的近似结果得到$q_{\pi}(s,a)$。在求解控制问题时，蒙特卡洛方法使用一个探索率$\epsilon$调整策略的更新，策略的更新公式为：

$$\pi(a|s)=\begin{cases} 1-\epsilon+\frac{\epsilon}{m},a=arg\max_a q(s,a)\\ \frac{\epsilon}{m},else \end{cases}$$

当$\epsilon$比较大时，鼓励去探索执行当前期望收益不是最大的动作；当$\epsilon$比较小时，则会逐渐收敛到执行当前期望收益最大的动作。为了最终结果可以达到收敛状态，随着迭代次数加深，探索率$\epsilon$会不断缩小。

时序差分

时序差分方法其实就是上面提到的蒙特卡洛方法，在上面的蒙特卡洛方法中，我们只使用了一步去求期望，即：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma q_{\pi}(s',a')-q_{\pi}(s,a))$$

事实上，我们还可以用两步求期望：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(R(s,a)+\gamma R(s',a')+\gamma^2q_{\pi}(s'',a'')-q_{\pi}(s,a))$$

还可以三步，四步直到无穷步求期望。有一种时序差分方法TD($\lambda$)，考虑到所有的步长，为每个步长设置一个权重$(1-\lambda)\lambda^{t-1}$表示步长为$t$的权重，对这些步长加权求和得到$G_{\lambda}(s,a)$，则更新公式变为：

$$q_{\pi}(s,a)=q_{\pi}(s,a)+\alpha(G_{\lambda}(s,a)-q_{\pi}(s,a))$$

更详细的求解过程可以参考这篇文章：https://www.cnblogs.com/pinard/p/9529828.html