蒙特卡罗法

之前我们讲过使用策略迭代、价值迭代和泛化迭代，但是算法的前提是需要知道环境的状态转移概率，即对环境的运作方式十分清楚（Model-based Problem），故可以用动态规划这样的算法。
但是很多时候，环境是未知的，不知道状态转移概率，故不能使用BELLMAN EQUATION对值函数进行更新
$\upsilon _\pi(s_{t}) = \sum_{a_t} \pi(a_t|s_t) \sum_{s_{t+1}}p(s_{t+1}|s_t,a_t) [r_{t+1} +\upsilon _\pi(s_{t+1})]$υπ​(st​)=at​∑​π(at​∣st​)st+1​∑​p(st+1​∣st​,at​)[rt+1​+υπ​(st+1​)]
所以当状态转移概率$\pi(a_t|s_t)$π(at​∣st​)无法知道的时候，我们把公式转变成
$q_\pi(s_t,a_t)=E_{s_{t+1}\sim p,\pi}[\sum^\infty_{k=0}\gamma^kr_{t+k}]$qπ​(st​,at​)=Est+1​∼p,π​[k=0∑∞​γkrt+k​]
我们可以用蒙特卡罗法随机采样来估计期望，通过不断与环境交互得到大量样本，用样本期望代替q值
$q(s,a)\simeq \frac 1 N \sum ^N _{i=1}[r^i_1+r^i_2+...]\ \ \ \ \ \ \text{有限序列}$q(s,a)≃N1​i=1∑N​[r1i​+r2i​+...]      有限序列
$q(s,a)\simeq \frac 1 N \sum ^N _{i=1}\sum^\infty_{k=0}\gamma^kr_{t+k}\ \ \ \ \ \ \text{无限序列}$q(s,a)≃N1​i=1∑N​k=0∑∞​γkrt+k​      无限序列
假设得到N个样本，求这N个样本的回报期望
那么我们同样使用和之前相同的policy_improve，即：
$\pi(s)=argmax_aq(s,a)$π(s)=argmaxa​q(s,a)
这里简单说明一下q值的迭代更新方法:
令状态行为价值为$q$q，当前时间为$t$t，积累的轨迹数为$N$N，我们要求的是$q^N_t$qtN​，已知之前的$q^{N-1}_t$qtN−1​和N，每一个轨迹的价值$\hat{q}^i_t$q^​ti​，可以得到
$q^N_t=\frac 1 N \sum^N_{i=0}\hat q^{i}_t\\ =\frac 1 N[\sum^{N-1}_{i=0}\hat q^{i}_t+\hat q^{N}_t]\\ =\frac 1 N \times (N-1)q^{N-1}_t+\frac 1 N\hat q^{N}_t \\ =q^{N-1}+\frac 1 N(\hat q^{N}_t-q^{N-1})$qtN​=N1​i=0∑N​q^​ti​=N1​[i=0∑N−1​q^​ti​+q^​tN​]=N1​×(N−1)qtN−1​+N1​q^​tN​=qN−1+N1​(q^​tN​−qN−1)所以每一个时刻我们都可以计算出q*
通过程序我们可以看到蒙特卡罗方法比前面知道转移概率的稍微差一点，毕竟我们对模型是未知的，可以理解，但是除此之外还有一个原因。
当我们的状态空间过大，比如游戏的图像可以是无穷多个的时候怎么办，并且状态的概率分布很难得到。我们可以使用$\epsilon-greedy$ϵ−greedy算法探索其他非最佳动作到达的状态
实验证明，在蛇行棋游戏中，使用$\epsilon-greedy$ϵ−greedy与蒙特卡罗法同样可以到达动态规划到达的分数。

---

但是，蒙特卡罗也不是完美的，当游戏持续实践比较长的时候，长期回报的方差比较大，通过大数定律收敛的速度十分慢，很困难。（在蛇棋游戏中导致方差大的因素有很多，每一次扔骰子的数字都不同，那么到达重点的时刻也不同，同一个位置计算的到的长期回报也会不一样【比如有时候扔到3就GG，扔到2就由*下降到起点附近的情况】）
并且采样的时候没有考虑到every-visit的情况，一次轨迹中若多次到达同一点，那么计算回报时候，不加区分的将两个长期回报等权重的加在一起，但是先前到达的回报和之后到达的回报差异较大，这一会使得方差增大，回报的期望难以收敛。虽然可以改为first-visit的计算方法只计算第一次到达某状态的回报
但是还是方差很大（很多因素）
但是，可以证明，蒙特卡罗在估计上是具有无偏估计但是方差较高的估计

---

TD法

