Deep Q-Network（DQN）

算法思路

目标：赢得这场游戏，即实现「回报」最大。
策略：得到「最优价值函数 $Q^(s,a)$」，这样就能通过带入状态 $s$，解算出最优动作 $a^ = argmax_a \ Q^*(s,a)$
问题： $Q^*(s,a)$ 只能通过上帝视角得到，角色是无法认知。
解决：利用一个神经网络 $Q(s,a;w)$ 来近似拟合出 $Q^*(s,a)$
- s：神经网络的输入
- a：神经网络的输出
- w：神经网络的参数

1. 问题模型

问题： 设计一个神经网络 $Q(w)$，对从NYC驾驶到atlanta所要花费的时间进行预测。

2. 梯度下降算法

模型估计时间： $q=Q(w) = 1000 min$；
真实驾驶时间： $y = 860 min$
计算损失值：$L = \frac{1}{2} ( q - y )^2$
计算关于系数 $w$ 的梯度：$\frac{\partial L}{\partial w} = \frac{\partial L}{\partial q} \frac{\partial q}{ \partial w} = (q - y) \frac{\partial Q(w)}{\partial w}$
更新系数：$w = w - \alpha \frac{\partial L}{\partial w}$

梯度下降法只能利用从NYC驾驶到atlanta跑完全程的时间作为真实时间 $y$ 进行计算，不能利用其中一段的时间。而DT算法则对这个情况进行改进。

3. 时间差分算法

模型估计时间： $q=Q(w) = 1000 min$；
真实驾驶时间只有从NYC到DC的 300 min，剩余的路程可以通过模型估计：$y = 300 + 600 = 900 min$
计算损失值：$L = \frac{1}{2} ( q - y )^2$
计算关于系数 $w$ 的梯度：$\frac{\partial L}{\partial w} = \frac{\partial L}{\partial q} \frac{\partial q}{ \partial w} = (q - y) \frac{\partial Q(w)}{\partial w}$
更新系数：$w = w - \alpha \frac{\partial L}{\partial w}$

思路： 由于DQN算法的目标是实现 $U_t$ 的最大化

\begin{aligned} U_t &= R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \gamma^3 R_{t + 3} + \dotsm \\ U_{t+1} &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t + 3} + \dotsm \\ \end{aligned}

对公式进行简化

\begin{aligned} U_t &= R_t + \gamma U_{t+1} \end{aligned}

将上述公式与DT算法进行对照：

$U_t$ 与 $U_{t+1}$ 就是 $Q(s,a;w)$ 模型的预测值：$Q(s_t,a_t;w)$ 、$Q(s_{t+1},a_{t+1};w)$
$R_t$就是一次工况下的部分真实测量值
TD目标就为： $$ \begin{aligned} y_t =& R_t + \gamma Q(s_{t+1},a_{t+1};w) \ =& R_t +\gamma \ max \ Q(s_{t+1},a;w) \end{aligned} $$
TD误差就为： $$ Q(s_t,a_t;w) - [R_t + \gamma Q(s_{t+1},a_{t+1};w)] $$