Markov决策过程（MDP）是强化学习的基础模型，是一种通过与环境交互从而学习一个策略，实现最大化累积奖励的理论框架。MDP的数学模型由状态空间、动作空间、转移概率和奖励函数组成。时至今日，MDP已经成为强化学习的标准模型，被广泛应用于各个领域，包括机器人控制、游戏AI和自动驾驶等。

1.1 基本定义#

1.1.1 智能体、环境与策略#

智能体 (agent): 通过与环境交互来学习和优化策略的实体。
环境 (environment): 智能体所处的外部世界，智能体通过与环境交互来获取信息和奖励。
状态 (state) $s_t$ : 环境在某一时刻的具体情况。
动作 (action) $a_t$ : 智能体在某一状态下可以采取的操作。
策略 (policy) $\pi(a|s)$ : 智能体在某一状态下选择动作的概率分布，通常用一个函数表示。
奖励 (reward) $r(s, a)$ : 智能体在某一状态下采取某一动作后，环境反馈给智能体的即时奖励。

具体来说，在每个时刻 $t$ ，智能体会和环境进行交互，即通过观察当前所在的环境状态 $s_t$ ，选择一个动作 $a_t$ ，得到环境对于状态 $s_t$ 和动作 $a_t$ 的奖励 $r_t$ ，之后智能体会转移到下一个状态 $s_{t+1}$ 。

1.1.2 轨迹、动作选择与状态转移#

上述过程逐步迭代进行，可以得到一个轨迹 $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots)$ ，其中 $s_t$ 是在时刻 $t$ 的状态， $a_t$ 是在时刻 $t$ 采取的动作， $r_t$ 是在时刻 $t$ 得到的奖励。

轨迹 (trajectory) $\tau$ : 智能体与环境交互的序列，包括状态、动作和奖励等信息，表示为 $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots)$ 。

由于在每个时刻 $t$ ，智能体都有可能有多个动作可供选择，而且每个动作导致的状态转移和奖励也可能不同，因此在每个时刻 $t$ ，智能体的动作选择、状态转移和奖励都可以用随机过程来表示。为了便于分析，整个决策过程使用 Markov 决策过程（MDP）来建模。 MDP的 Markov性体现在以下几个方面

