算法和人生抉择：午饭到底吃什么？

大数据文摘作品

午饭吃什么？去拔草楼下新开的餐厅，还是去对面那家常去的小馆子？

这可能是很多人每天面临的亘古选择题，也是我们每一天都在做一类特定的选择：选择已知的最爱还是未知的可能？

如何平衡这个选择不仅是我们纠结的日常，也是计算机学家半个世纪以来的研究对象。

本周，我们继续聊聊【选择】这个人生中的重大话题。由来自杜克大学美女主播段天霖与大家分享：在选择时，如何衡量“坚守已知（exploit)”或者“探索未知(explore)”。

就像读书会小蒋所说：对于计算机来说，explore代表收集信息，而exploit是运用这些信息来达到一个确定的理想结果；在生活中，explore是我们对未知世界的探索，而exploit是享受已知的美好。

从这个意义上讲，认识一个新朋友、听一首新歌是explore，与家人团聚、听一首循环无数次的老歌就是exploit。仔细想想，生活中这两者总是共存的，但他们之间的平衡却是因人而异的。那么从算法的角度，这个命题是否存在一种最佳解法呢？

要回答这个问题，我们还是要从它的起源说起。

虽然，计算机科学家对于午饭吃什么有种有啥吃啥的佛系心态，但是，他们对于幻想怎么在赌场赚最多的银子倒是有极大的热情。

假设赌场中有一排未知预期收益的老虎机，只能靠投钱来以身试法，你要花多久时间来收集信息，又该在什么时候锁定目标发家致富呢，这就是Explore-Exploit的最经典案例，multi-armed bandit，多臂老虎机问题。

让我们从这个经典案例说起，看看历史上，不同科学家是如何选择的。

Win-Stay逻辑

也许你可以随机挑选一台老虎机，只要你在赢就一直盯住它，一旦输了就转投另一台，以此循环。

这是由哥伦比亚大学的数学家Herbert Robbins针对多臂老虎机问题提出的第一个解法: Win-Stay Lose-Shift。

这个解法中Win-Stay的逻辑很直观：如果你已经选择一台机器，那么如果它让你赢了，那只会让你更有可能继续选择这台机器；但Lose-Shift就有待推敲了：试想你认准的机器让你连赢10次，但在第11次输了，你真的会因为这一次的结果而彻底改换一个尝试对象吗？

就像你最爱的那家餐厅，你真的会因为某一次的某道菜没有那么好吃就不再去了吗？

抓住时机

假设我们考虑的时间是一个有限的区间，探索的价值是逐日递减的，且不说你新发现的选项到底是不是比你目前的最爱更好，就算你找到了新的最爱，已经用来explore的时间也意味着起码这一次留给你exploit的时间没有多少了。

反过来，有限时间里exploit的价值却是递增的。你截止这个月为止最爱的餐厅by definition就一定和你上个月之前所尝试过的餐厅一样好或更好。

所以时间的维度决定了我们的策略应当根据剩余时间而定：如果你还有大把的时间去explore或者exploit，那么尽情探索吧。

基廷斯系数

现在我们知道了interval是平衡explore/exploit的关键，同时它并不一定是一个具象甚至有界的期限，那么我们该如何将这种对于interval的认知融合到算法中呢？

Gittins Index回答了这个问题。

要理解Gittins Index 基廷斯系数，我们要先介绍一个经济学中常见的概念：time discounting，Gittins认为这种单位回报是呈几何递减的。

以选择餐厅为例，如果你认为你有1%的可能性某天会离开这座城市，那么一顿第二天晚餐的价值就应该是今天晚餐价值的0.99，依次递推。基于目前所收集的信息，Gittins Index为每一种情况都赋予了一个系数。

因此，你的众多选择瞬间变成一个明确的定量比较——谁系数高就选谁。

后悔值和最优值

1985年，提出Win-Stay Lose-Shift的那位哥大数学家Robbins时隔多年又带着加强版解法归来了。

这一次他提供了另一个看待这类问题的思路：在你做一个选择时，你不必纠结任何一个选项会给你带来什么，而是扪心自问，如果不做某个决定，你会有多后悔？

Robbins的新算法所做的将后悔量化，定义为实施某一特定策略所得到的回报与最大可能的回报之间的差值，就是选择那个将你的后悔值最小化的策略。

如何平衡？

不过人和机器终究还是不同的，我们并不会、也不需要总按照最佳策略生活。

面对这变幻不息的世界，我们能从这些算法中学到的，或许并不只是某一种策略，而更是一种新的看待选择与变化的方式：

人生的旅程中，刚刚启程的孩子正该尽情探索属于他们的无限可能，而年纪渐长的父母老人在我们眼里的固执己见，又何尝不是一种看过更多人生风景后的积累与沉淀。

二月已过、三月将来，新春伊始，不如就从今天起将这些新的体会付诸实践：探索一家新的餐厅，也挑战踏出你的舒适圈，或许渐渐你会发现，生活真的一天比一天更美好。