第二章：Markov 决策过程（Markov Decision Process, MDP）

强化学习中最经典、最重要的数学模型就是Markov 决策过程（Markov Decision Process, MDP），本章将导出 Markov 决策过程模型，并介绍相关性质，最后给出一种求解 Markov 决策过程最优策略的方法。

一、Markov 决策过程模型

一个时间离散化的智能体与环境的交互轨迹（trajectory）可表示为：$S_0,O_0,A_0,R_1,S_1,O_1,A_1,R_2,S_2...$。若智能体可以完全观测到环境的状态，即环境是完全可观测的，不失一般性的，可令 $O_t=S_t\ (t=0,1,2,3,...)$，那么轨迹可表示为：$S_0,A_0,R_1,S_1,A_1,R_2,S_2,...$。部分不完全可观测的问题可以建模为部分可观测的 Markov 决策过程（Partially Observable Markov Decision Process, POMDP）。

引入概念定义：$\textrm {Pr}\left(S_{t+1}=s',R_{t+1}=r \mid S_t=s,A_t=a\right)$ 为在时间 $t$ ，动作 $A_t=a$ 情况下，从状态 $S_t=s$ 转移到 $S_{t+1}=s'$ 且获得奖励 $R_{t+1}=r$ 的概率，就可以得到 Markov 决策过程模型。在该定义下，下一状态 $S_{t+1}$ 和奖励 $R_{t+1}$ 只依赖于当前状态 $S_t$ 和动作 $A_t$ ，而不依赖于更早的状态和动作，这种性质称为 Markov 性。

若状态空间 $\mathcal S$、动作空间 $\mathcal A$、奖励空间 $\mathcal R$ 都是元素个数有限的集合，这样的 Markov 决策过程称为有限 Markov 决策过程（Finite Markov Decision Process, Finite MDP）。Markov 决策过程的环境由动力刻画，对于有限 Markov 决策过程，定义函数 $p：\mathcal S \times \mathcal R \times \mathcal S \times \mathcal A → [0, 1]$ 为 Markov 决策过程的动力（dynamics）：

利用动力的定义 $\eqref{eq:1}$ 可以导出：

• 状态转移概率：

• 给定“状态 - 动作”的期望奖励：

• 给定“状态 - 动作 - 下一状态”的期望奖励：

对于不是有限 Markov 决策过程的 Markov 决策过程，可以用类似的方法定义动力函数与导出量，只是定义时应当使用概率分布函数。动力的定义将离散空间和连续空间的情况用统一的字母表述，简化了书写。

在 Mrokov 决策过程中，定义策略（policy）为从状态到动作的转移概率。对于有限 Markov 决策过程，可以定义策略 $\pi：\mathcal S \times \mathcal A \rightarrow [0, 1]$ 为：

这种策略称为随机性策略。对于动作集为连续的情况，可以用概率分布来定义策略。若策略为 $\pi：\mathcal S \rightarrow \mathcal A$ ，即定义：$\pi\left(s\right)=a,\ \ s \in \mathcal S,a \in \mathcal A$ ，则该策略称为确定性策略。

强化学习的核心概念是奖励，强化学习的目标是最大化长期的奖励，下面来定义这个长期的奖励。对于回合制任务，假设回合在 $T$ 步终止，则从步骤 $t\ (t<T$) 以后的回报（return）：

对于连续性任务，引入折扣（discount）概念，定义回报为：

其中折扣因子 $\gamma \in [0, 1]$ 。折扣因子决定了如何在最近的奖励和未来的奖励间进行折中：$\gamma=0$ 只考虑眼前利益，$\gamma=1$未来和当前一样重要，一般设定 $\gamma \in (0, 1)$ ，此时若奖励有界，则回报也是有界的。

基于回报的定义，可以进一步定义价值函数（value function）。对于给定的策略 $\pi$ ，可以定义一下价值函数：

• 状态价值函数（state value function）：状态价值函数 $v_\pi\left(s\right)$ 表示从状态 $s$ 开始采用策略 $\pi$ 的预期回报。

• 动作价值函数（action value function）：动作价值函数 $q_\pi\left(s, a\right)$ 表示在状态 $s$ 采取动作 $a$ 后，采用策略 $\pi$ 的预期回报。

二、Bellman 期望方程

策略评估（policy evaluation）：试图求解给定策略的价值函数（Bellman 期望方程常用来进行策略评估）。

状态价值函数和动作价值函数之间可以互相表示，它们的的关系及推导如下：

从状态价值和动作价值的互相表示出发，用代入法消除其中一种价值，就可以得到 Bellman 期望方程：

• 状态价值函数表示：

• 动作价值函数表示：

三、最优策略及其性质

定义一个偏序关系：对于策略 $\pi$ 和 $\pi'$ ，如果对于任意 $s \in \mathcal S$ 都满足 $v_\pi\left(s\right) \leq v_{\pi'}\left(s\right)$ ，则称策略 $\pi$ 小于等于 $\pi'$ ，记做 $\pi \leq \pi'$ 。如果动作空间 $\mathcal A \left(s\right) \left(s \in \mathcal S\right)$ 是闭集，那么就存在一个策略 $\pi_*$ ，使得所有的策略都小于等于这个策略，此时的策略 $\pi_*$ 就称为最优策略（optimal policy）。最优策略的价值函数称为最优价值函数，包括以下两种形式：

