PPT 截取有用信息。 课程网站做习题。总体 MOOC 过一遍

• 1、学堂在线 视频 + 习题
• 2、相应章节 过电子书 复习 【下载：本章 PDF 文档GitHub】
• 3、MOOC 习题
• 不理解的地方

学堂在线 课程页面链接
中国大学MOOC 课程页面链接
B 站 视频链接

PPT和书籍下载网址： 【GitHub链接】

---

——————

7.1 状态值 的 TD 学习算法

P1

temporal-difference (TD) learning 时间差分学习

第 5 章 蒙特卡洛方法 model-free 方法 非增量
本章的 TD 学习 是 第二种 model-free 方法 增量式
下一章介绍 的值函数近似 基于 TD 方法。

本章 (表格) ——> 下一章 (函数表示)

用 RM 算法 求解 3 个 问题：

问题 1：
简单的均值估计问题:： 基于随机变量$X$的独立同分布采样数据   { x }   ~\{x\}~  {x} ，计算 $w=\mathbb{E}[X]$。
令 $g(w)=w-\mathbb{E}[X]$, 将问题重新表述为 寻根问题 $g(w)=0$
可获取的 带误差的值 $\tilde{g}(w,\eta )=w-x=(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\doteq 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)$

$\doteq$$\doteq$

问题 2：
估计函数 $v(X)$ 的均值： $w=\mathbb{E}[v(X)]$， 基于$X$的独立同分布采样数据   { x }   ~\{x\}~  {x} 。
令 $g(w)=w-\mathbb{E}[v(X)]$, 将问题重新表述为 寻根问题 $g(w)=0$
可获取的 带误差的值 $\tilde{g}(w,\eta )=w-v(x)=(w-\mathbb{E}[v(X)])+(\mathbb{E}[v(X)]-v(x))\doteq 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=\mathbb{E}[R+\gamma v(X)]$， 基于$X$的独立同分布采样数据   { x }   ~\{x\}~  {x}  和 $R$的独立同分布采样数据   { r }   ~\{r\}~  {r} , $\gamma$ 为常数。
令 $g(w)=w-\mathbb{E}[R+\gamma v(X)]$, 将问题重新表述为 寻根问题 $g(w)=0$
可获取的 带误差的值 $\tilde{g}(w,\eta )=w-[r+\gamma v(x)]=(w-\mathbb{E}[R+\gamma v(X)])+(\mathbb{E}[R+\gamma v(X)]-[r+\gamma v(x)])\doteq g(w)+\eta$
RM 算法迭代求解公式： $w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k[w_k-(r_k+\gamma v(x_k))]$

——————
P2
TD 算法的目标：求解 给定策略 $\pi$ 的 状态值
求解了 状态值， 相当于做了 策略评估，用于后续的 策略改进。

基于 数据 / 经验。$\{(s_t,r_{t+1},s_{t+1})\}$

TD 学习算法
$\underset{新的估计值}{\underbrace{v_{t+1}(s_t)}}=\underset{当前估计值}{\underbrace{v_t(s_t)}}-\underset{学习率}{\underbrace{\alpha (s_t)}}\stackrel{\mathrm{TD}误差{\delta }_t}{\overbrace{[v_t(s_t)-\underset{\mathrm{TD}目标{\bar{v}}_t}{\underbrace{[r_{t+1}+\gamma v_t(s_{t+1})]}}]}}$
  ~  
$v_{t+1}(s)=v_t(s)，\forall s\ne s_t$ 未访问的状态 (非当前的 $s_t$) 的值 不更新

• $t=0,1,2,...$
• $v_t(s_t)$： $v_{\pi }(s_t)$ 的 状态值 估计。
• ${\alpha }_t(s_t)$：$s_t$ 在时间 $t$ 的学习率。

————

在时刻 $t$，只有访问过的状态 $s_t$ 的值被更新，而未访问过的状态 $s_t$ 的值保持不变。
新的估计 $v_{t+1}(s_t)$ 是当前估计 $v_t(s_t)$ 和 TD 误差的组合。

