【强化学习】马尔可夫决策过程

前言

马尔科夫性

未来只与现在有关，与过去无关。

设 $\{X(t),t\in T\}$ 为一随机过程，$E$ 为其状态空间，若对任意的 $t_1<t_2<…<t_n<t$ ，任意的 $x_1,x_2,…,x_n,x\in E$ ，随机变量 $X(t)$ 在已知变量 $X(t_1)=x_1,…,X(t_n)=x_n$ 之下的条件分布函数只与 $X(t_n) = x_n$ 有关，而与 $X(t_1)=x_1,…,X(t_{n-1})=x_{n-1}$ 无关，即条件分布函数满足等式：

$$F(x,t|x_n,x_{n-1},...,x_2,x_1,t_n,t_{n-1},...,t_2,t_1)=F(x,t|x_n,t_n)$$

此性质被称为马尔科夫性，也称为无后效性或无记忆性。

若 $X(t)$ 为离散型随机变量，则马尔科夫性亦满足等式：

$$P\{X(t) = x|X(t_n) = x_n,...,X(t_1)=x_1\}=P\{X(t)=x|X(t_n)=x_n\}$$

具有马尔科夫性的随机过程 $\{X(t),t\in T\}$ 被称为马尔可夫过程。

具有马尔可夫性质的过程满足下列公式：

$$P(S_{t+1}|S_t)=P(S_{t+1}|S_1,...,S_t)$$

即：

• 某个给定的当前状态 $S_t$ ，其将来的状态 $S_{t+1}$ 与 $t$ 时刻之前的状态都已经没有关系。
• 状态 $S_t$ 包含了所有历史相关信息，或者说历史的所有状态的相关信息都在当前状态 $S_t$ 上体现出来，一旦 $S_t$ 知道了，那么 $S_1,S_2,…,S_{t-1}$ 都可以被抛弃。数学上可以认为：状态是将来的充分统计量（即凭借当前状态能够唯一的确定之后时刻的状态）。因此，这里要求环境全观测。

举个例子：比如说下围棋时，关注的只是当前的棋盘局面。

状态转移矩阵

状态转移概率：从一个马尔可夫状态 $s$ 跳转到后继状态 $s’$ 的概率（空心字母表示统计运算符）

$$\mathcal{P}_{ss'}=\mathbb{P}[S_{t+1}=s'|S_t=s]$$

将所有的状态 $s$ 组成行，后继状态 $s’$ 组成列，得到状态转移矩阵：

$$\mathcal{P}=\begin{bmatrix} \mathcal{P}_{11} & \cdots & \mathcal{P}_{1n} \\ \vdots & \ddots & \vdots \\ \mathcal{P}_{n1} & \cdots & \mathcal{P}_{nn} \end{bmatrix}$$

其中：

• n 表示状态的个数
• $\mathcal{P}$ 代表整个状态转移的集合

• 每行元素相加等于 1

  当状态数量太多或者是无穷多状态（连续状态）时，更适合使用状态转移函数，此时有

  $$\int_{s'}\mathcal{P}(s'|s)=1$$

片段（episode）

强化学习中，从初始状态 $S_1$ 到终止状态 $S_T$ 的序列过程，被称为一个片段：$S_1,S_2,…,S_T$ 。

如果一个任务总以终止状态结束那么这个任务被称为片段任务（episodic task）。

如果一个任务没有终止状态，会被无限执行下去，这被称为连续性任务（continuing task）。

马尔可夫过程

若随机过程 $\{X(t),t\in T\}$ 满足马尔科夫性，则称为马尔可夫过程。

一个马尔可夫过程是一个无记忆的随机过程（我的理解：无记忆，就是说只需要知道当前状态，而不需要模型去记忆历史状态；随机过程即概率论的知识，即从当前状态转移到哪一个新状态是随机的，与转移矩阵不矛盾）。

马尔可夫过程可以由一个二元组来定义：$$，其中，$S$ 代表了状态的集合，$\mathcal{P}$ 描述了状态转移矩阵：$\mathcal{P}_{ss’}=\mathbb{P}[S_{t+1}=s’|S_t=s]$ 。

