学位论文 > 优秀研究生学位论文题录展示

激励学习的若干新算法及其理论研究

作　者: 殷苌茗
导　师: 王汉兴
学　校: 上海大学
专　业: 运筹学与控制论
关键词: 激励学习 Markov决策过程算法风险敏感度最优策略
分类号: O234
类　型: 博士论文
年　份: 2006年
下　载: 243次
引　用: 1次
阅　读: 论文下载

内容摘要

本博士论文大体上可以分成两大部分，第一部分我们给出了激励学习的一些新算法，其目的是为了改进现有算法所面临的诸于维数灾难与计算速度等问题。第二部分是我们在基于风险敏感度概念的基础上，研究了与激励学习有关的最优方程与最优解的理论问题。本论文首先提出了一种新的激励学习算法，即我们所说的激励学习的遗忘算法。这种算法的基本思想是基于下面的考虑：以前的有关激励学习算法都只是通过对状态被访问次数的短时记忆来确定状态值函数空间的更新长度。对于这些算法来说，无论是用lookup表的形式，还是用函数逼近器的形式，对所有状态的值函数都必须要全部记忆。这些方法对大状态空间问题会导致需要指数增长的记忆容量，从而呈指数地减慢计算速度。Sutton等人考虑过这个问题，但始终没有得到满意的解决方案。基于上述考虑，将记忆心理学中有关遗忘的基本原理引入值函数的激励学习算法的研究之中，特别是对于著名的SARSA(λ)算法，形成了一类适合于值函数激励学习的遗忘算法。我们提出了基于效用聚类的激励学习算法。这种算法的模型使用了POMDP的某些概念。在激励学习的诸多算法中，把非常多的精力集中在如何对系统的大状态空间进行有效的分解，其中U-Tree算法是其之一。但是，由于U-Tree算法的一个最大的问题是边缘节点生成的随意性和统计检验的计算负担，各种扩展方法都没有解决这个问题。本文提出了一种新的效用聚类激励学习算法，即我们称之为U-Clustering算法。该算法完全不用进行边缘节点的生成和测试，克服了上述提及的U-Tree算法的致命弱点。我们的新算法首先根据实例链的观测动作值对实例进行聚类，然后对每个聚类进行特征选择，最后再进行特征压缩，经过压缩后的新特征就成为新的叶节点。实验与仿真结果表明，我们的新算法比一般的U-Tree算法更有效。针对具有大状态空间的环境系统以及系统状态不完全可观测所面临的问题，本论文提出了求解部分可观测Markov决策过程的动态合并算法。这个方法利用区域这个概念，在环境状态空间上建立一个区域系统，而Agent在区域系统的每个区域上独自实现其最优目标，就好像有若干个Agent在并行工作一样。然后把各组成部分的最优值函数按一定的方式整合，最后得出POMDP的最优解。另外还对提出的算法进行了复杂度分析和仿真实验。通过对New York Driving的仿真和算法的实验分析，结果表明动态合并算法对于大状态空间上的求解问题是一个非常有效的算法。本文提出了风险敏感度的激励学习广义平均算法。这个算法通过潜在地牺牲解的最优性来获取鲁棒性(Robustness)。提出这种算法的主要原因是因为，如果在理论模型与实际的物理系统之间存在不匹配，或者实际系统是非静态的，或者控制动作的“可使用性”随时间的变化而变化时，那么鲁棒性就可能成为一个十分重要的问题。我们利用广义平均算子来替代最大算子max(或sup)，对激励学习问题中的动态规划算法进行了研究，并讨论了它们的收敛性，目的就是为了提高激励学习算法的鲁棒性。我们提出了风险敏感度渐进策略递归激励学习算法并对策略的最优性进行了讨论。当系统的计算出现维数灾难时，比如在Markov决策过程的求解问题中，如果系统的动作空间非常之大，那么利用一般的策略递归(PI)算法或值递归(Ⅵ)算法，来进行策略的改进计算是不实际的。我们这个算法所关注的问题是，当状态空间相对较小而动作空间非常之大时如何得到最优策略或好的策略。在本算法的策略改进过程中，不需在整个动作空间上对值函数进行最大化运算，而是通过策略转换的方法来直接处理策略问题的。本文的另一个主要内容是，我们对多时间尺度风险敏感度Markov决策过程的最优方程与解的最优性问题进行了初步研究。由于需要使智能体能够适应更加复杂的环境，因此大规模控制问题在实际应用中显得越来越重要。在本章中采用了一种更加符合实际情况的复杂环境，即多时间尺度下的Markov决策过程模型，并利用风险敏感度的概念，第一次提出了多时间尺度风险敏感度Markov决策过程的概念。这是一个全新的问题。我们利用效用函数和风险敏感度等概念，讨论了二时间尺度风险敏感度Markov决策问题，然后给出了二时间尺度风险敏感度Markov决策过程的Bellman最优控制方程的一般形式，并证明了最优值函数满足这个Bellman最优控制方程，同时还得到了一些相关的结论。本博士论文所讨论的都是现阶段关于激励学习的热点和难点问题。激励学习方法已经成为控制理论与人工智能研究的最重要的分支之一，还有许多问题亟待解决。在本文的最末，我们给出了对这些问题的研究方向和未来的工作，希望能起到抛砖引玉的作用。

