【RL】Temporal-Difference Learning（时序差分方法）

本文主要是介绍【RL】Temporal-Difference Learning（时序差分方法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Lecture 7: Temporal-Difference Learning

TD learning of state values

TD learning通常指的是一大类 RL 算法

TD学习也指用于估计state value的特定算法。

TD learning of state values – Algorithm description

算法中需要的data/experience：

$(s_0,r_1,s_1,...,s_t,r_{t+1},s_{t+1},\cdots )$或由给定的policy $\pi$生成的$\{(s_t,r_{t+1}),s_{t+1}\}$。

TD learning算法为：
$$\begin{array}{rl}& v_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]],(1)\\ & v_{t+1}(s)=v_t(s),\forall s\ne s_t,(2)\end{array}$$
其中，$t=0,1,2,\cdots$，$v_t(s_t)$是针对$v_{\pi }(s_t)$的估计的state value，${\alpha }_t(s_t)$是在时间$t$ $s_t$的 learning rate（学习率）。

• 在时间$t$，仅更新已访问状态$s_t$ 的值，而未访问状态$s\ne s_t$ 的值保持不变。

TD learning of state values – Algorithm properties

TD算法可以表示为:
$$\underset{\text{new estimate}}{\underbrace{v_{t+1}(s_t)}}=\underset{\text{current estimate}}{\underbrace{v_t(s_t)}}-{\alpha }_t(s_t)[\stackrel{\text{TD error }{\delta }_t}{\overbrace{v_t(s_t)-[\underset{\text{TD target }{\bar{v}}_t}{\underbrace{r_{t+1}+\gamma v_t(s_{t+1})}}]}},(3)$$
其中：
$$\overline{v}\doteq r_{t+1}+\gamma v(s_t+1)$$
被称为TD target；
$${\delta }_t\doteq v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]=v(s_t)-{\bar{v}}_t$$
被称为 TD error；

很明显，新的估计$v_{t+1}(s_t)$ 是当前估计 $v_t(s_t)$ 和 TD error的加权组合。

why is ${\overline{v}}_t$ called the TD target?

这是因为算法使$v(s_t)$趋向于${\overline{v}}_t$

如下式：
$$\begin{array}{rl}& v_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]\\ \Rightarrow & v_{t+1}(s_t)-{\bar{v}}_t=v_t(s_t)-{\bar{v}}_t-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]\\ \Rightarrow & v_{t+1}(s_t)-{\bar{v}}_t=[1-{\alpha }_t(s_t)][v_t(s_t)-{\bar{v}}_t]\\ \Rightarrow & |v_{t+1}(s_t)-{\bar{v}}_t|=|1-{\alpha }_t(s_t)||v_t(s_t)-{\bar{v}}_t|\end{array}$$
因为 ${\alpha }_t(s_t)$是一个小的正数，故:
$$0<1-{\alpha }_{(}{s}_t)<1$$
因此，
$$|v_{t+1}(s_t)-{\bar{v}}_t|\le |v_{(}{s}_t)-{\bar{v}}_t|$$
因此，$v(s_t)$不断趋向于${\bar{v}}_t$。

what is the interpretation of the TD error?
$${\delta }_t=v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]$$
它是两个后续时间步长之间的差异。

其反映了$v_t$和$v_{\pi }$之间的不足。 如下式：
$${\delta }_{\pi ,t}\doteq v_{\pi }(s_t)-[r_{t+1}+\gamma v_{\pi }(s_{t+1})]$$
注意：
$$\mathbb{E}[{\delta }_{\pi ,t}|S_t=s_t]=v_{\pi }(s_t)-\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s_t]=0.$$

• 如果$v_t=v_{\pi }$，那么${\delta }_t$应该为0
• 因此，若${\delta }_t$非0，那么$v_t$不等于$v_{\pi }$

TD error可以理解为“创新”，即从experience（经验）中获得新的信息$(s_t,r_{t+1},s_{t+1})$。

等式（3）仅估计了给定policy的state value。

• 其没有估计action value
• 其没有搜索最优policy

TD learning of state values – The idea of the algorithm

What does this TD algorithm do mathematically?

它求解给定policy $\pi$ 的Bellman方程。

第一，Bellman方程的新表达式。

policy $\pi$ 的state value的定义为：
$$v_{\pi }(s)=\mathbb{E}[R+\gamma G|S=s],s\in \mathcal{S}(4)$$
其中，$G$使离散的return。因为：
$$\mathbb{E}[G|S=s]=\sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })=\mathbb{E}[v_{\pi }(S^{\prime })|S=s],$$
其中，$S^{\prime }$是下一个state，因此等式（4）可以写为：
$$v_{\pi }(s)=\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s],s\in \mathcal{S}.(5)$$
等式（5）是Bellman等式的另一种表达，其也被称为Bellman expectation equation。

