Policy Learning and Value Learning
深度学习的目标是找到最优的策略，通常有两种办法：策略学习和Q学习。Policy Learning 的优化对象就是策略函数 $\pi(a|s)$, 而 Value Learning 的优化对象是 $Q^*(s,a)$, 目标是找到最准确的 Optimal Action Value 函数，从而据此选择最合适的策略。
Deep Q Network (DQN)
Deep Q-Learning 的目标是，给定状态和动作，预测其可能最高获得回报的期望（最高意味着选择最好的策略）。我们用一个神经网络来预测这个期望。Deep Q-Learning 的方法是，先把 state 输入卷积层，抽取为特征之后，再输入全连接层，最后返回一个分数向量，经过 softmax 函数之后转化为概率值，最后选择概率最大的那一个 action 作为执行动作。（有个小问题：在 LLM 中，为了使生成的文本更灵活丰富，往往不会单纯选择概率最大的输出，而是根据 temperature 和 top_p 参数，从概率最大的几个中采样取出，这样的思路是否能用到 DQN 中呢？这会不会使得 DQN 在训练初期表现得更好？）
Deep Q-Learning 网络可以记作 $Q(s,a;\textbf{w})$, 式中 $\textbf{w}$ 表示神经网络的参数（也就是训练的对象）。要训练神经网络，我们应该找出一个损失函数，比如关于预测的回报和真实的回报$y$，我们取：
\[
L(\textbf{w}) = \frac{1}{2} (Q(s,a ; \textbf{w}) - y)^2
\]
然后求梯度：
\[
\nabla_{\textbf{w}}L(\textbf{w}) = (Q(s,a ; \textbf{w}) - y) \cdot \nabla_{\textbf{w}} Q(s,a ; \textbf{w})
\]
注意，对于一个标量求关于矢量的梯度，梯度的形状与矢量的形状一致。然后做梯度下降（取学习率为 $\alpha$ ）：
\[
\textbf{w} \leftarrow \textbf{w} - \alpha \cdot \nabla_{\textbf{w}}L(\textbf{w})
\]
然而这种办法存在一种弊端：每次跑完一个 trajectory（假设episodic）才能做一次更新，优化的效率太低了，有没有其他的办法实现每一步更新一次呢？这就需要 Temporal Difference 算法（时间差分算法）。
Temporal Difference Algorithm
时间差分算法实现了每运行一步更新一次神经网络参数。具体方法如下：
- 观察所处的状态 $s_t$
- 根据 $Q(s_t,a_t;\textbf{w})$, 选择预期回报最大的动作执行
- 执行一次之后收到了奖励 $r_{t}$, 并且更新到状态 $s_{t+1}$
- 根据 $Q(s_{t+1},a_{t+1};\textbf{w})$ 预测，并选择出预期回报最大的动作，但是不执行
- 计算 TD error $\delta_{t} = Q(s_{t},a_{t};\textbf{w}) - [r_{t} + \gamma \cdot Q(s_{t+1},a_{t+1};\textbf{w})]$，其中，$Q(s_{t+1},a_{t+1};\textbf{w})$ 称为 TD Target
- 计算损失函数：
\[
L(\textbf{w}) = \frac{1}{2} (Q(s_{t},a_{t};\textbf{w}) - (r_{t} + \gamma \cdot Q(s_{t+1},a_{t+1};\textbf{w})))^2
\] - 对损失函数求梯度（这里假装 TD Target 关于 $\textbf{w}$ 是一个常数）：
\[
\nabla_{\textbf{w}}L(\textbf{w}) = (Q(s_{t},a_{t};\textbf{w}) - (r_{t} + \gamma \cdot Q(s_{t+1},a_{t+1};\textbf{w}))) \cdot \nabla_{\textbf{w}} Q(s,a ; \textbf{w})
\]
\[
\nabla_{\textbf{w}}L(\textbf{w}) = \delta_{t} \cdot \nabla_{\textbf{w}} Q(s,a ; \textbf{w})
\] - 梯度下降：
\[
\textbf{w} \leftarrow \textbf{w} - \alpha \cdot \delta_{t} \cdot \nabla_{\textbf{w}} Q(s,a ; \textbf{w})
\]
理解与解释：
时间差分算法是比较在每一步操作前和操作后对于最大回报期望的估计，每一步前后的区别是：每一步执行前，对未来的回报估计是纯的估计，而每一步执行后，都能够得到一个立刻的奖励（这个奖励是真实发生的），把这一步的真实奖励和这一步后对未来的估计结合起来，就能得到这一步前对未来的另一个估计。后者的这个估计比前者的估计要准确（毕竟有一部分是真实观测的），所以我们努力使得前者的估计贴近后者的估计，而这就可以用一个误差函数去优化了。
此处还有一个问题：为什么要设置 TD Target: $r_{t} + \gamma \cdot Q(s_{t+1},a_{t+1};\textbf{w})$ 有这样的形式？
回忆一下回报的定义：\[ U_t = \sum_{k=t}^{n} \gamma^{k-t} \cdot R_k \] \[ U_{t+1} = \sum_{k=t+1}^{n} \gamma^{k-t-1} \cdot R_k\]由 $ U_t $ 和 $ U_{t+1}$的定义可得：
\[
U_t = R_t + \gamma \cdot \sum_{k=t+1}^{n} \gamma^{k-t-1} \cdot R_k
\]
回忆一下，Optimal Action Value Function 可以写成
\[
Q_* (s_t, a_t) = \max_{\pi} \mathbb{E} [U_t | S_t = s_t, A_t = a_t]
\]
再回忆一下Bellman Optimal Equation, 可以发现：
\[
\begin{aligned}
Q_* (s_t, a_t) &= \mathbb{E}_{S_{t+1} \sim p(\cdot | s_t, a_t)} [R_t + \gamma \cdot \max_{a \in \mathcal{A}} Q_* (S_{t+1}, a) | S_t = s_t, A_t = a_t].
\end{aligned}
\]
我们可以用 Monte Carlo 算法对上式进行估计：
\[
Q_* (s_t, a_t) \approx r_t + \gamma \cdot \max_{a \in \mathcal{A}} Q_* (S_{t+1}, a)
\]
再结合到 DQN 中，我们用 $Q(s_{t},a_{t};\textbf{w})$ 来估计 $Q_*(s_{t},a_{t})$, 这就不难理解 TD Target 的形式了。
Training Process
应用 TD 算法进行训练，步骤如下：
收集训练数据：我们可以用任何策略函数 $\pi$ 去控制智能体与环境交互，这个 $\pi$ 就叫做行为策略（behavior policy）。比较常用的是 $\epsilon$-greedy 策略：
\[
a_t =
\begin{cases}
\arg \max_a Q(s_t, a; w), & \text{以概率 } (1 - \epsilon); \\
\text{均匀抽取 } A \text{ 中的一个动作}, & \text{以概率 } \epsilon.
\end{cases}
\]
把智能体在一局游戏中的轨迹记作：
\[
s_1, a_1, r_1, s_2, a_2, r_2, \cdots, s_n, a_n, r_n.
\]
把一条轨迹划分成 $n$ 个 $(s_t, a_t, r_t, s_{t+1})$ 这种四元组，存入数组，这个数组叫做经验回放数组（replay buffer）。更新 DQN 参数 $w$：
- 随机从经验回放数组中取出一个四元组，记作 $(s_j, a_j, r_j, s_{j+1})$。设 DQN 当前的参数为 $w_{\text{now}}$，执行下面的步骤对参数做一次更新，得到新的参数 $w_{\text{new}}$。
- 对 DQN 做正向传播，得到 Q 值：
\[
\hat{q}_j = Q(s_j, a_j; w_{\text{now}}) \quad \text{和} \quad \hat{q}_{j+1} = \max_{a \in A} Q(s_{j+1}, a; w_{\text{now}}).
\] - 计算 TD 目标和 TD 误差：
\[
\hat{y}_j = r_j + \gamma \cdot \hat{q}_{j+1} \quad \text{和} \quad \delta_j = \hat{q}_j - \hat{y}_j.
\] - 对 DQN 做反向传播，得到梯度：
\[
g_j = \nabla_w Q(s_j, a_j; w_{\text{now}}).
\] - 做梯度下降更新 DQN 的参数：
\[
w_{\text{new}} \leftarrow w_{\text{now}} - \alpha \cdot \delta_j \cdot g_j.
\]
智能体收集数据、更新 DQN 参数这两者可以同时进行。可以在智能体每执行一个动作之后，对 $w$ 做几次更新。也可以在每完成一局游戏之后，对 $w$ 做几次更新。