节点农场：探索与停止的策略设计

1. 问题定义与记号

地图上有 $N = 300$ 个块，块 $i$ 的产出 $q_i$ 固定但事先未知。$q_1, \dots, q_N$ 相互独立（一个块的产出不影响另一个块），服从同一个分布 $F$（每个块的产出都是按同一条规则随机抽的，规则规定了产出落在每一段数值范围内的概率，$F$ 就是这条规则）。 $F$ 属于六个家族之一（均匀、正态、Beta、对数正态、幂律、两堆），家族在每局开始时公布，家族内的参数不公布。参数分两类：尺度（整体产出大约多大，比如均匀分布的上界）和形状（大块与小块的比例怎么分布，比如幂律的指数）。 一局 $T = 200$ 轮。第 1 轮随机分配一个块；之后每轮三选一：留在当前块、换一个没去过的块、回到去过的某个块。留下得 $q_{\text{当前}}$；换块（不论换到新块还是回到去过的块）得目标块的产出并扣费用 $c$；第 1 轮的块是开局分配的，不扣费。 $c$ 每张地图不同：等于本图产出中位数乘以一个 0.05 到 0.6 之间的随机比例（第 5.1 节），玩家可见。目标是 200 轮总得分最大。

记号：第 $t$ 轮已挖过 $n$ 个块，其产出记为 $x_1, \dots, x_n$，其中最大值 $y = \max_j x_j$；剩余轮数 $\ell = T - t + 1$，含本轮（第 200 轮时 $\ell = 1$）。基准"上限"定义为从第 1 轮起一直站在全图最好的块上的总分 $T \cdot \max_i q_i$，所有成绩以占上限的比例报告。

三条假设贯穿全文：

• 没去过的块与去过的块相互独立，都是 $F$ 的抽样（每个块的产出都是从 $F$ 里独立抽出来的一个数）。一个常见的问题是"我手里的样本在全部 300 块里排第几"，它在这里不需要回答：给定 $F$，剩下的块的分布与已见样本无关，已见样本只用于估计 $F$ 的参数。
• 产出固定（基础版），一个块挖一次即完全已知。
• 所有策略拿到的"换新块"顺序相同（地图由一个种子生成，种子是生成地图用的一个数字，同一个数字生成同一张图；"换新块"时拿到的块按同一个随机顺序排好；种子相同则顺序相同），策略之间的差异完全来自何时停手，没有抽签运气。

这个问题和三个经典问题都有关系，但都不相同。多臂老虎机 [1, 4, 5] 研究在几条臂之间反复试验以估计各臂的平均回报；这里块比轮数多（300 块、200 轮），且产出固定，挖一次就完全知道，不存在"再试一次以估得更准"的问题。秘书问题 [3] 只能录用当前面试者，错过不能回头；这里可以回到任何去过的块，只是要付换块费。Weitzman 的保留值 [2] 处理"每个箱子有开箱费，开完只能拿一个"的搜索问题；这里没有开箱费，费用发生在换块，而且守着一个块每轮都有收入。所以本文不直接套用这三者的解法，而是从"每一轮守还是探"的动态规划出发（第 2.3 节），把它化成一步比较（第 4.1 节）。

2. 模型一：先探后守

2.1 规则与期望得分

先探后守（explore-then-commit）只有一个参数 $K$：前 $K$ 轮每轮换一个没挖过的新块，第 $K+1$ 轮回到这 $K$ 块里产出最高的那块，守到第 $T$ 轮结束。图 1 把同一张地图上 $K$ 取 5、18、60 的三局画在一起：横轴是轮次，纵轴是这一轮挖到多少，一局的总分就是蓝色和绿色的面积减去红色的换块费。

三块面积各有名字。蓝色是探索期的 $K$ 根条子，每根是一个随机块的产出，平均高度记 $E[X]$（$X$ 是随机抽一个块的产出，这样的量叫随机变量；$E[\cdot]$ 读作"……的平均值"）。绿色是守的 $T-K$ 轮，高度是 $K$ 块里最高的那块，记 $\max_K$，它的平均高度记 $E[\max_K]$（探索期结束时，第 1 节记号里的 $n$ 就是 $K$，$y$ 就是 $\max_K$）。红色是 $K$ 次换块费：探 $K$ 块换了 $K-1$ 次，回到最好的块再换 1 次。图 1 是一张图的账；把三块面积换成对很多张图取平均的高度，就是期望总分（平均能拿多少分）：

同样是 $K = 18$，图 1 那一张图的账是 17972，平均账 $f(18)$ 是 18052（图 4）。$K$ 取多少最好，取决于绿色平台的高度 $E[\max_K]$ 随 $K$ 长得多快。$E[\max_K]$ 是"$K$ 个随机块里最高那块的产出"对所有可能的地图取平均，算法分两种。均匀分布 $[0, 100]$ 有公式 $E[\max_K] = 100K/(K+1)$。理由：把 0 到 100 这条线段首尾接成一个圆环，在圆环上随机放 $K+1$ 个点，再从其中一个点剪开拉直，剪开的那个点就是 0 和 100 两端，其余 $K$ 个点就是 $K$ 个随机数。圆环上的 $K+1$ 个点没有哪个特殊，所以剪出来的 $K+1$ 段平均长度相等，各为 $100/(K+1)$；最大的数离 100 差的正是最后一段，平均 $100/(K+1)$。其他分布没有简单公式，用数值积分：把产出的取值范围切成很多小段，每段"这段的产出 × 最好块落在这段的概率"相加，用程序算。图 2 把两种分布的 $E[\max_K]$ 画成黑线，并配 30 张地图的实际轨迹作对照。

