马尔可夫决策过程

基本概念

马尔可夫决策过程$（Markov\ Decision\ Process, MDP）$是在环境中模拟智能体的随机性策略$（policy）$与回报的数学模型，且环境的状态具有马尔可夫性质。在强化学习中，马尔科夫决策过程是对完全可观测的环境进行描述的，也就是说观测到的状态内容完整地决定了决策的需要的特征。几乎所有的强化学习问题都可以转化为$MDP$。

具体而言：机器处在一个环境中，每个状态为机器对当前环境的感知；机器只能通过动作来影响环境，当机器执行一个动作后，会使得环境按某种概率转移到另一个状态；同时，环境会根据潜在的奖赏函数反馈给机器一个奖赏。综合而言，强化学习主要包含四个要素：状态、动作、转移概率以及奖赏函数。

tbQcZj.png

根据上图，agent（智能体）在进行某个任务时，首先与environment进行交互，产生新的状态state，同时环境给出奖励reward，如此循环下去，agent和environment不断交互产生更多新的数据。强化学习算法就是通过一系列动作策略与环境交互，产生新的数据，再利用新的数据去修改自身的动作策略，经过数次迭代后，agent就会学习到完成任务所需要的动作策略。

用途

模型定义

马尔科夫链/过程

**马尔科夫链（Markov Chain）**即马尔可夫过程，是一种特殊的随机过程——具备马尔可夫性的随机过程。

• 马尔可夫性：（Markov Property）: 如果满足$P(S_{t+1}|S_t,S_{t-1}\cdots S_1)=P(S_{t+1}|S_t)$，即具备了马尔可夫性。简单来说， 和之间存在关系，和以前的时刻的没有关系，即只和“最近的状态” 有关系。

• 现实例子：**下一个时刻仅依赖于当前时刻，跟过去无关。**比如：一个老师讲课，明天的讲课状态一定和今天的状态最有关系，和过去十年的状态基本就没关系了。

• 最主要考量：为了简化计算。$P(S_{t+1}|S_t,S_{t-1}\cdots S_1)=P(S_{t+1}|S_t)$ ，如果$S_{t+1}$和 $S_t,S_{t-1}\cdots S_1$都有关系的话，计算就会太大了，可能造成无法计算。

