论文里经常会突然出现一个复杂公式：作者先给定义，再解释每一项负责什么。每个符号似乎都能看懂，但合在一起仍然会让人困惑：他们当初为什么会想到把公式写成这样？

SimpleTES 的历史选择算法 RPUCG 就是一个典型例子：

$$\mathrm{RPUCG}(i) =U_i+\lambda\rho_i\frac{\sqrt{1+\lvert S\rvert}}{1+n_i}.$$

第一次看到它时，我们可以逐项查定义，却很难建立直觉。本文换一种方式：先不背公式，而是假装它还没有被发明。我们从最普通的 multi-armed bandit 开始，每次只引入一个新的失败模式，依次构造 UCB、UCT、PUCT，最后重新得到 RPUCG。

这并不是对作者真实思考过程的历史还原。论文没有公开实验室日志，我们无法知道作者当时究竟按什么顺序思考。本文做的是一条教学性重构：如果面对同样的问题，怎样用最少的跳步长出同一种公式。

先看论文原式：RPUCG 到底在解决什么问题

SimpleTES 会让 LLM 反复生成候选方案，用 evaluator 打分，再把有价值的历史方案放进下一轮 prompt。随着搜索进行，历史集合 $S$ 会越来越大，而 context window 有限，不可能把所有历史都塞给模型。

因此，系统需要一个 selector 回答：下一轮 prompt 应该引用哪些历史节点？

论文先定义节点 $i$ 的 propagated value：

$$\boxed{ U_i=\max\left(r_i,\gamma\max_{j\in Ch(i)}U_j\right) } \tag{1}$$

其中：

  • $r_i$ 是节点 $i$ 自己的 evaluator score；
  • $Ch(i)$ 是所有受节点 $i$ 启发而产生的 child nodes；
  • $\gamma\in(0,1]$ 是向祖先传播时的折扣。

然后，论文用下面的分数选择历史节点：

$$\boxed{ \mathrm{RPUCG}(i) =U_i+\lambda\rho_i\frac{\sqrt{1+\lvert S\rvert}}{1+n_i} } \tag{2}$$

其中 $\rho_i$ 是节点原始分数在当前历史中的 percentile prior，$n_i$ 是它此前被放入 proposal context 的次数，$\lambda$ 控制 exploration 强度。选出一个节点后，算法还会排除它的一跳 parent 和 children，再继续选择，以免 prompt 里全是同一家族的近亲方案。

论文把 RPUCG 称为 PUCT 的 “graph-based extension”，并解释一个历史经验可能因为自己分数高而有价值，也可能因为它曾经 “has led to strong descendants”。原文与公式见 SimpleTES v2, pp.31–32。

公式写得很紧凑，但它留下了真正的问题：为什么是价值加 bonus？为什么 bonus 的分母是 $1+n_i$，分子又要放 $\rho_i\sqrt{1+\lvert S\rvert}$？要回答这些问题，我们先退回到 UCB。

第一步：从标准 Bandit 构造 UCB

假设桌上有几台老虎机。每台机器 $i$ 的真实平均收益 $\mu_i$ 固定但未知，每次拉动只看到一个随机 reward。到第 $t$ 轮，我们只知道：

  • $n_i(t)$：机器 $i$ 已经被选择多少次；
  • $\hat\mu_i(t)$：机器 $i$ 的经验平均收益。

如果总选 $\hat\mu_i$ 最大的机器，一次偶然的高分就可能让系统永远忽略真正更好的机器。因此，选择分数至少需要两部分：

$$\text{score} =\text{目前看起来有多好} +\text{还可能被低估多少}.$$

前一项对应 exploitation，后一项对应 exploration。

第一项最自然就是 $\hat\mu_i$。第二项需要满足三条直觉：

  1. $n_i$ 越大，我们越确定，bonus 应越小；
  2. 总轮数 $t$ 越大，长期没被检查的 arm 越值得重新检查；
  3. 样本均值的典型误差按 $1/\sqrt{n_i}$ 缩小。

所以 bonus 大致应当长成：

$$\mathrm{bonus}_i(t) \propto\sqrt{\frac{\text{随总轮数缓慢增长的量}}{n_i(t)}}.$$

从 Hoeffding inequality 得到置信半径

若 reward 独立且位于 $[0,1]$，Hoeffding inequality 给出：

$$\Pr\left(\mu_i>\hat\mu_i+\epsilon\right) \leq\exp(-2n_i\epsilon^2).$$

令失败概率为 $t^{-4}$：

