强化学习（二）马尔科夫决策过程（MDP）

1. 简介

• 马尔可夫决策过程正式地描述了强化学习的环境
• 其中环境是完全可观测的
• 即当前状态完全表征了这个过程
• 几乎所有的强化学习问题都可以形式化为马尔可夫决策过程，例如：
  • 最优控制主要处理连续的马尔可夫决策过程
  • 部分可观察的问题可以转化为马尔可夫决策过程
  • 赌场问题是具有单一状态的马尔可夫决策过程

2. 马尔科夫性（Markov property）

当一个随机过程在给定现在状态及所有过去状态情况下，其未来状态的条件概率分布仅依赖于当前状态；换句话说，在给定现在状态时，它与过去状态（即该过程的历史路径）是条件独立的，那么此随机过程即具有马尔可夫性质。具有马尔可夫性质的过程通常称之为马尔可夫过程。

用式子来表示：

$$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,\cdots ,S_t]$$

或者：

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

状态转移矩阵 $\mathcal{P}$ 定义了从 $s$ 的所有状态到所有后继状态 $s^{\prime }$ 的转移概率，每一行的和都是1

3. 马尔可夫过程（Markov Process）

马尔科夫过程是一个无记忆的随机过程，比如一系列遵循马尔科夫性的随机状态 $S_1,S_2,\cdots$

定义：马尔可夫过程（也称为马尔可夫链）是一个元组 $⟨S,\mathcal{P}⟩$，其中：

• $S$ 是一个有限的状态集合
• $\mathcal{P}$ 是一个状态转移矩阵，${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s]$

例子：学生马尔可夫链

这个马尔科夫链从 $S_1=C1$ 开始，$S_1,S_2,\cdots ,S_T$ 举例如下：

$C1,C2,C3,Pass,Sleep$
$C1,FB,FB,C1,C2,Sleep$
$C1,C2,C3,Pub,C2,C3,Pass,Sleep$
$C1,FB,FB,C1,C2,C3,Pub,C1,FB,FB,FB,C1,C2,C3,Pub,C2,Sleep$

学生马尔可夫链的转移矩阵：

4. 马尔可夫奖励过程（Markov Reward Process）

马尔可夫奖励过程是一个元组 $⟨S,\mathcal{P},\mathcal{R},\gamma ⟩$

• $S$ 是一个有限的状态集合
• $\mathcal{P}$ 是一个状态转移矩阵，${\mathcal{P}}_{s{s}^{\prime }}=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s]$
• $\mathcal{R}$ 是一个奖励函数，${\mathcal{R}}_s=\mathbb{E}[R_{t+1}|S_t=s]$
• $\gamma$ 是一个折扣系数，$\gamma \in [0,1]$

例子：学生马尔可夫奖励过程（Student MRP）

$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}$ 代表收获（return)，是一个MDP中从某一个状态 $S_t$ 开始采样直到终止状态时所有奖励的有衰减的和。

其中：

• 折扣系数（或者叫衰减系数）$\gamma \in [0,1]$ 是未来奖励的当下价值
• 在 $k+1$ 个时间步后获得奖励的价值为 ${\gamma }^{k}R$
• 即时奖励的价值高于延迟奖励:
  • $\gamma$ 接近0会导致“近视”评估
  • $\gamma$ 接近1会导致“远视”评估

大多数马尔可夫奖励和决策过程是带有折扣的。为什么？

• 数学上折扣奖励更方便
• 避免循环马尔可夫过程中出现无限回报
• 对未来的不确定性可能无法完全表示
• 如果奖励是金钱，即时奖励可能比延迟奖励赚取更多利息
• 动物/人类行为表现出对即时奖励的偏好
• 有时可以使用不带折扣的马尔可夫奖励过程（即$\gamma =1$），比如所有的序列都一定会终止

例子：Student MRP Returns

初始状态为 $S_1=C1$，$\gamma =\frac{1}{2}$

$$G_1=R_2+\gamma R_3+\cdots +{\gamma }^{T-2}{R}_T$$

$\gamma =0$ 时学生MRP的状态价值函数：

$\gamma =0.9$ 时学生MRP的状态价值函数：

$\gamma =1$ 时学生MRP的状态价值函数：

马尔科夫奖励过程的贝尔曼方程

状态价值函数可以被分解为两部分：

• 即时奖励 $R_{t+1}$
• 后续状态的折扣价值 $\gamma v(S_{t+1})$