第二，使用RM算法解决等式（5）

定义：
$$g(v(s))=v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s],$$
公式（5）可以写为：
$$g(v(s))=0$$
由于我们只能获得 $R$ 和 $S^{\prime }$ 的样本 $r$ 和 $s^{\prime }$ ，因此我们得到的噪声观测值是:
$$\begin{array}{rl}\tilde{g}(v(s))& =v(s)-\left[\begin{array}{c}r+\gamma v_{\pi }(s^{\prime })\end{array}\right]\\ & =\underset{g(v(s))}{\underbrace{\left(v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s]\right)}}+\underset{\eta }{\underbrace{\left(\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s]-[r+\gamma v_{\pi }(s^{\prime })]\right)}}.\end{array}$$
因此，为了计算$g(v(s))$，RM算法为：
$$\begin{array}{rl}{v}_{k+1}(s)=& v_k(s)-{\alpha }_k\tilde{g}(v_k(s))\\ =& v_k(s)-{\alpha }_k(v_k(s)-[r_k+\gamma v_{\pi }(s_k^{\prime })\left]\right),\end{array}k=1,2,3,\cdots (6)$$
其中，$v_k(s)$是$v_{\pi }(s)$在第$k$步的估计；$r_k,s_k^{\prime }$是在第$k$步中在$R,S^{\prime }$中的样本。

公式（6）中的RM算法有两个假设需要特别注意：

• 必须要有experience集合$\{(s,r,s^{\prime })\},k=1,2,3,\dots$
• 假设对于任意$s^{\prime }$，$v_{\pi }(s^{\prime })$已知

为了在RM算法中移除这两个假设，可以将其修改为：

• 将 $\{(s,r,s^{\prime })\}$ 更改为 $(s_t,r_{t+1},s_{t+1})$，以便算法可以利用episode中的连续样本。
• $v_{\pi }(s^{\prime })$ 被它的估计值取代，因为事先不知道它。

Theorem (Convergence of TD Learning)

By the TD algorithm (1), $v_t(s)$ converges with probability 1 to $v_{\pi }(s)$ for all $s\in S$ as $t\to \infty$ if ${\sum }_t{\alpha }_t(s)=\infty$ and ${\sum }_t{\alpha }_t^2(s)<\infty$ for all $s\in S$.

• 该定理表示，对于给定的policy $\pi$，可以通过 TD 算法找到state value
• ${\sum }_t{\alpha }_t(s)=\infty$和${\sum }_t{\alpha }_t^2(s)<\infty$必须对所有$s\in S$都满足。在时间步 $t$，如果 $s=s_t$，这意味着 $s$ 在时间 $t$ 被访问，则 ${\alpha }_t(s)>0$； 否则，对于所有其他 $s\ne st$，${\alpha }_t(s)=0$。 这要求每个state必须被访问无限（或足够多）次。
• 学习率$\alpha$通常被选为一个小的常数。 此时，${\sum }_t{\alpha }_t^2(s)<\infty$的条件不再成立。 当$\alpha$一定时，仍然可以证明算法在期望意义上收敛。

算法比较：

TD/Sarsa learning	MC learning
Online: TD learning是online的。 它可以在收到reward后立即更新state/action value。	offline: MC learning是offline的。 它必须等到一个episode完全收集完毕。
Continuing tasks：由于TD学习是online的，因此它可以处理episodic任务和连续任务。	Episodic任务：由于MC学习是离线的，它只能处理具有终止状态的episodic任务。
Bootstrapping: TD bootstraps是因为值的更新依赖于该值的先前估计。 因此，它需要初始猜测。	Non-bootstrapping: MC不是bootstrapping，因为它可以无需任何初始猜测即可估计state/action value。
低估计方差：TD 比 MC 低，因为随机变量较少。 例如，Sarsa 需要 $R_{t+1}、S_{t+1}、A_{t+1}$。	高估计方差：为了估计 $q_{\pi }(s_t,a_t)$，需要 $R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$ 样本。假设每个episode的长度为$L$。有$

TD learning of action values: Sarsa

Sarsa – Algorithm

上一节介绍的TD算法只能估计state value。
接下来将介绍Sarsa，一个可以直接估计state value的算法。

