由于全文太长，只好分开发了。 (已完结！在专栏查看本系列其他文章）

个人博客可以直接看全文~

本系列为在学习赵世钰老师的“强化学习的数学原理” 课程后所作笔记。

课堂视频链接https://www.bilibili.com/video/BV1sd4y167NS/

第七章 Temporal-Difference learning

Temporal-Difference learning （TD）时序差分算法

这是一个incremental 迭代式的算法。

motivating example

1. 先考虑一个简单的问题 mean estimation ： 计算

$w=[X]$ , (X是一些iid(独立同分布)采样 { x } \{x\} {x})

令$g(w)=w-\mathbb{E}[X]$ ,则有

$\tilde{g}(w,\eta )=w-x=(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\approx g(w)+\eta$

然后根据RM算法，可以得到$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-x_k)$

2. 考虑一个复杂一些的例子：计算

$w=\mathbb{E}[v(X)]$ , (X是一些iid(独立同分布)采样 { x } \{x\} {x})

令$g(w)=w-\mathbb{E}[v(X)]$

$\tilde{g}(w,\eta )=w-v(x)=(w-\mathbb{E}[X])+(\mathbb{E}[X]-v(x))\approx g(w)+\eta$

然后根据RM算法，可以得到$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-v(x_k))$

3. 第三个例子：计算

$w=[R+\gamma v(X)]$ , ($R,X$ 是随机变量，$\gamma$ 是常量，$v(\cdot )$ 是函数)

令$g(w)=w-\mathbb{E}[R+\gamma v(X)]$ ,
$$\begin{array}{rl}\tilde{g}(w,\eta )& =w-\mathbb{E}[R+\gamma v(X)]\\ & =(w-\mathbb{E}[R+\gamma v(X)])+(\mathbb{E}[R+\gamma v(X)]-[r+\gamma v(X)])\\ & \approx g(w)+\eta \end{array}$$
然后根据RM算法，可以得到KaTeX parse error: Invalid color: ' #0000FF' at position 11: \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{w_{k+1} = w_k …

TD算法中的state values

注意：

• TD算法通常指的是一大类的RL算法。
• TD算法也可以特指一种用于估计state values的算法。

TD算法基于数据：$(s_0,r_1,s_1,...,s_t,r_{t+1},s_{t+1},...)$ 或者$\{(s_t,r_{t+1},s_{t+1}){\}}_t$ ，这种数据通过给定的策略$\pi$ 来生成。

TD算法则是：
$$\begin{array}{rlr}{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}$$
对于公式$(2)$ 表示，如果现在的状态是$s_t$ ，那么其他状态的value是不更新的。

我们关注于第一个式子：

$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})]]$

其中的$v_{t+1}(s_t)$ 是新的估计值，$v_t(s_t)$ 是现在的估计值。

$v_t(s_t)-[r_{t+1}+\gamma v_t(s_{t+1})]$ 是误差${\delta }_t$

$[r_{t+1}+\gamma v_t(s_{t+1})]$ 是目标${\overline{v}}_t$

为什么${\overline{v}}_t$ 是“TD目标” ？因为每次$v(s_t)$ 都会向着 ${\overline{v}}_t$ 移动。
KaTeX parse error: Invalid color: ' #0000FF' at position 127: …s_t) \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{-\overline v_t…
因为$0<1-{\alpha }_t(s_t)<1$

于是$|v_{t+1}(s_t)-{\overline{v}}_t|\le |v_t(s_t)-{\overline{v}}_t|$

为什么 ${\delta }_t$是“TD error”？

${\delta }_t=v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]$

因为发生在t和t+1两个时刻 ，所以才叫时序差分，

TD error 描述了$v_t$ 和$v_{\pi }$ 之间的误差。

当$v_t=v_{\pi }$ 时，那么应该有${\delta }_t=0$ 。

TD error是一种 innovation，这是经验$(s_t,r_{t+1},s_{t+1})$的一种新的信息。

TD算法的数学意义

他解决了给定$\pi$，求解贝尔曼公式。

新的贝尔曼公式：
$$v_{\pi }(s)=\mathbb{E}[R+\gamma G|S=s],s\in S$$
在这之中G是下个状态的Reward，所以$\mathbb E[G|S = s] $可以表示为：
$$\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 }$ 是下一个状态

于是s的state value可以写为：
$$v_{\pi }(s)=\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s],s\in S$$
这个公式也被称为贝尔曼期望公式。