如何理解 TD 目标 ${\bar{v}}_t$

• 算法 驱使 $v(s_t)$ 向 ${\bar{v}}_t$ 移动

---

$v_{t+1}(s_t)=v_t(s_t)-{\alpha }_t(s_t)[v_t(s_t)-{\bar{v}}_t]$

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

$v_{t+1}(s_t)-{\bar{v}}_t=[1-{\alpha }_t(s_t)][v_t(s_t)-{\bar{v}}_t]$
$|v_{t+1}(s_t)-{\bar{v}}_t|=|1-{\alpha }_t(s_t)||v_t(s_t)-{\bar{v}}_t|$
因为 ${\alpha }_t(s_t)$ 是小的正数， 则 $0<1-{\alpha }_t(s_t)<1$
$|v_{t+1}(s_t)-{\bar{v}}_t|\le |v_t(s_t)-{\bar{v}}_t|$
两者越来越近。

如何理解 TD误差？${\delta }_t=v(s_t)-[r_{t+1}+\gamma v(s_{t+1})]$

• 从经验 $(s_t,r_{t+1},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$

如果 ${\delta }_t\ne 0$, 则 $v_t\ne v_{\pi }$。

时序差分： 两个不同时刻。

TD学习的基本思想是根据新获得的信息修正 当前对状态值的估计。

————————————————

当前 TD 算法：仅能 估计给定策略的 状态值。
后续 TD 算法：可估计动作值，然后搜索最优策略。

——————
P3
TD 算法的目标： 在没有模型的情况下，求解 给定策略的 贝尔曼公式。model-free

贝尔曼期望方程：
策略 $\pi$ 的状态值 $v_{\pi }(s)=\mathbb{E}[R+\gamma G|S=s],s\in \mathcal{S}$

• $G$ 是 折扣回报

由于 $\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 }$： 下一状态

$v_{\pi }(s)=\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|S=s],s\in \mathcal{S}$

如何求解上述 贝尔曼期望方程？

已知： $R$ 的样本 $r$， $S^{\prime }$ 的样本 $s^{\prime }$

带误差的观测值：
$\begin{array}{rl}\tilde{g}(v(s))& =v(s)-[r+\gamma v_{\pi }(s^{\prime })]\\ & =\underset{g(v(s))}{\underbrace{(v(s)-\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s])}}+\underset{\eta }{\underbrace{(\mathbb{E}[R+\gamma v_{\pi }(S^{\prime })|s]-[r+\gamma v_{\pi }(s^{\prime })])}}\end{array}$

求解 $g(v(s))=0$ 的 RM 算法：

$\begin{array}{rl}{v}_{k+1}(s)& =v_k(s)-{\alpha }_k\tilde{g}(v_k(s))\\ & =v(s)-{\alpha }_k(v_k(s)-[r_k+\gamma v_{\pi }(s_k^{\prime })]),k=1,2,3,...\end{array}$

上述解法需要满足两个前提：有些量未知！！！
1、已知 经验集 { s , r , s ′ } \{s, r, s^\prime\} {s,r,s′}， 对于 $k=1,2,3,...$。——> 利用 一个 episode 的序列样本：改成 $\{(s_t,r_{t+1},s_{t+1}\}$
2、已知 任意 $s^{\prime }$ 的状态值 $v_{\pi }(s^{\prime })$。 ——> 用估计值 $v_k(s_k^{\prime })$ 代替

TD 学习的收敛性：
当对所有的 $s\in \mathcal{S}$， 均满足 $\sum _t{\alpha }_t(s)=\infty$ 和 $\sum _t{\alpha }_t^2(s)<\infty$，则当 $t\to \infty$ 时，$v_t(s)$ 以 概率 1 收敛到 $v_{\pi }(s)$ 。

该定理表明，对于给定的策略，可以通过 TD 算法找到 状态值。

要求 每个状态 被访问足够多次。

• TD 学习 的 收敛性证明 7.1.3 P139 - P141

——————
TD 学习 和 MC 学习 都是 model-free

• Sarsa 类似于 TD 学习， 但能估计 动作值

TD/Sarsa 学习	MC 学习
在线Online：在收到奖励后立即更新 状态值/行动值。	离线Offline：一个 episode 修改一次。
除了 episodic tasks， 还可以处理 continuing tasks	具有终止状态的 episodic tasks
Bootstrapping：值的更新依赖于先前对该值的估计。因此，它需要初始猜测。	Non-bootstrapping：可直接估计状态/动作值，而不需要任何初始猜测。
低估计方差：随机变量更少。$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}+...$ 假设每个 episode 的长度为 $L$， 则共有 $|\mathcal{A}{|}^L$ 个 episodes，只通过 一个 episode 来估计这么多值， 方差必然会很大。
估计值是否有偏差和 初始猜测 和 迭代次数 有关	无偏估计