$$\exp(-2n_i\epsilon^2)=t^{-4}.$$

两边取对数并解出 $\epsilon$：

$$-2n_i\epsilon^2=-4\ln t,$$

$$\epsilon^2=\frac{2\ln t}{n_i},$$

$$\epsilon=\sqrt{\frac{2\ln t}{n_i}}.$$

于是我们得到真实均值的 optimistic upper bound：

$$\mu_i\lesssim\hat\mu_i+\sqrt{\frac{2\ln t}{n_i}}.$$

UCB1 因而选择：

$$\boxed{ i_t=\arg\max_i\left[ \hat\mu_i(t)+\sqrt{\frac{2\ln t}{n_i(t)}} \right] } \tag{3}$$

这就是 Upper Confidence Bound 的名字来源：系统不按当前均值排序，而按“在现有证据下，它乐观地可能有多好”排序。不同 UCB 变体会改变常数和置信项，但核心结构不变：

$$\boxed{\text{UCB}=\text{经验价值}+\text{不确定性 bonus}}$$

原始算法与 regret 分析可参考 Auer et al., 2002。实际运行时，通常先让每个 arm 至少被选一次，避免 $n_i=0$。

一个数字例子

假设 $t=100$：

Arm $\hat\mu_i$ $n_i$ UCB1 score
A 0.70 50 $0.70+\sqrt{2\ln100/50}\approx1.13$
B 0.62 5 $0.62+\sqrt{2\ln100/5}\approx1.98$

B 当前均值更低，但只试过 5 次，不确定性很大，所以系统会再给它机会。UCB score 超过 1 并不矛盾：它是用于选择的乐观指数，不是下一次 reward 的预测值。

第二步：从 UCB 到 UCT——把每个树节点看成局部 Bandit

普通 bandit 的 arms 是固定的。Tree search 中，每走一步都会进入新状态，新状态下面又出现一批新 action。决定“从状态 $s$ 继续走哪个 child”，可以看成一个局部 bandit：

标准 Bandit 状态 $s$ 下的局部 Bandit
arm $i$ action $a$ / child
总轮数 $t$ 父节点访问次数 $N(s)$
arm 次数 $n_i$ 分支访问次数 $N(s,a)$
平均 reward $\hat\mu_i$ 分支平均回传价值 $Q(s,a)$

把这些变量代入 UCB，就得到常见的 UCT selection rule：

$$\boxed{ a^*=\arg\max_a\left[ Q(s,a)+c\sqrt{\frac{\ln N(s)}{N(s,a)}} \right] } \tag{4}$$

$c$ 控制 exploration 强度并吸收常数。UCT 的关键不是又发明了一套全新公式，而是：在树的每一个分叉点都运行一次局部 UCB。 完整的 tree-search iteration 还要选择路径、展开节点、评价节点，并沿路径回传 $Q$ 和访问次数。详见 Kocsis & Szepesvári, 2006。

到这里，推导主要是变量映射；下一步开始进入 heuristic design。

第三步：从 UCT 到 PUCT——已有 prior 时，怎样既相信又怀疑它

想象一个节点下面有 100 个合法 action，但预算只够认真搜索 10 个。我们手里还有一个不完美的 policy network，它能给出 prior $P(s,a)$，提示哪些 action 更像高手的选择。

三种策略中，第三种最合理：

  1. 完全忽略 policy：浪费已有知识；
  2. 永远服从 policy：prior 一旦错，搜索无法纠正；
  3. 让 prior 引导早期探索，再让真实 evidence 逐渐推翻它。

Prior 为什么不应作为固定价值直接相加

先试候选 A：

$$\mathrm{score}=Q(s,a)+P(s,a)+\mathrm{exploration}.$$

问题是，即使 action 已被搜索上万次，错误 prior 仍然永久加在价值上。

候选 B 更符合目标：

$$\mathrm{score}=Q(s,a)+P(s,a) B(s,a),$$

只要 $B(s,a)$ 随 evidence 增加而衰减，prior 就只负责早期导航，不会永久篡改最终价值。

自己构造 exploration bonus

被访问越多，bonus 越小，最简单的分母是：

$$B(s,a)\propto\frac{1}{1+N(s,a)}.$$

但是分子不能永远为 1。若父节点已搜索 10,000 次，而某个 prior 不低的 action 只访问过 1 次，它应该重新获得探索压力。因此分子需要随父节点的总搜索量增长，但不能增长得太快。一个常见的选择是：

