强化学习导论 | 第三章 有限马尔科夫决策过程

本章将讲解有限马尔科夫决策过程中的有关反馈、策略和价值函数的内容。这个问题也是评估性反馈（evaluative feedback），但和上一章中讲到的多臂**机不同，多臂**机仅包含一个状态。在包含多个状态的情况下，我们需要考虑在不同状态下选择不同的动作。

3.1 agent和环境的交互

agent是决策者，在每个时间步$t$t与环境进行交互（$t = 0,1,2,3...$t=0,1,2,3...）。交互过程如下：

• 环境发送给agent一个状态表示$S_t \in \mathcal{S}$St​∈S
• 在给定状态的基础上，选择一个动作$A_t \in \mathcal{A}_t(s)$At​∈At​(s)
• 一个时间步之后，环境给agent反馈一个reward值$R_{t+1} \in \mathcal{R} \subset R$Rt+1​∈R⊂R 和agent下一步所处的状态$S_{t+1}$St+1​。
  
  这样的一系列步骤完成后，我们会得到一个轨迹（trajectory）：
  $S_0, A_0, R_1, S_1, A_1, R_2, S_2, A_2, R_3, \cdots$S0​,A0​,R1​,S1​,A1​,R2​,S2​,A2​,R3​,⋯

在有限MDP问题中，状态空间、动作空间的大小，还有奖励值的个数都是有限的。

3.2 马尔科夫性质

定义MDP的动态分布为：
$p(s', r | s, a) \doteq \Pr\{S_t=s',R_t = r | S_{t-1} = s, A_{t-1} = a\}$p(s′,r∣s,a)≐Pr{St​=s′,Rt​=r∣St−1​=s,At−1​=a}

$\doteq$≐表示的是一种定义，而不是等于。

我们看到，这里下一个状态$s'$s′和奖励$r$r都只和当前的状态和动作有关，所以这样的状态具有马尔科夫性质。

那么，对于状态$s$s，采取了动作$a$a，agent可能收到的下一个状态$s'$s′以及奖励值$r$r的所有可能的概率和为1。即对于所有的状态$s \in \mathcal{S}$s∈S和动作$a \in \mathcal{A(s)}$a∈A(s)：
$\sum_{s' \in \mathcal{S}}\sum_{r \in \mathcal{R}} p(s', r | s, a) = 1$s′∈S∑​r∈R∑​p(s′,r∣s,a)=1

根据上面的定义，可以计算出一些常用的其他值，比如：状态转移概率，状态-动作对的期望奖励，状态-动作-下个状态元组的期望奖励：

• 状态转移概率
  $p(s' | s, a) \doteq \Pr\{S_{t+1} = s' | S_t = s, A_t = a\} = \sum_{r \in \mathcal{R}} p(s', r | s, a)$p(s′∣s,a)≐Pr{St+1​=s′∣St​=s,At​=a}=r∈R∑​p(s′,r∣s,a)
• 状态-动作对的期望奖励
  $r(s, a) \doteq \mathbb{E}[R_{t+1} | S_t = s, A_t = a] = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p(s', r | s, a)$r(s,a)≐E[Rt+1​∣St​=s,At​=a]=r∈R∑​rs′∈S∑​p(s′,r∣s,a)
• 状态-动作-下个状态元组的期望奖励
  $r(s, a, s') = \mathbb{E}[R_{t+1} | S_t = s, A_t = a, S_{t+1} = s'] = \sum_{r \in \mathcal{R}}r \frac{p(s', r | s, a)}{p(s' | s, a)}$r(s,a,s′)=E[Rt+1​∣St​=s,At​=a,St+1​=s′]=r∈R∑​rp(s′∣s,a)p(s′,r∣s,a)​

3.3 强化学习目标

agent始终为了得到更高的回报（reward）而不断改进。所以，agent的目标就是最大化长期累积的回报。

That all of what we mean by goals and purposes can be well thought of as the maximization of the expected value of the cumulative sum of a received scalar signal (called reward).

我们则要设计好的reward机制，使得agent能不断达到我们的目的。比如：

• 我们想要机器人学会走路，那么机器人得到的奖励应该与它所走的路程成正比的。
• 我们想要让机器人快速的走出迷宫，那么我们可以设置在机器人走出迷宫之前的每一步都得到-1的奖励，走出迷宫得到较高的奖励。

知道了agent的目标，那么该怎样计算累积奖励呢？
这里有两种不同的方式：

• 非折扣累积奖励（undiscounted）
• 折扣累积奖励（discounted）

非折扣累积奖励
$G_t \doteq R_{t+1} + R_{t+2} + R_{t+3} + \cdots + R_{T}$Gt​≐Rt+1​+Rt+2​+Rt+3​+⋯+RT​

即累加从当前时刻到最终时刻的所有奖励值。

但不是所有任务都有一个明确的终止时间$T$T，有些任务时连续的，所以需要定义一种统一的表示，不管对于episodic任务还是对于连续任务，都可以统一计算累计奖励。下图表现了统一表示的思想，即对于episodic任务，在其终止时间$T$T之后，加上一个吸收态的状态，后续的所有奖励全都为0，这样就相当于一个连续的任务了。

那么对于连续任务，它的终止时刻定义为$\infty$∞，其累积奖励计算如下：
折扣累积奖励
$G_t \doteq R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$Gt​≐Rt+1​+γRt+2​+γ2Rt+3​+⋯=k=0∑∞​γkRt+k+1​

即对未来的奖励进行一定的折扣，如果$\gamma$γ接近于1，则累积奖励更注重当前得到的即时奖励。如果$\gamma$γ接近于0，则累积奖励更注重未来的奖励。

所以，对于episodic任务，也可以写成这样的形式，即：
$G_t \doteq \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$Gt​≐k=t+1∑T​γk−t−1Rk​

3.4 策略和值函数

策略是从状态空间$\mathcal{S}$S、动作空间$\mathcal{A}$A到概率空间$\mathcal{P}$P的映射。$\pi : \mathcal{S} \times \mathcal{A} \rightarrow \mathcal{P}$π:S×A→P

在状态$s$s，采取动作$a$a的概率分布表示为：$\pi(a|s)$π(a∣s)。

值函数用来评估当前状态好不好，或者在当前状态做出某个动作好不好。几乎所有的强化学习算法都涉及到估计值函数。

状态$s$s在策略$\pi$π下的值函数表示为$v_{\pi}(s)$vπ​(s)，称为状态值函数（state-value function），计算方法为：
$v_{\pi}(s) \doteq \mathbb{E}_{\pi}[G_t | S_t = s] = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s]$vπ​(s)≐Eπ​[Gt​∣St​=s]=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s]