---

7.2 动作值 的 TD 算法： Sarsa

P4

Sarsa 算法 可以 直接估计 动作值。
如何 使用 Sarsa 来找到 最优策略。

• Sarsa 估计动作值 + 策略改进 步骤 ， 即可寻找最优策略。

————————————
目标： 估计给定策略 $\pi$ 的动作值。

一些经验： { ( s t , a t , r t + 1 , s t + 1 , a t + 1 ) } t \left\{(s_t,a_t,r_{t+1},s_{t+1}, a_{t+1})\right\}_t {(st​,at​,rt+1​,st+1​,at+1​)}t​
使用下面的 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})]]$
$q_{t+1}(s,a)=q_t(s,a),\forall (s,a)\ne (s_t,a_t)$

• $t=0,1,2,...$
• $q_t(s_t,a_t)$： $q_{\pi }(s_t,a_t)$ 的估计值。
• ${\alpha }_t(s_t,a_t)$： 取决于 $s_t,a_t$ 的学习率。

在时间 $t$，只有 $(s_t,a_t)$ 的 q 值 被更新。

Sarsa：state-action-reward-state-action 的缩写, $(s_t,a_t,r_{r+1},s_{t+1},a_{t+1})$

Sarsa 是 TD 算法的 动作值版本。
$v(s)\to q(s,a)$

Sarsa：求解 以下问题的随机近似算法。
$q_{\pi }(s,a)=\mathbb{E}[R+\gamma q_{\pi }(S^{\prime },A^{\prime })|s,a],\forall s,a$
这是 Bellman方程 的另一个用动作值表示的表达式。

• 电子书 证明 P143

Sarsa 学习 的收敛性：
当对所有的 $(s,a)$， 均满足 $\sum _t{\alpha }_t(s,a)=\infty$ 和 $\sum _t{\alpha }_t^2(s,a)<\infty$，则当 $t\to \infty$ 时，$q_t(s,a)$ 以 概率 1 收敛到 $q_{\pi }(s,a)$ 。

$\sum _t{\alpha }_t(s,a)=\infty$ 要求 每个 状态-动作对 必须被访问 无数次 或至少 足够多 次。

在 时间 $t$， 如果 $(s,a)=(s_t,a_t)$， 则 ${\alpha }_t(s,a)>0$； 否则 ${\alpha }_t(s,a)=0$

对于给定策略 $\pi$, 可以通过 Sarsa 算法 计算 动作值。

————————————

7.2.2 通过 Sarsa 学习最优策略

Sarsa + 策略改进 步骤

每次迭代有两个步骤。
第一步是更新被访问 状态-动作对的 q 值。
第二步是将策略更新为 $\epsilon$-greedy 策略。q 值更新步骤仅更新所访问的单个状态-动作对

在 $q(s_t,a_t)$ 更新之后，立即更新 $s_t$ 的策略。
平衡 利用exploitation 和 探索exploration： $ϵ$-greedy。 访问更多的 $(s,a)$

例子：寻找从特定起始状态 [左上角] 到 目标状态 的最优路径。

可行路径 or 最优路径

---

Sarsa 的两个变形： Expected Sarsa、 n-step Sarsa。