$$\sqrt{N(s)}=\sqrt{\sum_bN(s,b)}.$$

再加入 exploration 系数 $c_{\mathrm{puct}}$，得到 AlphaGo Zero 风格的常见 PUCT 形式；更早的 predictor/UCB 变体在常数与具体写法上并不完全相同：

$$\boxed{ a^*=\arg\max_a\left[ Q(s,a) +c_{\mathrm{puct}}P(s,a) \frac{\sqrt{\sum_bN(s,b)}}{1+N(s,a)} \right] } \tag{5}$$

现在每一项都对应一个行为：

  • $Q$：服从真实搜索结果；
  • $P$：有限预算下，优先检查更有希望的分支；
  • $1+N(s,a)$：反复访问后降温；
  • $\sqrt{\sum_bN(s,b)}$：总搜索推进时，恢复对被忽略分支的压力；
  • $c_{\mathrm{puct}}$：控制相信 prior 的程度。

这里必须画清证据边界：PUCT 不是从 UCT 唯一代数推出的定理。 平方根、分母和 prior 的放置方式都是满足目标行为的建模选择。相关路线可参考 Rosin, 2011 与 AlphaGo Zero。

第四步：从 PUCT 构造 RPUCG

现在回到 SimpleTES。这里没有棋盘上的 action，而有一张历史方案 DAG。每轮只能选少数节点放进下一次 prompt。

我们从四个会真实发生的失败开始。

失败一：只看当前分数，会遗忘 stepping stone

最朴素的 selector 是：

$$\mathrm{value}(i)=r_i.$$

考虑一条历史：

1
2
3
A：0.55，提出一个新结构
└── B：0.60，把结构实现得更完整
    └── D：0.90，最终形成突破

A 自己分数不高，却产生了高分后代 D。只按 $r_i$ 排序，A 很快会被忘掉；但它显然包含了一个有生产力的 idea。

我们因此要求新的价值满足：保留自己的分数；强 child 给 parent 一部分信用；距离越远信用越弱；只要曾经引出一条强路线就应被记住。把这些要求填进半成品：

$$U_i=\max\left(r_i,\gamma\max_{j\in Ch(i)}U_j\right).$$

这里的三部分分别是自己的价值 $r_i$、距离折扣 $\gamma$，以及最强 child 的传播价值 $\max_{j\in Ch(i)}U_j$。

这正好得到论文公式 (1)。若 $\gamma=0.8$，前面的例子变成：

$$U_D=0.90,$$

$$U_B=\max(0.60,0.8\times0.90)=0.72,$$

$$U_A=\max(0.55,0.8\times0.72)=0.576.$$

选择 max 而不是 children 的平均值，并非数学上唯一正确。它表达的是这个 discovery objective 的偏好：保留“曾经产生过突破”的信号，不让大量失败后代把它平均掉。

失败二：只看 $U_i$，赢家会垄断 prompt

如果每轮都选 $U_i$ 最大的节点，同一个成功节点会反复进入 context，搜索逐渐围绕单一路线局部微调。

于是 Bandit 的老问题再次出现：

$$\mathrm{selection\ score}=U_i+\mathrm{exploration\ bonus}.$$

令 $n_i$ 表示节点 $i$ 以前被放入 proposal context 的次数。沿用 PUCT 的思路，被用得越多，bonus 越小：

$$\mathrm{bonus}(i)\propto\frac{1}{1+n_i}.$$

失败三：所有冷门节点并不都值得探索

两个节点可能都从未进入 prompt，但一个处于历史前 10%，另一个连程序都跑不起来。如果 bonus 只看 $n_i$，系统会平等探索两者，浪费大量预算。

因此还需要一个 prior-like gate。直接使用 raw score 会受不同任务量纲影响，更稳妥的做法是把分数转换为当前集合中的 percentile：

$$\rho_i=\text{节点 }i\text{ 的 score percentile}.$$

它不直接加进价值，而只调节 exploration：

$$\mathrm{score}(i)=U_i+\rho_i\frac{?}{1+n_i}.$$

失败四：历史扩大后，旧节点可能永久沉底

搜索初期也许只有 10 个历史节点，后来却有 1,000 个。如果探索压力不随历史规模增加，一个早期只被用过一两次的节点可能永远被新节点淹没。

PUCT 在固定 parent 下用总访问量衡量搜索进度；RPUCG 从整个历史集合 $S$ 中选节点，因此最直接的全局进度是 $\lvert S\rvert$。沿用缓慢增长的平方根形式：

