马尔可夫决策过程（1）

4.1简介

马尔可夫决策过程(Markov decision process, MDP)是强化学习的重要概念。前面两章所讲的环境其实就是一个马尔可夫决策过程。我们之前讲到的老虎机问题不算一个MDP问题，是因为MDP还包括状态信息以及状态信息之间的转移。MDP是强化学习问题在数学上的理想化形式，他其实就是一种通过交互式学习来实现目标的理论框架。这个框架我们可以理解成在写作文时，都需要有开头、主要内容、结尾一样。如果我们准备用强化学习去解决一个问题，第一个关键步骤就是要将实际问题抽象为一个MDP(PS:为了图方便，所有的马尔可夫决策过程后续我都写成MDP了)，也就是明确马尔可夫决策过程的各个组成要素。

为了更好地理解MDP，所以我们将会从马尔科夫过程(不是马尔可夫决策过程)进行，逐渐深入，引出MDP。

4.2马尔可夫过程

4.2.1 随机过程

为什么要提一下随机过程呢，因为马尔可夫过程是一种特定类型的随机过程。随机过程的研究对象是随时间演变的随机现象(例如天气随时间变化、大陆漂移等等)。在随机过程里面，随机现象在某时刻 $t$ 的取值是一个向量随机变量，用 $S_t$ 表示。刚才提到的天气变化等随机现象就hi状态的变化过程。随机过程中当前时刻的状态 $S_t$ 一般取决于之前所有时刻的状态 $\{S_1,S_2,...S_{t-1}\}$ .我们已知历史状态信息 $(S_1,S_2,...,S_t)$ 时，下一个时刻状态为 $S_{t+1}$ 的概率表示成 $P(S_{t+1} | S_1,...,S_t)$ .这句话也很好理解，医生在观察住院病人情况时，不能只根据病人昨天的状态判断今天状态，而是要根据住院以来或者近一段时间情况分析。

4.2.2 马尔可夫性质

当且仅且某时刻的状态只取决于上一个时刻的状态时，一个随机过程被称为马尔可夫性质，用公式来表示即为 $P(S_{t+1}|S_t) = P(S_{t+1}|S_1,S_2,...S_t)$ .也就是讲，下一时刻状态只取决于当前状态，而不会受到过去状态的影响。但是强调一下:具有马尔可夫性质的随机过程就和历史状态无关了。虽然 $t+1$ 的状态只与 $t$ 时刻状态相关，但 $t$ 时刻状态是与其实包含了 $t-1$ 时刻的状态信息，以此类推。通过链式传递的关系，历史的信息被传递到 $t+1$ 时刻。马尔可夫性质大大简化了运算，因为只要当前的状态可知，历史信息都可以不用知道，利用当前信息就可以决定未来。

4.2.3 马尔可夫过程

具有马尔可夫性质的随机过程被称为马尔可夫过程，也被称为马尔科夫链。通常用元组 $<S,P>$ 描述一个马尔可夫过程，其中 $S$ 是有限数量的状态集合， $P$ 是状态转移矩阵。 $P$ 指的是从一个状态到另一个状态的概率。假设一共有 $n$ 个状态，此时 $S = \{s_1,s_2,...,s_n\}$ ,状态转移矩阵 $P$ 定义了所有状态对之间的转移概率，即

$\mathbb{P} = \begin{bmatrix} P(s_1|s_1) & \cdots & P(s_n|s_1) \\ \vdots & \ddots & \vdots \\ P(s_1|s_n) & \cdots & P(s_n|s_n) \end{bmatrix}$