研究思路：从经典算法出发，推广-改进

Expected Sarsa

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})]]$
$q_{t+1}(s,a)=q_t(s,a),\forall (s,a)\ne (s_t,a_t)$
————————
Expected 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 \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)$

• $\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})$ 【策略 ${\pi }_t$ 的 $q_t(s_{t+1},a)$ 的期望值 】

计算量比 Sarsa 大， 但由于随机参数变少， 估计方差减小。

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

$\sim$$\sim$

n-step Sarsa

Sarsa 和 MC 学习 是 n-step Sarsa 的两个极端情况

$t+n$ 时刻 更新 $(s_t,a_t)$ 时刻的 q 值。

如果 n 较大，则其性能接近 MC 学习，因此方差较大，但偏差较小。
如果 n 较小，则其性能接近 Sarsa，因此由于初始猜测和相对较低的方差，其偏差较大。

---

7.4 最优动作值 的 TD 学习： Q-learning

P6
Q-learning 可以直接估计 最优动作值并获得最优策略。

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})]]$
$q_{t+1}(s,a)=q_t(s,a),\forall (s,a)\ne (s_t,a_t)$
————————
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{a\in \mathcal{A}(s_{t+1})}{\max }{q}_t(s_{t+1},a)]]$
$q_{t+1}(s,a)=q_t(s,a),\forall (s,a)\ne (s_t,a_t)$

• 需要对 $a$ 进行优化

给定 $(s_t,a_t)$，需要的经验数据：
Sarsa：$(r_{t+1},s_{t+1},a_{t+1})$
Q-learning： $(r_{t+1},s_{t+1})$

Q-learning 求解 用 动作值 表示的 Bellman 最优方程。
$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$

• 电子书 证明 上式为 贝尔曼最优公式

7.4.2 Off-policy vs on-policy

behavior policy： 和环境进行交互，然后生成 experience 样本。
target policy：不断朝 最优策略 更新。

on-policy:

• behavior policy 和 target policy 相同
• 用策略来和环境交互，得到 experience， 同时改进策略，然后用 改进的策略和环境交互。
• Sarsa, MC

off-policy:

• behavior policy 和 target policy 可以不同， 也可以相同。
• 用一个策略和环境交互得到大量的经验，用这些经验不断改进一个策略，直到策略收敛。
• Q-learning

——————
如何 判断 某个算法 是 on-policy 还是 off-policy？

• 算法的目标是解决什么数学问题？
• 算法需要哪些经验样本？

Sarsa:

• 求解给定策略的贝尔曼公式
• 需要
• 
  $a_{t+1}$ 和 策略有关。

MC： 估计 动作值

贝尔曼最优公式 不涉及 任何策略。

若 $(s_t,a_t)$ 给定， 从上述两个 转移概率公式可计算 $(s_{t+1},a_{t+1})$， 不涉及 策略。

P7
Q-learning 算法 如何 实现？

on-policy 版本： 让 目标策略 和 行为策略 相同

b： behavior

根据已有的数据 寻找最优策略

这里 不再是 $\epsilon -$greedy。

---

例子： 为 每个状态 找对应的最优策略

探索性 比较强

---

P8

之前的内容：Q-learning 算法是什么？解决什么样的数学问题？
Sarsa 和 蒙特卡洛方法 都是 on-policy
Q-learning 是 off-policy

为什么将神经网络 和 TD 算法 结合的时候选择 Q-learning ， 和 Q-learning 的 off-policy 性质有很大关系。

目标： 让 $q_t$ 不断接近 TD target

——————————
7.6

TD-learning：Sarsa、n-step Sarsa 和 Q-learning

on-policy： 目标策略被用作行为策略来生成经验样本。

Q-learning 是 off-policy 的根本原因是，Q-learning 旨在解决 Bellman 最优性方程，而不是给定策略的 Bellman 方程。

7.7
为什么 Sarsa 的更新策略设计为 $\epsilon$-greedy?
答：这是因为该策略也用于生成样本进行价值估计。产生足够的经验样本应该是探索性的。

