[人工智能]强化学习笔记（3）—— 有限马尔可夫决策过程（finite MDP）

• 参考：
  1. 周博磊老师的教程
  2. Richard S.Sutton 《Reinforce Learning》第3章
• 符号说明：本文用 $S_t$ 或 s 代表当前时刻 t 的状态，$S_{t+1}$ 或 s’ 代表下一时刻的状态；$A_t$ 或 a 代表当前时刻 t 的动作，$A_{t+1}$ 或 a’ 代表下一时刻的动作

1. “智能体-环境”交互接口

1.1 强化学习中的交互过程

• 强化学习中，进行学习和实施决策的机器称为 智能体 (agent)，智能体之外所有与之交互作用的事物都被称为 环境(environment)。每个时刻，智能体根据根据其 策略(policy)，在当前所处 状态(state) 选择一个 动作(action)，环境对这些动作做出相应的相应的响应，并转移到新状态。同时环境还会产生一个 奖励信号 (reward)，这通常是一个数值，奖励的折扣累加和称为 收益/回报 (return)，是智能体在动作选择过程中想要最大化的目标
  
  确切地说，在每个时刻 $t=0,1,2,3...$，智能体和环境发生了交互，在每个时刻 $t$ ，智能体观察到所在环境状态的某种特征表达：$S_t\in \mathcal{S}$，并在此基础上选择一个动作：$A_t\in \mathcal{A}(s)$。下一时刻，作为动作的结果，智能体受到一个数值化的奖励：$R_{t+1}\in \mathcal{R}?\mathbb{R}$，并进入一个新状态 $S_{t+1}$。从而，环境和智能体共同给出一个序列或轨迹，即
  $$S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,...$$
• 说明：
  1. 为了简化问题，我们只关注离散时间的情况，虽然也有一些方法扩展到了连续时间情况
  2. 为了简化符号，我们有时假设一个特殊情况，即所有状态下的动作集合都是一样的，因此动作集可以简单记作 $\mathcal{A}$，可以通过对所有状态下动作集取并集来转化成这种特殊情况
  3. 我们使用 $R_{t+1}$ 而非 $R_t$ 来表示 $A_t$ 导致的收益，是为了强调下一时刻收益和下一时刻状态是一起被环境一起决定的。不过这两种表示方法都在文献中广泛使用，因此需要特别注意。

1.2 交互过程的形式化

• 假设上述过程中，状态、动作、收益的集合 $\mathcal{S},\mathcal{A},\mathcal{R}$ 都只有有限个元素。这时随机变量 $R_t,S_t$ 服从具有确定定义的离散概率分布，并且只依赖于前驱状态和动作（因此其具有马尔可夫性）。这个概率分布定义了整个交互过程的动态特性

1.2.1 四参数动态函数

• 考虑 $t$ 时刻，智能体在状态 $s$ 执行动作 $a$，在 $t+1$ 时刻转移到新状态 $s^{\prime }$ 并获得奖励 $r$ 的概率
  p ( s ′ , r ∣ s , a ) ? P r { S t + 1 = s ′ , R t = r ∣ S t = s , A t = a } p(s',r|s,a) \doteq Pr\{S_{t+1}=s',R_t=r|S_t=s,A_t= a\} p(s′,r∣s,a)?Pr{St+1?=s′,Rt?=r∣St?=s,At?=a}
  其中 $s^{\prime },s\in \mathcal{S}$，$a\in \mathcal{A}(s)$，$r\in \mathcal{R}$
• 这是一个四参数式，$p:\mathcal{S}\times \mathcal{R}\times \mathcal{S}\times \mathcal{A}\to [0,1]$，它对每个 $(s,a)$ 二元组的选择指定了一个概率分布，即有
  $$\sum _{s^{\prime }\in \mathcal{S}}\sum _{r\in \mathcal{R}}p(s^{\prime },r|s,a)=1,对所有s\in \mathcal{S},a\in \mathcal{A}(s)$$

1.2.2 三参数动态函数