状态转移概率 $p(s_{t+1} | s_t, a_t)$ : 在时刻 $t$ ，智能体在状态 $s_t$ 下采取动作 $a_t$ 后，转移到下一个状态 $s_{t+1}$ 的概率，这里的历史依赖性被简化为只依赖于当前状态和动作。此外，在通常情况下，我们认为环境是定常的而非时变的，此时动作转移概率也可以是定常的。那么动作转移概率可以去掉时间下标 $t$ ，表示为 $p(s'|s, a)$ ，表示在状态 $s$ 下采取动作 $a$ 后转移到状态 $s'$ 的概率。
动作选择概率 $p(a_t | s_t) = \pi(a_t|s_t)$ : 在状态 $s_t$ 下，智能体选择动作 $a_t$ 的概率分布，也就是策略函数。策略可以是确定性的，也可以是随机的。动作的选择不依赖于历史状态和动作，只依赖于当前状态。
奖励概率 $p(r_t | s_t, a_t)$ : 在状态 $s_t$ 下，智能体采取动作 $a_t$ 后，环境反馈给智能体的奖励。奖励是一个随机变量，表示为 $r_t \sim p(r_t | s_t, a_t)$ 。

需要注意的是，状态转移概率和奖励概率本质是环境的模型，而非智能体的属性。只有策略也就是动作选择概率是智能体的属性。 换言之，只要状态转移概率和奖励概率确定，一个环境模型也就确定了；而一个动作策略函数确定，一个智能体也就确定了。

1.1.3 分幕式任务#

终止状态 (terminal state): 智能体与环境交互的过程中的一个特殊状态，表示任务的结束。终止状态通常是一个吸收状态，智能体在达到终止状态后，不会再进行任何动作和奖励的反馈。
非终止状态 (non-terminal state): 智能体与环境交互的过程中的普通状态，表示任务的继续进行。非终止状态通常是一个非吸收状态，智能体在达到非终止状态后，可以继续进行动作和奖励的反馈。
幕 (episode): 智能体与环境交互的完整过程，从初始状态到终止状态（每幕的最后一个状态必须是终结状态）的序列，表示为 $\tau = (s_0, a_0, r_0, s_1, a_1, r_1, \dots, s_T)$ ，其中 $T$ 是终止时刻。
分幕式任务 (episodic task): 智能体与环境交互的任务是有限的，智能体在每个幕中都要完成一个特定的目标。分幕式任务通常有一个明确的终止状态，智能体在达到终止状态后，任务结束。不同幕之间是独立的，下一幕的初始状态与上一幕的终止状态无关。例如，下象棋，打掼蛋等游戏，每一局游戏就是单独的一幕。
非分幕式任务 (continuing task): 智能体与环境交互的任务是无限的，智能体在每个时刻都要完成一个特定的目标。非分幕式任务通常没有明确的终止状态，智能体在每个时刻都要继续与环境交互。

1.1.4 回报与价值函数#

MDP 的目标是最大化智能体在整个决策过程中的累积奖励。累积奖励可以用回报（return）来表示，回报是从当前时刻开始的未来奖励的加权和。回报的计算方式通常是将未来的奖励进行折扣处理，以便更好地平衡当前奖励和未来奖励的重要性。

折扣因子 $\gamma$ : 用于平衡当前奖励和未来奖励的重要性，通常取值在 $[0, 1]$ 之间。 $\gamma$ 越大，表示未来奖励越重要，智能体也会相应地更加目光长远； $\gamma$ 越小，表示当前奖励越重要，智能体也会相应地更加目光短浅。折扣因子 $\gamma$ 的取值通常是一个小于 1 的正数，表示未来奖励的衰减程度。 $\gamma = 0$ 表示只考虑当前奖励， $\gamma = 1$ 表示考虑所有未来奖励。
回报 (return) $G_t$ : 从时刻 $t$ 开始的回报，通常表示为

\begin{align*} G_t &= \sum_{l=0}^{\infty} \gamma^l r_{t + l}\\ &= r_t + \gamma r_{t + 1} + \gamma^2 r_{t + 2} + \dots \\ &= r_t + \gamma G_{t + 1} \\ \end{align*}

其中 $r_{t + l}$ 是在时刻 $t + l$ 的奖励。

对于分幕式任务，我们可以把终止状态后续的奖励视为 0，且智能体在原状态保持不变（这只是为了统一公式，便于把分幕式任务看作是持续性任务，不过把下面的表达式也可以视作对分幕式任务的回报定义），此时回报表示为从初始状态开始，到终止状态结束的折扣奖励和，表示为

\begin{align*} G_t &= \sum_{l=0}^{T - t} \gamma^l r_{t + l}\\ &= r_t + \gamma r_{t + 1} + \gamma^2 r_{t + 2} + \dots + \gamma^{T - t} r_T \\ &= r_t + \gamma G_{t + 1} \\ \end{align*}

其中 $T$ 是终止时刻。

很显然，这些奖励都是随机变量，因此回报 $G_t$ 也是一个随机变量。为了便于分析，我们需要使用期望来分析回报。不过，从不同的初始状态出发，智能体得到的回报通常是不同的，所以我们会使用价值函数来描述这种不同状态或状态-动作下的期望回报。

状态价值函数 $V_\pi(s)$ : 在状态 $s_t = s$ 下，智能体在策略 $\pi$ 下的预期回报（关于 $s_t = s$ 的条件期望），表示为

V_\pi(s) = \mathbb{E}_\pi[G_t | s_t = s] = \mathbb{E}_{a_t \sim \pi(a_t | s) , s_{t+1} \sim p(s_{t+1} | s, a_t), r_t \sim p(r_t | s, a_t), a_{t+1} \sim \pi(a_{t+1} | s_{t+1}), \dots} [\sum_{l=0}^{\infty}\gamma^l r_{t + l}]

上式对任意的状态 $s$ 均满足，因为在 $t$ 时刻，智能体可能处于状态空间中的任意一个状态。此外，此式对任意时刻 $t$ 均满足，如果环境模型是非时变的。下标 $\pi$ 是为了体现这个期望是与策略 $\pi$ 有关的，策略不同，得到的期望可能不同。

动作价值函数 $Q_\pi(s, a)$ : 在状态 $s_t = s$ 下采取动作 $a_t = a$ 后，智能体在策略 $\pi$ 下的预期回报，表示为

Q_\pi(s, a) = \mathbb{E}_\pi[G_t | s_t = s, a_t = a] = \mathbb{E}_{s_{t+1} \sim p(s_{t+1} | s, a), r_t \sim p(r_t | s, a), a_{t+1} \sim \pi(a_{t+1} | s_{t+1}), \dots} [\sum_{l=0}^{\infty}\gamma^l r_{t + l}]

上式对任意的状态 $s$ 和动作 $a$ 均满足，因为在 $t$ 时刻，智能体可能处于状态空间中的任意一个状态，并且可能采取动作空间中的任意一个动作。同样地，此式对任意时刻 $t$ 均满足，如果环境模型是非时变的。下标 $\pi$ 是为了体现这个期望是与策略 $\pi$ 有关的，策略不同，得到的期望可能不同。

优势函数 $A_\pi(s_t, a_t)$ : 在状态 $s_t$ 下，采取动作 $a_t$ 的优势程度，表示为

A_\pi(s, a) = Q_\pi(s, a) - V_\pi(s)

优势函数的作用是用来衡量某个动作相对于其他动作的优势程度。优势函数可以用来指导智能体在选择动作时，优先选择那些具有较高优势的动作，从而提高学习效率。优势函数的值越大，表示该动作相对于其他动作的优势程度越高，智能体在选择动作时应该优先考虑该动作。

这是因为状态价值函数是动作价值函数关于动作的期望，即

V_\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a|s) Q_\pi(s, a)

