马尔科夫（马尔可夫）决策过程浅析

我是 Andy.Qin，一个想创造哆啦 A 梦的 Maker，更多好文章可以到我的博客：qin.news

马尔科夫链（Markov Chain）是一种随机过程，它最初是由俄国数学家A. A. 马尔科夫在1907年提出的。它被广泛应用于自然科学、社会科学、工程技术等领域中的随机过程建模和分析。马尔科夫链是一种离散时间、离散状态的随机过程，其特点是当前状态只与前一状态有关，而与过去的状态无关。因此，马尔科夫链具有“无记忆性”的特点，即它的未来状态只与当前状态有关，而与之前的历史状态无关。马尔科夫链最初被应用于描述游走问题，即在一个由节点组成的图中，一个点从当前位置跳到下一个位置的概率只与当前位置有关，而与之前的路径无关。随着时间的推移，这个点可以在不同的节点之间进行跳跃。

马尔科夫链可以用于建模和分析这种过程，可以计算出在不同的时间步骤下，这个点处于不同节点的概率分布情况，从而可以预测未来的状态。除了游走问题，马尔科夫链还被应用于模拟和预测各种随机过程，如天气变化、股票价格变化、信用评级等。它也被用于解决各种实际问题，如自然语言处理中的语言模型、机器学习中的概率图模型等。而马尔科夫决策过程虽然与马尔科夫链名字很像，但是是两个概念，解决的问题和应用的场景也不太一样。

马尔科夫链是一种描述随机过程的数学模型，它假设当前状态只与前一个状态有关，而与之前的历史状态无关。马尔科夫链主要用于分析和预测离散时间、离散状态的随机过程，例如天气变化、股票价格变化、语言模型等。

马尔科夫决策过程是一种用于描述序列决策问题的数学框架，它将决策者需要在不确定环境中做出决策的问题形式化为一个状态空间、一个决策空间、一个状态转移概率和一个奖励函数。马尔科夫决策过程主要用于解决决策者需要在不确定环境中做出决策的问题，例如机器人导航、自动驾驶、资源管理、金融投资等。

简单来说马尔科夫链主要用于预测和模拟随机过程，而马尔科夫决策过程则用于在不确定环境中做出最优决策。在某些情况下，马尔科夫链可以用于描述马尔科夫决策过程中的状态转移概率，但是它并不能提供最优决策策略，因此在序列决策问题中并不能完全替代马尔科夫决策过程。

马尔科夫决策过程（Markov decision process, MDP） 最初被应用于解决决策问题，特别是在控制领域和人工智能领域中。具体来说，它可以用于解决决策者需要在不确定环境中做出决策的问题，例如机器人导航、自动驾驶、资源管理、金融投资等。

在这些问题中，决策者需要通过观察环境状态并根据自己的目标做出一系列的决策，每个决策都会影响未来的状态和奖励，从而影响最终的决策结果。MDP 提供了一种形式化的方法来描述这类问题，它将问题抽象为一个状态空间、一个决策空间、一个状态转移概率和一个奖励函数。具体来说，MDP 将问题的状态抽象为状态空间中的一个状态，将决策抽象为决策空间中的一个行动，将状态转移抽象为状态转移概率，将行动的奖励抽象为奖励函数。在此基础上，MDP 提供了一种数学方法来计算最优的决策策略，即在每个状态下选择最优的行动，以达到最大化总体奖励的目标。当我们需要做出一系列决策时，比如在游戏中选择下一步该怎么走，或者在自动驾驶中决定汽车下一步应该往哪里开，我们需要考虑现在的状态和未来可能的状态，并且需要知道每个决策对未来状态和奖励的影响。

马尔科夫决策过程就是为了解决这类问题而提出的数学框架。它将问题形式化为一个状态空间、一个决策空间、一个状态转移概率和一个奖励函数。我们可以用这些概念来计算出最优的决策策略，以达到最大化总体奖励的目标。

