从零开始强化学习（二）——马尔可夫决策过程

2022-06-23 本文已影响0人晓柒NLP与药物设计

二. 马尔可夫决策过程(Markov Decision Processes, MDP)

2.1 马尔可夫性质(Markov Property)

如果一个状态转移是符合马尔可夫的，那就是说一个状态的下一个状态只取决于它当前状态，而跟它当前状态之前的状态都没有关系

假设状态的历史为 $h_t=\{s_{1},s_{2},s_{3},...,s_{t}\}$ ， $h_t$ 包含了之前的所有状态，如果一个状态转移是符合马尔可夫的，也就是满足如下条件：

$p\left(s_{t+1} \mid s_{t}\right) =p\left(s_{t+1} \mid h_{t}\right)\\ p\left(s_{t+1} \mid s_{t}, a_{t}\right) =p\left(s_{t+1} \mid h_{t}, a_{t}\right)$

从当前 $s_t$ 转移到 $s_{t+1}$ 这个状态，它是直接就等于它之前所有的状态转移到 $s_{t+1}$ 。如果某一个过程满足马尔可夫性质(Markov Property)，就是说未来的转移跟过去是独立的，它只取决于现在。马尔可夫性质是所有马尔可夫过程的基础。

2.2 马尔可夫过程/马尔可夫链(Markov Process/Markov Chain)

通俗地说，马尔科夫过程是一个无记忆的随机过程。例如，如具有马尔可夫性质的随机状态序列 $S_1,S_2,...$ ，称为马尔科夫过程又称为马尔科夫链，可以用一个元组 $<S,P>$ 表示，其中:

$S$ ：有限数量的状态集
$P$ ：状态转移概率矩阵

可以用状态转移矩阵(State Transition Matrix) $P\$ 来描述状态转移 $\ p\left(s_{t+1}=s^{\prime} \mid s_{t}=s\right)$ ，如下式所示。
$P=\left[\begin{array}{cccc} P\left(s_{1} \mid s_{1}\right) & P\left(s_{2} \mid s_{1}\right) & \ldots & P\left(s_{N} \mid s_{1}\right) \\ P\left(s_{1} \mid s_{2}\right) & P\left(s_{2} \mid s_{2}\right) & \ldots & P\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ P\left(s_{1} \mid s_{N}\right) & P\left(s_{2} \mid s_{N}\right) & \ldots & P\left(s_{N} \mid s_{N}\right) \end{array}\right]$
状态转移矩阵类似于一个conditional probability，若知道当前在 $s_t$ 这个状态过后到达下面所有状态的一个概念，所以它每一行其实描述了是从一个节点到达所有其它节点的概率

2.3 马尔可夫奖励过程原理(Markov Reward Process)

2.3.1 概念及基本原理

马尔科夫奖励过程在马尔科夫过程的基础上增加了奖励R和折扣系数 $\gamma$ ，马尔科夫奖励过程是一个元组 $<S,P,R,\gamma>$ ，其中：

$S$ ：有限数量的状态集
$P$ ：状态转移概率矩阵
$R$ ：奖励函数， $R_{s}=\mathbb{E}[R_{t+1}|S_{t}=s]$
$\gamma\$ ：折扣因子, $\gamma\in[0,1]$

下图是一个马尔可夫奖励过程的示例，在马尔科夫过程的基础上针对每一个状态增加了相应的奖励，这里没有给定折扣因子，在实际应用中，可以根据具体问题，选择一个折扣因子

2.3.2 奖励函数(Reward Function)

$R\$ 是一个奖励函数。在当前状态 $S_t$ 下,执行动作 $a_t$ ,进入到下一个时刻(t+1)能获得的奖励期望。 $R\$ 约定为离开该状态获得的奖励，而不是进入该状态获得的奖励，即 $S_t$ 对应奖励为 $R_{t+1}$ 。因为状态是从 $S_0$ 开始的，Agent未采取动作之前，环境有一个初始状态。 $S_0$ 的奖励为离开 $S_0$ 的奖励，离开 $S_0$ 后进入下一个状态。如下图所示，离开状态 $S_t$ ，环境更新状态，进入到t+1时刻

2.3.3 折扣因子(Discount Factor)

在大部分马尔可夫奖励过程和马尔可夫决策过程中，都引入折扣因子 $\gamma\in[0,1]$ ，主要原因如下：

首先，数学上的方便表示，在带环的马尔可夫过程中，可以避免陷入无限循环，达到收敛
其次，随着时间的推移，远期利益的不确定性越来越大，符合人类对于眼前利益的追求
再次，在金融等领域的具体问题上，近期的奖励可能比远期的奖励获得更多的利息，越早获得奖励，收益越高

