1.2 value based RL

复习

1. 在学习DQN之前，首先复习一些基础知识。在一局游戏中，把从起始到结束的所有奖励记作：$$。
2. 定义折扣率$$。折扣回报的定义是：

$$。

3. 在游戏尚未结束的$$时刻，$$是一个未知的随机变量，其随机性来自于$$时刻之后的所有状态与动作。动作价值函数 的定义是：

$$,

• 公式中的期望消除了t tt 时刻之后的所有状态$$与所有动作$$

4. 最优动作价值函数用最大化消除策略$$：$$。
5. 可以这样理解$$: 已知$$和$$, 不论未来采取什么样的策略$$, 回报$$的期望不可能超过$$。
6. 最优动作价值函数的用途：假如我们知道$$, 我们就能用它做控制。
   1. 举个例子，超级玛丽游戏中的动作空间是$$。
   2. 给定当前状态$$, 智能体该执行哪个动作呢？
   3. 假设我们已知$$函数，那么我们就让$$给三个动作打分，
   4. 比如：$$。
7. 这三个值是什么意思呢？ 1.$$的意思是：如果现在智能体选择向左走，不论之后采取什么策略$$, 那么回报$$的期望最多不会超过 370。
   2. 同理，其他两个最优动作价值也是回报的期望的上界。
   3. 根据$$的评分，智能体应该选择向上跳，因为这样可以最大化回报$$的期望。

DQN

• 我们希望知道$$, 因为它就像是先知一般，可以预见未来，在$$时刻就预见$$到$$时刻之间的累计奖励的期望。
• 假如我们有$$这位先知，我们就遵照先知的指导，最大化未来的累计奖励。
• 然而在实践中我们不知道$$的函数表达式。是否有可能近似出$$这位先知呢？
• 对于超级玛丽这样的游戏，学出来一个“先知”并不难。假如让我们重复玩超级玛丽一亿次，那我们就会像先知一样，看到当前状态，就能准确判断出当前最优的动作是什么。
• 这说明只要有足够多的“经验”, 就能训练出超级玛丽中的“先知”。

1. 最优动作价值函数的近似：
   1. 在实践中，近似学习“先知”$$最有效的办法是深度Q网络(deep Q network, 缩写 DQN), 记作$$, 其结构如图所述。
   2. 其中的$$表示神经网络中的参数。首先随机初始化$$, 随后用“经验”去学习$$。
   3. 学习的目标是：对于所有的$$和$$, DQN 的预测$$尽量接近$$。后面几节的内容都是如何学习$$!

2. 可以这样理解 DQN 的表达式$$。
   1. DQN 的输出是离散动作空间$$上的每个动作的 Q 值，即给每个动作的评分，分数越高意味着动作越好。
   2. 举个例子，动作空间是$$, 那么动作空间的大小等于$$, 那么 DQN 的输出是 3 维的向量，记作$$, 向量每个元素对应一个动作。
   3. 在图 4.1 中，DQN 的输出是 4.$$。
3. 总结一下，DQN 的输出是$$维的向量$$, 包含所有动作的价值。而我们常用的符号$$是标量，是动作$$对应的动作价值，是向量$$中的一个元素。
4. 用DQN玩游戏：agent每次采取的action是使得Q函数取最大的那个动作，一直玩下去。下图的顺序是从左往右看。

5. DQN 的梯度：在训练 DQN 的时候，需要对 DQN 关于神经网络参数$$求梯度。用$$

• 表示函数值$$关于参数$$的梯度。因为函数值$$是一个实数，所以梯度的形状与$$完全相同。
• 如果$$是$$的向量，那么梯度也是$$的向量。如果$$是$$的矩阵，那么梯度也是$$的矩阵。如果$$是$$的张量，那么梯度也是$$的张量。

6. 给定观测值$$和$$, 比如$$, 可以用反向传播计算出梯度$$。
   1. 在编程实现的时候，TensorFlow 和PyTorch 可以对 DQN 输出向量的一个元素(比如$$这个元素) 关于变量$$自动求梯度，得到的梯度的形状与$$完全相同。

时间差分（TD）算法

驾车时间预测的例子

1. 假设我们有一个模型$$, 其中$$是起点，$$是终点，$$是参数。
   1. 模型$$可以预测开车出行的时间开销。
   2. 这个模型一开始不准确，甚至是纯随机的。
   3. 但是随着很多人用这个模型，得到更多数据、更多训练，这个模型就会越来越准，会像谷歌地图一样准。
