Chap3 finite mdp

第3章：有限马尔可夫决策过程

这一章主要读一下鱼书的对应章节

一、引入

---

在老虎机问题中，无论智能代理采取什么行动，之后要解决的问题都是一样的——寻找最好的老虎机拉动摇杆。

但MDP问题不同。例如，在围棋游戏中，落子后棋盘上的棋子排列会发生变化。智能代理采取的不同行动导致棋局每时每刻都在变化。智能代理需要考虑到棋局的转变，下出最佳的一手。

第2章中我们曾经讨论过“非稳态问题”，即老虎机的奖励设置（奖励的概率分布）会随时间发生变化。这不是一个MDP问题，因为奖励概率是随时间变化的（引起变化的是时间），与智能代理的行动无关。而MDPs探讨的则是环境状态随着Agent的行动而变化的问题。

三、分幕式/持续性任务

---

四、分幕式和持续性的统一表示

---

五、价值函数

---

1）三个函数的区别

（去掉*就是去掉“最优策略”的“最优”二字）

2）$v_π$的贝尔曼方程

---

前置定义：

                                        $G_t=R_{t+1}$$+R_{t+2}+…+R_{T}$

\[\begin{aligned} v_{\pi}(s) = \mathbb{E}_{\pi}\left[ R_{t} + \gamma R_{t+1} + \gamma^{2} R_{t+2} + \cdots \mid S_{t} = s \right] \end{aligned}\]

贝尔曼方程的推导：

\[\begin{aligned} v_{\pi}(s) &\doteq \mathbb{E}{\pi}[G_t \mid S_t = s] \\ &= \mathbb{E}{\pi}[R_{t+1} + \gamma G_{t+1} \mid S_t = s] \\ &= \sum_{a} \pi(a|s) \sum_{s'} \sum_{r} p(s', r \mid s, a) \Big[ r + \gamma \mathbb{E}{\pi}[G{t+1} \mid S_{t+1} = s'] \Big] \\ &= \sum_{a} \pi(a|s) \sum_{s', r} p(s', r \mid s, a) \Big[ r + \gamma v_{\pi}(s') \Big], \quad \text{对于所有 } s \in \mathcal{S}. \end{aligned}\]

a. 解释

---

• 第二项中的 s′ 和 r 与最后一项中的 s′ 和 r 是完全相同的变量。

• $\pi(a

  s)$和$p(s’, r \mid s, a)$充当了期望计算中，每一项的权重。

b. 怎么由初始形式展开的？

---

---

3.5-3.6的例题要好好写！

七、最优性和近似

---

我们定义了最优值函数和最优策略。按照前面的方法只需要求解贝尔曼方程就能得到一个最优策略，但实际上这种情况很少发生。主要受限于两方面约束：

• 计算能力约束

正如上一节讲到的西洋棋的例子，即使我们知道了环境模型，依然需要可能上千年的时间才能求解出贝尔曼方程组。这是不可接受的。

• 内存约束

为了表征值函数、策略和模型，我们往往需要大量的内存。对于状态空间不大、有限的任务，我们确实可以通过表格或者数组来记录所有值函数的值或者模型。我们叫做表格式任务(tabular case)，相应的方法叫做表格式方法（tabular methods）。但实际中，可能状态空间太大以至于根本无法用基于表格存储的方式来解决。这些情况下，必须用近似的方法，使用一些更加紧凑搞笑的值函数表征方法。

但强化学习问题的一些独特特性，也使得我们能够实现有线的近似。例如有些状态对于智能体来说很少出现，或者对于回报的贡献值很低，这样我们就可以忽略这些状态。专注于频繁出现的状态的决策。