在理解蒙特卡洛方法和时序差分学习一文中已经对时序差分学习进行了直观上的解释，本文中将具体的描述时序差分学习的数学推导过程及在强化学习中的应用。

一、时序差分学习的数学推导

根据折扣回报（Discounted Return）的定义，有：

Gt=Rt+γ⋅Rt+1+γ2⋅Rt+2+γ3⋅Rt+3+⋯=Rt+γ⋅(Rt+1+γ⋅Rt+2+γ2⋅Rt+3+⋯ )=Rt+γ⋅Gt+1\begin{aligned} G_t & = R_t + \gamma \cdot R_{t+1} + \gamma^2 \cdot R_{t+2} + \gamma^3 \cdot R_{t+3} + \cdots \\ & = R_t + \gamma \cdot (R_{t+1} + \gamma \cdot R_{t+2} + \gamma^2 \cdot R_{t+3} + \cdots) \\ & = R_t + \gamma \cdot G_{t+1} \end{aligned}

根据动作价值函数（Action-value function）的定义，有：

Qπ(st,at)=E[Gt∣st,at]=E[Rt+γ⋅Gt+1∣st,at]=E[Rt∣st,at]+γ⋅E[Gt+1∣st,at]=E[Rt∣st,at]+γ⋅E[Qπ(St+1,At+1)∣st,at]=E[Rt+γ⋅Qπ(St+1,At+1)]\begin{aligned} Q_{\pi}(s_t, a_t) & = \mathbb{E}[G_t | s_t, a_t] \\ & = \mathbb{E}[R_t + \gamma \cdot G_{t+1} | s_t, a_t] \\ & = \mathbb{E}[R_t | s_t, a_t] + \gamma \cdot \mathbb{E}[G_{t+1} | s_t, a_t] \\ & = \mathbb{E}[R_t | s_t, a_t] + \gamma \cdot \mathbb{E}[Q_{\pi}(S_{t+1}, A_{t+1}) | s_t, a_t] \\ & = \mathbb{E}[R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1})] \\ \end{aligned}

即，对所有的策略 π\pi 都有如下的等式：

Qπ(st,at)=E[Rt+γ⋅Qπ(St+1,At+1)], for all πQ_{\pi}(s_t, a_t) = \mathbb{E}[R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1})], \text{ for all }\pi

直接求 Rt+γ⋅Qπ(St+1,At+1)R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1}) 的期望很困难，可以对期望做蒙特卡洛（Monte Carlo）近似，即：

  • 使用真实的奖励值 rtr_t 来近似 RtR_t。
  • 使用真实的Q值 Qπ(st+1,at+1)Q_{\pi}(s_{t+1}, a_{t+1}) 来近似 Qπ(St+1,At+1)Q_{\pi}(S_{t+1}, A_{t+1}) 。

所以：

Qπ(st,at)=E[Rt+γ⋅Qπ(St+1,At+1)]≈rt+γ⋅Qπ(st+1,at+1)\begin{aligned} Q_{\pi}(s_t, a_t) & = \mathbb{E}[R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1})] \\ & \approx r_t + \gamma \cdot Q_{\pi}(s_{t+1}, a_{t+1}) \\ \end{aligned}

结论：

  1. 常将 rt+γ⋅Qπ(st+1,at+1)r_t + \gamma \cdot Q_{\pi}(s_{t+1}, a_{t+1}) 的值记作 yty_t 。
  2. 因为 yty_t 中包含了真实的奖励值 rtr_t ，所以认为 yty_t 比 Qπ(st,at)Q_{\pi}(s_t, a_t) 更准确。
  3. 将 yty_t 命名为 TD target，而将 yt−Qπ(st,at)y_t - Q_{\pi}(s_t, a_t) 的值命名为 TD error。
  4. TD error 的绝对值越小，就表明模型预测误差越小，预测的结果越准确。所以，在确定好 TD error 的计算方式后，可以通过 梯度下降 方法来更新模型的参数，降低 TD error 。
  5. 时序差分学习的目的是让模型预测出的 Qπ(st,at)Q_{\pi}(s_t, a_t) 值不断的接近TD target 。