首先，我们的目标是估计给定policy $\pi$ 的action value。假设有一些经验 $\{(s_t,a_t,r_{t+1},s_{t+1},a_{t+1}){\}}_t$。那么可以使用以下 Sarsa 算法来估计动作值：
$$\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]],\\ q_{t+1}(s,a)& =q_t(s,a),\forall (s,a)\ne (s_t,a_t),\end{array}$$
其中：$t=0,1,2,\cdots$

• $q_t(s_t,a_t)$是$q_{\pi }(s_t,a_t)$的估计值
• ${\alpha }_t(s_t,a_t)$是依赖于$s_t,a_t$的学习率。

Why is this algorithm called Sarsa?

因为算法的每一步都涉及$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$。 Sarsa 是state-action-reward-state-action的缩写。

What is the relationship between Sarsa and the previous TD learning algorithm?

可以通过将TD算法中的state value估计$v(s)$替换为action value估计$q(s,a)$来获得Sarsa。 因此，Sarsa 是 TD 算法的action-value版。

What does the Sarsa algorithm do mathematically?

Sarsa 的表达式表明其是求解以下方程的随机近似算法：
$$q_{\pi }(s,a)=\mathbb{E}\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a\right],\forall s,a.$$
这是Bellman方程的另一种以action value表示的表达式。

Theorem (Convergence of Sarsa learning)

By the e Sarsa algorithm, $q_t(s,a)$ converges with probability 1 to action value $q_{\pi }(s,a)$ as $t\to \infty$ for all $(s,a)$ if ${\sum }_t{\alpha }_t(s)=\infty$ and ${\sum }_t{\alpha }_t^2(s)<\infty$ for all $(s,a)$.

该定理表明，对于给定的policy $\pi$，Sarsa 可以找到action value。

Sarsa – Implementation

强化学习的最终目标是找到最优policy。
为此，可以将 Sarsa 与policy improvement步骤结合起来。组合算法也称为 Sarsa。

• $s_t$ 的policy在 $q(s_t,a_t)$更新后立即更新。 这是基于广义policy迭代的思想。
• 政策是$\epsilon$-greedy而不是贪心，以很好地平衡开采（exploitation）和探索（exploration）。
• 核心思想很简单：就是用一种算法来求解给定policy的Bellman方程。

Sarsa – Examples

$r_{\text{target}}=0,r_{\text{forbidden}}=r_{\text{boundary}}=-10$，$r_{\text{other}}=-1$，学习率$\alpha =0.1$，$\epsilon =0.1$

如上图左：并非所有state都有最优policy

如上图右：每episode总reward的指标将被频繁使用。

TD learning of action values: Expected Sarsa

Sarsa 的一个变体是 Expected Sarsa 算法：
$$\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-(r_{t+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)])],\\ q_{t+1}(s,a)& =q_t(s,a),\forall (s,a)\ne (s_t,a_t),\end{array}$$
其中，
$$\mathbb{E}[q_t(s_{t+1},A)])=\sum _a{\pi }_t(a|s_{t+1})q_t(s_{t+1},a)\doteq v_t(s_{t+1})$$
是policy ${\pi }_t$ 下 $q_t(s_{t+1},a)$ 的期望值。

与Sarsa比较：

• TD target 从 Sarsa 中的 $r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$ 更改为 Expected Sarsa 中的 $r_{t+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)]$。
• 需要更多的计算。 但从减少估计方差的意义上来说，它是有益的，因为它将 Sarsa 中的随机变量从 { s t , a t , r t + 1 , s t + 1 , a t + 1 } \{s_t,a_t,r_{t+1},s_{t+1},a_{t+1}\} {st​,at​,rt+1​,st+1​,at+1​}减少到 { s t , a t , r t + 1 , s t + 1 } \{s_t,a_t,r_{t+1},s_{t+1}\} {st​,at​,rt+1​,st+1​}。

What does the algorithm do mathematically?

Expected Sarsa 是一种随机近似算法，用于求解以下方程:
$$q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma {\mathbb{E}}_{A_{t+1}\sim \pi (S_{t+1})}[q_{\pi }(S_{t+1},A_{t+1})]|S_t=s,A_t=a],\forall s,a.$$
上式是Bellman方程的另一种表达：
$$q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s,A_t=a]$$

TD learning of action values: n-step Sarsa

$n$-step Sarsa：可以统一 Sarsa 和 Monte Carlo learning

