不基于模型的强化学习问题定义
在动态规划一文中，我们提到强化学习的两个基本问题：预测问题与控制问题。在处理上述两种问题的时候，其状态转化概率矩阵\(P\)都是已知的，即MDP已知（MDP需要状态转化概率矩阵计算\(P_{ss'}^a\))，对于这样的问题，我们称为基于模型的强化学习问题。当事先并不知道模型状态转化矩阵时，强化学习的两个基本问题可以被描述为：（1）给定状态集\(S\)，动作集\(A\)，即时奖励\(R\)，衰减因子\(\gamma\)，给定策略\(\pi\)，求解该策略的状态价值函数\(v(\pi)\)；（2）给定状态集\(S\)，动作集\(A\)，即时奖励\(R\)，衰减因子\(\gamma\)，探索率\(\epsilon\)，求解最优的动作价值函数\(q_*\)以及最优策略\(\pi_*\)。本文使用的蒙特卡洛法就是上述不基于模型的强化学习问题。
蒙特卡洛法求解特点
蒙特卡洛法是一种近似求解问题的方法，它通过采样若干经历完整的状态序列（episode）来估计状态的真实价值。相比于动态规划法，其特点为不需要依赖于模型状态转化概率，且其从经历过的完整序列学习，完整的经历越多，学习的效果越好。
蒙特卡洛法求解强化学习预测问题
假设给定的策略\(\pi\)产生了一个完整的状态序列如下：
\[ S_1,A_1,R_2,S_2,A_2,...S_t,A_t,R_{t+1},...R_T, S_T \]
马尔科夫决策过程中对于价值函数的定义为：
\[ v_{\pi}(s) = \mathbb{E}_{\pi}(G_t|S_t=s ) = \mathbb{E}_{\pi}(R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3}+...|S_t=s) \]
可以看出每个状态的价值函数\(v\)等于所有该状态收获在策略分布\(\pi\)下的期望。同时这个收获是通过后续的奖励与对应的衰减乘积后求和得到的。在蒙特卡洛法中，求一个状态对应的\(v\)，只需要求出所有完整序列中该状态出现时候的收获再取平均值即可近似求解。即：
\[ G_t =R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3}+... \gamma^{T-t-1}R_{T} \]
\[ v_{\pi}(s) \approx average(G_t), s.t. S_t=s \]
当一个状态在完整的状态序列中出现一次以上时，有两种考虑方法。第一种是仅仅把状态序列中第一次出现该状态时的\(G(t)\)纳入到收获平均值的计算中；另一种是针对一个状态序列中每次出现该状态，都计算对应的\(G(t)\)并纳入收获平均值的计算中。在完整的经历样本序列比较少的场景下第二种方法会更为适用。
本算法可以使用累进更新平均值( incremental mean )进行优化：
\[ N(S_t) = N(S_t) +1 \]
\[ V(S_t) = V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t) ) \]
当数据量巨大时，\(N(S_t)\)可以使用常数系数\(\alpha\)替代：
\[ V(S_t) = V(S_t) + \alpha(G_t - V(S_t) ) \]
蒙特卡洛法求解强化学习控制问题
蒙特卡洛法求解控制问题的思路和动态规划的思路相似，动态规划中在每轮迭代中先做策略评估，计算出\(v_k(s)\),然后基于一定的方法（比如贪婪法）更新的当前策略\(\pi\)。
和动态规划相比，蒙特卡洛法不同之处体现在三点：一是预测问题策略评估的方法不同，第二是蒙特卡洛法一般是优化最优动作价值函数\(q_*\)，而不是状态价值函数\(v_*\)。三是动态规划一般基于贪婪法更新策略。而蒙特卡洛法一般采用\(\epsilon\)-贪婪法进行更新。\(\epsilon\)-贪婪法先假设一个较小的\(\epsilon\)值，使用\(1-\epsilon\)的概率贪婪的选择目前认为是最大行为价值的行为，而使用\(\epsilon\)的概率随机的从所有行为中选择。 为了使算法可以收敛，一般\(\epsilon\)会随着算法的迭代过程逐渐减小，并趋于0。
蒙特卡洛法控制问题算法流程
输入：状态集\(S\)，动作集\(A\)，即时奖励\(R\)，衰减因子\(\gamma\)，探索率\(\epsilon\)
输出：最优的动作价值函数\(q_*\)以及最优策略\(\pi_*\)
初始化所有的动作价值\(Q(s,a) = 0\)，状态次数\(N(s,a) = 0\)，采样次数\(k=0\)，随机初始化一个策略
\(k=k+1\)，基于策略\(\pi\)进行第\(k\)次蒙特卡洛采样，得到一个完整的状态序列
\[ S_1,A_1,R_2,S_2,A_2,...S_t,A_t,R_{t+1},...R_T, S_T \]
对于状态序列里出现的每一对状态行为对\((S_t, A_t)\)，计算收获\(G_t\)，更新其计数\(N(s,a)\)和行为价值函数\(Q(s,a)\)：
\[ G_t =R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+3}+... \gamma^{T-t-1}R_{T} \]
\[ N(S_t, A_t) = N(S_t, A_t) +1 \]
\[ Q(S_t, A_t) = Q(S_t, A_t) + \frac{1}{N(S_t, A_t)}(G_t - Q(S_t, A_t) ) \]
基于新计算出的动作价值，更新当前的策略：
\[ \epsilon = \frac{1}{k} \]
\[ \pi(a|s)= \begin{cases} \epsilon/m + 1- \epsilon & {if\; a^{*} = \arg\max_{a \in A}Q(s,a)}\\ \epsilon/m & {else} \end{cases} \]
如果所有的\(Q(s,a)\)收敛，则有最优的动作价值函数\(Q(s,a)\)以及最优策略\(\pi(a|s)\)。
蒙特卡洛法小结
蒙特卡洛法不像动态规划法需要考虑所有可能的后续状态，而且其计算也不需要事先知道环境转化模型，因此可以用于海量数据的复杂模型。其缺点在于每次采样都需要一个完整的状态序列。