基于强化学习的gambler策略研究与评价毕业设计论文(编辑修改稿)

基于强化学习的gambler策略研究与评价毕业设计论文(编辑修改稿)内容摘要：

和瞬时奖惩之间的状态值函数。 即： 21 2 3 10kt t t t t kkR r r r r            () 这里  错误 !未找到引用源。 是一个参数， 错误 !未找到引用源。 ，称为折扣率。 ( ) { }ttV s E R s s  }{0 1ssrE tk ktk    }{ 0 21 ssrrE tk ktkt          39。 10 239。 39。 }39。 {),( s tk ktkassassa ssrERPas     39。 39。 39。 )]39。 ([),( s assassa sVRPas  () 根据 Bellman 最优策略公式，在最优策略 * 下，其值函数的定义如下： },)({m a x)( 1*1)(* aasssVrEsV ttttsAa       39。 *39。 39。 )( )]39。 ([m a x s assasssAa sVRP  () 马尔可夫决策过程 (MDP) 在理想状况下，往往希望一个状态能够简练地抽象总结过去的感觉，然而这种方式又能保留所有相关信息。 正常的来说，这比只要求即时感觉要求得更多，但是比要求全部的过去感知历史要少得多。 一个成功保留所有相关信息的状态信号称为马尔可夫的，或者说具有马尔可夫性质。 比如，一个棋子的位置 —— 当前的在棋盘上所有棋子的结构 —— 将作为一个马尔可夫状态，因为它汇集了所有关于引导它完成位置序列的重要的东西。 虽然关于这个 序列的很多信息丢失了，但是所有有关于这个游戏的最重要的东西被保留下来了。 对于所有在过去事件中的 39。 s ， r ， 和所有的可能值： 1 1 1 0 0, , , , , ... , , ,t t t t ts a r s a r s a 来说，如果状态信号有马尔可夫特性，那么环境在 1t 的响应只取决于在 t 时刻的状态和动作的表示，在此情况下，环境和任务是一体的，都称为具有 马尔可夫性质，环境的动态量可以定义为： 1 1 ,P r { 39。 , | }t t t ts s r r s a () 苏州大学本科生毕业设计（论文） 8 满足马尔可夫性质的强化学习任务被称为是马尔可夫决策过程或者 MDP。 很多强化学习问题基于的一个关键假设就是 Agent 与环境之间的交互可以被看成一个马尔可夫决策过程 (MDP)，因此强化学习的研究主要集中于对 Markov 的问题处理。 Markov 决策过程的模型可以用一个四元组  RTAS , 表示： S 为可能的状态集合， A为可能的动作集合， TAST : 是状态转移函数； RASR : 是奖赏函数 [1]。 在每一个时间步 k ，环境处于状态集合 S 中的某状态 kx ， Agent 选择动作集合 A 中的一个动作 ka ，收到即时奖赏 kr ，并转移至下一状态 ky。 状态转移函数 ),( kkk yaxT 表示在状态 kx 执行动作 ka 转移到状态 ky 的概率可以用 )( kyx aPkk表示。 状态转移函数和奖赏函数都是随机的。 Agent 目标就是寻求一个最优控 制策略，使值函数最大 [12]。 强化学习的基本算法 大多数关于强化学习的方法研究都是建立在 MDP 理论框架之上的，通过 MDP 建模，强化学习问题一般可采用迭代技术更新值函数的估计值来获得最优策略。 当前状态向下一状态转移的概率和奖赏值只取决于当前状态和选择的动作，而与历史状态和历史动作无关。 根据在学习过程中 Agent 是否需要学习 MDP 知识，强化学习可以分为模型无关法(modelfree)和基于模型法 (modelbase)。 动态规划属于基于模型法，而蒙特卡罗算法则属于模型无关法。 动态规划 (Dynamic Programming, DP) 动态规划方法是利用值函数来搜索好的策略方法，适用于解决大规模问题，设环境是一个有限马尔可夫集，对任意策略  ， 如果环境的动态信息完全知道，如：策略  和 39。 assR ，39。 assP 已经知道，为了减少计算量，我们常用值迭代法来近似求出 0V , 1V , 2V „„，其更新公式为： 1 1 1( ) { ( ) | }k t k t tV s E r V s s s      39。 39。 ( , ) [ ( 39。 ) ]aass ss kass a P R V s () 常规的动态规划方法主要有以下三种方法 :第一种是值函数迭代法，其本质是有限时段的动态规划算法在无限时段上的推广，是一种逐次逼近算法，该算法与强化学习有着密切的联系；第二种是策略迭代，这是一种基于 Bellman 最优方程的算法；第三种是改进的策略迭代法，综合了前面两种算法，也称为一般化策略迭代法，是许多强化学习算法的基本思想的来源之一 [13]。 动态规划算法的局限性是明显的，它容易出现“维数灾”和“建模灾”问题。 其计算量会使状态变量的数量呈指数增长；它要求事先知道系统的确切模型信息，如 39。 assR 和 39。 assP 的苏州大学本科生毕业设计（论文） 9 值，而在实际的大规模随机问题中，系统的确切模型信息通常是难以获得且不易计算的。 蒙特卡罗算法 (Monte Carlo method, MC) 蒙特卡罗算法是一种无模型 (modelfree) 的学习方法，不需要系统模型 —— 状态转移函数和奖赏函数，只需要通过与环境的交互获得的实际或模拟样本数据 (状态、动作、奖赏值 ) 序列，从而发现最优策略。 MC 总是基于平均化取样回报来解决强化学习问题，它把要解决的问题分解为情节 (episode)。 当环境状态为终止状态 G 时，将得到的累积回报赋予开始状态 S 的值函数。 由于从起始状态到终止状态的过程中， S 可能不止出现一次，这样对 S 的值函数的更新，可以有两种方法 :FVMC(First Visit MC)和 EVMC(Every Visit MC)。 前者将回报赋予第一次访问的 S,后者将每次访问 S 到终止状态 G 的回报平均化以后赋予 S 的值函数。 两者虽然在理论上有区别，但是都可以最终收敛到最优值函数。 与动态规划方法相比， MC 法直接同环境交互获得经验来优化动作行为，不需建立一个环境的动态信息模型，该算法中一些状态集的值函数的计算不依赖于其它状态集的值函数，所以我们可以在那些能够精确描述环境信息的状态子集中计算所获得的平均奖赏值。 另外，它对马尔可夫性要求不是很严。 强化学习中有待解决的问题 (1) 在任一 阶段， Agent 都要面对如何在探索与利用之间取舍的问题。 利用已知的动作可保证得到一定的奖赏，然而对一定的状态而言，探索新动作可能产生更高的奖赏，但过多的探索又会降低系统的性能。 (2) 传统的强化学习算法是基于环境的，是一个马尔可夫决策假设。 系统的将来状态依赖于当前的环境状态，和以前的环境状态无关，在真实世界的大多数情况中，实际系统非常复杂， Agent 不能够精确感知环境的所有状态，因此算法收敛性的假设在实际环境中得不到满足。 (3) 强化学习算法通过搜索状态空间和优化值函数得到好的策略，当系统变得复杂时，需要大量的参数来刻 画它，这样会引起状态空间到动作空间映像的组合爆炸，给搜索带来了繁重的任务，进而影响行动决策的优化问题。 本章小结 本章先介绍了强化学习的原理和模型，然后介绍了强化学习系统的一些重要组成元素以及马尔可夫决策过程。 此外本章还介绍了当前强化学习中的一些重要算法：动态规划、Monte Carlo 算法，最后提出了一些强化学习中有待解决的问题。 苏州大学本科生毕业设计（论文） 10 第三章 动态规划分析 动态规划 (dynamic programming)是运筹学的一个分支，是求解 决策过程 (decision process)最优化的数学方法。 20 世纪 50 年代初美国数学家 等人在研究 多阶段决策过程 (multistep decision process)的优化问题时，提出了著名的 最优化原理 (principle of optimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法 ——动态规划。 动态规划是建立在严格的数学基础之上的，它需要一个完整、精确的环境模型。 动态规划涉及到一系列算法，这些算法能用于在给定完美的马尔可夫决策过程环境模型情况下计算最优化问题。 动态规划的适用条件 任何思想方法都有 一定的局限性，超出了特定条件，它就失去了作用。 同样，动态规划也并不是万能的。 适用动态规划的问题必须满足最优化原理和无后效性。 最优化原理 最优化原理可以这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。 简而言之，一个最优化策略的子策略总是最优的。 一个问题满足最优化原理又称其具有最优子结构性质。 最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。 无后向性 将各阶段按照一定的次序排列好之后， 对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。 换句话说，每个状态都是过去历史的一个完整总结。 这就是无后向性，又称为无后效性。 子问题的重叠性 动态规划算法的根本目的是解决冗余。 其实质上是一种以空间换时间的技术，它在实现过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其他算法。 设原问题的规模为 n，当子问题树中的子问题总数是 n 的超多项式函数，而不同的子问题数只是 n 的多项式函数时，动态规划显得特别有意义，此时动态规划法具有线性时间复杂性。 所以能够用 动态规划解决的问题还有一个显著特征：子问题的重叠性。 这个性质并不是动苏州大学本科生毕业设计（论文） 11 态规划适用的必要条件，但是如果该性质无法满足，动态规划算法同其他算法比较就不具备优势。 算法流程 一般来说，强化学习和动态规划的关键思想就是用值函数去组织和构造好的策略，一旦我们找到符合 Bellman 最优方程的最优值函数， *V 和 *Q ，就能很容易地得到最优策略。 事实上，动态规划算法是由 Bellman 方程转化而来，也就是修正 Bellman 等式的 规则以提高所期望的值函数的近似值。 在实际应用中往往按以下几个步骤进行： (1) 分析最优解的性质，并刻画其结构特征。 (2) 递归地定义最优值。 (3) 以自底向上或自顶向下的方法计算出最优值。 (4) 根据计算最优值时得到的信息，构造一个最优解。 策略评估 策略评估 (policy evaluation) 是指， 对于任意策略  ， 考虑如何计算状态值函数 V。 对于任意 sS , 39。 39。 39。 ( ) ( , ) [ ( 39。 ) ]aas s s sasV s s a P R V s () 这里 (, )sa 是指在策略  下，状态 s 执行动作 a 的概率。 在实际计算中，可以通过迭代方法来计算 V 值。 考虑一个逼近值函数序列： 0 1 2, , ,...,V V V 映射 S 到  的 V。 当 V 存在且k 时，序列 {}KV 通常收敛于 V ， 这个算法被称为迭代策略评估。 为了产生每一个连续的近似值，从 kV 到 1kV ， 对于 每一个状态 s ，迭代策略评估都采取相同的操作：在被评估策略下，沿着所有可能的一步转换，用 s 的后续状态的旧值与期望的立即奖赏计算得到的新值来替换 s 的旧值。 这个操作称为全更新。 迭代策略评估的每一次迭代，一旦产生了一个新的近似值函数 1kV ，就要更新每一个状态值。 在实现方面，另一个关注点是算法的终止。 一种典型的迭代算 法的终止条件是，在每执行一次扫描过后，去检查 1m a x | ( ) ( ) |s S k kV s V s 的值，并且当这个值足够小的时候停止执行。 策略改进 对策略计算值函数的一个原因就是有助于发现更好的策略。 假如对于任一策略  确定一个值函数 V ,对于某些状态 s 应该如何判断是否应该改变策略来选择动作 a ( ()as )。 最关键的评判标准就是计算 ( , )Q sa 是大于还是小于 ()Vs。 如果大于的话，在状态 s 下苏州大学本科生毕业设计（论文） 12 选择动作 a ， 然后再遵循策略  ，要优于一直遵循策略 。 并且最好在以后每次遇到状态的时 候都采用动作 a ，事实上，这一新的策。