其中$S$是有限数量的状态集$S={s_1,s_2,\cdots,s_t}$，$P$是状态转移概率矩阵$p(S_{t+1}=s'|s_t=s)$，其中$s'$表示下一时刻的状态，$s$表示当前状态。

如下如所示：对于状态$s_1$来说，有$0.1$的概率保持不变，有$0.2$的概率转移到$s_2$状态，有$0.7$的概率转移到$s_4$状态。

tHJIg0.png

使用矩阵来表示：

$$\begin{align} P = \left[ \begin{matrix} P(s_1|s_1)&P(s_2|s_1)&\cdots&P(s_N|s_1) \\ P(s_1|s_2)&P(s_2|s_2)&\cdots&P(s_N|s_2) \\ \vdots&\vdots&\ddots&\vdots \\ P(s_1|s_N)&P(s_2|s_N)&\cdots&P(s_N|s_N) \\ \end{matrix} \right] \end{align}$$

马尔科夫奖励过程

马尔科夫奖励过程是在马尔科夫过程基础上增加了奖励函数 $R$ 和衰减系数$\gamma$， 用$<S,R,P,\gamma>$表示。

• $R$: 表示 $S$ 状态下某一时刻的状态$S_t$ 在下一个时刻$ (t+1)$能获得的奖励的期望

$$R_s=E[R_{t+1}|S_t=s]$$

• $G_t$: 收获$G_t$为在一个马尔科夫奖励链上从t时刻开始往后所有的奖励的有衰减的收益总和

$$G_t = R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots+\gamma^{T-t-1}R_T$$

• $\gamma$：折扣因子$（discount\ factory \in [0,1]）$

  • 1、为了避免出现状态循环的情况

  • 2、系统对于将来的预测并不一定都是准确的，所以要打折扣

  • 很显然$\gamma$越靠近1，考虑的利益越长远。

• $V(s)$: 状态价值函数（state value function） 表示从从该状态开始的马尔科夫链收获$G_t$的期望

例子：对于如下状态，我们设定进入 $S_1$状态奖励为 $5$，进入$S_7$ 状态奖励为$10$，其余状态奖励为 $0$。则RR可以如下表示：$R=[5,0,0,0,0,0,10]$，折扣 因子 $\gamma$ 为 $0.5$。则对于下面两个马尔可夫过程获得的奖励为：

• $S4,S5,S6,S7:0 + 0.50 + 0.50 + 0.125 *10 = 1.25$

• $S4,S3,S2,S1:0 + 0.5 ×0 + 0.25×0 + 0.125×5 = 0.625$

在这里插入图片描述

Bellman Equation

$$\begin{align} v(s) &= \mathbb E[G_t|S_t=s] &收获的期望 \\ &= \mathbb E[R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots|S_t=s] \\ &= \mathbb E[R_{t+1}+\gamma(R_{t+2}+\gamma R_{t+3}+\cdots)|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] & v(S_{t+1})表示是收获的期望的期望 \\ \end{align}$$

即当前状态的值$v(s)$等于完成当前状态的奖励$R_{t+1}$以及下一步各状态的值的衰减和的期望。

使用贝尔曼方程状态价值$V$可以表示为：

$$V(s) = R(s) + \gamma \sum\limits_{s'\in S}P(s'|s)V(s')$$

$S$表示下一时刻的所有状态，$s' $表示下一时刻可能的状态

通过贝尔曼方程，可以看到价值函数$v(s)$有两部分组成，一个是当前获得的奖励的期望，即$R(s)$，另一个是下一时刻的状态期望，即下一时刻 可能的状态能获得奖励期望与对应状态转移概率乘积的和，最后在加上折扣。如下图所示，对于状态$s1$，它的价值函数为：

$$V(s_1)=R(s_1)+γ(0.1∗V(s_1)+0.2∗V(s_2)+0.7∗V(s_4))​$$

在这里插入图片描述

马尔可夫决策过程

马尔可夫决策过程（Markov Decision Process），即马尔可夫奖励过程的基础上加上action，即：Markov Chain + Reward + action。用股票为例子的话，我们只能每天看到股票价格的上涨或者下降，然后看到自己的收益，但是无法操作股票的价格的，只有看到份，只是一个“小散户”。这里的马尔可夫决策过程相当于政策的制定者，相当于一个操盘手，可以根据不同的状态而指定一些政策，也就相当于 action。

马尔可夫基础知识

马尔可夫决策过程由五元组组成$(S,A,P,\gamma,R)$：

• $S$：表示状态集合

• $A$：表示一组动作

• $P$：表示在某一状态$S_i$下，采取动作$A_i$，转移到$S_{i+1}$状态的概率，也就是说在确定的状态下采取相应的动作之后不能完全确定下一状态，而是以一定的概率确定下一状态，即$P_{ss'}^a=P(S_{t+1}=s'|S_t=s,A_t=a)$。

• $\gamma$：表示决策过程的一个阻尼系数，用户定义回报在决策过程中随时间打折扣，加快决策过程的收敛，$\gamma \in [0,1]$。

• $R$：表示奖励函数，$R(s)$描述了在状态$s$下执行某动作的期望(立即)奖励，$\mathcal R(s,a)=\mathbb E[R_{t+1}|S_t=s,A_t=a]$。

policy

用$\pi$表示策略的集合，其元素$ π(a|s)$表示某一状态 s 采取可能的行为 a 的概率

• Policy定义完整定义的个体行为方式，即包括了个体在各状态下的所有行为和概率

• 同时某一确定的Policy是静态的，与时间无关

• Policy仅和当前的状态有关，与历史信息无关，但是个体可以随着时间更新策略

在马尔科夫奖励过程中 策略 $π$ 满足以下方程，可以参照下面图来理解

$$状态转移概率：P^π(s′|s)=∑_{a∈A}π(a|s)P(s'|s,a)\\ 奖励函数：R^π(s)=∑_{a∈A}\pi(a|s)R(s,a)$$

状态转移概率可以描述为：在执行策略 $π$ 时，状态从$ s$ 转移至$ s' $的概率等于执行该状态下所有行为的概率与对应行为能使状态从 $s$ 转移至$ s’$ 的概率的乘积的和。

奖励函数可以描述为：在执行策略 $π $时获得的奖励等于执行该状态下所有行为的概率与对应行为产生的即时奖励的乘积的和。

在这里插入图片描述

引入策略，也可以理解为行动指南，更加规范的描述个体的行为，既然有了行动指南，要判断行动指南的价值，需要再引入基于策略的价值函数。

基于策略的状态价值函数（state value function）

• $V(s)$表示从状态 $s$开始，遵循当前策略时所获得的收获的期望

$$v_π(s)=E_π[G_t|S_t=s]$$

其中$G_t$ 可以参照马科夫奖励过程。我们有了价值衡量标准，如果状态$s$ 是一个好的状态，如何选择动作到达这个状态，这时就需要判断动作的好坏，衡量行为价值。

在某一个状态下采取某一个行为的价值，可以分为两部分：其一是离开这个状态的价值，其二是所有进入新的状态的价值于其转移概率乘积的和。参考下图右理解

• 由状态价值函数和行为价值函数的定义，可得两者的关系

$$v_π(s)=∑_{a∈A}π(a|s)⋅q_π(s,a)$$

我们知道策略就是用来描述各个不同状态下执行各个不同行为的概率，而状态价值是遵循当前策略时所获得的收获的期望，即状态 $s$ 的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和。参照下图左理解

在这里插入图片描述

• 上面两个公式组合可得 Bellman Expectation Equation

$$v_π(s)=∑_{a∈A}π(a|s)(R(s,a)+γ∑_{s′∈S}P(s′|s,a)⋅v_π(s′))\\ q_π(s,a)=R(s,a)+γ∑_{s′∈S}P(s′|s,a)⋅∑_{a′∈A}π(a′|s′)⋅q_π(s′,a′)$$

最优价值函数

解决强化学习问题意味着要寻找一个最优的策略让个体在与环境交互过程中获得始终比其它策略都要多的收获，这个最优策略我们可以用$ π∗ $表示。一旦找到这个最优策略$π∗$ ，那么我们就解决了这个强化学习问题。一般来说，比较难去找到一个最优策略，但是可以通过比较若干不同策略的优劣来确定一个较好的策略，也就是局部最优解。

我们一般是通过对应的价值函数来比较策略的优劣，也就是说，寻找较优策略可以通过寻找较优的价值函数来完成。可以定义最优状态价值函数是所有策略下产生的众多状态价值函数中的最大者，即：

$$V_*(s) = max_{\pi}V_{\pi}(s)$$

同理也可以定义最优动作价值函数是所有策略下产生的众多动作状态价值函数中的最大者，即：

$$q_*(s,a) = max_{\pi}q_\pi(s,a)$$

我们可以最大化最优行为价值函数找到最优策略：

\pi^*(a|s)= \left\{ \begin{array}{**lr**} 1, & if\ a=argmax\ q_{*}(s,a) \\ 0, & otherwise\\ \end{array} \right.

Bellman Optimality Equation

只要我们找到了最大的状态价值函数或者动作价值函数，那么对应的策略$ π∗$就是我们强化学习问题的解。同时，利用状态价值函数和动作价值函数之间的关系，我们也可以得到

$$v_*(s) = max_aq_*(s,a)$$

当到达 最优的时候，一个状态的价值就等于在当前 状态下最大的那个动作价值。

$$q_*(s,a)=R(s,a)+\gamma\sum_{s'\in S}P^a_{s's}\cdot V_*(S')$$

把上面两个式子结合起来有Bellman Optimality Equation

$$v_*(S)=max_a(R(s,a)+\gamma\sum_{s'\in S}P^a_{s's}\cdot v_*(s')) \\ q_*(s,a) = R(s,a)+\gamma\sum_{s'\in S}P^a_{s's}\cdot max_{a'}q^*(s',a')$$

MDP 实例

下面给出一个例子，希望能能好的理解MDP过程

UIHumq.png

例子是一个学生学习考试的MDP。里面左下那个圆圈位置是起点，方框那个位置是终点。上面的动作有study, pub, facebook, quit, sleep，每个状态动作对应的即时奖励R已经标出来了。我们的目标是找到最优的动作价值函数或者状态价值函数，进而找出最优的策略。

为了方便，我们假设衰减因子$γ=1,π(a|s)=0.5$

对于终点方框位置，由于其没有下一个状态，也没有当前状态的动作，因此其状态价值函数为$0$。对于其余四个状态，我们依次定义其价值为$v1,v2,v3,v4 $分别对应左上，左下，中下，右下位置的圆圈。我们基于

来计算所有状态的价值函数，可以得到如下方程组

• 对于$ v_1: v1=0.5∗(−1+v1)+0.5∗(0+v2)$

• 对于$ v_2: v2=0.5∗(−1+v1)+0.5∗(−2+v3)$

• 对于 $v_3: v3=0.5∗(0+0)+0.5∗(−2+v4)$

• 对于 $v_4: v4=0.5∗(10+0)+0.5∗(1+0.2∗v2+0.4∗v3+0.4∗v4)$

解这个方程组可得：$v1=−2.3,v2=−1.3,v3=2.7,v4=7.4$ 既是每个状态的价值函数

UIHM7V.png