人工智能中的马尔可夫决策过程

人工智能中的马尔可夫决策过程简介

马尔可夫决策过程 (MDP) 是一种数学框架，用于解释动态系统中需要顺序和随机决策的决策过程。MDP 基于马尔可夫性质，强调当前状态的重要性，使代理能够选择最佳行动方案以最大化奖励。它们在机器人、人工智能和运筹学等领域至关重要，尤其是在概率规划和强化学习方面。MDP 通过解决复杂的优化问题，在智能系统设计、交通管理和系统维护等实际应用中发挥作用。这种范式彻底改变了各行业的决策过程。

在结果是随机的或由随时间进行连续决策的决策者控制的情况下，马尔可夫决策过程 (MDP) 是一种随机决策过程，它使用数学框架来模拟动态系统的决策。本文通过几个现实世界的例子来说明 MDP。

马尔可夫决策过程：它是什么？

马尔可夫决策过程 (MDP) 是一种随机决策过程，它使用数学框架来模拟动态系统的决策。它适用于结果是预先确定或由随着时间推移进行连续选择的决策者控制的情况。MDP 评估决策者根据系统当前状态和环境采取的行动方案。

为了确定系统的下一个最佳行动方案，MDP 考虑了环境、代理行为和奖励等因素。根据诸如动作集、可能状态和决策频率等多个变量，它们分为四类：有限、无限、连续和离散。

MDP 的历史可以追溯到 20 世纪 50 年代初。俄罗斯数学家安德烈·马尔可夫，他为随机过程的发明做出了重要贡献，他的名字被用作马尔可夫的绰号。MDP 最初因其解决路线规划、排队优化以及库存管理和控制问题的能力而闻名。如今，MDP 被广泛应用于 动态规划、机器人学、自动控制、经济学、制造业等领域，用于研究优化问题。

MDP 在人工智能中对具有概率动态的顺序决策场景进行建模。它们用于设计必须在决策可能产生不可预测结果的环境中长时间运行的智能机器或代理。

MDP 模型通常用于人工智能的子领域，如 强化学习 (RL) 和概率规划。

• 概率规划领域使用既定的模型来实现参与者的目标和目的。在这个过程中，它非常重视帮助计算机或代理做出决策，同时教它们如何采取行动以帮助它们实现目标。
• 应用程序可以通过代理从其环境接收到的反馈中学习，这就是强化学习的原理。

让我们用一个现实世界的例子来更好地理解这一点

想象一只饥饿的羚羊在野生动物保护区里寻找食物。它发现左边有一个菜花，右边有一个蘑菇。如果它吃了蘑菇，羚羊就会得到水作为奖励。但如果它选择了菜花，保护区里的狮子就会被放出笼子。羚羊最终学会选择蘑菇那边，因为这样做会带来丰厚的回报。

在上述 MDP 示例中，代理和环境是两个关键组成部分。在这里，羚羊充当代理并做出决策。环境是羚羊的栖息地，即野生动物保护区。当代理采取不同行动时，会出现不同的情况。这些情况被称为状态。例如，羚羊会根据它所采取的行动（例如吃蘑菇）改变状态并获得奖励（水）。随着时间的推移，代理（羚羊）通过重复这个过程来学习在每种状态下的最佳行动方案。

我们可以正式说明，羚羊知道最佳行动方案，那就是吃蘑菇。因为它不想吃菜花，因为它会带来可能危及生存的风险。如示例所示，MDP 对于封装 RL 情况的动态至关重要。

理解 MDP 模型

MDP 模型由几个基本组成部分构成，包括代理、状态、动作、奖励和最优策略。术语“代理”描述了一个负责做出决策和执行活动的系统。它在一个环境中运行，该环境描述了代理在其之间变化时所处的确切状态。MDP 定义了特定状态和代理活动如何导致其他状态。此外，根据代理执行的动作和它所到达的状态（当前状态），会给予代理奖励。根据其当前状况，MDP 模型中的策略指示代理的下一个行动方案。