在策略$\pi$π下，状态$s$s采取动作$a$a的值函数表示为$q_{\pi}(s, a)$qπ​(s,a)，称为动作值函数（action-value function），计算方法为：
$q_{\pi}(s, a) \doteq \mathbb{E}[G_t | S_t = s, A_t = a] = \mathbb{E}_{\pi}[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} | S_t = s, A_t = a]$qπ​(s,a)≐E[Gt​∣St​=s,At​=a]=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s,At​=a]

3.5 贝尔曼方程（Bellman equation）

上面我们得到的状态值函数$v_{\pi}(s)$vπ​(s)可以分成以下两个部分：

• 即使奖励$R_{t+1}$Rt+1​
• 后继状态的折扣价值函数$\gamma v_{\pi}(S_{t+1})$γvπ​(St+1​)
  

上式称为$v_{\pi}$vπ​的贝尔曼方程。下图称为$v_{\pi}$vπ​的backup diagram。空心圆表示状态，实心圆表示所做的动作。状态$s$s的价值函数就等于即时奖励加上后续状态的价值函数。这是一个迭代的过程。

当然，动作值函数$q_{\pi}(s, a)$qπ​(s,a)也可以写成这样迭代的形式。

3.6 最优策略和最优价值函数

agent在与环境交互的过程中，总是希望能找到一个更好的策略，根据该策略选择动作能得到更高的累计奖励值。

对于有限MDPs，一个策略$\pi$π优于另一个策略$\pi'$π′，当且仅当对于所有的$s \in \mathcal{S}，$s∈S，$v_{\pi}(s) \geq v_{\pi'}(s)$vπ​(s)≥vπ′​(s)。

可能存在不止一个最优策略，将所有最优策略都定义为$\pi_*$π∗​。它们拥有同样的状态价值函数，称为最优状态价值函数。表示为$v_*$v∗​，定义如下：
$v_*(s) \doteq \max_{\pi}v_{\pi}(s)$v∗​(s)≐πmax​vπ​(s)

最优的策略也拥有同样的最优动作价值函数，表示为$q_*$q∗​，定义为：
$q_*(s, a) \doteq \max_{\pi} q_{\pi}(s, a)$q∗​(s,a)≐πmax​qπ​(s,a)

$v_*(s)$v∗​(s)的值一定是等于在当前状态$s$s下选择最优的动作$a$a所得到的期望奖励。其贝尔曼最优方程（Bellman optimality equatsion）表示为：

$q_*(s, a)$q∗​(s,a)的贝尔曼最优方程表示为：

图示如下：
当我们已经有了$v_*$v∗​，就能很容易的确定最优策略。对于任意一个状态$s$s，总会有一个或多个动作执行后能达到$v_*(s)$v∗​(s)的值。如果一个策略仅仅将选择这些动作的概率置为非0值，那么这个策略就是最优策略。

这看似是贪心的方法，仅考虑当前状态下能取得最优价值的动作，但是$v_*$v∗​已经将后续的价值都考虑了进去，所以这其实是全局的最优。

当我们已经有了$q_*$q∗​，对于任意状态$s$s，只需要找到一个动作$a'$a′，使得$q_* (s, a') = \max_{a} q_*(s,a)$q∗​(s,a′)=maxa​q∗​(s,a)。

但是通过贝尔曼公式来确定最优策略并不实用，因为这个方法依赖于三个假设：

• 精确的知道$p(s', r| s, a)$p(s′,r∣s,a)
• 有足够的计算资源
• 满足马尔科夫性质

这三个假设使得问题变得比较困难，书中后面的部分介绍了怎么样去近似求解值函数。