二、Sarsa算法

Sarsa是State–action–reward–state–action这几个单词的缩写。

时序差分学习的一个应用就是Sarsa算法，Sarsa算法的目的就是使用神经网络 Q(s,a)Q(s,a) 去逼近 动作价值函数（action-value function）Qπ(s,a)Q_{\pi}(s,a) 。

Sarsa算法的TD target为 yt=rt+γ⋅Q(st+1,at+1)y_t = r_t + \gamma \cdot Q(s_{t+1}, a_{t+1}) 。

三、Q-Learning算法的数学推导

在时序差分学习的数学推导中得到了，对所有的策略 π\pi 都有如下的等式：

Qπ(st,at)=E[Rt+γ⋅Qπ(St+1,At+1)], for all πQ_{\pi}(s_t, a_t) = \mathbb{E}[R_t + \gamma \cdot Q_{\pi}(S_{t+1}, A_{t+1})], \text{ for all }\pi

对最优策略 π∗{\pi}_* 也成立，所以：

Q∗(st,at)=E[Rt+γ⋅Q∗(St+1,At+1)]Q_*(s_t, a_t) = \mathbb{E}[R_t + \gamma \cdot Q_*(S_{t+1}, A_{t+1})]

Qπ∗(st,at)Q_{\pi_*}(s_t, a_t) 可以简写为 Q∗(st,at)Q_*(s_t, a_t) ，都可以表示最优动作价值函数。

因为最优动作价值函数总是采用最优的动作：

At+1=argmax⁡aQ∗(St+1,a)A_{t+1} = \underset{a}{\operatorname{argmax}}Q_*(S_{t+1}, a)

所以：

Q∗(St+1,At+1)=max⁡aQ∗(St+1,a)Q_*(S_{t+1}, A_{t+1}) = \max_a Q_* (S_{t+1}, a)

即：

Q∗(st,at)=E[Rt+γ⋅Q∗(St+1,At+1)]=E[Rt+γ⋅max⁡aQ∗(St+1,a)]\begin{aligned} Q_*(s_t, a_t) & = \mathbb{E}[R_t + \gamma \cdot Q_*(S_{t+1}, A_{t+1})] \\ & = \mathbb{E}[R_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_* (S_{t+1}, a)] \\ \end{aligned}

直接求 Rt+γ⋅max⁡aQ∗(St+1,a)R_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_* (S_{t+1}, a) 的期望很困难，可以对期望做蒙特卡洛（Monte Carlo）近似，即：

  • 使用真实的奖励值 rtr_t 来近似 RtR_t。
  • 使用真实的Q值 max⁡aQ∗(st+1,a)\underset{a}{ \operatorname{max} } Q_*(s_{t+1}, a) 来近似 max⁡aQ∗(St+1,a)\underset{a}{ \operatorname{max} } Q_*(S_{t+1}, a) 。

所以：

Q∗(st,at)=E[Rt+γ⋅max⁡aQ∗(St+1,a)]≈rt+γ⋅max⁡aQ∗(st+1,a)\begin{aligned} Q_*(s_t, a_t) & = \mathbb{E}[R_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_* (S_{t+1}, a)] \\ & \approx r_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_*(s_{t+1}, a) \\ \end{aligned}

四、Q-Learning算法

时序差分学习的另一个应用就是Q-Learning算法，Q-Learning算法的目的就是使用神经网络 Q(s,a)Q(s,a) 去逼近 最优动作价值函数（optimal action-value function）Q∗(s,a)Q_*(s,a) 。

Q-Learning算法的TD target为 yt=rt+γ⋅max⁡aQ∗(st+1,a)y_t = r_t + \gamma \cdot \underset{a}{\operatorname{max}} Q_*(s_{t+1}, a) 。

参考：TD Learning