评估反馈

2. Evaluative Feedback (incompleteideas.net)

强化学习与其他学习区别最主要的特征是：使用训练信息评估（evaluate）行为而不是通过正确的行为来指导（instruct）。这就是需要积极探索的原因，需要明确的试错法来寻找良好的行为。 纯粹的评价性反馈表明所采取的行动有多好，而不是它是可能的最好还是最差的行动。 评价反馈是函数优化方法的基础，包括进化方法。 另一方面，纯粹的指导性反馈表明要采取的正确行动，而与实际采取的行动无关。 这种反馈是监督学习的基础，包括模式分类、人工神经网络和系统识别的大部分内容。 就其纯粹的形式而言，这两种反馈是截然不同的：评价性反馈完全取决于所采取的行动，而指导性反馈则独立于所采取的行动。 还有一些有趣的中间案例，其中评估和教学融合在一起。

在本章中，我们在简化的环境中研究强化学习的评估方面，这种环境不涉及学习在多种情况下采取行动。 这种非关联设置是大多数涉及评估反馈的先前工作已经完成的设置，它避免了完整强化学习问题的大部分复杂性。 研究这个案例将使我们能够最清楚地看到评估反馈与指导性反馈有何不同，但又可以与指导性反馈相结合。

我们探索的特定非关联评估反馈问题是n-armed bandit 问题的简单版本。 我们使用这个问题来介绍一些基本的学习方法，我们将在后面的章节中扩展这些方法以应用于完整的强化学习问题。 在本章的最后，我们通过讨论当老虎机问题变得具有关联性时会发生什么，即在不止一种情况下采取行动时会发生什么，从而更接近完整的强化学习问题。

2.1 多臂赌博机问题（n-Armed Bandit Problem)

Consider the following learning problem. You are faced repeatedly with a choice among different options, or actions. After each choice you receive a numerical reward chosen from a stationary probability distribution that depends on the action you selected. Your objective is to maximize the expected total reward over some time period, for example, over 1000 action selections. Each action selection is called a play.

If you maintain estimates of the action values, then at any time there is at least one action whose estimated value is greatest. We call this a greedy action. If you select a greedy action, we say that you are exploiting your current knowledge of the values of the actions. If instead you select one of the nongreedy actions, then we say you are exploring because this enables you to improve your estimate of the nongreedy action's value. Exploitation is the right thing to do to maximize the expected reward on the one play, but exploration may produce the greater total reward in the long run.

如果您保持对动作值的估计，那么在任何时候都至少有一个动作的估计值最大。 我们称之为贪婪行动。 如果您选择贪婪的行动，我们说您正在利用您目前对行动价值的了解。 相反，如果您选择其中一个非贪婪操作，那么我们说您正在探索，因为这使您能够改进对非贪婪操作价值的估计。 探索是在一次游戏中最大化预期回报的正确做法，但从长远来看，探索可能会产生更大的总回报。

For example, suppose the greedy action's value is known with certainty, while several other actions are estimated to be nearly as good but with substantial uncertainty. The uncertainty is such that at least one of these other actions probably is actually better than the greedy action, but you don't know which one. If you have many plays yet to make, then it may be better to explore the nongreedy actions and discover which of them are better than the greedy action. Reward is lower in the short run, during exploration, but higher in the long run because after you have discovered the better actions, you can exploit them. Because it is not possible both to explore and to exploit with any single action selection, one often refers to the "conflict" between exploration and exploitation.

In any specific case, whether it is better to explore or exploit depends in a complex way on the precise values of the estimates, uncertainties, and the number of remaining plays.There are many sophisticated methods for balancing exploration and exploitation for particular mathematical formulations of the n-armed bandit and related problems. However, most of these methods make strong assumptions about stationarity and prior knowledge that are either violated or impossible to verify in applications and in the full reinforcement learning problem that we consider in subsequent chapters. The guarantees of optimality or bounded loss for these methods are of little comfort when the assumptions of their theory do not apply.

下面介绍几种解决多臂赌博机问题的方法。