• 四参数动态函数同时考虑转移新状态 $s^{\prime }$ 和 奖励 $r$，但在大部分情境中，某个 $(s,a)$ 二元组对应的奖励往往是定值，我们也常把将二者拆开分析，这时有
  { p ( s ′ ∣ s , a ) ? P r { S t + 1 = s ′ ∣ S t = s , A t = a } = ∑ r ∈ R p ( s ′ , r ∣ s , a ) r ( s , a ) ? E [ R t + 1 ∣ S t = s ′ ∣ S t = s , A t = a ] = ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) = ∑ r , s ′ r p ( s ′ , r ∣ s , a ) \left\{ \begin{aligned} &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)\\ &r(s,a) \doteq \mathbb{E}[R_{t+1}|S_t=s'|S_t=s,A_t= a] = \sum_{r\in\mathcal{R}}r \sum_{s'\in\mathcal{S}} p(s',r|s,a) = \sum_{r,s'}rp(s',r|s,a)\\ \end{aligned} \right. ???????????p(s′∣s,a)?Pr{St+1?=s′∣St?=s,At?=a}=r∈R∑?p(s′,r∣s,a)r(s,a)?E[Rt+1?∣St?=s′∣St?=s,At?=a]=r∈R∑?rs′∈S∑?p(s′,r∣s,a)=r,s′∑?rp(s′,r∣s,a)?
• 本文后续内容将混用以上两种动态函数，请读者注意

1.2.3 利用动态函数计算环境信息

• 上面我们利用 $p(s^{\prime },r|s,a)$ 计算了三参数的动态函数，事实上，利用四参数动态函数，我们可以算出关于环境的任何其他信息，比如：
  1. $(s,a,s^{\prime })$ 三元组的期望奖励：
     $$r(s,a,s^{\prime })?\mathbb{E}[R_{t+1}|S_t=s,A_t=a,S_{t+1}=s^{\prime }]=\sum _{r\in \mathcal{R}}r\frac{p(s^{\prime },r|s,a)}{p(s^{\prime }|s,a)}$$
  2. 当前状态是 $s$，智能体按策略 $\pi$ 选择动作，那么下一时刻获取的期望奖励：
     $$r(s)?\mathbb{E}[R_{t+1}|S_t=s]=\sum _{a\in \mathcal{A}(s)}\pi (a|s)r(s,a)=\sum _{a\in \mathcal{A}(s)}\pi (a|s)\sum _{r,s^{\prime }}rp(s^{\prime },r|s,a)$$
  3. 智能体在状态 $s$ 按策略 $\pi$ 选择动作，下一时刻转移到 $s^{\prime }$ 的概率：
     p ( s ′ ∣ s ) ? P r { S t + 1 = s ′ ∣ S t = s } = ∑ a ∈ A ( s ) π ( a ∣ s ) p ( s ′ ∣ s , a ) = ∑ a ∈ A ( s ) π ( a ∣ s ) ∑ r ∈ R p ( s ′ , r ∣ s , a ) p(s'|s) \doteq Pr\{S_{t+1}=s'|S_t=s\} = \sum_{a\in\mathcal{A}(s)}\pi(a|s)p(s'|s,a) = \sum_{a\in\mathcal{A}(s)}\pi(a|s)\sum_{r\in\mathcal{R}}p(s',r|s,a) p(s′∣s)?Pr{St+1?=s′∣St?=s}=a∈A(s)∑?π(a∣s)p(s′∣s,a)=a∈A(s)∑?π(a∣s)r∈R∑?p(s′,r∣s,a)

1.2.4 小结

• 可见，通过把交互过程抽象为动作集、状态集、奖励信号及动态函数，整个交互过程可以被良好地形式化，并且能方便地计算各种环境信息。在强化学习中，我们把这种框架抽象为马尔可夫决策过程（MDP），下面第2节将进行介绍
• $p$ 和 $r$ 是关于环境的两个重要函数，通常称 $p$ 为 状态转移矩阵，称 $r$ 为 奖励函数

1.3 交互过程的细节

1.3.1 目标和收益

• 交互过程中的每个时刻，智能体都从环境获取一个单一的标量数值 $R_t\in \mathcal{R}$ 作为奖励，智能体对其进行折扣累加得到收益，并且试图通过调整策略最大化这个收益。注意到要最大化并非某一步的奖励，而是长期奖励的折扣累加和，这意味要最大化的并非当前奖励，而是长期的累计收益

• “奖励&收益” 其实是智能体目标的一种形式化表征。可以把这种想法非正式地表述为 “收益假设”

  智能体所有的 “目标” 或 “目的” 都可以归结为：最大化智能体收到的标量奖励信号的累计和（称之为“收益”）的概率期望值

  使用收益来形式化目标是强化学习最显著的特征之一

• 设计奖励函数是强化学习的一大难点，请注意：

  1. 智能体只会学习如何最大化收益，如果想让它完成某些指定任务，就必须保证我们设计的奖励函数可以使得智能体最大化收益的同时也能实现我们的目标
  2. 不要试图将实现目标的先验知识通过奖励函数传递给智能体。尽管大部分符合先验知识的动作有助于实现最终的 “目标”，但由于缺乏约束，这时最大化收益不能保证目标一定可以实现。例如，国际象棋游戏中，智能体应当只有在最终获胜时获得奖励，而非到达某个子目标（比如吃掉对方的棋子或者控制中心区域），否则智能体很可能找到某些 “刷分方法”，通过不停地实现子目标得到比实现最终目标更大的奖励（比如只顾着吃掉对方棋子而不在乎最终是否获胜）。收益信号只能用来传达什么是你想要实现的目标，而不是如何实现这个目标。虽然说起来很简单，但在复杂任务中，清晰地描述最终目标是很难的，有时还会遇到多个目标的情况，这些都使得设计奖励函数变得十分复杂。这里可以参考：强化学习《奖励函数》的设计和设置（REWARD SHAPING）
  3. 要想传授先验知识，更好的方法是给智能体设置初始策略，或初始价值函数，或对这两者施加影响

1.3.2 收益的形式化定义

• 这一节我们考虑如何形式化地定义强化学习的目标，假设时刻 t 之后收到的奖励序列为 $R_{t+1},R_{t+2},R_{t+3},...$，智能体要最大化 “期望收益”，期望收益通常被定义为收益序列的一些特定函数，记为 $G_t$。首先，我们注意到任务可以分成两类
  1. 分幕式任务：这类任务中存在 “最终时刻” 的概念，智能体和环境的交互过程可以被自然地划分为一系列包含最终时刻的子序列。分幕意味着智能体的一个动作仅能影响到之后的有限个奖励。我们称每个子序列为一个 幕/轨迹(episode)，例如一局游戏、一次走迷宫的旅程，或任何这类重复性的交互过程。每幕都以一种特殊的状态结束，称之为 “终结状态”。随后会重新从某个标准的起始状态或起始状态的分布中的某个状态样本开始。下一幕的开始与上一幕完全无关，可以把所有幕看作在相同的状态下终止，只是对不同的结果有着不同的收益。分幕式任务中，我们有时要区分非终结状态集，记为 $\mathcal{S}$，和包含状态状态的所有状态集，记为 ${\mathcal{S}}^{+}$。假设某幕在任务开始后的 $T$ 时刻到达终结状态，$T$ 是一个随机变量，通常随着每幕的不同而不同
  2. 持续性任务：这类任务中，智能体和环境的交互过程不能被自然地划分为单独的幕，而是持续不断地发生。不分幕意味着智能体的一个动作可以影响到之后收到的无限个收益。例如某个持续性控制任务（如维持倒立摆直立），这时最终时刻 $T=\infty$。由于交互过程永远持续，智能体不断接受奖励，很容易使得要最大化的收益 $G_t$ 趋向 $\infty$，这是一个严重问题，因为往往很多策略都能导致无限长收益序列，进而导致无穷收益，这时即使最大化收益也无法锁定最优策略。
• 下面给出收益 $G_t$ 的常用定义式，其数学形式尽量简单：
  1. 分幕式任务：一定不会出现无穷收益的问题，可以简单地把 $G_t$ 定义为 t 时刻后的所有奖励之和，即
     $$G_t?R_{t+1}+R_{t+2}+...+R_T$$
  2. 持续性任务：通常把收益 $G_t$ 定义为奖励序列的折扣累加和，即
     $$G_t?R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...=\sum _{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$$
     其中 $\gamma \in [0,1)$ 称为 折扣系数/折扣率，因为折扣系数小于1，能够保证不会出现无穷奖励
• 针对 $\gamma$ 的进一步说明：
  1. 设置 $\gamma <1$ 可以避免无限长奖励序列导致无穷收益。比如每时刻获取收益 $+1$，那么收益为
     $$G_t=\sum _k^{\infty }{\gamma }^k=\frac{{\gamma }^0(1?{\gamma }^{\infty })}{1?\gamma }=\frac{1}{1?\gamma },(\gamma <1)$$
     事实上，“避免在持续性任务中出现无穷收益” 是我们必须引入 $\gamma$ 的唯一原因。以下其他几点都是锦上添花的好处。
  2. 折扣率决定了未来收益的现值：未来时刻 $k$ 的奖励值只有其实际值的 ${\gamma }^{k?1}$ 倍，越未来的状态乘上的折扣系数越多，这是对于未来奖励不确定性的体现
  3. 人和动物的行为中都表现出对即刻奖励的追求，$\gamma$ 可以模拟这一点，它使模型更看重短期奖励（权重更高）
  4. $\gamma =0$ 时意味只考虑当前奖励，智能体是 “目光短浅的”，其目标是学习如何选择 $A_t$ 来最大化下一时刻奖励 $R_{t+1}$，这仅在智能体的动作不影响未来奖励时适用，但通常情况下，最大化当前收益会减少未来的收益。这个关系有点像局部最优与全局最优；随着 $\gamma$ 增大，折后收益将更多地考虑未来收益，智能体也就变得 “有远见” 了
  5. 折扣系数 $\gamma$ 一般用作超参数，可以通过调整它获取不同行为的智能体
• 示例 & 练习：
  1. 倒立摆：这个任务中，智能体通过控制向滑车施加推力，维持滑车上道理的杆子不倒，若杆子偏离超过一定角度或小车偏离轨道则视为失败，每次失败后，杆子重新回到垂直状态。我们可以把这个任务视作分幕式任务，对每个合格时刻给出+1的奖励，因此每个轨迹的收益就是其长度，而永远不倒就意味着无限收益；我们也可以把它视作持续性任务，仅在每次失败时给与-1的奖励，这时训练过程中的失败重启并不打断收益的计算，因此有
     $$G_t=?\sum _{k\in \mathcal{K}}{\gamma }^{k?t},\mathcal{K}是倒下时刻的集合$$
     重要的一点是，无论那种设定，都要保证在最大化收益的同时，也能顺带实现我们的目标
  2. 走迷宫：想象我们在设计一个走迷宫机器人，当它从迷宫逃脱时得到收益+1，否则收益为0。这个任务似乎可以自然地被看作分幕任务，我们设置 $\gamma =1$，但在训练一段时间后，机器人逃离迷宫的能力不再提高了，问题出在哪里？事实上，只要机器人一直随机移动，总能以1的概率到达终点，又因为 $\gamma =1$，无论轨迹有多长，最终的收益都一致，因此无论智能体策略如何，性能都一样。要处理这个问题，首先要明确我们希望的是 “尽快” 走出迷宫，为此我们可以设置 $\gamma <1$，或者在每一时刻施加一个负奖励，这样智能体才能在最大化收益时实现尽快走出迷宫的目标。另外，在某些情况下，代理可能会陷入循环中，为此必须针对性施加某些规则进行处理
  3. 假设 $\gamma =0.9$，收益序列是首项 $R_1=2$ 的无限7循环序列（即$R_2=R_3=...=7$），请计算 $G_1,G_0$。
     $$?\begin{array}{rl}& G_1=7+7\gamma +7{\gamma }^2+...=7\sum _{k=0}^{\infty }{\gamma }^k=\frac{7}{1?\gamma }\\ & G_0=R_1+\gamma G_1=2+\frac{7}{1?\gamma }\end{array}$$

1.3.3 分幕式任务和持续性任务的统一表示法

• 我们常常会同时讨论分幕式和持续性两种任务，因此我们需要一个统一的表示法，使我们能够同时精确地讨论这两种情况。
• 首先考虑两种任务在符号表示上的主要区别
  1. 分幕式任务：
     1. 我们面对的是一组有限长的 “幕序列”，理论上不能简单的将时刻 t 的状态表示为 $S_t$，而是要区分其所在的幕，比如用 $S_{t,i}$ 表示第 i 幕中 t 时刻的状态（对于 $A_{t,i},R_{t,i},T_i$ 等也是一样的）
     2. 由于每幕长度有限，不用担心出现 $G_t=\infty$ 的情况，收益可以简单地定义为奖励求和
  2. 持续性任务：
     1. 我们面对的只有一条无限长的幕，因此可以将时刻 t 的状态表示为 $S_t$
     2. 为了避免出现无限收益，必须引入折扣系数 $\gamma$，收益定义为奖励的折扣加权和
• 为了统一符号，我们做以下两个约定：
  1. 对于分幕性任务，由于实践中，我们几乎总是在考虑某个特定的幕序列，或者考虑适用于所有幕的东西。因此我们约定忽略幕编号 $i$，来略微地滥用符号，也就是说，我们在分幕任务中也使用 $S_t$ 来表示 $S_{t,i}$ 等，从而统一了符号表示
  2. 对于分幕性任务，我们把幕的终止看作一个特殊的 “吸收状态” 入口，它只会转移到自己并只产生0收益。下图为一个示例
     
     这样一来，无论我们计算前 $T$ 个收益（上图 $T=3$）的总和，还是计算无限序列的全部总和，我们都能得到相同的收益，并且在加入折扣时依然成立。换句话说，只要我们把 $T$ 时刻的折后收益设为 $G_T=0$，那么持续性任务的收益定义就适用于任何时刻 $t<T$，即使最终时刻出现在 $T+1$ 也不例外，而且这时不需折扣，可以设置 $\gamma =1$
     
• 综上所述，我们把收益定义为
  $$G_t?R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...+{\gamma }^{T?t?1}{R}_T=\sum _{k=t+1}^T{\gamma }^{k?t?1}{R}_k$$
  其中 $\gamma \in [0,1]$，并且在 $\gamma <1$ 时允许 $T=\infty$
• 根据以上定义，邻接时刻的收益可以用如下的递归方式连接起来：
  $$\begin{array}{rl}{G}_t& ?R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...\\ & =R_{t+1}+\gamma (R_{t+1}+\gamma R_{t+1}+{\gamma }^2{R}_{t+4})\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$
  这个式子对于强化学习的理论和算法来说至关重要：
  1. 计算给定时刻的收益 $G_t$ 时，我们通常利用此式对奖励序列进行反向折扣求和
  2. Bellman等式的推导中也使用了此式

2. 马尔可夫链

• 从本节开始，我们逐步对强化学习中的整个交互框架进行形式化，从环境具有的一个关键性质：“马尔可夫性” 入手
• 马尔可夫链这个框架中，包含了第一节中的 状态 以及 状态转移矩阵

2.1 马尔可夫性/无后效性（Markov Property）

• 定义：过程或系统在时刻 $t_0$ 所处的状态为已知的情况下，在时刻 $t>t_0$ 所处状态的条件分布与过程在时刻 $t_0$ 之前所处的状态无关。通俗的说就是系统下一步状态仅取决于当前状态，而与历史状态无关，注意，这不是说过去的状态不会影响下一步状态，而是过去的状态通过影响当前的状态，进而间接地影响下一步状态
• 形式化定义：
  1. 定义 状态历史： h t = { s 1 , s 2 , s 3 , . . . , s t } h_t = \{s_1,s_2,s_3, ...,s_t\} ht?={s1?,s2?,s3?,...,st?}
  2. 定义 马尔可夫性：如果系统满足以下性质，我们称这个系统具有马尔科夫性
     $$\{\begin{array}{rl}& P(s_{t+1}|s_t)=P(s_{t+1}|h_t)\\ & P(s_{t+1}|s_t,a_t)=P(s_{t+1}|h_t,a_t)\end{array}$$
• 需要说明的是，这种性质不是为了简化而简化，而是有一定依据的。比如我们都知道的一个走迷宫技巧：在每个岔路总是选择拐弯（这会执行一个深度优先搜索），把我们所在的不同位置看作不同状态，则每个新状态只与当前状态有关，而这个当前状态又是由历史的所有状态决定的
• 注意到第一节中描述的 “智能体-环境” 交互框架的动态函数为 $p(s^{\prime },r|s,a)$，任意时刻 $t$ 时 $S_t,R_t$ 的取值仅取决于前一个状态 $S_{t?1}$ 和前一个动作 $A_{t?1}$，因此RL交互框架中的状态和奖励信号具有马尔可夫性

2.2 马尔可夫过程（Markov Process/MP）

• 定义：具有马尔科夫性的随机过程称为马尔科夫过程
• 马尔科夫过程描述的是系统从一个状态到另一个状态转换的随机过程。该过程要求具备马尔可夫性，也就是下一状态的概率分布只与当前的状态有关，而与时间序列中其他前面的事件无关。

2.3 马尔可夫链（Markov Chain）

• 马尔可夫链描述了一个具有马尔可夫性质的系统的状态转移情况
• 把系统的所有状态画成若干个点，然后用箭头和转移概率把它们连接起来，就得到了这个系统的马尔可夫链。例如：下图是一个具有4个状态的系统，状态间以一定的概率转移，且这个概率仅取决于当前状态
• 形式化描述
  1. 状态（概率）向量： X n = { x 1 n , x 2 n , . . . , x k n } X^n = \{x_1^n,x_2^n,...,x_k^n\} Xn={x1n?,x2n?,...,xkn?}
     • 状态向量描述了第n次观测时，系统可能处于各个状态的概率
     • 系统的可能状态数有k个，$x_1^n,x_2^n,...,x_k^n$都是概率，${\sum }_{i=1}^k{x}_i^n=1$
     • $X^0$ 被称为初始状态
  2. 状态转移矩阵
     • 我们用$P_{s{s}^{\prime }}$表示从状态s转移到状态s’的概率，即$P_{s{s}^{\prime }}=P(S_{t+1}=s^{\prime }|S_t=s)$
     • 这样就可以用矩阵的形式表示所有状态的转移概率
       称这个矩阵为 “状态转移矩阵”，注意这个矩阵的行和/列和都是1
  3. 只要求出状态转移矩阵 $P$，这个系统（马尔可夫模型）就确定了：根据无后效性，我们可以得出任意时刻 n，系统处于各个状态的概率为
     $$\begin{array}{rl}{X}^n& =X^{n?1}P\\ & =X^0{P}^n\end{array}$$
• 利用马尔可夫链（准确说是利用状态转移矩阵），我们就可以从初始状态预测系统未来任意时刻可能处于的状态概率分布。这个预测本质就是状态转移矩阵的连乘，因此这还涉及一个收敛性的问题，这里不展开讨论，可以参考：数学模型——初步理解马尔可夫链（Markov chain）

3. 马尔可夫奖励过程（Markov reward process/MRP）

• 简单看，MRP = Markov chain + reward function
• MRP这个框架中，进一步包含了第一节的 奖励（函数） 以及 收益，并且引入了 状态价值函数

3.1 基础概念

1. 轨迹/幕(episode/trajectory/trial)：对马尔可夫链采样得到一个状态序列，称为一个轨迹
2. 幕长(horizon)：一个轨迹的最大时间步数（number of maximum time step），可以是$\infty$，否则称为 有限MRP
3. 收益(return) $G_t$：t 时刻的收益，定义为给定轨迹horizon中从第 t 步开始到最后的奖励折扣加权和
   $$G_t?R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...+{\gamma }^{T?t?1}{R}_T=\sum _{k=t+1}^T{\gamma }^{k?t?1}{R}_k$$
   其中 $\gamma \in [0,1]$，并且在 $\gamma <1$ 时允许 $T=\infty$
4. 状态价值函数(value function) $v(s)$：$v(S_t)$ 代表第 t 步处于状态 $S_t=s$ 时的收益 (return) 的期望，即 “未来可能获取奖励的加权和” 的当前期望值
   $$v(S_t=s)=\mathbb{E}[G_t|S_t=s]=\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...+{\gamma }^{T?t?1}{R}_T|S_t=s]$$
   $v(s)$也常记为$v(S_t)$ 或 $v_s$ ，这是对状态的一个评鉴指标。它描述了进入状态s可以获取的 “长期价值” （long-term value），这真正表示了进入状态s有多好

3.2 定义

• 马尔可夫奖励过程MRP是一个四元组 $<S,P,R,\gamma >$
  1. $S$：有限状态集
  2. $P$：状态转移矩阵，定义了 $P_{s{s}^{\prime }}=P(S_{t+1}=s^{\prime }|S_t=s)$
  3. $R$：奖励函数 $R(S_t=s)=\mathbb{E}[R_{t+1}|S_t=s]$
  4. $\gamma$：折扣系数，$\gamma \in [0,1]$
• MRP对应一个 “状态-奖励” 序列，形如
  $$S_0,R_1,S_1,R_2,S_2,R_3...$$

3.3 MRP的示例

• MRP中，系统状态按照状态转移矩阵，在马尔可夫链上依概率来回游走，并随之获取奖励，产生奖励序列。例如
  

4. 马尔可夫决策过程（MDP）

• 简单看，MDP = MRP + Policy，MDP是有决策的MRP
• MRP这个框架中，进一步包含了第一节的 动作 以及 策略，并且引入了 动作状态价值函数

4.1 基础概念

1. 策略(policy) $\pi$：策略是从状态到每个动作选择概率之间的映射，是智能体的行为方式，影响着智能体未来所能获取的奖励。设 t 时刻智能体的策略为 $\pi$，给定一个状态 $s$，Policy 指定一个动作的概率分布（ distribution over actions）即：
   $$\pi (a|s)=P(A_t=a|S_t=s)$$
   对于随机性策略，其返回的就是概率分布 $\pi (a|s)$；对于确定性策略，会以某种规则从分布 $\pi (a|s)$ 选择特定动作 $a$ 返回
2. （策略引导的）状态价值函数(value function) $v_{\pi }(s)$：和MRP中的计算方式完全一致，但是产生状态序列和奖励序列的方式不同。MDP中的状态价值函数 $v_{\pi }(s)$ 代表从状态s，采取动作a开始，以Policy $\pi$ 运行获取的 return $G_t$ 的期望
   $$v_{\pi }(S_t=s)={\mathbb{E}}_{\pi }[G_t|S_t=s]={\mathbb{E}}_{\pi }[\sum _{k=t+1}^T{\gamma }^{k?t?1}{R}_k|S_t=s,A_t=a]$$
3. （策略引导的）动作状态价值函数(q function) $q_{\pi }(s,a)$：类似价值函数 $v(s)$， $q_{\pi }(s,a)$ 代表从状态s，采取动作a开始，以 Policy $\pi$ 运行的return $G_t$ 的期望
   $$q_{\pi }(S_t=s,A_t=a)?{\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]={\mathbb{E}}_{\pi }[\sum _{k=t+1}^T{\gamma }^{k?t?1}{R}_k|S_t=s,A_t=a]$$

4.2 定义

• 马尔可夫决策过程MDP是一个五元组 $<S,A,P^a,R,\gamma >$
  1. S：有限状态集
  2. A：有限动作集
  3. $P^a$：状态转移矩阵，定义了 $P_{s{s}^{\prime }}=P(S_{t+1}=s^{\prime }|S_t=s,A_t=a)$
  4. R：奖励函数 $R(S_t=s,A_t=a)=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$
  5. $\gamma$：折扣系数，$\gamma \in [0,1]$
• MDP本身对应一个 “状态-动作-奖励” 序列，形如
  $$S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,...$$

4.3 MDP 和 MRP

4.3.1 从MDP转换到MRP

1. 给出MDP $<S,A,P,R,\gamma >$ 以及 Policy $\pi$
2. 使用 S,P 和 $\pi$ 可以构造 马尔可夫过程MP：$<S,P^{\pi }>$，这对应一个 “状态序列” $S_1,S_2,...$
3. 使用 S,P,R,$\gamma$ 和 $\pi$ 可以构造 马尔可夫奖励过程MRP：$<S,P^{\pi },R^{\pi },\gamma >$，这里$P^{\pi },R^{\pi }$都是把某个状态下所有动作做加权和（求期望），从而消除了动作A：
   $$\begin{gathered} P_{\pi }(s^{\prime }|s)=\sum _a\pi (a|s)P(s^{\prime }|s,a) \\ {R}_{\pi }(s)=\sum _a\pi (a|s)R(s,a) \end{gathered}$$

4.3.2 对比MDP和MRP

• 相比MRP，MDP从状态s出发后首先要在动作分布中选一个action a，然后才能得到转移概率P，进而转移到新状态s’。“选action” 这一环就是 “决策”
  
• 有一个很经典的比喻

  MRP好像一个纸船，在马尔可夫链上的各个状态之间按概率转移矩阵随波逐流
  MDP好像有人在架船，它有Policy，会根据当前的状态采取不同的action，进而影响下一个进入的状态

5. MDP中价值函数的计算

• 价值函数 $v_{\pi }$ 和 $q_{\pi }$ 都能从经验中估算得到，几乎所有强化学习方法都是在用不同的手段估计这个价值。所有的RL方法可以粗略分成以下几类，这些方法将在后续文章进一步详细介绍：
  1. 蒙特卡洛方法（MC）：只要我们对每个遇到的 “$s$ 或 $(s,a)$二元组” 记录其实际收益，那么根据大数定律，只要记录次数趋近于 $\infty$，那么记录收益的平均值会收敛到 $v_{\pi }(s)$ 和 $q_{\pi }(s,a)$。比如要估计 $v_{\pi }(s)$，就可以从状态 $s$ 开始采样多个轨迹，分别计算 $G_t$ 然后取均值（$q(s,a)$ 同理）。这种方法仅适用于状态数量较少的离散状态
  2. 解bellman方程（动态规划方法 DP）：bellman方程给出了价值函数之间的递归关系，$v_{\pi }$ 和 $q_{\pi }$ 是其唯一解。这种方法也仅适用于状态数量较少的离散状态，通常使用迭代法间接求解
  3. 时序差分方法（TD）：结合动态规划的自举思想和蒙特卡洛的采样思想的一种方法，这种方法也仅适用于状态数量较少的离散状态
  4. 函数近似方法（DRL）：当环境中状态数量很多时，独立地估计每个状态的价值是不切实际的，这时我们可以使用函数近似法。把价值函数 $v_{\pi }$ 和 $q_{\pi }$ 参数化（参数数量远远小于要估计的价值数量），然后通过调整价值函数的参数来更好地计算收益值。深度强化学习方法基本都属于函数近似法
• 本节符号约定：$S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s^{\prime },A_{t+1}=a^{\prime }$

5.1 v 和 q 关系

1. 用 $q_{\pi }(s,a)$ 表示 $v_{\pi }(s)$： $v_{\pi }(s)$ 是状态 $s$ 下 $q_{\pi }(s,a)$ 关于 $a$ 的期望，即
   $$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|s]\\ & ={\mathbb{E}}_a{\mathbb{E}}_{\pi }[G_t|s,a]\\ & ={\mathbb{E}}_{a|s}[q_{\pi }(s,a)]\\ & =\sum _a\pi (a|s)q_{\pi }(s,a)\end{array}$$
   用回溯图表示如下：
2. 用 $v_{\pi }(s)$ 表示 $q_{\pi }(s,a)$ ：
   $$\begin{array}{rl}{q}_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[G_t|s,a]\\ & ={\mathbb{E}}_{\pi }[r+\gamma G_{t+1}|s,a]\\ & ={\mathbb{E}}_{\pi }[r+\gamma v_{\pi }(s^{\prime })|s,a]\\ & ={\mathbb{E}}_{s^{\prime },r|s,a}{\mathbb{E}}_{\pi }[r+\gamma v_{\pi }(s^{\prime })]\\ & =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$
   也可使用三参数状态转移函数表示
   $$\begin{array}{rl}{q}_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[r+\gamma v_{\pi }(s^{\prime })|s,a]\\ & ={\mathbb{E}}_{\pi }[r|s,a]+\gamma {\mathbb{E}}_{\pi }[v_{\pi }(s^{\prime })|s,a]\\ & =r(s,a)+\gamma {\mathbb{E}}_{s^{\prime }|s,a}{\mathbb{E}}_{\pi }[v_{\pi }(s^{\prime })]\\ & =r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{\pi }(s^{\prime })\end{array}$$
   用回溯图表示如下：
   

5.2 贝尔曼等式

• 符号约定：$S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s^{\prime },A_{t+1}=a^{\prime }$

5.2.1 贝尔曼等式（Bellman equation）

• 前文1.1.3节最后，给出了相邻时刻收益的递归关系
  $$G_t=R_{t+1}+\gamma G_{t+1}$$
  注意到价值函数 $v_{\pi }(S_t),q_{\pi }(S_t,A_t)$ 和 $v_{\pi }(S_{t+1}),q_{\pi }(S_{t+1},A_{t+1})$ 分别是 $G_t,G_{t+1}$ 的期望值，依此我们可以建立相邻时刻价值函数的递归关系

5.2.1.1 两种贝尔曼等式

1. 相邻时刻状态价值函数 $v_{\pi }$ 间的Bellman等式
   $$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|s]\\ & =\sum _a\pi (a|s)[r(s,a)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s,a)v_{\pi }(s^{\prime })]\end{array}$$
   也可使用四参数状态转移函数表示
   $$\begin{array}{rl}{v}_{\pi }(s)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$
   用回溯图表示：
   
