07. 十口井的旅人

旅人到达沙漠的那天傍晚,看见了那十口井。

它们沿着一条干涸的河床排开,每口井的样子都差不多——石头砌的井圈,一只小水桶。他要在这片沙漠里走三十天,每天必须从其中一口井打一桶水。三十桶水,决定他能不能活着出去。

他不知道哪口井好。每口井的水可能甜,可能苦,可能多,可能少,可能干。而且他每天只能选一口井——一旦下了井圈,就要把那口井的水喝下去,不能再换。

第一天,他随便挑了第三口井。水还行,不算特别好,但能解渴。

第二天,他面对一个问题:今天去第三口井,因为他知道那口至少能喝;还是去试第七口,看看能不能找到更好的?

他选了第七口。水比第三口苦,但量很大。

第三天他去了第八口——干的。一滴水都没有,白白浪费一天。

第四天他犹豫了很久。第三口"还行",第七口"苦但量大",第八口"干"。剩下七口井他完全不了解。如果他一直去试新井,他可能会再遇到几口干井,白白浪费宝贵的几天。但如果他从此只在第三、第七里选,他可能永远不知道第二口或第九口其实是这片沙漠里最好的井。

旅人想了一夜。

第二天早上,他做了一件事——他在心里给每口井打了一个分,但这个分有两部分:一部分是这口井已知的好坏,另一部分是他对这口井还有多少不知道。已知很差的井,分低;已知很好的井,分高;但完全没试过的井,他也给一个高分——因为不试就不会知道,而不知道,是一种危险。

按这个新打分法,他每天选分最高的那口井去打水。前几天,他选的几乎全是没试过的新井——他在快速地"摸底"。每试一口井,他对那口井的"未知"就少一点,那口井的分就稳定下来;有些井试过之后被证明很差(那口分会暴跌,以后基本不去),有些被证明很好(分会稳定在高位)。

到了第十二天左右,他对十口井都有了大致了解。这时,他选井的频率开始变了——他开始主要去那两三口最好的井,但偶尔还是会去那些虽然试过但还有不确定的井再试一次——也许第六口井那次苦水,只是当天天气不好;也许第二口井其实在月圆之夜会涌出更甜的水。

到了第二十五天,他几乎完全只在最好的两口井之间轮换。但是有一天,他最常去的第二口井突然变咸了——可能下了雨,可能地下水位变了。他的"打分"立刻把这口井降了下去,然后他又被迫去回顾那些"曾经试过但不算最好"的井,选其中现在最好的去用。

第三十天他走出了沙漠。回头看,他发现自己这一辈子的小冒险有个奇怪的形状:前期他狂试,中期他稳赚,但他从来没有完全停止试。

他后来回到城里,跟一个学者说了这件事。学者听完,沉默了很久,说:

你做的事情,其实是这个世界上最古老的一个困境。一只松鼠面对十棵树要不要去试新的;一个农民面对十块田要不要换种新的庄稼;一个商人面对十种生意要不要去开发新的;一个国家面对十种政策要不要尝试改革——它们全都是你那十口井。

而你做出的那个"已知的好 + 还有多少不知道"的打分法,是这个世界上没人能彻底解决,但也没人能逃避的智慧。

寓言之外

这个困境在算法里有个名字:Multi-Armed Bandit(多臂老虎机) —— 来源于赌场里那种有很多拉杆的老虎机,每个拉杆背后中奖率不同、你不知道,你必须边玩边学。这个问题的核心,叫做 Exploration vs Exploitation 困境(探索与利用)。

Exploitation(利用)——按你已知的最好选项行动。安全,短期收益高,但有可能错过那些你还没试过的更好选项。 Exploration(探索)——故意去试还不确定的选项。可能有大收获,也可能浪费一次机会。这次的代价,是为了未来多几天的好水。