表 1：两个分布下最好块期望随样本数的增长。均匀分布看到第 10 块以后再看一块只涨不到 1 分，因为上界 100 就在那里；幂律看到第 40 块再看一块仍涨近 9 分：增量也在减（25 → 8.7），只是减得慢，因为尾巴上一直有更大的块。幂律行的数字看起来和"平均 50"不搭，用幂律的规则算一遍：产出超过 $x$ 的概率是 $(x_m/x)^\alpha$（$x \ge x_m$）。令 $(16.7/x)^{1.5} = 1/2$，解得 $x = 16.7 \times 2^{1/1.5} = 26.5$，即一半的块不到 26.5，平均值 50 是被少数大块拉上去的；单块超过 500 的概率是 $(16.7/500)^{1.5} = 0.6\%$，40 块里至少一块超过 500 的概率是 $1 - (1 - 0.006)^{40} \approx 22\%$（"至少一块超过"等于 1 减去"40 块全都不超过"），所以 40 块里最好的一块常常在几百以上；平均 524 是数值积分算出来的。

要判断该不该再多探一块，看 $f(K+1) - f(K)$。图 3 把这一步的变化画出来：底图是 $K = 3$ 的方案，斜线是改成 $K = 4$ 后变化的地方，只有三处。

三项里代价一随 $K$ 变大（平台越来越高）、代价二不变，只有收益项的走向需要论证：平台每次抬高的薄片是不是越来越薄。这就是引理 1。证明里用到两件事：一是"在……的前提下的平均"，记作 $E[A \mid B]$，指只看 $B$ 发生的那些情况，在这些情况里对 $A$ 取平均；二是一个只有"发生 / 不发生"两种情况的量（不发生时为 0），它的平均值 = 发生的概率 × 发生时的平均大小。

收益递减、代价递增，一个下降的数减一个上升的数只会从正变负一次，所以 $f$ 先升后降，只有一个峰；最优的 $K^*$ 就是收益刚好跌到代价以下的那一步。图 4 把这两条线画在均匀分布的例子上。

图 4 下面板的收益曲线由 $E[\max_K]$ 增长得多快决定，也就是分布尾巴（分布里数值很大但很少见的那一小部分）的轻重：轻尾（最大的块比平常大不了多少）的收益曲线很快掉到代价之下，早停；重尾（偶尔出现比平常大很多倍的块）的收益曲线迟迟不落，值得多探。第 2.2 节按家族仿真验证这一点。

2.2 各家族的最优探索轮数

2.1 的闭式（能写成一个公式直接算的式子）只对一张上界固定的均匀地图成立。实际每张图的参数（上界、换块费等）都是随机抽的，要对所有地图取平均，$f(K)$ 没有闭式，我们直接仿真（按第 5.1 节的规则生成地图，让策略在上面真的跑一遍，记下总分）：每个家族 150 张地图，$K$ 从 10 到 150 每隔 5 取一个值，跑先探后守，按"总分 ÷ 上限"对图取平均。

表 2：各家族的最优探索轮数。"最好块 / 前 5% 块"是尾巴轻重的直观指标：把一张图的 300 块按产出排序，最高的一块除以排在前 5% 边界上的那块（第 16 名），再对图取平均；比值接近 1 说明最好的块也就比第 16 名高一点，比值 8.5 说明最好的块是第 16 名的八倍多。来自 data/node-farm-eval.js（40 图）；$K^*$ 与得分来自 data/node-farm-kcurve.js（150 图）。

2.3 有效性：与分布已知时的最优解比较

先探后守把"什么时候停"定死在第 $K$ 轮。更一般的做法是每一轮重新决定。任何时刻，决定需要的信息只有两个数：还剩几轮 $\ell$（含本轮），手里最好的块产出多少 $y$。这两个数合起来叫一个"状态"。图 6 把这一轮的两个选择和各自的后果画出来，按"人此刻正站在最好的块上"画；右下角的分支说明了不站在上面时怎么记账。

图里"同样的问题再来一遍"就是递归（一个问题的答案由同一个问题在更小规模下的答案算出来，这里"更小"指少一轮）。记 $V_\ell(y)$ 为"从状态 $(\ell, y)$ 起，按最好的做法往后走，平均能拿多少分"。它不需要事先知道最好的做法是什么：只剩一轮时最好的做法显然是守，$V_1(y) = y$；有了 $V_{\ell-1}$ 就能算出 $V_\ell$，同时也就知道了这一状态该守还是该探。两条路各自的值取大的：

其中 $\max(X, y)$ 把图 6 的两个分支合成一个式子：刷新了就是 $X$，没刷新就是 $y$。$E[V_{\ell-1}(\max(X,y))]$ 是"各分支按概率加权平均"：粗看是两个分支，$X > y$ 的概率乘上那时的值，加 $X \le y$ 的概率乘上 $V_{\ell-1}(y)$；细看 $X > y$ 这一支里 $X$ 本身有很多可能的取值，每个取值又要按各自的概率加权，所以是对 $X$ 的所有取值加权平均。$V_\ell(y)$ 对每个 $(\ell, y)$ 是一个数，全部列出来就是一张表（行是 $\ell$，列是 $y$）。这张表这样算：$y$ 只取有限个值（第 4.1 节核对时取 0 到 100 的整数，等间距共 101 个；对真实地图取该图 300 个块的产出值），从 $\ell = 1$ 往上一层层算到 $\ell = T$，每个 $(\ell, y)$ 格子记下该守还是该探，这就是动态规划。