接下来使用RM算法来求解这个贝尔曼期望公式：
定义$g(v(s))=v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s]=0$

于是我们有$g(v(s))=0$
$$\begin{array}{rl}\tilde{g}(v(s))& =v(s)-[r+\gamma v_{\pi }(s^{\prime })]\\ & =(v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s])+(\mathbb{E}[R+\gamma v_{p}i(S^{\prime })|s]-[r+\gamma v_{\pi }(s^{\prime })])\end{array}$$
在这之中，$g(v(s)) = (v(s) - \mathbb E[R + \gamma v_\pi(S’)| s]) $ ,误差$\eta = E[R + \gamma v_pi(S’)| s] - [r + \gamma v_\pi (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 })]),k=1,2,3,...\end{array}$$
这里的$v_k(s)$代表$v_{\pi }(s)$在第k步的估计，而$r_k,s_k^{\prime }$ 是第k步中从$R,S^{\prime }$中取出的样本。

对公式做以下替换：

• 将一组采样$\{(s,r,s^{\prime })\}$ 替换为一组序列 { s t , r t + 1 , s t + 1 } \{s_t,r_{t+1},s_{t+1}\} {st​,rt+1​,st+1​}， 从而做到对所有的s都进行更新。

• 将$v_{\pi }(s^{\prime })$ 换为$v_k(s_k^{\prime })$ ，即我们直接用$s^{\prime }$ 在第k步的估计值来替代真实值。 虽然会有一些偏差，但是最终会收敛到$v_{\pi }$

TD算法的收敛：

对于所有状态$s\in S$ 。当$t\to \infty$ 时， $v_t(s)$ 以概率1收敛到策略$\pi$ 下的状态值函数$v_{\pi }(s)$。

如果对于所有的状态$s\in S$ ，步长参数序列${\alpha }_t(s)$ 都满足${\sum }_t{\alpha }_t=\infty$ 并且${\sum }_t{\alpha }_t^2(s)<\infty$ 那么上述收敛成立。

TD/Sarsa learning	MC learning
online：TD学习是在线的，在接收到一个奖励后可以更新state/action value	Not online：MClearning是非在线的，必须等到整个episode已经完成之后，计算return值然后进行估计。
continuing tasks：即能处理一直持续下去的任务，同时也能解决episodic tasks。	Episodic tasks：必须是有限步的episode，才能等到他的返回值。
Bootstrapping：会基于之前对状态的猜测，加上一些新的信息来形成一个新的猜测	Non-boostrapping：直接根据当前的episode计算return，不涉及到之前的估计值
Low estimation variance ：在算法过程中涉及到的随机变量比较少，所以方差会比较小	High estimation variance：它涉及到了很多的variable，因为一次episode会涉及到很多的Reward，而只用其中一次的采样，所以就会有比较大的方差。
bias：因为基于之前的经验，所以可能会因为之前的经验而产生bias，导致有偏估计，但是在不断增加经验后还是会趋于正确结果	no bias：不基于之前的估计，所以不会产生bias

TD算法中的action values：Sarsa

Sarsa是经验集$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ 的拼接。

TD算法是用来估计给定策略$\pi$ 的state value，但我们需要估计的是action value。下面引入Sarsa。

假设我们有如下经验$\{(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}$$
这个式子和TD算法几乎一样，只是类似地把$v_t(s_t)$ 改成了$q_t(s_t,a_t)$这样子。

Sarsa的数学意义和TD也是几乎一样的。（如贝尔曼公式，收敛性等）

Sarsa所求解的贝尔曼公式：
$$q_{\pi }(s,a)=\mathbb{E}[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a],\forall s,a$$

1. 收集经验：$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1})$ ,遵循${\pi }_t(s_t)$执行$a_t$ ，得到$r_{t+1}$的奖励，然后走到状态$s_{t+1}$ 并遵循${\pi }_t(s_{t+1})$ 来采取行动$a_{t+1}$ 。

2. 更新q值(q value update/policy evaluaton)：$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})]]$

3. 更新策略policy(policy update/policy improvement)：
   $$\begin{array}{rlr}{\pi }_{t+1}(a|s_t)& =1-\frac{ϵ}{|\mathrm{A}|}(|\mathrm{A}-1|),& ifa=argma{x}_a{q}_{t+1}(s_t,a)\\ {\pi }_{t+1}(a|s_t)& =\frac{ϵ}{|\mathrm{A}|},& otherwise\end{array}$$