2. 相邻时刻状态价值函数 $v_{\pi }$ 间的Bellman等式
   $$\begin{array}{rl}{q}_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|s,a]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|s,a]\\ & =r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\sum _a\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })\end{array}$$
   也可使用四参数状态转移函数表示
   $$\begin{array}{rl}{q}_{\pi }(s,a)& ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})|s,a]\\ & =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })]\end{array}$$
   用回溯图表示：
   

• 说明：
  1. 以上所有bellman等式都可以分成两部分，$r$ 代表当前状态的立即奖励，后半边可以看做未来奖励的加权和
  2. bellman等式满足递归特性，即 这一步的收益期望 = 这一步奖励 + 下一步的收益期望，可以写成递归矩阵形式，知道了下一步所有可能的 $v(s^{\prime }),q(s^{\prime },a^{\prime })$，即可解出当前状态的 $v(s),q(s,a)$，这种将后继状态的价值信息回传给当前时刻状态（或 “状态-动作” 二元组）的操作称为 回溯操作
  3. 当固定策略 $\pi (a|s)$ 时，价值函数 $v_{\pi }$ 和 $q_{\pi }$ 是bellman方程的唯一解。上面给出了许多 回溯图，它们描述的 回溯关系 是回溯操作的基础。（注：与状态转移图不同，回溯图中的状态节点不需要彼此不同，某个状态的后继状态扔是其本身）