可以这样想象：你正在玩一个冒险游戏，游戏中有许多关卡。每个关卡都有不同的难度和奖励，你需要决定每个关卡应该选择哪个决策来取得最大的奖励。在每个关卡中，你需要考虑当前的状态（例如：你的角色现在的血量、装备、位置等等），以及每个决策对未来状态和奖励的影响（例如：选择攻击还是逃跑、选择哪个道具等等）。通过使用马尔科夫决策过程，你可以计算出每个决策的期望收益，选择最优的决策策略，以达到最大化总体奖励的目标。它能够帮助我们在不确定环境中做出最优的决策。

那我们将 MDP 拆解成两个部分来讲解：状态转移和奖励，也就是马尔科夫过程和马尔科夫奖励过程来讨论马尔科夫决策过程。在实际应用中，马尔科夫过程和马尔科夫奖励过程通常是分开建模的。首先，根据问题的特点和需求，建立马尔科夫过程模型，计算出状态转移概率；然后，在此基础上建立马尔科夫奖励过程模型，计算出每个状态下采取不同决策所获得的奖励值。最终，利用这些模型，可以计算出最优的决策策略，以达到最大化总体奖励的目标。

马尔科夫过程

马尔科夫过程是一种随机过程，它可以用来描述许多实际问题中的状态转移，例如股票价格的变化、语音信号的识别、分子的运动等。在马尔科夫过程中，当前状态的未来状态只与当前状态有关，而与过去状态无关，因此具有“无记忆性”。 马尔科夫过程由状态空间和转移概率矩阵组成，其中状态空间是所有可能状态的集合，转移概率矩阵描述了从一个状态到另一个状态的概率。马尔科夫过程在金融学、自然语言处理、机器学习、生物学和物理学等领域中都有广泛的应用。

马尔科夫过程由状态空间和转移概率矩阵组成。状态空间是指所有可能的状态的集合，而转移概率矩阵描述了在一个状态下，转移到另一个状态的概率。这些转移概率必须满足概率的基本性质，即每个状态的概率值必须在 0 和 1 之间，而且所有状态的概率之和必须等于 1。

当我们走在路上时，我们的位置可以被看作是一个状态，而我们的移动可以被看作是状态之间的转移。如果我们假设我们有一个内置的“导航系统”，并且该系统可以通过观察我们当前的位置和周围的环境来预测我们可能要去的地方，那么我们的移动就可以被建模为一个马尔科夫过程。在这种情况下，当前位置是状态空间的一部分，而我们从一个位置到另一个位置的转移概率可以被看作是我们在不同方向上行走的可能性。

当我们描述一个离散时间的马尔科夫过程时，可以使用状态转移矩阵来表示状态之间的转移概率。假设我们的状态空间中有 (n) 个状态，状态转移矩阵 (\mathbf{P})  是一个 (n \times n)  的矩阵，其中 (\mathbf{P}_{ij})  表示从状态 (i)  转移到状态 (j)  的概率。则状态转移矩阵的一般形式可以表示为：

$\mathbf{P} = \begin{bmatrix}P_{11} & P_{12} & \cdots & P_{1n} \\\\P_{21} & P_{22} & \cdots & P_{2n} \\\\\vdots & \vdots & \ddots & \vdots \\\\P_{n1} & P_{n2} & \cdots & P_{nn}\end{bmatrix}$

其中，每个元素 $P_{ij}$ 必须满足以下条件：

$0 \leq P_{ij} \leq 1, \qquad \sum_{j=1}^n P_{ij} = 1, \qquad i,j=1,2,\cdots,n$

这些条件确保了每个状态的转移概率在 0 和 1 之间，并且每个状态从一个状态转移到另一个状态的概率之和为 1。状态转移矩阵是马尔科夫过程中一个非常重要的概念，它可以用于分析和预测随机过程的行为和性质。

马尔科夫过程可以用一个简单的公式来表示：

$P(X_{t+1} = j \mid X_t = i, X_{t-1} = i_{t-1}, \ldots, X_0 = i_0) = P(X_{t+1} = j \mid X_t = i)$

其中 (X_t) 表示在时间 (t) 的状态，(i,j) 分别表示状态空间中的两个状态，(P(X_{t+1} = j \mid X_t = i)) 表示从状态 (i) 转移到状态 (j) 的概率。