• 最优状态价值函数（optimal state value function）：$v_*\left(s\right)=\max\limits_\pi\ v_\pi\left(s\right), \qquad s \in \mathcal S$
• 最优动作价值函数（optimal action value function）：$q_*\left(s, a\right)=\max\limits_\pi\ q_\pi\left(s, a\right), \qquad s \in \mathcal S, a \in \mathcal A$

最优策略可能存在多个，但其价值函数是相同的，任取一个最优策略来考察也不是一般性。其中一种选取方法是选择这样的一种确定性策略：

其中若有多个动作使得 $q_*\left(s, a\right)$ 取得最大值，则任取一个动作。将以上确定性策略带入状态价值和动作价值的互相表示表达式中有：

同 Bellman 期望方程的推导，将上两式相互代带入，即可得到 Bellman 最优方程：

• 最优状态价值函数表示：

• 最优动作价值函数表示：

将 $v_*\left(s\right)=\max\limits_{a \in \mathcal A}\ q_*\left(s, a\right),\ (s \in \mathcal S)$ 松弛为 $v_*\left(s\right) \geq q_*\left(s, a\right),\ (s \in \mathcal S, a \in \mathcal A(s))$ ，并消去 $q_*\left(s, a\right)$ 以减少决策变量，即可得到一个线性规划：

其中 $c\left(s\right),\ (s \in \mathcal S)$ 是一组任意取值的正实数。Bellman 最优方程的解显然在线性规划的可行域内，而且由于 $c\left(s\right) > 0$ ，所以线性规划的最优解肯定会让约束条件中的某些不等式取到等号，使得 Bellman 最优方程成立。可以证明，这个线性规划的最优解满足 Bellman 最优方程。

但实际上使用 Bellman 最优方程求解最优策略可能会遇到下列困难：

• 难以列出 Bellman 最优方程。列出 Bellman 最优方程要求对动力系统完全了解，并且动力系统必须可以用有 Markov 性的 Markov 决策过程来建模。在实际问题中，环境往往十分复杂，很难非常周全地用概率模型完全建模。
• 难以求解 Bellman 最优方程。在实际问题中，状态空间往往非常巨大，状态空间和动作空间的组合更是巨大。这种情况下，没有足够的计算资源来求解 Bellman 最优方程。所以这时候会考虑采用间接方法求解最优价值函数的值，甚至是近似值。

四、案例：悬崖寻路（CliffWalking-v0）

使用 gym 库中的悬崖寻路问题（CliffWalking-v0）作为案例分析，该环境是一个有限 Markov 决策过程，该环境的信息和交互过程可以通过本人学习代码中的 get_env_info 和 run_episode 函数来了解。下面将使用 Bellman 期望方程来对策略进行评估，以及使用线性规划求解 Bellman 最优方程来获得最优策略。