有一处简化：没刷新纪录时其实不一定马上回去，如果下一轮还打算探，从差块出发和从最好块出发抽到的下一块是一样的，回去那次 $c$ 就多付了；公式按"总要回去"记账，把回程费算多了一点。这使"探"这条路的值被算低了一点，即偏保守（偏保守：算出的"探"的价值比真实的低，两可时公式会倾向于守，只会少探不会多探）。不改公式，是因为改正它要把"人此刻站在哪"（站在最好块上 / 不在，两种）也记进状态，表加倍；而第 4.1 节的规则 (1) 用同样的记账法，两者比较时记账方法一致。我们对每张图用它 300 个块的经验分布（把这 300 个块的实际产出当成"分布"，每块概率 $1/300$）求解这张表，作为"分布全知"时的最好成绩。

表 3：固定 $K$ 与分布全知上限的差距。每家族 60 图，来自 tournament/strategies/eval-basic.js。"随机家族"列：每张图的家族从六种里随机抽一种，相当于六家族混合，下文各表同。同一个 $K = 40$ 在表 2 是 65.8%、这里是 68.1%、表 8 是 66.6%：每张表用的是各自那批地图，数字略有出入。

一个参数的先探后守拿到全知上限的 93%（68.1 / 73.5），在轻尾家族上差距只有 2 到 7 个点。差距集中在两堆和幂律：知道金块存在的策略会坚持找，先探后守到 $K$ 就停。 这说明先探后守是有效的基线（基线：用来当比较标准的简单方法），也说明剩下的提升空间几乎全在"用样本判断这张图的尾巴"上。

3. 陪跑模型

五个对照模型，都不用公布的家族去估计分布（ε-greedy、UCB 和边际收益停止只用家族各调一个数字：换新块的概率、对新块的乐观程度、起步样本数）：

• ε-greedy：每轮以概率 $\varepsilon$ 换新块（按家族取 0.05 到 0.2，家族不公布时 0.1），否则去均值最高的块。除最后 15 轮外一直按这个概率探索。
• UCB：每块打分 $\bar r_i + C\,\bar r\,\sqrt{\ln t / n_i}$，其中 $\bar r_i$ 是块 $i$ 的平均产出，$n_i$ 是块 $i$ 挖过的次数，$t$ 是当前轮数，$\bar r$ 是所有挖过的块的总平均（用它缩放，使加分项不依赖本图产出的大小），$C = 0.4$ 是固定常数（不按家族调），$\ln$ 是自然对数；分数最高的块就是下一轮去的块。"换新块"也作为候选参与打分，它的分数是 $\bar r \times$ 乐观系数 $+ C\,\bar r\sqrt{\ln t}$，乐观系数按家族取 0.9 到 1.6（尾巴越重越乐观），这是 UCB 里唯一按家族调的数字。这个公式仅作对照，含义是给挖得少的块加一个乐观分。产出固定时挖一次就全知道，这个乐观分本来就无意义。
• 阈值停止：看够 10 块后，当前产出 $\ge$ 已见平均 $+ 2\times$ 标准差（标准差：一批数离它们平均值的典型距离）就守住；探过 60 块或临近结束回到已知最好的块。
• 边际收益停止：每轮比较 $(\ell - 1) \cdot \frac{1}{n+1} \cdot (x_{(1)} - x_{(2)})$ 与 $(y - \bar x) + 2c$。$x_{(1)}$、$x_{(2)}$ 是已挖的块里第一高和第二高的产出（$x_{(1)}$ 就是 $y$），$\bar x$ 是已挖的块的平均，$n$ 是已挖块数。前者是"本轮之后的轮数 × 刷新纪录的概率（引理 1 的 $1/(n+1)$） × 刷新幅度（用第一名减第二名估）"；后者是这一轮少拿的（最好块减平均）加两次换块费（换出去一次、回来一次）。起步样本数按家族取 10 到 30（均匀、正态 10，Beta 12，对数正态 20，两堆、幂律 30），样本不到它时一律探。
• 1/e 法则：秘书问题（依次面试候选人，每个人只能当场录用或放走，不能回头，求选中最优者的概率最大）的答案是先看完前 $1/e$ 的候选人再决定，$e \approx 2.718$，$1/e \approx 37\%$。这里用成前 37% 的轮数（$200/e$ 四舍五入为 74 轮）全部探索。秘书问题不能回头且只求选中第一名的概率，与本题目标不同，列入作为常见误用的对照。

表 4：陪跑模型成绩，每家族 40 图，来自 data/node-farm-eval.js。

边际收益停止在两堆分布上只有 46.8%：没见过金块时"第一名减第二名"接近零，它过早停止；没见过的尾巴无法从样本间距估出。 1/e 法则在幂律上是最好的（33.3%），在均匀上却是 77.1%，除 UCB 外最低：37% 的探索比例恰好落在重尾家族的最优附近，对轻尾家族则探过了头。

3.1 各模型擅长的题型

表 5：各模型的总分与擅长的家族。基线数据同表 4；分布预测模型一行来自表 8 的 300 图，"+12.0"等是与表 8 里先探后守 $K=40$ 那一行相减（两堆 74.8 − 62.8 = 12.0）。

