半马尔可夫决策过程 | 机器之心

简介

马尔科夫决策过程主要用于建模决策模型。考虑一个动态系统，它的状态是随机的，必须做出决定，而代价由决策决定。然而，在许多的决策问题中，决策阶段之间的时间不是恒定的，而是随机的。半马尔可夫决策过程（SMDPs）作为马尔科夫决策过程的扩展，用于对随机控制问题进行建模，不同于马尔科夫决策过程，半马尔科夫决策过程的每个状态都具有一定的逗留时间，并且逗留时间是一个通用的连续随机变量。

[描述来源：Tijms H C. A first course in stochastic models[M]. John Wiley and sons, 2003.]

一个半马尔科夫决策过程可以定义为一个五元组的形式：$(S,A,P,T,R,F)$,$S$表示的是状态集合，$A$表示动作集合，$P$表示状态转移概率的集合，$T$表示平稳状态持续时间，$R$是奖励函数，$F$是一个对应到状态-动作对的目标函数。所面对的问题就是抓住影响所控制的概率系统的机会，也就是适时的系列的作出行动的选择，以期达到决策者心中的某种标准的优化。由于受控制的系统在持续发展，过去的决策通过状态的转移影响今天的决策。一般来讲，一步最优的选择不是最好的决策，必须要考虑系统将来状态上的预期机会和费用。

[描述来源：Mahadevan G W S. Hierarchical optimization of policy-coupled semi-Markov decision processes[C]//Machine Learning: Proceedings of the Sixteenth International Conference (ICML'99), Bled, Slovenia, June 27-30, 1999. Morgan Kaufmann Pub, 1999: 464.]

半马尔可夫决策过程具有许多实际的应用，它可以应用于许多非平的多智能体任务中，如制造和机器人学。

发展历史

描述

自1963年，Jewell等人提出了半马尔可夫决策问题以来，这个方法得到了广泛的认可和应用。

1973至1980年间，学者们对这个方向进行了探索和相关算法的改进，提高了算法的实用性。

1994年，Puterman总结了有界和无界报酬折扣SMDP的一般性结果，帮助学者对这个领域有了更好的了解。

2008年，Yin等人研究了有限状态和紧致行动空间的折扣准则SMDP的性能优化问题。

主要事件

年份	事件	相关论文/Reference
1963	提出了半马尔可夫决策过程的概念	Jewell W S. Markov renewal programming I: Formulation, finite return models; Markov renewal programming II: Infinite return models, example. Oper Res, 1963, 11: 938–971. Howard R A. Semi-Markovian decision processes. Bull Inst Internat Statist, 1963, 40: 625–652.
1973	对半马尔可夫决策过程进行了改进，使用无边界限制的奖励来进行训练	Lippman S A. Semi-Markov decision processes with unbounded rewards[J]. Management Science, 1973, 19(7): 717-731.
1975	Wessels和van Nunen考虑了有界状态和行动的报酬折扣准则SMDP	Wessels J, van Nunen J A E E. Discounted semi-Markov decision processes: Linear programming and policy iteration. Statist Neerlandica, 1975, 29: 1–7
1977	Feldman考虑了由SMDP描述的冲击(shock)模型	Feldman R M. Optimal replacement with semi-Markov shock models using discounted costs. Math Oper Res, 1977, 2: 78–90
1980	Porteus改进了有限状态折扣SMDP最优策略的值迭代和策略迭代的数值算法,降低了计算复杂度	Porteus E. Improved iterative computation of the expected discounted return in Markov and semi-Markov chains. Z Oper Res, 1980, 24: 155–170
1994	Puterman总结了有界和无界报酬折扣SMDP的一般性结果	Puterman M L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York: John Wiley & Sons Inc, 1994
2008	Yin等人研究了有限状态和紧致行动空间的折扣准则SMDP的性能优化问题.	Yin B Q, Li Y J, Zhou Y P, et al. Performance optimization of semi-Markov decision processes with discounted-cost criteria. Eur J Control, 2008, 14: 213–222
2017	将强化学习与半马尔科夫决策过程结合，用于学习智能体如何直接与环境进行交互来学习策略。	Yang, J., Li, Y., Chen, H., & Li, J. (2017, November). Average Reward Reinforcement Learning for Semi-Markov Decision Processes. In International Conference on Neural Information Processing (pp. 768-777). Springer, Cham.

发展分析

瓶颈

SMDP是一类广泛而又重要的随机动态系统,目前研究活跃,取得了丰富的成果，瓶颈问题很少有论文涉及。

未来发展方向

半马尔科夫过程考虑了设备处在各个状态的平均停留时间，因此可以被应用在具备多个状态，并且考虑各个平稳状态持续时间的系统中。其未来发展方向有以下几个：

模型向一般化发展,考虑连续受控SMDP.作为一类连续时间模型,现有文献研究的SMDP模型大都是在跳跃点受控，未来会是连续受控的SMDP模型。
SMDP新的优化问题的研究.伴随着实际情形的不断变化,新的优化准则和问题必将不断提出,这也为推动SMDP的发展注入了动力。

Contributor: Yilin Pan

简介