2024年2月20日发(作者：)
本科毕业设计(论文)
学院(部)
题
年级
班级
姓名
目
计算机科学与技术学院
基于强化学习的Gambler策略研究与评价
专业 软件工程（嵌入式）
学号
职称
指导教师
论文提交日期
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作 者 签 名： 日 期：
指导教师签名： 日 期：
使用授权说明
本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名： 日 期：
I
学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。
作者签名： 日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名： 日期： 年 月 日
导师签名： 日期： 年 月 日
II
注 意 事 项
1.设计（论文）的内容包括：
1）封面（按教务处制定的标准封面格式制作）
2）原创性声明
3）中文摘要（300字左右）、关键词
4）外文摘要、关键词
5）目次页（附件不统一编入）
6）论文主体部分：引言（或绪论）、正文、结论
7）参考文献
8）致谢
9）附录（对论文支持必要时）
2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。
3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。
4.文字、图表要求：
1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写
2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画
3）毕业论文须用A4单面打印，论文50页以上的双面打印
4）图表应绘制于无格子的页面上
5）软件工程类课题应有程序清单，并提供电子文档
5.装订顺序
1）设计（论文）
2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订
3）其它
III
目 录
摘 要 ..................................................................................................................... 1
ABSTRACT .............................................................................................................. 2
第一章 前 言 ..................................................................................................... 1
1.1背景概述 ........................................................................................................... 1
1.2 强化学习的应用 .............................................................................................. 1
1.3 论文结构安排.................................................................................................. 2
第二章 强化学习 ..................................................................................................... 3
2.1 强化学习的原理和模型 ................................................................................. 3
2.2 强化学习系统的主要组成要素 ..................................................................... 4
2.3 马尔可夫决策过程 (MDP) ............................................................................ 6
2.4 强化学习的基本算法 ..................................................................................... 7
2.4.1 动态规划(Dynamic Programming, DP) ..................................................... 7
2.4.2 蒙特卡罗算法 (Monte Carlo method, MC) .............................................. 7
2.5 强化学习中有待解决的问题 ......................................................................... 8
2.6 本章小结 .......................................................................................................... 8
第三章 动态规划分析 ............................................................................................. 8
3.1 动态规划的适用条件 ..................................................................................... 9
3.1.1最优化原理 .................................................................................................. 9
3.1.2无后向性 ...................................................................................................... 9
3.1.3子问题的重叠性 .......................................................................................... 9
3.2 算法流程 ........................................................................................................ 10
3.2.1策略评估 .................................................................................................... 10
IV
3.2.2策略改进 .................................................................................................... 11
3.3 寻找最优策略................................................................................................ 11
3.3.1策略迭代 .................................................................................................... 11
3.3.2值迭代 ........................................................................................................ 11
3.4 动态规划的效率 ........................................................................................... 12
3.5 本章小结 ........................................................................................................ 13
第四章 实验平台分析与实现 ............................................................................... 13
4.1 实验平台描述................................................................................................ 13
4.1.1系统概述 .................................................................................................... 13
4.1.2系统运行环境 ............................................................................................ 13
4.2 Gambler问题仿真 ........................................................................................ 14
4.3 实验平台概要设计 ....................................................................................... 14
4.3.1底层框架模型 ............................................................................................ 14
4.3.2 Gambler问题模型 ..................................................................................... 17
4.3.3界面设计 .................................................................................................... 18
4.4 实验平台的详细设计 ................................................................................... 19
4.4.1类和接口 .................................................................................................... 19
4.4.2核心算法示例 ............................................................................................ 23
4.5 本章小结 ........................................................................................................ 26
第五章 实验结果分析 ........................................................................................... 27
5.1 实验结果 ........................................................................................................ 27
5.2 Gambler仿真结果分析 ................................................................................ 28
5.2.1Gambler 在不同P值下的策略 ................................................................ 28
V
5.2.2策略分析与评价 ........................................................................................ 29
5.2.3计算误差对策略的影响 ............................................................................ 30
5.3 本章小结 ........................................................................................................ 31
第六章 总结与展望 ............................................................................................... 31
6.1 课题总结 ........................................................................................................ 31
6.2 进一步的研究与展望 ................................................................................... 32
参考文献 ................................................................................................................. 34
致 谢 ..................................................................................................................... 36
VI
摘 要
强化学习是一种重要的机器学习方法。强化学习通过感知环境状态信息来学习动态系统的最优策略，通过试错法不断地与环境进行交互来改善自己的行为，并具有对环境的先验知识要求低的优点，是一种可以应用到实时环境中的在线学习方式。因此在智能控制，机器学习等领域中强化学习得到了广泛研究。
强化学习的任务就是学习从状态空间到动作空间的映射。环境对不同动作做出的评价性反馈信号决定了强化学习系统的动作选择策略。如果一个动作得到了最多的奖励，则该动作就会被采取。
本文的特点是在强化学习理论研究的基础上，以Gambler问题为仿真实验平台，对强化学习中的动态规划算法进行实现，并对不同P值下的实验结果进行分析。
关键词：强化学习，机器学习，动态规划，Gambler
作 者：李天琳
指导老师：刘 全
1
ABSTRACT
Reinforcement learning is an important machine learning method. It could
learn the optimal policy of the dynamic system through environment state
observation and improve its behavior through trial and error with the environment.
Reinforcement learning has the quality of low requirement for a priori knowledge
and is also a kind of online learning method for the real-time environment, which
is extensively explored in the field of intelligent control and machine learning.
The aim of reinforcement learning is to learn the mapping from the state
space to the action space. The selection policy of actions in the reinforcement
learning system is determined by the evaluative feedback signal which is made by
environment on different actions. If one action leading to the largest reward, it will
be taken.
The feature of this paper is that based on the basic theories and methods of
reinforcement learning, this paper applies the Gambler problem simulation
experiment to implement the dynamic programming algorithms and analyses the
results according to different P value thereafter.
Key Words: Reinforcement Learning, Machine Learning, Dynamic Programming,
Gambler
Author: Tianlin Li
Supervisor: Quan Liu
2
第一章 前 言
1.1 背景概述
学习是人类获取知识的主要形式，也是人类具有智能的显著标志，是人类提高智能水平的基本途径。建造具有类似人的智能机器是智能控制、人工智能研究的一个核心问题。要使机器具有一定智能，一种方式是靠人事先编程来建立知识库和推理机制，这具有明显的局限性。我们希望智能机具有向环境学习的能力，即自动获取知识、积累经验、不断更新和扩充知识，改善知识性能。一个学习系统是具有这样一种能力的系统，它通过与控制对象和环境的闭环交互作用，根据过去获得的经验信息，逐步改进系统自身的未来性能[1]。
在机器学习范畴，根据反馈的不同，学习技术可以分为监督学习(Supervised
learning)、非监督学习(Unsupervised learning) 和强化学习(Reinforcement learning)三大类。监督学习也称有导师的学习，这种学习方式需要外界存在一个“教师”，它可以对给定一组输入提供应有的输出结果，这种已知的输入-输出数据称为训练样本集，学习的目的是减少系统产生的实际输出和预期输出之间的误差，所产生的误差反馈给系统来指导学习。非监督学习又称无导师学习，它是指系统不存在外部教师指导的情形下构建其内部表征。
研究者发现，生物进化过程中为适应环境而进行的学习有两个特点：一个是人从来不是静止的被动的等待而是主动的对环境作试探；二是环境对试探动作产生的反馈是评价性的，生物根据环境的评价来调整以后的行为，是一种从环境状态到行为映射的学习，具有以上特点的学习就是强化学习(或称再励学习，评价学习，简记为RL)[2]。强化学习是一种以环境反馈作为输入的、特殊的、适应环境的机器学习方法。该方法不同与监督学习技术那样通过正例、反例来告知采取何种行为，而是通过试错(trial-and-error)的方法来发现最优行为策略[3]。
强化学习的概念是由Minsky在20世纪60年代最先提出的，从80年代末开始，随着对强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用也日益开展起来，成为目前机器学习领域的研究热点之一。
1.2 强化学习的应用
现在，强化学习已经成为制造业过程控制、作业调度、路径规划、WEB信息搜索、企业供应链、电子商务等领域，对目标行为优化的一种重要技术[4]。例
如，目前将强化学习理论与企业分销系统相结合，目的是将多个制造商与一个零售商组成的分销系统，他们以各自的利润最大化为目标。制造商给零售商提供奖金激励，零售商提供对应于奖金激励的服务水平，制造商需要进行为零售商提供多大奖金激励的决策，利用强化学习的启发式学习算法来优化制造商应提供的最优奖金激励。
在调度管理中，强化学习体现出了很大的经济价值。Crites和Barto将强化学习算法用于一个4个电梯、10层楼的系统中[5]。每一个电梯都有各自的位置、方向、速度和一系列表示乘客要离开的位置状态。这个系统的状态集合超过1022个，用传统方法很难管理，因此他们用反传算法训练表示Q函数的神经网络，与其它算法相比较，强化学习更加优越。另外强化学习在蜂窝电话系统中动态信道分配和Job shop规划问题上都有应用。
在游戏比赛中，强化学习理论也被广泛地应用。最早应用的例子是Samuel的下棋程序，近来，Tesauro把瞬时差分法应用于Backgamon，这就是著名的TD-Gammon。Backgammon大约有1020个状态[6]，Tesauro 采用三层BP神经网络把棋盘上的棋子位置与棋手获胜率联系起来，通过训练取得在40盘比赛中仅负1盘的战绩。
强化学习在多移动机器人系统中的应用研究正日益受到关注。Turcher Balch提出Clay控制结构应用于机器人足球赛，不同于基于行为控制结构的强化学习，他将强化学习与motor schemas 有机结合，使得系统既具有强化学习的自适应能力，又有motor schemas的实时性能。Mataric 利用改进的Q学习算法实现四个机器人执行foraging任务，事先利用领域知识将状态空间到动作空间的映射转化为条件行为来压缩状态空间的规模，加速学习[7]。
1.3 论文结构安排
本文以强化学习理论为基础，在Gambler仿真平台中实现了动态规划算法，并对实验结果进行了深入分析。论文结构安排如下：
第一章，前言。该章介绍了强化学习的背景及其应用。
第二章，强化学习。该章介绍了强化学习的基本原理和模型，强化学习系统的主要组成要素以及马尔可夫决策过程 (MDP)，然后介绍了强化学习的基本算法，包括动态规划，蒙特卡罗算法，最后提出了强化学习过程中有待解决的问题。
第三章，动态规划分析。该章重点介绍了动态规划理论，包括动态规划的适
用条件，算法流程以及寻找最优策略的两种迭代方式，最后分析了动态规划的效率。
第四章，实验平台分析与实现。该章详细分析了实验平台的概要设计和详细设计。
第五章，实验结果分析。该章分析了仿真平台的实验结果，对Gambler在不同P值下的策略进行了深入比较和分析。
第六章，总结与展望。该章对本文的研究工作进行了总结，对强化学习课题的前景做了进一步的展望。
第二章 强化学习
强化学习技术是从控制理论、统计学、心理学等相关学科发展而来，最早可以追溯到巴普洛夫的条件反射实验[8]。强化学习要解决的是这样一个问题：一个能够感知环境的自治Agent，怎样通过学习选择能够达到其目标的最优动作[9]。当Agent在环境中做出每个动作时，施教者会提供奖励或惩罚信息，以表示结果状态正确与否。例如，在训练Agent进行棋类对弈时，施教者可在游戏胜利时给出正回报，而在游戏失败时，给出负回报，其他的时候给出零回报。
2.1 强化学习的原理和模型
强化学习的基本原理为：如果Agent的某个行为策略导致环境正的奖励，那么Agent产生这个行为策略的趋势将会加强；如果Agent的某个行为策略导致环境负的奖励，那么Agent产生这个行为策略的趋势将会减弱，最终消亡。由于强化学习不像监督学习那样有教师信号，它仅有一个强化信号来判断动作的好坏，所以它的学习过程必定是漫长的。
强化学习把学习看作试探过程，基本模型如图2.l所示。在强化学习中，Agent选择一个动作a作用于环境，环境接收该动作后发生变化，同时产生一个强化信号(奖或罚)反馈给Agent，Agent再根据强化信号和环境的当前状态S再选择下一个动作，选择的原则是使受到正的报酬的概率增大[10]。选择的动作不仅影响立即回报值而且还影响下一时刻的状态及最终回报值。强化学习的目的就是寻找一个最优策略，使得Agent在运行中所获得的累计回报值最大[11]。
状态S
Agent
奖赏r
动作a
环境
图2.1 强化学习的基本结构
Agent与环境进行交互是，在每一时刻循环发生如下事件序列：
(1) Agent感知当前的环境状态；
(2) 针对当前的状态和强化值，Agent选择一动作执行；
(3) 当Agent所选择的动作作用于环境时，环境发生变化，即环境状态转移至新状态并给出奖赏(强化信号r)；
(4) 奖赏(强化信号r)反馈给Agent。
2.2 强化学习系统的主要组成要素
策略
状态值函数
瞬时奖惩
模型
图2.2 强化学习的四个要素
如图2.2所示，除了Agent和环境，一个强化学习系统还有四个主要的组成要素：策略(policy)、状态值函数(value function)、瞬时奖惩函数(reward function)和环境的模型(model)。
Agent的任务是产生控制动作，动作的选定则是根据策略得到的，所以说策略是状态到动作的映射：SA。策略是强化学习的核心，因为策略直接决定了Agent的动作，即告诉Agent选择什么动作，策略的好坏最终决定了Agent的行动和整体性能，策略具有随机性。
瞬时奖惩函数是在与环境交互的过程中，获取的奖励信号，该函数反应了Agent所面临的任务的性质，同时，它也可以作为Agent修改策略的基础。奖赏信号R是对所产生动作的好坏作一种评价，奖赏信号通常是一个标量信号，例如用一个正数表示奖，而用负数表示罚，一般来说正数越大表示奖的越多，负数越小表示罚的越多。强化学习的目的就是使Agent最终得到的总的奖赏值达到最大。瞬时奖惩函数往往是确定的、客观的，为策略的选择提供依据，即告诉Agent选择什么动作是好的。
如果说瞬时奖惩函数是对一个状态(或状态-动作对)的即时评价，那么状态值函数就是从长远的角度来考虑一个状态(或状态-动作对)的好坏。值函数又称为评价函数。状态st的值，是指Agent在状态st根据策略π执行动作at及采取后续策略所得到的积累奖赏的期望，记为V(st)。
环境的模型是某些强化学习系统的另一个元素，并不是所有的强化学习系统都需要建立环境的模型。
图2.2中给出了这四种要素之间的关系。它们自底向上地构成了强化学习的学习结构。首先，系统所面临的环境由环境模型定义，模型是学习环境的基础。aa但是由于模型中Pss只能使用瞬时奖惩选择策略。又因为考'函数和Rss'函数未知，虑到环境模型的不确定性和目标的长远性，所以产生了介于策略和瞬时奖惩之间的状态值函数。即：
Rtrt1rt2rt3krtk1 (2.1)
2k0这里错误！未找到引用源。是一个参数，错误！未找到引用源。，称为折扣率。
V(s)E{Rtsts}
E{krtk1sts}
k0E{rt1krtk2sts}
k0ak(s,a)PRss'E{rtk2st1s'}
as'k0ass'aa(s,a)Pss'[Rss'V(s')] (2.2)
as'根据Bellman最优策略公式，在最优策略*下，其值函数的定义如下：
V*(s)maxE{rt1V*(st1)sts,ata}
aA(s)aa*maxPss'[Rss'V(s')] (2.3)
aA(s)s'
2.3 马尔可夫决策过程 (MDP)
在理想状况下，往往希望一个状态能够简练地抽象总结过去的感觉，然而这种方式又能保留所有相关信息。正常的来说，这比只要求即时感觉要求得更多，但是比要求全部的过去感知历史要少得多。一个成功保留所有相关信息的状态信号称为马尔可夫的，或者说具有马尔可夫性质。比如，一个棋子的位置——当前的在棋盘上所有棋子的结构——将作为一个马尔可夫状态，因为它汇集了所有关于引导它完成位置序列的重要的东西。虽然关于这个序列的很多信息丢失了，但是所有有关于这个游戏的最重要的东西被保留下来了。
对于所有在过去事件中的s'，r，和所有的可能值：st,at,rt,st1,at1,...,r1,s0,a0来说，如果状态信号有马尔可夫特性，那么环境在t1的响应只取决于在t时刻的状态和动作的表示，在此情况下，环境和任务是一体的，都称为具有马尔可夫性质，环境的动态量可以定义为：
Pr{st1s',rt1r|st,at}(2.4)
满足马尔可夫性质的强化学习任务被称为是马尔可夫决策过程或者MDP。很多强化学习问题基于的一个关键假设就是Agent与环境之间的交互可以被看成一个马尔可夫决策过程(MDP)，因此强化学习的研究主要集中于对Markov的问题处理。
Markov决策过程的模型可以用一个四元组S,A,T,R表示：S为可能的状态集合，A为可能的动作集合，T:SAT是状态转移函数；R:SAR是奖赏函数[1]。在每一个时间步k，环境处于状态集合S中的某状态xk，Agent选择动作集合A中的一个动作ak，收到即时奖赏rk，并转移至下一状态yk。状态转移函数T(xk,ak,yk)表示在状态xk执行动作ak转移到状态yk的概率可以用Pxkyk(ak)表示。状态转移函数和奖赏函数都是随机的。Agent目标就是寻求一个最优控制策略，使值函数最大[12]。
2.4 强化学习的基本算法
大多数关于强化学习的方法研究都是建立在MDP理论框架之上的，通过MDP建模，强化学习问题一般可采用迭代技术更新值函数的估计值来获得最优策略。当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。根据在学习过程中Agent是否需要学习MDP知识，强化学习可以分为模型无关法(model-free)和基于模型法(model-base)。动态规划属于基于模型法，而蒙特卡罗算法则属于模型无关法。
2.4.1 动态规划(Dynamic Programming, DP)
动态规划方法是利用值函数来搜索好的策略方法，适用于解决大规模问题，设环境是一个有限马尔可夫集，对任意策略，如果环境的动态信息完全知道，aa如：策略和Rss'，Pss'已经知道，为了减少计算量，我们常用值迭代法来近似求出V0,V1,V2„„，其更新公式为：
Vk1(s)E{rt1Vk(st1)|sts}
aa(s,a)Pss'[Rss'Vk(s')]as
(2.5)
常规的动态规划方法主要有以下三种方法:第一种是值函数迭代法，其本质是有限时段的动态规划算法在无限时段上的推广，是一种逐次逼近算法，该算法与强化学习有着密切的联系；第二种是策略迭代，这是一种基于Bellman最优方程的算法；第三种是改进的策略迭代法，综合了前面两种算法，也称为一般化策略迭代法，是许多强化学习算法的基本思想的来源之一[13]。
动态规划算法的局限性是明显的，它容易出现“维数灾”和“建模灾”问题。其计算量会使状态变量的数量呈指数增长；它要求事先知道系统的确切模型信aa息，如Rss和P'ss'的值，而在实际的大规模随机问题中，系统的确切模型信息通常是难以获得且不易计算的。
2.4.2 蒙特卡罗算法 (Monte Carlo method, MC)
蒙特卡罗算法是一种无模型 (model-free) 的学习方法，不需要系统模型——状态转移函数和奖赏函数，只需要通过与环境的交互获得的实际或模拟样本数据
(状态、动作、奖赏值) 序列，从而发现最优策略。MC总是基于平均化取样回报来解决强化学习问题，它把要解决的问题分解为情节(episode)。当环境状态为终
止状态G时，将得到的累积回报赋予开始状态S的值函数。由于从起始状态到终止状态的过程中，S可能不止出现一次，这样对S的值函数的更新，可以有两种方法:FVMC(First Visit MC)和EVMC(Every Visit MC)。前者将回报赋予第一次访问的S,后者将每次访问S到终止状态G的回报平均化以后赋予S的值函数。两者虽然在理论上有区别，但是都可以最终收敛到最优值函数。
与动态规划方法相比，MC法直接同环境交互获得经验来优化动作行为，不需建立一个环境的动态信息模型，该算法中一些状态集的值函数的计算不依赖于其它状态集的值函数，所以我们可以在那些能够精确描述环境信息的状态子集中计算所获得的平均奖赏值。另外，它对马尔可夫性要求不是很严。
2.5 强化学习中有待解决的问题
(1) 在任一阶段，Agent都要面对如何在探索与利用之间取舍的问题。利用已知的动作可保证得到一定的奖赏，然而对一定的状态而言，探索新动作可能产生更高的奖赏，但过多的探索又会降低系统的性能。
(2) 传统的强化学习算法是基于环境的，是一个马尔可夫决策假设。系统的将来状态依赖于当前的环境状态，和以前的环境状态无关，在真实世界的大多数情况中，实际系统非常复杂，Agent不能够精确感知环境的所有状态，因此算法收敛性的假设在实际环境中得不到满足。
(3) 强化学习算法通过搜索状态空间和优化值函数得到好的策略，当系统变得复杂时，需要大量的参数来刻画它，这样会引起状态空间到动作空间映像的组合爆炸，给搜索带来了繁重的任务，进而影响行动决策的优化问题。
2.6 本章小结
本章先介绍了强化学习的原理和模型，然后介绍了强化学习系统的一些重要组成元素以及马尔可夫决策过程。此外本章还介绍了当前强化学习中的一些重要算法：动态规划、Monte Carlo算法，最后提出了一些强化学习中有待解决的问题。
第三章 动态规划分析
动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家n等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。动态规划是建立在严格的数学基础之上的，它需要一个完整、精确的环境模型。动态规划涉及到一系列算法，这些算法能用于在给定完美的马尔可夫决策过程环境模型情况下计算最优化问题。
3.1 动态规划的适用条件
任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
3.1.1 最优化原理
最优化原理可以这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。
3.1.2 无后向性
将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3.1.3 子问题的重叠性
动态规划算法的根本目的是解决冗余。其实质上是一种以空间换时间的技术，它在实现过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他算法。设原问题的规模为n，当子问题树中的子问题总数是n的超多项式函数，而不同的子问题数只是n的多项式函数时，动态规划显得特别有意义，
此时动态规划法具有线性时间复杂性。所以能够用动态规划解决的问题还有一个显著特征：子问题的重叠性。这个性质并不是动态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法比较就不具备优势。
3.2 算法流程
一般来说，强化学习和动态规划的关键思想就是用值函数去组织和构造好的策略，一旦我们找到符合Bellman最优方程的最优值函数，V*和Q*，就能很容易地得到最优策略。事实上，动态规划算法是由Bellman方程转化而来，也就是修正Bellman等式的规则以提高所期望的值函数的近似值。
在实际应用中往往按以下几个步骤进行：
(1) 分析最优解的性质，并刻画其结构特征。
(2) 递归地定义最优值。
(3) 以自底向上或自顶向下的方法计算出最优值。
(4) 根据计算最优值时得到的信息，构造一个最优解。
3.2.1 策略评估
策略评估 (policy evaluation) 是指，对于任意策略，考虑如何计算状态值函数V。对于任意sS,
aaV(s)(s,a)Pss'[Rss'V(s')]as'
(3.1)
这里(s,a)是指在策略下，状态s执行动作a的概率。在实际计算中，可以通过迭代方法来计算V值。考虑一个逼近值函数序列：V0,V1,V2,...,映射S到的V。当V存在且k时，序列{VK}通常收敛于V，这个算法被称为迭代策略评估。
为了产生每一个连续的近似值，从Vk到Vk1，对于每一个状态s，迭代策略评估都采取相同的操作：在被评估策略下，沿着所有可能的一步转换，用s的后续状态的旧值与期望的立即奖赏计算得到的新值来替换s的旧值。这个操作称为全更新。迭代策略评估的每一次迭代，一旦产生了一个新的近似值函数Vk1，就要更新每一个状态值。在实现方面，另一个关注点是算法的终止。一种典型的迭代算法的终止条件是，在每执行一次扫描过后，去检查maxsS|Vk1(s)Vk(s)|的
值，并且当这个值足够小的时候停止执行。
3.2.2 策略改进
对策略计算值函数的一个原因就是有助于发现更好的策略。假如对于任一策略确定一个值函数V,对于某些状态s应该如何判断是否应该改变策略来选择动作a(a(s))。最关键的评判标准就是计算Q(s,a)是大于还是小于V(s)。如果大于的话，在状态s下选择动作a，然后再遵循策略，要优于一直遵循策略。并且最好在以后每次遇到状态的时候都采用动作a，事实上，这一新的策略在全局上还是优于旧策略的。在这一特殊情况下所做的操作就称为策略改进原理。Q(s,a)的计算公式为：
Q(s,a)E{rt1V(st1)|sts,ata}
aa
Pss'[Rss'V(s')]
s'(3.2)
通过对原始策略的值函数使用或近似使用贪心算法，改进原始策略来制定新的策略的过程，就被称作是策略改进。
3.3 寻找最优策略
动态规划思想设计的算法从整体上看基本是按照递推关系式来进行迭代算得最优解。有两种迭代方式：策略迭代和值迭代。
3.3.1 策略迭代
一个策略在利用V被改进而产生一个新的更好的策略'后，计算V'，然后再次改进生成更好的策略''。每一个策略必须保证在前一个策略上严格的改进。因为一个有穷的马尔可夫决策过程(MDP)仅有有限数量的策略，这个过程在有限次的迭代后最终收敛于最优策略和最优值函数。寻找最优策略的方法称为策略迭代。对于每一次策略评估和其自身的迭代计算都开始于前一次策略的值函数，这使得策略评估的收敛速度有很大的提高。策略迭代经常在很少量的几步迭代后就收敛至最优策略。
3.3.2 值迭代
策略迭代的一大缺点就是它的每一次迭代都需要进行策略评估，而对于整个
状态集，该策略评估要对状态集多次扫描，不断地进行自身迭代计算。事实上，通过值迭代可以中断策略评估的执行，而且不影响最终策略迭代的收敛效果。值迭代将策略改进和终止策略评估的步骤结合了起来，在第一轮扫描 (每个状态的一次更新) 过后，策略评估就停止了，公式如下：
Vk1(s)maxE{rt1Vk(st1)|sts,ata}
aaamaxPss'[Rss'Vk(s')]as
(3.3)
在每一遍的值迭代过程中，都有效地将一遍策略评估和一遍策略改进相结合，通过在两遍策略改进之间插入多遍策略评估，从而加快了收敛至最优策略的速度。其终止方法是通过计算值函数在一次扫描后的变化量，如果非常小则停止程序的运行。图4.1就给出了关于这种带结束条件的完整的算法。
Repeat
0
For each
sS
vV(s)
aa'V(s)maxas'Pss'[R'V(s)]
ssmax(,|vV(s)|)
图4.1值迭代
Until
(一个极小的数)
输出一个确定的策略，例如：
aa'(s)argmaxas'Pss'[R'V(s)]
ss3.4 动态规划的效率
DP对于解决大型的问题来说可能并不太实际，但是与其它一些解决MDP算法相比较，它还是相当有效的。如果不考虑一些技术上的细节，那么利用动态规划算法去寻找最优策略所花费的(最长)时间是一个关于状态数和动作数的多项式。假设n和m表示状态和动作的数量，这就意味着动态规划算法将进行一系列操作步骤必将小于多项式所计算的结果。即使(确定的)策略的总数量是mn，动态规划算法也可以确保在由多项式所得出的时间范围内得到最优策略。从这个意义上来说，动态规划算法在寻找最优策略的速度上要远快于其他直接寻找的算法，因为那些直接寻找的算法需要尽力检验每一个策略以比较确定是否为最优策
略。线性规划算法也可以用来解决马尔可夫决策过程的问题，甚至在一些情况下，它的最差收敛保证要优于动态规划算法的。但是在状态的数量很小的时候，与动态规划算法比较时，线性规划算法就显的很不实际，比如当状态的数量只有100的时候。而对于那些大型的问题，只有动态规划算法才是可行的。
实际上，利用现今的计算机，动态规划可以用来解决状态数量达到百万级的马尔可夫决策过程的问题。策略迭代和值迭代现如今都被广泛使用，也不能说两者之间到底是哪一个比较好。实际上，这些算法的收敛速度都是要快于它们理论上的最差运行时间，尤其是当它们一开始就有的比较好的初始值函数或者策略。
3.5 本章小结
本章先介绍了动态规划的适用条件，然后说明动态规划的算法流程并且介绍了策略评估和策略改进。其次本章还介绍了两种寻找最优策略的迭代方法以及动态规划的效率。
第四章 实验平台分析与实现
基于强化学习理论，采用动态规划算法，以Gambler问题为实验平台，对上述理论进行仿真实现。本章重在讨论仿真平台的实现过程，详细介绍底层框架及核心算法。
4.1 实验平台描述
4.1.1 系统概述
Gambler问题是强化学习过程中比较经典的问题，本次实验重在借助Gambler问题，结合强化学习的理论和算法，在Visual Studio 2008环境下实现机器学习，最终能够给出Gambler问题中的最优策略。在该实验平台上，用户可以设定赌徒赢的概率，程序运行过程中，我们可以看到机器学习过程中所产生的V值以及最优策略的变化情况。
4.1.2 系统运行环境
(1) 硬件系统
处理器：Intel Pentium 166 MX 或者更高
内存：128M以上
硬盘空间：2G以上
显卡：SVGA显卡适配器
(2) 软件系统
操作系统：Windows 98/ME/2000/XP
实验环境：Visual Studio 2008
4.2 Gambler问题仿真
一个赌徒利用硬币投掷的正反面结果来赌博。假如投掷结果是硬币的正面朝上，那么他将赢得他所压在这一局的相同钱，如果是反面朝上，那么他将输掉他的赌金。当这个赌徒赢满100美元或者他输掉他所有的钱时，赌博结束。每一轮投掷，赌徒必须取出他资金的一部分作为赌金，赌金必须是整数。
在该实验平台上，能够有用户定义硬币正面朝上的概率P，并且能够暂停迭代来查看当前的V值及最优策略。程序运行结束后，能够在系统界面上看到最终的V值及最优策略的曲线图。
Gambler问题可以被描述为情节式无折扣的（可以理解为1）有限MDP模型。状态就是赌徒所拥有的资金，s{1,2,,99}，动作就是下赌注，a{1,2,,min(s,100s)}。每一轮只有当赌徒最后赢满100美元时，反馈值为+1，否则，反馈值为0。状态值函数给出每轮能够赢得赌博的概率。策略就是如何决定每轮取出多少钱去赌博。最优策略就是使取得最后胜利的概率最大化。
4.3 实验平台概要设计
本实验平台是由两部分构成，一部分是底层框架，该框架的设计初衷是能够适用任何强化学习问题，因此它是由许多抽象类和接口构成，另一部分是具体强化学习问题的模型，它是通过对具体问题建模并且继承底层框架的抽象类而获得的。
4.3.1 底层框架模型
在底层框架中，最重要的是IAgent, IEnvironment, IStrategy这三个抽象类及其子类。IAgnet是环境(Environment) 和策略(Strategy)模块交互的桥梁。
IEnvironment 主要包括Action和State，用来获得环境中的动作以及状态。IStrategy是采用的算法，包含进行学习的函数。在本实验平台中，由于环境模型是确定的，并未使用到IAgent，因此以下将具体说明环境，算法及值存储的相关部分。
(1) 环境的结构
IState IEnvronment IAction
IGraphics
CAbstractState
IEnvironmentModel CAbstractEnvironment
CAbstractEnvironmentModel
图4.1 环境的结构
如图4.1所示，最终的CAbstractEnvironmentModel类即是在具体问题中环境类所要继承的父类。该类同时继承IEnvironmentModel和CAbstractEnvironment主要包括一下方法：判断是否到达最终状态；获取当前状态的所有动作值；给定一对状态和动作后获得后继状态，获得立即奖赏值；初始化状态；获得所有状态；以文本形式返回所有的属性。
IGraphics是一个画图的接口，使用该接口可以将环境中的信息及时返回到系统的图形界面中。在Gambler问题的具体实现中，并没有通过这个类来画图。
IEnvironmentModel是基于模型的环境类，继承IEnvironment。在这个类中有两个抽象的方法：一个是获得转移概率的函数，另一个是获得所有后继状态的函数。
(2) 算法的结构
IStrategy
IStateValueLearner IModelBasedStrategy IModelFreeStrategy IActionValueLearner
CVISelector CMCOnPolicySelector
图4.2 算法的结构
IStrategy是算法的接口，最主要的功能是在给定一个状态后，获取它的最优动作或者最优动作列表。IModelFreeStrategy继承IStrategy，主要用于无模型的算法，如TD算法，MC算法，Q算法，包含以下方法：从所有动作中选择一个动作，从它的经验中进行学习。IModelBasedStrategy也继承于IStrategy，主要用于已知模型的算法，如DP算法，包含以下方法：进行策略评估，进行机器学习。IStateValueLearner和IActionValueLearner都是返回状态的V值的类。因此，由图4.2可以得知，如果实际问题是用基于模型的算法解决的，则调用CVISelector类，如果是用无模型的算法解决，则调用CMCOnPolicySelector类。
(3) 存储的结构
在机器学习的过程中，需要不断地使用到当前状态的值 (V值或Q值)，在底层框架中使用IVStore和IQStore来存取，并且如果在读取时发现还没值存入，则会调用IDefaultValueChooser来返回一个默认值。值可以是一个常数或是一个区间。CConstantValueChooser和CIntervalValueChooser都继承于IDefaultValueChooser结构如图4.3所示。
IVStore IQStore IDefaultValueChooser
CVMemorizer CQMemorizer
CConstantValueChooser
CIntervalValueChooser
CNullValueChooser
图4.3存储的结构
4.3.2 Gambler问题模型
Gambler问题是通过基于模型的DP算法来解决的，根据上述的底层框架可以得知，在Gambler这个具体问题中，根据实际的建模分析，需要创建状态，动作和环境的三个类，这三个类分别继承于CAbstractState，IAction和CAbstractEnvironmentModel。
(1) 状态类——Stake
赌徒当前手中的赌金即是一个状态。在该类中能够对状态进行复制，判断两个状态是否相等，获取当前赌金的金额。
(2) 动作类——Bet
赌徒的动作用他的下注金额来表示。在该类中能够对动作进行复制，判断两个动作是否一样，获取下注的金额。
(3) 环境类——Gambler
由于Gambler问题是基于模型的，所以环境类知道当前状态下的所有情况。在环境类中定义了硬币正面朝上的概率P及最终状态。在该类中能够判断是否到达最终状态，获得立即奖赏，在给定状态和动作的情况下获得所有的后续状态，在给定状态的情况下获得所有的动作，获得所有的状态，获得转移概率，设定P值，获取P值。
4.3.3 界面设计
界面设计应遵循简洁美观，方便易用的基本原则。
程序界面主要由两部分组成：左边的图形显示区和右边的具体信息显示区。右边的区域能够自由的展开或者隐藏。点击暂停按钮可以暂停迭代过程。整个页面布局使用CLR来实现，具体效果图如4.4，4.5所示：
图4.4 系统界面(1)
图4.4 系统界面(2)
4.4 实验平台的详细设计
基于上述的底层框架和具体问题模型，本系统在Visual Studio 2008开发环境上采用CLR实现了具体的功能。在具体实现的过程中，程序中加入了一些额外的代码，这些代码能够将问题中的各个属性(例如V值，状态值，动作值)输出到XML文件保存。下面将以代码的形式分析一些重要的类和接口。
4.4.1 类和接口
(1) IAction
class IAction
{
public:
/* Comparison object to be used for the strict weak ordering. */
struct Comparator
{
bool operator() (const IAction *lhs, const IAction *rhs) const
};
{
return *lhs < *rhs;
}
};
public:
typedef std::pair
public:
IAction()
{
act_props = new TxtProperties;
}
~IAction()
{
if (act_props)
delete act_props;
}
virtual IAction* Copy() const = 0;
virtual bool Equals(const IAction &a) const = 0;
virtual bool operator == (const IAction &a) const = 0;
virtual bool operator < (const IAction &a) const = 0;
/** return all the properties in text form */
virtual TxtProperties* GetTxtProperties() const = 0;
/** return the action in the form of string, for debugging */
virtual std::string ToString() const = 0;
protected:
TxtProperties *act_props;
在Gambler问题中，Bet类继承IAction，并且添加了一个GetAction()的方法。
(2) IState
class IState
{
public:
/** The list of all legal moves starting from the currrent state. */
virtual IAction::ActionList* GetActionList() const = 0;
virtual void SetEnvironment(const IEnvironment *e) = 0;
/** Change a state according to the action. */
virtual IState* Modify(const IAction *a) const = 0;
/** Read the universe the state is in. */
virtual const IEnvironment* GetEnvironment() const = 0;
/** Reward of (old,this,a) */
virtual double GetReward(const IState *old, const IAction *a) const = 0;
/** Is this state final ? */
virtual bool IsFinal() const = 0;
virtual IState* Copy() const = 0;
};
virtual bool Equals(const IState &s) const = 0;
virtual bool operator == (const IState &s) const = 0;
virtual bool operator < (const IState &s) const = 0;
virtual TxtProperties* GetTxtProperties() const = 0;
virtual std::string ToString() const = 0;
virtual int GetValue() const = 0;
/* Comparison object to be used for the strict weak ordering. */
struct Comparator
{
bool operator() (const IState *lhs, const IState *rhs) const
{
return *lhs < *rhs;
}
};
CAbstractState继承IState，定义了一些公共行为。Stake类继承CAbstractState，在此基础上添加了GetValue()方法来获得当前状态下的赌金数额。
(3) IEnvironment
class IEnvironment
{
public:
typedef IAction::ActionList ActionList;
typedef std::set
public:
virtual bool IsFinal(const IState *s) const = 0;
virtual ActionList* GetActionList(const IState *s) const = 0;
/** Computes the next state, given a start state and an action. */
virtual IState* SuccessorState(const IState *s, const IAction *a) const = 0;
/** Reward of (s1, s2, a) */
virtual double GetReward(const IState *s1, const IState *s2, const IAction *a) const = 0;
/** Default Initial State */
};
virtual IState* DefaultInitialState() = 0;
/* get all states */
virtual StateList* GetAllStates() const = 0;
/** return all the properties in text form */
virtual TxtProperties* GetTxtProperties() const = 0;
/** description */
virtual std::string GetDescription() const = 0;
IEnvironmentModel继承自IEnvironment，在此基础上添加了获取转移概率的方法和获取所有后继状态的方法。如图4.1所示，CAbstracatEnvironmentModel同时继承IEnvironmentModel和CAbstractEnvironment。在Gambler问题中，环境类Gambler继承CAbstracatEnvironmentModel，并对这些虚函数进行重载。
(4) IVStore
class IVStore
{
public:
/** @return The state value */
virtual double Get(IState *s) = 0;
/** Store a state/action value. We sometimes need the new state (sp)... */
virtual void Put(IState *s, double qsa, IState *sp = NULL ) = 0;
};
(5) IModelBasedStrategy
class IModelBasedStrategy: public IStrategy
{
public:
// policy evaluation
virtual double Evaluation(const IEnvironment::ActionList* actionList) = 0;
// deal with the learning process
virtual void Learn() = 0;
// set the object deals with the graphic user interface
virtual void SetGraphics(const IGraphics *g) = 0;
};
4.4.2 核心算法示例
(1)Evaluation方法
在Gambler问题中，最核心的部分在于CVISelector类的具体实现。在CVISelector类中，调用Evaluation方法进行策略评估，调用Learn方法进行完整的学习。由于采用的是基于值迭代的动态规划算法，所以在Learn方法中调用了Evaluation方法，具体原理参见3.3.2 值迭代。Evaluation方法代码如下所示：
double Evaluation(const IEnvironment::ActionList* actionList)
{
if (NULL == actionList)
return 0.0;
if (actionList->() == actionList->())
return 0.0;
const IState *s = actionList->first;
int tmp=s->GetValue();
set
double maxv = -DBL_MAX; //Minimal double value
while (act_it != actionList->())
{
double temp = 0.0;
IEnvironmentModel::SuccessorStateList *states =
myEnvironment->GetAllSuccessorStates(s, *act_it);
IEnvironmentModel::SuccessorStateList::const_iterator tran_it = states->begin();
while (tran_it != states->end())
{
temp += tran_it->second * (myEnvironment->GetReward(s, tran_it->first, *act_it)
+ gamma * memory->Get(tran_it->first));
++tran_it;
}
if (temp > maxv)
maxv = temp;
++act_it;
}
memory->Put(const_cast
if (NULL != gui)
gui->SendState(s);
return maxv;
}
(2)Evaluation方法在界面程序中的应用
在具体实现的过程中，由于每迭代一次都需要更新界面中的最优策略图及V
值图，并且在迭代过程中用户也可能需要随时暂停，因此并没有直接使用Learn方法来进行机器学习，而是在界面的backgroundWorker1_DoWork()事件中，按照Learn方法的思想，调用Ealuation方法，并在每次迭代中更新界面中的图。核心代码如下所示：
while(times<=Iter_time)
{
if(RUN) //判断是否需要暂停迭代
{
IEnvironmentModel::StateList *states = gambler->GetAllStates();
IEnvironmentModel::StateList::const_iterator set_it = states->begin();
double oldValue, newValue;
double delta = 0.0;
while (set_it != states->end())
{
oldValue = sel->GetValue(*set_it);
newValue = sel->Evaluation(gambler->GetActionList(*set_it));
delta = max(abs(oldValue - newValue), delta);
++set_it;
}
if (delta < sel->GetTheta())
{
progressBar1->Visible=false;
break;
}
/**画图部分的代码**/
times++;
}
}
(3)GetAllBestActions方法
还有一个关键点就是最优策略的获取。在实际问题中，一个状态s的最优动作a是通过计算这个状态下所有可以选择动作的Q(s,a)，值最大所对应的动作a即是最优策略，因此不排除在同一状态下几个最优策略，因此应该采用ActionList来存储所有的最优动作值。具体代码如下：
IEnvironment::ActionList *GetAllBestActions(const IState *s) const
{
IEnvironment::ActionList *actionList = s->GetActionList();//获得当前状态下的所有Action
std::set
if (size == 0)
return NULL;
bestActionList->first = s;
bestActionList->();
double maxv = -DBL_MAX; //Minimal double value
std::set
double v_value;
double action_value;
while (it != actionList->())
{
IAction *a = *it;
IEnvironmentModel::SuccessorStateList* succ_states =
myEnvironment->GetAllSuccessorStates(s, a);
IEnvironmentModel::SuccessorStateList::const_iterator state_it = succ_states->begin();
action_value = 0.0;
while (state_it != succ_states->end())
{
v_value = memory->Get(state_it->first);
action_value += state_it->second * (state_it->first->GetReward(s, a) + gamma *
v_value);
++state_it;
}
if (action_value > maxv)
{
bestActionList->();
bestActionList->(a);
maxv = action_value;
}
else if (action_value == maxv)
{
bestActionList->(a);
}
++it;
}
return bestActionList;
}
4.5 本章小结
本章首先对实验平台进行的介绍，说明了所要展示的系统以及该系统运行的环境。其次，对Gambler问题进行的具体的描述。然后详细分析了实验平台的概要设计和实现细节，在分析过程中介绍了各类之间的关系，并且以代码的形式说明了核心算法。实验平台实现了强化学习中的DP算法在Gambler问题中的具体运用，下一章将对实验结果进行分析。
第五章 实验结果分析
5.1 实验结果
在本实验平台中，所有最优动作即V值最大的所有点，都在最优策略图上显示了出来，因此在同一状态下可能有两个或三个最优动作，这与书上的最优策略图略有区别。在P=0.4
1.0的默认条件下，最优策略图及V值图如下图5.1，图5.2所示。
图5.1最优策略图
图5.2 V值图
当程序运行结束后，程序中所涉及到的各种数据，状态和动作的属性，以及
对环境的描述都会存储到项目所在文件夹的文件中，用于以后的数据分析。
5.2 Gambler仿真结果分析
针对Gambler这个具体问题，以下将对它的实验结果进行分析。
5.2.1 Gambler 在不同P值下的策略
(1) 当P<0.5时，取P为0.4，最优策略图如图5.1所示
(2) 当P=0.5时，最优策略图如图5.3所示
图5.3 P=0.5时的最优策略图
(3) 当P>0.5时，取P为0.6，最优策略图如图5.4所示
图5.4 P=0.6时的最优策略图
5.2.2 策略分析与评价
由以上三张图可以看出，当P值不同时策略图有很大的变化。策略图的得出是每个状态的最优动作，最优动作的计算在4.4.2核心算法示例中有具体的代码说明，程序通过P值和每个状态的V值求得最优动作，策略图是根据计算结果求解出来的。从图上可以看出，当P=0.5时，几乎所有的可用动作都可以用作最优策略，这是因为此时赌徒的输赢类似于随机概率。但是当P>0.5时，所有的最优动作变为1，这与P<0.5时出现有规律的变化完全不同。一般人都会认为在赢的概率大的情况下应该多压一些赌金，能够迅速取胜，但是经过机器学习后，却得出以每次只压1美元这种最慢的速度来进行操作，下面将从概率论的角度解释其原因。
以赌徒手中有2美元为例。当P=0.4时，根据最优策略图5.1，此时的最优策略为2，下一状态变为4的概率是0.4。如果采用图5.4的做法，每次只压1美元，如图5.5所示，
是从2美元变成4美元的具体过程，最终获得4美元的概率是：0.1620.160.160.480.160.48。同理，0.4当P=0.6时，根据图5.410.48应采用每次只压1美元的策略，则变成4美元的概率是：0.360.360.360.4820.360.480.6
10.48
2
0，4 0，6
3
0，4
0，6
0，4
1
0，6
4
0，4
2
0，6
0
3
0，4
0，6
0，4
1
0，6
4
2
0
图5.5 从2美元变成4美元的过程
从现实角度分析，当P>0.5时，只有增加参与的次数，才能使实际赢的概率更大。
5.2.3 计算误差对策略的影响
在本实验平台中，最终算出的数据并不是与理论值完全一致的，理论上，当P=0.4时，最优策略图应如图5.6所示，可以很明显的表示出最优策略的趋势。通过比较图5.6和图5.1，发现在图5.1中存在一些突变的点，比如当16，17，18这三个状态点，根据理论，采取的最优策略应该是9，8，7，但是在图5.1中却是16，17，18。通过跟踪程序中的数据，发现本实验平台计算出来的V值在小数点后14位至16位与理论值存在误差，就是由于这样细微的差别导致了最终数据存在一些突变的值。这也是本次毕业设计存在欠缺的方面，但是总体来说，整个实验平台的设计思路和实现方式都是正确的。
图5.6 当P=0.4时理论上的最优策略图
5.3 本章小结
本章对Gambler问题的实验结果进行了分析，比较了不同P值下的最优策略，并且解释了当P>0.5时出现所有最优策略都是1的原因。最后提出了V值计算误差对策略的影响。
第六章 总结与展望
6.1 课题总结
本论文论述的是强化学习理论的仿真实现，课题基于强化学习开展的动态规
划算法和Gambler具体问题的研究。论文中着重研究和讨论了基于值迭代的动态规划算法以及在Gambler问题上的应用。
本设计能够很好地展现强化学习的思想，系统结构较合理，具有如下的特点：
(1) 普遍、通用、操作简单
界面简洁、清晰，操作简单，用户可以自行设计参数(P值)来执行强化学习算法，窗口可以进行伸缩。在程序运行的同时，每一次迭代对策略的改进以直观的图形展示给用户。为了更好地进行分析，在界面上还可以看到每次迭代所产生的V值。
(2) 系统结构开放，便于扩充
本实验平台的底层框架是抽象的，可以运用到其他问题的求解中，本毕业设计小组的同学也都是使用同一的底层框架，目的在于便于以后强化学习问题的扩充，提供更好的公共接口。
(3) 使用XML文档存储数据
当程序运行结束后，程序中所有的数据，例如V值，以及环境中涉及到的各种状态，属性都会存储到XML文档中，用于以后的数据分析。
6.2 进一步的研究与展望
对于整个强化学习课题还可以进行后续研究，做进一步开发，主要有：
(1) “维数灾”问题
尽管在Gambler问题中没有“维数灾”问题，但是典型的强化学习算法采用状态-活动对(state-action)来表示行为策略，因而不可避免地出现学习参数个数随着状态变量维数呈指数级增长的现象，即“维数灾”(Curse Of Dimensionality)，这一问题严重制约着强化学习在实际中的应用。当前，“维数灾”是制约机器学习发展和应用的重要课题，如何更好解决这一问题就显得至关重要[14]。当前解决这一问题的方法主要有值函数近似法、状态抽象法、搜索空间限定法、分层强化学习法等，然而这些方法一般只能应用于特定领域，那么创新出一种适用范围更加广泛的方法也应该是今后应该考虑的问题。
(2) 分层强化学习
采用分层结构对搜索空间分层时可以大大降低搜索代价，但系统易收敛于局部最优，如何改善它使之收敛于最优策略是一个值得探讨的问题。
(3) 多Agent强化学习
多Agent强化学习是强化学习研究中非常重要的研究方向之一。在多Agent系统中，环境在多个Agent的联合动作下进行状态的迁移。对于单个Agent来讲，由于其只能确定自身Agent的行为动作，因此体现出一种行为动作上的“部分感知”，从而产生出另一种形式的非标准马尔可夫环境。多Agent强化学习机制被广泛应用到各个领域，例如游戏、邮件路由选择、电梯群控系统以及机器人设计等等[15]。目前多Agent系统强化学习离完全成熟尚有一段距离，还需要通过理论分析和实验验证手段对其机制加以研究。
(4) 部分可观马尔可夫模型(POMDP)问题
在实际的问题中，Agent往往无法完全感知环境状态信息。当Agent无法直接观测或通过其他手段了解环境信息时，将导致错误的状态转移，影响到状态转移概率。Agent与环境的交互将会导致隐状态或感知失真等问题的出现。单Agent的不完全感知问题在求解POMDP模型时，随着迭代次数的增加，其值函数有很高的计算复杂度，对于多Agent系统中采用POMDP模型，协调难度和计算复杂性增大，开发有效的求解POMDP算法是进一步研究解决该问题的一种思路。
参考文献
[1] 张汝波. 强化学习研究及其在AUV导航系统中的应用[D]. 哈尔滨: 哈尔滨工程大学, 1999.
[2] 阎平凡. 再励学习一原理, 算法及其在智能控制中的应用[J]. 信息与控制,
1996, 3(1): 28-34.
[3] L P Kaelbling, M L Littman, A W Moore. Reinforcement learning: a survey[J].
Journal of Artificial Intelligence Research, 1996, 4(2): 237~285.
[4] R S Sutton, A G Barto, R Williams. Reinforcement Learning is Direct Adaptive
Optimal Control [J]. IEEE Control Systems Magazine, 1991, 12(2): 19-22.
[5] R H Crites, A GBarto. Improving elevator performance using reinforcement
learning[C]. In：
Advance in Neural Information Processing System. Cambridge, MA,The MIT
Press. 1996, 1017-1023.
[6] J Tesauro. Tempo difference learning and TD-gammon[J], Communications of the
ACM,
1995, 38(3): 58-68.
[7] M J Mataric. Learning from History for Adaptive Mobile Robot Control[C]. In：Proceedings
Of the IEEE/ RSJ International Conference on Intelligent Robots and Systems.
1998, 1865-1870.
[8] Tom M Mitchell. 机器学习[M]. 北京: 机械工业出版社, 2004.
[9] S Sutton Richard and G Barto Andrew. Reinforcement Learning[M]. MIT Press,
Cambridge, MA, 1998.
[10] Qijun Chen, Xiaoyun Wei. Action Values Based Reinforcement Learning and
Optimized Reward Functions[J]. Tongji Daxue Xuebao/Journal of Tongji
University, 2007, 35 (4):531-536.
[11] C L Chen, D Y Dong, Z H Chen. Quantum Computation for Action Selection
Using Reinforcement Learning[J]. International Journal of Quantum Information,
2006, 4(6): 1071-1083.
[12] W S Lovejoy. A Survey of Algorithmic Methods for Partially Observed Markov
Decision Processes[J]. Annals of Operations Research, 1991, 28(4):47-65.
[13] 马莉, 蔡自兴. 再励学习控制器结构与算法[J]. 模式识别与人工智能, 1998，11(1) :96-100.
[14] A Barto, S Mahadevan. Recent Advances in Hierarchical Reinforcement
Learning[J]. Discrete Event Dynamic Systems: Theory and Applications, 2003, 13:
41-77
[15] S Kamio, H Iba. Adaptation Technique for Integrating Genetic Programming and
Reinforcement Learning for Real Robots[J]. IEEE Transactions on Evolutionary
Computation, 2005, 9(3):318-333.
致 谢
经过几个月的努力，本次毕业设计已经接近尾声，从论文选题到搜集资料，从接触强化学习理论到实验平台的完成，从论文的开始撰写到结束，整个过程我经历了迷茫、痛苦、 喜悦和彷徨，对帮助过我、鼓励过我、指导过我的人表示发自肺腑的诚挚谢意。
首先，我要感谢我的指导老师刘全教授和全程指导我们毕业设计的王辉老师。两位老师渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，朴实无华、平易近人的人格魅力对我影响深远，使我树立了远大的学术目标、掌握了基本的研究方法。
其次，感谢杨旭东学长，傅启明学长和李瑾学姐，当我遇到问题时总是问他们，而他们总是很耐心地向我讲解。从强化学习的基础理论、系统算法的创新、关键代码的实现到论文的撰写，学长学姐给了我莫大的指导和帮助，在我一次次的灰心失望时，帮我理清思路，鼓励我整旗鼓继续努力。在研究算法和撰写论文的过程中，他们给我提供了丰富的参考资料。这里我衷心的说一声谢谢！
第三，感谢计算机学院所有曾经为我们07软件工程(嵌入式)专业任课的老师，老师们教会我的不仅仅是专业知识，更多的是对待学习、对待生活的态度。
第四，感谢我的家人，在我遇到困难的时候给了我无尽的鼓励和支持，你们是我最坚强的后盾。
第五，感谢我的同学们，我永远不会忘记大学四年的快乐时光。
最后对老师，同学和家人再次致以我最衷心的感谢！
毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作 者 签 名： 日 期：
指导教师签名： 日 期：
使用授权说明
本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名： 日 期：
学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。
作者签名： 日期： 年 月 日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名： 日期： 年 月 日
导师签名： 日期： 年 月 日
指导教师评阅书
指导教师评价：
一、撰写（设计）过程
1、学生在论文（设计）过程中的治学态度、工作精神
□ 优 □ 良 □ 中 □ 及格 □ 不及格
2、学生掌握专业知识、技能的扎实程度
□ 优 □ 良 □ 中 □ 及格 □ 不及格
3、学生综合运用所学知识和专业技能分析和解决问题的能力
□ 优 □ 良 □ 中 □ 及格 □ 不及格
4、研究方法的科学性；技术线路的可行性；设计方案的合理性
□ 优 □ 良 □ 中 □ 及格 □ 不及格
5、完成毕业论文（设计）期间的出勤情况
□ 优 □ 良 □ 中 □ 及格 □ 不及格
二、论文（设计）质量
1、论文（设计）的整体结构是否符合撰写规范？
□ 优 □ 良 □ 中 □ 及格 □ 不及格
2、是否完成指定的论文（设计）任务（包括装订及附件）？
□ 优 □ 良 □ 中 □ 及格 □ 不及格
三、论文（设计）水平
1、论文（设计）的理论意义或对解决实际问题的指导意义
□ 优 □ 良 □ 中 □ 及格 □ 不及格
2、论文的观念是否有新意？设计是否有创意？
□ 优 □ 良 □ 中 □ 及格 □ 不及格
3、论文（设计说明书）所体现的整体水平
□ 优 □ 良 □ 中 □ 及格 □ 不及格
建议成绩：□ 优 □ 良 □ 中 □ 及格 □ 不及格
（在所选等级前的□内画“√”）
指导教师： （签名） 单位： （盖章）
年 月 日
发布评论