规律只有一条：探得少的模型赢在轻尾、输在重尾，探得多的相反。阈值停止与边际收益平均只探二十来块，在均匀、Beta 上接近最优，在幂律、两堆上停得太早；1/e 与 $K = 50$ 探得多，在重尾上得分更高，在均匀上多花几十轮。阈值停止的阈值是"已见平均加两个标准差"，随本图样本定，所以叫相对阈值；轻尾家族里这个位置离最好的块不远，重尾家族里远远达不到。 分布预测模型在六个家族上都高于固定 $K = 40$（表 5），领先幅度在两堆最大（+12.0），在对数正态和正态最小（+1.1、+1.2）。正态是各模型差距很小的家族之一（表 4 正态列除 UCB 的 69.1% 外都在 75% 到 84% 之间）：正态分布两头都窄，探 10 块和探 50 块看到的差不多。

4. 模型二：分布预测模型

4.1 决策规则

每轮按图 6 做一笔账，但"之后"不再递归，只假设探完这一块就守。像 2.1 那样先把两条路的总账列出来：

• 守：本轮和之后共 $\ell$ 轮每轮拿 $y$，合计 $\ell\,y$。
• 探一块然后守：付 $c$；本轮拿新块的产出 $X$，抽之前只知道它的平均值 $E[X]$；之后 $\ell - 1$ 轮守在两块里更好的那块上，每轮拿 $\max(X, y)$；若 $X < y$ 要再付一次 $c$ 回去，这件事发生的概率是 $P(X < y)$。合计的平均值是 $-c + E[X] + (\ell-1)\,E[\max(X,y)] - c\,P(X < y)$。

探划算当且仅当第二条大于第一条。把 $\ell y$ 拆成 $(\ell-1)y + y$，两边各自对应相减：$(\ell-1)E[\max(X,y)]$ 减 $(\ell-1)y$ 得 $(\ell-1)\big(E[\max(X,y)] - y\big)$，$E[X]$ 减 $y$ 得 $E[X] - y$。再看 $E[\max(X,y)] - y$：$y$ 是已知的数，两个量的平均值之差等于差的平均值，所以它等于 $E[\max(X,y) - y]$；而 $\max(X,y) - y$ 在 $X > y$ 时等于 $X - y$，否则等于 0，这正是 $(X-y)^+$。于是 $E[\max(X,y)] - y = E[(X-y)^+]$，记为 $g(y)$。它就是引理 1 里的增量 $E[(X-\max_K)^+]$，只是引理 1 里的纪录 $\max_K$ 是还没抽的随机量，这里的纪录 $y$ 是已经看到的数。探索划算当且仅当

规则 (1) 只比较两条路：再探一块然后守到底，或者现在就守到底。它不往后多想一步，所以下文称它为一步规则。

左边第一项是"找到更好的块能享受 $\ell-1$ 轮"；第二项 $E[X] - y$ 是"探索这一轮拿随机块，比守着最好块少拿多少"，$y$ 通常高于平均值 $E[X]$，所以它通常是负数，写在左边等于从收益里扣掉；右边是换块费和回程费。

规则 (1) 需要的全部信息只有三个量：$g(y)$、$E[X]$、$P(X < y)$。它们由本图分布决定，本图分布由公布的家族和待估的参数决定。模型的全部工作就是从已挖的 $n$ 个样本估这三个量。

三个量里，$P(X < y)$ 不需要知道分布。把每块产出换成它在本图分布里的百分位（产出低于它的块占多少），任何分布的样本在百分位轴上都是 0 到 1 之间均匀散布的点，手里最好的块是最右边的那个点（图 7）。$m$ 个均匀点里最右边那个的百分位平均是 $m/(m+1)$（理由与 2.1 图 2 前的圆环论证相同），所以 $P(X < y)$ 的估计只和见过几块有关，与分布无关；纪录之后失败过几次也不改变它，因为最右边的点不知道自己是第几个来的。第 3 节的边际收益停止用 $1/(n+1)$ 当刷新概率，正是这个道理。需要分布的是 $g(y)$：百分位轴上最右边那 $1/(m+1)$ 一小段，换回产出轴有多长，均匀分布是 1 分左右，幂律可能是几百分（表 1）。这一段的长度就是尾巴，只能从分布算。第 7.7 节把两者拆开验证：概率改用 $m/(m+1)$ 只损失 0.5 个点，幅度改用正态假设损失 6 个点。所以估计的重点在 $g(y)$，下一节按家族做。

4.2 各家族的估计

分布家族在每局开始时公布，需要估计的只是家族内的几个参数，比如均匀分布的上界 $S$。样本给参数提供的信息叫似然：假设参数是某个值，出现手头这批样本的概率有多大。看样本之前对参数各种取值的估计叫先验，看过样本之后的估计叫后验，后验 = 先验 × 似然再归一化（归一化：乘一个常数，让参数所有取值的后验概率加起来等于 1），这就是贝叶斯方法。多数家族用样本直接算出一个参数值（拟合：用样本把家族里的参数定下来）就够了；均匀的上界和两堆的金块比例这两个参数不能这么做，因为样本里可能根本没有它们的直接证据（没有样本恰好落在上界上，没见过一块金块），直接算会得到"上界就是已见最大值"或"金块比例为零"，规则会因此停得太早。对这两个参数我们保留后验里的全部可能取值，把 $g(y)$ 按后验加权平均。

