1700494651
算法之美：指导工作与生活的算法 赢留输变
1700494652
1700494653
事实证明，要用优化算法来处理多臂老虎机问题，难度非常大。彼得·惠特尔回忆说，“二战”期间，这个问题“令同盟国的分析人员身心俱疲……于是有人提议，把这个问题作为破坏智力的终极工具，交给德国人研究”。
1700494654
1700494655
战后，人们通过几年的研究，取得了若干进展。哥伦比亚大学的数学家赫伯特·罗宾斯提出了一个简单的策略，并指出，尽管这个策略尚不完善，但是可以给出一些效果不错的建议。
1700494656
1700494657
在具体考虑了只有两台老虎机的情况之后，罗宾斯提出了赢留输变算法：随便选择一台老虎机，只要它不断吐钱，就在这台机器上玩游戏。如果某次拉动拉把后，老虎机没有吐钱，就换另一台机器。1952年，罗宾斯提出的这个简单策略虽然远不完善，但是效果肯定比碰运气好。
1700494658
1700494659
在罗宾斯之后，不少人进一步研究了“赢留输变”原则，并发表了一系列论文。根据直觉，如果你本来就倾向于某台老虎机，而且这台机器刚刚又让你赢了一些钱，那么你对这台机器的评估就会升值，肯定不介意在这台机器上再玩一次。事实证明，在很多情况下，赢就留下原则都是探索与利用平衡问题优化策略的一个组成部分。
1700494660
1700494661
但是，输就走人这个原则就值得商榷了。不吐钱就换机器是一种非常草率的行为。假设你去一家餐厅用餐。你去过一百次，每次都感到非常满意。如果有一次你感到失望，会不会从此以后就再也不去这家餐厅了呢？正确的做法是不要对瑕疵惩戒过重。
1700494662
1700494663
更重要的是，赢留输变不含任何剩余时间的概念，因此没有为优化行为留出时间。你去你喜爱的餐厅用餐，结果扫兴而归，那么这个算法就会建议你以后换一家餐厅，即使你明天就要离开这座城市了。
1700494664
1700494665
不过，罗宾斯开启了多臂老虎机问题研究的先河，在随后几年里，这个领域涌现出大量的文献资料，研究人员也取得了重大进展。美国兰德公司的数学家理查德·贝尔曼发现，当我们预先知道所有的可选方案以及赢钱机会时，就能求出这个问题的精确解。就如全信息秘书问题的解法一样，贝尔曼基本上也采用了逆向法。首先，他假设自己知道之前所有决策会产生的结果，然后考虑应该在哪一台老虎机上最后一次拉下拉把。推算出结果之后，他再考虑倒数第二次的情况，然后是倒数第三次、倒数第四次，一直倒推到最开始。
1700494666
1700494667
贝尔曼的这个方法肯定可以得到确定无疑的答案，但是，如果可能的选择与赌博的轮次都非常多时，工作量就会非常大（甚至大到无法完成的程度）。此外，即使我们可以计算出未来的所有可能情况，我们也不一定确切地知道我们到底有多少赢钱机会（甚至不知道有多少种选择方案）。因此，多臂老虎机问题从本质上讲还没有得到解决。用惠特尔的话说：“它很快就变成了一个经典问题，同时也变成了永不妥协的代名词。”
1700494668
1700494669
1700494670
1700494671
1700494673
算法之美：指导工作与生活的算法 基廷斯指数
1700494674
1700494675
特例往往是通往宇宙奥秘的大门，这种情况在数学中也经常发生。20世纪70年代，联合利华公司请年轻的数学家约翰·基廷斯帮助他们优化药物试验。令人意想不到的是，基廷斯竟然解开了一道难住了一代数学家的难题。
1700494676
1700494677
基廷斯（牛津大学统计学教授）认真地思考了联合利华提出的问题：已知有几种不同的化合物，如何以最快的速度确定哪种化合物可能对哪种疾病有效？基廷斯把这个问题变成了尽可能简单的形式：有多个可选方案，每个可选方案得到回报的概率不同，可分配的精力（金钱或时间）是确定的。于是，这个问题变成了多臂老虎机问题的另外一个化身。
1700494678
1700494679
无论是追逐利润的制药公司，还是他们所在的医药行业，都经常需要面对探索与利用如何取舍的竞争需要。制药公司希望投入到研发部门的资金可以帮助他们发明新药，但是他们同时还希望现在正在帮助他们赚钱的生产线继续开足马力。医生在开处方时，肯定希望病人在现有条件下得到最好的治疗，但是他们也希望实验研究可以找到更有效的治疗手段。
1700494680
1700494681
显而易见，在这两种情况中，我们都无法确定相关的剩余时间到底是什么。从某种意义上讲，制药公司和医生一样，都对不确定的未来感兴趣。制药公司希望可以永远存在下去，而医药行业则希望取得突破，甚至希望在人们出生之前就可以向他们提供帮助。不过，他们对当前时间的重视程度更高：今天就把病人治愈，其价值高于让病人一周以后，甚至一年以后才康复，利润方面当然同样如此。经济学家把这种重现在、轻将来的概念称作“贴现”。
1700494682
1700494683
基廷斯在研究多臂老虎机问题时采用的就是这些术语，这是他与之前的研究人员不同的地方。在他的构想中，他的目标不是在固定时间段里追求最大回报，而是在时间无限长但是价值被打折扣的未来追逐最有利的结果。
1700494684
1700494685
这种贴现在我们自己的生活中并不鲜见。如果你准备在一座城市逗留10天，那么你在选择餐厅时就要记住逗留时间已经确定这个事实，但是，如果你居住在这座城市，时间就没有多大意义了。此时，你也许会想，时间越久，回报贬值的程度就越大：你更关心的是今天的晚餐，而不是明天的晚餐，并且对明天晚餐的关心程度又高于一年之后的晚餐。至于关心程度到底有多大差别，取决于你采用的“贴现函数”。基廷斯设置的条件是回报价值呈几何级数贬值，也就是说，每次去餐厅进餐的价值是上一次的分数倍。如果你认为每天被车撞的可能性为1%，那么在评估明天晚餐的价值时，就应该把它设定为今天晚餐价值的99%，因为你有可能根本没有机会享受明天的晚餐。
1700494686
1700494687
设定了这种几何贴现条件之后，基廷斯提出了这样一个策略：分别考察多臂老虎机的各个拉把，然后计算出各个拉把自己的价值。通过一个别出心裁的设想——贿赂，基廷斯完成了自己的研究，并且认为这个策略“至少可以给出一个效果不错的近似估计”。
1700494688
1700494689
在《交易还是不交易》（Deal or No Deal）这个热门电视节目中，参赛者要从26个箱子中选择一个。箱子里装有奖金，金额1美元~100万美元不等。随着游戏的进行，一位被称作银行家的神秘人物就会时不时出现。他愿意支付给参赛者金额不等的一笔钱，条件是参赛者不要打开他选中的那只箱子。参赛者需要做出选择，或者接受这笔实实在在的钱，或者选择装在箱子里的数额不确定的奖金。
1700494690
1700494691
基廷斯发现（尽管多年之后第一期《交易还是不交易》节目才播出），多臂老虎机问题与之并无区别。我们对每一台老虎机都知之甚少，甚至一无所知，但是它们都有某个保底回报率。如果摆在我们面前的不是老虎机，而是它的回报率，那么我们肯定不会去玩老虎机游戏。这个数字（基廷斯称之为“动态分配指数”，现在全世界都把它叫作“基廷斯指数”）告诉我们一条显而易见的赌博策略：一定要选择指数最高的那个拉把。[1]
1700494692
1700494693
事实上，基廷斯指数并不仅仅是一个效果不错的近似估计，还可以彻底解决回报按几何级数贴现的多臂老虎机问题。探索和利用之间的矛盾可以被转化成一个比较简单的任务：用一个数量使两者达成平衡并求这个数量的最大值。在说到自己的成就时，基廷斯非常谦虚，笑着说道：“这又不是费马大定理。”但是，他的这个定理让一大堆涉及探索与利用这个两难选择的问题得到了解决。
1700494694
1700494695
不过，即使知道以往的记录和贴现率，特定机器基廷斯指数的计算仍然非常复杂。但是，一旦我们知道某些特定条件下的基廷斯指数，我们就可以利用这些指数解决相同形式的任何问题。重要的是，由于每个拉把的基廷斯指数都是独立计算出来的，因此涉及的拉把个数不会产生任何影响。
1700494696
1700494697
下表给出了0~9次输赢所对应的基廷斯指数值，条件是回报以90%的比例递减。利用这些数值，可以解决日常生活中的多种多臂老虎机问题。例如，在这些条件下，你应该选择以往记录为1-1（即期望值为50%）的那台老虎机，而不选择记录为9-6（即期望值为60%）的那台机器。在下表中查询这两台机器对应的坐标就可以发现，了解得不多的那台机器的基廷斯指数为0.6346，而玩得比较多的那台机器得分仅为0.6300。问题解决了：这一次可以碰碰运气，大胆探索。
1700494698
1700494699
仔细观察表中的基廷斯指数，就会发现一些有意思的东西。首先，你会发现赢就留下这个原则在发挥作用：任选一排，从左向右看去，就会发现指数值一定在增长。如果在某个时候某个拉把是你的正确选择，而且你拉下那个拉把之后真的赢钱了，那么再次选择这个拉把就是一个明智的决定（沿着图表自左至右）。其次，你可以看出在什么情况下输就离开这个原则会误导你。先赢9次，然后输钱1次，对应的基廷斯指数为0.8695，仍然比表中的大多数指数高，因此你不要急于离开，至少再拉一次这个拉把。
[
上一页 ]
[ :1.70049465e+09 ]
[
下一页 ]