当我们想要建立一个马尔科夫过程来描述天气的变化时，可以将天气的状态定义为晴天、多云和雨天。我们可以使用状态转移矩阵来描述每个状态之间的转移概率。假设我们观察的时间间隔为一天，我们可以根据历史数据来估计天气状态之间的转移概率。例如，我们可能会得到以下状态转移矩阵：

$\mathbf{P} = \begin{bmatrix}0.7 & 0.2 & 0.1 \\\\0.4 & 0.4 & 0.2 \\\\0.3 & 0.3 & 0.4\end{bmatrix}$

这个矩阵表示，如果今天是晴天，那么明天有 $70$ 的概率还是晴天，$20$ 的概率变成多云，$10$ 的概率变成雨天。同样地，如果今天是多云，明天有 $40$ 的概率还是多云，$40$ 的概率变成晴天，$20$ 的概率变成雨天。如果今天是雨天，那么明天有 $30$ 的概率还是雨天，$30$ 的概率变成多云，$40$ 的概率变成晴天。

假设我们现在知道今天是晴天，我们想知道三天后的天气状态。我们可以使用状态转移矩阵来计算：

$\begin{aligned}& P(X_3 = \text{晴天} \mid X_0 = \text{晴天}) \\\\= & P(X_3 = \text{晴天} \mid X_2 = \text{晴天}) P(X_2 = \text{晴天} \mid X_1 = \text{晴天}) P(X_1 = \text{晴天} \mid X_0 = \text{晴天}) \\\\= & P_{11}^2 P_{11} \\\\= & 0.7^2 \cdot 0.7 \\\\= & 0.343\end{aligned}$

这意味着在未来三天中，有 $34.3$ 的概率天气一直是晴天。

马尔科夫奖励过程

马尔科夫奖励过程（Markov Reward Process）是一种用于描述序列决策问题的数学模型，其在强化学习中被广泛应用。

马尔科夫奖励过程描述了一个智能体在与环境进行交互时所经历的状态和对应的奖励。在每个时间步，智能体根据当前状态采取某个动作，然后转移到一个新的状态，并获得一个相应的奖励。

假设你正在玩一款游戏，你需要通过控制游戏中的角色来获得尽可能高的分数。在这个游戏中，你的角色可以在不同的位置上，而每个位置上都有不同的分数奖励。此外，你的角色每次移动都会消耗一定的能量。

现在我们可以将这个游戏建模成一个马尔科夫奖励过程。每个时间步，你的角色处于一个特定的位置，然后你需要选择一个移动方向，从而使角色转移到一个新的位置，并获得相应的分数奖励。这个过程中，每个位置的分数奖励和移动方向的能量消耗是固定的，因此我们可以将这个过程看作是“马尔科夫”过程，即当前状态只依赖于前一状态，而不依赖于更早的状态。

在这个过程中，你的目标是通过选择最优的移动方向，使得你的角色能够获得尽可能高的总分数。因此，我们可以使用期望回报作为评估标准，即选择使得期望总分数最大的移动方向。

马尔科夫奖励过程（Markov Reward Process）可以用以下公式来表示：

$\begin{aligned} G_t &= R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \ldots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}  \end{aligned}$

其中，$G_t$ 表示从时间步 $t$ 开始所获得的期望回报（expected return），$\gamma$ 表示衰减因子（discount factor），$R_{t+1}$ 表示在时间步 $t+1$ 获得的实际奖励（reward）。

期望回报可以分解为当前时刻获得的奖励 $R_{t+1}$ 和从下一时刻开始所获得的期望回报 $\gamma G_{t+1}$ 的和，其中 $\gamma$ 表示衰减因子，用于逐渐降低未来奖励的权重。

智能体需要做出一系列决策，以获得尽可能高的累计奖励。然而，由于环境的复杂性和随机性，未来的奖励往往比当前的奖励更加不确定，因此智能体需要谨慎地权衡眼前的奖励和未来的奖励。

衰减因子的作用就是逐渐降低未来奖励的权重，使得智能体更加重视眼前的奖励。具体来说，衰减因子的取值范围通常在 $0$ 到 $1$ 之间，当衰减因子接近 $0$ 时，未来奖励的权重会快速降低，从而使得智能体更加关注当前的奖励，而当衰减因子接近 $1$ 时，未来奖励的权重会缓慢降低，从而使得智能体更加平衡当前和未来的奖励。