$\gamma\$ 可以作为强化学习Agent的一个超参数来进行调整，然后就会得到不同行为的Agent

2.3.4 回报(Return)

Return说的是把奖励进行折扣后所获得的收益。Return可以定义为奖励的逐步叠加，如下式所示：
$G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\ldots+\gamma^{T-t-1} R_{T}$
这里有一个叠加系数，越往后得到的奖励，折扣得越多。这说明其实更希望得到现有的奖励，未来的奖励就要把它打折扣

2.3.5 价值函数(Value Function)

状态价值函数(state-value function)的定义：马尔可奖励过程的状态价值函数 $V(s)$ 是从该状态 $s$ 开始的回报的期望，即：
$\begin{aligned} V_{t}(s) &=\mathbb{E}\left[G_{t} \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots+\gamma^{T-t-1} R_{T} \mid s_{t}=s\right] \end{aligned}$
$G_t$ 是之前定义的Discounted Return，这里取了一个期望，期望就是说从这个状态开始，有可能获得多大的价值。所以这个期望也可以看成是对未来可能获得奖励的当前价值的一个表现，就是当进入某一个状态过后，现在就有多大的价值

2.3.6 MRP的贝尔曼方程(Bellman Equation for MRPs)

状态的价值函数可以分解成两部分，如下：

该状态的即时奖励 $R_{t+1}$
带折扣的该状态的后续状态的价值函数

Bellman equation 的推导过程如下：
$\begin{aligned} V(s)&=\mathbb{E}\left[G_{t} \mid s_{t}=s\right]\\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s\right] \\ &=\mathbb{E}\left[R_{t+1}|s_t=s\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s\right]\\ &=R(s)+\gamma \mathbb{E}[G_{t+1}|s_t=s] \\ &=R(s)+\gamma \mathbb{E}[V(s_{t+1})|s_t=s]\\ &=R(s)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right) V\left(s^{\prime}\right) \end{aligned}$

Bellman Equation就是当前状态与未来状态的迭代关系，表示当前状态的值函数可以通过下个状态的值函数来计算，因其提出者、动态规划创始人Richard Bellman而得名，也叫作动态规划方程

Bellman Equation定义的就是当前状态跟未来状态的一个迭代的关系，如下式所示：
$V(s)=R(s)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s\right)$
可以把Bellman Equation写成一种矩阵的形式，如下式所示：
$\left[\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right]=\left[\begin{array}{c} R\left(s_{1}\right) \\ R\left(s_{2}\right) \\ \vdots \\ R\left(s_{N}\right) \end{array}\right]+\gamma\left[\begin{array}{cccc} P\left(s_{1} \mid s_{1}\right) & P\left(s_{2} \mid s_{1}\right) & \ldots & P\left(s_{N} \mid s_{1}\right) \\ P\left(s_{1} \mid s_{2}\right) & P\left(s_{2} \mid s_{2}\right) & \ldots & P\left(s_{N} \mid s_{2}\right) \\ \vdots & \vdots & \ddots & \vdots \\ P\left(s_{1} \mid s_{N}\right) & P\left(s_{2} \mid s_{N}\right) & \ldots & P\left(s_{N} \mid s_{N}\right) \end{array}\right]\left[\begin{array}{c} V\left(s_{1}\right) \\ V\left(s_{2}\right) \\ \vdots \\ V\left(s_{N}\right) \end{array}\right]$
首先有这个转移矩阵，当前这个状态是一个向量 $[V(s_1),V(s_2),\cdots,V(s_N)]^T$ 。可以写成迭代的形式。每一行来看的话， $V$ 这个向量乘以了转移矩阵里面的某一行，再加上它当前可以得到的reward，就会得到它当前的价值。

当把Bellman Equation写成矩阵形式后，可以直接求解：
$\begin{aligned} V &= R+ \gamma PV \\ IV &= R+ \gamma PV \\ (I-\gamma P)V &=R \\ V&=(I-\gamma P)^{-1}R \end{aligned}$
可以直接得到一个解析解(analytic solution):
$V=(I-\gamma P)^{-1} R$
可以通过矩阵求逆把 $V$ 的价值直接求出来。但是矩阵求逆的过程的复杂度是 $O(N^3)$ ，所以这种通过解析解去求解的方法只适用于很小量的MRP。状态空间规模大的MRP的求解通常使用迭代法。常用的迭代方法有：动态规划(Dynamic Programming)、蒙特卡洛评估(Monte-Carlo evaluation)、时序差分学(Temporal-Difference)等