为什么 Q-learning 的 off-policy 版本会将策略更新设为 greedy 而不是 $\epsilon$-greedy?
答：这是因为目标策略不需要生成经验样本。因此，它不需要是探索性的。

---

习题 笔记：

Sarsa 估计的是 动作值

Q-learning 每次使用经验数据包括 $(s_t,a_t,s_{t+1},r_{t+1})$。相比 Sarsa，Q-learning 不需要 $a_{t+1}$.

PDF 补充

7.1.3 TD 学习 的 收敛性

考虑 任意状态 $s\in \mathcal{S}$， 在 时间 $t$：

$v_{t+1}(s)=v_t(s)-{\alpha }_t(s)(v_t(s)-(r_{t+1}+\gamma v_t(s_{t+1}))),s=s_t$

$v_{t+1}(s)=v_t(s),s\ne s_t$

估计误差 ${\Delta }_t(s)=v_t(s)-v_{\pi }(s)$

$v_{\pi }(s)$： 策略 $\pi$ 下状态 $s$ 的状态值 。

当 $s=s_t$：

$v_{t+1}(s)-v_{\pi }(s)=v_t(s)-v_{\pi }(s)-{\alpha }_t(s)(v_t(s)-v_{\pi }(s)+v_{\pi }(s)-(r_{t+1}+\gamma v_t(s_{t+1}))),s=s_t$

$\begin{array}{rl}{\Delta }_{t+1}(s)& ={\Delta }_t(s)-{\alpha }_t(s)({\Delta }_t(s)+v_{\pi }(s)-(r_{t+1}+\gamma v_t(s_{t+1})))\\ & =(1-{\alpha }_t(s)){\Delta }_t(s)+{\alpha }_t(s)(\underset{{\eta }_t(s)}{\underbrace{r_{t+1}+\gamma v_t(s_{t+1})-v_{\pi }(s)}})\\ & =(1-{\alpha }_t(s)){\Delta }_t(s)+{\alpha }_t(s){\eta }_t(s)\end{array}$

当 $s\ne s_t$：

$v_{t+1}(s)-v_{\pi }(s)=v_t(s)-v_{\pi }(s)$

${\Delta }_{t+1}(s)={\Delta }_t(s)$

证明

${\Delta }_{t+1}(s)=(1-{\alpha }_t(s)){\Delta }_t(s)+{\alpha }_t(s){\eta }_t(s)$

满足 定理 6.3 的 3 个条件。

条件 2：
对 所有的 $s\in \mathcal{S}$，有 $||\mathbb{E}[{\eta }_t(s)|{\mathcal{H}}_t]|{|}_{\infty }\le \gamma ||{\Delta }_t(s)|{|}_{\infty }$

${\mathcal{H}}_t$ 表示历史信息。

由马尔可夫性质， 一旦 $s$ 给定， ${\eta }_t(s)=r_{t+1}+\gamma v_t(s_{t+1}-v_{\pi }(s))$ 或 ${\eta }_t(s)=0$， 和 历史信息无关。

对于 $s\ne s_t$： ${\eta }_t(s)=0$
$|\mathbb{E}[{\eta }_t(s)]|=0\le \gamma ||{\Delta }_t(s)|{|}_{\infty }$

对于 $s=s_t$：
$\begin{array}{rl}\mathbb{E}[{\eta }_t(s)]& =\mathbb{E}[{\eta }_t(s_t)]\\ & =\mathbb{E}[r_{t+1}+\gamma v_t(s_{t+1})-v_{\pi }(s_t)|s_t]\\ & =\mathbb{E}[r_{t+1}+\gamma v_t(s_{t+1})|s_t]-v_{\pi }(s_t)\end{array}$

由于 $v_{\pi }(s_t)=\mathbb{E}[r_{t+1}+\gamma v_{\pi }(s_{t+1})|s_t]$