矩阵 $P$ 中第 $i$ 行和第 $j$ 列元素 $P(s_j|s_i)$ $= P(S_{t+1}=s_j | S_t = s_i)$ 表示从状态 $s_i$ 转移到 $s_j$ 的概率，我们称 $P(s'|s)$ 为状态转移函数。从某个状态出发，到达其他状态的概率和必须为1，即状态转移矩阵 $P$ 的每一行的和为1.

上图是一个具有6个状态 $\{s_1,s_2,s_3,s_4,s_5,s_6\}$ ，绿色圆圈表示一个状态，每个状态都有一定概率(包括概率0)转移到其他状态，其中 $s_6$ 被称为终止状态，因为他不会在转移到其它状态，可以理解为永远以概率1转移到自己，状态之间的虚线箭头表示状态的转移，箭头旁的数字表示该状态转移发生的概率。从每个状态出发转移到其它概率总和为1.例如， $s_1$ 有90%的概率保持不变，有10%的概率转移到 $s_2$ ， $s_6$ 就是100%到自己。

可以写出这个状态转移图的马尔可夫过程的状态转移矩阵:

$\mathbb{P} = \begin{bmatrix} 0.9 & 0.1 & 0 & 0 & 0 & 0\\ 0.5 & 0 & 0.5 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0.6 & 0.4 \\ 0 & 0 & 0 & 0 & 0.3 & 0.7 \\ 0 & 0.2 & 0.3 & 0.5 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$

其中第 $i$ 行 $j$ 列的值 $P_{i,j}$ 则代表从状态 $s_i$ 转移到 $s_j$ 的概率。

给定一个马尔可夫过程，我们就可以从某个状态出发，根据他的状态转移矩阵生成一个状态序列，这个步骤也被叫做采样。例如，从 $s_1$ 出发，可以生成序列 $s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_6$ 或者序列 $s_1 \rightarrow s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \rightarrow s_5 \rightarrow s_3 \rightarrow s_6$ 等。生成这些序列的概率和状态转移矩阵有关。

4.3马尔可夫奖励过程

在马尔科夫过程的基础上加入奖励函数 $r$ 和折扣因子 $\gamma$ ,就可以得到一个马尔可夫奖励过程（Markov reward process）。一个马尔可夫奖励过程由 $<S,P,r, \gamma>$ 构成，各个元素含义如下所示:

$S$ 是有限状态的集合。
$P$ 是状态转移矩阵。
$r$ 是奖励函数，某个状态 $s$ 的奖励 $r(s)$ 指转移到该状态时可以获得奖励的期望。
$\gamma$ 是折扣因子（discount factor），取值范围为[0,1)。引入折扣因子的理由为远期利益具有一定不确定性，有时我们更希望能够尽快获得一些奖励，所以我们需要对远期利益打一些折扣。接近 1 的 $\gamma$ 更关注长期的累计奖励，接近 0 的 $\gamma$ 更考虑短期奖励.

4.3.1 回报

在一个马尔可夫奖励过程中，从第 $t$ 时刻状态 $S_t$ 开始，直到终止状态时，所有奖励的衰减之和称为回报 $G_t$ （Return），公式如下：

$G_t = R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k}$

其中， $R_t$ 表示在时刻获得的奖励。在下图中，我们继续沿用马尔可夫过程的例子，并在其基础上添加奖励函数，构建成一个马尔可夫奖励过程。例如，进入状态 $s_2$ 可以得到奖励-2，表明我们不希望进入 $s_2$ ，进入 $s_4$ 可以获得最高的奖励10，但是进入 $s_6$ 之后奖励为零，并且此时序列也终止了。

比如选取 $s_1$ 为起始状态，设置 $\gamma = 0.5$ ，采样到一条状态序列为 $s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_6$ ，就可以计算 $s_1$ 的回报 $G_1$ ，得到 $G_t = -1 +0.5*(-2) + 0.5^2 *-2 = -2.5$ 。

接下来我们用代码表示图中的马尔可夫奖励过程，并且定义计算回报的函数。

import numpy as np
np.random.seed(0)
# 定义状态转移概率矩阵P
P = [
    [0.9, 0.1, 0.0, 0.0, 0.0, 0.0],
    [0.5, 0.0, 0.5, 0.0, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.6, 0.0, 0.4],
    [0.0, 0.0, 0.0, 0.0, 0.3, 0.7],
    [0.0, 0.2, 0.3, 0.5, 0.0, 0.0],
    [0.0, 0.0, 0.0, 0.0, 0.0, 1.0],
]
P = np.array(P)

rewards = [-1, -2, -2, 10, 1, 0]  # 定义奖励函数
gamma = 0.5  # 定义折扣因子


# 给定一条序列,计算从某个索引（起始状态）开始到序列最后（终止状态）得到的回报
def compute_return(start_index, chain, gamma):
    G = 0
    for i in reversed(range(start_index, len(chain))):
        G = gamma * G + rewards[chain[i] - 1]
    return G


# 一个状态序列,s1-s2-s3-s6
chain = [1, 2, 3, 6]
start_index = 0
G = compute_return(start_index, chain, gamma)
print("根据本序列计算得到回报为：%s。" % G)