2.4 马尔可夫决策过程(Markov Decision Process)

马尔可夫决策过程是在马尔可夫奖励过程的基础上加入了决策，即增加了动作，马尔科夫决策过程是一个元组 $<S,A,P,R,\gamma>$ ，其定义为：

$S$ ：有限数量的状态集
$A$ ：有限数量的动作集
$P$ ：状态转移概率矩阵， $\mathcal{P}^a_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s,A_t=a]$
$R$ ：奖励函数， $R^a_{s}=\mathbb{E}[R_{t+1}|S_{t}=s,A_t=a]$
$\gamma\$ ：折扣因子, $\gamma\in[0,1]$

从上面定义可以看出，马尔可夫决策过程的状态转移概率和奖励函数不仅取决于Agent当前状态 $s$ ，还取决于智能体选取的动作 $a$ ，而马尔可夫奖励过程仅取决于当前状态

2.4.1 策略(Policy)

定义：策略 $\pi$ 是给定状态时，关于动作 $a$ 的分布，即：
$\pi(a|s)=\mathbb{P}[A_T=a|S_T=s]$
一个策略 $\pi$ 完整地定义了Agent的行为方式，即策略 $\pi$ 定义了Agent在各种状态下可能采取的动作 $a$ ，以及在各种状态下采取各种动作的概率。MDP的策略仅与当前的状态有关，与历史信息无关；同时某一确定的策略是静态的，与时间无关；但是个体可以随着时间更新策略

当给定一个 $MDP=<S,A,P,R,\gamma>$ 和一个策略 $\pi$ 时，状态序列 $S_1,S_2,...$ 是一个马尔科夫过程 $<S,P^\pi>$ ；同样，状态和奖励序列 $S_1,R_1,S_2,...$ 是一个马尔科夫奖励过程 $<S,P^\pi,R^\pi,\gamma>$ ，并且在这个奖励过程中满足下面方程：

$P^π_{(s′|s)}=\sum_{a∈A}π(a|s)P^a_{s′|s}$
对于这个奖励函数，把action拿掉，这样就会得到一个类似于MRP的奖励函数：
$R^π_{s}=\sum_{a∈A}π(a|s)R^a_{s}$
从上面两个方程可知，已知马尔可夫决策过程和策略 $\pi$ ，可以把马尔可夫决策过程转换成马尔可夫奖励过程。在马尔可夫决策过程中，状态转移函数 $P^a_{s′∣s}$ 基于当前的状态以及当前的动作。而策略 $π(a|s)$ 是给定状态时，关于动作 $a$ 的分布且已知。可以通过策略求关于状态 $s$ 的边缘分布，从而状态转移函数和奖励函数都变为只关于状态的函数

2.4.2 价值函数(Value Function)

定义：MDP的状态价值函数(state-value Function) $v_\pi(s)$ ，是从状态 $s$ 开始，执行策略所获得的收获的期望；或者说在执行当前策略 $\pi$ 时，衡量智能体处在状态 $s$ 时的价值大小。数学定义如下：
$v_π(s)=\mathbb{E}_π[G_t∣S_t=s]$
定义: 行为价值函数(action-value function) $Q_\pi(s,a)$ ，是从状态 $s$ 开始，采取动作 $a$ , 执行策略所获得的收获的期望；或者说在遵循当前策略 $\pi$ 时，衡量对当前状态执行动作 $a$ 的价值大小。行为价值函数一般都是与某一特定的状态相对应的，更精细的描述是状态行为对的价值函数。行为价值函数的数学定义如下：
$Q_π(s,a)=\mathbb{E}_π[G_t∣S_t=s,A_t=a]$
$V$ 和 $Q$ 的关系：状态价值函数 $v_π(s)$ 可以通过行为价值函数 $Q_π(s,a)$ 来定义，状态价值函数定义为行为价值函数关于动作 $a$ 的期望，数学描述为：
$v_π(s)=\mathbb{E}_{a～\pi(a|s)}[Q_\pi(s,a)]=\sum_{a\in A}\pi(a|s)Q_\pi(s,a)$
行为价值函数 $Q_\pi(s,a)$ 描述的是状态 $s$ 时，采取动作 $a$ 的价值函数，是状态-动作对 $(s,a)$ 的价值；而状态价值函数 $v_π(s)$ 是在状态 $s$ 时的价值函数。上式两者关系可以理解为， $v_π(s)$ 等于 $Q_\pi(s,a)$ ，在状态 $s$ 时，根据策略采取所有可能动作 $a$ 的平均性能动作 $\bar{a}$ 和状态 $s$ 的 $Q$ 值，即可以理解为 $v_π(s)=Q_\pi(s,\bar{a})$ ,所以 $v_π(s)$ 描述的是状态 $s$ 下，平均性能动作的价值，因此，只关注状态

