2.1 多臂赌博机问题

考虑下面这一问题：你面对的是在k个不同操作中不断重复做出一个选择或者是行动，每做出一个选择后你都会收到一个来自固定的与你的选择相关的概率分布的数值奖励，您的目标是最大限度地提高一段时间内的预期总回报，例如超过1000个选择或时间步骤的时间内。

这就是多臂赌博机问题的原始形式，与老虎机或“单臂赌博机”类似，但是有多个杠杆而非单独一个。每个动作的选择就像一个老虎机的杠杆之一，奖励是命中大奖的奖金。通过不断的行动选择，你可以通过把你的行动集中在最好的杠杆上来最大化你的奖金。另一个比喻是医生选择一些实验性方法来治疗一些重病患者。 每个行动都是治疗方法的具体选择，奖励则是每个病人的生存与否。如今，“赌博机问题”这个术语有时候被用来表述上述问题的更加通用的形式，但是在本书中，它只指代这个简单的例子。

在我们的多臂赌博机问题中，每个行动选择后都具有预期的或平均的奖励；我们可以这一奖励为这一行动的价值。我们将在时间步骤t选择的行动表示为$A_t$，相应的报酬表示为$R_t$。那么任意行动$a$的价值可以记做$q_*(a)$，也就是a在选择后的期望奖励：

$Q_*(a) = \mathbb{E} \left[ R_t | A_t=a \right]$.

如果已知所有行动的价值，那么多臂赌博机问题就很容易解决：只需要永远都选择那个价值最大的行动。我们假设你虽然有行动价值的估计，但是不知道行动价值的确定值。那么在时间步骤t时估计的行动$a$的价值记为$Q_t(a)$，我们希望$Q_t(a)$能够尽量接近$q_*(a)$。

只要你记住了每个行动价值的估计，那么在任何一个时间步骤下，总有起码一个行动的估计价值是最高的。这些行动就是贪婪行动。当你选择这些行动之一，那么你就是在开发现有的对行动价值的知识。如果相反你选择的是非贪婪的行动，那么你就是在探索，因为这样可以让你改进非贪婪行动的价值的估计。开发在单步情况下是最大化期望回报的正确方式，不过探索可以在长期情况下获得更好的总回报。比如，假如一个贪婪行动的价值是非常确定的，同时还有其他几个行动的估计值也很不错，只是这些行动的估计还是有很大的不确定。所有有可能其中某一个行动其实比贪婪的行动表现更好，只是你现在还不知道具体是哪个。如果你未来还有很多步的空间来做行动的选择，那么去探索一下非贪婪的行动来发现它们中哪一个会比贪婪行动的表现好会是个更佳的途径。在探索过程中，回报在短期是比较低的，但是长期下来会更高。因为一旦你探索到了更好的行动，你就可以不断的开发这些行动。由于没法在一个单个行动选择中同时进行探索和开发，所以人们常常会提到这两者之间的“冲突”。

在各种具体的案例中，探索还是开发孰好孰坏这个问题十分复杂，取决于准确的价值估计、不确定性、还有剩余步数。有许多复杂的方法来平衡探索和开发特定形式的多臂赌博机和相关问题。不过其中大部分都对稳定性、先验知识做了很强的假设，结果就是在实际应用中或者是后续章节会讨论的完整增强学习中要么无法满足这些假设要么就是这些无法验证这些假设。这些方法的理论假设如果不能满足的话，其中的最优性、有界损失的保证都是没意义的。

本书的内容不会去考虑如何用一种复杂的方法来平衡两者；我们会考虑如何从根本上来解决平衡问题。本章会展示多臂赌博机问题的集中简单的平衡方法，并且验证他们会比单纯只开发的方法表现好的多。平衡探索和开发的需求是增强学习中出现的独特挑战；本书中这一版本的多臂赌博机问题相对简单，可以让我们以一个清晰的形式来展现这一特点。