免模型预测

免模型预测

前面介绍的方法假定我们已知状态转移函数和奖励函数，这在许多游戏的场景中是可行的。但是仍然存在部分场景，我们不能了解它的状态转移函数和奖励函数。

蒙特卡罗学习

蒙特卡罗方法是一种免模型的方法，也就是它不需要环境的状态转移函数以及环境的奖励函数。

蒙特卡罗方法利用完整的回合经验来学习，也就是利用采样样本学习。它的核心思想是利用均值估计期望。

由于这是一个预测任务，因此学习目标是学习给定策略的v函数。

我们之前定义的return和状态价值函数：

$\begin{equation} \begin{aligned} G_t &= R_{t + 1} + \gamma R_{t + 2} + \gamma^2 R_{t + 3} + ...\\ v_{\pi}(s) &= E_{\pi}[G_t |S_t = s] \end{aligned} \end{equation}$

有两种主要的方式来估计v函数:

First-Visit Monte-Carlo Policy Evaluation
Every-Visit Monte-Carlo Policy Evaluation

方式的选择针对具体的问题

First-Visit Monte-Carlo Policy Evaluation

First-visit 蒙特卡罗评估方法强调我们只对一个回合中第一次出现的状态进行估计。也就是如果在一个回合中一个状态出现了多次，我们只对第一次进行统计平均，具体的：

遍历N个回合：
遍历一个回合中的每一个状态：
如果当前状态是这个回合中第一次出现，则 $N(s) \leftarrow N(s) + 1, S(s) \leftarrow S(s) + G(t)$
结束所有回合后： $V(s) = \frac{S(s)}{N(s)}$
当N趋于无穷，则V趋于真实的v函数

Every-Visit Monte-Carlo Policy Evaluation

Every-Visit 蒙特卡罗评估方法则是对每一次出现的状态都统计，不考虑它是否是一个回合中第一次出现。也就是每一次出现，我们都会对它做统计平均，具体的：

遍历N个回合：
遍历一个回合中的每一个状态：
对当前状态： $N(s) \leftarrow N(s) + 1, S(s) \leftarrow S(s) + G(t)$
结束所有回合后： $V(s) = \frac{S(s)}{N(s)}$
当N趋于无穷，则V趋于真实的v函数

增量形式的蒙特卡罗更新

前面的对于均值的计算都是最后取平均，但是我们更希望的形式是，每出现一次都可以进行一次更新，也就是将求均值的问题写成增量形式：

$\begin{equation} \begin{aligned} \mu_n &= \frac{1}{n}\sum\limits_{j = 1}^n x_j\\ &= \frac{1}{n}(x_n + \sum\limits_{j = 1}^{n - 1} x_j)\\ &= \frac{1}{n}(x_n + (n - 1)\mu_{n - 1})\\ &= \mu_{n - 1} + \frac{1}{n}(x_n - \mu_{n -1}) \end{aligned} \end{equation}$

这个增量形式可以理解为： $\mu_{n -1}$ 是原本的对于均值的预测，此时多了一个 $x_n$ , 发现 $x_n$ 和原本均值的预测存在误差 $x_n - \mu_{n -1}$ ，因此要修正误差， $\frac{1}{n}$ 则为学习率。

因此可以将蒙特卡罗的方法更新为：

遍历N个回合：
遍历一个回合中的每一个状态：
对当前状态 $N(S_t) \leftarrow N(S_t) + 1, V(S_t) \leftarrow V(S_t) + \frac{1}{N(S_t)}(G_t - V(S_t))$

需要注意的是 $G_t$ 的计算是根据真实的回合reward，因此只有获得完整的回合才可以计算。

由于这里的 $\frac{1}{N(S_t)}$ 可以看成学习率，因此可以用超参数 $\alpha$ 来控制每一次对于value function的修正程度。

时序差分学习

时序差分同样是免模型的方法。它同样是通过实际的和环境的交互来学习。但是它可以用不完整的回合来学习，它采用的方式叫做bootstrapping（自举），简单说就是将不完整的部分用估计值弥补。它的过程可以理解为是从一个估计值向另一个估计值更新。

自举：更新中使用了估计

TD(0)