2.4.3 贝尔曼期望方程(Bellman Expectation Equation)

通过对状态-价值函数进行一个分解，就可以得到一个类似于之前MRP的Bellman Equation，这里叫Bellman Expectation Equation，如下式所示：
$v_{\pi}(s)=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma v^{\pi}\left(S_{t+1}\right) \mid S_{t}=s\right]$
对于 $Q$ 函数，也可以做类似的分解，也可以得到Q函数的 Bellman Expectation Equation，如下式所示：
$Q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, A_{t+1}\right) \mid S_{t}=s, A_{t}=a\right]$
此处给出 $Q$ 函数的Bellman equation：
$\begin{aligned} q(s,a)&=\mathbb{E}\left[G_{t} \mid s_{t}=s,a_{t}=a\right]\\ &=\mathbb{E}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\ldots \mid s_{t}=s,a_{t}=a\right] \\ &=\mathbb{E}\left[R_{t+1}|s_{t}=s,a_{t}=a\right] +\gamma \mathbb{E}\left[R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\ldots \mid s_{t}=s,a_{t}=a\right]\\ &=R(s,a)+\gamma \mathbb{E}[G_{t+1}|s_{t}=s,a_{t}=a] \\ &=R(s,a)+\gamma \mathbb{E}[V(s_{t+1})|s_{t}=s,a_{t}=a]\\ &=R(s,a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime} \mid s,a\right) V\left(s^{\prime}\right) \end{aligned}$
根据上式推导：
$Q_\pi(s,a)=R(s,a)+\gamma\sum_{s'\in S}P(s'|s,a)V_\pi(s')$
根据上一小节给出的关系：
$v_π(s)=\sum_{a∈A}π(a|s)Q_π(s,a)$
带入得：
$v_{\pi}(s)=\sum_{a \in A} \pi(a|s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right) v_{\pi}\left(s^{\prime}\right)\right)\\ Q_{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right) \sum_{a\in A}\pi\left(a^{\prime}|s^{\prime}\right)Q_{\pi}\left(s^{\prime}, a^{\prime}\right)$

2.4.4 备份图(Backup Diagram)

backup类似于bootstrapping之间这个迭代关系，就对于某一个状态，它的当前价值是跟它的未来价值线性相关的

把上面这样的图称为backup diagram(备份图)，因为它们图示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将价值信息从一个状态（或状态-动作对）的后继状态（或状态-动作对）转移回它。每一个空心圆圈代表一个状态，每一个实心圆圈代表一个状态-动作对：
$v_{\pi}(s)=\sum_{a \in A} \pi(a|s)\left(R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right) v_{\pi}\left(s^{\prime}\right)\right)\\ Q_{\pi}(s, a)=R(s, a)+\gamma \sum_{s^{\prime} \in S} P\left(s^{\prime}|s, a\right) \sum_{a\in A}\pi\left(a^{\prime}|s^{\prime}\right)Q_{\pi}\left(s^{\prime}, a^{\prime}\right)$
如上式所示，这里有两层加和：

第一层加和就是这个叶子节点，往上走一层的话，就可以把未来的价值( $s'$ 的价值) backup到黑色的节点
第二层加和是对action进行加和。得到黑色节点的价值过后，再往上backup一层，就会推到根节点的价值，即当前状态的价值

所以backup diagram定义了未来下一时刻的状态-价值函数跟上一时刻的状态-价值函数之间的关联

MDP的贝尔曼期望方程的矩阵形式可以通过MRP的贝尔曼方程的的矩阵形式推导而来，其实就是增加了策略：
$V_\pi=R^\pi+\gamma P^\pi V_\pi$
其解析解(analytic solution)为：

$V_\pi=(I-\gamma P^\pi)^{-1}R^\pi$

2.4.5 最优价值函数(Optimal Value Function)

最优价值函数最优状态价值函数 $V_*(s)$ 指的是从策略产生的所有状态价值函数中，选取使得状态 $s$ 价值最大的函数：
$v_*=\underset{\pi}{\operatorname{max}}V_\pi(s)$
类似的，最优行为价值函数 $Q_*(s,a)$ 指的是从策略产生的所有行为价值函数中，选取使得状态动作对 $<s,a>$ 价值最大的函数：
$Q_*(s,a)=\underset{\pi}{\operatorname{max}}Q_\pi(s,a)$
最优价值函数具体明确了MDP的最优可能表现，当知道了最优价值函数，也就知道了每个状态的最优价值，也就是解决了MDP问题，基于价值的方法给出的状态价值就是最优价值，也就隐式地给出了策略

2.4.6 最优策略(Optimal Policy)

定义关于策略的偏序(partial ordering)：当对于任何状态 $s$ ，遵循策略 $\pi$ 的状态价值大于等于遵循策略 $\pi'$ 的状态价值，则策略 $\pi$ 优于策略 $\pi'$ ，即：
$\pi\geq\pi',if\ v_\pi(s)\geq v_{\pi'}(s),\forall s$
定理: 对于任何MDP，有下面性质：