假设你是一名学生，现在要决定如何分配时间来学习和休息，以获得最好的成绩。在这个例子中，你可以将自己看作是一个智能体，学习和休息是可以选择的行为，成绩是奖励信号。

现在假设你有两个选择：学习或者休息。如果你选择学习，你将获得当前的学习效果，但是你需要消耗一定的体力和时间。而如果你选择休息，你可以恢复体力，但是无法获得任何学习效果。

在这个例子中，你可以将衰减因子看作是你对未来学习效果的重视程度。当衰减因子较小时，你更加关注眼前的学习效果，而较少考虑未来的学习效果。例如，如果你的衰减因子为 $0.1$，那么你会更倾向于选择学习，因为眼前的学习效果可以帮助你获得更高的奖励，即更好的成绩。

然而，当衰减因子较大时，你更加平衡当前和未来的学习效果。例如，如果你的衰减因子为 $0.9$，那么你会更加关注未来的学习效果，因为你知道未来的学习效果对于获得更高的奖励也非常重要。在这种情况下，你可能会更倾向于选择休息，以便在未来更好地学习。

智能体在每个时间步 t 观测到现在状态 $s_{t}$，并执行某个行动 $a_{t}$转换到下一个状态$s_{t+1}$，得到奖励 $R_{t+1}$。然而，由于环境的随机性和不确定性，相同的状态和行动可能会导致不同的奖励，即  $R_{t+1}$可能会是一个随机变量并服从某一概率分布。

为了描述这种随机性，我们通常会假设每个状态和行动对应一个概率分布，表示在这个状态和行动下获得每个奖励的概率。

在实际应用中，我们通常会假设奖励分布是一个均值为 $\mu$，方差为 $\sigma^2$ 的高斯分布。但奖励分布不一定是高斯分布，而可以是任何分布。在实际应用中，我们需要根据具体的环境和任务来选择合适的奖励分布模型，并且根据实际情况进行调整。

值函数

值函数是马尔科夫决策过程中的一个重要概念。简单来说,它衡量采取某个动作后,可以获得的长期回报。

通过值函数,我们可以:

1. 估计每个状态下最优动作。值函数较高的状态对应的动作通常就是最优动作。
2. 找出策略。我们通过对每个状态选择可以获得最大值函数的动作,就构造出了一个策略。
3. 评价和改进策略。我们可以计算策略在每个状态下能获得的期望回报(值函数),从而评价和改进策略。

可以想象成一个投资问题。当你有现金可以投资时,需要选择投资渠道。不同的投资渠道有不同的回报率。

你的状态就是持有的现金数额。你的动作是选择不同的投资渠道。值函数则代表从当前状态(持有现金数额)采取对应动作(投资)后,可以获得的期望长期回报。

值函数的公式可以写为:

$V_t(s) = E[G_t | S_t = s]$

$V_t(s)$: 状态s 在时间t时的价值函数。

$G_t$ 参考上面。

简单来说,值函数是从当前状态 s 开始长期回报的期望值,将未来的回报用 gamma 折扣。通过遍历所有状态 action 对，选择可以获得最大值函数的 action ，就构造出了最优策略。值函数满足贝尔曼方程:

$V_t(s) = E[R_{t+1} + \gamma V_{t+1}(s’) | S_t = s, A_t = a]$

也就是说,状态 s 下的价值等于采取 action a 后获得的即时回报加上 gamma 衰减后的下一个状态 s’ 的价值。通过不断更新各个状态的价值,终将收敛到最优价值，从而获得最优策略。

价值函数定义了每个状态的期望未来回报,但并不能直接计算出来。因此我们需要贝尔曼方程,通过回报和下一状态的价值,迭代的不断更新每个状态的价值函数,最终收敛到最优价值。

状态值函数