$$\begin{array}{rl}v(s)& =\mathbb{E}[G_t\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\dots \mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+\dots )\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma G_{t+1}\mid S_t=s]\\ & =\mathbb{E}[R_{t+1}+\gamma v(S_{t+1})\mid S_t=s]\end{array}$$

马尔科夫奖励过程（MRPs）的贝尔曼方程：

$$v(s)=\mathbb{E}[R_{t+1}+\gamma v(S_{t+1}|S_t=s)]$$

$$v(s)={\mathcal{R}}_s+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}v(s^{\prime })$$

例子：Student MRP的贝尔曼方程

这里的 $\gamma =1$，并且已经知道了Pub的状态价值为0.8，Pass的状态价值为10

贝尔曼方程的矩阵形式：

$$v=\mathcal{R}+\gamma \mathcal{P}v$$

其中 $v$ 是每个状态都有一个对应元素的列向量：

求解贝尔曼方程：

贝尔曼方程是一个线性方程，可以被直接求解：

$$\begin{array}{rl}v& =\mathcal{R}+\gamma \mathcal{P}v\\ (I-\gamma \mathcal{P})v& =\mathcal{R}\\ v& =(I-\gamma \mathcal{P}{)}^{-1}\mathcal{R}\end{array}$$

对于n个状态的计算复杂度为 $O(n^3)$

因为计算复杂度比较大，直接求解只可能在小规模的马尔科夫奖励过程中实现，在大规模马尔科夫奖励过程中可以使用很多迭代的方法，比如：

• 动态规划（Dynamic Programming）
• 蒙特卡洛法（Monte-Carlo evaluation）
• 时序差分法（Temporal-Difference）

5. 马尔科夫决策过程 Markov Decision Process

马尔科夫决策过程（MDP）就是带有决策的马尔科夫奖励过程（MRP），它是一个所有状态都符合马尔科夫性质的环境。

马尔科夫决策过程是一个元组 $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$

• $\mathcal{S}$是一个有限的状态集合
• $\mathcal{A}$ 是一个有限的动作集合
• $\mathcal{P}$ 是一个状态转移概率矩阵，${\mathcal{P}}_{s{s}^{\prime }}^a=\mathbb{P}[S_{t+1}=s^{\prime }|S_t=s,A_t=a]$
• $\mathcal{R}$ 是一个奖励函数，$\mathcal{R}=\mathbb{E}[R_{t+1}|S_t=s,A_t=a]$
• $\gamma$ 是一个折扣率，$\gamma \in [0,1]$

例子：学生马尔科夫决策过程

策略$\pi$是给定状态下动作的概率分布

$$\pi (a|s)=\mathbb{P}[A_t=a|S_t=s]$$

• 策略完全定义了一个agent的行为
• MDP的策略只依赖当前状态（不依赖历史状态）
• 比如，策略是静态的，与时间无关，$A_t\sim \pi (\cdot \mid S_t),\forall t>0$

给定一个MDP $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$ 和一个策略 $\pi$，状态序列 $S_1,S_2,\cdots$ 是一个马尔科夫过程 $⟨\mathcal{S},{\mathcal{P}}^{\pi }⟩$，状态和奖励序列 $S_1,R_2,S_2,\cdots$ 是一个马尔科夫奖励过程 $⟨\mathcal{S},{\mathcal{P}}^{\pi },{\mathcal{R}}^{\pi },\gamma ⟩$，则有：

$${\mathcal{P}}_{s,s^{\prime }}^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{P}}_{s{s}^{\prime }}^a$$

$${\mathcal{R}}_s^{\pi }=\sum _{a\in \mathcal{A}}\pi (a\mid s){\mathcal{R}}_s^a$$

价值函数：

一个MDP的状态价值函数 $v_{\pi }(s)$ 是从状态 $s$ 开始依据策略 $\pi$ 的收获（$G_t$）的期望：

$$v_{\pi }(s)={\mathbb{E}}_{\pi }[G_t|S_t=s]$$

动作价值函数 $q_{\pi }(s,a)$ 是是从状态 $s$ 开始依据策略 $\pi$ 采取动作 $a$ 的期望：

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]$$

例子：Student MDP的状态价值函数

Bellman期望方程 Bellman Expectation Equation

MDP下的状态价值函数和动作价值函数与MRP下的价值函数类似，可以改用下一时刻状态价值函数或动作价值函数来表达，具体方程如下：

$$v_{\pi }(s)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma v_{\pi }(S_{t+1})\mid S_t=s\right]$$