$$\sqrt{1+\lvert S\rvert}.$$

把它代回半成品，再加入 exploration 系数 $\lambda$：

$$\boxed{ \mathrm{RPUCG}(i) =U_i+\lambda\rho_i\frac{\sqrt{1+\lvert S\rvert}}{1+n_i} }$$

我们终于重新得到了论文公式，而且每个部件都对应一个此前出现的失败：

失败模式 公式中的修正
只看当前分数会忘记 stepping stone $U_i$ 传播最强后代价值
成功节点反复垄断 prompt $1/(1+n_i)$ 让用得多的节点降温
所有冷门节点被同等探索 $\rho_i$ 优先“冷门但有希望”的节点
历史扩大后旧节点永久沉底 $\sqrt{1+\lvert S\rvert}$ 恢复探索压力
不同任务需要不同探索强度 $\lambda$ 提供调节旋钮

还有一个公式外的失败：贪心取前五名可能得到 A、A1、A2、A3、A4，全是同一家族的近亲。论文因此在选中一个节点后排除它的一跳邻居，再选下一个，减少 context redundancy。

四条公式之间，哪些是推导，哪些是设计

把整条路线压缩成一张图：

1
2
3
4
5
6
7
8
9
10
11
12
13
Hoeffding inequality
        │ 选择失败概率，代数解出 confidence radius
        ▼
UCB = empirical value + uncertainty bonus
        │ 在树的每个节点建立局部 bandit，替换变量
        ▼
UCT = branch value + visit-count exploration
        │ 加入 policy prior，重新设计 bonus
        ▼
PUCT = branch value + prior-weighted exploration
        │ 将棋树统计量改写为历史方案 DAG 的统计量
        ▼
RPUCG = propagated value + percentile-prior × context-use exploration

其中只有第一段包含明确的 concentration-bound 推导；UCB 到 UCT 主要是局部 bandit 的变量映射；UCT 到 PUCT、PUCT 到 RPUCG 则包含越来越多的目标选择与 heuristic design。

这一区分很重要。若把所有步骤都写成“因此必然得到”，读者虽然看到了连贯的代数，却会误以为 RPUCG 是唯一正确答案。事实并非如此：descendant credit 也可以取平均或由 value model 学习；global progress 也可以不用 $\lvert S\rvert$；prior 也可以来自 uncertainty、semantic novelty 或 learned policy。论文提出的是一个合理、可实验检验的设计，而不是一条数学定理。

为什么这种解读一下子变清楚了

回头看，真正降低理解门槛的并不是“解释得更口语”，而是改变了信息出现的顺序。

1. 从失败模式正向构造，而不是从成品反向注释

“$\rho_i$ 是 percentile prior”只解释了符号是什么，却没有解释它为什么存在。先展示“所有低访问节点获得相同 bonus”这个失败后，读者会自己意识到需要一个 gate；此时 $\rho_i$ 不再是额外负担，而是一个正在等待名字的空位。

2. 每一步只增加一个自由度

我们没有同时介绍 $U_i,\rho_i,n_i,\lvert S\rvert,\lambda$。每遇到一个新问题，只加入一个新量，认知负担始终停留在“旧骨架 + 一个变化”。

3. 先固定不变量，再允许公式变形

从 UCB 到 RPUCG，始终不变的是：

$$\text{selection score}=\text{value}+\text{exploration bonus}.$$

读者只需要追踪“value 在当前对象上是什么意思”“uncertainty 或 under-use 怎样衡量”，不必把四条公式当成四个互不相关的知识点。

4. 把事实、推断和教学重构分开

论文确实说 RPUCG 是 PUCT 的 graph-based extension，也明确解释了 descendant value、percentile prior 和 context-use count。至于“作者先遇到失败一，再遇到失败二”，则是我们为教学安排的顺序。标出这条边界，既保留直觉，也避免把一个讲得顺的故事误当成历史事实。

5. 让读者在答案出现前先产生预测

当文章问“被反复使用的节点应该放在分子还是分母”时，读者不是被动读答案，而是在极小的搜索空间里亲手完成一步设计。公式因此从外部信息变成了自己刚刚做出的选择。

遮住答案，再重构一次

试着回答下面六个问题：

  1. 如果只做 exploitation，历史节点的价值至少应包含什么？
  2. 为什么只看 $r_i$ 会漏掉关键 stepping stone？
  3. 哪个量应该让“很少进入 prompt”的节点得到更高 bonus？它应在分子还是分母？
  4. 哪个量可以充当 prior，避免盲目探索所有低分节点？
  5. 历史越来越大时，怎样让长期被忽略的节点重新获得探索压力？
  6. 对照 SimpleTES v2 pp.31–32：哪些内容是论文明确写出的公式或解释，哪些只是本文为了教学安排的“失败一到失败四”发现顺序？