注意这里的PE和PI是立刻执行的，而不是等return之后再精确计算。

注意这个策略是一个$ϵ-greedy$策略，也就是说倾向于采取qvalue最大的action，但是其他的action同样有概率取到。

Expected Sarsa

公式如下：
KaTeX parse error: Invalid color: ' #0000FF' at position 94: …a_t)-\textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{(r_{i+1} + \ga…
此处的$\mathbb{E}[q_t(s_{t+1},A)]=\sum _{\pi }{\pi }_t(a|s_{t+1})q_t(s_{t+1},a)\approx v_t(s_{t+1})$

和普通的sarsa的区别是用$(r_{i+1}+\gamma \mathbb{E}[q_t(s_{t+1},A)])$ 替换了$r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$.

不再需要$a_{t+1}$ 了,随机性会减小一些，但是需要更大的计算量。

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]$

n-step Sarsa

是Sarsa的一个推广，包含了Sarsa和蒙德卡罗方法。

我们的action value如下定义：$q_{\pi }(s,a)=\mathbb{E}[G_t|S_t=a,A_t=a]$

那么$G_t$ 可以被写成如下形式：
$$\begin{array}{rl}\text{Sarsa}\leftarrow & G_t^{(1)}=R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\\ & G_t^{(2)}=R_{t+1}+\gamma R_{t+1}+{\gamma }^2{q}_{\pi }(S_{t+2},A_{t+2})\\ & ...\\ \text{n-step Sarsa}\leftarrow & G_t^{(n)}=R_{t+1}+\gamma R_{t+2}+...+{\gamma }^n{q}_{\pi }(S_{t+n},A_{t+n})\\ & ...\\ MC\leftarrow & G_t^{(\infty )}=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}...\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}+...+{\gamma }^n{q}_t(s_{t+n},a_{t+n})]]$$
n-step Sarsa需要的数据是$(s_t,a_t,r_{t+1},s_{t+1},a_{t+1},...,r_{t+n},s_{t+n},a_{t+n})$

所以他的数据需要等到$t+n$ 时刻，才能进行更新。是online和offline的结合。

• 当n比较大的时候，更接近于MC，会有比较大的variance，比较小的bias。
• 当n比较小的时候，更接近于Sarsa，会有比较小的variance，比较大的bias。

TD中最优action value学习:Q-learning

算法如下：
KaTeX parse error: Invalid color: ' #0000FF' at position 97: …t) - \textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{[r_{t+1} + \ga…
和Sarsa相比，用$r_{t+1}+\gamma \underset{\alpha \in \mathcal{A}}{\max }{q}_t(s_{t+1},a)$ 替换了$r_{t+1}+\gamma q_t(s_{t+1},a_{t+1})$

Q-learning求解的数学问题是（不是在求解贝尔曼方程）：

求解一个贝尔曼最优方程：
$$q(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S_t=s,A_t=a],\forall s,a$$

off-policy 和 on-policy

两种策略：

1. behavior policy用来生成经验样本
2. target policy不断地更新来将target policy更新到optimal policy。

基于这两种策略，可以分为两类算法：

• on-policy： 其中的behavior policy和target policy是相同的，即用自己的策略来和环境交互，然后得到经验并改进自己的策略，之后再用相同的策略和环境交互。
• off-policy：用一个策略和环境交互得到大量经验，然后用这些经验来不断改进策略（一步到位，不再通过新的策略引入新的经验）

on-policy的好处就是可以不断接收新的经验，实时更新策略。

off-policy的好处就是可以直接使用别人已经获取过的经验。如用之前通过探索性较强的算法得到的经验。

如何判断一个TD算法是on-policy还是off-policy？

1. 看这个TD算法是在解决什么样的数学问题
2. 看在算法的执行过程中需要什么东西才能使算法跑起来

• Sarsa是on-policy的：

Sarsa在数学上就是在求解一个贝尔曼公式：
$$q_{\pi }(s,a)=\mathbb{E}[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a],\forall s,a$$
此处的KaTeX parse error: Invalid color: '0xFF0000' at position 45: …s,a),\textcolor{̲0̲x̲F̲F̲0̲0̲0̲0̲}̲{A' \sim \pi(A'…

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 q_t(s_{t+1},a_{t+1})]]$$

1. 如果给定了$(s_t,a_t)$ 那么$r_{t+1}$和$s_{t+1}$和任何策略无关，和$p(r|s,a),p(s^{\prime }|s,a)$有关。