$$q_{\pi }(s,a)={\mathbb{E}}_{\pi }\left[R_{t+1}+\gamma q_{\pi }(S_{t+1},A_{t+1})\mid S_t=s,A_t=a\right]$$

根据动作价值函数 $q_{\pi }(s,a)$ 和状态价值函数 $v_{\pi }(s)$ 的定义，我们很容易得到他们之间的转化关系公式：

利用上贝尔曼方程，我们也很容易用状态价值函数表示动作价值函数
，即：

当然，也可以做一层推算：

例子：Student MDP的贝尔曼期望方程

图中计算Pass的状态价值所用方程：

$$v_{\pi }(s)=\sum _{a\in \mathcal{A}}\pi (a\mid s)\left({\mathcal{R}}_s^a+\gamma \sum _{s^{\prime }\in \mathcal{S}}{\mathcal{P}}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })\right)$$

因为不是从Pub来推理Pass，而是从Pub的上一层 Class 1，Class 2和Class 3来推理，所以不用知道Pub的状态价值就可以计算。同理因为Sleep没有上一层，所以只需要用它的奖励就可以计算Pass的价值。

贝尔曼期望方程的矩阵形式：

Bellman期望方程可以用诱导MRP简洁地表示：

$$v_{\pi }={\mathcal{R}}^{\pi }+\gamma {\mathcal{P}}^{\pi }{v}_{\pi }$$

可以直接求解：

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

6. 最优价值函数

定义：

最优状态价值函数 $v_{\ast }(s)$ 指的是在所有策略产生的状态价值函数中，使状态s价值最大的那个函数：

$$v_{\ast }(s)=\underset{\pi }{\max }{v}_{\pi }(s)$$

最优动作价值函数 $q_{\ast }(s,a)$ 指的是在所有策略产生的动作价值函数中，使状态动作对$⟨s,a⟩$价值最大的那个函数：

$$q_{\ast }(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$

最优价值函数明确了MDP的最优可能表现，当我们知道了最优价值函数，也就知道了每个状态的最优价值，这时便认为这个MDP得到了解决。

例子：Student MDP的最优价值函数

例子：Student MDP的最优动作价值函数

最优策略

定义策略的部分排序：

$$\pi \ge {\pi }^{\prime }\text{if}{v}_{\pi }(s)\ge v_{{\pi }^{\prime }}(s),\forall s$$

定理：

对于任意马尔可夫决策过程（Markov Decision Process, MDP）：

• 存在一个最优策略 ${\pi }_{\ast }$，它优于或等于所有其他策略，即 ${\pi }_{\ast }\ge \pi ,\forall \pi$
• 所有最优策略都能达到最优状态价值函数，即 $v_{{\pi }_{\ast }}(s)=v_{\ast }(s)$
• 所有最优策略都能达到最优动作-价值函数，即 $q_{\pi }\ast (s,a)=q_{\ast }(s,a)$

寻找最优策略

可以通过最大化最优行为价值函数来找到最优策略：

$${\pi }_{\ast }(a|s)=\{\begin{array}{ll}1& \text{if }a=\underset{a\in \mathcal{A}}{\mathrm{argmax}}{q}_{\ast }(s,a)\\ 0& \text{otherwise}\end{array}$$

• 对于任何MDP问题，总存在一个确定性的最优策略；
• 如果我们得到了最优动作价值函数 $q_{\ast }(s,a)$，则表明我们已经找到了最优策略。

例子：Student MDP的最优策略

$v_{\ast }$的贝尔曼最优方程

最优值函数通过贝尔曼最优方程递归关联

$Q_{\ast }$的贝尔曼最优方程

$v_{\ast }$的贝尔曼最优方程（2）

$Q_{\ast }$的贝尔曼最优方程（2）

例子：Student MDP的贝尔曼最优方程

求解贝尔曼最优方程：

尔曼最优方程是非线性的，（一般情况下）没有封闭解，但有许多迭代求解方法来解决：价值迭代（Value Iteration）、策略迭代（Policy Iteration）、Q学习（Q-learning）、Sarsa等

还有一些马尔可夫决策过程（MDPs）的扩展，比如：

• 无限和连续的马尔可夫决策过程（Infinite and continuous MDPs）
• 部分可观测的马尔可夫决策过程（Partially observable MDPs）
• 无折扣、平均奖励的马尔可夫决策过程（Undiscounted, average reward MDPs）

这里不做一一讲解