[强化学习的数学原理—赵世钰老师]学习笔记01-基本概念

本文章为西湖大学赵世钰老师《强化学习数学原理》中文版第1章 基本概念的学习笔记，在书中内容的基础上增加了自己的一些理解内容和相关补充内容。

1.1 网格世界的例子

  根据赵老师书里所述，首先给出如图所示的网格世界（grid world） 的例子，来直观的对一些概念和算法进行解释。网格世界包括如下几个元素：
  智能体（agent）：可以在网格世界中移动，但每个时刻只能停留或占据一个单元格。
  允许进入区域：网格世界中的白色区域都是智能体可以自由出入的区域。
  禁止进入区域：网格世界中的黄色区域都是智能体禁止进入的区域。
  目标区域：网格世界中的蓝色区域，智能体最终需要抵达的区域。
在网格世界中，智能体需要完成的任务是从一个任意的初始区域出发，最终到达目标区域。

注：根据网格世界中智能体需要完成的任务可知，智能体需要规划一条能到达目标区域的路径。这时候存在两种情况：
1）智能体已知网格世界的地图，可以轻松的规划处一条合适的目标路径；
2）智能体事先不知道自己所处网格世界环境的相关信息，规划任务变得有难度，智能体只有不断与环境交互学习，获取经验才能找到合适的目标路径。描述这个学习的过程需要引入一些基本概念，这就是后续需要介绍的内容。

1.2 状态和动作

  本小节介绍的两个概念为状态（state） 和动作（action），其定义如下：
  状态（state）：所描述的智能体与环境的相对状况。
  动作（action）：智能体在环境中可以执行的动作。

  通过基本定义，给出智能体在网格世界中的状态和动作定义。以网格世界为例，图1.2的左图中状态对应的是智能体所在单元格的位置。9个单元格对应了9个状态（$s_1,s_2,\dots ,s_9$），这9个状态构成的集合被称为状态空间（state space）表示为 S = { s 1 , s 2 , … , s 9 } \mathcal{S}=\{s_1,s_2,\dots ,s_9\} S={s1​,s2​,…,s9​}。
  在图1.2的右图中，动作对应的是智能体可以在单元格运动的方向。可选动作为：向上移动（$a_1$），向右移动（$a_2$），向下移动（$a_3$），向左移动（$a_4$），原地不动（$a_5$），这5个状态构成的集合被称为动作空间（state space） 表示为 A = { a 1 , a 2 , … , a 5 } \mathcal{A}=\{a_1,a_2,\dots ,a_5\} A={a1​,a2​,…,a5​}。

注：不同状态可以对应不同的动作空间，这是因为我们可以考虑理论上存在的所有动作，也可以剔除那些实际上不合理的动作。例如，向上移动或者向左移动对于状态$s_1$来说是不合理的，可以从动作空间里删除。但是为了更一般化的表示，赵老师的书里考虑了所有的可能动作，并不会避开不合理的动作，目的是为了让智能体通过算法学习来区分动作的好与坏。这里状态对应的一般化的动作空间可以表示为 A ( s ) = A = { a 1 , a 2 , … , a 5 } ,    ∀ s ∈ S \mathcal{A}\left( s \right) =A=\{a_1,a_2,\dots ,a_5\},\;\forall s\in \mathcal{S} A(s)=A={a1​,a2​,…,a5​},∀s∈S。

1.3 状态转移

  本节介绍的概念为状态转移（state transition），定义如下：
  状态转移（state transition）：智能体从一个状态转移到另一个状态的过程。
  以网格世界为例，若智能体当前时刻处在状态$s_1$，即将要执行动作$a_2$，也就是向右移动，那么下个时刻智能体将移动到状态$s_2$，这个过程表示为$s_1\stackrel{a_2}{\to }{s}_2$。
  特殊且重要情况分析:

• 智能体试图超越网格世界边界的情况
  如果智能体试图超越网格世界的边界，那么下一时刻智能体的状态是存在多种情况的。首先它不可能跳出状态空间，只会被弹回到属于状态空间中的某一种状态。通常设置为弹回到原本的状态。但在网格世界也可以任意设置弹回的状态，在物理世界则需要遵循物理规律来设置弹回的状态。