存在一个最优策略，比任何其他策略更好或至少相等 $\pi_*\geq\pi;\forall \pi$
所有的最优策略有相同的最优价值函数 $v_{\pi *}(s)=v_*(s)$
所有的最优策略具有相同的行为价值函数 $Q_\pi(s,a)=Q_*(s,a)$

可以通过最大化最优行为价值函数来找到最优策略：
$\pi(a|s)= \begin{cases} 1\ \ \ \ if\ a=\underset{a\in A}{\operatorname{argmax}}Q_*(s,a)\\ 0\ \ \ \ otherwise \end{cases}$
对于任何MDP问题，一定存在一个最优的且是确定的策略，但这并不意味着只有确定策略是最优的。也可以是随机策略是最优的，比如在某个状态 $s$ 时，有两个动作 $a1,a2$ 有相同的Q值,可以随机选择其中之一。另外，如果知道最优行为价值函数，则通过最优 $Q$ 值可以找到最优策略,即上式中采取使得最优Q值最大的动作

2.4.7 贝尔曼最优方程(Bellman Optimality Equation)

$V^*$ 的贝尔曼最优方程：
- 一个状态的最优价值等于从该状态出发采取的所有动作产生的动作价值中最大的那个动作价值： $V_*(s)=\underset{a}{\operatorname{max}}Q_*(s,a)$

$Q^*$ 的贝尔曼最优方程：
- 在某个状态 $s$ 下，采取某个动作的最优动作价值由两部分组成，一部分是离开状态 $s$ 的即时奖励，另一部分则是所有能到达的后续状态 $s’$ 的最优状态价值与相应的转移概率的乘积后求和: $Q_*(s,a)=R(s,a)+\gamma\sum\limits_{s'\in S}P(s'|s,a)V_*(s')$

贝尔曼最优方程的求解是非线性的，通常没有闭式解，但可以通过一些迭代方法来求解：价值迭代、策略迭代、Q-learning、Sarsa等

2.4.8 代码演示

nan=np.nan      #  代表不可能的动作 
T = np.array([  #  shape=[s, a, s']        
    [[0.7, 0.3, 0.0], [1.0, 0.0, 0.0], [0.8, 0.2, 0.0]],
    [[0.0, 1.0, 0.0], [nan, nan, nan], [0.0, 0.0, 1.0]],       
    [[nan, nan, nan], [0.8, 0.1, 0.1], [nan, nan, nan]],]) 
R = np.array([  #  shape=[s, a, s']        
    [[10., 0.0, 0.0], [0.0, 0.0, 0.0], [0.0, 0.0, 0.0]],        
    [[10., 0.0, 0.0], [nan, nan, nan], [0.0, 0.0, -50.]],        
    [[nan, nan, nan], [40., 0.0, 0.0], [nan, nan, nan]],]) 
possible_actions = [[0, 1, 2], [0, 2], [1]]
# 运行Q值迭代算法
Q = np.full((3, 3), -np.inf)  #  -inf 对应着不可能的动作 
for state, actions in enumerate(possible_actions):    
    Q[state, actions] = 0.0   #  对所有可能的动作初始化为0.0
learning_rate = 0.01 
discount_rate = 0.95 
n_iterations = 100
for iteration in range(n_iterations):   
    Q_prev = Q.copy()    
    for s in range(3):        
        for a in possible_actions[s]:            
            Q[s, a] = np.sum([T[s, a, sp] * (R[s, a, sp] + discount_rate * np.max(Q_prev[sp]))  
            for sp in range(3)])
# 结果Q值输出如下：
>>> Q 
array([ [ 21.89498982,  20.80024033,  16.86353093],       
        [  1.11669335,         -inf,   1.17573546],       
        [        -inf,  53.86946068,         -inf]]) 
>>> np.argmax(Q, axis=1)      #  每一状态的最优动作
array([0, 2, 1])