5.2.1.2 策略评估

• 策略评估(prediction)要求我们根据给定的策略 $\pi$ 计算价值函数 $v_{\pi }(s)$ 。这是RL中的一个核心问题，形式化地讲：
  1. 输入：MDP $<S,A,P,R,\gamma >$ 及 Policy $\pi$ （或 MRP $<S,P^{\pi },R^{\pi },\gamma >$）
  2. 输出：价值函数 $v_{\pi }(s)$ 或 $q_{\pi }(s,a)$
• 环境给定了状态状态矩阵 $p$ 和奖励函数 $r$，当策略 $\pi$ 固定时，bellman方程中的未知量就只有价值向量 $v\text{v}v$ 或 $q\text{q}q$，这时每个 $s$ 或 $(s,a)$ 对应一个方程，整体是可解的。虽然理论上可以直接显式地解出 $v_{\pi }(s)$ 或 $q_{\pi }(s,a)$，但这样做复杂度很高，通常我们使用迭代法进行求解。这部分将在下一篇文章详细分析

5.2.2 贝尔曼最优等式（Bellman optimal equation）

5.2.2.1 最优策略与最优价值函数

• 解决一个强化学习问题，意味着找出一个策略，使其能在长期过程中获得大量收益。在RL中，“更好” 意味着获取的收益更大，对于有限MDP，我们可以通过比较价值函数定义策略间的偏序关系
  $$策略\pi 优于策略{\pi }^{\prime }?v_{\pi }(s)\ge v_{\pi ‘}(s),s\in \mathcal{S}是\pi 覆盖的状态$$
  可见，较好的策略意味着在所有状态下都有更高的期望收益。因此，给出以下定义
  1. 最优状态价值函数（$v_{?}$）：对于任意状态 $s\in \mathcal{S}$，
     $$v_{?}(s)?\underset{\pi }{\max }{v}_{\pi }(s)$$
  2. 最优策略（${\pi }_{?}$）：使得任意状态 $s\in \mathcal{S}$ 下期望收益（价值）为 $v_{?}(s)$ 的策略称为最优策略
  3. 最优状态动作价值函数（$q_{?}$）：对于任意状态 $s\in \mathcal{S}$，动作 $a\in \mathcal{A}$，
     $$q_{?}(s,a)?\underset{\pi }{\max }{q}_{\pi }(s,a)$$
     注意，$q_{?}$ 给出了在状态 $s$ 下，先采取动作 $a$，之后按照最优策略去决策的的期望收益（在 $s$ 选择 $a$ 不一定是 ${\pi }_{?}$ 控制的），可以用 ${\pi }_{?}$ 表示 $q_{?}$
     $$q_{?}(s,a)=\mathbb{E}[R_{t+1}+\gamma v_{?}(S_{t+1})|S_t=s,A_t=a]$$