2. 我们该如何训练这个模型呢？
   1. 在用户出发前，用户告诉模型起点$$和终点$$, 模型做一个预测$$。
   2. 当用户结束行程的时候，把实际驾车时间$$反馈给模型。
   3. 两者之差$$反映出模型是高估还是低估了驾驶时间，以此来修正模型，使得模型的估计更准确。
3. 假设我是个用户，我要从北京驾车去上海。从北京出发之前，我让模型做预测，模型告诉我总车程是 14 小时：

$$。

4. 当我到达上海，我知道自己花的实际时间是 16 小时，并将结果反馈给模型；见图 4.2。

5. 可以用梯度下降对模型做一次更新，具体做法如下。把我的这次旅程作为一组训练数据：

$$。

6. 我们希望估计值$$尽量接近真实观测到的$$, 所以用两者差的平方作为损失函数：

$$。

7. 用链式法则计算损失函数的梯度，得到：

$$。

8. 然后做一次梯度下降更新模型参数$$：

$$，

• 此处的$$是学习率，需要手动调整。在完成一次梯度下降之后，如果再让模型做一次预测，那么模型的预测值

$$

• 会比原先更接近$$。

TD算法

• 接着上文驾车时间的例子。出发前模型估计全程时间为$$小时；模型建议的路线会途径济南。我从北京出发，过了$$小时，我到达济南。此时我再让模型做一次预测，模型告诉我

$$。

• 见图 4.3 的描述。假如此时我的车坏了，必须要在济南修理，我不得不取消此次行程。
  • 我没有完成旅途，那么我的这组数据是否能帮助训练模型呢？
  • 其实是可以的，用到的算法叫做 时间差分 (temporal difference, 缩写 TD)。

• 下面解释 TD 算法的原理。
  • 回顾一下我们已有的数据：模型估计从北京到上海一共需要$$小时，我实际用了$$小时到达济南，模型估计还需要$$小时从济南到上海。
  • 到达济南时，根据模型最新估计，整个旅程的总时间为：
    $$。
• TD 算法将$$称为 TD 目标 (TD target), 它比最初的预测$$更可靠。
  • 最初的预测$$纯粹是估计的，没有任何事实的成分。
  • TD 目标$$也是个估计，但其中有事实的成分：其中的$$就是实际的观测。
• 基于以上讨论，我们认为 TD 目标$$比模型最初的估计值$$更可靠，所以可以用$$对模型做“修正”。
  • 我们希望估计值$$尽量接近 TD 目标$$, 所以用两者差的平方作为损失函数：
    $$。
• 此处把$$看做常数，尽管它依赖于$$。计算损失函数的梯度：

$$，

• 此处的$$称作 TD 误差 (TD error)。做一次梯度下降更新模型参数$$：
  $$。
• 如果你仍然不理解 TD 算法，那么请换个角度来思考问题。模型估计从北京到上海全程需要$$小时，模型还估计从济南到上海需要$$小时。这就相当于模型做了这样的估计：从北京到济南需要的时间为$$。
• 而我真实花费$$小时从北京到济南。模型的估计与我的真实观测之差为$$。这就是 TD 误差！以上分析说明 TD 误差$$就是模型估计与真实观测之差。TD 算法的目的是通过更新参数$$使得损失$$减小。

用TD训练DQN

• TD算法是一种在线学习算法，可以逐步更新值函数，而不需要等到回合结束。
• 视频中用到的例子是从纽约到亚特兰大，途径华盛顿，但是道理都是一样的。

• 如何把TD算法用到DQN？和驾车的例子很像，等式左边是 t 时刻的 Q 的估计，等式右边是一个实际观测值加一项关于 t+1 时刻的 Q 估计。

1. 等式$$

• 这个等式反映了相邻两个折扣回报之间的关系：t 时刻的折扣回报$$等于 t 时刻的奖励$$加上折扣因子$$乘以 t+1 时刻的折扣回报$$。

2. 得来的过程如下：

$$。这个公式两边是两个估计（estimate）

3. 左边是 prediction，右边是 TD target。

4. 使用TD算法训练DQN的过程如下图：下图中的 t+1 时刻的 Q 为什么可以写成 max 的形式？是因为 t+1 时刻的 action$$就是选择 t 时刻使得 Q 最大的那个 action。

