多臂匪徒问题

8.1　多臂匪徒问题

多臂匪徒模型最早是由Robbins于1952年提出来的。该模型属于统计决策模型，曾在统计学的领域有过仔细的研究。该模型通过对当前信息不断更新的同时来优化自己的决策。它是在没有任何先验知识的前提下，通过不断的探索来搜集知识，并且在每次确定新的搜索路径的时候，都通过在对已搜集到知识的利用和对新知识的探索间进行协调来寻找到最优的搜索路径，以便更快捷的完成搜索过程的一个最优决策的模型。这个模型应用范围很广，在临床试验中对于在不同的治疗方法间做选择来保证病人的痛苦最小，在自适应路由中最小化网络的延迟及动态资源配置等诸多领域中都有所应用。在一个经济环境中，跨期分配问题中的实验性消费就是一个在当前收益和信息价值两者间取得权衡的问题。

多臂匪徒模型是对单臂匪徒模型的一个扩展，所谓单臂匪徒模型就是大家所熟知的老虎机或角子机。如图8.1所示，老虎机主要由内部三个卷轴、一个投硬币的槽，以及外部的一个拉手组成，当投下硬币之后，便可拉动拉手，三个转轴便会旋转，当转轴转动停止之后，出来的结果就决定是赢是输，产生多少回报。

图8.1　赌场里的老虎机

多臂匪徒模型，就是给这个老虎机赋予多个拉手，拉动每个拉手所能产生的回报是互不相关的。赌博者的目的都是为了赢得尽可能多的钱，获得最大的回报，多臂匪徒模型的目的也是如此，找到一个合理的策略，可以使得拉动拉手的人获得最大的收益。也就是说，多臂匪徒就是一个拥有K个拉手的老虎机，赌博者要从这K个拉手中选择一个拉手进行操作来获得回报，这个回报可能为正值、0或者负值；而每个拉手的回报所遵循的分布式是不尽相同的，其中每拉动一次拉手都可以获得一个回报；而在某一个特定的时间段内，赌博者则只能拉动一个拉手。而我们要做的就是找到一个策略，使得赌博者可以根据这个策略来获得尽可能大的回报。

当一个赌徒站在这台多臂老虎机面前时，他可以说是没有任何头绪的，所有的拉手对他来说都是同等概率的，他要想知道哪个拉手最好，唯一办法就是不断地去试探，通过不断的试探来发现规律，以此来推断出哪个拉手是可能获得回报最大的拉手。

当然，我们不能让他无限制地试探下去，我们可以给他限定时间或者拉动的次数，让他在这个有限的时间或次数内来尽快获得一个结论。赌徒为了让自己的尝试更加有效率，就不会随机去试探每个拉手，就必然会通过一种方法来有选择地试探拉动拉手的顺序。这也就是我们这个模型要解决的问题。

这个问题看似简单，但其在统计决策领域却作为一个极其经典的问题不断被研究人员所关注，主要是由于它在探索（对每个拉手进行试探以找到最好的那一个）和利用（拉动当前看来回报最好的那个拉手）间的权衡问题上建立了一个很好的模型。对于拉手的每次选择都会立即产生一个随机的回报，但是决定这些回报的过程是通过不断地拉动拉手所产生的。

多臂匪徒模型的一个显著特点是，每个拉手回报的分布只有当这个拉手被拉动之后才发生变化。因而，一个拉手的回报并不依赖于从其他拉手所获得的回报。这个特性也意味着，每个拉手回报的分布并不显著的依赖其被拉动的时刻。