$\begin{array}{rl}\mathbb{E}[{\eta }_t(s)]& =\mathbb{E}[r_{t+1}+\gamma v_t(s_{t+1})|s_t]-v_{\pi }(s_t)\\ & =\mathbb{E}[r_{t+1}+\gamma v_t(s_{t+1})|s_t]-\mathbb{E}[r_{t+1}+\gamma v_{\pi }(s_{t+1})|s_t]\\ & =\gamma \mathbb{E}[v_t(s_{t+1})-v_{\pi }(s_{t+1})|s_t]\\ & =\gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s_t)[v_t(s^{\prime })-v_{\pi }(s^{\prime })]\end{array}$

$\begin{array}{rl}|\mathbb{E}[{\eta }_t(s)]|& =\gamma |\sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s_t)[v_t(s^{\prime })-v_{\pi }(s^{\prime })]|\\ & \le \gamma \sum _{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s_t)\underset{s^{\prime }\in \mathcal{S}}{\max }|v_t(s^{\prime })-v_{\pi }(s^{\prime })|\\ & =\gamma \underset{s^{\prime }\in \mathcal{S}}{\max }|v_t(s^{\prime })-v_{\pi }(s^{\prime })|\\ & =\gamma ||v_t(s^{\prime })-v_{\pi }(s^{\prime })|{|}_{\infty }\\ & =\gamma ||{\Delta }_t(s)|{|}_{\infty }\end{array}$

条件 3：

对于 $s=s_t$：
$\mathrm{var}[{\eta }_t(s)|{\mathcal{H}}_t]=\mathrm{var}[r_{t+1}+\gamma v_t(s_{t+1})-v_{\pi }(s_t)|s_t]=\mathrm{var}[r_{t+1}+\gamma v_t(s_{t+1})|s_t]$

对于 $s\ne s_t$：
$\mathrm{var}[{\eta }_t(s)|{\mathcal{H}}_t]=0$

由于 $r_{t+1}$ 有界。

???

证明： 7.13 是贝尔曼公式 P142

动作值 的 贝尔曼公式 为：

$\begin{array}{rl}{q}_{\pi }(s,a)& =\sum _{r}rp(s|s,a)+\gamma \sum _{s^{\prime }}\sum _{a^{\prime }}{q}_{\pi }(s^{\prime },a^{\prime })p(s^{\prime }|s,a)\pi (a^{\prime }|s^{\prime })\\ & =\sum _{r}rp(s|s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\sum _{a^{\prime }}{q}_{\pi }(s^{\prime },a^{\prime })\pi (a^{\prime }|s^{\prime })\end{array}$

这个方程建立了 动作值 之间的关系

$\begin{array}{rl}p(s^{\prime },a^{\prime }|s,a)& =p(s^{\prime }|s,a)p(a^{\prime }|s^{\prime },s,a)\\ & =p(s^{\prime }|s,a)p(a^{\prime }|s^{\prime })\\ & =p(s^{\prime }|s,a)\pi (a^{\prime }|s^{\prime })\end{array}$

$q_{\pi }(s,a)=\sum _{r}rp(s|s,a)+\gamma \sum _{s^{\prime }}\sum _{a^{\prime }}{q}_{\pi }(s^{\prime },a^{\prime })p(s^{\prime },a^{\prime }|s,a)$

证明： 7.19 为贝尔曼最优公式 P149

根据 期望值 定义， (7.19) 可改写为：

$q(s,a)=\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\underset{a\in \mathcal{A}(s^{\prime })}{\max }q(s^{\prime },a)$

$\underset{a\in \mathcal{A}(s)}{\max }q(s,a)=\underset{a\in \mathcal{A}(s)}{\max }[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\underset{a\in \mathcal{A}(s^{\prime })}{\max }q(s^{\prime },a)]$

记 $v(s)=\underset{a\in \mathcal{A}(s)}{\max }q(s,a)$

$\begin{array}{rl}v(s)& =\underset{a\in \mathcal{A}(s)}{\max }[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v(s^{\prime })]\\ & =\underset{\pi }{\max }\sum _{a\in \mathcal{A}(s)}\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v(s^{\prime })]\end{array}$

正是 第 3 章的 贝尔曼最优公式