前面的蒙特卡罗方法不能够用在不完整的回合中的主要原因在于它的更新中对 $G_t$ 的计算是采用 $R_{t + 1} + \gamma R_{t + 2} +...$ 的方式计算的。所有的R都是这个回合真实的reward，因此只能在完整的回合中进行。但是如果将 $G_t$ 用别的方式计算，直接估计出后面部分的reward，就不需要完整的回合了。

$\begin{equation} \begin{aligned} G_t &= R_{t + 1} + \gamma R_{t + 2} + ..\\ &= R_{t + 1} + \gamma G_{t + 1}\\ \end{aligned} \end{equation}$

用 $G_{t + 1}$ 的期望去估计 $G_t$ , 得到：

$G_t \approx R_{t + 1} + \gamma V(S_{t + 1})$

因此，状态价值函数的更新：

$V(S_t) \leftarrow V(S_t) + \alpha (R_{t + 1} + \gamma V(S_{t + 1}) - V(S_t))$

其中的 $R_{t + 1} + \gamma V(S_{t + 1}) - V(S_t)$ 为TD error

这个问题也可以不根据蒙特卡罗的思路去考虑

$V_{\pi}(S_t) = R_{t + 1} + \gamma V_{\pi}(S_{t + 1})$

也就是更新是 $V(S_t) \leftarrow V(S_t) + \alpha(V_{\pi}(S_t) - V(S_t))$

这个 $V_{\pi}(S_t)$ 是在下一步骤已经进行之后，策略对于之前状态的价值的更新策略价值函数，理论上会比之前更准确。因此向着这个方向更新状态函数。

TD( $\lambda$ )

n-steps 蒙特卡罗方法

前面介绍的TD(0)是向前进行了一步之后，估计前一步状态的价值。但是可以走多步之后，再估计几步之前的状态价值，这样甚至更准确，但是需要更长时间收敛。当步骤足够多时候，问题退化成为蒙特卡罗方法。形式化描述：

$\begin{equation} \begin{aligned} G_t^{(n)} &= R_{t + 1} + \gamma R_{t + 2} + .. + \gamma^{n-1}R_{t + n} + \gamma^n V(S_{t + n})\\ V(S_t) &\leftarrow V(S_t) + \alpha(G_t^{(n)} - V(S_t)) \end{aligned} \end{equation}$

但是对于不同的具体问题n的采取是不同的，因此是否能有一种方法，考虑所有n取值的情况，这样的结果会更加稳定。

TD( $\lambda$ )

$\begin{equation} \begin{aligned} G_t^{\lambda} &= (1 - \lambda)\sum\limits_{n = 1}^{\infty} \lambda^{n - 1}G_t^{(n)}\\ V(S_t) &\leftarrow V(S_t) + \alpha(G_t^{\lambda} - V(S_t)) \end{aligned} \end{equation}$

它给不同的n得到的return加权求和。因为n越大，更新时候积攒的return值越大，为了防止n大的return有更大的比重，因此给n大的return一个更小的权重来平衡。

蒙特卡罗 vs 时序差分

更新方向：

蒙特卡罗方法是将每一个状态价值向着真实的最终的结果的方向更新
时序差分方法是将每一个状态价值向着下一轮的价值函数的方向更新，而不一定是最终的真实结果的方向

偏差和方差：

蒙特卡罗的结果和真实情况的偏差小，但是由于环境会带来许多的噪声导致方差大
时序差分的结果和真实结果的偏差较大，但是方差小

思想：

蒙特卡罗直接从经验中学习
时序差分则是先对于当前的数据建立合适的MDP，再根据新的数据对MDP进行调整
因此时序差分利用了马尔可夫的性质，它的收敛速度通常更快
但是在非马尔可夫状态的问题上，蒙特卡罗仍然成立。比如观测并不能完整的得到真实状态等等的情况。

更新：

蒙特卡罗经过一个完整回合才能进行更新，而且只考虑了这个回合真实经历的状态和回报。因此它深度很深，广度不广。
时序差分一步一更新，也只考虑了这个回合真实经历的状态和回报，深度不深，广度不广。
动态规划考虑了每一种情况，但只考虑一步的，深度不深，广度很广。