马尔科夫决策过程MDPs.docx

《马尔科夫决策过程MDPs.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数学模型-MATLAB工具箱-马尔可夫决策过程-MDPs前言：MDPs提供了一个数学框架来进行建模，适用于结果部分随机部分由决策者控制的决策情景。由于其在数学建模或学术发表中经常被用到，这里我们从实用的角度对其做一些归纳整理，案例涉及到大数据应用方面的最新研究成果，包括基本概念、模型、能解决的问题、基本算法（基于MATLAB或R工具箱）和应用场景。最后简单介绍了部分可观察马尔可夫决策过程(POMDP)。由于相关的理论和应用研究非常多，这里我们只介绍最基本的东西（但是提供了必要而丰富的展开），并提供相应的参考文献和工具

2、箱链接，以期帮助读者更快上手，至于更加深入的研究和更加细致的应用，则需要参照相关研究领域的学术文献。一、基本概念（1）序贯决策（SequentialDecision）[1]：用于随机性或不确定性动态系统的最优化决策方法。（2）序贯决策的过程是：从初始状态开始，每个时刻作出最优决策后，接着观察下一时刻实际出现的状态，即收集新的信息，然后再作出新的最优决策，反复进行直至最后。（3）无后效性无后效性是一个问题可以用动态规划求解的标志之一。某阶段的状态一旦确定，则此后过程的演变不再受此前各种状态及决策的影响，简单的说，就是“

3、未来与过去无关”，当前的状态是此前历史的一个完整总结，此前的历史只能通过当前的状态去影响过程未来的演变。（4）马尔可夫决策过程系统在每次作出决策后下一时刻可能出现的状态是不能确切预知的，存在两种情况：①系统下一步可能出现的状态的概率分布是已知的，可用客观概率的条件分布来描述。对于这类系统的序贯决策研究得较完满的是状态转移律具有无后效性的系统，相应的序贯决策称为马尔可夫决策过程，它是将马尔可夫过程理论与决定性动态规划相结合的产物。②系统下一步可能出现的状态的概率分布不知道，只能用主观概率的条件分布来描述。用于这类系统的

4、序贯决策属于决策分析的内容。注：在现实中，既无纯客观概率，又无纯主观概率。客观概率是根据事件发展的客观性统计出来的一种概率。主观概率与客观概率的主要区别是，主观概率无法用试验或统计的方法来检验其正确性。客观概率可以根据历史统计数据或是大量的试验来推定。客观概率只能用于完全可重复事件，因而并不适用于大部分现实事件。为什么引入主观概率：有的自然状态无法重复试验。如：明天是否下雨，新产品销路如何。主观概率以概率估计人的个人信念为基础。主观概率可以定义为根据确凿有效的证据对个别事件设计的概率。这里所说的证据，可以是事件过去的

5、相对频率的形式，也可以是根据丰富的经验进行的推测。比如有人说:“阴云密布,可能要下一场大雨!”这就是关于下雨的可能性的主观概率。主观概率具有最大的灵活性，决策者可以根据任何有效的证据并结合自己对情况的感觉对概率进行调整。二、和马尔可夫链的联系马尔科夫决策过程是一个离散时间随机控制过程。在每个时间步，决策过程处于某个状态S，决策者可能选择在S状态下任何可能的动作a。然后决策过程在下一个时间步随机地进入一个新的状态S`，同时给决策者相应的reward，记为Ra(s,s`)。进入新状态S`的概率会受到决策者选择的动作a的影

6、响，可以用状态转换函数Pa(s,s`)来表示。因此，下一个状态S`依赖于当前状态S和决策者的动作a。在给定S和a时，S`和之前所有的状态或动作无关，换句话说具有无后效性。马尔可夫决策过程是马尔可夫链的一个扩展，区别在于马尔可夫决策过程引入了动作和回馈，即允许决策者进行选择并给予决策者激励。极端情况下，当每个状态都只允许一种动作而且所有的reward都相同时，马尔可夫决策过程就变成了马尔可夫链。一、具体模型上图是[2]中给出的一个只有三个状态、两种动作的简单MDP。马尔可夫决策过程可以用一个四元组来描述：(S,A,P(

7、·,·),R(·,·))。其中：S是有限个状态的集合；A是有限个动作的集合；As是S状态下允许的所有动作的集合；Pa(S,S`)=Pr(St+1=S`

8、St=S,at=a)，表示t时刻在状态S中选择动作a导致进入状态S`的概率。Ra(S,S`)是从状态S进入状态S`得到的实时反馈(reward)。注意，马尔可夫决策过程的理论并不要求S和A是有限集合，但是在一些基本算法中有这样的要求。二、要解决的问题MDP的核心问题是找到每个状态S下决策者选择的动作去D(s)。目标是找到一个函数D，使得某些累积量最大化。一个例子如下：

9、衰减和其中at=D(s)；·是衰减系数，在0到1之间；R是reward。由于无后效性，最佳决策方法仅为s的函数，即D(s)。三、基本算法假设我们知道状态转移概率P和反馈函数R，目标是求出决策规则D(s)使得上述的衰减和最大。算法的具体实现对计算机基础要求较高，故这里我们推荐采用MATLAB工具箱进行求解。NEWS:Version4.0.1(Ja