参考答案

答案依次是：propagated value $U_i$；向祖先传播 descendant value；把 context-use count $n_i$ 放在分母；使用 percentile prior $\rho_i$；在分子加入随 $\lvert S\rvert$ 缓慢增长的 $\sqrt{1+\lvert S\rvert}$。最后用 $\lambda$ 调节 exploration 强度。

因此可以重新写出：

$$U_i+\lambda\rho_i\frac{\sqrt{1+\lvert S\rvert}}{1+n_i}.$$

原文明确给出 propagated value、RPUCG 公式、各变量含义、exploration term 和一跳邻居排除规则；“先遇到 stepping stone 被遗忘，再遇到赢家垄断”等顺序是本文的教学性重构，不能当成作者真实的发明史。

我们是怎样用 Prompt 产出这种解读的

这篇文章不是靠一句“解释这个公式”直接生成的。更有效的过程是先指出初稿的具体失败，再要求模型改变推理顺序：不要先揭晓公式；先暴露失败模式；让读者填半成品；最后区分严格推导与人为设计。

下面是一份可以复用的 Prompt。把论文原文、公式、读者背景和已有初稿一并交给模型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
你要把论文中的复杂算法公式写成一篇可独立阅读的教学文章。

目标读者：
- 知道基础概率/机器学习概念，但可能已经忘记前置公式；
- 希望理解“为什么会想到这个结构”，而不只是知道每个符号的定义。

输入：
1. 论文原文、公式编号和页码；
2. 目标公式；
3. 读者目前真正记得的前置知识；
4. 已有解释及读者看不懂的具体位置。

写作流程：
1. 先原样给出论文的目标公式与作者公开说明，附可靠来源；
2. 提出问题：这个公式为什么会长成这样？
3. 从读者仍掌握的最小起点开始；若前置公式可能忘记，就从问题定义重新推导；
4. 不要提前公布下一条公式。先给一个会失败的最小方案；
5. 展示该方案的具体失败案例，再列出新方案必须满足的行为；
6. 给出只缺一两个部件的半成品公式，让读者先预测；
7. 每一步只引入一个新变量或设计选择，并用数值例子检查方向；
8. 最后才揭晓论文公式，逐项映射到先前的失败模式；
9. 明确标注：哪些步骤是定理或代数推导，哪些是变量映射，哪些是 heuristic design；
10. 不得把教学性重构冒充作者真实、但未公开的心理过程；
11. 结尾给出一组遮住答案后可以重构公式的问题。

输出结构：
- 论文原始表述
- 它引发的问题
- 从最小前置知识开始的逐步构造
- 严格推导与设计选择的边界
- 为什么这种解释更容易理解
- 自测题与参考答案

Prompt 之外，仍需要两轮人工工作：第一轮检查“读者到底卡在哪里”，第二轮回到原论文核对公式、术语和证据边界。高质量解读往往不是一次生成，而是把读者的困惑当作新的 evidence，持续修改信息顺序。

以后怎样快速复现这种解读

可以把这次过程压缩成一个六步检查表：

  1. 钉住原文：先核对公式、符号、页码和作者明确给出的理由；
  2. 探测真实起点：不要因为读者“学过 UCB”就假设他现在能直接调用 UCB；
  3. 找到不变骨架：例如贯穿全文的 “value + exploration bonus”；
  4. 收集失败模式：每个新公式部件都必须回答一个先出现的问题；
  5. 控制揭晓顺序：失败案例 → 必要行为 → 半成品 → 候选比较 → 最终公式；
  6. 审计证据边界：分清数学推导、变量映射、设计选择与教学重构。

真正应该记住的也不是四条孤立公式，而是四次问题变形：

  • UCB：不能因早期噪声永远忽略某个 arm；
  • UCT：多步搜索中，每个树节点都有自己的 exploration–exploitation；
  • PUCT：已有 predictor 时，要让 prior 引导早期搜索，但允许 evidence 推翻它；
  • RPUCG：历史方案不是棋步，要奖励能产生强后代、当前有希望、又尚未被充分放进 prompt 的节点。

当一条复杂公式可以从这些问题中重新长出来，它才真正变成了自己的知识。

参考资料