以下是 MDP 框架的主要组成部分：

• S：状态 (s ∈ S)
• A：动作 (a ∈ A)
• P (St+1|st.at)：转移概率
• R (s)：奖励

MDP 模型如图所示：

MDP 模型使用马尔可夫性质，该性质断言未来只能从包含过去所有相关知识的当前状态推断出来。可以使用此方程来评估马尔可夫性质：

P[St+1|St] = P[St+1 |S1,S2,S3……St]

此方程表示，下一个状态的概率 (P[St+1]) 由当前状态 (St) 确定，并由考虑所有先前状态 (S1, S2, S3, …St) 的下一个状态的概率 (P[St+1]) 决定。这表明 MDP 仅根据当前状态评估下一个动作，而不依赖于先前的状态或动作。

价值和策略的作用

给定当前状态，策略 (Π) 被理解为决定代理为最大化奖励而应采取的最佳行动方案。简单来说，它将状态和动作联系起来。

Π: S -> A

定义显示代理在每个状态下奖励的收益，以便识别最优策略。因此，不建议使用时限方法来侧重于短期或长期收益。相反，引入了一个称为“折扣因子 (γ)”的变量。根据规则，如果 γ 的值接近零，则优先考虑即时收益。如果 γ 显示的值接近一，则重点转移到长期收益。因此，折扣无限时域方法是识别最优策略的关键。

每个特定状态下的奖励收益由值函数 V(s) 确定。预期贴现未来收益的总和是其公式的特征。

当前状态的奖励和下一个状态的贴现奖励值构成了值函数的两个部分。贝尔曼方程由此分解得出：

值得注意的是，在这种情况下，策略会影响代理的行为和激励。这意味着存在特定于策略的值函数。

可以使用动态规划、时间差学习和蒙特卡洛评估等迭代技术来求解最优值函数。最优策略是考虑当前情况并选择最大最优值的策略。以下方程是其数学表示：

因此，策略是当前状态的结果，每个时间步都使用当前状态的数据来评估新策略。为了求解最优策略函数，通过值迭代、Q 学习、策略迭代和线性规划等多种技术来实现。

为了进一步理解 MDP 的工作原理，现在让我们检查一个现实世界的例子。

为了保证长期收益，我们必须确定部落是否应该在附近的森林里猎鹿。每只鹿都会产生固定的收益。然而，如果部落狩猎超过一定程度，下一年的产量可能会降低。因此，我们必须确定可以捕捉的鹿的理想百分比，同时优化长期产量。

在这种情况下，问题陈述很简单：是否应该猎杀某只鹿？在 MDP 的上下文中，困难可以表述如下：

状态：相关年份森林中存在的鹿的数量。以下定义适用于四种状态：空、低、中、高。

• 空：没有鹿可供狩猎
• 低：可用鹿的数量低于阈值 t_1
• 中：可用鹿的数量介于 t_1 和 t_2 之间
• 高：可用鹿的数量高于阈值 t_2

动作：有两种动作：go_hunt（去狩猎）和 no_hunting（不狩猎）。前者表示捕获一定比例的鹿。应注意，no_hunting 是唯一可以对空状态执行的动作。

奖励：每个状态都为狩猎提供某种形式的奖励。在不同状态下狩猎可能会带来例如 5,000 美元、50,000 美元和 100,000 美元的奖励。此外，如果该动作导致状态变为空，则支付 -200,000 美元。这是因为必须重新繁殖新鹿，这需要时间和金钱。

状态转移：在一个状态下狩猎会导致该状态下的鹿数量减少。除了“高”状态外，“不狩猎”动作会导致转移到鹿数量更多的状态。

马尔可夫决策过程示例

在包括计算机科学、电气工程、制造、运筹学、金融与经济学、电信等在内的多个应用领域，MDP 都做出了巨大贡献。

以下是 MDP 仍然非常活跃的几个简单示例：

1. 路由问题

基于 MDP 的顺序决策处理路由问题，例如在 旅行商问题 (TSP) 中识别的问题。TSP 由几个组成部分构成：

