13增强学习_机器学习

2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏1机器学习第13章增强学习2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏2概述•增强学习要解决的问题：一个能够感知环境的自治agent，怎样通过学习选择能达到其目标的最优动作•当agent在其环境中做出每个动作，施教者提供奖励或惩罚信息，agent从这个非直接的回报中学习，以便后续动作产生最大的累积回报•本章介绍一个称为Q学习的算法，它可从有延迟的回报中获取最优控制策略•增强学习与动态规划算法有关，后者常被用于解决最优化问题2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏3简介•考虑一个可学习的机器人，它可以观察环境的状态并能做出一组动作改变这些状态，学习的任务是获得一个控制策略，以选择能达到目的的行为•本章关心的是：机器人怎样在环境中做实验并根据回报函数成功学习到控制策略•图13-1，学习控制策略以使累积回报最大化这个问题很普遍，它是一个通过学习来控制序列过程的问题，比如–生产优化问题：选择一系列生产动作，使生产出的货物减去其成本达到最大化–出租车调度：选择出租车运载乘客，其中回报函数为乘客等待的时间和车队的整体油耗2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏4简介（2）•在第11章，已经接触到了通过学习来控制序列过程的问题，用基于解释的方法学习规则，以控制问题求解中的搜索•本章考虑的问题不同于第11章，因为考虑的问题中，行为可能有非确定性的输出，而且学习器缺少描述其行为输出的领域理论•学习控制策略类似前面讨论过的函数逼近问题，这里待学习的目标函数是控制策略:SA，它在给定当前状态S集合中的s时，从集合A中输出一个合适的动作a2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏5简介（3）•增强学习问题与普通函数逼近问题有几个重要的不同：–延迟回报：施教者只在机器人执行其序列动作时提供一个序列立即回报值，因此面临一个时间信用分配的问题：确定最终回报的生成应归功于序列中哪一个动作–探索：学习器面临一个权衡过程，是选择探索未知的状态和动作，还是选择利用它已经学习过、会产生高回报的状态和动作–部分可观察状态：机器人的传感器只能感知环境的部分状态–终生学习：使得有可能使用先前获得的经验或知识在学习新任务时减小样本复杂度2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏6学习任务•本节我们把学习序列控制策略的问题更精确地形式化，有多种可选择的形式化方法，比如–机器人的行为是确定性或非确定性的–机器人可以预测或不能预测每一个行为所产生的状态–机器人由外部专家通过示例最优动作序列来训练或必须通过执行自己选择的动作来训练–...2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏7学习任务（2）•我们基于马尔科夫决策过程定义学习控制策略问题的一般形式–设机器人可感知到其环境的不同状态集合S，可执行的动作集合A–在每个离散时间步t，机器人感知到当前状态st，选择当前动作at，环境给出回报rt=r(st,at)，并产生后继状态st+1=(st,at)–注意：回报函数和后继状态函数只依赖于当前状态和动作，这里先考虑它们为确定性的情形•定义：策略从初始状态st获得的累积值为0221...)(iitittttrrrrsV2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏8学习任务（2）•上面定义的量又称为折算累积回报，还有其他一些整体回报的定义：有限水平回报、平均回报•定义：学习控制策略的任务是，要求机器人学习到一个策略，使得对于所有状态s，V(s)为最大，表示为最优策略的值函数记作V*(s)•图13-2，对上面定义的示例)(),(maxarg*ssV)(*sV2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏9Q学习•机器人在任意的环境中直接学习最优策略很难，因为没有形式为s,a的训练样例•训练数据是立即回报函数，容易学习一个定义在状态和动作上的数值评估函数，然后实现最优策略•很明显，可以将V*作为待学习的评估函数，由于状态s下的最优动作是使立即回报r(s,a)加上立即后继状态的V*值最大的动作a，即因此，如果具有回报函数和状态转移函数的完美知识，那么就可以计算出任意状态下的最优动作•但在实际问题中，无法知道回报函数和状态转移函数的完美知识))],((),([maxarg)(**asVasrsa2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏10Q函数•对于无法知道回报函数和状态转移函数完美知识的情形，我们使用评估函数Q•评估函数Q的定义：•式子13.3可以重写为：•因此只需对当前状态的Q值做出反应，就可以选择到全局最优化的动作序列)),((),(),(*asVasrasQ),(maxarg)(*asQsa2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏11Q函数（2）•注意到•式子13.4可重写为•这个Q函数的递归定义提供了迭代逼近Q算法的基础•用表示实际Q的估计，算法中用一个大表存储所有状态-动作对的值•一开始所有表项填充为初始的随机值，然后利用下式更新表项，直到这些值收敛)',(max)('*asQsVa)'),,((max),(),('aasQasrasQaQˆQˆ)','(ˆmax),('asQraSQa),('ass2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏12表13-1在确定性回报和动作假定下的Q学习算法Q学习算法•对每个s,a初始化表项•观察当前状态s，一直重复做：–选择一个动作a并执行它–接收到立即回报r–观察新状态s’–对按照下式更新表项–ss’0),(ˆasQ),(ˆasQ)','(ˆmax),(ˆ'asQrasQa2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏13Q算法举例•图13-3，单个状态转移的Q学习•吸收目标状态：没有移出的状态•情节：在每个情节中，机器人从某个随机选择的状态开始执行动作直到到达吸收目标状态•训练过程包含一系列情节•值的演化过程–因为初始的值都为0，算法不会改变任何表项，直到它恰好到达目标状态并且收到非零回报，这导致通向目标状态的转换的值被精化–在下一个情节中，如果经过这些与目标状态相邻的状态，其非0的值会导致与目的相差两步的状态中值的变化，依次类推，最终得到一个表QˆQˆQˆQˆQˆQˆ2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏14Q算法举例（2）•上面的Q学习算法有两个特点：–值在训练中不会下降–值保持在0和真实Q值区间内•因此上面的Q学习算法会收敛到正确的Q函数•定理13.1（确定性马尔科夫决策过程中的Q学习的收敛性）–考虑一个Q学习，在一个有有界回报的确定性MDP中，Q学习使用式子13.7的训练规则，将表初始化为任意有限值，并且使用折算因子，令表示在第n次更新后的值，如果那么对所有的s和a，当n时收敛到Q(s,a)QˆQˆ),(ˆasQ),(ˆasQn),(ˆasQn2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏15Q算法举例（3）–证明：•令s’=(s,a)，则•令，则|)',''()',''(ˆ|max|)','()','(ˆ|max|)','(max)','(ˆmax||)','(max())','(ˆmax(||),(),(ˆ|','''''''1asQasQasQasQasQasQasQrasQrasQasQnasnaanaanan|),(),(ˆ|max,asQasQnasnnn10limnn2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏16实验策略•表13-1的算法的一个明显的策略是，对于状态s，选择使最大化的动作•上面策略的风险是过度束缚到在早期训练中有高值的动作，而不能探索到其它可能有更高值的动作•在Q学习中，通常使用概率的途径来选择动作，有较高值的动作被赋予较高的概率，但所有动作的概率都非0，其中一种方法是),(ˆasQQˆQˆjasQasQijikksaP),(ˆ),(ˆ)|(2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏17更新序列•定理13.1说明，Q学习不需要用最优动作进行训练，就可以收敛到最优策略•可以改变训练转换样例的序列，以改进训练效率而不危及最终的收敛性–图13-1的例子，以逆序方式执行更新，那么在第一个情节后，agent会沿着通向目标的路径对每个转换更形Q估计，这个过程要求更多的内存来存储整个情节，但会在更少的循环次数内收敛•第二个策略是存储过去的状态-动作转换，以及相应收到的立即回报，然后周期性地在其上重新训练–重放旧的转换相比于从环境中获得新转换的程度取决于两种操作的开销2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏18非确定性回报和动作•考虑非确定性情况，即回报函数和转换函数有概率的输出，比如西洋双陆棋，输出的动作具有固定的概率性•把处理确定性情况的方法扩展到非确定性的情况，一种一般化的方法是引入期望值•把非确定性情况下的Q(s,a)简单地重定义为在确定性情况下定义的量的期望值][)(0iititrEsV'''***)','(max),|'()],([)'(),|'()],([))],(([)],([))],((),([),(sasasQassPasrEsVassPasrEasVEasrEasVasrEasQ2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏19非确定性回报和动作（2）•前面对确定性情形推导的训练法则不能够在非确定性条件下收敛•???2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏20时间差分学习•Q学习算法是时间差分算法中的特例，时间差分算法的学习过程是减小机器人在不同的时间做出估计间的差异•基于单步、两步、多步前瞻计算的训练值),(ˆmax),(1)1(asQrasQtattt),(ˆmax),(221)2(asQrrasQtatttt),(ˆmax...),(111)(asQrrrasQntanntnttttn2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏21时间差分学习（2）•Sutton使用的合并从不同前瞻距离中获得的估计的TD()法•一个等价的递归定义•如果选择=0，则得到原来的训练估计Q(1)，它只考虑估计中的单步差异，当增大时，算法重点逐渐转移到更远的前瞻步•TD()方法的动机是，在某些条件下，如果考虑更远的前瞻，训练会更有效–如果机器人遵循最优策略选择动作，=1时将提供对真实Q值的完美估计，而不能多么不准确...]),(),(),()[1(),()3(2)2()1(ttttttttasQasQasQasQ)],(),(ˆmax)1[(),(11tttatttasQasQrasQQˆQˆ2003.12.18机器学习-增强学习作者：Mitchell译者：曾华军等讲者：陶晓鹏22从样例中泛化•Q学习中，只有每个可能的状态-动作被无限频繁的访问，