• 智能体试图进入网格世界禁止区域的情况：
  如果智能体试图进入网格世界禁止区域，那么会存在两种情况。
  情况1，网格世界的禁止区域是 “不可进入” 的，智能体会被弹回到原本的状态。
  情况2，网格世界的禁止区域是 “可以进入” 的，但智能体进入后会受到惩罚。

  基于图1.2网格世界的状态和动作产生的状态转移情况可以通过表格来表示，如表1.1所示。通过表格中的行表头（状态$s$）和列表头（动作$a$），我们就能确定智能体会转移到的下一个状态。

  状态转移过程在数学上可以用概率来描述，以状态$s_2$和动作$a_3$为例：
$$p\left(s_1|s_2,a_3\right)=0,p\left(s_2|s_2,a_3\right)=0,p\left(s_3|s_2,a_3\right)=0,p\left(s_4|s_2,a_3\right)=0,p\left(s_5|s_2,a_3\right)=1\text{\hspace{1em}(1)}$$可以看出，状态$s_2$执行动作$a_3$，在下一个时刻智能体一定会转移到$s_5$，因为转移到$s_5$的概率为$1$，转移到其他状态的概率为$0$。

注：表格表示法描述的是确定性的状态转移过程，而状态转移一般具有随机性，且可以通过条件概率来描述。网格世界中存在的干扰和实际物理世界的复杂情况都会导致状态转移的随机性，比如状态$s_2$执行动作$a_3$后，由于干扰的存在可能会导致下一时刻状态转移到$s_4$而不是$s_5$。这种情况可以用条件概率表示为：$p\left(s_4|s_2,a_3\right)=0.5,p\left(s_5|s_2,a_3\right)=0.5$。

1.4 策略

  策略（policy） 的作用是告诉智能体在每一个状态应该执行什么动作。由图1.3可知，策略直观上可以通过箭头来描述。

  智能体执行某一种策略后会按照策略给定的每个状态对应执行的动作生成从初始状态到目标状态的一条轨迹，从不同初始状态出发执行对应的策略会生成不同的轨迹，其示例如图1.4所示。

  策略一般分为确定性策略和随机性策略两种，在数学上均可以通过条件概率来描述，通常用$\pi (a|s)$ 表示在状态$s$执行动作$a$的概率。$\pi (a|s)$对每一个状态和每一个动作都有定义。下面给出一些确定策略和随机策略的网格世界示例及条件概率表示。
   确定性策略： 智能体的每个状态有固定的动作执行策略，下面给出智能体在状态$s_1-s_4$时对应的策略
$$\begin{array}{rl}\pi (a_1|s_1)& =0,\pi (a_2|s_1)=1,\pi (a_3|s_1)=0,\pi (a_4|s_1)=0,\pi (a_5|s_1)=0\\ \pi (a_1|s_2)& =0,\pi (a_2|s_2)=0,\pi (a_3|s_2)=1,\pi (a_4|s_2)=0,\pi (a_5|s_2)=0\\ \pi (a_1|s_3)& =0,\pi (a_2|s_3)=0,\pi (a_3|s_3)=0,\pi (a_4|s_3)=1,\pi (a_5|s_3)=0\\ \pi (a_1|s_4)& =0,\pi (a_2|s_4)=1,\pi (a_3|s_4)=0,\pi (a_4|s_4)=0,\pi (a_5|s_4)=0\end{array}\text{\hspace{1em}(2)}$$  随机性策略： 每个状态的动作策略是随机的，如图1.5所示，智能体在状态$s_1$有$0.5$的概率执行向右移动（$a_2$）的动作，有$0.5$的概率执行向下移动（$a_3$）的动作，此时智能体在状态$s_1$时对应的策略为
$$\pi (a_1|s_1)=0,\pi (a_2|s_1)=0.5,\pi (a_3|s_1)=0.5,\pi (a_4|s_1)=0,\pi (a_5|s_1)=0\text{\hspace{1em}(3)}$$

  策略也可以用表格来表示，如表1.2所示。具体来说，表格中第$i$行和第$j$列的元素对应了在第$i$个状态执行了第$j$个动作的概率。在编程时可以定义一个这样的表格，方便理解算法。

