本节主要内容导览

首先，我们介绍不具备完整环境知识的MDP框架（这是前置知识）

其次，我们对蒙塔卡洛方法进行概览介绍，主要包括：特点，适用范围，主要思想，与DP算法的比较等等

随后，我们介绍基本的蒙特卡洛方法，为了连贯性，我们会进行一些假设。这些假设可能不切实际，但有利于我们的讲解。

然后，我们会针对上述基本蒙特卡洛方法的各个环节提出改进，拓展，帮助大家有更全面的了解。（期间会夹杂着与DP算法（动态规划算法）的对比，联动等）

最后，进行总结，同时提出一些尚未解决的问题供大家思考。

不具备完整环境知识的MDP框架

通俗来说，就是我们无法预测在状态$s$下选择某个动作$a$之后，我们会转移到其他状态$s^{\prime }$的概率分布。

严谨来说，我们不清楚MDP框架中的状态转移矩阵$P$，例如$P_{s{s}^{\prime }}^{\pi }$等

概览介绍

1. 与DP算法对比：
   DP算法要求我们了解完整的环境知识。它更像是解决一个确定的有最优解的复杂问题。这类问题我们完全可以通过贝尔曼方程解出最优解，但是为了降低复杂度，我们选择了DP算法。这不像是一个智能体agent应该做的事，反倒像是一个计算方法。而与DP算法不同，MC方法不需要我们知道状态转移矩阵$P$，对于环境的了解和分析主要由agent通过学习获得。这样看来，MC方法更像是智能体在学习一样。

2. 基本思想：
   通过大量采样来计算$v_{\pi }(s)$和$q_{\pi }(s,a)$。因为我们不清楚$P$矩阵，所以需要通过采样的经验来学习。

3. 特点
   由于MC方法通过采样来学习，这样可以避免一些复杂的运算。例如，有一个十分复杂的问题，可以使用DP算法求解。但是我们知道DP算法开销较大，这时候选用MC算法可以有效避免大的开销。因为MC算法只需要采样即可，不需要考虑太多逻辑上的事。

4. 适用范围
   因为MC算法在计算一个状态的$v_{\pi }(s)$时与其他状态的值无关，所以当我们只需要了解一部分状态或动作的价值时，采用MC算法可以很好的减少开销。

基本的MC框架

MC预测环节

我们先考虑如何评估一个策略$\pi$的价值。和DP算法一样，我们要考虑计算$v_{\pi }(s)和q_{\pi }(s,a)$。这里我们先以计算$v_{\pi }(s)$为例。

1. 初始化：初始化所有状态的价值。另外，为每一个状态$s$分配一个空列表$Returns(s)$，这个列表用来存我们每次采样中得到的$s$的价值。
2. 无限循环：每一次循环都是一场对局（更严谨的来说是一幕）。每一幕中，我们根据策略$\pi$生成一个序列$S_0,A_0,R_1,S_1,A_1,R_2......S_{T-1}.A_{t-1},R_T$，代表agent做的决策和状态的转移。根据这个序列，我们可以计算出该序列里每一个状态的价值。例如：$v_{\pi }(S_{T-1})=R_T,V_{\pi }(S_{T-2})=R_{T-1}+\gamma \ast R_T......$我们将这些价值放入对应的$Return(s)$中作为一次采样。同时，我们计算每个$Return(s)$的平均值来更新对应的$v_{\pi }(s)$。

Reinforcement Learning 这本书上区分了首次访问型MC和每次访问型MC，想要了解的读者可以去看看。另外，大家可以去看看这本书上的提供的伪代码，可能会有更深的理解

3.当然，我们不一定要通过求和计算$Return(s)$的平均值。我们可以通过下面的式子更新

4 .再次改进一下，我们每次都是更新固定的步长$a$而不是求平均值，就像这样

这是考虑到了环境可能会随着时间发生改变，当前的信息更为重要（我们不想让过去的过时的信息束缚我们）

MC动作价值的估计

由于我们并不清楚矩阵$P$，所以单靠$v_{\pi }(s)$并不能对策略进行优化。（想想DP算法是怎么确定优化方案的）所以，我们还得算出$q_{\pi }(s,a)$。

具体的计算方法和上面的一样，只不过把$v_{\pi }(s)$替换为$q_{\pi }(s,a)$而已。

但是，这里有一个复杂点：倘若我们评估的策略$\pi$是一个确定性的策略（每个状态只会采取特定动作，而不知根据概率采取动作），那么有一些二元组$(s^{\prime },a^{\prime })$永远不会在这个策略中出现。于是这些动作我们将无法评判，从而影响了最终结果。

如何解决这个问题？

书本上提出了两个方法：试探性出发和$\epsilon -greedy$策略。由于试探性出发策略限制过大，这里我们不介绍了。

$\epsilon -greedy$策略

介绍两个基本概念，$ϵ-软性策略$：指每个动作的可能性都大于等于$\frac{ϵ}{|A(s)|}$。其中$|A(s)|$指状态$s$下动作的数量。$ϵ$是一个人为设定的小正数。
$ϵ-greedy策略$：价值最大的动作概率为$1-ϵ+\frac{ϵ}{|A(s)|}$，其余动作的概率为：$\frac{ϵ}{|A(s)|}$，其中$ϵ$是一个人为设定的小正数。

我们初始化策略可以使用$ϵ-软性策略$，改进策略的时候可以采取$ϵ-greedy策略$，从而可以保证所有动作可能性都会被访问到。

MC策略更新

最简单的版本是：我们依然采用之前提到的广义迭代，即进行一定程度的价值评估，然后根据价值评估结果进行策略改进。当然，我们希望最后学习到的策略是一个确定性策略，而不是软性策略。所以，我们可以每一轮策略更新后，将$ϵ$减小，使得它在多论训练后收敛至0。例如：在第$k$轮训练后，$ϵ$更新为$\frac{1}{k}$。

拓展部分

可以预见的是：MC算法对于太长的幕或者干脆没有终止的幕不适用。如果幕太长，那么计算时间太长。如果幕没有终止，那么连采样都无法完成。

这样，我们就引入下节课要讲的，时序差分算法(TD($\lambda$))