马尔可夫决策过程（Markov decision process，简称 MDP）是一种序贯决策的数学模型，其中智能体的动作既影响即时奖励，也影响随后遇到的状态。它将受控的随机过程与用于评估长期决策效果的目标相结合。其核心假设是：当前状态和动作包含确定下一状态与奖励分布所需的全部信息。MDP 为强化学习、决策理论和随机控制提供了基础。(incompleteideas.net)
数学表述
离散时间、折扣型 MDP 通常由元组 ((S,A,P,r,\gamma)) 定义：
- (S) 为状态集合。
- (A) 为动作集合，在各状态下可进一步限制为允许的动作子集 (A(s))。
- (P(s'\mid s,a)) 为在状态 (s) 下选择动作 (a) 后进入状态 (s') 的概率。
- (r(s,a)) 为即时奖励的期望值。
- (\gamma) 为折扣因子，满足 (0\leq\gamma<1)。
在时刻 (t)，智能体观察到 (S_t)，选择 (A_t)，获得 (R_{t+1})，并进入 (S_{t+1})。奖励可以是随机的；更细致的模型会给出联合分布 (p(s',r\mid s,a))。某些表述则使用成本，以最小化成本为目标。有限 MDP 的状态集合和动作集合均为有限集，而更一般的表述允许使用连续空间。(incompleteideas.net)
马尔可夫性质意味着，在给定当前状态和动作的条件下，更早的历史不会提供额外的预测信息：
[ \Pr(S_{t+1},R_{t+1}\mid S_0,A_0,\ldots,S_t,A_t)
\Pr(S_{t+1},R_{t+1}\mid S_t,A_t). ]
这是对条件独立的陈述，并不要求相邻状态彼此独立。这一性质是否成立取决于状态的定义方式；遗漏相关信息可能使其不再成立。在固定的平稳策略下，状态序列构成一条马尔可夫链。(incompleteideas.net)
策略与目标
策略规定如何选择动作。确定性平稳策略将每个状态映射到一个动作；随机平稳策略则为动作赋予概率 (\pi(a\mid s))。更一般的策略可以依赖时间或完整的交互历史。所要求解的是策略，而不是单一的动作序列，因为决策必须根据实际遇到的状态作出响应。(web.mit.edu)
对于无限时域折扣问题，回报为
[ G_t=\sum_{k=0}^{\infty}\gamma^kR_{t+k+1}. ]
目标是使其期望值最大化。折扣使较远期的奖励具有较低权重，并在奖励有界时保证回报有限。有限时域问题评估指定步数内的奖励，而平均奖励问题评估长期的每步平均奖励。回合式问题在到达指定终止状态时结束。这些评价准则不一定会产生相同的最优策略。(web.stanford.edu)
价值函数与贝尔曼方程
策略的状态价值函数为
[ V^\pi(s)=\mathbb E_\pi[G_t\mid S_t=s]. ]
其动作价值函数 (Q^\pi(s,a)) 评估先执行动作 (a)、随后遵循策略 (\pi) 所获得的回报。对于平稳折扣问题，贝尔曼期望方程以递归形式表达价值：
[ V^\pi(s)= \sum_a\pi(a\mid s) \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^\pi(s')\right]. ]
该方程将即时奖励与未来状态的折扣价值分开。因此，对于有限模型，策略评估可以用矩阵写成线性方程组。(web.stanford.edu)
最优价值函数 (V^*(s)=\sup_\pi V^\pi(s)) 满足
[ V^(s)=\max_{a\in A(s)} \left[r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V^(s')\right]. ]
当状态集合和动作集合有限、奖励有界且 (\gamma<1) 时，存在最优的确定性平稳策略。在该方程中选择使表达式达到最大值的动作，即可得到这样的策略。相应的贝尔曼算子在最大范数下是压缩映射，从而保证最优价值函数的唯一性以及反复更新的收敛性。(introml.mit.edu)
求解方法
当转移概率和奖励已知时，动态规划提供了标准的求解方法。价值迭代反复对价值估计应用贝尔曼最优性更新。策略迭代则交替进行当前策略的评估，以及通过选择具有更高期望回报的动作来改进策略。有限时域问题从终端价值出发进行逆向归纳；最优动作可能取决于剩余时域。有限折扣型 MDP 也可以表述为数学优化中的线性规划问题。(introml.mit.edu)
当模型未知时，强化学习根据交互数据估计价值或策略。基于模型的方法在规划之前或规划过程中学习状态转移模型和奖励模型；无模型方法则不显式构建这些模型。例如，Q学习利用采样得到的状态转移来估计最优动作价值。MDP 定义决策问题，而学习算法规定如何求得该问题的解。(see.stanford.edu)
应用与扩展
其应用包括机器人学、库存控制、资源分配和供应链优化。以库存模型为例，状态记录库存量及其他相关变量，动作规定补货数量，不确定的需求决定状态转移，奖励则表示收入减去成本。如果需求取决于仅靠库存量无法反映的条件，就必须在状态中纳入相关的需求信息。(see.stanford.edu)
普通 MDP 假设决策者能够观察到状态。部分可观测马尔可夫决策过程提供的则是观测信息，这些信息可能无法揭示状态，或只能不完全地揭示状态。可能状态上的概率分布称为信念状态，可作为一个等价的完全可观测决策过程的状态。半马尔可夫决策过程允许决策之间的时间间隔长短不一。(cs.cmu.edu)
庞大的状态空间使精确的价值表和穷尽式更新难以实际实施，这体现了维数灾难。近似方法以紧凑形式表示价值或策略，并用基于采样或受限范围的计算代替完整计算。这些方法的表现取决于近似方法、可用数据，以及状态转移模型和奖励模型的有效性。(incompleteideas.net)