[UCAS强化学习]4·无模型预测

1 简介

上节课我们学习了使用动态规划求解一个已知的 MDP——我们学习了迭代策略评估来评价某个给定策略（称作预测问题），以及策略迭代和价值迭代来寻找最优策略（称作控制问题）。这些动态规划方法的共同点是，它们都要求“模型”或“环境”，也就是 $P$ 矩阵和 $R$ 向量是已知的，因此我们将它们称为基于模型的 (model-based) 方法。而这两节课我们将探讨无模型 (model-free) 方法，其中这节课关注无模型预测，而下节课关注无模型控制。

我们将学习 3 种无模型预测方法：蒙特卡洛学习，时间差分学习和 TD(λ).

2 蒙特卡洛学习

蒙特卡洛 (Monte-Carlo, MC) 方法是一类用采样近似期望的方法。在强化学习的背景下，这意味着我们通过采样一系列轨迹 (episodes) 进行学习，而不需要知道转移概率矩阵 $P$ 和奖励向量 $R$ 到底是多少。运行 MC 方法通常要求：所有轨迹都到达终止状态或者轨迹足够长。

给定策略 $π$ ，采样的轨迹可以表示为一个随机变量序列，记作： $S_{0}, A_{0}, R_{1}, \dots, S_{k} \sim π$ MC 方法的思想就是用回报的经验均值来近似回报的真实期望（即价值函数）。具体而言，那么对于某个状态 $s \in S$ ，只需从它开始采样若干条样本，通过计算这些样本轨迹的回报即可近似价值函数 $v_{π} (s)$ .

2.1 首次访问的 MC 策略评估

由于一条轨迹可能会反复回到同一个状态，所以我们有两种计数策略。首次访问的 MC 策略评估只考虑第一次访问状态 $s$ 的时候，它未来的回报是怎样的。具体而言，为了估计状态 $s$ 的价值函数，我们：

采样一条轨迹，找到第一次访问状态 $s$ 的时刻 $t$
$N (s) \leftarrow N (s) + 1, S (s) \leftarrow S (s) + G_{t}$
重复上述过程若干次
计算 $V (s) = S (s) / N (s)$ ，根据大数定律，当 $N (s) \to \infty$ 时， $V (s) \to v_{π} (s)$

注：由于第 2 步涉及到了计算，是未来整个过程的加权奖励，因此我们必须要求轨迹最后终止。

2.2 每次访问的 MC 策略评估

另一种计数策略是把每一次访问都纳入考量，具体来说，

采样一条轨迹
对于该轨迹中每次访问状态的时刻，执行：
重复上述过程若干次
计算，当时，

2.3 增量式 MC 更新

对一组不断产生新数据的序列，可以增量式地计算当前观测的均值：这个递推式可以解释为：新的均值是原来的均值加上一个误差项 .

将其用在 MC 方法中，我们称之为增量式 MC 更新：

采样一条轨迹
对于每一个状态及其回报，计算：
重复上述过程

如果我们把系数替换为某个固定常数，那就得到了指数移动平均的形式：指数移动平均在非平稳（波动很大）的情形下很有用，我们不希望过早的历史信息对现在仍有相同比重的影响。

3 时间差分学习

3.1 TD

时间差分 (Time Difference, TD) 也是通过采样来学习的，但与 MC 不同的是，TD 不需要采样完整的、最后终止的轨迹，它借助了自举法 (bootstrapping) 去估计未来的回报。

TD 算法可以表述为：

采样一条轨迹
使用估计回报在线更新价值函数：其中称为 TD 目标，称作 TD 误差.
重复上述过程

可以看见，与增量式 MC 更新相对比，TD 用一个带有估计性质的代替了真实的，这就是自举法的含义——用自己手上的估计值而非真实值。受益于此，TD 可以在智能体运行过程中的每一时刻在线更新，而 MC 在采样出完整的轨迹之后才能更新。

我们可以举一个例子说明在线更新的好处。考虑一个开车的场景，在某一条轨迹中，我们与对面驶来的车擦肩而过——差点就车祸但是没有车祸。如果使用 MC 方法，我们不会得到任何负面的反馈，因为车祸毕竟没有发生，但使用 TD 方法，我们将期望车祸很有可能发生，因而会立刻更新价值函数，而不是一定要等到挂掉之后才能更新。