• 示例：现有MDP如下所示，在顶部状态下，只有left和right两个可选动作，线上数值代表执行动作后获取的固定收益。判断在 $\gamma =0、0.9、0.5$ 时，哪个策略最优
  
  对于${\pi }_{left}$，$G_{left}=1+{\gamma }^2+{\gamma }^4+...=\frac{1}{1?{\gamma }^2}$；对于${\pi }_{right}$，$G_{right}=0+2\gamma +2{\gamma }^3+...=\frac{2\gamma }{1?{\gamma }^2}$。因为左右都只有一条路回顶部状态，且每个环路仅一个非零奖励，因此顶部状态和左下（或右下）价值相等，分别带入3个 $\gamma$ 值，可知 $\gamma =0、0.9、0.5$ 时，较好策略为 “left，right，一样”

5.2.2.2 贝尔曼最优等式

• 因为 $v_{?}$ 和 $q_{?}$ 本质上也是价值函数，因此它们也要满足bellman等式的一致性条件，但因为它们是最优价值函数，所以它们的一致性条件可以以一种特殊的形式表示，而不拘泥与任何特定的策略。这就是bellman最优等式

  1. 相邻时刻状态价值函数 $v_{?}$ 间的Bellman optimal等式
     $$\begin{array}{rl}{v}_{?}(s)& =\underset{a\in \mathcal{A}(s)}{\max }{q}_{{\pi }_{?}}(s,a)\\ & =\underset{a}{\max }{\mathbb{E}}_{{\pi }_{?}}[G_t|S_t=s,A_t=a]\\ & =\underset{a}{\max }{\mathbb{E}}_{{\pi }_{?}}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]\\ & =\underset{a}{\max }\mathbb{E}[R_{t+1}+\gamma v_{?}(S_{t+1})|S_t=s,A_t=a]\\ & =\underset{a}{\max }\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{?}(s^{\prime })]\end{array}$$
     也可使用三参数状态转移函数表示
     $$v_{?}(s)=\underset{a}{\max }[r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{?}(s^{\prime })]$$
     用回溯图表示（弧线代表求 $\max$，没有弧线代表求期望）
     

  2. 相邻时刻状态价值函数 $q_{?}$ 间的Bellman optimal等式
     $$\begin{array}{rl}{q}_{?}(s,a)& =\max {\mathbb{E}}_{{\pi }_{?}}[G_t|S_t=s,A_t=a]\\ & =\max {\mathbb{E}}_{{\pi }_{?}}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]\\ & =\mathbb{E}[R_{t+1}+\gamma \underset{a^{\prime }}{\max }{q}_{?}(S_{t+1},a^{\prime })|S_t=s,A_t=a]\\ & =\sum _{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{\max }{q}_{?}(s^{\prime },a^{\prime })]\end{array}$$
     也可使用三参数状态转移函数表示
     $$q_{?}(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)\underset{a^{\prime }}{\max }q(s^{\prime },a^{\prime })$$
     用回溯图表示（弧线代表求 $\max$，没有弧线代表求期望）
     