1.5 奖励

  奖励（reward） 是强化学习中最独特的概念之一，当一个状态执行一个动作后，智能体会获得奖励$r$，这里，$r$是一个实数，也是状态$s$和动作$a$的函数$r(s,a)$。奖励$r$的取值可以是正数、负数或零。
  直观来看，正的奖励$r$意味着鼓励智能体执行对应的动作，负的奖励$r$意味着不鼓励智能体执行对应的动作，且负的奖励$r$还是一种 “惩罚”，不过在强化学习中都不加区分的统一称为 “奖励”。
  以网格世界为示例，可以定义以下奖励：

• 智能体试图越过边界，令$r_{边界}=-1$
• 智能体试图进入禁止区域，令$r_{禁止}=-1$
• 智能体到达目标区域，令$r_{目标}=1$
• 其他情况：令$r_{其他}=0$

  奖励的过程也可以分为确定性奖励和随机性奖励。确定性奖励的过程可以同时用表格和条件概率来表示。当用如表1.3所示的表格表示时，表格中的元素代表每一行的状态$s$在执行对应列的动作$a$后所获得的奖励$r$。用条件概率可以表示更一般化的奖励过程，在状态$s$执行动作$a$后可以获得奖励$r$的概率为$p(r|s,a)$。例如，对状态$s_1$，有
$$p(r=-1|s_1,a_1)=1,p(r\ne -1|s_1,a_1)=0\text{\hspace{1em}(4)}$$表明状态$s_1$在执行动作$a_1$后可以获得奖励$r=-1$的概率为$1$，获得其他奖励$r$的概率为$0$。

  但是随机性奖励的过程只能用条件概率来表示，例如，
$$p(r=-1|s_1,a_1)=0.5,p(r=-2|s_1,a_1)=0.5\text{\hspace{1em}(5)}$$表明状态$s_1$在执行动作$a_1$后可以获得奖励$r=-1$的概率为$0.5$，可以获得奖励$r=-2$的概率为$0.5$。

注：智能体在到达目标状态后，还有可能持续执行策略，进而持续获得奖励。奖励是人机交互的重要手段，可以通过设置合适的奖励来引导智能体按照人为设置的预期来运动来实现复杂的任务。

  通过奖励表格直接选择最大奖励对应的工作来找到最好的策略是不可取的，因为这些奖励是在执行一个动作后可以立即获得的奖励，也就是即时奖励（immediate reward）。要寻找一个最好的策略，必须考虑更长远的总奖励（total reward）。具有最大及时奖励的动作不一定能带来最大的总奖励。关于总奖励的详细介绍会在第1.6节给出。

1.6 轨迹、回报、回合

1.6.1 轨迹和回报

  首先给出轨迹（trajectory） 和回报（return） 的相关概念定义。
  轨迹（trajectory）： 一条轨迹指的是一个“状态-动作-奖励”的链条。
  汇报（return）： 智能体沿着一条轨迹不断得到的一系列即时奖励之和。即时奖励的定义在第1.5节中已经给出。

  下面通过图1.6所描述的策略及对应轨迹来进一步解释这两个概念。
  基于图1.6所述的策略及对应轨迹，智能体从状态$s_1$出发会得到如下轨迹：
$$s_1\underset{r=0}{\overset{a_2}{\to }}{s}_2\underset{r=0}{\overset{a_3}{\to }}{s}_5\underset{r=0}{\overset{a_3}{\to }}{s}_8\underset{r=+1}{\overset{a_2}{\to }}{s}_9$$得到的回报为
$$\mathrm{return}=0+0+0+1=1\text{\hspace{1em}(6)}$$  这里，我们基于例子重新描述一下回报的概念。回报是由即时奖励（immediate reward） 和未来奖励（future reward） 组成。即时奖励和未来奖励定义如下：
  即时奖励（immediate reward）： 智能体在执行一个动作后可以立即获得的奖励。
  未来奖励（future reward）： 智能体在离开初始状态后获得的奖励之和。
通过式（6）可知，图1.6所描述的策略及对应的轨迹所得到的即时奖励是0，未来奖励是1，则总奖励是1。