表 6：各家族的估计方法。生成规则一列的记号：$S$ 是尺度参数；$U(a,b)$ 是 $a$ 到 $b$ 之间的均匀随机数，$U$ 单独出现指 $U(0,1)$；$Z$ 是标准正态随机数（平均 0、标准差 1）；$\kappa$ 是正态的形状参数（产出的标准差占尺度的比例）；$\sigma$ 是对数正态在对数尺度上的标准差；$\alpha$ 是幂律指数；两堆分布里每块以概率 $p$ 是金块（产出 $S \times \text{mul} \times U(0.8,1.2)$，mul 是金块倍数），否则是普通块。$g(y)$ 一列：$\mu, \sigma$ 是估出的均值和标准差，$z = (y-\mu)/\sigma$，$\varphi, \Phi$ 是标准正态的密度函数与分布函数（密度函数 $\varphi(z)$：连续取值的量落在 $z$ 附近的概率高低，画出来是钟形曲线；分布函数 $\Phi(z)$：标准正态随机数不超过 $z$ 的概率），$m$ 是样本最大值，$n$ 是样本数，$Q$ 是截断点（见下）。极大似然：取让似然最大的那个参数值；"向先验中点收缩"：样本少时把它往参数范围的中点拉近一些。正态一行的"标准差乘 $\sqrt{1+1/n}$"是把"均值本身也估不准"算进去。

均匀分布的上界。插入估计（先用样本算出一个参数值，再把它当真值代进公式）$\hat S = m(n+1)/n$（$\hat S$ 上的帽子表示"估计值"；均匀分布上 $n$ 个样本的最大值平均落在 $S$ 的 $n/(n+1)$ 处，所以用 $m$ 除以 $n/(n+1)$ 估 $S$）有一个结构性问题：$y$ 本身就是样本最大值，估出的上界永远紧贴 $y$，$g(y)$ 永远接近 0，规则会过早停止。改用贝叶斯：取先验 $\propto 1/S$（$\propto$ 读作"成正比"，只差一个常数倍）。似然这样算：上界为 $S$ 时，每个样本落在 $[0, S]$ 里任一位置的密度是 $1/S$，$n$ 个样本一起是 $(1/S)^n$，且 $S$ 必须不小于样本最大值 $m$，否则 $m$ 不可能出现。先验乘似然，后验 $\propto S^{-(n+1)}$（$S \ge m$）。再算上界为 $S$ 时超过 $m$ 的期望，用引理 1 前的"概率 × 幅度"：新块超过 $m$ 的概率是 $(S-m)/S$，超过时平均超 $(S-m)/2$，相乘得 $(S-m)^2/(2S)$。把它按后验对 $S$ 加权平均得

其中 $\int$ 是积分，即对连续取值的加权求和；$n\,m^n$ 是归一化常数，让 $S^{-(n+1)}$ 从 $m$ 到无穷加起来等于 1。积分过程略去，结果为 $m/(n^2-1)$。它是插入估计 $m / (2n(n+1))$（把 $\hat S$ 代进 $(S-m)^2/(2S)$）的约两倍（$n = 15$ 时 $1/224$ 对 $1/480$，2.1 倍）。$E[X]$ 和 $P(X < m)$ 也按同一后验加权平均，得 $E[X] = \frac{n}{n-1}\cdot\frac{m}{2}$，$P(X < m) = \frac{n}{n+1}$。

两堆分布的金块比例。$p$ 的先验均匀在 $[0.02, 0.08]$（生成器的范围），见到 $k$ 块金块后按似然 $p^k(1-p)^{n-k}$ 更新（$n$ 块里 $k$ 块是金块、$n-k$ 块不是，各块独立，概率相乘），在 30 点网格（把 $[0.02, 0.08]$ 等分成 30 个点，只在这些点上算）上取后验均值。没见过金块时先验均值 5% 会被往下拉，因为"连续 $n$ 块都不是金块"在 $p$ 小时更可能发生：$n = 10$ 时后验均值 4.7%，$n = 30$ 时 4.1%，不为 0，这使模型在两堆分布上坚持探索直到找到金块。

重尾家族的截断。参数化的对数正态和幂律尾巴无限长，但地图只有 $N = 300$ 块。$g(y)$ 的积分上限取分位点 $Q = F^{-1}(1 - \frac{1}{2N})$（分位点 $F^{-1}(q)$：使"产出不超过它"的概率恰为 $q$ 的那个数），即"全图预期只有半块能超过"的位置。不截断时幂律地图会探到 170 多块。

Beta 的模型平均。模型平均指不选定一组参数，而是把所有候选参数各算一次，再按似然加权。在 $(a, b)$ 网格与尺度倍数 $S / m \in [1.02, 2.2]$ 上算每组参数的似然，按似然加权平均 $g(y)$，而不是取似然最大的一组。样本少时似然最大的一组总是上界紧贴 $m$ 的那组，会把上界可能更高的情况丢掉。

4.3 小样本尾巴偏差与校正

用同一批样本拟合分布，再用它估"超过这批样本最大值"的期望，存在系统性低估：拟合出来的分布已经把样本最大值当成"这个分布里正常会出现的最大的那一档"，从这个分布看，再高的块就显得很少见，尾巴显得很薄。我们直接测量这个偏差：每家族 80 张图，随机挖 $n$ 块，比较模型估计的 $g(y)$ 与用剩下的块直接算的真实值。表 7 的"估计均值 / 真实均值"是对 80 张图分别平均；"估 / 真（中位数）"是先对每张图算一个比值，再取 80 个比值的中位数；"判断一致"是把估计值和真实值分别代入规则 (1)（剩 150 轮），得出的"该继续 / 该停"是否相同的比例。低估的幅度见均值那两列：Beta 估 0.30、真 0.63，估的只有真的一半；逐图比值的中位数（0.87）和均值比对不上，是因为逐图比值分布很偏，有的图真实值接近 0。

表 7：校正前的估计质量，来自 tournament/strategies/diag-excess.js。均匀分布的中位数比值偏大是因为真实值常为 0（已见最大值就是全图最高），均值上两者一致。

