马尔可夫决策过程（MDP）是一种用于在结果不确定时进行序贯决策的数学模型。它是一种随机决策过程，通常通过随机动态规划方法求解。MDP起源于20世纪50年代的运筹学，此后在生态学、经济学、医疗保健、电信以及强化学习等领域获得了认可。在强化学习中，MDP框架建模了学习智能体与其环境之间的交互，其特征为状态、动作和奖励，为Artificial intelligence挑战中的关键要素（包括因果关系、不确定性和明确目标）提供了简化表示。
其名称源于与马尔可夫链的联系，后者由俄罗斯数学家安德雷·马尔可夫发展而来。“马尔可夫”性质指的是底层结构，其中状态转移仅依赖于当前状态和动作，而不依赖于先前历史。该过程被称为“决策过程”，因为它涉及影响这些转移的决策，将马尔可夫链扩展为不确定性下的决策。
形式定义
MDP通常定义为一个四元组\((S, A, P_a, R_a)\)，其中：
- \(S\)是状态空间，可以是离散或连续的（例如，实数集）。
- \(A\)是动作空间，其中\(A_s\)表示从状态\(s\)可用的动作集合。该集合也可以是离散或连续的。
- \(P_a(s, s')\)是转移概率，表示在时间\(t\)的状态\(s\)中采取动作\(a\)导致在时间\(t+1\)进入状态\(s'\)的概率。对于离散状态，\(P_a(s, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)\)。对于连续状态空间，概率通过积分定义，通常相对于勒贝格测度。
- \(R_a(s, s')\)是从\(s\)转移到\(s'\)时采取动作\(a\)后获得的即时奖励（或期望奖励）。奖励通常是一个随机变量。
策略函数\(\pi\)是从状态空间到动作空间的（可能为概率性的）映射，指定在每个状态下应采取何种动作。
优化目标
MDP中的目标是找到一种策略\(\pi\)，使随机奖励的累积函数最大化，通常是无限时间范围内的期望折扣总和：\(\mathbb{E}[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_t, s_{t+1})]\)，其中\(\gamma \in [0, 1)\)是折扣因子。一旦策略固定，MDP就像马尔可夫链一样运行，因为每个状态中的动作由\(\pi(s)\)确定。
常见的求解方法包括动态规划技术，如值迭代和策略迭代，这些方法计算最优值函数或最优策略。这些方法是Reinforcement learning算法（如Q学习和SARSA）的基础。
应用
MDP在许多领域得到广泛应用。在经济学中，它们用于建模最优消费和投资决策。在医疗保健中，它们指导不确定性下的治疗计划，例如慢性病管理。在电信领域，它们优化资源分配和网络路由。在生态学中，它们为物种管理的保护策略提供信息。在Machine learning中，MDP是强化学习的核心，使智能体能够通过与环境的交互进行学习，如在机器人技术、游戏和自主系统中所示。
与强化学习的关系
强化学习（RL）使用MDP框架来形式化智能体-环境交互。在RL中，智能体事先不知道转移概率或奖励函数；相反，它通过试错并使用来自环境的样本学习最优策略。这使RL区别于经典的MDP求解方法，后者假设已知模型参数。现代RL，包括深度强化学习，将MDP与Neural network函数逼近器相结合，以处理大规模状态空间，如游戏和自动驾驶等应用中所示。
扩展与变体
几种扩展解决了基本MDP的局限性。部分可观测马尔可夫决策过程（POMDP）处理智能体无法直接观测完整状态的情况。因子化MDP利用状态变量中的结构来提高可扩展性。多智能体MDP将框架扩展到具有交互目标的多个决策者。这些变体保留了核心的马尔可夫性质，同时适应更复杂的现实世界问题。
历史背景
MDP的形式化归功于20世纪50年代的理查德·贝尔曼，他还发展了动态规划。安德雷·马尔可夫早期关于随机过程的工作提供了理论基础。自那时起，MDP已成为运筹学和人工智能的基石，影响了序贯决策的理论和应用工作。