全文目录

摘要  6-8
ABSTRACT  8-11
目录  11-15
第一章绪论  15-25
  1.1 引言  15
  1.2 问题的提出与本研究的意义  15-18
  1.3 国内外关于激励学习的研究历史与现状  18-21
  1.4 本博士论文所做的工作  21-25
第二章激励学习算法与Markov决策过程  25-41
  2.1 引言  25
  2.2 激励学习  25-29
    2.2.1 激励学习的概念  25-28
    2.2.2.激励学习的常规算法  28-29
  2.3 Markov决策过程(MDP)  29-38
    2.3.1 Markov决策过程的定义  29-31
    2.3.2 求解Markov决策过程的动态规划方法  31-34
    2.3.3 策略递归算法  34-35
    2.3.4 几种常用的最优准则  35-36
    2.3.5 几种常规的激励学习算法  36-38
  2.4 部分可观测Markov决策过程(POMDP)  38-40
  2.5 小结  40-41
第三章激励学习的遗忘算法  41-57
  3.1 引言  41-42
  3.2 问题的背景  42-43
  3.3 离线策略和在线策略算法  43
  3.4 SARSA(λ)算法  43-45
  3.5 遗忘准则和Forget-SARSA(λ)  45-50
    3.5.1 遗忘准则  45-46
    3.5.2 Forget-SARSA(λ)算法  46-47
    3.5.3 算法性质分析  47-49
    3.5.4 存在的问题和解决办法  49-50
    3.5.5 与限制搜索算法的区别  50
  3.6 迷宫实验  50-53
  3.7 杆平衡(pole balancing)实验  53-54
  3.8 平均渐近遗忘TD(λ)算法  54-55
    3.8.1 平均渐近瞬时差分学习算法  54
    3.8.2 基于平均渐近TD(λ)的遗忘算法  54-55
  3.9 结论与未来的工作  55-57
第四章基于效用聚类的激励学习算法  57-73
  4.1 引言  57-58
  4.2 U-Tree算法  58-61
  4.3 效用聚类算法U—Clustering  61-64
    4.3.1 U-Clustering算法的基本原理  61-63
    4.3.2 U-Clustering算法的执行步骤  63-64
  4.4 仿真研究  64-72
    4.4.1 基本环境描述与复杂性分析  64-68
    4.4.2 基本环境仿真实验  68-70
    4.4.3 限制环境仿真实验  70-72
  4.5 结论与未来的工作  72-73
第五章部分可观测Markov决策过程的动态合并算法  73-89
  5.1 引言  73-74
  5.2 POMDP模型  74-76
  5.3 区域可观测的POMDP  76-78
    5.3.1 辅助系统  76-77
    5.3.2 区域系统  77-78
  5.4 合成的部分可观测Markov决策过程  78-82
    5.4.1 多目标Markov决策过程  78-79
    5.4.2 合成的部分可观测Markov决策过程  79-82
  5.5 动态合并算法  82-85
    5.5.1 动态合并问题  82
    5.5.2 动态合并算法  82-85
  5.6 实验与仿真  85-87
    5.6.1 基本环境仿真实验  85-86
    5.6.2 限制环境仿真实验  86-87
  5.7 结论与展望  87-89
第六章风险敏感度Markov决策过程  89-95
  6.1 引言  89-90
  6.2 概念与决策模型  90-91
  6.3 效用函数  91-92
  6.4 性能指标与最优方程  92-93
  6.7 小结  93-95
第七章风险敏感度的激励学习广义平均算法  95-109
  7.1 引言  95-96
  7.2 概念与模型  96-99
    7.2.1 风险敏感度动态规划算法与Bellman方程  96-98
    7.2.2 关于广义平均的一些基本结论  98-99
  7.3 基于动态规划风险敏感度的递归不动点  99-106
  7.4 策略空间的最优性  106-107
  7.5 结论与未来的工作  107-109
第八章风险敏感度渐进策略递归激励学习算法  109-129
  8.1 引言  109-110
  8.2 背景模型  110-114
  8.3 基于风险敏感度的渐进策略递归  114-125
    8.3.1 算法描述  114-117
    8.3.2 初始化与策略选择  117-118
    8.3.3 策略转换  118-122
    8.3.4 策略变异  122-124
    8.3.5 子策略组的结构与停止规则  124
    8.3.6 收敛性  124-125
  8.4 算法的并行化处理  125-127
  8.5 结论与将来的工作  127-129
第九章多时间尺度风险敏感度Markov决策过程的最优方程与解的最优性问题  129-145
  9.1 引言  129-130
  9.2 多时间尺度风险敏感度Markov决策过程  130-134
  9.3 最优方程与解的最优性条件  134-144
  9.4 结论与未来的工作  144-145
第十章结论与对未来研究的展望  145-150
参考文献  150-159
作者在攻读博士学位期间公开发表的以及与博士论文有关的论文  159-161
作者在攻读博士学位期间所参与的科研项目  161-162
致谢  162-163

激励学习的若干新算法及其理论研究

内容摘要

全文目录

相似论文