马尔科夫决策过程主要用于建模决策模型。考虑一个动态系统，它的状态是随机的，必须做出决定，而代价由决策决定。然而，在许多的决策问题中，决策阶段之间的时间不是恒定的，而是随机的。半马尔可夫决策过程（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