# 马尔科夫决策过程

## 马尔科夫决策过程

* [返回顶层目录](https://github.com/luweikxy/machine-learning-notes/tree/994efe9a1942533ce4f543c98b52dec4b6225352/content/reinforcement-learning/SUMMARY.md)
* [本章在学习地图中的位置](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#本章在学习地图中的位置)
* [马尔科夫决策过程简介](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫决策过程简介)
* [符号约定](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#符号约定)
* [马尔科夫过程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫过程)
  * [马尔科夫性](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫性)
  * [状态转移矩阵](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#状态转移矩阵)
  * [状态转移函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#状态转移函数)
  * [马尔科夫过程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫过程)
  * [片段](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#片段)
  * [马尔科夫链的例子](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫链的例子)
* [马尔科夫奖励过程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫奖励过程)
  * [马尔科夫奖励过程例子](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫奖励过程例子)
  * [回报值](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#回报值)
  * [再聊片段](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#再聊片段)
  * [再聊衰减值](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#再聊衰减值)
  * [值函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#值函数)
  * [例子：回报值和值函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#例子：回报值和值函数)
    * [回报值](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#回报值)
    * [针对例子的V函数值](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#针对例子的V函数值)
  * [MRPs中的贝尔曼方程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#MRPs中的贝尔曼方程)
    * [针对例子的贝尔曼方程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#针对例子的贝尔曼方程)
    * [贝尔曼方程的矩阵形式](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼方程的矩阵形式)
* [马尔科夫决策过程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫决策过程)
  * [马尔科夫决策过程的定义](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#马尔科夫决策过程的定义)
    * [MDPs例子](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#MDPs例子)
  * [策略](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#策略)
  * [MDPs和MRPs之间的关系](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#MDPs和MRPs之间的关系)
  * [MDPs中的值函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#MDPs中的值函数)
  * [贝尔曼期望方程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼期望方程)
    * [V函数与Q函数之间的相互转化](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#V函数与Q函数之间的相互转化)
    * [贝尔曼期望方程—V函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼期望方程—V函数)
    * [贝尔曼期望方程—Q函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼期望方程—Q函数)
    * [贝尔曼期望方程例子](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼期望方程例子)
    * [贝尔曼期望方程的矩阵形式](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼期望方程的矩阵形式)
  * [最优值函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优值函数)
    * [最优V函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优V函数)
    * [最优Q函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优Q函数)
  * [最优策略](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优策略)
    * [最优策略定理](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优策略定理)
    * [怎么得到最优策略](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#怎么得到最优策略)
    * [最优策略例子](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优策略例子)
  * [v\*与q\*的相互转化](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#v*与q*的相互转化)
  * [贝尔曼最优方程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#贝尔曼最优方程)
    * [最优V函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优V函数)
    * [最优Q函数](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#最优Q函数)
    * [和贝尔曼期望方程的关系](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#和贝尔曼期望方程的关系)
    * [解贝尔曼最优方程](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#解贝尔曼最优方程)
* [MDPs的扩展](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#MDPs的扩展)
  * [无穷或连续MDPs](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#无穷或连续MDPs)
  * [部分可观测MDPs](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#部分可观测MDPs)
  * [无衰减MDPs](https://luweikxy.gitbook.io/machine-learning-notes/pages/-LpO5vHPEo26IuYVi3s1#无衰减MDPs)

## 本章在学习地图中的位置

![learning-map](/files/-LpO60k1bqG6kPc3DImz)

马尔科夫决策过程是强化学习的数学基础，也是将强化学习从直观定义到数学定义的一个桥梁。

## 马尔科夫决策过程简介

* **马尔科夫决策过程（Markov Decision Process, MDPs）**是对强化学习问题的**数学描述**。
* 要求环境是全观测的。（原因后述）
* 几乎所有的RL问题都能用MDPs来描述
  * 最优控制问题可以描述成**连续MDPs**
  * 部分观测问题可以转化成POMDPs
  * 赌博机问题是只有**一个状态**的MDPs

注：虽然大部分RL问题都可以转化成MDPs，但是在我写的笔记中所描述的MDPs是在全观测的情况下。

## 符号约定

* 用大写字母表示随机变量：例如

  $$
  S,A,R
  $$
* 用小写字母表示某一个具体的值

  $$
  s,a,r
  $$
* 用空心字母表示统计运算符

  $$
  \mathbb{E,P}
  $$
* 用花体字母表示集合或函数（注：这里没用花体表示是因为gitbook不支持渲染花体\cal{}）

  $$
  S,A,P
  $$

## 马尔科夫过程

### 马尔科夫性

只要知道**现在**，将来和过去是条件独立的。

定义：

如果在t时刻的状态St满足如下等式，那么这个状态被称为马尔科夫状态，或者说该状态满足马尔科夫性：

$$
\mathbb{P}\[S\_{t+1}|S\_t]=\mathbb{P}\[S\_{t+1}|S\_1,...,S\_t]
$$

* 状态St包含了所有历史**相关**信息（注：这里的相关指与问题相关，可能有一些问题无关的信息没有在St中）
* 或者说历史的所有状态的相关信息都在当前状态St上体现出来
* 一旦St知道了，那么S1,S2,...,St-1都可以被抛弃
* 数学上可以认为：状态是将来的充分统计量
* 因此，这里要求环境全观测（马尔科夫性与状态的定义息息相关，比如打砖块，就要求状态是当前画面帧和上一次的画面帧，不然得不到砖块下落速度）
* 例子
  * 下棋时，只用关心当前局面
  * 打俄罗斯方块时，只用关心屏幕
* 有了马尔科夫状态之后
  * 定义状态转移矩阵
  * 忽略时间的影响

### 状态转移矩阵

定义：

状态转移概率指从一个马尔科夫状态s跳转到后继状态（successor state）s‘的概率

$$
{P}*{ss'}=\mathbb{P}\[S*{t+1}=s'|S\_t=s]
$$

所有的状态组成行，所有的后继状态组成列，我们得到状态转移矩阵

$$
\begin{aligned}
{P}=
\begin{bmatrix}
{P}*{11} & ... & {P}*{1n}\\
\vdots & \ddots & \vdots\\
{P}*{n1} & ... & {P}*{nn}\\
\end{bmatrix}
\end{aligned}
$$

* n表示状态的个数
* 由于P代表了整个状态转移的集合，所以用花体
* 每行元素相加等于1

### 状态转移函数

我们也可以将状态转移概率写成函数的形式

$$
{P}*{ss'}=\mathbb{P}\[S*{t+1}=s'|S\_t=s]
$$

* 状态转移概率到下一各状态的和为1，即

  $$
  \sum\_{s'}\mathbb{P}(s'|s)=1
  $$
* 状态数量太多或者是无穷大（连续状态）时，更适合使用状态转移函数，此时

  $$
  \int\_{s'}\mathbb{P}(s'|s)=1
  $$

### 马尔科夫过程

一个马尔科夫过程（Markov process， MP）是一个无记忆的随机过程，即一些马尔科夫状态的序列

定义：

马尔科夫过程可以由一个二元组来定义\\

* S代表了状态的集合
* P代表了状态转移概率矩阵

  $$
  {P}*{ss'}=\mathbb{P}\[S*{t+1}=s'|S\_t=s]
  $$

注：虽然我们有时候并不知道P的具体值，但是通常我们假设P是存在且稳定的

注：当P不稳定时，是不稳定环境，需要在线学习，快速学习

**马尔科夫过程的例子**：

![MP-example](/files/-LpO60k5Bk6inr1Sjlie)

* 一个学生每天需要学习三个科目，然后通过测验
* 不过也有可能只学完两个科目之后直接睡觉
* 一旦挂科，有可能需要重新学习某些科目
* 用椭圆表示普通状态，每一条线上的数字表示从一个状态跳转到另一个状态的概率
* 方块表示终止（terminal）状态
* 终止状态的定义有两种：
  * 时间终止
  * 状态终止

由于马尔科夫过程可以用图中的方块和线条组成，所以可以称马尔科夫过程为**马尔科夫链（MDPs chain）**

### 片段

定义：

强化学习中，从**初始**状态S1到终止状态的序列过程，被称为一个片段（episode）

$$
S\_1,S\_2,...,S\_T
$$

* 如果一个任务总以终止状态结束，那么这个任务被称为**片段**（episodic task）
* 如果一个任务会没有终止状态，会被无限执行下去，这被称为**连续性任务**（continuing task）

### 马尔科夫链的例子

![MP-example](/files/-LpO60k7KW_K2SFLR2MP)

**片段**：

假设初始状态是“科目一”，从这个马尔科夫链中，我们可能采样到如下的片段

* “科目一”，“科目二”，“睡觉”
* “科目一”，“科目二”，“科目三”，“通过”，“睡觉”
* “科目一”，“玩手机”，“玩手机”，... ，“玩手机”，“科目一”，“科目二”，“睡觉”
* “科目一”，“科目二”，“科目三”，“挂科”，“科目二”，“科目三”，“挂科”，“科目一”，“科目二”，“科目三”，“挂科”，“科目三”，“通过”，“睡觉”

**转移矩阵**

分别用s1\~s7代表“科目一”，“科目二”，“科目三”，“通过”，“挂科”，“玩手机”，“睡觉”

$$
{P}=
\begin{bmatrix}
-& 0.5 & -& -& -& 0.5 & -\\
-& -& 0.8 & -& -& -& 0.2\\
-& -& -& 0.6 & 0.4 & -& -\\
-& -& -& -&- & -& 1.0\\
0.2 & 0.4 & 0.4 & -& -& -& -\\
0.1 & -& -& -& -& 0.9 & -\\
-& -& -& -&- & -& 1.0\\
\end{bmatrix}
$$

## 马尔科夫奖励过程

接下来我们在马尔科夫过程中加一个强化学习中三大交互学习组成中最重要的一个：奖励，这也是强化学习和其他机器学习问题中比较大的一个区别。

马尔科夫过程主要描述的是状态之间的转移关系，在这个转移关系上赋予不同的奖励值即得到了马尔科夫**奖励**过程。

定义：

马尔科夫奖励过程（Markov Reward Process，MRP）过程由一个四元组组成\\

* S代表了状态的集合
* P描述了状态转移矩阵

  $$
  {P}*{ss'}=\mathbb{P}\[S*{t+1}=s'|S\_t=s]
  $$
* **R表示奖励函数，R(s)描述了在状态s的奖励，**

  $$
  {R}(s)=\mathbb{E}\[R\_{t+1}|S\_t=s]
  $$
* γ表示衰减引子，

  $$
  \gamma\in \[0,1]
  $$

### 马尔科夫奖励过程例子

![markov-reward-process-example1](/files/-LpO60k99iuKU2174ldU)

### 回报值

* 奖励值：对每一个**状态**的评价
* 回报值：对每一个**片段**的评价

定义：

回报值（return Gt）是从时间t处开始的累计衰减奖励。

* 对于片段性任务：

  $$
  \begin{aligned}
  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}
  \end{aligned}
  $$
* 对于连续性任务：

  $$
  \begin{aligned}
  G\_t&=R\_{t+1}+\gamma R\_{t+2}+\gamma^2R\_{t+3}+...\\
  &=\sum\_{k=0}^{\infty}\gamma^kR\_{t+k+1}
  \end{aligned}
  $$

### 再聊片段

![slice](/files/-LpO60kChHDLKBAnzGuU)

* 终止状态等价于自身转移概率为1，奖励为0的状态
* 因此我们能够将片段性任务和连续性任务统一表达：

  $$
  G\_t=\sum\_{k=0}^{T-t-1}\gamma^kR\_{t+k+1}
  $$

  这里当T=∞时，表示连续性任务，否则即为片段性任务。

### 再聊衰减值

为什么我们要使用这样的衰减指数值？

* 直观感觉
  * 影响未来的因素不仅仅包含当前
  * 我们对未来的把握也是逐渐衰减的
  * 一般情况下，我们更关注短时间的反馈
* 数学便利
  * 一个参数就描述了整个衰减过程，只需要调节这一个参数γ就可以来调节长时奖励和短时奖励的权衡（trade-off）
  * 指数衰减形式又很容易进行数学分析
  * 指数衰减是对回报值的有界保证，避免了循环MRP和连续性MRP情况下回报值变成无穷大

注：在一些特殊情况，也可以使用γ=1的回报值

### 值函数

为什么要值函数？

* 回报值是一次片段的结果，存在很大的样本偏差
* 回报值的脚标是t，值函数关注的是状态s

值函数定义：

一个马尔科夫奖励过程MRP的值函数定义如下：

$$
v(s)=\mathbb{E}\[G\_t|S\_t=s]
$$

也是就是从这个状态出发的所有片段的回报值的按照概率加权的平均值（即期望值）。

* 这里的值函数针对的是状态s，所以称为**状态值函数**，又称V函数
* Gt是一个随机变量
* 这里使用小写的v函数，代表了真实存在的值函数

### 例子：回报值和值函数

#### 回报值

![markov-reward-process-example1](/files/-LpO60kHwBO-IfB-z4yZ)

针对初始状态S1=“科目一”，且γ=0.5计算不同片段的回报值

* "科目一"，“科目二”，“睡觉”

  $$
  \begin{aligned}
  g\_1&=(-2)+0.5\times (-2)+0.5^2\times (0)\\
  &=-3
  \end{aligned}
  $$
* "科目一"，“科目二”，“科目三”，“通过”，“睡觉”

  $$
  \begin{aligned}
  g\_1&=(-2)+0.5\times (-2)+0.5^2\times (-2)+0.5^3\times (10)+0.5^4\times (0)\\
  &=-2.25
  \end{aligned}
  $$
* "科目一"，“玩手机”，“玩手机”，“玩手机”，"科目一"，“科目二”，“睡觉”

  $$
  \begin{aligned}
  g\_1=&(-2)+0.5\times (-1)+0.5^2\times (-1)+0.5^3\times (-1)\\
  &+0.5^4\times (-2)+0.5^5\times (-2)+0.5^6\times (0)\\
  \=&-3.0625
  \end{aligned}
  $$
* "科目一"，“科目二”，“科目三”，“挂科”，“科目二”，“科目三”，“挂科”，"科目一"，“科目二”，“科目三”，“挂科”，“科目三”，“通过”，“睡觉”

  $$
  \begin{aligned}
  g\_1&=(-2)+0.5\times (-2)+0.5^2\times (-2)+...\\
  &=-4.4214...
  \end{aligned}
  $$

**虽然都是从相同的初始状态开始，但是不同的片段有不同的回报值，而值函数是它们的期望值。**

#### 针对例子的V函数值

当γ=0时

![value-function-gamma-0](/files/-LpO60kLj8pU1iPBmVMS)

当γ=1时

![value-function-gamma-1](/files/-LpO60kNU5oNz8efZ_qq)

### MRPs中的贝尔曼方程

值函数的表达式可以分解成两部分

* 瞬时奖励$R\_{t+1}$
* 后继状态$S\_{t+1}$的值函数乘上一个衰减系数

$$
\begin{aligned}
v(s)&=\mathbb{E}\[G\_t|S\_t=s]\\
&=\mathbb{E}\[R\_{t+1}+\gamma R\_{t+2}+\gamma^2R\_{t+3}+...|S\_t=s]\\
&=\mathbb{E}\[R\_{t+1}+\gamma (R\_{t+2}+\gamma R\_{t+3}+...)|S\_t=s]\\
&=\mathbb{E}\[R\_{t+1}+\gamma G\_{t+1}|S\_t=s]\\
&=\mathbb{E}\[R\_{t+1}+\gamma v(S\_{t+1})|S\_t=s]\\
\end{aligned}
$$

* 体现了v(s)与v($S\_{t+1}$)之间的迭代关系
* 这是强化学习中的理论核心之一
* 注意s小写，$S\_{t+1}$大写

如果我们已知转移矩阵P，那么

$$
\begin{aligned}
v(s)&=\mathbb{E}\[R\_{t+1}+\gamma v(S\_{t+1})|S\_t=s]\\
&=\mathbb{E}\[R\_{t+1}|S\_t=s]+\gamma\mathbb{E}\[v(S\_{t+1})|S\_t=s]\\
&={R}(s)+\gamma\sum\_{s'\in S}{P}\_{ss'}v(s')
\end{aligned}
$$

!\[value-ss']\(pic/value-ss'.png)

图中我们可以用v(s1)，v(s2)，v(s3)去计算v(s0)。

#### 针对例子的贝尔曼方程

当γ=1时，我们来看下一状态可能性最多的“科目三”状态：

$$
0.6=(-2)+0.6\times 10+0.4\times(-0.85)
$$

![bellman-equation-example1](/files/-LpO60kQQ26EQoEbTrNU)

#### 贝尔曼方程的矩阵形式

使用矩阵-向量的形式表达贝尔曼方程，即

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

假设状态集合为

$$
{S}={s\_1,s\_2,...,s\_n}
$$

，那么

$$
\begin{aligned}
\begin{bmatrix}
v(s\_1)\\
\vdots\\
v(s\_n)\\
\end{bmatrix}
=============

\begin{bmatrix}
{R}(s\_1)\\
\vdots\\
{R}(s\_n)\\
\end{bmatrix}
\+
\gamma
\begin{bmatrix}
{P}*{11} & ... & {P}*{1n}\\
\vdots & \ddots & \vdots\\
{P}*{n1} & ... & {P}*{nn}\\
\end{bmatrix}
\end{aligned}
\begin{bmatrix}
v(s\_1)\\
\vdots\\
v(s\_n)\\
\end{bmatrix}
$$

贝尔曼方程本质上是一个线性方程，可以直接解

$$
\begin{aligned}
v&={R}+\gamma{P}v\\
(1-\gamma{P})v&={R}\\
v&=(1-\gamma{P})^{-1}{R}
\end{aligned}
$$

* 计算复杂度O(n^3)
* 要求已知状态转移矩阵P
* 直接求解的方式仅限于小的MRPs

## 马尔科夫决策过程

### 马尔科夫决策过程的定义

**与马尔科夫过程MP和马尔科夫奖励过程MRP的区别：**

* MP和MRP中，我们都是作为观察者，去观察其中的状态转移现象，去计算回报值。
* 对于一个RL问题，我们更希望去**改变**状态转移的流程，去**最大化**回报值。
* 通过在MRP中引入决策，即得到了**马尔科夫决策过程（Markov Decision Process，MDPs）**

**马尔科夫决策过程的定义**

一个马尔科夫决策过程（MDPs）由一个五元组构成

$$
<{S,A,P,R,\gamma}>
$$

* S代表了状态的集合
* A代表了**动作**的集合
* P描述了状态转移矩阵

  $$
  {P}*{ss'}^a=\mathbb{P}\[S*{t+1}=s'|S\_t=s,A\_t=a]
  $$
* R表示奖励函数，R(s,a)描述了在状态s**做动作a**的奖励

  $$
  {R}(s,a)=\mathbb{E}\[R\_{t+1}|S\_t=s,A\_t=a]
  $$
* γ表示衰减引子，γ∈\[0,1]

#### MDPs例子

![MDPs-example1](/files/-LpO60kTrqfMtHFBtGXz)

* 针对状态的奖励变成了针对\的奖励
* 能通过动作进行控制的状态转移由原来的状态转移概率特换成了动作
* MDP只关注那些可以做出决策的动作
* 被动的状态转移关系被压缩成一个状态
  * “被动”指无论做任何动作，状态都会发生跳转。这样的状态不属于MDPs中考虑的状态
  * 原图中，由于“通过”后一定会去“睡觉”，因此进行了压缩
  * 原图中，“挂科”后的跳转不受控制

注：图中除了在“科目三”的状态上执行“不复习”动作外，其他的所有状态跳转都是不确定性的，我们通过在不同的状态上执行不同的动作，即可实现不同的状态跳转。

### 策略

我们将之前的MRPs中的状态转移矩阵分成了两个部分

* 能被智能体控制的**策略，Policy**
* MDPs中的转移矩阵P（不受智能体控制，认为是环境的一部分）

策略的定义：

在MDPs中，一个策略（Policy）π是给定状态下的动作的概率分布

$$
\pi(a|s)=\mathbb{P}\[A\_t=a|S\_t=s]
$$

策略的特点

* 策略是对智能体行为的全部描述
* MDPs中的策略是基于马尔科夫状态的（而不是基于历史）
* 策略是时间稳定的，只与状态s有关，与时间t无关
* 策略是RL问题的**终极**目标
* 如果策略的概率分布输出都是**独热的**（one-hot）的，那么成为确定性策略，否则即为随机性策略

### MDPs和MRPs之间的关系

对于一个MDP问题\，如果给定了策略π

* MDP将会退化成MRP，

  $$
  <{S},{P}^{\pi},{R}^{\pi},\gamma>
  $$
* 此时

  $$
  \begin{aligned}
  {P}*{ss'}^{\pi}&=\sum*{a\in {A}}\pi(a|s){P}*{ss'}^a\\
  {R}*s^{\pi}&=\sum*{a\in {A}}\pi(a|s){R}*{s}^a
  \end{aligned}
  $$

注：注意由于策略π代表：1，一个动作；2，一个动作分布，所以有时候，π和a会存在一定的混淆。

### MDPs中的值函数

在MDPs问题中，由于动作的引入，值函数分为了两种：

1. 状态值函数（V函数）
2. 状态动作值函数（Q函数）

定义：

MDPs中的**状态值函数**是从状态s开始，使用策略π得到的期望回报值

$$
v\_{\pi}(s)=\mathbb{E}\_{\pi}\[G\_t|S\_t=s]
$$

定义：

MDPs中的**状态动作值函数**是从状态s开始，执行动作a，然后对接下来的状态使用策略π得到的期望回报值

$$
q\_{\pi}(s,a)=\mathbb{E}\_{\pi}\[G\_t|S\_t=s,A\_t=a]
$$

这个怎么理解呢？

假设一条马尔可夫链为s1, a1, s2, a2, s3, a3 ......

q(s, a)表示初始状态和初始动作确定了s=s1, a=a1，之后的动作a2, a3，...都是来自策略π的：a2,a3,...服从π

也就是与下式是等价的：

给定当前状态s和当前动作a，在未来遵循策略π，那么系统将以概率p(s'|s,a)转向下个状态s'，上式可以重写为：

$$
Q^{\pi}(s,a)=\sum\_{s'\in S}P(s'|s,a)\[R(s'|s,a)+\gamma V^{\pi}(s')]
$$

注：在MDPs中，任何不说明策略π的情况下，讨论值函数都是在耍流氓！

### 贝尔曼期望方程

和MRP相似，MDPs中的值函数也能分为瞬时奖励和后继状态的值函数两部分

$$
\begin{aligned}
v\_{\pi}(s)&=\mathbb{E}*{\pi}\[R*{t+1}+\gamma v\_{\pi}(S\_{t+1})|S\_t=s]\\
q\_{\pi}(s,a)&=\mathbb{E}*{\pi}\[R*{t+1}+\gamma q\_{\pi}(S\_{t+1},A\_{t+1})|S\_t=s,A\_t=a]\\
\end{aligned}
$$

例子：

![MDPs-bellman-expectation-equation-example1](/files/-LpO60kVv_JMYHTXq4Um)

* 当对于所有的s和a，都有π(a|s)=0.5时，v\_π(s)如上图
* 将图中的圆圈状态从上到下从左到右

  分别记为s1,s2,s3,s4，将终止状态记

  为s5，则对于所有的s和a，当π(a|s)=0.5时，状态转移矩阵为&#x20;

$$
{P}=
\begin{bmatrix}
0.5 & 0.5 & -& -& -\\
0.5 & -& 0.5 & -& -\\
-& -& -& 0.5 & 0.5 \\
-& 0.1 & 0.2 & 0.2 & 0.5 \\

* & - & - & -& 1\\
  \end{bmatrix}
  $$

#### V函数与Q函数之间的相互转化

![v-q-convert](/files/-LpO60kX-RTuE9BSMr4V)

$$
v\_{\pi}(s)=\sum\_{a\in {A}}\pi(a|s)q\_{\pi}(s,a)
$$

注：本质上是全概率公式

![q-v-convert](/files/-LpO60kZmiv4sHbBnC4B)

$$
q\_{\pi}(s,a)={R}(s,a)+\gamma\sum\_{s'\in S}{P}*{ss'}^av*{\pi}(s')
$$

#### 贝尔曼期望方程—V函数

![v-q-v-convert](/files/-LpO60kbC0-XvZZakbLN)

$$
\begin{aligned}
v\_{\pi}(s)&=\sum\_{a\in{A}}\pi(a|s)q\_{\pi}(s,a)\\
&=\sum\_{a\in {A}}\pi(a|s)\left({R}(s,a)+\gamma\sum\_{s'\in S}{P}*{ss'}^av*{\pi}(s')\right)
\end{aligned}
$$

实际上等价于

$$
v\_{\pi}(s)=\mathbb{E}*{\pi}\[R*{t+1}+\gamma v\_{\pi}(S\_{t+1})|S\_t=s]
$$

为什么？

#### 贝尔曼期望方程—Q函数

![q-v-q-convert](/files/-LpO60kdVV81T8NeJtcD)

$$
q\_{\pi}(s,a)={R}(s,a)+\gamma\sum\_{ss'}^a\sum\_{a'\in{A}}\pi(a'|s')q\_{\pi}(s',a')
$$

实际上等价于

$$
q\_{\pi}(s,a)=\mathbb{E}\[R\_{t+1}+\gamma q\_{\pi}(S\_{t+1},A\_{t+1})|S\_t=s,A\_t=a]
$$

，为什么？

#### 贝尔曼期望方程例子

当γ=1，π(a|s)=0.5时

$$
2.8=0.5\times (10+0)+0.5\times (-5+0.2\times(-3.6)+0.4\times 0.4+0.4\times 2.8)
$$

![MDPs-bellman-expectation-equation-example2](/files/-LpO60kfdRg1B9Aqb_ys)

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

MDPs下的贝尔曼期望方程和MRP的形式相同。

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

同样地，可以直接求解

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

求解的要求：

* 已知π(a|s)
* 已知P(s'|s,a)

### 最优值函数

之前值函数，以及贝尔曼期望方程针对的都是给定策略π的情况，是一个**评价**的问题。

现在我们来考虑强化学习中的**优化**问题，即找出最好的策略。

定义：

最优值函数指的是在所有策略中的值函数最大值，其中包括最优V函数和最优Q函数

$$
\begin{aligned}
v\_*(s)&=\mathop{\text{max}}*{\pi}\ v*{\pi}(s)\\
q\_*(s,a)&=\mathop{\text{max}}*{\pi}\ q*{\pi}(s,a)
\end{aligned}
$$

* 最优值函数指的是一个MDP中所能达到的最佳性能
* 如果我们找到最优值函数，即相当于这个MDP已经解决了

#### 最优V函数

当γ=1时的最优V函数v\*(s)

![optimal-v-function](/files/-LpO60kjCMwidRRLge5k)

#### 最优Q函数

当γ=1时的最优Q函数q\*(s,a)

![optimal-q-function](/files/-LpO60klGrresHm8Lja7)

### 最优策略

为了比较不同策略的好坏，我们首先应该定义策略的比较关系

$$
\pi\geq\pi'\quad\text{if}\quad v\_{\pi}(s)\geq v\_{\pi'}(s),\ \forall s
$$

#### 最优策略定理

对于任何MDPs问题

* 总**存在**一个策略&#x3C0;*，要好于或等于其他所有的策略，π\\*>π，∀π
* **所有**的最优策略都能够实现最优的V函数

  $$
  v\_{\pi\*}(s)=v\_\*(s)
  $$
* **所有**的最优策略都能够实现最优的Q函数

  $$
  q\_{\pi\*}(s,a)=q\_\*(s,a)
  $$

注：具体证明参考[《Total Expected Discounted Reward MDPs: Existence of Optimal Policies 》](http://www.ams.sunysb.edu/~feinberg/public/enc_dis.pdf)

#### 怎么得到最优策略

我们已知了最优Q函数之后，我们能够马上求出最优策略，只要根据q\*(s,a)选择相应的动作即可。

$$
\begin{aligned}
\pi\_*(a|s)=
\left{\begin{matrix}
&1\quad&\text{if  a = arg }\mathop{\text{max}}*{a\in A}q**(s,a)\\
&0\quad&\text{otherwise}
\end{matrix}\right.
\end{aligned}
$$

* 可以看出对于任何MDPs问题，总存在一个确定性的最优策略
* 如果已知最优V函数，能不能找到最优策略呢？

#### 最优策略例子

当γ=1时的最优策略π\*(a|s)

![optimal-policies-example](/files/-LpO60knJBymJQGPwUmF)

### v\*与q\*的相互转化

* 之前我们已经讨论了vπ(s)和qπ(s,a)之前的关系——贝尔曼期望方程
* 同样地，v\*(s)和q\*(s,a)也存在着递归的关系——贝尔曼**最优**方程

**v->q：**

![bellman-optical-equition](/files/-LpO60kpK7dZHumWkqBh)

$$
v\_*(s)=\mathop{\text{max}}*a\ q**(s,a)
$$

和贝尔曼期望方程的关系：

$$
v\_*(s)=v\_{\pi*}(s)=\sum\_{a\in A}\pi\_*(a|s)q\_{\pi}(s,a)=\mathop{\text{max}}*a\ q*{\pi*}(s,a)
$$

上式很好理解，因为最优动作对应的概率为1嘛。

**q->v：**

![bellman-optical-equition-2](/files/-LpO60kr3_qR7I7iPcIr)

$$
q\_*(s,a)=R(s,a)+\gamma\sum\_{s'\in S}P\_{ss'}^av\_*(s')
$$

### 贝尔曼最优方程

#### 最优V函数

![bellman-optical-equition-V-function](/files/-LpO60kt66M2XJGSQ7wz)

$$
v\_*(s)=\mathop{\text{max}}*a\[R(s,a)+\gamma\sum*{s'\in S}P\_{ss'}^av\_*(s')]
$$

#### 最优Q函数

![bellman-optical-equition-Q-function](/files/-LpO60kvHX_dfqiZ5sKD)

$$
q\_*(s,a)=R(s,a)+\gamma\sum\_{s'\in S}P\_{ss'}^a\ \mathop{\text{max}}*{a'}\ q**(s',a')
$$

#### 和贝尔曼期望方程的关系

* 贝尔曼最优方程本质上就是利用了π\*的特点，将求期望的算子转化成了max\_a
* 在贝尔曼期望方程中，π是已知的。而贝尔曼最优方程中，π\*是未知的。
* 解贝尔曼期望方程的过程即对应了**评价**，解贝尔曼最优方程的过程即对应了**优化**。

#### 解贝尔曼最优方程

* 贝尔曼最优方程不是线性的
* 一般很难有闭式的解
* 可以使用迭代优化的方法去解
  * 值迭代
  * 策略迭代
  * Q学习
  * SARSA
  * ...

## MDPs的扩展

* 无穷或连续MDPs
* 部分可观测MDPs（Partially observable MDPs, POMDPs）
* 无衰减MDPs

### 无穷或连续MDPs

* 动作空间或状态空间无限可数
* 动作空间或状态空间无限不可数 (连续)
* 时间连续&#x20;

### 部分可观测MDPs

* 此时观测不等于状态Ot≠St
* POMDPs由七元组成

  $$
  \<S,A,O,P,R,Z,\gamma>
  $$
* 其中**Z**是观测函数

  $$
  Z\_{s'o}^a=\mathbb{P}\[O\_{t+1}=o|S\_{t+1}=s',A\_t=a]
  $$
* 观测不满足马尔科夫性，因此也不满足贝尔曼方程
* 状态未知，隐马尔科夫过程
* 有时对于POMDPs来说，最优的策略是随机性的

### 无衰减MDPs

* 用于各态历经马尔科夫决策过程
  * 各态历经性：平稳随机过程的一种特性
* 存在独立于状态的平均奖赏ρ^π
* 求值函数时，需要减去该平均奖赏，否则有可能奖赏爆炸

## 参考文献

* [《强化学习理论与实践》第二章：马尔科夫决策过程](http://www.shenlanxueyuan.com/my/course/96)

本章内容是该课程这节课的笔记。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://luweikxy.gitbook.io/machine-learning-notes/markov-decision-processes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.