校正方法：对每个家族和样本数 $n \in \{6, 8, 10, 15, 20, 30, 50, 80\}$，用 150 张图测"真实 ÷ 估计"的倍数（两者各自对图取平均后相除，与表 7 的均值口径相同，但地图是另一批，所以 Beta 在 $n = 15$ 测得 2.8 而表 7 的均值比是 2.1），做成表，按 $n$ 线性插值（$n$ 落在两个表格点之间时，按距离比例取两个表值之间的数）后乘到 $g(y)$ 上。仿真测得的校正表（平滑后）：Beta 从 $n = 6$ 时 6.0 递减到 $n = 15$ 时 2.8、$n \ge 50$ 时 1.5；对数正态 1.5 到 1.9；幂律 2.5 到 3.0；两堆、均匀、正态在 0.8 到 1.2 之间。按这张表校正后，Beta 的平均探索块数从 14 升到 32。最终版本里，两个家族的表按锦标赛积分改过，改前改后的成绩按同一种方式计分：对阵四个陪跑模型（第 6 节的阵容），在另一批 300 张地图上（这批地图选参数时没用过，专门用来核对改动是否真的有效），每张地图的积分（按第 5.2 节的名次计分，每张地图满分 10 分）。这批地图与第 6 节表 8 的 7.75 分不是同一批，数字只在各自的改前、改后之间比较。Beta 原按仿真测得 6.0 到 1.5 递减，后改为恒定 1.5，每张地图的积分 6.82 升到 7.09；幂律的表整体乘 0.5，变为 1.25 到 1.5（按名次计分时追小概率巨块不划算），每张地图的积分 6.71 升到 6.92。对数正态、两堆、均匀、正态仍用仿真表。这两组数字来自 tournament/strategies/tune-beta.js 与 tune-family.js。

4.4 实现

基础版里样本集只在探索时变化，守着的轮次 $n$ 不变，拟合结果缓存（存起来，下次直接用，不重算）在 state.memory 里，一局最多重算 $n$ 次。Beta 的模型平均是最重的一步（约 300 组参数各 120 点积分），一局总耗时在 10 毫秒量级。完整源码 tournament/strategies/bayes-basic.js，245 行。

程序有四组按家族设置的参数，它们各自作用在规则 (1) 的一个位置。表 8、表 9 用的是以下最终值：

• 起步样本数（MIN_SAMPLE）：样本数 $n$ 不到它时不算规则 (1)，直接探；均匀、正态、Beta、两堆 10，对数正态 15，幂律 25。
• 校正倍数（CAL）：4.3 的校正表，乘在左边的 $g(y)$ 上。
• 代价系数（COST_MULT）：乘在右边的 $c(1 + P(X < y))$ 上，大于 1 更早停手；均匀、Beta、两堆 1.0，正态、幂律 0.5，对数正态 1.5。
• 探索上限（MAX_EXPLORE）：$n$ 达到它时不论规则 (1) 怎么算都停；六个家族都不设上限。

每个家族用哪条规则是可以替换的：程序按家族选择规则，用哪条由实验结果决定。最终版本均匀家族用第 3 节的边际收益停止规则，其余家族用规则 (1)（均匀分布上界之外没有尾巴，规则 (1) 对上界的不确定性让它多探几块，多数图上多付了费用；按 4.3 的计分方式，即对阵四个陪跑模型、另一批 300 张地图，改用边际收益规则后每张地图的积分 6.28 升到 6.56，总分不变，来自 tournament/strategies/portfolio-points.js）。

5. 环境、榜单与计分

5.1 地图生成

• 尺度 $S$ 在 40 到 400 之间对数均匀抽取（对数均匀：$S$ 的对数在两端之间均匀抽，效果是 40 到 80、80 到 160、160 到 320 这几段各占相同的概率，小尺度不会被大尺度淹没）。
• 家族从六种中等概率挑一种；形状参数在各自范围内均匀抽：正态 $\kappa \in [0.15, 0.35]$，Beta $a \in [1.2, 2.5]$、$b \in [4, 10]$，对数正态 $\sigma \in [0.5, 1.3]$，幂律 $\alpha \in [1.3, 3]$，两堆金块比例 $p \in [0.02, 0.08]$、倍数 $\in [3, 6]$。记号同表 6。
• 换块费用 $c = $ 本图产出中位数 $\times$ 一个在 $[0.05, 0.6]$ 上对数均匀的比例。这个比例是随机的，所以玩家从 $c$ 只能把中位数定位在 $c/0.6$ 到 $c/0.05$ 之间，即 $1.7c$ 到 $20c$，相差 12 倍：挖到一块低于 $1.7c$ 的可以肯定它在下半区，高于 $20c$ 的可以肯定在上半区，但仅凭 $c$ 推不准尺度。挖三五块之后样本给出的尺度信息就比这个区间窄得多，所以本文的策略不用 $c$ 估尺度，只把它当费用。若比例固定，$c$ 就直接等于尺度的倍数，策略可以不挖就知道产出大约多大。
• 基础版公布家族（策略通过 state.dist 读取），不公布尺度与形状参数。

5.2 榜单与计分

• 公开分站 20 个，种子 50001 到 50020，任何人打开榜单页时在本地浏览器里把所有提交的代码跑一遍，现场排名。
• 正式成绩由老师在隐藏种子上重跑。每站按总分排名，前五名得 10 / 7 / 5 / 3 / 1 分；总分相同并列同名次同积分。总积分相同依次比冠军、亚军、季军数，再比平均占上限比例。
• 提交时先在公开分站测试：编译失败、10 秒跑不完、任何一站抛异常的不收。正式运行中抛异常或超时的那一站记 0 分，Worker 被终止，不影响其他人。
• 昵称先到先得，与提交设备的身份码绑定，防止冒名。