用符号 $V_{\pi}(s)$ 表示。状态值函数给出了在状态 $s$ 下，遵循策略 $\pi$ 的期望回报。换句话说，它表示了在当前状态 $s$ 下，按照策略 $\pi$ 采取行动所能获得的长期收益。这个函数的定义如下：

$V_{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s]$

这里，$G_t$ 表示累积回报，它是从时刻$t$开始的未来奖励的折扣和。$\mathbb{E}_{\pi}$ 表示在策略 $\pi$ 下的期望。

动作值函数

用符号 $Q_{\pi}(s, a)$ 表示。动作值函数表示在状态$s$下采取动作$a$，然后遵循策略 $\pi$ 的期望回报。换句话说，它表示了在当前状态 $s$ 下，首先采取动作$a$，然后按照策略 $\pi$ 进行行动所能获得的长期收益。这个函数的定义如下：

$Q_{\pi}(s, a) = \mathbb{E}_{\pi}[G_t | S_t = s, A_t = a]$

与状态值函数类似，$G_t$ 表示累积回报，$\mathbb{E}_{\pi}$ 表示在策略 $\pi$ 下的期望。

状态值函数关注的是在某个状态下遵循特定策略的期望回报。它仅基于当前状态来评估长期收益，不考虑选择哪个动作。换句话说，状态值函数表示在状态下遵循策略的平均表现。动作值函数关注的是在某个状态下采取某个动作，然后遵循特定策略的期望回报。它基于当前状态以及采取的动作来评估长期收益。动作值函数表示在状态下采取动作并遵循策略的平均表现。

马尔科夫决策过程

在马尔科夫决策过程中，我们有一个智能体，它在一个马尔科夫过程中进行决策，每次决策都会导致状态的转移和获得即时奖励。智能体的目标是通过选择动作来最大化未来奖励的期望值。

MDP（马尔科夫决策过程） 通常用马尔科夫决策过程是个五元组：$<S, A, P, R, \gamma>$，其中：

• S 表示状态集合，代表智能体可能处于的所有状态。
• A 表示动作集合，代表智能体可以采取的所有动作。
• P 表示转移概率函数，它描述了在当前状态下执行某个动作后，智能体将转移到下一个状态的概率分布。
• R 表示奖励函数，它描述了在某个状态下执行某个动作所获得的即时奖励。
• $\gamma$ 表示折扣因子。

在决策过程中，策略是指一种映射关系，它将每个状态映射到一个动作上。简单来说，策略就是一个决策规则，告诉智能体在特定状态下应该采取什么样的动作。

策略可以是确定性的，也可以是随机性的。确定性策略是指对于每个状态，都有一个确定的动作与之对应；随机性策略是指对于每个状态，都有一定的概率分布来描述应该采取哪些动作。

策略 π 依赖于当前状态，与历史无关且是固定的。

在马尔科夫决策过程中，策略 $\pi$ 是一个从状态集 $S$ 到动作集 $A$ 的映射函数，它规定了在每个状态下应该采取什么动作。可以将策略 $\pi$ 表示为：

$\pi: S \rightarrow A$

在马尔科夫决策过程中，智能体的目标是找到一个最优策略 $\pi^*$，使得在该策略下获得的长期累积奖励最大化。为了找到最优策略，我们可以使用值函数来评估每个策略的好坏，并且通过迭代更新值函数，从而得到最优策略。

具体来说，我们可以定义状态值函数 $V^{\pi}(s)$ 和动作值函数 $Q^{\pi}(s,a)$。其中，$V^{\pi}(s)$ 表示在状态 $s$ 下执行策略 $\pi$ 获得的长期累积奖励，而 $Q^{\pi}(s,a)$ 则表示在状态 $s$ 下执行动作 $a$，然后按照策略 $\pi$ 继续执行获得的长期累积奖励。

给定一个马尔可夫的决策过程和策略 π 便可以转换成马尔可夫过程和马尔科夫奖励过程。这也是马尔科夫决策过程，马尔科夫过程和马尔科夫奖励过程的联系。

马尔科夫过程是马尔科夫决策过程的特例，其中没有动作的概念。因此，马尔科夫过程是一个包含状态集、状态转移概率函数的随机过程，它描述了一个具有马尔科夫性质的随机系统。

