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

• 1、学堂在线 视频 + 习题
• 2、相应章节 过电子书 复习 GitHub界面链接
• 3、总体 MOOC 过一遍

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

PPT和书籍下载网址： 【github链接】
onedrive链接：
【书】
【课程PPT】

---

——————

回报 return: 沿着 轨迹 获得的 奖励 折扣和。
可用于 评估策略

计算 return 的值，来评估以下 3 个策略
3 种策略的区别在于第一格。 策略 1 是往下走，策略 2 是 往右走，策略 3 往下 和 往右的概率 分别为 50%。其它格相同。

计算 return

方法一： 根据定义

$\mathrm{retur}{\mathrm{n}}_3$ 实际是 状态值。

方法二： 根据状态间回报的依赖关系

$v_i$： 从 $s_i$ 出发获得的回报

例：

推导：
$v_1=r_1+\gamma r_2+{\gamma }^2{r}_3+...=r_1+\gamma (r_2+\gamma r_3+...)=r_1+\gamma v_2$
$v_2=r_2+\gamma r_3+{\gamma }^2{r}_4+...=r_2+\gamma (r_3+\gamma r_4+...)=r_2+\gamma v_3$
$v_3=r_3+\gamma r_4+{\gamma }^2{r}_1+...=r_3+\gamma (r_4+\gamma r_1+...)=r_3+\gamma v_4$
$v_4=r_4+\gamma r_1+{\gamma }^2{r}_2+...=r_4+\gamma (r_1+\gamma r_2+...)=r_4+\gamma v_1$

写成矩阵形式
$$\begin{array}{rl}\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]& =\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\gamma \left[\begin{array}{c}{v}_2\\ v_3\\ v_4\\ v_1\end{array}\right]\\ & =\left[\begin{array}{c}{r}_1\\ r_2\\ r_3\\ r_4\end{array}\right]+\gamma \left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right]\left[\begin{array}{c}{v}_1\\ v_2\\ v_3\\ v_4\end{array}\right]\\ \mathbf{v}& =\mathbf{r}+\gamma \mathbf{Pv}\end{array}$$

Bellman 方程的核心思想：从一种状态出发所获得的收益依赖于从其他状态出发所获得的收益。

从不同状态出发得到的 return ， 依赖于 从其它状态 出发得到的 return。

Bootstrapping: 从自己出发不断迭代

---

State value 状态值 $v_{\pi }(s)$

P2 状态值

$G_t$ 的期望【期望值/均值】
状态值函数 / 状态值: $v_{\pi }(s)=\mathbb{E}[G_t|S_t=s]$

状态值 $v_{\pi }(s)$ 取决于 状态 $s$ 和 策略 $\pi$, 和 时间 $t$ 无关。

多步 trajectory：
$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}\stackrel{A_{t+1}}{\to }{R}_{t+2},S_{t+2}\stackrel{A_{t+2}}{\to }{R}_{t+3},...$$
折扣回报：
$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...$$

• $\gamma \in [0,1)$ 为折扣率

return VS state value
return: 针对 单个 trajectory
state value: 多个 trajectory 的 return 的平均值

• 从 某个状态 出发，有可能得到多个 trajectory，此时得到的值可能不一样。
• 当 从 某个状态出发，仅存在一条 trajectory，此时两者相同

---

贝尔曼公式 推导

P3 贝尔曼公式 推导

贝尔曼公式 描述了 不同状态 的 state value 之间的关系。

对于某个 trajectory：
$$S_t\stackrel{A_t}{\to }{R}_{t+1},S_{t+1}\stackrel{A_{t+1}}{\to }{R}_{t+2},S_{t+2}\stackrel{A_{t+2}}{\to }{R}_{t+3},...$$
折扣回报：
$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...\\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...)\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$
状态值
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[G_t|S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\end{array}$$
其中
即时奖励 均值
$$\begin{array}{rl}\mathbb{E}[R_{t+1}|S_t=s]& =\sum _a\pi (a|s)\mathbb{E}[R_{t+1}|S_t=s,A_t=a]\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r\end{array}$$
未来奖励 【延迟奖励】均值
$$\begin{array}{rl}\mathbb{E}[G_{t+1}|S_t=s]& =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_t=s,S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & =\sum _{s^{\prime }}\mathbb{E}[G_{t+1}|S_{t+1}=s^{\prime }]p(s^{\prime }|s)\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })p(s^{\prime }|s)\\ & =\sum _{s^{\prime }}{v}_{\pi }(s^{\prime })\sum _{a}p(s^{\prime }|s,a)\pi (a|s)\end{array}$$

表征状态值 之间关系 的 贝尔曼公式：

——————————————
PDF 补充：