这两件事根本上是矛盾的。每一次选择都是在两者之间分配——多偏一边就少另一边。整个机器学习里强化学习的所有问题,本质上都是这个困境的变种。

旅人发明的"已知的好 + 还有多少不知道"的打分法,在算法里被叫做 UCB(Upper Confidence Bound,上置信界):对每个选项,你不只看它的平均回报,还要给"你试过它的次数少"这件事额外加分。次数少 = 不确定 = 加分高。这逼你把不确定的选项也试一试。试得多了,加分就降下来了,自然过渡到只用最好的。

更实用的兄弟算法是 ε-greedy:大部分时间(比如 90%)用已知最好的,小部分时间(比如 10%)随机选一个。简单粗暴,但在很多场景下有效。

更优雅的是 Thompson Sampling:对每个选项,维护一个"它可能有多好"的概率分布(其实就是 Bayes 推断的应用——回到上一篇渔夫的本子);每次决策时,从每个选项的分布里抽样一次,选抽样值最高的那个。一个真的好的选项,大部分时候抽样值都很高;一个不确定的选项,有时抽样会抽到很高的值,这时它就会被选中——天然就达到了 "稳和探索的平衡"。这个算法非常接近贝叶斯地最优。

这些算法的真正用处,远远超出沙漠和井的范围:

广告系统——给你看十种广告,哪个点击率高?系统不能只投表现最好的那一个,因为新广告永远没机会被试到。 新闻推荐——首页文章排序,既要展示用户已知喜欢的,又要尝试推荐新主题(否则用户会被困在过滤气泡里)。 A/B 测试——传统 A/B 测试是 50/50 流量,UCB 或 Thompson 让流量自动倾斜到表现好的版本,损失更小。 药物试验——能不能在试验早期就把更多病人分配到看起来更有效的疗法?这是 Bayesian Adaptive Trial,在伦理学上仍有争议。 强化学习——AlphaGo 在每一步选下棋的位置时,本质就是在这十万个候选位置里做"探索 vs 利用"——多用蒙特卡洛树搜索结合 UCB 思想。

更深一层——没有完美解。这个困境没有数学意义上的最优策略,只有"在某种意义下接近最优"的策略。原因是:任何承诺"最终找到最好选项"的算法,都必须无限次地探索——而无限次探索意味着永远没法 fully 利用。两者根本不能同时满足。

所以,你能做的最好,是 后悔(Regret)的最小化——和"上帝视角下一直选最好选项"相比,你少赚的那部分。一个好算法的指标,是它的累积后悔随时间增长得多慢——好的算法是 O(log T),朴素的算法是 O(T)。

最后一句话——这个困境为什么这么动人?因为它不只是算法,它是所有需要在不完全信息下做长期决策的生命体的共同处境。

你换工作的时候在做这个事。你交朋友的时候在做这个事。你今晚是回去那家熟悉的餐厅,还是试一家从来没去过的新店?你已经在做这个事。

只是大多数人没有给这件事起一个名字。

在 AI 史的位置

多臂老虎机问题在 1952 年 由统计学家 Herbert Robbins 正式提出,比深度学习还早了 60 年。一开始它是一个数学好奇品。后来,1985 年 Lai 和 Robbins 给出了 Regret 下界,证明了"任何在线学习算法都不可能比 O(log T) 更快"——这是这个领域的奠基性结果。

进入 AI 时代,多臂老虎机成了强化学习的最简单形态——一个没有"状态"只有"动作"的 RL 问题。所有更复杂的 RL 算法(Q-learning、策略梯度、PPO),都以"如何平衡探索与利用"为底层关切。AlphaGo 内部的蒙特卡洛树搜索使用 UCB1 的变体来选择下一步落子——它本质上就是在每个棋盘节点上,做了一次 multi-armed bandit。

今天,你刷的每个推荐流、看的每个广告、用的每个 A/B 测试平台,底层多多少少都跑着 Robbins 在 1952 年提出的那个问题的某种变种。