智能控制第6章学习控制-增强学习.ppt

第 6章 学习控制 增强学习 智能控制基础 2/51 6.2.1 增强学习的基本思想 6.2.2 增强学习的主要算法 6.2.3 增强学习在控制中的应用 6.2 增强学习 3/51 6.2.1增强学习的基本思想 强化学习是介于监督学习和无监督学习之间 的一种学习方法，它不需要训练样本，但需 要对行为结果进行评价，通过这些评价来间 接指导行为的改进，直至满足目标。 4/51 心理学基础 19世纪末，俄国生理学家巴甫洛夫（ Pavlov）建立 经典条件反射（ classical conditioning）理论。 美国心理学家桑代克（ Thorndike）也通过动物实 验发现了效果律（ law of effect），即动物可以根据 试错尝试（ trial-and-error）中得到的赏罚信息，学 得情景下的有效行为。 这种行为的效果被随后的斯肯纳（ Skinner）称为强 化作用（ reinforcement），而相应的学习则被称为 操作条件学习（ operant conditioning）。 5/51 发展历史 二十世纪五十年代， Minsky 首次提出。 六十年代， Waltz和付京孙 将这种思想应用 在智能控制中。 八十年代以后，大量标志性的成果涌现。 6/51 系统结构图 感知 行动 agent 环 境 强化信号 r 状态 s 动作 a 7/51 增强学习的建模 有限 Markov决策过程 MDP （ Markov Decision Processes) 。 系统状态集合为 S； 允许行为集合为 As， As与状态 s有关； 行动为 at下的状态转移概率 P(st+1|st, at) 得到即时回报（ immediate reward） rt+1的期望为 ),|),( 111 ttttttt sasrEsasr 8/51 确定系统 其中， 为状态转移函数 ),(1 ttt ass ),(),( 11 tttttt sasrasrr 9/51 即时回报 举例 惩罚 中性 奖赏 1 0 1 tr 10/51 增强学习的问题 目标函数构造 如何获得最优决策和最优目标函数值 11/51 目标函数 用累计回报 (return) 期望来作为学习的价值函 数 。 无限折扣模型（ infinite-horizon discounted model） 有限模型（ finite-horizon model） 平均回报模型（ average-reward model） ,|)( 0 13 2 21 t k kt k ttttt srEsrrrEsV ,)( 0 1 t h k ktt srEsV ,1)( 0 1 t h k ktt srEhsV 为策略 12 目标函数求解 目标函数 求解 迭代策略 计算法 Monte Carlo法 瞬时差分 法 13 迭代策略计算 IPE （ Iterative Policy Evaluation） 目标函数可写作递推形式 V(s)是递推公式的不动点，可用迭代逼近 st tAa s tntttttttttn sVsasrassPassV 1 )(),(),|(),()( 1111 st tAa s ttttttttt sVsasrassPas 1 )(),(),|(),( 111 ,|)( 3221 ttttt srrrEsV 14/51 存在的问题 需要了解整个系统的模型（状态转移、即时 回报等）。 15/51 Monte Carlo法 目标函数为期望，在统计上可以用累计回报 采样的平均值来逼近。 0 11 )()1()( k kt k tntn rsVsV )()( 1 0 11 tn k kt k tn sVrsV 16/51 存在的问题 要完成整个尝试才能进行目标函数估计的更 新。 离线学习。 17/51 瞬时差分法（ Temporal Difference） Sutton在 1988年提出。 根据 可得： ,|)()( 11 tttt ssVrEsV )()()( )()()1()( 11111 1111 tntnttn tnttntn sVsVrsV sVrsVsV 18/51 特点 结合了迭代策略计算法和 Monte Carlo法。 不需要完整的模型 可进行在线学习 19/51 最优策略的求解 最优策略 的求解 动态规划 法 推广策略 迭代 20/51 动态规划法 将递推公式两边取最优 得到 st tAa s tttttttttt sVsasrassPassV 1 )(),(),|(),()( 111 1 )(*),(),|(m a x)(* 111 t st s tttttttAat sVsasrassPsV 21/51 推广策略迭代 GPI 推广策略迭代 GPI（ Generalized Policy Iteration） 特点 1 )(),(),|(m a x)( 1111 t st s tnttttttAatn sVsasrassPsV V*， * V0， 0 V的计算 的选取 22/51 6.2.1 增强学习的基本思想 6.2.2 增强学习的主要算法 6.2.3 增强学习在控制中的应用 6.2 增强学习 23/51 6.2.2 增强学习的主要算法 增强学习的主 要算法 Q-学习算法 （ Watkins 提 出） Sarsa算法 24/51 1. Q-学习算法 定义一个与行为有关的价值函数 Q函数： 可知 策略选取 ,|),( 3221 ttttttt asrrrEasQ ),(*m a x)(* ttAat asQsV st ),(*m a xa r g)(* tt at asQs t 25/51 具体算法 因为 借鉴瞬时差分的思想 1 1 ),(*m a x),|(,|),(* 1111 t ts ttatttttttt asQassPasrEasQ ),(),(m a x),(),( ),( 111111 1 ttnttnatttnnttn ttn asQasQsasrasQ asQ t 26/51 确定 MDP下的收敛性 定理 6-7：在确定 MDP下采取 Q学习算法，如 果对任意允许的 (s, a)，有 | r(s, a)| 和 Q 0(s, a) 有界， 01， n=1， 则当 n，且每一个 (s, a)会被无限访问时，以概率 1趋向于最优 值 Q*(s, a)。 27/51 证明 |),(*m a x),(),(m a x),(| |),(*),(| 1 asQasrasQasr asQasQ ana n ),(*m a x),(m a x 1 asQasQ ana |),(*),(|m a x 1 asQasQ na 11, |),(*),(|m a x nnas QasQasQ 01 QQQ nnn n时 ， Qn0 28/51 不确定 MDP下的收敛性 定理 6-6：在不确定 MDP下采取 Q学习算法， 如果对任意允许的 (s, a)，有 | r(s, a)| 和 Q 0(s, a)有界， 01， 0n1，且满足 则当 n，且每一个 (s, a)会被无限访问时， 以概率 1趋向于最优值 Q*(s, a)。 其中， N (n, s, a)为第 n次迭代时，单元 (s, a) 被访问的累计次数。 1 ),( n asnN 1 2 ),( n asnN 29/51 学习步长选择 上述定理告诉我们学习步长既不可衰减太快 慢、又不可衰减太快，一般可取 n为： ),(1 1 asnNn 30/51 遍历性条件的策略选择 ),(),(m a x),(),( ),( 111111 1 ttnttnatttnnttn ttn asQasQsasrasQ asQ t ),(m a xa r g)( tt at asQs t 隐含了贪婪原则的选择策略， 无法同时保证遍历性，需要寻找其它选择策略 在下面的迭代过程中 31/51 -贪婪方法 其中 |A(st)|为决策集合的大小， 为探索概率， 一般随时间的增长而递减。 e l s e asQa sA QsaP ttat t tt t ),(m a xa r g 1|)(| 1 ),|( 32/51 Boltzman分布法 模仿热力学中的 Boltzman分布，得到了一种 新的策略选取方法，可以使价值函数值大的 行为获得更大的被选概率。 的取值一般也随时间的增长而减小。 a asQ asQ tt t tt e e QsaP /),( /),( ),|( 33/51 2. Sarsa算法 Rummery和 Niranjan于 1994年提出 由于算法中只用到了 st、 at、 r、 st 1和 at 1五 个量，所以 Sutton在其书中将其命名为 Sarsa。 一种策略有关（ on-policy）的学习算法 ),(),(),(),( ),( 111111 ttnttntttnnttn ttn asQasQsasrasQ asQ 34/51 Sarsa学习算法的收敛性 定理 6-8：有限 MDP下，如果 Sarsa学习算法 的策略选择满足 GLIE（ Greedy in the Limit with Infinite Exploration）条件或 RRR （ Restricted Rank-based Randomized）条件， 且 Varr(s, a)有界， 0n1，满足 则当 n，收敛于最优值 Q*(s, a)。 1 ),( n asnN 1 2 ),( n asnN 35/51 策略选择条件 GLIE(Greedy in the Limit with Infinite Exploration)条件 每一个 (s, a)会被无限访问； Q函数的策略选择随着迭代次数的增长，以概率 1收敛 于贪婪方法 RRR条件是另一类常见的策略选择思想，这一条 件要求对某一行为的选择概率应与该行为的价值函 数值呈非减关系，即： ),(),( asQasQ ),|(),|( QsaPQsaP 36/51 存在问题 收敛速度慢（状态空间、决策空间规模） 因为在一步学习中，获得的即时回报只能影响 相邻状态的价值函数值预测。 Markov条件 37/51 3. 多步学习算法 学习公式改为： en(s)资格迹 (eligibility trace) （时间信度） 0SP+1 High： if SP+0.2 y(t) SP+1 Goal： if SP-0.2 y(t) SP+0.2 Low： if SP-1 y(t) SP-0.2 Lower： if y(t)SP-1 42/51 行为设计 滴定系统采用增量式控制 a为行为编号，具体有： 大减、减、小减、等待、小增、增、大增 7种，依次编号。例如等待的行为编号为 4。 )()4(#001.0)( tuatu 43/51 状态转移图 44/51 即时回报设计 除了在 Goal区域，其余区域的回报均是惩罚 L ow e rs L ows G oa ls H i ghs H i gh e rs sasr t t t t t ttt 1 1 1 1 1 1 1 1 100 1 1 ),( 45/51 学习策略 单步 Q-学习控制 行为选择采用 贪婪算法，具体参数如下： 折扣因子 0.98， 学习率 0.3， 探索概率 0.3。 46/51 控制效果 47/51 假设机器人欲前往目的地 G，不同行为的即时回报 r如 下图所示。 0),( 0 ii asQ G 100 100 0 0 0 0 0 0 0 0 0 0 0 2. 移动机器人路径规划 48/51 ),(m a x),( ),(),(m a x),(),( ),( 1111 111111 1 1 ttn a tttn ttnttn a tttnnttn ttn asQsasr asQasQsasrasQ asQ t t G 100 100 0 0 0 0 0 0 0 0 0 0 0 一步迭代 1 ,9.0 n 49/51 ),(m a x9.0),(),( 1111 1 ttnatttnttn asQsasrasQ t G 100 100 0 0 90 90 90 0 0 0 0 0 0 第 2步迭代 50/51 ),(m a x9.0),(),( 1111 1 ttnatttnttn asQsasrasQ t G 100 100 0 81 90 90 90 81 81 81 81 0 0 第 3步迭代 51/51 ),(m a x9.0),(),( 1111 1 ttnatttnttn asQsasrasQ t G 100 100 0 81 90 90 90 81 81 81 81 72.9 72.9 第 4步迭代