马尔科夫奖励过程是马尔科夫过程的一个扩展，它增加了一个奖励函数来衡量智能体在某个状态下采取某个动作所获得的奖励。因此，马尔科夫奖励过程包含状态集、状态转移概率函数、奖励函数和折扣因子，它描述了一个带有奖励的马尔科夫性质的随机系统。

马尔科夫决策过程是一个更加通用的模型，它包含了马尔科夫过程和马尔科夫奖励过程，并且还增加了决策变量和策略函数。马尔科夫决策过程描述了一个具有马尔科夫性质、带有奖励的随机系统，并且智能体可以在每个状态下根据策略函数来决定采取哪个动作，从而最大化长期累积奖励。

下面的例子由 GPT4 生成，已经人工修改过一遍，仍然可能存在错误，仅供参考。

假设一个3×3的网格世界，机器人的任务是从起始位置（0,0）到达目标位置（2,2），尽量避免障碍物（1,1）。网格表示如下：

+---+---+---+
| S |   |   |
+---+---+---+
|   | X |   |
+---+---+---+
|   |   | G |
+---+---+---+

S 表示起始位置，G 表示目标位置，X 表示障碍物。

状态（state） ：在这个例子中，状态可以表示为机器人在网格中的位置，例如（0,0）或者（2,1）。

动作（action） ：机器人可以采取的动作包括向上（U）、向下（D）、向左（L）和向右（R）。

转移概率（transition probability） ：由于机器人可能因为控制错误或者环境不确定性导致转移不成功，我们可以为每个状态和动作定义一个转移概率。例如，从状态（0,0）向上移动的概率为0.8，向右移动的概率为0.1，向左和向下移动的概率为0。

奖励函数（reward function） ：奖励函数定义了机器人在每个状态执行特定动作后获得的奖励。为了鼓励机器人尽快到达目标并避免障碍物，我们可以定义以下奖励函数：

• 达到目标位置：+10
• 撞到障碍物：-10
• 其他情况：-1（表示每走一步的代价）

接下来，我们需要为这个MDP定义一个策略（policy）来指导机器人的行动。策略是一个从状态到动作的映射，表示在某个状态下应该采取哪个动作。我们可以使用值迭代（Value Iteration）或策略迭代（Policy Iteration）等强化学习算法来求解最优策略。

以值迭代为例，计算过程如下：

1. 初始化值函数 V(s) 为0。
2. 迭代更新值函数，直到收敛：对于每个状态 s，更新 V(s) 为：

$V(s) = max_a [R(s, a) + γ * Σ P(s’|s, a) * V(s’)]$

其中，R(s, a) 表示奖励函数，γ 是折扣因子（通常选择 0.9 或者 0.99），P(s’|s, a) 表示转移概率。

3. 根据收敛后的值函数得到最优策略，对于每个状态 s，选择使得 Q(s, a) 最大的动作a作为策略输出：

$π(s) = argmax_a [R(s, a) + γ * Σ P(s’|s, a) * V(s’)]$

经过值迭代后，我们可以得到一个最优策略，指导机器人在网格世界中达到目标位置并尽量避免障碍物。

我们首先将折扣因子 γ 设为0.99，并初始化值函数。下面是值迭代算法的一些关键步骤：

初始化值函数：

迭代更新值函数。对于每个状态，计算所有可能动作的期望值，并将值函数更新为最大期望值。例如，在状态（0,0）:

取最大的 Q 值更新 V(0,0)。

重复第2步，直到值函数收敛。收敛后的值函数示例：

根据收敛后的值函数计算最优策略。例如，在状态（0,0）：

计算每个可能动作的Q值：

根据最大的 Q 值选择动作，例如，可以选择向上移动。

为所有状态计算最优策略。示例策略：

根据上述最优策略，机器人将从起始位置（0,0）开始，向右移动到（0,1），然后向右移动到（0,2），向下移动到（1,2），最后再向下移动到目标位置（2,2），同时避免了障碍物（1,1）。

感谢 Ray 同学帮忙二次勘校。

我是 Andy.Qin，一个想创造哆啦 A 梦的 Maker，更多好文章可以到我的博客：qin.news