5.3 回测方法

本文的主结果（表 8、表 9）都在同一批 300 张随机家族地图上比较：种子为 $300000 + 29i$，$i = 0, \dots, 299$，每张图的家族从六种里随机抽一种，各家族张数见表 8。每张图上跑完所有策略，记录总分占上限的比例；比较两个策略时用逐图的差，而不是各自的平均。图 8 说明原因：地图本身的难易主导了得分，主模型与固定 $K = 40$ 的逐图得分几乎在一条直线上（相关系数 0.90），两者各自的标准差都是 23 个百分点，而逐图之差的标准差只有 10；平均值的标准误 1.3，逐图之差的标准误 0.59。不在同一批图上跑的两个数，差 1 到 2 个点分不出高低；同一批图上逐图相减，差 1 个点就已经显著。锦标赛计分同样逐图进行：主模型与四个陪跑模型在同一张图上排名次，前五名得 10 / 7 / 5 / 3 / 1 分，图 9 是名次的分布。

6. 结果

表 8：主结果。所有策略跑同一批 300 张随机家族地图（各家族张数：Beta 42、对数正态 43、幂律 52、两堆 46、均匀 53、正态 64），数值是总分占上限的平均；"全部"列附标准误（标准差 ÷ √300，单位百分点），各家族列样本较少，标准误约为全部列的 2 到 3 倍。分布预测模型用最终版本的参数（第 4.4 节）。来自 tournament/strategies/eval-final.js。

主模型在六个家族上全部高于同一批地图上的先探后守 $K=40$：两堆 +12.0（74.8 − 62.8）、均匀 +4.4、幂律 +3.1 个百分点，其余三个家族 +1 到 +2；与分布全知的动态规划相差 2.9 个点（标准误 1.3）。平均探索块数 32，动态规划 36，说明提升来自"每张图上何时停"，不是探索总量。

按比赛的计分方式，对阵四个陪跑模型（第 3 节的阈值停止、边际收益停止、1/e 法则，加上固定探 30 块的先探后守 $K=30$；第 3 节五个里的 ε-greedy 和 UCB 在表 4 随机家族总分最低，不列入），同一批 300 张地图上主模型平均每张地图 7.75 分（标准误 0.16），平均名次 1.90，54% 的分站第一。作为参照，五个策略里随机排名的策略每个名次各占 $1/5$，期望积分 $(10+7+5+3+1)/5 = 5.2$ 分。在 20 个公开分站上复现，主模型平均 70.7%，动态规划 72.3%。

逐图看（图 8、图 9）有三点在平均数里看不到。第一，优势集中在两个家族：两堆有 96% 的图主模型高于固定 $K = 40$，均匀 87%，其余四个家族只有 64% 到 76%。第二，输掉的图有固定模式：落后最多的 8 张里 3 张是幂律，主模型探了 150 块以上，是把尾巴估厚了；2 张是 Beta，主模型只探了 10 块和 31 块就停，是把尾巴估薄了。两种都是估参数的失误，方向相反。第三，优势不随换块费变化：费用比例从 0.05 到 0.6 分四档，主模型领先固定 $K$ 3.6 到 4.3 个点，探索块数从 36 降到 29，说明规则 (1) 按费用调整了探索量。名次上，两堆和均匀 75% 以上第一，对数正态只有 37% 第一、28% 在第四第五，重尾家族的名次波动最大。

7. 敏感性分析

7.1 探索轮数

先探后守的 $K$ 从 30 到 55，六家族平均都在 65.0% 到 65.8% 之间；$K = 20$ 是 63.3%，$K = 60$ 是 64.3%，$K = 100$ 是 55.8%。峰顶平坦的原因是多探一轮的代价很小：总分约等于 $T$ 轮乘最好块的产出，多探一轮至多损失一轮的最好块产出加一次换块费，大约是总分的 $1/T = 0.5\%$；而少探的代价取决于尾巴，重尾家族少探几轮可能错过一块产出翻倍的块。结论对 $K$ 的选择不敏感，但对"轮数远少于块数"这一设定敏感（见 7.4）。

7.2 校正强度与代价系数

表 9：主模型的变体，与表 8 同一批 300 张随机地图，对阵表 8 里的四个陪跑模型（阈值停止、边际收益停止、先探后守 $K=30$、1/e 法则）。代价系数、探索上限、起步样本数的含义见第 4.4 节。来自 tournament/strategies/eval-final.js。

校正表减半损失 1.0 个点，每张地图的积分少 0.17；加大代价系数或限制探索上限的各种"更保守"设置，总分与积分都不高于最终版本，第一名比例也都更低。起步样本数 Beta 改为 15 与最终版本几乎相同（70.3 对 70.4，7.72 对 7.75）。所有变体与最终版本的总分差都在 1.6 个点以内，与标准误 1.3 同量级；积分上只有探索上限 25 / 40 明显更低（7.36 对 7.75，标准误 0.17）。主模型对这些参数不敏感。

7.3 家族是否公布

