DQN（Deep Q-learning）入门教程（三）之蒙特卡罗法算法与Q-learning算法
蒙特卡罗法
在介绍Q-learing算法之前，我们还是对蒙特卡罗法（MC）进行一些介绍。MC方法是一种无模型（model-free）的强化学习方法，目标是得到最优的行为价值函数\(q_*\)。在前面一篇博客中，我们所介绍的动态规划算法则是一种有模型的算法。那么问题来了，什么是模型（model）？模型其实就是我们在第一篇博客：DQN（Deep Q-learning）入门教程（一）之强化学习介绍种所介绍的状态转化模型： \(P_{ss’}^a\)。
在动态规划解决问题的时候，我们是已知\(P_{ss’}^a\)，但是实际上我们也可能对于\(P_{ss’}^a\)我们是未知的。那么怎么办呢？此时，我们使用经验平均来解决这个问题。其中的思想有点类似大数定理，尽管我不知道模型概率是什么，但是我可以使用无数次的实验来逼近这个概率。
任然是分为两个部分：
- 策略评估
- 策略控制
- 探索性
- 无探索性
策略评估
前面我们说了，我们使用多次实验来解决model-free，因此我们将历史实验数据称之为经验，然后进行平均求得的价值函数当成价值函数当作结果。
-
经验：我们使用策略做很多次实验，每次实验都是从最初状态到终止状态。假如一次实验所得得到的数据如下：\(S_1,A_1,R_2,S_2,A_2,…S_t,A_t,R_{t+1},…R_T, S_T\)，则在状态\(s\)处获得的回报是：\(G_{t}(s)=R_{t+1}+\gamma R_{t+2}+\cdots+\gamma^{T-1} R_{T}\)。而我们就可以进行多次实验，就可以得到多份数据。
-
平均：平均有两种方式，第一次访问蒙特卡罗方法和每次访问蒙特卡罗方法。假如我们做实验的到的数据如下，现在需要来计算\(G(s)\):
-
第一次访问蒙特卡罗方法：只是使用每次实验第一次出现状态\(s\)的放回值。比如说上图中\(G_{11},G_{21}\)，但是不使用\(G_{12}\)。
\[\begin{equation}v(s)=\frac{G_{11}(s)+G_{21}(s)+\cdots}{N(s)}\end{equation} \\
N(s)代表出现的次数
\] -
每次访问蒙特卡罗方法：则就是只要出现过，就使用，比如说上图中的\(G_{11},G_{12},G_{21}\)。
\[\begin{equation}v(s)=\frac{G_{11}(s)+G_{12}(s)+\cdots+G_{21}(s)+\cdots}{N(s)}\end{equation}
\]
-
不过我们可以想一想，这样计算平均值会有什么问题？浪费内存空间，因为我们需要储存该状态所有历史实验数据然后再取平均。因此我们对取平均值的方法进行改进，改进的原理如下：
\]
也就是说，状态价值公式可以改写为：
N\left(s\right)=N\left(s\right)+1 \\
V_{k+1}\left(s\right)=V_{k}\left(S\right)+\frac{1}{N\left(S\right)}\left(G_{t}-V_{k}\left(S\right)\right)
\end{array}\end{equation}
\]
这样我们存储上一步的状态价值函数就