action value的定义为：
$$q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=s,A_t=a].$$
discount return $G_t$ 可以写成不同的形式：
$$\begin{array}{rl}\text{Sarsa}⟵G_t^{(1)}& =R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1}),\\ G_t^{(2)}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{q}_{\pi }(S_{t+2},A_{t+2}),\\ & ⋮\\ n\text{-step Sarsa}⟵G_t^{(n)}& =R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n}),\\ & ⋮\\ \text{MC}⟵G_t^{(\infty )}& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \end{array}$$
需要注意的是，$\begin{array}{r}{G}_t=G_t^{(1)}=G_t^{(2)}=G_t^{(n)}=G_t^{(\infty )}\end{array}$，其中上标仅表示$G_t$的不同分解结构。

Sarsa目的是解决：
$$q_{\pi }(s,a)=\mathbb{E}[G_t^{(1)}|s,a]=\mathbb{E}[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|s,a].$$
MC目的是解决：
$$q_{\pi }(s,a)=\mathbb{E}[G_t^{(\infty )}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots |s,a].$$
$n$-step Sarsa 的中间算法目的是解决：
$$\begin{array}{r}{q}_{\pi }(s,a)=\mathbb{E}[G_t^{(n)}|s,a]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})|s,a].\end{array}$$
$n$-step Sarsa 算法目的是解决：
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_t(s_{t+n},a_{t+n})]].$$
$n$-step Sarsa 更通用，因为当$n=1$ 时它变成（one-step）Sarsa 算法，当 $n=\infty$ 时它变成 MC learning算法。

$n$-step Sarsa需要$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1},\dots ,r_{t+n},s_{t+n},a_{t+n}).$

由于 $(r_{t+n},s_{t+n},a_{t+n})$在时间 $t$ 尚未收集，因此无法在步骤 $t$ 实现 $n$-step Sarsa。 然而，可以等到时间 $t+n$ 来更新 $(s_t,a_t)$ 的 q 值：
$$\begin{array}{rl}{q}_{t+n}(s_t,a_t)=& q_{t+n-1}(s_t,a_t)\\ & -{\alpha }_{t+n-1}(s_t,a_t)[q_{t+n-1}(s_t,a_t)-[r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_{t+n-1}(s_{t+n},a_{t+n})]]\end{array}$$
由于 $n$-step Sarsa 将 Sarsa 和 MC learning作为两种极端情况，因此其性能是 Sarsa 和 MC learning的混合：

• 如果$n$很大，它的性能接近MC learning，因此方差很大但偏差很小。
• 如果$n$较小，则其性能接近Sarsa，因此由于初始猜测和相对较低的方差而具有相对较大的偏差。

n-step Sarsa 也用于policy evaluation。 它可以与policy improvement步骤相结合来搜索最优policy。

TD learning of optimal action values: Q-learning

Sarsa 可以估计给定policy的action value。 它必须与policy improvement步骤相结合才能找到最佳policy。

Q-learning 可以直接估计最优action value，从而估计最优policy。

Q-learning – Algorithm

Q-learning算法为：
$$\begin{array}{rl}{q}_{t+1}(s_t,a_t)& =q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-[r_{t+1}+\gamma \underset{a\in \mathcal{A}}{\max }{q}_t(s_{t+1},a)]\right],\\ q_{t+1}(s,a)& =q_t(s,a),\forall (s,a)\ne (s_t,a_t),\end{array}$$
Q-learning 与 Sarsa 非常相似。 它们仅在 TD target方面有所不同：

• Q-learning 中的 TD target是: $r_{t+1}+\gamma {\max }_{a\in \mathcal{A}}{q}_t(s_{t+1},a)$
• Sarsa 中的 TD target是: $r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$

What does Q-learning do mathematically?

其目的是解决：
$$q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)\right|S_t=s,A_t=a],\forall s,a.$$
这是用action values表示的Bellman最优方程。

Off-policy vs on-policy

在进一步研究Q-learning之前，需要首先介绍两个重要的概念：on-policy learning和off-policy learning。
TD learning任务中存在两种policy：

• behavior policy用于生成经验样本
• target policy不断更新以达到最优policy

On-policy vs off-policy：

• 当behavior policy与target policy相同时，这种学习称为on-policy learning。
• 当不同时，称为off-policy learning。

Advantages of off-policy learning：

它可以根据任何其他policy生成的经验样本来搜索最优policy。

作为一个重要的特例，behavior policy可以选择具有探索性。 例如，如果想估计所有state-action对的action value，可以使用探索性policy来生成多次访问每个state-action对的episode。

How to judge if a TD algorithm is on-policy or off-policy?

首先，检查算法在数学上的作用。

其次，检查实现算法需要哪些东西。

Sarsa is on-policy.

首先，Sarsa 的目标是求解给定policy $\pi$ 的Bellman方程：
$$q_{\pi }(s,a)=\mathbb{E}\left[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a\right],\forall s,a.$$
其中，$R\sim p(R|s,a),S^{\prime }\sim p(S^{\prime }|s,a),A^{\prime }\sim \pi (A^{\prime }|S^{\prime }).$