根据本序列计算得到回报为：-2.5。

4.3.2 价值函数

在马尔可夫奖励过程中，一个状态的期望回报(即从这个状态出发的未来累计奖励的期望)被称为这个状态的价值。所有状态的价值就组成了价值函数。价值函数的输入为某个状态，输出为这个状态的价值。我么讲价值函数写成 $V(s) = E[G_t|S_t = s]$ ，展开为:

$V(s) = E[G_t \mid S_t = s] \\ = E[R_t + \gamma R_{t+1} + \gamma^2 R_{t+2} + \cdots \mid S_t = s] \\ = E[R_t + \gamma (R_{t+1} + \gamma R_{t+2} + \cdots) \mid S_t = s] \\ = E[R_t + \gamma G_{t+1} \mid S_t = s] \\ = E[R_t + \gamma V(S_{t+1}) \mid S_t = s]$

在上式的最后一个等号中，一方面，即时奖励的期望正式奖励函数的输出，即 $E[R_t|S_t = s] = r(s)$ ；另一方面，等式中剩余部分 $E[\gamma V(S_{t+1}) | S_t = s]$ 可以从状态 $s$ 出发的转移概率得到，即可以得到 $V(s) = r(s) + \gamma \sum_{s' \in S} p(s' \mid s) V(s')$ ，这个公式就是马尔可夫奖励过程中的贝尔曼方程。对每一个状态都成立。若一个马尔科夫奖励过程一共有 $n$ 个状态，即 $S = \{s_1, s_2, s_3,...s_n\}$ ,我们将所有状态的价值表示成一个列向量 $V = [V(s_1), V(s_2),...V(s_n)]^T$ ,同理，将奖励函数写成一个列向量 $R = [r(s_1), r(s_2), ...,r(s_n)]^T$ ,于是，我们可以将贝尔曼方程写成矩阵的形式:

根据矩阵运算求解，得到下面的解析解:

以上解析解的计算复杂度是 $O(n^3)$ ，其中 $n$ 是状态个数，因此这种方法只适用很小的马尔可夫奖励过程。求解较大规模的马尔可夫奖励过程中的价值函数时，可以使用动态规划（dynamic programming）算法、蒙特卡洛方法（Monte-Carlo method）和时序差分（temporal difference），这些方法将在之后的章节介绍。

接下来编写代码实现求解价值函数的解析解方法，并根据此计算该马尔科夫奖励过程中所有状态的价值。

def compute(P, rewards, gamma, states_num):
    ''' 利用贝尔曼方程的矩阵形式计算解析解,states_num是MRP的状态数 '''
    rewards = np.array(rewards).reshape((-1, 1))  #将rewards写成列向量形式
    value = np.dot(np.linalg.inv(np.eye(states_num, states_num) - gamma * P),
                   rewards)
    return value


V = compute(P, rewards, gamma, 6)
print("MRP中每个状态价值分别为\n", V)

MRP中每个状态价值分别为
 [[-2.01950168]
 [-2.21451846]
 [ 1.16142785]
 [10.53809283]
 [ 3.58728554]
 [ 0.        ]]

根据以上代码，求解得到各个状态的价值 $V(s)$

4.4 总结

本章第一部分从随机过程引出了马尔可夫过程，并介绍了马尔可夫性质；以及马尔可夫奖励过程的回报和价值函数的概念。在下一章，将会介绍马尔可夫决策过程(MDP)的策略，状态价值函数、动作价值函数、贝尔曼期望方程、贝尔曼最优方程、蒙特卡洛方法等内容

标签：状态,0.0,决策,奖励,马尔可夫,过程,转移
From： https://blog.csdn.net/qq_45481856/article/details/140245672

马尔可夫决策过程（1）

4.1简介

4.2马尔可夫过程

4.2.1 随机过程

4.2.2 马尔可夫性质

4.2.3 马尔可夫过程

4.3马尔可夫奖励过程

4.3.1 回报

4.3.2 价值函数

4.4 总结

相关文章

赞助商

阅读排行

马尔可夫决策过程 （1）

4.1简介

4.2马尔可夫过程

4.2.1 随机过程

4.2.2 马尔可夫性质

4.2.3 马尔可夫过程

4.3马尔可夫奖励过程

4.3.1 回报

4.3.2 价值函数

4.4 总结

相关文章

赞助商

阅读排行

马尔可夫决策过程（1）