注：回报也可以称为总奖励（total reward）或者累积奖励（cumulative reward）。

  回报具有可以评价一个策略“好坏”的能力。这里我们给出如图1.7所示的第二种策略及对应轨迹，然后得出智能体按照其策略从状态$s_1$出发得到的轨迹如下：
$$s_1\underset{r=0}{\overset{a_3}{\to }}{s}_4\underset{r=-1}{\overset{a_3}{\to }}{s}_7\underset{r=0}{\overset{a_2}{\to }}{s}_8\underset{r=+1}{\overset{a_2}{\to }}{s}_9$$得到的回报为
$$\mathrm{return}=0-1+0+1=0\text{\hspace{1em}(7)}$$  分别观察图1.6，图1.7和其对应的计算出的回报结果（6）和（7），我们可以发现，通过直觉观察图1.6，图1.7描述的策略及其对应轨迹，可知图1.6的策略比图1.7的策略要好，这是因为图1.7描述的策略会经过禁止区域。这样的结果和数学上计算回报得到的结论是一致的。

  下面考虑轨迹长度的两种不同情况：
  有限长轨迹： 如图1.6和图1.7所考虑的轨迹，轨迹是有限长的，智能体到达目标区域后会停止策略的执行，也不会再获得奖励。
  无限长轨迹： 实际中可能存在无限长的轨迹，智能体到达目标区域后会还会继续执行策略，也会不断获得奖励。
  这里以图1.6为例，给出考虑无限长轨迹的情况。当智能体到达目标区域$s_9$后不会停止策略的执行，在$s_9$后执行保持不动的动作会不断得到$+1$的奖励，对应的轨迹理论上也是无限长的，轨迹给出如下：
$$s_1\underset{r=0}{\overset{a_2}{\to }}{s}_2\underset{r=0}{\overset{a_3}{\to }}{s}_5\underset{r=0}{\overset{a_3}{\to }}{s}_8\underset{r=+1}{\overset{a_2}{\to }}{s}_9\underset{r=+1}{\overset{a_5}{\to }}{s}_9\underset{r=+1}{\overset{a_5}{\to }}{s}_9\underset{r=+1}{\overset{a_5}{\to }}{s}_9\cdots$$
得到的回报为
$$\mathrm{return}=0+0+0+1+1+1+\cdots =\infty \text{\hspace{1em}(8)}$$可以看出，所计算出的无限长轨迹的回报会发散到无穷。为了避免这种情况，引入折扣回报（discounted return）的概念，定义$\gamma \in (0,1)$为折扣因子（discounted rate），折扣回报的定义如下：
  折扣回报（discounted return）： 折扣回报是所有折扣奖励的总和，即不同时刻得到的奖励添加对应的折扣因子再求和。
  基于上述定义计算出的无限长轨迹的折扣回报如下：
$$\mathrm{discounted}\mathrm{return}=0+\gamma 0+{\gamma }^{2}0+{\gamma }^{3}1+{\gamma }^{4}1+{\gamma }^{5}1+\cdots \text{\hspace{1em}(9)}$$由于折扣因子$\gamma \in (0,1)$，式（9）中的折扣回报值不再是无穷的，通过提取公因子，利用等比数列的求和公式及折扣因子$\gamma$的属性，可以计算出如下的有限折扣回报值：
$$\mathrm{discounted}\mathrm{return}={\gamma }^3(1+\gamma +{\gamma }^2+\cdots )={\gamma }^3\frac{1}{1-\gamma }\text{\hspace{1em}(10)}$$

注：等比数列求和公式：$S_n=n{a}_1,q=1;S_n=\frac{a_1(1-q^n)}{1-q},q\ne 1$。对于式（10），折扣因子$\gamma \in (0,1)$，所以，当$n\to \infty$，${\gamma }^n\to 0$。

  折扣因子引入的作用如下：

• 允许考虑无限长的轨迹，且避免了回报发散到无穷的情况。
• 引入折扣因子可以用来调整对近期或远期奖励的重视程度。

注：若$\gamma$接近0，则智能体会更加重视近期奖励，最后得到的策略会比较短视。若$\gamma$接近1，则智能体会更加重视远期奖励，最后得到的策略也更具有远见。