下面提出一种可以使算法中更新数值更稳定，跨度（方差）更小的算法，TD法，因为TD法的q值迭代公式是使用下一刻的回报和价值得到的，并没有涉及整个轨迹，数值边好了很多
$q_t(s,a)=q_{t-1}(s,a)+\frac 1 N [r(s')+\gamma q(s',a')-q_{t-1}(s,a)]$qt​(s,a)=qt−1​(s,a)+N1​[r(s′)+γq(s′,a′)−qt−1​(s,a)]从更新公式上看，TD法通过下一刻的价值更新前一时刻的价值，似乎是承认了下一时刻的回报和价值足够优秀，从而利用这个最优子结构进行更新，这和动态规划的思想一致。只不过TD方法只考虑了当前一步的回报，所以当整体系统没有到达最优的时候，这样的估计都是存在偏差的。
而TD法又分为两种算法：
1.SARSA
$q_t(s,a)=q_{t-1}(s,a)+\frac 1 N [r(s')+\gamma q_{t-1}(s',a')-q_{t-1}(s,a)]$qt​(s,a)=qt−1​(s,a)+N1​[r(s′)+γqt−1​(s′,a′)−qt−1​(s,a)]
2.Q-learning
$q_t(s,a)=q_{t-1}(s,a)+\frac 1 N [r(s')+\gamma max_a q_{t-1}(s',a')-q_{t-1}(s,a)]$qt​(s,a)=qt−1​(s,a)+N1​[r(s′)+γmaxa​qt−1​(s′,a′)−qt−1​(s,a)]
算法的差别只有一项：SARSA遵循了交互序列，根据下一步的真实行动进行价值估计；Q-learning没有遵循交互序列，而是在下一时刻选择了使得价值最大的行动，这分别对应着两种策略评估方式：On-Policy和Off-Policy。Off-Policy选择了来自其他策略的交互序列的子部分代替了原本的交互序列。
从思想上，OffPolicy算法结合了子部分的最优价值，希望每一次都使用前面迭代累积的最优结果进行更新，这也给Q-learning带来了一些问题，由于是使用最有价值的行动代替交互时使用的行动进行更新，在估计的时候就有可能造成对q的过高估计，而没有采样到的q和采样到的q之间的差距便会加大。

在书上可以证明Q-learning的收敛性，但是有点难，就我来说看不懂，有心去的同学可以去书中查看，必定收获颇多

---

DQN

在一些S和A（状态空间和行为空间）比较小的环境下，Q表的存储还比较容易，但是当SA增大，Q表在很多情况下往往过大，既然Q是S，A->S’的映射，我们很自然的想要用监督学习的方法回归Q值以此减少SxQ的参数量。
其实，Q表也是一种模型，只是Q表这个模型的参数很多，每一个点的Q都完美拟合，在现实情况下，表格Q是大到很难训练的，而拟合得到的模型可以训练，只是收敛性没有保证（Q-learning在书中有证明过收敛），所以如果没有选好一个表达能力强的模型，有可能会出现很难收敛的情况。

DQN的介绍

DQN除了使用卷积神经网络来回归q值之外还有两个特性
1.Replay Buffer：使得sample后的数据独立同分布，且sample后平均的价值期望更接近真实值
2.Target Network：
我们在Q-learning中可以将计算公式分为两个步骤：

• 当前状态行为下的价值目标值：$\Delta q_t(s,a)=r(s')+\gamma max_a q_{t-1}(s',a')$Δqt​(s,a)=r(s′)+γmaxa​qt−1​(s′,a′)
• 网络模型的更新：$q_t(s,a)=q_{t-1}(s,a)+\frac 1 N [\Delta q_t(s,a)-q_{t-1}(s,a)]$qt​(s,a)=qt−1​(s,a)+N1​[Δqt​(s,a)−qt−1​(s,a)]
  由于Q-learning的特性，数据样本的差异性会造成一定的价值差异，这种差异造成的数据不稳定，使得每一轮迭代都可能产生一些波动，如果按照
  $q_t(s,a)=q_{t-1}(s,a)+\frac 1 N [r(s')+\gamma max_a q_{t-1}(s',a')-q_{t-1}(s,a)]$qt​(s,a)=qt−1​(s,a)+N1​[r(s′)+γmaxa​qt−1​(s′,a′)−qt−1​(s,a)]
  公式计算，波动会立即反应到下一个迭代的计算之中，这样就很难得到平稳的模型，
  所以DQN引入两个网络，Target Network和Behavior Network，开始的时候参数相同，Behavior Network负责产生数据，然后学习的时候，原本Q-learning的目标价值是上次更新的q值下的计算的到的（前面说过，如果上次更新的q值变化很不稳定，那么这个q值计算出来的结果再去给网络模型更新，训练出来的网络就很不平稳），而这次不是上一次q值计算，而是用TargetNetwork的输出代替我们这里计算的价值目标值$\Delta q_t(s,a)$Δqt​(s,a)，然后用该$\Delta q_t(s,a)$Δqt​(s,a)和BehaviorNetwork的估计值（之前参数估计的价值）相比较得到$\Delta q_t(s,a)-q_{t-1}(s,a)$Δqt​(s,a)−qt−1​(s,a)，进而更新Behavior Network，每一次训练一定轮数之后，Behavior Network的参数就会同步给Target Network

DQN的算法流程图

DQN实现

在Baselines中有关于DQN的实现
就在这个baselines/deepq中
由于代码中包含了除了DistributionalDQN的所有rainbow组建，这里不做讲解，需要用到的时候再进行书本查看、源码阅读与使用

DQN变种

Priority Replay Buffer

权重：TD-Error表示->不可靠
样本出现概率：$\Large P(i)=\frac{p_i^\alpha}{\sum_k p _k^\alpha}$P(i)=∑k​pkα​piα​​
线段树

可以更搞笑的使用其中的样本，让模型更多的选择能够让模型提高的样本

Dueling DQN

将值函数拆解成两部分，使得模型更容易训练的同时，可以表达更多有用的信息

DQN from Demonstration

解决了Q-learning的冷启动问题，也平衡了监督学习和强化学习两部分对模型的影响力

Distributional DQN

将模型的输出从计算价值期望改为计算价值分布，使得模型可以学习更多有价值的信息

Noisy DQN

通过给参数增加噪声的方式为模型增加一定的探索能力，这种方式更具有可控性

Rainbow

Rainbow模型继承了上述模型的优点，给出了多种特性融合的可能性