其次，算法是:
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-[r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})]],$$
需要$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$

如果给出 $(s_t,a_t)$，则$r_{t+1}$ 和 $s_{t+1}$ 不依赖于任何policy。$a_{t+1}$ 是根据 ${\pi }_t(s_{t+1})$生成的。

${\pi }_t$ 既是behavior policy又是target policy。

Monte Carlo learning is on-policy.

首先，MC方法目的是计算：
$$q_{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\dots |S_t=s,A_t=a\right],\forall s,a.$$
其中样本是根据给定policy $\pi$ 生成的。

其次，MC方法的实现是：
$$q(s,a)\approx r_{t+1}+\gamma r_{t+2}+\dots$$
action value用于生成样本，样本进一步用于估计policy的action value。 基于action value，可以改进policy。

Q-learning is off-policy.

首先，Q-learning旨在求解Bellman最优方程：
$$q(s,a)=\mathbb{E}\left[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S_t=s,A_t=a\right],\forall s,a.$$
其次，算法为：
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)\left[q_t(s_t,a_t)-[r_{t+1}+\gamma \underset{a\in \mathcal{A}}{\max }{q}_t(s_{t+1},a)]\right]$$
需要$(s_t,a_t,r_{t+1},s_{t+1}).$

根据 $s_t$ 生成 $a_t$ 的behavior policy可以是任何内容。 target policy将收敛于最优policy。

由于 Q-learning是off-policy的，因此它可以既可以以off-policy形式实现也可以以on-policy形式实现。

Q-learning – Examples

$r_{\text{boundary}}=r_{\text{forbidden}}=-1$，$r_{\text{target}}=1$。discount rate $\gamma =0.9$。学习率$\alpha =0.1$。

下图是behavior policy和其生成的样本（$10^5$步）：

off-policy Q-learning 学习到的policy：

探索的重要性：$10^5$个episode
如果policy探索性不够，样本就不够好。如下图：

A unified point of view

本讲介绍的所有算法都可以用一个统一的表达式来表示：
$$q_{t+1}(s_t,a_t)=q_t(s_t,a_t)-{\alpha }_t(s_t,a_t)[q_t(s_t,a_t)-{\bar{q}}_t],$$
其中，${\bar{q}}_t$是TD target。

不同的TD算法有不同的${\bar{q}}_t$。

Algorithm	Expression of ${\bar{q}}_t$
Sarsa	${\bar{q}}_t=r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$
$n$-step Sarsa	${\bar{q}}_t=r_{t+1}+\gamma r_{t+2}+\cdots +{\gamma }^n{q}_t(s_{t+n},a_{t+n})$
Expected Sarsa	${\bar{q}}_t=r_{t+1}+\gamma {\sum }_a{\pi }_t(a|s_{t+1})q_t(s_{t+1},a)$
Q-learning	${\bar{q}}_t=r_{t+1}+\gamma {\max }_a{q}_t(s_{t+1},a)$
Monte Carlo	${\bar{q}}_t=r_{t+1}+\gamma r_{t+2}+\dots$

MC 方法也可以通过设置 ${\alpha }_t(s_t,a_t)=1$ 从而 $q_{t+1}(s_t,a_t)={\bar{q}}_t$ 来表达在这个统一表达式中。

所有算法都可以看作求解Bellman方程或Bellman最优方程的随机近似算法：

Algorithm	Equation aimed to solve
Sarsa	$\text{BE: }{q}_{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})S_t=s,A_t=a\right]$
$n$-step Sarsa	$\text{BE: }{q}_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\cdots +{\gamma }^n{q}_{\pi }(s_{t+n},a_{t+n})S_t=s,A_t=a]$
Expected Sarsa	$\text{BE: }{q}_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma {\mathbb{E}}_{A_{t+1}}[q_{\pi }(S_{t+1},A_{t+1})]|S_t=s,A_t=a]$
Q-learning	$\text{BE: }q(s,a)=\mathbb{E}\left[R_{t+1}+{\max }_{a}q(S_{t+1},a)|S_t=s,A_t=a\right]$
Monte Carlo	$\text{BE: }{q}_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+\dots |S_t=s,A_t=a]$

Summary

• Introduced various TD learning algorithms
• Their expressions, math interpretations, implementation, relationship, examples
• Unified point of view

以上内容为B站西湖大学智能无人系统 强化学习的数学原理 公开课笔记。

这篇关于【RL】Temporal-Difference Learning（时序差分方法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---