• 也可以从另一个角度推导，根据bellman等式，${\pi }_{?}$ 和 $q_{?}$ 的关系如下
  $$?\begin{array}{rl}& v_{?}(s)=\underset{a\in \mathcal{A}}{\max }{q}_{?}(s,a)\\ & q_{?}(s,a)=r(s,a)+\gamma \sum _{s^{\prime }}p(s^{\prime }|s,a)v_{?}(s^{\prime })=\sum _{s^{\prime },r}p(s^{\prime },r,|s,a)[r+\gamma v_{?}(s^{\prime })]\end{array}$$
  这两个相互带入即得bellman optimal equation

5.3 从最优价值函数到最优策略

1. 从 $v_{?}$ 到 ${\pi }_{?}$
   • ${\pi }_{?}$ 是能够最大化交互期望收益的策略，因此智能体应当始终朝向能获取更大期望收益（$v_{?}(s)$更大）的状态移动。因此，对于 $v_{?}$ 来说，任何贪心策略都是最优策略。
   • $v_{?}$ 让人最感兴趣的地方是，使用它来评估动作的短期结果（准确说是单步结果）时，从长期来看贪心策略也是最优的，这是由于 $v_{?}$ 本身已经包含了未来所有可能的行为产生的回报影响。定义 $v_{?}$ 的意义就在于。可以将最优的长期（全局）收益期望值转化为每个状态对应的一个当前局部量的计算。因此一次单步搜索就可以产生长期（或者说全局）最优的动作序列
