2.10 本章总结

本章我们提出了几种平衡探索动作及利用动作的简单方法，其中\varepsilon-贪婪方法随机利用少量时间执行探索动作；而UCB方法虽然采用确定的动作选择策略，但巧妙的倾向于选择被选择次数更少的动作；梯度强盗算法（gradient bandit algorithm)评估动作选择倾向而非动作价值，并通过基于柔性最大化分布的分级的及概率性的原则来选择倾向性更高的动作；即便最简单的乐观初始化这种应急性办法，也能使贪婪动作策略执行更多的探索动作。

学习了上面这些方法，我们很自然的想知道到底这其中哪一种方法最有效。虽然概括性的回答这个问题很难，但我们可以将这些方法全部应用于解决本章使用的10臂赌徒摇臂机问题上，以此来比较不同方法的表现。比较中的一点麻烦就是这些方法都含有参数，也就是说它们都是关于自身参数的函数，所以为了使比较结果有意义，我们需将方法均考虑为函数形式。到目前为止，本书中的学习曲线（learning curve）图都是以时间为横轴，不同参数设定下某一方法的学习表现图，但如果我们将全部的算法处于不同参数条件下的学习表现绘制在一张图内，那么该图将过于复杂，难于进行算法比较。因此，我们将某一算法在某一参数值下的1000个时间步内表现做平均，并将其作为一点标注在图上，实现学习曲线的简化，图2.6表现了多种赌徒算法的学习表现图，每种算法可视为关于参数的函数，这种图被称为参数研究（parameter study）图，请注意参数的值是由两个因子相乘并取对数得到。通过观察可知，图中算法的表现都呈现倒U形状，也就是说所有的算法都是在参数中间值取得最佳表现，既不是高参数值也不是低参数值。在评估方法时，我们不应该仅关心在最佳参数下方法的表现，同时应该考虑方法表现对参数变化得到敏感性。图2.6中表现的算法都较不敏感，在参数值变化一个量纲范围内的表现都较平稳，但总体来讲，在10臂赌徒摇臂机问题上，UCB算法的表现最佳。

尽管本章讨论的算法都很简单，但在作者看来这些方法都可以被认为是最先进的。虽然存在一些更精巧的方法，但在我们真正关心的完全强化学习问题上，这些方法的复杂性以及使用时所需要的假设条件，使它们变得不够实用。从第5章开始，我们开始介绍解决完全强化学习问题的方法，其中部分使用了本章中介绍的简单方法。

虽然本章介绍的简单方法已经是我们目前可以采用的最佳方法了，但它们远远未达到完全解决探索与利用平衡问题的程度。

经过充分研究，目前发现了一种用来平衡k臂赌博机问题中探索与利用动作的有效方法，该方法通过计算一种被称为Gittins索引（Gittins indices)的特殊函数来实现。这提供了一种解决特定赌徒摇臂机问题的最优方法，但该方法假设问题的先验概率分布已知。不幸的是，不论是这种理论还是它的计算难度都无法归纳到解决完全强化学习问题的方法中。

贝叶斯（Bayesian）方法是一种假设已知初始动作价值分布并在后续每一步精确更新价值的方法（假设动作价值的真值是稳定不变的），一般来讲，更新的计算过程可能非常复杂，但对于特定的分布（共轭先验分布（conjugate priors）），该过程很简单。一种可能的情况是根据每一步中，可执行动作为最佳动作的后验概率来选择动作，这种方法，有时被称为后验采样（posterior sampling）或汤普森采样（Thompson sampling），通常与本章中介绍的不需要分布模型的方法表现相似。

在贝叶斯条件下，我们甚至有可能得到探索与利用的最佳平衡，利用该方法可以计算所有可能动作对应的不同即时奖励的概率，以及动作结果产生的动作价值后验分布。这种进化式的价值分布代表着所要解决问题的信息状态（information state），假设有一个1000步的横轴，我们可以得到1000中每一步的可能动作、可能结果奖励、下一步可能动作、下一步可能奖励，根据这个假设，每一个可能的事件序列的奖励和及概率都可以被确定，那么我们只需从中选取最佳的一组，但在该问题中，概率树将会快速的增长，即便只有两个可能动作和两个可能奖励，概率树将出现2^{2000}个叶节点。一般来讲精确实现这么大的计算量是不可行的，但实现高效近似计算或许可行，这种思想可以有效的将赌徒摇臂机问题转化为完全强化学习问题。在此条件下，我们可以使用类似本书第2部分介绍的近似强化学习方法找到问题的最优解，但该部分是目前学界的一个研究课题，超出了本书的介绍范围。