2.2 行动-价值方法

首先更仔细地研究一些用于估计动作值和使用估计值来做出动作选择决策的简单方法。本章中， 把action的真实值表示为，且第次play的估计值表示为 。一个动作的真正价值是选择该动作时收到的平均奖励。估计这一点的一种自然方法是对选择动作时实际收到的奖励进行平均。 换句话说，第t 次游戏时之前游戏行为a被选择了次，每次相应回报为那么它的评估回报为：

(2.1)

如果，那么定义为如的默认值。当时，根据大数定律，收敛于.我们称其为用于估计动作值的样本平均方法，因为每个估计值都是相关奖励样本的简单平均值。 当然，这只是估计动作值的一种方法，不一定是最好的方法。 尽管如此，现在让我们继续使用这种简单的估计方法，然后转向如何使用估计来选择动作的问题。

最简单的动作选择规则是选择估计值最高的动作（或动作之一），即在第次游戏选择，满足。如果有不止一个贪婪的行为，那么就以某种任意的方式，也许是随机的，在它们之间进行选择。我们将这个贪婪的动作选择方法写成

其中表示动作a，随后的表达式被最大化（同样，任意断开连接）。

这种方法总是利用当前的知识来最大化即时奖励；它根本不花时间对明显较差的动作进行采样，以查看它们是否真的会更好。 一个简单的替代方法是大部分时间都贪婪选择，而每隔一段时间，以小概率ε随机、统一地，独立于动作值估计选择一个动作。我们将这个近似贪婪的动作选择规则调用方法称为方法。这些方法的一个优点是，在限制次数增加的情况下，每个动作都会被无限次采样，保证对于所有，当时，所有的收敛于。也就是说，几乎可以肯定，这当然意味着选择最优动作的概率收敛到大于。 然而，这些只是渐近保证，并没有说明这些方法的实际有效性。

练习2.1 在ε-贪婪行为选择中，对于两个action且ε=0.5的情况，选择贪婪行为的概率是多少？

解答：选择贪婪行为，即选择当前回报均值大的那个action，根据ε-贪婪算法实现方式，若random≥ε，则进行贪婪选择，即概率为0.5.

练习2.2 Bandit示例考虑K＝4个动作的k-armed bandit问题，表示为1, 2, 3和4。考虑应用ε-贪婪动作选择、样本平均动作值估计，对于所有a，初始估计的bandit算法。假设行动和奖励的初始顺序为，在这些时间步中，可能发生了ε概率情况，导致随机选择一个动作。肯定是在什么时间发生的？可能发生在什么时间点？

计算每次action后的回报Q(a):

第一次不发生ε概率进行动作选择的情况为： A1=argmax(Q1(a))=1，与实际相同，也有可能发生ε情况

第一次action后，,Q2(a|a≠1)=0

第二次不发生 ε概率进行动作选择的情况为： A2=argmax(Q2(a))=1，与实际不同

第二次action后，=1 ,Q3(1)=1 ,Q3(a|a≠1,2)=0

第三次 不发生 ε概率进行动作选择的情况为：A3=argmax(Q3(a))=1 ，与实际不同

第三次 action后，  ,Q4(1)=1 ， Q4(a|a≠1,2)=0

第四次 不发生 ε概率进行动作选择的情况为：A4=argmax(Q4(a))=2，与实际同， 也有可能发生ε情况

第四次 action后，  ,Q5(1)=1 ， Q5(a|a≠1,2)=0

第五次 不发生 ε概率进行动作选择的情况为：A5=argmax(Q5(a))=2，与实际不同

第五次 action后， ,Q6(1)=1 ， Q6(a|a≠1,2)=0，Q6(2)=1.67

根据ε-greedy算法，每次以概率ε随机选择，以1-ε选择最大回报值的臂，因此若选出的臂不是最大的，则说明进行了随机选择，即第二三、五次肯定是 ε概率 随机的，可能是第一、四次。

2.3 10臂测试平台

