Value-based 强化学习

Agent 的目标是赢得游戏，「赢得游戏」等价于「使 reward 之和最高」。为使 reward 之和最高，需要做出回报最好的 action 。\(Q^*(s, a)\) 可以使 agent 知道每个 action 的平均回报，agent 应当选择平均回报最高的 action 。当前并没有现成的 \(Q^*(s, a)\) ，而 Value-based RL ，价值学习的目标便是学习一个函数近似 \(Q^*(s, a)\) 。

Deep Q-Network (DQN)

用神经网络 \(Q(s, a; \mathbf{w})\)（即 DQN ）近似 \(Q^*(s, a)\) 。其中 \(\mathbf{w}\) 是神经网络的参数，\(Q(s, a; \mathbf{w})\) 的返回值是对所有可能 action 的打分，每个分数对应一个 action 。通过 reward 训练，该神经网络打分的准确度会越来越高。

用 DQN 操控 agent 的流程：

• 读取 \(s_t\) ，DQN 对所有 action 打分并发起读出分数最高的 \(a_t\)（ \(a_t = \mathrm{argmax}_a Q(s_t, a; \mathbf{w})\) ）；

• 环境改变 ，得到 \(r_t\) 和 \(s_{t + 1}\)（ \(s_{t + 1} \sim p( \cdot | s_t, a_t)\) ）；

DQN 再次对所有 action 打分并发起读出分数最高的 \(a_{t + 1}\)（ \(a_{t + 1} = \mathrm{argmax}_a Q(s_{t + 1}, a; \mathbf{w})\) ）；

• 环境改变 ，得到 \(r_{t + 1}\) 和 \(s_{t + 2}\)（ \(s_{t + 2} \sim p( \cdot | s_{t + 1}, a_{t + 1})\) ）；

• 再次对所有 action 打分并发起读出分数最高的 \(a_{t + 2}\)（ \(a_{t + 2} = \mathrm{argmax}_a Q(s_{t + 2}, a; \mathbf{w})\) ）

• ...

• 游戏结束。

Temporal Difference (TD) Learning

即时间差分学习算法（ TD 算法），是训练 DQN 最常用的算法。

一般的 learning 流程：

• 取得预测值：\(q = Q(\mathbf{w})\) ；

• 完成所有任务取得实际值：\(y\) ；

• 计算损失：\(L = \frac{1}{2}(q - y) ^ 2\) ；

• 计算梯度：\(\frac{\partial L}{\partial \mathbf{w}} = \frac{\partial q}{\partial \mathbf{w}} \cdot \frac{\partial L}{\partial q} = (q - y) \cdot \frac{\partial Q(\mathbf{w})}{\partial \mathbf{w}}\) ；

• 梯度下降，得到新参数：\(\mathbf{w}_{t + 1} = \mathbf{w}_t - \alpha \cdot \frac{\partial L}{\partial \mathbf{w}}|_{\mathbf{w} = \mathbf{w}_t}\) 。

\(\alpha\) 是学习率，用来控制参数更新的步长大小，决定模型学习速度和稳定性。

但显然，如果「所有任务」很多，一轮 learning 需要大量的时间，使训练效率大打折扣。考虑到许多任务重复性很强，那么如何在不完成所有任务的情况下完成一轮 learning 呢？

TD 算法可以解决这个问题，learning 流程为：

• 取得预测值：\(q = Q(\mathbf{w})\) ；

• 完成一部分任务取得 TD Target ：\(y\) ；

• 计算损失：\(L = \frac{1}{2}(q - y) ^ 2\) ；

• 计算梯度：\(\frac{\partial L}{\partial \mathbf{w}} = \frac{\partial q}{\partial \mathbf{w}} \cdot \frac{\partial L}{\partial q} = (q - y) \cdot \frac{\partial Q(\mathbf{w})}{\partial \mathbf{w}}\) ；

• 梯度下降，得到新参数：\(\mathbf{w}_{t + 1} = \mathbf{w}_t - \alpha \cdot \frac{\partial L}{\partial \mathbf{w}}|_{\mathbf{w} = \mathbf{w}_t}\) 。

TD Target 是什么呢？比如预测开车从 A 地到 B 地（途经 C 地）所需时间，通过 TD 算法在只从 A 地开到 C 地的情况下完成一轮 learning 。模型首先做出一次预测 \(Q(\mathbf{w}) = 1000\)（分钟），然后把车开到 C 地，用时 300 分钟，此时再做一次预测，得到预测值 300 分钟。那么，TD Target: \(y = 300 + 600 = 900\)（分钟）。 还是这个情境，模型预估从 A 地到 B 地所需时间，预测值为 1000 分钟，到达 C 地后做第二次预测，预测值为 600 分钟，那么 A 地到 C 地的预测值就是 400 分钟。而实际上从 A 地到 C 地只用了 300 分钟，这之间的误差 100 分钟称为 TD error \(\delta\)。 TD 算法的目标，是令 TD error 尽可能接近 0 。

TD Leaning 用于 DQN

在上文预测开车所需时间的情境中，显然有这样一个公式：

左右之差即 TD error 。

推广到深度强化学习，也有这样一个公式：

• \(Q(s_t, a_t; \mathbf{w})\) 是 DQN 在 \(t\) 时刻做的估计，即未来奖励总和的期望；

• \(r_t\) 是真实观测到的奖励；

• \(Q(s_{t + 1}, a_{t + 1}; \mathbf{w})\) 是 DQN 在 \(t + 1\) 时刻做的估计。

TD Leaning 训练 DQN 基本流程：

• 在 \(t\) 时刻做出预测：\(Q(s_t, a_t; \mathbf{w})\) ；

• 在 \(t + 1\) 时刻做出预测，计算 TD Target ：

• 计算损失：\(L_t = \frac{1}{2}[Q(s_t, a_t; \mathbf{w}) - y_t] ^ 2\) ；

• 梯度下降，得到新参数：\(\mathbf{w}_{t + 1} = \mathbf{w}_t - \alpha \cdot \frac{\partial L}{\partial \mathbf{w}}|_{\mathbf{w} = \mathbf{w}_t}\) 。

通过奖励更新 DQN 的基本参数

一轮迭代的基本流程：

• 在 \(t\) 时刻做出预测：\(q_t = Q(s_t, a_t; \mathbf{w}_t)\) ；

• 计算梯度：\(\mathbf{d}_t = \frac{\partial Q(s_t; a_t; \mathbf{w})}{\partial \mathbf{w}}|_{\mathbf{w} = \mathbf{w}_t}\) ；

• 发出 action \(a_t\) 后，环境更新 state \(s_{t+1}\) 和 reward \(r_t\) ；

• 计算 TD Target ：\(y_t = r_t + \gamma \cdot \underset{a}{\mathrm{max}} Q(s_{t + 1}, a; \mathbf{w}_t)\)

• 梯度下降，得到新参数：\(\mathbf{w}_{t + 1} = \mathbf{w}_t - \alpha \cdot (q_t - y_t) \cdot \mathbf{d}_t\) 。