第05章：模型未知的MDP问题求解-蒙特卡罗算法
- author: zhouyongsdzh@foxmail.com
- date: 2017-11-25
- weibo: @周永_52ML
目录
写在前面
上一章介绍了当模型已知时，可以用动态规划方法求解MDP问题。那么本章和下一章主要介绍模型未知时如何求解MDP问题，即无模型的马尔科夫决策问题。无模型的强化学习算法主要包括蒙特卡罗算法和时间差分算法，我们先看蒙特卡罗算法。
蒙特卡罗算法
之前讲到，我们可以把强化学习问题用MDP来描述。如果状态转移概率已知（即模型已知），我们可以用动态规划来求解最优策略。其中，动态规划方法包括策略迭代和值迭代两种方法，它们可以用广义策略迭代方法来统一，即先对当前策略进行策略评估（计算值函数），然后基于值函数进行策略改进（比如贪婪策略）。
无模型的强化学习问题求解思路与动态规划相似，包括策略评估和策略改进两步。我们先回忆下动态规划方法中值函数的计算方法：
$$
v_{\pi}(s) = \sum_{a \in \mathcal{A}} \pi(a|s) \left(R(s,a) + \gamma \sum_{s’ \in \mathcal{S}} P(s’|s,a) \cdot v_{\pi}(s’) \right) \qquad(rl.5.1)
$$
可以看到，动态规划方法计算状态值函数时用到了转移概率$P(s’|s,a)$(即模型)，在无模型的强化学习问题中，模型$P(s’|s,a)$时未知的。无模型的强化学习算法要想利用策略评估和策略改进框架，那么必须要采用其它的方法来计算当前策略的值函数（策略评估）。
在第3章我们讲值函数原始定义的时候，提到状态值函数和状态行为值函数实际上是计算长期收益回报的期望。动态规划方法中利用模型$P(s’|s,a)$对该期望进行计算。无模型时，可以利用随机样本来估计期望，即蒙特卡洛算法。蒙特卡罗算法在计算值函数时利用经验平均代替随机变量的期望。
经验平均
怎么理解经验平均呢？首先，当要平均Agent的当前策略时，可以利用该策略产生多次试验，每次试验都是从任意的初始状态开始直到终止状态。比如一次试验的序列表示为：$S_1, A_1, R_2, S_2, A_2, R_3, \cdots S_T$。那么状态$S_1$处的折扣回报为$G_t(S_1) = R_{t+1} + \gamma R_{t+2} + \cdots + \gamma^{T-1} R_T$。这里的经验是指利用该策略做很多次试验（积累试验数据的过程）。
利用蒙特卡罗方法求状态$s$处的值函数时，又可以分为第一次访问蒙特卡罗方法和每次访问蒙特卡罗方法。
第一次访问蒙特卡罗方法指的是在计算状态$s$处的值函数时，只利用每次试验中第一次访问到状态$s$时的期望值。计算公式为：
$$
v(s) = \frac{G_{11}(s) + G_{21}(s) + \cdots } {N(s)}
$$
其中，$N(s)$表示状态$s$处的试验次数。
每次访问蒙特卡罗方法指的是在计算状态$s$处的值函数时，利用所有访问到状态$s$时的回报期望值。公式表示为：
$$
v(s) = \frac{G_{11}(s) + G_{12}(s) + \cdots + G_{21}(s) + \cdots } {N(s)}
$$
递增的计算经验平均的方法：
$$
\begin{align}
v_{k}(s) & = \frac{1}{k} \sum_{i=1}^{k} G_i(s) = \frac{1}{k} \left(G_{k}(s) + \sum_{i=1}^{k-1} G_i(s) \right) \\\
& = \frac{1}{k} \left(G_k(s) + (k-1) v_{k-1}(s) \right) \\\
& = v_{k-1}(s) + \frac{1}{k} \left(G_k(s) - v_{k-1}(s) \right)
\end{align}
$$
经验获取即探索的过程
由于事先不知道Agent与Environment交互模型，蒙特卡罗算法利用经验平均来估计值函数。能否得到正确的值函数，这取决于经验。获取充足的经验是无模型的强化学习问题求解的核心所在。
回到动态规划方法，为了保证值函数的收敛性，算法会对状态空间中的状态逐个扫描。无模型的方法充分评估当前策略的前提是每个状态都能被访问到。因此，蒙特卡罗算法必须采用一定的方法保证每个状态都能被访问到。其中一种方法是探索性初始化。
所谓探索性初始化是指每个状态都有一定的几率作为初始状态。在给出基于探索性初始化的蒙特卡罗算法前，我们还需要给出策略改进方法，以及便于进行迭代计算的平均方法。
蒙特卡罗策略改进
蒙特卡罗算法利用经验平均估计当前策略的值函数。当值函数被估计出来后，对于每个状态$s$，通过最大化动作值函数来进行策略改进。即$\pi(s) = \arg \max_{a} q(s,a)$。
探索性初始化的蒙特卡罗算法
// TODO 1. 给出伪代码，2. 解释算法
探索性初始化的目标是为了获取更多的经验数据，可以看到在每一次迭代中，初始状态都是随机分配的，这样可以保证迭代过程中每个<状态，行为>对都能被选中。这里面有一个假设，即假设所有的动作都会被频繁选中。对于这个假设大多数场景很难成立，或无法保证。
那么在实际过程中，如何设计探索策略，以保证每个状态都能被访问到呢？
// TODO $\quad \epsilon-soft$策略.