强化学习笔记：多臂老虎机问题
目录
3. Conlict between exploitation and exploring
4. Action-Value method, 行动-价值方法
1. 前言
强化学习与其它类型的学习的最重要的差异之一是它所利用的训练信息为评价性反馈信息(evaluative feedback information)，而不是指令式的反馈信息(instructive feedback information)。评价性反馈信息是关于所采取的行动的得分，单纯根据得分你无法判断行动是否最优或者最差，只有通过多次尝试才能统计性地给出行动相对好坏的估计。评价性反馈信息取决于所采取的行动，而另一方面，指令式的反馈信息直接告诉你正确的行动是什么，与你所采取的行动无关。
本章通过多臂老虎机的例子来研究强化学习的基于评价性反馈的特色，介绍强化学习的一些基本学习方法。一开始我们会将问题设定限定在非关联设定（non-associative setting）下，即学习的情境(situation)是单一的，智能体不需要学习多种情境下的所应该采取的不同行动。最后我们会将解除这一限制，考虑存在多种情境且最佳行动取决于情境的多臂老虎机问题。
参考文献：
Sutton-Reinforcement-Learning: section2.1~2.3
2. 多臂老虎机问题描述
设想一个反复进行的游戏，其中k种行动可以选择。每一次行动后，你将收获一个数值奖励，该奖励为随机性的，遵从依赖于你所采取的行动的某种平稳概率分布。你的目标是最大化一段时间内的总体奖励，比如说1000次行动，或者1000个时间步长（每个时间步长采取一次行动）。
这个问题是多臂老虎机游戏的一个抽象描述。它可以代表除了现实的多臂老虎机以外的很多不同的现实问题实例。比如说，一个医生为危重病人们（每次一个，先后串行进行的，因而构成一个时序列）尝试实验性疗法，每次给一个病人施加一种疗法后，得到的结果有好有坏，病人存活下来或者变好就是一次疗法尝试的奖励。如果有k种疗法那就相当于是一个k-臂老虎机。
在以上问题中，每种行动每次所获得的奖励不是确定性的，而是遵从某种平稳随机分布，我们把它的期望称为这个行动的价值value。我们假定在t时刻采取的行动记为
，对应的奖励为 ，则行动a的价值定义为：
如果我们已知每个行动的价值，那这个问题就变得微不足道了，你总是选择价值最大的那个行动就可以了。所以这个问题的前提是你不知道，但是你可以通过不断尝试并根据每次行动所得到的反馈去估计，记到时刻t为止对行动a的估计价值为 。很显然，我们希望我们的估计值尽量接近 。
3. Conlict between exploitation and exploring
通俗一点说就是，享受与探索之间的冲突。
接上一章，如果你持续对所采取过的行动的价值进行评估，那么在每一时刻，你有一个关于所有的可能行动的价值列表，其中必定有某个或者某些行动的价值是最大的。你可以采取一个最简单（不幸的是，最简单的未必是最好的）的策略，就是总是采取估计价值最大的那个行动或那些估计价值等于最大值中的某个行动，这些行动我们称之为贪婪行动(greedy action)，这种策略我们称之为贪心策略。当你选择采取贪婪行动时，我们称之为exploiting（大意是说享用我们之前探索的结果，不冒险了）。反之，如果你不采取贪婪行动，而是从其它行动选项中随机选一个，我们称之为exploring（即探索未知世界中更好的东西）。
Exploitation和exploration是一枚硬币的两面，两者都不可或缺。Exploration是为了将来能够更好地exploiting，但是，如果光exploitation的话，那尚未探明的未知领域或许还有更好的东西呢，可能就错过了。即便考虑经历了一段时间的exploring后得到了一些关于各个行动的价值估计，由于只是基于有限样本的统计估计，所以当前的具有最大价值的行动并不一定就是最优的。如果从此之后就采取单纯的exploitation就有可能错失了真正的最优选项。所以从理论上来说，在一个无限游戏中，只要行动的回报（或奖励）是具有随机性质的，从理论上来说，任何时刻开始完全采取贪婪策略都可能错过真正的最优解。
但是如果光顾着exploring，不适时地享用一下既往探索得到的成果就好比公司上市财务自由了还是苦哈哈地啃着方便面保持着每周工作80个小时的节奏奋斗不止直到挂机一样也挺冤的。
在任何一个时刻要么exploiting要么exploring无法两者兼顾，这就是我们通常所说的conflict between exploitation and exploring.
在任何特定的场合下，到底应该exploiting还是exploring是一个非常复杂的问题，取决于对于价值的估计的精确度、不确定性，以及游戏尚余的时间。。。以人生为例，如果你刚刚走出学习，前面的路还长着呢，那么你应该更多地去exploring，不断地探索未知世界寻找更好的东西；如果你已经步入中老年，就该消停一些，更多地exploiting，好好地享受既往奋斗的成果。
总之，如何取得exploitation and exploring之间的折衷是强化学习中的一个非常关键的问题。接下来我们会讨论几种简单的折衷方法。
4. Action-Value method, 行动-价值方法
接下来我们讨论基于行动价值估计值进行行动选择的方法，这种方法我们统称为“行动-价值”方法。作为这个方法的前提自然是先要进行行动价值的估计。最直观简单的方法自然就将某个行动既往所获得的奖励进行平均，如下所示：
其中， 是所谓的indicator function。上式看起来很炫其实道理非常简单，就是针对所有采取行动a所获得的奖励Ri就简单的平均，这种价值估计方法就称为sample-average方法，很直白。
一个简单的事情用数学公式一表示立马逼格就不一样了，尤其是用了像 这样的^-^。
很显然，当行动a的样本数足够大时，根据大数定律，估计价值将收敛于真实价值，即：
当然，这只是价值估计方法的一种而已，不一定是最好的一种。
最简单的行动选择方法自然就是根据它们的估计价值进行选择。如前所述，这中策略就是贪婪策略（always exploiting），这个策略记为：
上一节的讨论我们已经知道了这种贪婪策略并不是一个好的策略。最极端的情况是，假定所有的行动的价值估计在一开始被初始化为0，在第一次行动（由于所有的行动的价值估计都为0所以会随机选择一种行动）后该行动的价值估计将变为大于0（假定它的奖励为正），因为在此后将永远都只选择这一个行动。只有当单次行动的奖励会出现负值时才可能出现不同的选择。
为了取得上节所述的exploitation and exploring之间的折衷，可以考虑所谓-greedy策略，即有的概率进行随机选择（对应exploring），另外(1-)的概率则选择greedy-action（对应exploitation）。由于随机选择时仍然有可能选中greedy-action，因此这一策略中，选择greedy-action的概率将略大于(1-)。假定总共有K个行动供选择，而随机选择时总是等概率地从所有行动中选取的话，则选择greedy-action概率为：
5. 仿真
以下我们将通过仿真来探索一下以上所描述的-greedy策略在多臂老虎机问题中的表现。
具体仿真代码和仿真结果分析参见下一篇。敬请期待。。。