摄动马尔可夫决策与哈密尔顿圈
2009-4
中国科学技术大学出版社
刘克
332
无
马氏决策过程是一个非常有用的决策分析工具，已经成功的用于解决很多实际问题。利用马氏决策过程的建模思想，可以将一些离散数学中的传统问题描述为特殊的马氏决策过程加以考虑。通过优化这些特殊的马氏决策过程，不仅可以为解决这些传统问题提供新的思路，而且还可以促进马氏决策过程本身理论的发展。但是，在研究这类特殊马氏决策过程时，只有引入摄动因素才能有效的处理问题，所以我们还介绍了马氏决策的摄动理论。本书的内容包括一些基本的马氏决策过程知识，主要集中在有限状态和有限行动的马氏决策过程上。然后介绍了有关马氏决策过程的摄动理论。最后，利用前面的内容，比较详细的介绍了摄动马氏决策与哈密尔顿圈之间的关系和近些年的最新研究成果，提出了一些这个领域里人们现在最为感兴趣的研究问题。 本书适用于三种读者，一个是希望利用马氏决策过程建立有效的模型来分析决策行为的读者，通过前四章的阅读可以了解基本的分析工具，后面的阅读可以使读者获得建立具体模型并进行分析的一些技巧；二是为希望利用这个随机优化的工具研究离散数学或者其他相关科学里的问题的读者提供思路；最后，对于希望发展马氏决策过程理论的读者，可以了解这方面的动态，尽快介入这方面的前沿研究领域。
总序前言主要符号表第一部分 马氏决策过程与摄动 第1章 绪论 1.1 序列决策模型 1.2 马氏决策过程的例子 1.3 马氏决策过程的定义与记号 1.3.1 决策时刻与周期 1.3.2 状态与行动集 1.3.3 转移概率和报酬 1.3.4 历史、决策规则与策略 1.3.5 诱导过程、效用准则与马氏策略优势 1.4 马氏决策过程的起源和发展 第2章 有限阶段模型 2.1 最优准则 2.2 有限阶段的策略迭代和最优方程 2.3 最优策略的存在性和算法 2.4 最优策略的结构 2.5 单调策略的最优性 第3章 无限阶段折扣模型 3.1 最优准则 3.2 最优方程 3.3 最优策略的存在性 3.4 策略迭代算法 3.5 值迭代算法 3.6 改进的策略迭代算法 3.7 线性规划算法 3.8 最优单调策略 3.9 最优策略的结构 第4章 无限阶段平均模型 4.1 最优准则 4.2 最优平稳策略的存在性 4.3 平稳策略的一些特征 4.4 最优方程与策略迭代算法 4.5 单链的线性规划与相关问题 4.5.1 极限平均频率 4.5.2 带约束模型问题 4.5.3 方差问题 4.6 多链的线性规划与相关问题 4.6.1 对偶可行解与随机平稳策略 4.6.2 基本可行解与确定性决策规则 4.6.3 最优解与最优策略 4.7 平均准则下的Bellman最优原则 第5章 摄动MDP 5.1 预备知识 5.2 一些基本记号和定义 5.3 摄动平均问题的渐进性和极限控制原则 5.4 折扣准则的摄动问题 5.5 一般的摄动 5.6 单摄动极限平均MDP的算法 5.6.1 假设与渐进性质 5.6.2 数学规划和极限马尔可夫决策问题 5.6.3 聚合一分解算法 5.7 进一步的研究进展 5.7.1 折扣权重摄动模型 5.7.2 折扣平均权重摄动问题第二部分 摄动MDP与哈密尔顿圈 第6章 HC与MDP 6.1 哈密尔顿圈问题 6.2 有向图到MDP的嵌入 6.3 平稳策略的分类 6.4 约束折扣MDP与HC 6.5 约束折扣MDP的求解 6.6 HC与TSP 第7章 HCP嵌入MDP的摄动 7.1 转移概率的摄动 7.1.1 转移概率的对称线性摄动 7.1.2 转移概率的非对称线性摄动 7.1.3 转移概率的非对称二次摄动 7.2 摄动下子图的稳态分布 7.3 非对称线性摄动下的几个例子 7.4 非对称线性摄动下HC的性质 7.5 更为精细的分析 7.6 开问题和有关猜想 第8章 频率空间上的分析 8.1 长期平均MDP频率空间中的HCP 8.2 二次非对称摄动与新目标函数 8.3 启发式内点算法 8.3.1 内点算法简介 8.3.2 关于(QP)求解的启发式算法 8.3.3 数值计算例子 8.4 一些开问题及其他 第9章 双随机摄动与HC 9.1 基本矩阵 9.2 再谈双随机摄动 9.3 渐进表达式 9.4 优化问题与HC的全局最优性 9.4.1 非线性规划问题 9.4.2 方向导数 9.4.3 HC既是局部也是全局最小 9.5 哈密尔顿间隙 9.6 对称双随机矩阵的探讨 9.7 混合时间及其变化的最小化 9.7.1 从不可约链到一般的情形 9.7.2 迹与对角线上的元素 9.7.3 摄动带来的好处 9.7.4 带有对称线性摄动的双随机矩阵 第10章 将来的研究方向和结束语 10.1 将来的研究方向 10.2 结束语参考文献索引
第一部分 马氏决策过程与摄动 第1章 绪论 人们在做决策的时候，不仅要考虑做决策当前的效果，也要照顾到所做的决策对长远利益的影响．正像一个长跑运动员，他要根据需要跑的距离而合理分配自己的体力，以避免尚未跑完全程就筋疲力尽．因此，做决策不是孤立的，也就是说今天的决策会影响到明天，而明天的决策会影响到将来，如果不顾及对将来的影响而只考虑当前的利益做决策，从长远的角度来看，效果不会很好。 本书涉及的马尔可夫决策过程是在不确定环境下的一类序列决策模型，决策者不仅要考虑决策结果的即时效应，还要考虑为将来继续做决策创造机会，也就是要考虑这次选择决策后对将来发展过程的影响．看上去这个模型似乎不复杂，但是它的应用极其广泛，而且产生了丰富的数学理论，这一章主要通过一些例子来说明决策的过程和动态，然后给出马尔可夫决策过程的一般记号与定义，最后叙述了马氏决策过程的发展简史和一些比较有影响的相关书籍。 1.1 序列决策模型 我们用图1.1描述多阶段决策过程的一个完整步骤，在时刻t，控制系统的决策者观察到系统当前所处的状态，并根据这个状态选取一个行动。
本书主要介绍了两个方面的研究工作：一个是马氏决策过程的理论及其摄动问题。在介绍了一般的马氏决策过程理论模型之后，本书还介绍了一些最新的相关进展。特别的，本书专门介绍马氏决策过程的摄动问题。 另一方面的工作就是将离散数学中的一类经典问题，诸如哈密尔顿圈问题、旅行商问题等等嵌入到凸域上的、可处理的分析问题中去，使得问题可能得到解决。很明显，这些经典问题的主要困难是来自于问题定义域的离散性。将原始的确定性问题的关键元素赋予概率解释之后，就可以获得扩展解域的凸化结构。以哈密尔顿圈问题或者旅行商问题为例，可以建立一种技术将其嵌入到单摄动的马氏决策过程中去。其主要思想就是将子图解释为由确定性策略（如果有，就包含哈密尔顿圈）为顶点所构成的凸多面体空间中的元素，即为随机平稳策略所对应。 本书主要从理论和算法两个方面着手考虑哈密尔顿圈或者旅行商问题，揭示了图论的理论结构、概率代数和相应的马尔可夫链之间的一些关系，包括首次返回时间的矩、访问节点的极限频率、用于分析马尔可夫链的某些矩阵的谱等等。本书还列出了一些尚未解决的开问题，以供读者欣赏和研究。
无
导师编写的教材，很实用，是马氏决策的经典教材