强化学习——学习笔记2

在上一篇文章中对强化学习进行了基本的概述，在此篇文章中将继续深入强化学习的相关知识。

一、什么是DP、MC、TD？

动态规划法（DP）：动态规划法离不开一个关键词，拆分 ，就是把求解的问题分解成若干个子阶段，前一问题的结果就是求解后一问题的子结构。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
举一个简单的例子：
有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问第n个月的兔子总数为多少？

对于这个问题，我们可以根据月份把问题划分为n个阶段，每个月的兔子数，都会等于前一个月的兔子数加上这个月新出生的兔子数，
所以 第n个月的兔子数=第n-1个月的兔子数+新出生的兔子数，而 新出生的兔子数=有繁殖能力的兔子数=两个月前的兔子数，即：第n个月的兔子数=第n-1个月的兔子数+第n-2个月的兔子数。
看着有点混乱？
再举一个例子：
有一个背包，可以装载重量为5kg的物品。
​ 有4个物品，他们的重量和价值如下。
​ 背包：载重5kg
​ 物品1
​ 重量: 1kg
​ 价值:￥3
​ 物品2
​ 重量:2kg
​ 价值:￥4
​ 物品3：
​ 重量: 3kg
​ 价值:￥5
​ 物品4
​ 重量:4kg
​ 价值:￥6
​ 那么请问，在不得超过背包的承重的情况下，将哪些物品放入背包，可以使得总价值最大?
对于上题，总重量是5kg，从四个物品中选，我们要求的问题就是：F(5,4)。
对于第四个物品就只有两种情况，我们可以选择选，或者是不选，不选的话就还是5kg，只从前面三个物品去选，F(5,3)。选的话就是还剩下1kg，从前面三个去选，F(1,3)
则有如下状态转移计算：
F ( 5 , 4 ) = m a x { F ( 1 , 3 ) + 6 , F ( 5 , 3 ) } F(5,4) = max \{ F(1,3) + 6, F(5,3) \} F(5,4)=max{F(1,3)+6,F(5,3)}

F ( W , N ) = m a x { F ( W − W n , N − 1 ) + V n , F ( W , N − 1 ) } F(W,N) =max \{F(W-W_n, N-1)+V_n,F(W,N-1)\} F(W,N)=max{F(W−Wn​,N−1)+Vn​,F(W,N−1)}（w是重量，n是从前n个去选，$W_n$是第n个的重量，$V_n$是第n个的价值）
当重量只剩下0kg的时候，就没有能够选择的物品了，最大价值就是0，所以F(0,n)=0,
当只是剩下的重量大于0，但是已经遍历到从前1个物品中选择时，那么能选择的物品就只有第一个，最大价值就是3，即F(n,1)=3。

从上面两个问题可以看出，动态规划一般只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。

动态规划算法一般分为以下4个步骤：
1、描述最优解的结构
2、递归定义最优解的值
3、按自底向上的方式计算最优解的值 //此3步构成动态规划解的基础。
4、由计算出的结果构造一个最优解 //此步如果只要求计算最优解的值时，可省略

换言之，动态规划方法的最优化问题的两个要素：最优子结构性质，和子问题重叠性质

最优子结构
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。意思就是，总问题包含很多个子问题，而这些子问题的解也是最优的。
重叠子问题
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。

如果已经理解了上文中的动态规划算法基本知识，我们就可以蒋动态规划算法应用到强化学习中了。

求解最优策略$v_{\ast }(s)$

1、最优策略可以通过最大化$q_{\pi }(s,a)$找到。
在上一篇文章中提到如下公式：


2、从上面两个公式中可以看出，若想$q_{\pi }(s,a)$最大，则需要${\pi }_{\ast }(a|s)$最大，也就是${\pi }_{\ast }(a|s)=1$。

结合上面两个理论可以得出下式：

同时在上一篇文章中提出下式：

综合以上两个公式我们最终得出：

回归到DP问题，相当于当知道奖励函数和状态转换函数时，便可以根据下一个状态的价值来更新当前状态的价值，意味着可以把计算下一个可能状态的价值当成一个子问题，而把计算当前状态的价值看做当前问题。
下面展示DP求解最优策略的算法流程

蒙特卡洛法(MC):也称为统计模拟方法，就是通过大量的随机样本来估算或近似真实值，比如近似估算圆的面经、近似定积分、近似期望、近似随机梯度。
有如下例子：
可以通过这个式子来近似计算：圆的面积/ 正方形的面积 = 圆中点的个数/正方形中点的个数

类似的，也可以用蒙特卡洛法来估计一个策略在一个马尔可夫决策过程中的状态价值。考虑到 一个状态的价值是它的期望回报，那么如果我们用策略在马尔科夫决策过程上采样很多条序列，然后计算从这个状态出发的回报再求其期望。公式如下：

时序差分法（TD）:
当面对状态价值函数的求解时

动态规划(DP)会把上述第三个等式的估计值作为目标，不是因为DP要求需要环境模型本身提供期望值，而是因为真实的$v_{\pi }(S_{t+1})$是未知的，所以只能使用当前的估计值$v_{\pi }(S_{t+1})$来替代:

且DP求解状态$S_t$的状态值函数时，需要利用所有后续状态$S_{t+1}$

蒙特卡洛方法(MC)会上述把第一个等式的估计值作为目标，毕竟第一个等式中的期望值是未知的，所以我们用样本回报来代替实际的期望回报。但MC求解状态$S_t$的状态值函数时，需要等一个完整序列结束，因为只有到此时，$G_t$才是已知的:

而时序差分(TD)既要采样得到上述第一个等式的期望值，而且还要通过使用上述第三个等式中当前的估计值V来替代真实值$v_{\pi }$且TD每过一个time step就利用奖励$R_{t+1}$和值函数$V(S_{t+1})$更新一次（当然，这里所说的one-step TD 方法，也可以两步一更新，三步一更新….）

考虑到$G_t=R_t+1+\gamma V(S_{t+1})$，可得:

TD与DP一致的是，时序差分方法也无需等待交互的最终结果，而可以基于下一个时刻的收益$R_{t+1}$和估计值$V(S_{t+1})$就可以更新当前状态的价值函数，不需像MC等到N步以后即等一个完整序列结束后才能更新$V(S_t)$。

总之，TD结合了DP和MC，与DP一致的点是与MC不一致，与DP不一致的点恰又与MC一致，某种意义上来说，结合了前两大方法各自的优点，从而使得在实际使用中更灵活，具体而言如下图所示：

顺带再举一个例子，好比行军打仗时，为了得到更好的行军路线，将军派一人前去探路
MC的做法相当于一条道走到黑 没走个10公里不回头;
DP相当于所有道比如10条道 每条道都走个1公里 不错过任何一条可能成为最好道的可能，最后10条道都走完1公里后才返回汇报;
TD则相当于先选一条道走个1公里即返回汇报，之后再走下一条道的1公里;

参考自：https://blog.csdn.net/v_JULY_v/article/details/128965854