马尔可夫决策过程

马尔可夫决策过程为决策者在随机环境下做出决策提供了数学架构模型，为动态规划与强化学习的最优化问题提供了有效的数学工具，广泛用于机器人学、自动化控制、经济学、以及工业界等领域。当我们提及马尔可夫决策过程时，我们一般特指其在离散时间中的随机控制过程：即对于每个时间节点，当该过程处于某状态(s)时，决策者可采取在该状态下被允许的任意决策(a)，此后下一步系统状态将随机产生，同时回馈给决策者相应的期望值，该状态转移具有马尔可夫性质。

（描述来源：https://en.wikipedia.org/wiki/Markov_decision_process#Continuous_time_Markov_decision_process ）

定义：

马尔可夫决策过程是一个五元组：

其中：

• S表示状态的有限集
• A表示决策的有限集

• 表示状态转换概率矩阵

• 表示期望方程

• 表示折扣系数，是介于[0,1]区间的任意实数

基本性质：

• 状态转换概率矩阵P满足马尔可夫性质，即

• 期望方程R满足：

最优策略：

马尔可夫决策过程的核心问题是寻找最优策略组合，即在一系列决策的组合下，决策者将得到最大期望值。

首先定义在给定状态s（时间t）下决策者采取决策a的概率分布为：

因为马尔可夫决策过程的本质是一条马尔可夫链，因此我们已知该分布取决于当下的状态，即该分布是静止的（或满足时间独立性）：

在此基础上，最优策略问题可以定义为：寻找一项策略组合π，使得无穷时间范围内的期望折扣总和最大化：

价值方程：

马尔可夫决策过程中的状态价值方程V是指，决策者从状态s开始按照决策组合π作出决策从而得到的预期回报：

马尔可夫决策过程中的行动价值方程Q是指，决策者从状态s开始并作出决策a，之后按照决策组合π作出决策从而得到的预期回报：

两种价值方程的关系如下图所示：

并满足以下关系式：

算法：

马尔可夫决策过程问题可以通过线性规划求解，即假设已知状态转换方程P以及期望方程R，求最优策略组合π，使得期望折扣总和最大化。

（描述来源： Reinforcement Learning: An Introduction, by R. Sutton and A. G. Barto； Algorithms for Reinforcement Learning, by C. Szepesvari）

发展历史

马尔可夫决策过程这一概念最早于20世纪50年代由美国数学家理查德·贝尔曼提出，并于20世纪60年代由罗纳德·霍华德发表的著作《动态规划与卡尔科夫过程》中建立起成熟的数学架构模型，自此该理论广泛应用于经济学、电子通讯、工程学、社会生态学等领域；20世纪60年代至80年代，该理论随着理论上的突破及算法上的实现，在各个领域实现了蓬勃发展；自20世纪90年代以来，马尔可夫决策过程多用于人工智能领域的研究，英国剑桥学者沃特金斯在其博士毕业论文里依靠马尔可夫决策过程提出的Q学习，为日后强化学习（Reinforcement Learning）的建立提供了理论依据。

主要事件

发展分析

瓶颈

求解最优策略组合的过程实际上是一个求解以状态s为参数的多项式的过程，而在模拟马尔可夫决策过程时状态s的数量将会以指数级增长，而目前可操作的计算量大概在千万级左右。

未来发展方向

马尔可夫决策过程作为强化学习的基本架构，随着强化学习在AI领域的发展，相信日后定会有所突破。

Contributor: Han Zhang