在该案例中，到达下一个状态的奖励是确定的，即公式 $\eqref{eq:3}$ 可写为 $\displaystyle r\left(s,a\right)=\sum_{s'} rp\left(s' \mid s,a\right)$ ，再代入到根据用状态价值函数表示的 Bellman 期望方程 $\eqref{eq:12}$ ，并化为方程组的标准形式有：

根据该公式，将所有参数代入即可得到一个线性方程组，求解该线性方程组即可得到状态价值函数的解。在求解状态价值函数后，将改写的 $r\left(s,a\right)$ 带入到公式 $\eqref{eq:11}$ 中，即可求得动作价值函数：

该案例的策略评估代码实现如下。为求解线性方程组 $\eqref{eq:20}$ ，先根据已知的环境模型 env 和策略 policy 参数求出系数矩阵 a 和向量 b（ 2~8 行），再通过 np.linalg.solve 函数求解线性方程组 $ax=b$ 得到状态价值函数 v ；然后再次结合已知参数，通过公式 $\eqref{eq:21}$ 求出动作价值函数 q（ 11~14 行）。

1
def evaluate_policy(env, policy, gamma=1.0):
2
    a, b = np.eye(env.nS), np.zeros((env.nS))
3
    for state in range(env.nS - 1):
4
        for action in range(env.nA):
5
            pi = policy[state][action]
6
            for proba, next_state, reward, done in env.P[state][action]:
7
                a[state, next_state] -= gamma * pi * proba
8
                b[state] += pi * reward * proba
9
    v = np.linalg.solve(a, b)
10
    q = np.zeros((env.nS, env.nA))
11
    for state in range(env.nS - 1):
12
        for action in range(env.nA):
13
            for proba, next_state, reward, done in env.P[state][action]:
14
                q[state][action] += (proba * (reward + gamma * v[next_state]))
15
    return v, q

将线性规划 $\eqref{eq:19}$ 中的 $c\left(s\right),\ (s \in \mathcal S)$ 全都设置为 1 ，并将改写的 $r\left(s,a\right)$ 带入到公式中，再转化为标准形式有：

然后使用 scipy.optimize.linprog 函数来计算该动态问题，代码如下。该函数第一个参数为系数 $c\left(s\right)$ ，全部设置为 1 （ 第9 行）；第二、三个参数为形如 “$Ax \leq b$” 这样的不等式约束的系数矩阵 $A$ 和向量 $b$ 的值，线性规划 $\eqref{eq:22}$ 的不等式约束转化为 $\leq$ 表示后，在代码中的系数矩阵 $A$ 为 a_ub 和向量 $b$ 为 b_ub；关键字参数 bounds 指定决策变量是否有界；关键字参数 method 确定优化方法，因默认的方法不能处理不等式约束，所以这里选择了能够处理不等式约束的内点法（interior-point method）。最后求解出最优状态价值函数为 optimal_v 及最优动作价值函数为 optimal_q。

xxxxxxxxxx
16
1
def get_optimal_value_func(env, gamma=1.0):
2
    p = np.zeros((env.nS, env.nA, env.nS))
3
    r = np.zeros((env.nS, env.nA))
4
    for state in range(env.nS - 1):
5
        for action in range(env.nA):
6
            for proba, next_state, reward, done, in env.P[state][action]:
7
                p[state, action, next_state] += proba
8
                r[state, action] += (reward * proba)
9
    c = np.ones(env.nS)
10
    a_ub = gamma * p.reshape(-1, env.nS) - np.repeat(np.eye(env.nS), env.nA, axis=0)
11
    b_ub = -r.reshape(-1, )
12
    bounds = [(None, None),] * env.nS
13
    res = scipy.optimize.linprog(c, a_ub, b_ub, bounds=bounds, method='interior-point')
14
    optimal_v = res.x
15
    optimal_q = r + gamma * np.dot(p, optimal_v)
16
    return optimal_v, optimal_q

得到最优动作价值函数后，再由公式 $\eqref{eq:14}$ 可以得到一种最优确定性策略，代码为：

xxxxxxxxxx
2
1
optimal_v, optima_q = get_optimal_value_func(env)
2
optimal_policy = optimal_q.argmax(axis=1)