1.6.2 回合

  回合（episode） 的定义如下：
  回合（episode）： 当执行一个策略进而与环境交互时，智能体从初始状态开始到终止状态（terminal state） 停止的过程被称为一个回合或尝试（trial）。
  此外，回合通常还可以被视为一个有限长的轨迹，但也存在无限长轨迹的情况，这就引申出了两个定义：
  回合制任务（episodic task）： 最多有有限步的任务。
  持续性任务（continuing task）： 智能体与环境的交互永不停止，任务没有终止状态。
  回合制任务可以转化为持续性任务，只需合理定义智能体到达终止状态后的状态和动作元素等，一般存在以下两种转化方法：

• 将终止状态视为特殊状态，可以通过设计专门的动作空间或状态转移来使智能体永远停留在终止状态。这样的状态也称为吸收状态（absorbing state）。

例如，针对状态$s_9$，可以设计其动作空间 A = { a 5 } \mathcal{A}=\{a_5\} A={a5​}，这样智能体到达这个状态后只能执行原地不动的动作。

• 将终止状态视为普通状态，与其他状态一视同仁，智能体机制到达终止状态也可以离开该状态并再次回来。

例如，智能体每次到达状态$s_9$都会获得$r=+1$的正奖励，未来的预期是智能体最终会学会永远停留在状态$s_9$，这样可以获得更多的奖励。但是为了避免计算的回报发散到无穷，在这种情况下，将回合制任务转化为持续性任务需要引入折扣因子$\gamma$并计算折扣回报。

1.7 马尔可夫决策过程

  马尔可夫决策过程（Markov decision process，MDP） 是描述随机动态系统的一般框架，并不局限于强化学习，恰恰是强化学习依赖于这个框架。下面首先给出马尔可夫决策过程涉及的关键要素。

• 集合：

  • 状态空间：所有状态的集合，记为$\mathcal{S}$。
  • 动作空间：与每个状态$s\in \mathcal{S}$相关联的所有动作的集合，记为$\mathcal{A}(s)$。
  • 奖励集合：与$(s,a)$相关联的所有奖励的集合，记为$\mathcal{R}(s,a)$。

• 模型/概率分布（probability distrubution）：

  • 状态转移概率：在状态$s$执行动作$a$时，智能体转移到状态$s^{\prime }$的概率为$p(s^{\prime }|s,a)$。对于任意的$(s,a)$，都有${\sum }_{s^{\prime }\in \mathcal{S}}p(s^{\prime }|s,a)=1$成立。
  • 奖励概率：在状态$s$执行动作$a$时，智能体获得奖励$r$的概率为$p(r|s,a)$ 。对于任意的$(s,a)$，都有${\sum }_{r\in \mathcal{R}}p(r|s,a)=1$成立。

• 策略： 在状态$s$时，智能体执行动作$a$的概率为$\pi (a|s)$。对于任意的状态$s\in \mathcal{S}$，都有${\sum }_{a\in \mathcal{A}s}\pi (a|s)=1$成立。

• 马尔可夫性质： 马尔可夫性质（Markov property）指的是随机过程中的无记忆性质，在数学上的表示如下：
  $$\begin{array}{r}p(s_{t+1}|s_t,a_t,s_{t-1},s_{t-1},\dots ,s_0,a_0)=p(s_{t+1}|s_t,a_t)\\ p(r_{t+1}|s_t,a_t,s_{t-1},s_{t-1},\dots ,s_0,a_0)=p(r_{t+1}|s_t,a_t)\end{array}\text{\hspace{1em}(11)}$$其中，$t$表示当前时刻，$t+1$表示下一时刻。从式（11）可知，下一个状态和奖励仅依赖于当前时刻的状态和动作，与之前时刻的状态的动作无关。
    一些与马尔可夫决策过程相关的概念知识解释：

• 模型（model）\动态（dynamic）： 马尔可夫决策过程中的$p(s^{\prime }|s,a)$和$p(r|s,a)$被称为模型或动态。

  • 平稳（stationary）模型/动态：不会随时间变化的模型/动态。
  • 非平稳（nonstationary）模型/动态：会跟随时间变化的模型/动态。

  例如，在网格世界中，如果一个禁止区域时而出现时而小消失，那么所对应的状态转移或者奖励就是随时间变化的，这时系统就是非平稳的。