有时我们并不知道 $\mathcal{P}$ 的具体值，但我们假设 $\mathcal{P}$ 是存在且稳定的；当 $\mathcal{P}$ 不稳定时，意味着模型需要从新的环境中获取信息，更新状态转移矩阵，这时就涉及到在线学习了。

马尔科夫链

即状态空间为可数集的马尔可夫过程。

生成模式（Generating Patterns）

确定性模式（Deterministic Patterns）：确定性系统

举例：交通信号灯：红-绿-黄-红……

已知当前状态是绿色，那么下一个状态一定是黄色。也就是说，该系统是确定的。

非确定性模式（Non-deterministic patterns）：马尔可夫

例如：预测天气。

马尔科夫假设：假设模型的当前状态仅仅依赖于前面的几个状态。

虽然在将模型简化为马尔可夫过程的时候，忽略了一些环境中的重要因素（此例子中包括风力、气压等等），但是这样简化的模型易于求解，所以我们通常接受这样的模型假设。

n 阶马尔可夫模型：下一个状态选择取决于前 n 个状态。

最简单的马尔可夫过程是一阶模型，其状态选择仅与前一个状态有关。对于有 M 个状态的一阶马尔可夫模型，共有 $M^2$ 个状态转移，每个状态转移都有一个概率值，称为状态转移概率。这样的 $M^2$ 个概率也可以用一个状态转移矩阵来表示，注意这些概率并不随着时间的变化而变化（非常重要但有时不符合实际的假设）。

隐藏模式（Hidden Patterns）：隐马尔可夫

没懂，暂时不需要，占坑。

马尔可夫决策过程

完全可观测：个体能够直接观测得到所有需要的环境状态。在这种条件下，个体对环境的观测=个体状态=环境状态。

MDP 是对完全可观测（Fully observable）的环境进行描述的，即观测到的状态内容完整的决定了决策需要的特征；几乎所有的强化学习问题都可以转化为 MDP。

马尔可夫奖励过程

定义

是一个带有价值的马尔可夫过程，可以表示为 $\{S,\mathcal{P},\mathcal{R},\gamma\}$ ，其中：

• S 为有限状态的集合
• P 为状态转移矩阵
• R 为奖励函数，描述了在状态 s 时的奖励，$\mathcal{R}_s=E[R_{t+1}|S_t=s]$
• $\gamma$ 为衰减系数

这里的奖励函数为什么是 $R_{t+1}$ 起初不是很理解，在查了资料之后，我的理解如下：广义上的期望指的是均值，也就是说这个值在模型中应该是事先通过各种测量和观察得到的给定的值，而不是在模型中进行计算的（问问老师）。

而这里取 $R_{t+1}$ 的理由，可以理解为是一个约定，指的是离开状态 $S_t=s$ 能够获得的立即奖励。

回报（收获）$G_{t}$

$G_t$ 是从时间序列 $t$ 开始所有的折扣回报（乘以 $\gamma$ ）

• 针对连续性任务而言（无穷个状态），$G_t=R_{t+1} +\gamma R_{t+2}+…=\sum_{k=0}^\infin \gamma^kR_{t+k+1}$
• 针对片段性任务而言（有限个状态），$G_t=R_{t+1} +\gamma R_{t+2}+…+\gamma^{T-t-1}R_T=\sum_{k=0}^{T-t-1}\gamma^kR_{t+k+1}$

上述片段性任务的终止状态是时间到达 T。

奖励和回报的不同：奖励是针对状态的，即转移到下一个状态会得到的奖励；回报是立足现在对未来某种状态序列的评估，是从 t 时刻开始往后所有的奖励的有衰减的收益总和，是针对一个片段的。

由于无法穷尽所有可能的序列，所以并不能精确算出所有 $G_t$。

状态价值函数

是从状态 s 开始的回报的期望值：$v(s)=E[G_t|S_t=s]$

贝尔曼方程

公式及推导：

$$\begin{aligned} v(s)&=E[G_t|S_t=s] \\&=E[R_{t+1}+\gamma G_{t+1}|S_t=s] \\&=E[R_{t+1}|S_t=s]+E[\gamma G_{t+1}|S_t=s] \\&=R_{t+1}+\gamma v(S_{t+1}) \\&=E[R_{t+1}|S_t=s]+E[\gamma v(S_{t+1})|S_t=s] \\&=E[R_{t+1}+\gamma v(S_{t+1})|S_t=s] \end{aligned}$$