贝尔曼公式：

$v_{\pi }(s)=\sum _a\pi (a|s)[\sum _{r}p(r|s,a)r+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })]$

贝尔曼公式 的 另两种等效写法：

等效 写法一：
$p(s^{\prime }|s,a)=\sum _{r}p(s^{\prime },r|s,a)$ 后续是否 进入 某个状态 取决于 回报

$p(r|s,a)=\sum _{s^{\prime }}p(s^{\prime },r|s,a)$ 获得 某个回报 的概率 取决于 后续状态

$v_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })])$

等效 写法二 : 某些问题的 回报 $r$ 仅取决于 下一状态 $s^{\prime }$
$v_{\pi }(s)=\sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)[r(s^{\prime })+\gamma v_{\pi }(s^{\prime })]$

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

2.5 示例：确定 相应的贝尔曼方程

如何写出 Bellman 方程并逐步计算状态值

如何写出 Bellman 方程并逐步计算状态值。

示例 2：

上一个 示例采取的策略 计算得到的 $v_{\pi }(s_1)$ 比当前 这个示例 大， 因为 上一个 示例直接往下走， 当前这个示例 有 50% 的 概率 会 往 右走，进入 禁区。

---

P4 贝尔曼公式的 矩阵 和 向量 形式

状态值
$$\begin{array}{rl}{v}_{\pi }(s)& =\mathbb{E}[R_{t+1}|S_t=s]+\gamma \mathbb{E}[G_{t+1}|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{r}p(r|s,a)r+\gamma \sum _a\pi (a|s)\sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\\ & =r_{\pi }(s)+\gamma \sum _{s^{\prime }}{p}_{\pi }(s^{\prime }|s)v_{\pi }(s^{\prime })\end{array}$$

$$v_{\pi }(s_i)=r_{\pi }(s_i)+\gamma \sum _{s_j}{p}_{\pi }(s_j|s_i)v_{\pi }(s_j)$$
$${\mathbf{v}}_{\pi }={\mathbf{r}}_{\pi }+\gamma {\mathbf{P}}_{\pi }{\mathbf{v}}_{\pi }$$

状态转移矩阵：

求解 贝尔曼方程

求解 贝尔曼方程 是进行策略评估的 重要步骤。

证明： $v_k$ 最终 收敛到 $v_{\pi }$
归纳法
定义 误差 ${\Delta }_k=v_k-v_{\pi }$， 只需证明 ${\Delta }_k\to 0$
将用到的等式
1、贝尔曼公式 $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$
2、$v_{k+1}={\Delta }_{k+1}+v_{\pi }$
3、$v_k={\Delta }_k+v_{\pi }$
————————
$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$
——> ${\Delta }_{k+1}+v_{\pi }=r_{\pi }+\gamma P_{\pi }({\Delta }_k+v_{\pi })$
——> ${\Delta }_{k+1}=-v_{\pi }+r_{\pi }+\gamma P_{\pi }{\Delta }_k+\gamma P_{\pi }{v}_{\pi }=\gamma P_{\pi }{\Delta }_k$
迭代递推
${\Delta }_{k+1}=\gamma P_{\pi }{\Delta }_k={\gamma }^2{P}_{\pi }^2{\Delta }_{k-1}={\gamma }^3{P}_{\pi }^3{\Delta }_{k-2}=...={\gamma }^{k+1}{P}_{\pi }^{k+1}{\Delta }_0$

---

Action value 动作值 $q_{\pi }(s,a)$

P5 Action value： 选哪个 action

State value VS Action value
State value：从 某个状态 出发 获得 的平均回报。$v_{\pi }(s)$
Action value: 从某个状态出发，进行动作后的平均回报。$q_{\pi }(s,a)$

动作值 = 即时奖励的均值 + 未来奖励的均值。

先计算 state values, 再计算 action values 。
在没有模型的情况下，通过数据直接计算 action values。

状态值 和 回报的关系： 状态值是 agent 从该状态出发所能获得的收益的平均值。

状态值 和 动作值的关系： 一方面，状态值是 该状态的 动作值的平均值。另一方面，动作值 依赖于 agent 在采取动作后可能过渡到的下一个状态的状态值。
$v_{\pi }(s)=\sum _a\pi (a|s)q_{\pi }(s,a)$

用 动作值 的贝尔曼方程

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

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

习题笔记：

• State value：折扣回报的期望值。
• 状态值 $v_{\pi }(s)$ 和 策略、状态有关。不是 动作。
• 贝尔曼方程 描述了所有状态值之间的关系。
• 每一个状态都对应一个贝尔曼方程。
• 动作值（action value）$q_{\pi }(s,a)$ 和动作、状态和策略有关。