强化学习入门知识与经典项目分析2.1
之前的所有文章基于环境动力学规则，即状态转移概率\(P_{ss'}^a\)已知的情况下分析的，而在实际的更多情况下，环境动力学未知，不知道状态转移概率，这一类问题被称为无模型问题。本篇文章主要是介绍基于完整采样的蒙特卡罗强化学习。
主要的学习资源是五个:
- B站许志钦老师的视频（主要入门理论）https://www.bilibili.com/video/BV15a4y1j7vg?spm_id_from=333.999.0.0
- 书籍《强化学习入门：从原理到实践》（叶强等著，机械工业出版社）
- github中的配套资源 https://github.com/qqiang00/Reinforce
- 书籍《强化学习精要：核心算法与TensorFlow实现》（冯超著，中国工信出版集团）
- Sutton的强化学习导论第二版 http://incompleteideas.net/book/the-book-2nd.html
1.无模型问题算法的设计思路
因为不知道状态转移概率，就无法利用贝尔曼公式进行值函数更新。参考人类的思路，可以采用不断尝试的方法，就得到了无模型问题的算法大体思路：
- 确定一个初始策略
- 利用这个策略参与该环境交互过程，得到一些序列\(\{s_1,a_1,s_2,a_2,...\}\)
- 一旦参与该环境交互过程的序列达到一定数目，就可以认为这些序列代表了当前策略与环境交互的表现，将这些序列聚合起来，得到状态对应的值函数。
- 得到值函数也就是完成了策略评估的过程，这样就继续按照策略迭代的方法进行策略提升。重复2-4步骤直到策略更新完成。
上述过程介绍了学习的过程，那么学习的关键落到了下面的两个问题：
- 如何使用这些序列进行评估
- 如何使用这些序列进行控制
2.蒙特卡罗预测简述
蒙特卡罗预测的目的是要根据采样到的序列，按照固定策略\(π\)学习得到价值函数\(V_π\)。
可以回顾，针对一个状态行为链：
收获的定义为
\[G_t = R_{t+1}+γR_{t+2}+...+γ^{T-1}R_T \]价值函数的定义为
\[V_π(s)=E_π[G_t|S_t=s] \]在Sutton强化学习一书中提到了两种预测方法：首次访问、每次访问蒙特卡罗评估。前者是仅把状态序列中第一次出现该状态时的收获值纳入收获平均值的计算中，后者是针对一个状态序列中每次出现该状态时都计算对应的收获值并纳入收获值的计算中。
下图为B站许志钦老师的授课笔记中的首次访问蒙特卡罗算法流程：
下图为B站许志钦老师的授课笔记中的每次访问蒙特卡罗算法流程：
在求解状态收获的平均值的过程中，介绍一种非常实用的不需要存储所有历史收获的计算方法：累进更新平均值，具体公式如下：
\[\begin{aligned} u_k&=\dfrac{1}{k}\sum_{j=1}^kx_j\\ &=\dfrac{1}{k}(x_k+\sum_{j=1}^{k-1}x_j)\\ &=\dfrac{1}{k}(x_k+(k-1)u_{k-1})\\ &=u_{k-1}+\dfrac{1}{k}(x_k-u_{k-1}) \end{aligned} \]如果把该式中平均值和新数据分别看成是状态的价值和该状态的收获，那么该公式就变成了递增式的蒙特卡罗法更新状态价值。其公式如下：
\[N(S_t)\larr N(S_{t})+1\\ V(S_t)\larr V(S_t)+\dfrac{1}{N(S_t)}(G_t-V(S_t)) \]如果无法精确统计被访问的次数，可以用系数α代替，此时公式变为：
\[V(S_t)\larr V(S_t)+\alpha(G_t-V(S_t)) \]3.蒙特卡罗控制(上)
根据优化控制过程中是否利用已有或他人的经验策略来改进我们自身的控制策略，我们可以将这种优化控制分为两类:
同策略学习：其基本思想是个体已有一个策略，并且遵循这个策略进行采样，或者说采取一系列该策略下产生的行为，根据这一系列行为得到的奖励，更新状态函数，最后根据该更新的价值函数来优化策略得到较优的策略。
异策略学习: 其基本思想是，虽然个体有一个自己的策略，但是个体并不针对这个策略进行采样，而是基于另一个策略进行采样，这另一个策略可以是先前学习到的策略，也可以是人类的策略等一些较为优化成熟的策略，通过观察基于这类策略的行为，或者说通过对这类策略进行采样，得到这类策略下的各种行为，继而得到一些奖励，然后更新价值函数，即在自己的策略形成的价值函数的基础上观察别的策略产生的行为，以此达到学习的目的。这种学习方式类似于“站在别人的肩膀上可以看得更远”。
异策略我还没有学到，所有本系列都是同策略的。
贝尔曼公式得到的状态-行为价值函数如下：
\[q_π(s,a)=R_s^a+γ\sum_{s'\in S}V_{π}(s')P_{ss'}^a \]在无模型问题中，公式需要转变为
\[q_π(s_t,a_t)=E_{s_{t+1}-p,π}[\sum_{k=0}^{\infty}γ^kR_{t+k}] \]蒙特卡罗方法是一种通过随机采样来估计期望值的方法。假设通过一些方法，从状态s和行动a开始不断地与环境交互，得到了大量的样本序列
\[\{s_t,a_t,s_{t+1}^i,a_{t+1}^i,...\}_{i=1}^N \]对应的回报序列为\(\{R_t,R_{t+1}^i...\}_{i=1}^N\)，这里的i是表示第i个序列。
我们可以通过这些样本序列逼近真实期望值，那么公式就可以近似等于：
如果序列是有限的，我们也可以直接使用序列产生的回报和计算价值：
\[q(s,a)\approx \dfrac{1}{N}\sum_{i=1}^{N}[R_1^i+R_2^i+...] \]下图是sutton书中的对应算法：
但是这个算法可能无法得到最优的策略，不具有收敛性，下图是叶强老师举得例子：
sutton对此提供了改进方案：??贪婪策略
下面证明了??贪婪策略提升：
\[\begin{aligned} q_π(s,π'(s))&=\sum_{a\in A}π'(a|s)q_π(s,a)\\ &=?/m\sum_{a\in A}q_π(s,a)+(1-?)\underset{a\in A}{max}q_π(s,a)\\ &\ge?/m\sum_{a\in A}q_π(s,a)+(1-?)\sum_{a\in A}\dfrac{π(a|s)-?/m}{1-?}q_π(s,a)\\ &=\sum_{a\in A}π(a|s)q_π(s,a)=V_π(s) \end{aligned} \]4.蒙特卡罗控制(下)
在?-贪婪探索算法下，始终只能得到基于某一策略下的近似Ｑ函数，且该算法没有一个终止条件，因为它一直在进行探索。因此必须关注以下两个方面：一方面不想丢掉任何更好信息和状态，另一方面随着策略的改善，我们最终希望能终止于某一个最优策略，因为事实上最优策略不应该包括一些随机行为选择。为此引入了另一个理论概念：GLIE。
GILE包含两层意思，一是所有的"状态-行为对"都会被无限探索：
\[\underset{k \to \infty}{lim} N_k(s,a)=\infty \]二是随着采样趋向无穷多，策略收敛至一个贪婪策略：
\[\underset{k \to \infty}{lim}π_k(a|s)=1 \]存在如下定理：基于GLIE的蒙特卡罗控制能收敛至最优的状态行为价值函数：
\[Q(s,a) \to q^*(s,a) \]这个定理是有概率论中的大数定理和前面文章中已经证明的贪婪策略收敛于最优策略推论得到的。
这就给出基于GLIE的蒙特卡罗控制流程：
- 基于给定策略π，采样第k个完整的状态序列：\(\{S_1,A_1,R_2,···,S_T\}\)
- 对于该状态序列里出现的每一状态行为对\((S_t, A_t)\)，更新其计数N和行为价值函数Q：
- 基于新的行为价值函数Q以如下方式改善策略：
在实际应用中，?的取值可不局限于取1/k，只要符合GLIE特性的设计均可以收敛至最优策略。