2. 从 $q_{?}$ 到 ${\pi }_{?}$
   • 在给定 $q_{?}$ 的情况下，选择最优动作的过程变得更加简单，甚至不需要进行单步搜索过程，只要找到使得 $q_{?}(s,a)$ 最大化的动作 $a$ 即可
     π ? ( a ∣ s ) = 1 { a = arg?max ? α q ? ( s , α ) } ∑ a 1 { a = arg?max ? α q ? ( s , α ) } \pi_*(a|s) = \frac{1\{a=\argmax_{\alpha}q_*(s,\alpha)\}}{\sum_a1\{a=\argmax_{\alpha}q_*(s,\alpha)\}} π??(a∣s)=∑a?1{a=αargmax?q??(s,α)}1{a=αargmax?q??(s,α)}?
   • 动作价值函数有效地保存着所有单步搜索的结果。它将最优的长期受益的期望值表达为对每个 $(s,a)$ 二元组的一个当前局部量。因此，将价值函数表达为 $(s,a)$ 二元组的函数而非 $s$ 的函数后， 最优动作的选取就不再需要知道后继状态和其对应的价值了，也就是说，不再需要知道任何环境的动态变化特性了（即动态函数$p$）

5.4 最优性和近似算法

• 显式求解bellman optimal equation给出了一个找 ${\pi }_{?}$ 的方法（即RL问题的一种解法），但是这个方法很少是直接有效的。我们要预估所有的可能性，计算每种可能性出现的概率即期望收益，这种解法至少依赖于三条很强的假设

  1. 需要准确知道环境的动态变化特性（$p$ 和 $r$）
  2. 有足够的计算资源
  3. 马尔可夫性

  尽管（1）和（3）在RL问题设定常常满足，但是一旦状态集或动作集太大，计算 $v$ 或 $q$ 的任务需要耗费巨量的计算资源，（2）常常无法满足。因此RL中，我们通常只能用近似解法来处理。

• 存储容量也是一个重要的约束，价值函数、策略和模型的估计通常需要大量的存储空间。在状态集小而有限的任务中，常用数组或表格来估计每个状态（或 “状态-动作” 二元组）的价值，我们称之为**表格型任务**，对应的方法称为 表格型方法。但在许多情况下（比如连续情况），状态数量无限可分，不能用表格存储。这时通常使用紧凑的参数化函数表示法

• 强化学习在线运行的本质，使得它在近似最优策略的过程中，对于那些经常出现的状态集合会花更多的努力去学习好的决策，而代价就是对不经常出现的状态学习力度不够。这是区别强化学习方法和其他解决MDP问题方法的一个重要判断依据

6. 小结