去掉期望：假设下一个状态是 $s’$，即 $s’=S_{t+1}$，那么有：

$$\begin{aligned} v(s)&=E[R_{t+1}+\gamma v(s')|S_t=s] \\&=R_s+\gamma \sum_{s'\in S}P_{ss'}v(s') \end{aligned}$$

$R_s$ 指的是离开当前状态 $s$ 所获得的奖励。

对于大规模的 MRP 问题，通常采用动态规划、蒙特卡洛估计等等方法来迭代求解。

收获和价值的计算（例子）

在马尔可夫过程上，添加了对每一个状态的奖励：

可以将图中给出的条件表示成下面的矩阵形式：

假设得到了下面4个马尔科夫链（四条达到终点的路径），假设 $\gamma=0.5$，出发点为 $C_1$，可以求出每条马尔可夫链的 G 值。

再举个计算状态价值函数的例子：（$\gamma = 1$）

在状态class3处的状态值函数计算就非常简单了。这里还是需要说明：其实一开始计算时候0.8肯定是不存在的，实际计算可以采用迭代法，一开始任意初始化，后面学习更新即可，这就是所谓的值迭代法。当然对于这个问题，可以采用下面的方法直接求解。

Bellman方程的矩阵形式和求解

将上述的不含期望的贝尔曼期望方程写成矩阵形式，可以看出它是一个线性方程，那么可以直接采用线性代数的方法求解，无需迭代。

求解后得到的结果是：$v=(I-\gamma P)^{-1}R$

实际上，计算复杂度是 $O(n^3)$，$n$ 是状态数量。因此直接求解仅适用于小规模的MRPs。大规模MRP的求解通常使用迭代法。常用的迭代方法有：动态规划（Dynamic Programming, DP）、蒙特卡洛评估（Monte-Carlo evaluation）、时序差分学习（Temporal-Difference, TD）。

马尔可夫决策过程

在之前的 MP 和 MRP 过程中，我们都只是处于观察者的角度，观察其中的状态转移现象，计算回报值，而对于一个 RL 问题，我们更希望决定状态改变的策略，来最大化回报值。

相比较于马尔可夫奖励过程，马尔可夫决策过程多了一个行为集合 A ，它是这样的一个元组：$<\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma>$ 。其中：

• S 是有限的状态集
• A 是有限的动作集
• P 是状态转移矩阵，$\mathcal{P}^a_{ss’}=P[S_{t+1}=s’|S_t=s,A_t=a]$ ，表示从状态 s 经过行为 a 转移到状态 s’ 的概率
• R 是奖励函数，$\mathcal{R}^a_s=E[R_{t+1}|S_t=s,A_t=a]$ ，描述了在状态 s 做动作 a 的奖励
• $\gamma$ 是衰减系数

可以看到，这里面的状态转移和奖励函数都不再仅仅对应于某个状态，也与具体的行为 a 有关。

示例

对比之前 MRP 中的图可以发现，奖励与动作对应了，同一个状态下采取不同的行为得到的奖励是不同的，即针对状态 s 的奖励变成了针对 $$ 的奖励。

在图中，当选择Pub（去查阅文献）这个动作时，主动进入了一个临时状态（黑色实心圆点），随后被动的被环境分配到另外三个状态，就是说此时 Agent 没有选择权来决定去哪个状态。

策略

策略 $\pi$ 是概率的集合，其元素 $\pi(a|s)$ 指的是，对过程中的某一状态 s 采取某个行为 a 的概率，即 $\pi(a|s)=P[A_t=a|S_t=s]$ 。

• 一个策略完整定义了个体的行为方式，也就是说定义了个体在各个状态下的各种可能的行为方式以及其概率的大小；
• 策略是RL问题的终极目标；
• 策略仅和当前的状态有关，与历史信息无关；
• 个体可以随着时间更新策略；
• 如果策略的概率分布输出都是独热的（one-hot，指一个向量只有一个元素为1，其他均为 0）的，那么称为确定性策略，否则即为随机策略。

当给定一个MDP：$\mathcal{M}=<\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma>$ 和一个策略 $\pi$ ，那么状态序列$S_1,S_2,…,S_n$ 是一个马尔可夫过程 $<\mathcal{S},\mathcal{P^{\pi}}>$ ；状态和奖励序列 $S_1,R_2,S_2,…$ 是一个 MRP：$\mathcal{M}=<\mathcal{S},\mathcal{P}^\pi,\mathcal{R}^\pi,\gamma>$ ，并且在这个奖励过程中满足下面两个方程：

$$\mathcal{P}^\pi_{ss'}=\sum_{a\in A}\pi(a|s)\mathcal{P}^a_{ss'}\\ \mathcal{R}^\pi_s=\sum_{a\in A}\pi(a|s)\mathcal{R}^a_s$$

文字描述如下：

• 状态转移：在执行策略 $\pi$ 时，状态从 s 转移至 s’ 的概率等于一系列概率的和，这一系列概率指的是在执行当前策略时，执行某一个行为的概率与该行为能使状态从 s 转移至 s’ 的概率的乘积。
• 奖励函数：当前状态 s 下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

策略在MDP中的作用相当于agent可以在某一个状态时做出选择，进而有形成各种马尔可夫过程的可能，而且基于策略产生的每一个马尔可夫过程是一个马尔可夫奖励过程，各过程之间的差别是不同的选择产生了不同的后续状态以及对应的不同的奖励。

基于策略 $\pi$ 的价值函数

状态价值函数

定义 $v_\pi(s)$ 是在 MDP 下的基于策略 $\pi$ 的状态价值函数，表示从状态 s 开始，遵循当前策略所获得的收获的期望；或者说在执行当前策略 $\pi$ 时，衡量个体处在状态 s 时的价值大小。数学表示如下：$v_\pi(s)=E_\pi[G_t|S_t=s]$ 。

行为价值函数

定义 $q_\pi(s,a)$ 为行为价值函数，表示在执行策略 $\pi$ 时，对当前状态 s 执行某一具体行为 a 所能获得的收获的期望；或者说在遵循当前策略 $\pi$ 时，衡量对当前状态执行行为 a 的价值大小。行为价值函数一般都是与某一特定的状态相互对应的。数学表示如下： $q_\pi(s,a)=E_\pi[G_t|S_t=s,A_t=a]$ 。

Bellman期望方程

用这个图可以更好的表示 v 和 q 之间的关系：

在图中，空心白色点表示状态，黑点表示动作，agent 有一定概率选择左边的点（假设是0.4），有一定概率选择右边的点（假设是0.6），这个概率是由策略 $\pi$ 决定的。而 $q_\pi(s,a)$ 表示的是执行一个具体动作后的 reward 值，所以 v 和 q 的关系就是：$v_\pi(s)=0.4\times q_\pi(s,a_1)+0.6\times q_\pi(s,a_2)$ 。

承接上一个图。在经过动作 a 之后，可能会转移到两种状态，而这样的改变就会产生一个奖励 R，然后到达 s’ 状态，这样就又回到了 $v_\pi(s’)$ 。

两个图连起来就是这样的

上图是对于v来说的，下图是对于q

综上所述，贝尔曼期望方程实质上刻画了后继状态 $s’$ 的状态价值函数 $v_\pi (s’)$ 与当前状态 s 的价值函数 $v_\pi(s)$ 之间的关系，和后继状态 $s’$ 和后继动作 $a’$ 的行为价值函数 $q_\pi(s’,a’)$ 和当前的动作 a 、当前状态 s 的行为价值函数 $q_\pi (s,a)$即：

$$v_\pi(s)=E_\pi [R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s]\\ q_\pi(s,a)=E_\pi[R_{t+1}+\gamma q_\pi(S_{t+1},A_{t+1})|S_t=s,A_t=a]$$

学生 MDP 示例（如何计算状态价值函数）

如图所示，在 $\pi(a|s)=0.5$ ，$\gamma=1$ 时，粉色圆圈的状态对应的状态价值是如何计算的。

同理，也可以求出其他状态价值函数和动作价值函数。

Bellman期望方程的矩阵形式求解

状态价值函数的矩阵计算推导如下所示：

$$v_\pi=\mathcal{R}_\pi+\gamma \mathcal{P}^\pi v_\pi\\ (1-\gamma \mathcal{P}^\pi)v_\pi=\mathcal{R}^\pi\\ v_\pi=(1-\gamma \mathcal{P}^\pi)^{-1}\mathcal{R}^\pi$$

接下来可以求出随即策略 $\pi$ 下的动作价值函数：

$$q_\pi(s,a)=\mathcal{R}_s^a+\gamma \sum_{s'\in S}\mathcal{P}^a_{ss'}v_\pi(s')$$

最优价值函数

最优状态价值函数 $v_(s)$ 指的是在从所有策略产生的状态价值函数中，选取使状态 s 价值最大的函数：$v_(s)=\max_{\pi}v_\pi(s)$

类似的，最优行为价值函数 $q_(s,a)$ 指的是从所有策略产生的行为价值中，选取使得 $$ 价值最大的函数：$q_(s,a)=\max_{\pi}q_\pi(s,a)$

最优价值函数明确了 MDP 的最优可能表现，也就是相当于每一步都要找到最大的。当求得最优价值函数，也就知道了每个状态的最优价值，这时便认为这个 MDP 得到了解决。

最优策略即如何寻找

当对于任何状态 s ，遵循策略 $\pi$ 的价值不小于遵循策略 $\pi’$ 下的价值，则策略 $\pi$ 优于策略 $\pi’$ 。即：

$$\pi\ge\pi'\ \ if\ \ v_\pi(s)\ge v_{\pi'}(s),\forall s$$

定理

对于任何 MDP，下面几点成立

存在一个最优策略 $\pi_$，比其他任何策略更好或至少相等，即 $\pi_\ge\pi,\forall\pi$

所有的最优策略有相同的最优状态价值函数，即 $v_{\pi_}(s)=v_(s)$

所有的最优策略有相同的最优行为价值函数，即 $q_{\pi_}(s,a)=q_(s,a)$

可以通过最大化最优行为价值函数 $q_{*}(s,a)$ 来找到最优策略。

此公式表示，在已经使得 q 达到最大化时，此时状态为 s 时，选择哪一个策略（动作）就能达到 $q_*$。

argmax：若有结果x0= argmax(f(x))，则表示当函数f(x)取x=x0的时候，得到f(x)取值范围的最大值

Bellman 最优方程

针对 $v_$ ，一个状态的最优价值，等于该状态出发采取的所有行为产生的行为价值中，最大的那个行为价值：$v_(s)=max_a q_*(s,a)$

再对比一下贝尔曼期望方程：$v_\pi(s)=\sum_{a\in A}\pi(a|s)q_\pi(s,a)$

可以得到如下推导过程：$v_(s)=v_{\pi_}(s)=\sum_{a\in A}\pi_(a|s)q_{\pi_}(s,a)=max_{a} q_{\pi_}(s,a)=max_a q_(s,a)$

（理解第三个等号如何成立：这里用到了之前介绍的最大化最优行为价值函数，即在 a 为取得最大行为价值函数需要进行的动作时，$\pi_*(a|s)$ 的值为1，其他都为0）

（理解第四个等号如何成立：所有的最优策略有相同的最优行为价值函数，即 $q_{\pi_}(s,a)=q_(s,a)$）

针对 $q_*$ ，在某个状态 s 下，采取某个行为的最优价值由两个部分构成，一部分是离开状态 s 的即时奖励，另一部分是所有能够到达的状态 $s’$ 的最优状态价值按出现的概率求和：

$$q_*(s,a)=\mathcal{R}^a_s+\gamma \sum_{s'\in S}\mathcal{P}^a_{ss'}v_*(s')$$

组合起来，针对 $v_*$ ，有

$$v_*(s)=max_a(\mathcal{R}^a_s+\gamma\sum_{s'\in S}\mathcal{P}^a_{ss'}v_*(s'))$$

针对 $q_*$，有

$$q_*(s,a)=\mathcal{R}^a_s+\gamma \sum_{s'\in S}\mathcal{P}^a_{ss'}max_{a'}\ q_*(s',a')$$