其中 $\mathcal{A}(s)$ 是状态 $s$ 的动作空间。于是优势函数可以看作零均值化的动作价值函数。

需要注意的是，当环境模型和智能体策略确定时，状态价值函数 $V_\pi(s)$ 和动作价值函数 $Q_\pi(s, a)$ 是确定的，体现出价值函数是策略的函数，这点可以从定义中得到。价值函数会满足 Bellman 期望方程，通过求解方程可以得到价值函数的唯一解，从而说明价值函数是确定的。

1.2 Bellman期望方程#

Bellman期望方程（Bellman方程）是强化学习中的一个重要概念，它描述了在给定策略下，价值函数在不同时刻的值之间的关系。Bellman方程可以用来递归地计算状态价值函数和动作价值函数，从而实现动态规划。

在给定策略 $\pi$ 下，状态价值函数的Bellman期望方程为

V_\pi(s) = \mathbb{E}_\pi[r_t + \gamma V_\pi(s_{t+1}) | s_t = s] = \mathbb{E}_{a_t \sim \pi(a_t | s), s_{t+1} \sim p(s_{t+1} | s, a_t), r_t \sim p(r_t | s, a_t)} [r_t + \gamma V_\pi(s_{t+1})]

其展开形式为

V_\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a|s) \left[ \sum_{s' \in \mathcal{S}} p(s'|s, a) \gamma V_\pi(s') + \sum_{r \in \mathcal{R}} p(r|s, a) r \right]

其中 $s'$ 是 $s_{t+1}$ 的可能取值， $a$ 是 $a_t$ 的可能取值。

在给定策略 $\pi$ 下，动作价值函数的Bellman期望方程为

Q_\pi(s, a) = \mathbb{E}_\pi[r_t + \gamma V_\pi(s_{t+1}) | s_t = s, a_t = a] = \mathbb{E}_{s_{t+1} \sim p(s_{t+1} | s, a), r_t \sim p(r_t | s, a)} [r(s, a) + \gamma V_\pi(s_{t+1})]

其展开形式为

Q_\pi(s, a) = \sum_{s' \in \mathcal{S}} p(s'|s, a) \gamma V_\pi(s') + \sum_{r \in \mathcal{R}} p(r|s, a) r

其中 $s'$ 是 $s_{t+1}$ 的可能取值。

关于 Bellman 方程的推导过程及解存在的证明，可以参考西湖大学赵世钰老师所出版的强化学习的数学原理的 P22-P33。

1.3 Bellman最优方程#

既然强化学习的目标是最大化累积奖励，那么我们就需要找到一个最优策略 $\pi^*$ ，使得在所有可能的策略中，智能体在每个状态下的预期回报最大。那如何评价一个策略比另一个策略好呢？基于前面所讨论的价值函数是策略的函数这一个点，我们可以使用价值函数来进行比较。

如果一个策略 $\pi_1$ 在所有状态下的价值函数都大于另一个策略 $\pi_2$ 的价值函数，即

V_{\pi_1}(s) \geq V_{\pi_2}(s), \forall s \in \mathcal{S}

那么我们就可以说策略 $\pi_1$ 优于策略 $\pi_2$ 。

最优策略 (optimal policy) $\pi^*$ : 在所有可能的策略中，能够使得智能体在每个状态下的预期回报最大的策略。最优策略是强化学习的目标。最优策略往往不止一个，但是它们的共性是对应的价值函数是相同的，即最优价值函数。
最优状态价值函数 (optimal state value function) $V^*(s)$ : 在状态 $s$ 下，智能体在最优策略 $\pi^*$ 下的预期回报，表示为

V^*(s) = \max_\pi V_\pi(s) = \max_\pi \mathbb{E}_\pi[G_t | s_t=s] = \max_\pi \mathbb{E}_{a_t \sim \pi(a_t | s), s_{t+1} \sim p(s_{t+1} | s, a_t), r_t \sim p(r_t | s, a_t), a_{t+1} \sim \pi(a_{t+1} | s_{t+1}), \dots} [\sum_{l=0}^{\infty}\gamma^l r_{t + l}]

最优动作价值函数 (optimal action value function) $Q^*(s, a)$ : 在状态 $s$ 下采取动作 $a$ 后，智能体在最优策略 $\pi^*$ 下的预期回报，表示为

Q^*(s, a) = \max_\pi Q_\pi(s, a) = \max_\pi \mathbb{E}_\pi[G_t | s_t=s, a_t=a] = \max_\pi \mathbb{E}_{s_{t+1} \sim p(s_{t+1} | s, a), r_t \sim p(r_t | s, a), a_{t+1} \sim \pi(a_{t+1} | s_{t+1}), \dots} [\sum_{l=0}^{\infty}\gamma^l r_{t + l}]

Bellman最优方程就是求解最优策略的方程，它描述了在最优策略下，价值函数自身的关系。可以说，所有的强化学习算法都是在求解这个方程，因为求解 Bellman 最优方程，即可求得最优价值函数，利用最优价值函数，我们就可以得到最优策略。

利用以上对最优策略和最有价值函数的定义，可以推导出如下方程

\begin{align*} V^*(s) &= \max_\pi V_\pi(s) \\ &= \max_\pi \mathbb{E}_\pi[r + \gamma V_\pi(s') | s]\\ &= \max_\pi\mathbb{E}_{a \sim \pi(a|s)}\left[\mathbb{E}_{r \sim p(r | s, a)} [r] + \gamma \mathbb{E}_{s' \sim p(s' | s, a)} [V_\pi(s')]\right] \\ &= \max_\pi \sum_{a \in \mathcal{A}(s)} \pi(a|s) \left[ \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma\sum_{s' \in \mathcal{S}} p(s'|s, a) V_\pi(s') \right] \\ &= \max_\pi \sum_{a \in \mathcal{A}(s)} \pi(a|s) \left[ \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma\sum_{s' \in \mathcal{S}} p(s'|s, a) V^*(s') \right] \end{align*}

注意在最后一步推导中，我们将 $V_\pi(s')$ 替换为 $V^*(s')$ ，这是因为如果目标是最大化 $V_\pi(s)$ ，那么根据 $V^*(s') \ge V_\pi(s')$ , 且环境模型与 $s'$ 状态下的状态价值函数没有关系，而且动作 $a$ 和状态 $s$ 此时已经确定，于是有

\sum_{r\in \mathcal{R}} p(r|s, a) r + \gamma\sum_{s' \in \mathcal{S}} p(s'|s, a) V^*(s') \ge \sum_{r\in \mathcal{R}} p(r|s, a) r + \gamma\sum_{s' \in \mathcal{S}} p(s'|s, a) V_\pi(s')

而且， $V^*(s')$ 也是诸多被优化的价值函数中的一个，是方程右侧可以取得的，所以我们可以将 $V_\pi(s')$ 替换为 $V^*(s')$ 。得到的方程就是状态价值函数的 Bellman 最优方程

V^*(s) = \max_{\pi} \sum_{a \in \mathcal{A(s)}} \pi(a|s) \left[ \sum_{r \in \mathcal{R}} p(r|s, a) r + \gamma \sum_{s' \in \mathcal{S}} p(s'|s, a) V^*(s') \right] \quad \forall s \in \mathcal{S}