为了粗略评估贪婪方法和ε-贪婪方法的相对有效性，我们在一组测试问题上对它们进行了数值比较。这是一组2000个随机生成的n-armed（n=10)赌博机问题。对于行动，回报符合均值为，方差为1的高斯分布。2000次多臂赌博机任务通过2000次对进行选择，每次均符合均值为0，方差为1的正态分布。接着对该问题应用学习方法，在时间步t时从服从均值为方差为1的正态分布中选择动作。对任务进行平均，我们可以绘制各种方法的性能和行为，因为它们随着超过 1000 次游戏的经验而改进，如图 2.1 所示。 我们将这套测试任务称为 10 臂测试平台。

假设可以与赌博机交互T次，显然我们每次采取的行动（action）不必一成不变，记我们在t时刻采取的行动为，获得的回报为那么目标是

.

实际应用中，会根据之前得到和进行优化调整，也就是说是和的函数。但是是随机的因此必然是一个随机变量，我们记为。同时，为了简化，记。以上优化问题，可以重写为

这里的概率分布与和的取值有关。事实上，对概率分布的调整的过程就是学习的过程。

图2.1 10臂赌博机测试平台的案例。根据标准正态分布把10项行动的真实值均值被选择出来，然后根据均值的单位方差正态分布选择实际奖励，如上图所示（小提琴图）

当应用于一个bandit问题时，我们可以通过超过1000个时间步的试验来衡量它的性能和行为，这构成了一次运行。在2000次独立运行中重复这个过程，每次运行都是不同的bandit问题，我们习得了学习算法平均行为的度量。

图2.2 ε-贪婪方法在10臂测试平台的平均表现。这些数据是超过2000次的平均值，所有方法使用样本平均作为行为-价值估计值

图2.2 比较了贪婪算法和两种ε-贪心算法在10臂赌博机问题中的表现。这两种方法都使用样本平均技术形成了它们的动作值估计。 上图显示了随着运行次数增加后的预期奖励。贪心方法一开始比其他方法提高得略快，但随后在较低的水平上趋于平稳。 它每一步获得的奖励只有大约 1，而在该测试平台上的最佳奖励约为 1.55。 从长远来看，贪心方法的性能要差得多，因为它经常卡在执行次优操作中。下图显示贪心方法仅在大约三分之一的任务中找到了最佳动作。 在另外三分之二中，它的最佳动作的初始样本令人失望，并且再也没有回到它。ε-贪心算法因为持续进行探索（explore）从而提高了找到最佳动作的机会，因此最终表现更好。探索的更多，因此更早地找到了最佳行动，但是在超过91%的时间里都没有选择最佳动作；方法搜索的更慢，但是最终在两个性能指标上都表现得比好。同样可以设置随着时间减少的ε来在最大值和最小值中找到最佳值。

ε-贪心算法的优势取决于任务，例如，假设奖励方差更大，比如 10 而不是 1。对于更嘈杂的奖励，需要更多的探索才能找到最佳动作，并且 ε-greedy 方法相对于 greedy 方法应该表现得更好。 另一方面，如果奖励方差为零，那么贪心方法在尝试一次后就会知道每个动作的真实价值。 在这种情况下，贪心方法实际上可能表现最好，因为它很快就会找到最佳动作，然后就永远不会探索了。 但即使在确定性的情况下，如果我们削弱其他一些假设，探索也有很大的优势。 例如，假设老虎机任务是非平稳的，即动作的真实值随时间变化。 在这种情况下，即使在确定性的情况下也需要探索，以确保非贪婪行为之一没有改变为比贪婪行为更好。 正如我们将在接下来的几章中看到的，有效的非平稳性是强化学习中最常见的情况。 即使基本任务是固定的和确定性的，学习者也面临着一组类似强盗的决策任务，每个任务都因学习过程本身而随时间变化。 强化学习需要在探索和利用之间取得平衡。

练习 2.3  在图 2.2 所示的比较中，从长期来看，哪种方法在累积奖励和选择最佳行动的累积概率方面表现最好？ 会好多少？

ε=0.01的情况会最好，在累积奖励方面。