5. 下面是王树森书中具体的推导过程：

• 下面我们推导训练 DQN 的 TD 算法（严格地讲，此处推导的是“Q 学习算法”, 它属于 TD 算法的一种。本节就称其为 TD 算法）。回忆一下回报的定义$$,$$。由$$和$$的定义可得：

$$。

• 回忆一下，最优动作价值函数可以写成

$$。

• 从公式出发，经过一系列数学推导 , 可以得到下面的定理。这个定理是最优贝尔曼方程 (optimal Bellman equations) 的一种形式。

• 最优贝尔曼方程具体公式如下：

$$。

• 贝尔曼方程的右边是个期望，我们可以对期望做蒙特卡洛近似。
  • 当智能体执行动作$$之后，环境通过状态转移函数$$计算出新状态$$。奖励$$最多只依赖于$$,$$,$$。那么当我们观测到$$,$$,$$时，则奖励$$也被观测到，记作$$。有了四元组$$,
  • 我们可以计算出

$$。

• 它可以看做是下面这项期望的蒙特卡洛近似：

$$。

• 由定理和上述的蒙特卡洛近似可得：

$$。

• 这是不是很像驾驶时间预测问题？左边的$$就像是模型预测“北京到上海”的总时间，$$像是实际观测的“北京到济南”的时间，$$相当于模型预测剩余路程“济南到上海”的时间。见图 4.4 中的类比。

6. 把公式中的最优动作价值函数$$替换成神经网络$$, 得到：
   $$。

• 左边的$$是神经网络在 t 时刻做出的预测，其中没有任何事实成分。右边的 TD 目标$$是神经网络在 t+1 时刻做出的预测，它部分基于真实观测到的奖励$$。 +$$和$$两者都是对最优动作价值$$的估计，但是$$部分基于事实，因此比$$更可信。应当鼓励$$接近$$。定义损失函数：

$$。

• 假装$$是常数（实际上$$依赖于$$, 但是我们假装$$是常数）, 计算$$关于$$的梯度：
  $$。
• 做一步梯度下降，可以让$$更接近$$：
  $$。
• 这个公式就是训练 DQN 的 TD 算法。
• 总结一下：最优行动价值函数是未知的，DQN算法就是用神经网络近似这个最优行动价值函数。

7. TD算法具体流程如下：

8. 书中介绍的训练流程

• 首先总结上面的结论。给定一个四元组$$, 我们可以计算出 DQN 的预测值$$, 以及 TD 目标和 TD 误差：
  $$和$$。
• TD 算法用这个公式更新 DQN 的参数：
  $$。
• 注意，算法所需数据为四元组$$, 与控制智能体运动的策略$$无关。这就意味着可以用任何策略控制智能体与环境交互，同时记录下算法运动轨迹，作为训练数据。因此，DQN 的训练可以分割成两个独立的部分：收集训练数据、更新参数$$。

9. 收集训练数据：

• 我们可以用任何策略函数$$去控制智能体与环境交互，这个$$就叫做行为策略 (behavior policy)。比较常用的是$$-greedy 策略：
  $$
• 把智能体在一局游戏中的轨迹记作：
  $$。
• 把一条轨迹划分成$$个$$这种四元组，存入数组，这个数组叫做经验回放数组 (replay buffer)。

10. 更新 DQN 参数$$：

• 随机从经验回放数组中取出一个四元组，记作$$。
• 设 DQN 当前的参数为$$, 执行下面的步骤对参数做一次更新，得到新的参数$$。
  1. 对 DQN 做正向传播，得到 Q 值：
     $$和$$。
  2. 计算 TD 目标和 TD 误差：
     $$和$$。
  3. 对 DQN 做反向传播，得到梯度：
     $$。
  4. 做梯度下降更新 DQN 的参数：
     $$。

智能体收集数据、更新 DQN 参数这两者可以同时进行。可以在智能体每执行一个动作之后，对$$做几次更新。也可以在每完成一局游戏之后，对 $$ 做几次更新。

注意

上面介绍用 TD 算法训练 DQN, 更准确地说，我们用的 TD 算法叫做 Q 学习算法 (Q-learning)。TD 算法是一大类算法，常见的有 Q 学习和 SARSA。Q 学习的目的是学到最优动作价值函数 $$, 而 SARSA 的目的是学习动作价值函数 $$。后面会介绍 SARSA 算法。