家族不公布时，主模型没有家族可以拟合，退化为第 3 节的边际收益规则：刷新概率用 $1/(n+1)$，刷新幅度用第一名减第二名。另一条路是先猜家族：用 25 个样本猜家族的分类器（输入样本、输出"属于哪个家族"的程序）准确率只有 23% 到 74%（两堆分布有 77% 被认错），猜错一次两堆分布上损失十几个点；而猜对家族能换来的好处有限：家族只用来选探索轮数时，表 2 里各家族在自己的 $K^*$ 上的得分平均为 67.6%，比固定 $K = 40$ 的 65.8% 只高 1.8 个点（主模型比固定 $K$ 高 3.8 个点，多出的部分来自用样本判断每张图的尾巴，前提也是家族正确）。因此不公布家族时固定 $K = 40$ 是理性选择，公布家族才使自适应策略有意义。这是本题设计上最重要的设定。

7.4 轮数与块数之比

表 10：块数固定 300，改变轮数，每格 20 图，来自 data/node-farm-eval-horizon.js。"探完所有块再守"在 $T = 200$ 时 300 块探不完，200 轮全部在换新块，从没守过，所以只有 20.3%。"保留值（拟合分布，不封顶）"是另一个策略，也是一步规则：不管公布的家族是什么，一律把已见样本拟合成对数正态分布，用它算"再探一块能超过当前最好多少"的期望 $g(y)$，乘剩余轮数与代价比；不做 4.2 的截断，也不设探索上限。$K = 50$ 这一行的 62.9% 与表 4 的 65.7% 是另一批地图。

轮数远多于块数时探索几乎免费，"探完再选"接近最优，任何停止规则都没有意义。$T = 200$、$N = 300$ 是探索与利用真正冲突的区间，题目的全部难度来自这个比例。

7.5 按家族切换到最佳基线

家族公布后，一个自然的替代方案是"每个家族换成该家族上表现最好的模型"。在 300 张地图上按家族选最佳（Beta、对数正态、幂律、两堆四种选中分布预测模型，均匀选先探后守 $K=20$，正态选先探后守 $K=30$），再在另外 300 张地图上验证：

表 11：来自 tournament/strategies/portfolio.js，选参数的一批与验证的一批各 300 图。

切换没有带来提升。同一批地图上比较，分布预测模型在均匀和正态上反而比"最佳基线"高 0.2 到 0.3 个点（表 11：均匀 89.7 对 89.4，正态 83.2 对 83.0），在选参数那批地图上的"最佳基线"到验证那批地图上就不再最佳。第 3 节各表中基线在某些家族上"更高"的数字来自不同批次的地图，不能跨表比较。

7.6 分布家族的组成

表 2 显示 $K^*$ 从均匀的 20 到幂律的 70。六家族等权混合下固定 $K = 40$ 离各家族最优都不远，若比赛只用重尾家族，固定 $K$ 应上调到 55 到 70，主模型则不需要改动，它按公布的家族自动调整。

7.7 概率与幅度拆开验证

规则 (1) 的收益项是"超过纪录的概率 × 超过时的平均幅度"。按 4.1 末尾的百分位论证，概率可以不用分布、只数点：$1/(m+1)$；幅度必须知道分布。把两半分别替换，在与表 8 同一批 300 张地图上比较（表 12）。概率换成 $1/(m+1)$、幅度仍按家族拟合，只比主模型低 0.5 个点，与逐图之差的标准误 0.4 同量级，说明概率这一半用分位数就够了。幅度改用正态假设（样本均值和标准差算超出量）在正态上与主模型持平，均匀低 1.8，但对数正态低 8.7、幂律低 10.1、两堆低 13.7：正态假设把重尾的超出量估得太小，早停十几个点，与阈值停止的失败模式相同。

表 12：概率与幅度分别替换后的成绩，与表 8 同一批 300 张随机地图；"比主模型低"是逐图相减的平均及其标准误。来自 tournament/strategies/eval-quantile.js。

8. 局限与改进方向

• 估参数的代价。主模型与分布全知的动态规划差 4.6 个点。图 10 把中间两步补上：家族和参数都用真值（直接把生成地图时抽到的参数交给规则 (1)，跳过估计）时一步规则得 72.4%，比主模型高 3.5 个点，这是估参数的代价；直接用全图 300 块的真实分布时得 74.6%，再高 2.2 个点，这是参数族和尾巴截断带来的近似代价。它比动态规划的 73.5% 还高 1.1 个点：一步规则本身没有损失，第 2.3 节的动态规划按"总要回去"记账，反而略保守。估参数最难的是均匀的上界（只能从最大值推）和 Beta 的形状参数。
• 期望目标与名次目标。动态规划最大化期望总分，在幂律地图上平均探 83 块去找极端金块（与表 3 同一批的 60 张幂律地图，用第 2.3 节的动态规划测得；六家族平均是 34 块），按每站名次计分时常常输给探 30 块就停的策略。主模型继承了这一点。按名次优化需要知道对手阵容。第 4.4 节按家族分别调整的代价系数、起步样本数和校正表，对阵四个陪跑模型时把每张地图的积分从 7.71 提高到 7.93（另一批 300 张随机地图，tournament/strategies/tune-family.js）；对阵真实学生阵容时应重新调整。
• 校正表的适用范围。校正倍数是对生成器的参数范围仿真得到的，改变参数范围需要重新校正。
• 加强版。产出有波动时"挖一次即已知"不再成立，样本均值的可信度与挖过次数有关，规则 (1) 需要把估计误差纳入。这一部分留待单独处理。

参考文献

1. Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5), 527–535.
2. Weitzman, M. L. (1979). Optimal search for the best alternative. Econometrica, 47(3), 641–654.
3. Ferguson, T. S. (1989). Who solved the secretary problem? Statistical Science, 4(3), 282–289.
4. Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47, 235–256.
5. Lattimore, T., & Szepesvári, C. (2020). Bandit Algorithms. Cambridge University Press.