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中输出一个合适的动作 a
2003.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获得的累积值为
0
221,..)(
i
iti
tttt
r
rrrsV
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
学习任务（ 2）
上面定义的量又称为折算累积回报，还有其他一些整体回报的定义：有限水平回报、平均回报
定义：学习控制策略的任务是，要求机器人学习到一个策略?，使得对于所有状态 s,V?(s)为最大，表示为最优策略的值函数 记作 V*(s)
图 13-2，对上面定义的示例
)(),(m a xa rg* ssV
)(* sV?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
Q学习
机器人在任意的环境中直接学习最优策略很难，因为没有形式为 <s,a>的训练样例
训练数据是立即回报函数，容易学习一个定义在状态和动作上的数值评估函数，然后实现最优策略
很明显，可以将 V*作为待学习的评估函数，由于状态 s
下的最优动作是使立即回报 r(s,a)加上立即后继状态的
V*值最大的动作 a，即因此，如果具有回报函数和状态转移函数的完美知识，
那么就可以计算出任意状态下的最优动作
但在实际问题中，无法知道回报函数和状态转移函数的完美知识
))],((),([m a xa r g)( ** asVasrs a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
Q函数
对于无法知道回报函数和状态转移函数完美知识的情形，我们使用评估函数 Q
评估函数 Q的定义：
式子 13.3可以重写为：
因此只需对当前状态的 Q值做出反应，就可以选择到全局最优化的动作序列
)),((),(),( * asVasrasQ
),(m a xa rg)(* asQs a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
Q函数（ 2）
注意到
式子 13.4可重写为
这个 Q函数的递归定义提供了迭代逼近 Q算法的基础
用 表示实际 Q的估计，算法中用一个大表存储所有状态 -动作对的 值
一开始所有表项填充为初始的随机值，然后利用下式更新表项，直到这些值收敛
)',(max)( '* asQsV a?
)'),,((m a x),(),( ' aasQasrasQ a
Q?
Q?
)','(?m a x),( ' asQraSQ a ),(' ass
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 13-1 在确定性回报和动作假定下的 Q学习算法
Q学习算法
对每个 s,a初始化表项
观察当前状态 s，一直重复做：
– 选择一个动作 a并执行它
– 接收到立即回报 r
– 观察新状态 s’
– 对 按照下式更新表项
– s?s’
0),(asQ
),(? asQ )','(?m a x),(? ' asQrasQ a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
Q算法举例
图 13-3，单个状态转移的 Q学习
吸收目标状态：没有移出的状态
情节：在每个情节中，机器人从某个随机选择的状态开始执行动作直到到达吸收目标状态
训练过程包含一系列情节
值的演化过程
– 因为初始的 值都为 0，算法不会改变任何 表项，直到它恰好到达目标状态并且收到非零回报，这导致通向目标状态的转换的 值被精化
– 在下一个情节中，如果经过这些与目标状态相邻的状态，其非 0的 值会导致与目的相差两步的状态中值的变化，依次类推，最终得到一个 表
Q?
Q? Q?
Q?
Q?
Q?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
Q算法举例（ 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
),(? asQn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Q算法举例（ 3）
– 证明：
令 s’=?(s,a)，则
令,则
|)',''()',''(?|m a x
|)','()','(?|m a x
|)','(m a x)','(?m a x|
|)','(m a x())','(?m a x(||),(),(?|
',''
'
''
''1
asQasQ
asQasQ
asQasQ
asQrasQrasQasQ
nas
na
ana
anan
|),(),(?|m a x,asQasQ nasn
nn1
0lim nn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
实验策略
表 13-1的算法的一个明显的策略是，对于状态 s，
选择使 最大化的动作
上面策略的风险是过度束缚到在早期训练中有高 值的动作，而不能探索到其它可能有更高值的动作
在 Q学习中，通常使用概率的途径来选择动作，
有较高 值的动作被赋予较高的概率，但所有动作的概率都非 0，其中一种方法是
),(? asQ
Q?
Q?
j asQ
asQ
i j
i
k
ksaP
),(?
),(?)|(
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
更新序列
定理 13.1说明,Q学习不需要用最优动作进行训练，就可以收敛到最优策略
可以改变训练转换样例的序列，以改进训练效率而不危及最终的收敛性
– 图 13-1的例子，以逆序方式执行更新，那么在第一个情节后，
agent会沿着通向目标的路径对每个转换更形 Q估计，这个过程要求更多的内存来存储整个情节，但会在更少的循环次数内收敛
第二个策略是存储过去的状态 -动作转换，以及相应收到的立即回报，然后周期性地在其上重新训练
– 重放旧的转换相比于从环境中获得新转换的程度取决于两种操作的开销
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
非确定性回报和动作
考虑非确定性情况，即回报函数和转换函数有概率的输出，比如西洋双陆棋，输出的动作具有固定的概率性
把处理确定性情况的方法扩展到非确定性的情况，一种一般化的方法是引入期望值
把非确定性情况下的 Q(s,a)简单地重定义为在确定性情况下定义的量的期望值
][)( 0 i itit rEsV
' '
'
*
*
*
)','(m a x),|'()],([
)'(),|'()],([
) ) ],(([)],([
) ) ],((),([),(
s a
s
asQassPasrE
sVassPasrE
asVEasrE
asVasrEasQ
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
非确定性回报和动作（ 2）
前面对确定性情形推导的训练法则不能够在非确定性条件下收敛
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
时间差分学习
Q学习算法是时间差分算法中的特例，时间差分算法的学习过程是减小机器人在不同的时间做出估计间的差异
基于单步、两步、多步前瞻计算的训练值
),(?m a x),( 1)1( asQrasQ tattt
),(?m a x),( 221)2( asQrrasQ tatttt
),(?m a x.,,),( 111)( asQrrrasQ ntanntnttttn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
时间差分学习（ 2）
Sutton使用的合并从不同前瞻距离中获得的估计的
TD(?)法
一个等价的递归定义
如果选择?=0，则得到原来的训练估计 Q(1)，它只考虑估计中的单步差异，当?增大时，算法重点逐渐转移到更远的前瞻步
TD(?)方法的动机是，在某些条件下，如果考虑更远的前瞻，训练会更有效
– 如果机器人遵循最优策略选择动作,?=1时将提供对真实 Q值的完美估计，而不能 多么不准确
..,]),(),(),()[1(),( )3(2)2()1( tttttttt asQasQasQasQ
)],(),(?m a x)1[(),( 11 tttattt asQasQrasQ
Q?
Q?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
从样例中泛化
Q学习中，只有每个可能的状态 -动作被无限频繁的访问，学习过程才会收敛，执行效率很低
比较实际的系统通常在 Q学习中合并使用其他章讨论的函数逼近方法
把反向传播算法结合到 Q学习中，方法是用神经网络替代查找表，把每个 更新作为训练样例，例如
– 把状态 s和动作 a编码为网络输入，并使用式子 13.7
和 13.10训练网络
一旦引入了泛化函数逼近器，增强学习将不能收敛
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
与动态规划的联系
像 Q学习这样的增强学习方法，与用于解决马尔科夫决策过程的动态规划方法有紧密的关系
Q学习的新颖之处在于它假定不具有环境的完美知识，
因此不能在内部模拟的状态空间移动中学习，而必须在现实世界的移动中观察后果
我们主要考虑机器人为收敛到一个可接受的策略必须执行的真实世界动作的数量，而不是计算迭代次数，
这是因为在外部世界中执行动作的时间和费用开销比计算开销更值得关注
在真实环境中移动学习并观察结果的系统通常称为在线系统，而主要通过模型模拟动作的学习的被称为离线系统
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
与动态规划的联系（ 2）
Bellman等式形成了解决 MDP的动态规划方法的基础，形式如下
Bellman证明了最优策略满足上式，且满足上式的任何策略为最优策略
动态规划早期的工作包括 Bellman-Ford最短路径算法，它基于节点邻居的距离，通过不断更新每个图节点到终点的估计距离来学习图中的路径，图的各边以及目标节点已知的假定，等价于移动函数和回报函数已知的假定
) ) ) ](,(())(,([)()( ** ssVssrEsVSs
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
小结
增强学习解决自治机器人学习控制策略的问题，目标是使机器人从任意起始状态收到的总回报最大化
本章介绍的增强学习算法适合一类被称为马尔科夫决策过程的问题，即应用任意动作到任意状态上的输出只取决于当前动作和状态
Q学习是增强学习的一种形式，其中机器人学习的是一组状态和动作上的估计函数，它被定义为最大期望折算积累回报，算法可用在不具备动作怎样影响环境的先验知识情况下
在一定假定下,Q学习具备收敛性，实践中需要大量的训练循环
Q学习是更广泛的时间差分算法中的一种，时间差分算法通过不断减小在不同时间内产生的估计间的差异来学习
增强学习与动态规划有密切联系，关键差异是，动态规划假定拥有状态转移函数和回报函数的知识，而 Q学习假定缺乏这些知识
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
补充读物
Samuel1959，西洋双陆棋学习程序
Bellman1958,Ford & Fulkerson1962，最短路径算法
Holland1986，学习分类系统的组桶式方法
Barto et al.1983，时间信用分配方法
Sutton1988,Dayan1992,TD(?)方法
Watkin1989,Q学习
McCallum1995和 Littman1996，增强学习的扩展
,..
机器学习第 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中输出一个合适的动作 a
2003.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获得的累积值为
0
221,..)(
i
iti
tttt
r
rrrsV
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 8
学习任务（ 2）
上面定义的量又称为折算累积回报，还有其他一些整体回报的定义：有限水平回报、平均回报
定义：学习控制策略的任务是，要求机器人学习到一个策略?，使得对于所有状态 s,V?(s)为最大，表示为最优策略的值函数 记作 V*(s)
图 13-2，对上面定义的示例
)(),(m a xa rg* ssV
)(* sV?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 9
Q学习
机器人在任意的环境中直接学习最优策略很难，因为没有形式为 <s,a>的训练样例
训练数据是立即回报函数，容易学习一个定义在状态和动作上的数值评估函数，然后实现最优策略
很明显，可以将 V*作为待学习的评估函数，由于状态 s
下的最优动作是使立即回报 r(s,a)加上立即后继状态的
V*值最大的动作 a，即因此，如果具有回报函数和状态转移函数的完美知识，
那么就可以计算出任意状态下的最优动作
但在实际问题中，无法知道回报函数和状态转移函数的完美知识
))],((),([m a xa r g)( ** asVasrs a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 10
Q函数
对于无法知道回报函数和状态转移函数完美知识的情形，我们使用评估函数 Q
评估函数 Q的定义：
式子 13.3可以重写为：
因此只需对当前状态的 Q值做出反应，就可以选择到全局最优化的动作序列
)),((),(),( * asVasrasQ
),(m a xa rg)(* asQs a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 11
Q函数（ 2）
注意到
式子 13.4可重写为
这个 Q函数的递归定义提供了迭代逼近 Q算法的基础
用 表示实际 Q的估计，算法中用一个大表存储所有状态 -动作对的 值
一开始所有表项填充为初始的随机值，然后利用下式更新表项，直到这些值收敛
)',(max)( '* asQsV a?
)'),,((m a x),(),( ' aasQasrasQ a
Q?
Q?
)','(?m a x),( ' asQraSQ a ),(' ass
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 12
表 13-1 在确定性回报和动作假定下的 Q学习算法
Q学习算法
对每个 s,a初始化表项
观察当前状态 s，一直重复做：
– 选择一个动作 a并执行它
– 接收到立即回报 r
– 观察新状态 s’
– 对 按照下式更新表项
– s?s’
0),(asQ
),(? asQ )','(?m a x),(? ' asQrasQ a
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 13
Q算法举例
图 13-3，单个状态转移的 Q学习
吸收目标状态：没有移出的状态
情节：在每个情节中，机器人从某个随机选择的状态开始执行动作直到到达吸收目标状态
训练过程包含一系列情节
值的演化过程
– 因为初始的 值都为 0，算法不会改变任何 表项，直到它恰好到达目标状态并且收到非零回报，这导致通向目标状态的转换的 值被精化
– 在下一个情节中，如果经过这些与目标状态相邻的状态，其非 0的 值会导致与目的相差两步的状态中值的变化，依次类推，最终得到一个 表
Q?
Q? Q?
Q?
Q?
Q?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 14
Q算法举例（ 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
),(? asQn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 15
Q算法举例（ 3）
– 证明：
令 s’=?(s,a)，则
令,则
|)',''()',''(?|m a x
|)','()','(?|m a x
|)','(m a x)','(?m a x|
|)','(m a x())','(?m a x(||),(),(?|
',''
'
''
''1
asQasQ
asQasQ
asQasQ
asQrasQrasQasQ
nas
na
ana
anan
|),(),(?|m a x,asQasQ nasn
nn1
0lim nn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 16
实验策略
表 13-1的算法的一个明显的策略是，对于状态 s，
选择使 最大化的动作
上面策略的风险是过度束缚到在早期训练中有高 值的动作，而不能探索到其它可能有更高值的动作
在 Q学习中，通常使用概率的途径来选择动作，
有较高 值的动作被赋予较高的概率，但所有动作的概率都非 0，其中一种方法是
),(? asQ
Q?
Q?
j asQ
asQ
i j
i
k
ksaP
),(?
),(?)|(
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 17
更新序列
定理 13.1说明,Q学习不需要用最优动作进行训练，就可以收敛到最优策略
可以改变训练转换样例的序列，以改进训练效率而不危及最终的收敛性
– 图 13-1的例子，以逆序方式执行更新，那么在第一个情节后，
agent会沿着通向目标的路径对每个转换更形 Q估计，这个过程要求更多的内存来存储整个情节，但会在更少的循环次数内收敛
第二个策略是存储过去的状态 -动作转换，以及相应收到的立即回报，然后周期性地在其上重新训练
– 重放旧的转换相比于从环境中获得新转换的程度取决于两种操作的开销
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 18
非确定性回报和动作
考虑非确定性情况，即回报函数和转换函数有概率的输出，比如西洋双陆棋，输出的动作具有固定的概率性
把处理确定性情况的方法扩展到非确定性的情况，一种一般化的方法是引入期望值
把非确定性情况下的 Q(s,a)简单地重定义为在确定性情况下定义的量的期望值
][)( 0 i itit rEsV
' '
'
*
*
*
)','(m a x),|'()],([
)'(),|'()],([
) ) ],(([)],([
) ) ],((),([),(
s a
s
asQassPasrE
sVassPasrE
asVEasrE
asVasrEasQ
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 19
非确定性回报和动作（ 2）
前面对确定性情形推导的训练法则不能够在非确定性条件下收敛
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 20
时间差分学习
Q学习算法是时间差分算法中的特例，时间差分算法的学习过程是减小机器人在不同的时间做出估计间的差异
基于单步、两步、多步前瞻计算的训练值
),(?m a x),( 1)1( asQrasQ tattt
),(?m a x),( 221)2( asQrrasQ tatttt
),(?m a x.,,),( 111)( asQrrrasQ ntanntnttttn
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 21
时间差分学习（ 2）
Sutton使用的合并从不同前瞻距离中获得的估计的
TD(?)法
一个等价的递归定义
如果选择?=0，则得到原来的训练估计 Q(1)，它只考虑估计中的单步差异，当?增大时，算法重点逐渐转移到更远的前瞻步
TD(?)方法的动机是，在某些条件下，如果考虑更远的前瞻，训练会更有效
– 如果机器人遵循最优策略选择动作,?=1时将提供对真实 Q值的完美估计，而不能 多么不准确
..,]),(),(),()[1(),( )3(2)2()1( tttttttt asQasQasQasQ
)],(),(?m a x)1[(),( 11 tttattt asQasQrasQ
Q?
Q?
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 22
从样例中泛化
Q学习中，只有每个可能的状态 -动作被无限频繁的访问，学习过程才会收敛，执行效率很低
比较实际的系统通常在 Q学习中合并使用其他章讨论的函数逼近方法
把反向传播算法结合到 Q学习中，方法是用神经网络替代查找表，把每个 更新作为训练样例，例如
– 把状态 s和动作 a编码为网络输入，并使用式子 13.7
和 13.10训练网络
一旦引入了泛化函数逼近器，增强学习将不能收敛
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 23
与动态规划的联系
像 Q学习这样的增强学习方法，与用于解决马尔科夫决策过程的动态规划方法有紧密的关系
Q学习的新颖之处在于它假定不具有环境的完美知识，
因此不能在内部模拟的状态空间移动中学习，而必须在现实世界的移动中观察后果
我们主要考虑机器人为收敛到一个可接受的策略必须执行的真实世界动作的数量，而不是计算迭代次数，
这是因为在外部世界中执行动作的时间和费用开销比计算开销更值得关注
在真实环境中移动学习并观察结果的系统通常称为在线系统，而主要通过模型模拟动作的学习的被称为离线系统
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 24
与动态规划的联系（ 2）
Bellman等式形成了解决 MDP的动态规划方法的基础，形式如下
Bellman证明了最优策略满足上式，且满足上式的任何策略为最优策略
动态规划早期的工作包括 Bellman-Ford最短路径算法，它基于节点邻居的距离，通过不断更新每个图节点到终点的估计距离来学习图中的路径，图的各边以及目标节点已知的假定，等价于移动函数和回报函数已知的假定
) ) ) ](,(())(,([)()( ** ssVssrEsVSs
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 25
小结
增强学习解决自治机器人学习控制策略的问题，目标是使机器人从任意起始状态收到的总回报最大化
本章介绍的增强学习算法适合一类被称为马尔科夫决策过程的问题，即应用任意动作到任意状态上的输出只取决于当前动作和状态
Q学习是增强学习的一种形式，其中机器人学习的是一组状态和动作上的估计函数，它被定义为最大期望折算积累回报，算法可用在不具备动作怎样影响环境的先验知识情况下
在一定假定下,Q学习具备收敛性，实践中需要大量的训练循环
Q学习是更广泛的时间差分算法中的一种，时间差分算法通过不断减小在不同时间内产生的估计间的差异来学习
增强学习与动态规划有密切联系，关键差异是，动态规划假定拥有状态转移函数和回报函数的知识，而 Q学习假定缺乏这些知识
2003.12.18 机器学习 -增强学习 作者,Mitchell 译者：曾华军等 讲者：陶晓鹏 26
补充读物
Samuel1959，西洋双陆棋学习程序
Bellman1958,Ford & Fulkerson1962，最短路径算法
Holland1986，学习分类系统的组桶式方法
Barto et al.1983，时间信用分配方法
Sutton1988,Dayan1992,TD(?)方法
Watkin1989,Q学习
McCallum1995和 Littman1996，增强学习的扩展
,..