2. $a_{t+1}$是由策略${\pi }_t(s_{t+1})$ 产生。 所以${\Pi }_t$ 既是behavior policy也是target policy

• MC learning 是on-policy的：

MC目的是求解如下贝尔曼方程：
$$q_{\pi }(s,a)=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+...|S_t=s,A_t=a]$$
MC的实现是
$$q(s,a)\approx r_{t+1}+\gamma r_{t+2}+...$$

我们用策略$\Pi$ 来得到trajectory经验，然后得到return来近似估计$q_{\pi }$ 进而改进$\Pi$

• Q learning 是off-policy的：

Q learning求解的数学问题是：

求解贝尔曼最优公式：
$$q(s,a)=\mathbb{E}[R_{t+1}+\gamma \underset{a}{\max }q(S_{t+1},a)|S_t=s,A_t=a],\forall s,a$$
Q learning的实现过程是：
$$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 \underset{\alpha \in \mathrm{A}}{\max }{q}_t(s_{t+1},a)]]$$
需要的经验是$(s_t,a_t,r_{t+1},s_{t+1})$

注意这里的经验不包含$a_{t+1}$

如果$(s_t,a_t)$ 给定，那么$r_{t+1}$ 和$s_{t+1}$ 不依赖于策略。

behavior policy是从$s_t$ 出发得到$a_t$

target policy 是根据$q_{\pi }$ 来选择action

Q-learning 的实施

如果将Q-learning中的behavior policy 和target policy强行设置为一致的，那么它可以是on-policy的：

0. 对每个episode执行以下三步

1. 收集经验$(s_t,a_t,r_{t+1},s_{t+1})$ ，在这一步根据${\pi }_t(s_t)$ 采取行动$a_t$ 来生成$(r_{t+1},s_{t+1})$

2. 更新q-value：$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 ma{x}_a{q}_t(s_{t+1},a)]]$

3. 更新policy：
   $$\begin{array}{rl}{\pi }_{t+1}(a|s_t)& =1-\frac{ϵ}{|\mathrm{A}|}(|\mathrm{A}|-1)\text{ if }a=\underset{a}{\mathrm{argmax}}{q}_{t+1}(s_t,a)\\ {\pi }_{t+1}(a|s_t)& =\frac{ϵ}{|\mathrm{A}|}\text{ otherwise}\end{array}$$

也可以是off-policy的：

0. 对每个episode生成策略${\pi }_b$ (这里的b代表behavior),这个策略用来生成experience

1. 对episode的每一步$t=0,1,2,...$ 执行以下两步：

2. 更新q-value:$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 ma{x}_a{q}_t(s_{t+1},a)]]$

3. 更新target policy:
   $$\begin{array}{rl}{\pi }_{T,t+1}(a|s_t)& =1\text{ if }a=\underset{a}{\mathrm{argmax}}{q}_{t+1}(s_t,a)\\ {\pi }_{T,t+1}(a|s_t)& =0\text{ otherwise}\end{array}$$

注意这里的第三步是greedy不是$ϵ-greedy$ ，因为我们不需要新的策略来生成经验，所以也就不需要使用$ϵ-greedy$ 来增加探索性，只需要保证最优性。

使用off-policy的话，使用的behavior policy最好是探索度比较强的策略，否则可能得不到好的target policy。

TD的统一表示

所有的TD算法都能用如下公式表达：
KaTeX parse error: Invalid color: ' #0000FF' at position 78: …a_t)-\textcolor{̲ ̲#̲0̲0̲0̲0̲F̲F̲}̲{\overline{q}_t…
这里的${\overline{q}}_t$ 就是TD target。

TD算法的目标就是接近TD target ，减小TD error

算法	${\overline{q}}_t$ 的表示
Sarsa	${\overline{q}}_t=r_{t+1}+\gamma q_t(s_{t+1}，a_{t+1})$
n-step Sarsa	${\overline{q}}_t=r_{t+1}+\gamma r_{t+2}+...+{\gamma }^n{q}_t(s_{t+n}，a_{t+n})$
Expected Sarsa	$\overline q_t = r_{t+1} + \gamma \underset{a}{\sum}\pi_i(a
Q-learning	${\overline{q}}_t=r_{t+1}+\gamma \underset{a}{\max }{q}_t(s_{t+1},a)$
Monte Carlo	${\overline{q}}_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+...$