练习2.9 （编程练习） 对练习2.5中的非稳定实例做一个如图2.6的绘图分析，包括\alpha=0.1的定步长\varepsilon-贪婪算法。对每种算法和参数设定运行200,000步，对最后100,000的奖励做平均并绘图。

参考文献

2.1 一直以来，赌徒摇臂机问题在统计学、工程学和心理学领域被广泛研究，在统计学中，赌徒摇臂机问题被归类为“顺序设计的实验”，该问题由Thompson（1933,1934）和Robbins（1952）年引入，在1956年得到了Bellman的研究。Berry和Fristedt在1985年从统计学角度为赌徒摇臂机问题提出了广泛适用的解决办法。Narendra和Thathachar（1989）从工程角度看待赌徒摇臂机问题，对该问题涉及的各种理论传统进行了良好的讨论。在心理学领域，赌徒摇臂机问题从属于统计学习理论（如Bush和Mosteller,1955;Estes,1950)。

贪婪一词经常出现于关于启发式搜索的文献中（如Pearl，1984），在控制工程中，关于探索与利用之间的冲突通常理解为鉴别（或估计）与控制的冲突（如Witten，1976）。考虑到控制不确定系统时需要同时解决鉴别和控制的问题，Feldbaum（1965）称该问题为双重控制问题。Hollan（1975）在讨论遗传算法时，强调了这种利用的需要与探索的需求之间冲突的重要性。

2.2 解决我们K臂赌徒摇臂机问题的动作价值方法首先是由Thathachar和Sastry在1985年提出的，在学习自动机相关文献中，这类方法通常被称为价值估计算法，动作价值（action value）一词由Watkins于1989年提出，第一次使用\varepsilon-贪婪方法的或许也是Watkins（1989，p.187)，但由于这个想法比较简单，在此之前同样有一些看似相似的方法。

2.4-5 该部分内容属于随机迭代算法，Bertsekas和Tsitsiklis（1996）年较完善的论述了该部分内容。

2.6 乐观初始化是Sutton（1996）应用于强化学习中的。

2.7 早期关于使用置信上界进行动作选择的研究由Lai和Robbins（1985），Kaelbling（1993b），Agrawal（1995）年提出。本节中提出的UCB算法在文献中被称为UCB1，首次使用是由Auer，Cesa-Bianchi和Fischer在2002年。

2.8 梯度强盗算法是Williams（1992）提出的基于梯度的强化学习方法的一种特殊例子，本书后续章节将介绍该方法进一步发展成的演员-评论家算法和策略梯度算法。该节的叙述方式借鉴于Balaraman Ravindran（私人交流）。关于基线的进一步讨论可见Greensmith，Bartlett和Baxter（2001,2004）以及Dick（2015）的论文。

2.9 相关搜索（associative search)一词及其相关的问题由Barto，Sutton和Brouwer（1981）提出。相关强化学习(associative reforcement learning)一词也被用于相关搜索(Barto和Anandan，1985)，但我们更倾向于保留该词来表示完全强化学习问题（Sutton，1984）。（并且，如我们所叙述的那样，现在一些论文也使用“情境赌徒摇臂机问题”来描述该问题。）我们注意到Thorndike在效果法则的论述中中通过构建情景（状态）与动作之间的联系描绘了相关搜索，根据操作、仪器或条件上的术语（Skinner，1938），一个有识别力的刺激是表现了特别的强化情景的一种刺激。在强化学习问题中，不同的有识别力的刺激对应不同的状态。

2.10 Bellman（1956）是第一个提出如何利用基于贝叶斯公式的动态规划方法解算探索与利用平衡问题的学者。Gittins索引由Gittins和Jones（1974）提出。Duff（1995）提出了使用强化学习赌徒摇臂机的Gittins索引的方法，Kumar（1985）的调查很好的讨论了解决此类问题的贝叶斯与非贝叶斯方法。信息状态（information state）一词来源于部分可观测MDPs,详见Lovejoy（1991）。

其他关于探索效率的理论研究，通常由算法收敛到最优策略的速度评判。一种规范探索效率的方式是将监督学习中抽样复杂度（sample complexity）概念引入强化学习中，该概念为算法达到一定置信水平下目标函数所需要的训练样本数量。强化学习算法中抽样复杂度的定义是算法选择近优动作之前所经历的时间步数量（Kakade，2003）。Li（2012）讨论了抽样复杂度和其他的一些可以用于评判强化学习中探索效率的理论方法。