• 推销员 = 代理，
• 代理的可用路线是它在当前状态下可以执行的操作。
• 奖励等于使用特定路线的成本，并且
• 目标：在旅途中最小化总成本的最佳行动方案。

2. 动态系统的维护和修复监督

由于各种上下文中的动作（例如汽车、公共汽车或卡车）而随时间恶化的动态系统会受到维护和修复问题的影响。在这种情况下，选择可能是更换车辆的关键部件、进行维修或什么都不做。通过在 MDP 下构建这个问题，系统可以选择有助于随着时间推移降低车辆维护成本的措施。

3. 设计智能机器

随着人工智能和机器学习的发展，MDP 被广泛应用于机器人、复杂的自主系统、自动驾驶汽车、自动化系统等领域。MDP 被用于强化学习模型，以教授机器和机器人如何自主学习并完成特定任务。

例如，谷歌旗下的 DeepMind Technologies 通过将神经网络与 MDP 架构相结合，训练计算机系统在雅达利游戏中超越人类。此外，该公司还使用 MDP 训练机器玩诸如 AlphaGo 等棋盘游戏。DeepMind Technologies 还使用 MDP 框架训练模拟机器人进行奔跑和行走。

4. 设计问答游戏

设计具有特定级别的问答游戏是 MDP 的常见应用。每个级别都有一个问题，如果回答正确，就会获得金钱奖励。随着级别的提高，问题会变得更难，提供的奖励也更高。

当玩家在问答游戏中表现出色并正确回答所有问题时，他们会获得奖金，并且可以选择继续玩问答游戏或结束游戏。如果他们决定停止，他们就可以保留他们累积的所有奖金。然而，如果他们决定继续玩，但在特定级别的游戏中无法正确回答问题，他们就会失去所有累积的奖励。这些游戏旨在通过评估玩或停止的动作来最大化收益。

5. 管理交通交叉口的等待时间

交通信号灯的时长是通过 MDP 来确定的。在这里，目标是减少车辆的等待时间，同时增加可以通过路口的车辆数量。它可以是一个双向交叉口，意味着交通可以朝任一方向（例如，南方或西方）通行。此外，预计该系统装有传感器，可提供关于有多少汽车正在接近交叉口的信息。在这种情况下，交通信号灯为绿色和红色。每一步需要几秒钟，可能是两秒或五秒。根据交叉口的汽车数量及其等待时间，您可以使用 MDP 来确定是否更改交通信号灯。

6. 确定入院的患者数量

每天都有一定数量的患者因各种原因来到医院。然后，医院必须决定可以收治多少患者，同时考虑以下因素：

• 迄今为止已入院的患者数量，
• 可用床位数量，以及
• 每天康复并出院的总患者数。

在决定收治多少患者的同时，医院的目标是在特定时期内最大化康复的患者数量。为他们创建 MDP 可以帮助实现这两个目标。

除了上述现实世界示例外，MDP 对于加快股票交易、改进制造业的队列控制和优化通信协议至关重要。

要点

马尔可夫决策过程是一种基于马尔可夫性质原理的随机决策技术。它用于为动态系统做出最佳决策，同时考虑其当前状态和运行环境。MDP 通常用于创建智能系统，并且是强化学习应用的重要组成部分。MDP 在制造业、银行与经济、物流和机器人流程自动化等各个行业中经常用于执行日常活动。

结论

本文对马尔可夫决策过程 (MDP) 进行了全面介绍，MDP 是一种用于动态系统随机决策的数学框架。在仅依赖当前状态且不需要历史数据的马尔可夫性质的指导下，MDP 允许决策者或智能代理根据当前状态和奖励选择最佳行动方案。MDP 在机器人、人工智能、强化学习和运筹学等领域得到了广泛应用，在解决交通管理、维护、路由和游戏设计优化等实际问题方面发挥了至关重要的作用。它们在模拟具有概率结果的顺序决策方面的适应性，突显了它们在各个领域的重要性。