• 马尔可夫过程（Markov procession，MP）： 马尔可夫过程（Markov procession，MP）：若马尔可夫决策过程中的策略是确定的，那么马尔可夫决策过程就会退化为马尔可夫过程。
    如图1.8所示，网格世界中的策略是给定的，这时整个系统就被抽象成了一个马尔可夫过程。

注：所研究的马尔可夫决策过程一般都是考虑有限情况，也就是状态和动作的数量都是有限的。

  强化学习的过程涉及智能体与外接环境的交互，智能体之外的一切都被视为环境（environment）。
  强化学习的过程中智能体承担的角色

• 感知者：具有类似眼睛功能的感知能力，能感知并理解当前的状态。
• 决策者：具有类似大脑的决策能力，能够知道在什么状态执行什么动作。
• 执行者：具有操作执行机构的能力，能够操作机构来执行策略所指示的动作，达到改变状态并获得奖励的目的。

  关于问答中提问二（奖励是下一个状态的函数吗？）中公式的推导补充。

这个问题的数学描述是：是否应该用$p(r|s,a,s^{\prime })$而不是$p(r|s,a)$？
答案：$r$实际上依赖于$s$、$a$、$s^{\prime }$这三者。但由于$s^{\prime }$也依赖于$s$和$a$，所以可以等效地将$r$写为$s$和$a$的函数：
$$p(r|s,a)=\sum _{s^{\prime }\in \mathcal{S}}p(r|s,a,s^{\prime })p(s^{\prime }|s,a)$$在推导之前，首先给出相关基础知识。
联合概率： 符号$p(X=x,Y=y)$或$p(x,y)$描述随机变量$X$取值$x$和随机变量$Y$取值$y$的概率，也就是事件$X=x$和事件$Y=y$同时发生的概率。且有如下关系：
$$\sum _{y}p(x,y)=p(x)$$条件概率： 符号$p(X=x|A=a)$描述了在随机变量$A$已经取值$a$的情况下，随机变量$X$取值$x$的概率。$p(X=x|A=a)$通常简写为$p(x|a)$。联合概率和条件概率存在以下关系：
$$p(x,a)=p(x|a)p(a),p(x|a)=\frac{p(x,a)}{p(a)}$$全概率公式： 由$p(x)={\sum }_{a}p(x,a)$，以下关系成立
$$p(x)=\sum _{a}p(x,a)=\sum _{a}p(x|a)p(a)$$下面基于上述知识，给出关系$p(r|s,a)={\sum }_{s^{\prime }\in \mathcal{S}}p(r|s,a,s^{\prime })p(s^{\prime }|s,a)$的推导过程：
对于式${\sum }_{s^{\prime }\in \mathcal{S}}p(r|s,a,s^{\prime })p(s^{\prime }|s,a)$，根据联合概率和条件概率，可以得到
$$\begin{array}{rl}\sum _{s^{\prime }\in \mathcal{S}}p(r|s,a,s^{\prime })p(s^{\prime }|s,a)& =\sum _{s^{\prime }\in \mathcal{S}}[\frac{p(r,s,a,s^{\prime })}{p(s^{\prime },s,a)}\times \frac{p(s^{\prime },s,a)}{p(s,a)}]=\sum _{s^{\prime }\in \mathcal{S}}\frac{p(r,s,a,s^{\prime })}{p(s,a)}\end{array}$$对于式${\sum }_{s^{\prime }\in \mathcal{S}}\frac{p(r,s,a,s^{\prime })}{p(s,a)}$，根据全概率公式可以得到
$$\begin{array}{r}\sum _{s^{\prime }\in \mathcal{S}}\frac{p(r,s,a,s^{\prime })}{p(s,a)}=\frac{p(r,s,a)}{p(s,a)}=p(r|s,a)\end{array}$$关系得证。

参考文献：
[1] 赵世钰.强化学习的数学原理[M].清华大学出版社:202504.271.