Research note

Elimination in
Fusing Bandits

When should we stop measuring? From RAGE to witness-bottleneck elimination, efficiency comes from proving that a direction can no longer change the answer.

Daoyuan GuoSeptember 202612 min read

Experimental design asks where to measure next. Elimination asks the equally important question: what can we safely stop measuring?

1. RAGE is a loop, not just an allocation

In transductive linear best-arm identification, an arm \(z\) has value \(z^\top\theta^\star\), but the learner may collect noisy observations along a different set of probes \(\mathcal X\). The hard objects are not individual arms. They are directions such as \(z-z'\): the learner must determine the signs of their inner products with an unknown parameter.

RAGE turns this geometry into a phase-wise loop:

active arms→target directions→optimal design→estimate→eliminate

At phase \(r\), the resolution shrinks geometrically. RAGE constructs pairwise directions among the surviving arms, solves an experimental-design problem that controls the worst uncertainty over those directions, collects a batch, and removes arms that are confidently suboptimal. The next phase therefore faces a smaller statistical problem.

This last step is not housekeeping. Without elimination, every phase would continue protecting directions whose signs have already been settled. The efficiency of the design depends on the elimination rule deciding which comparisons can still affect the final answer.

RAGE-GLM carries the same architecture into transductive linear logistic bandits. Least-squares geometry is replaced by likelihood and Fisher-information geometry, together with a warm-up that makes the logistic estimator reliable. Yet the organizing principle remains phase-wise: design for unresolved directions, estimate, then eliminate.

The common core: RAGE and RAGE-GLM use different observation models and confidence machinery, but both become adaptive because an elimination rule rewrites the target set after every phase.

2. Fusion changes what “irrelevant” means

Now suppose every arm \(i\) is judged through two feedback modalities: a numerical reward parameter \(\theta_R\) and a pairwise-dueling parameter \(\theta_D\). They need not agree. Define the modality-wise gaps and fused gap by

\[\Delta_{m,i}=\max_j (x_j-x_i)^\top\theta_m,\qquad \Delta_i=\max\{\Delta_{R,i},\Delta_{D,i}\}.\]

An arm is jointly \(\varepsilon\)-optimal only if it lies within \(\varepsilon\) on both sides. Running two independent RAGE-style procedures would be correct, but it would ignore a useful fact: the two sides serve the same final classification problem. A certificate obtained on one side can make some measurements on the other side irrelevant.

\[\text{Which target--comparator directions can still change whether }\Delta_i<\varepsilon?\]

3. First compression: identify the bottleneck

Because \(\Delta_i\) is a maximum, both modality-wise gaps do not always need the same precision. Suppose the current confidence intervals certify

\[U_{D,i}^{(r)}<L_{R,i}^{(r)}.\]

Then \(\Delta_{D,i}<\Delta_{R,i}\), so reward is the bottleneck and \(\Delta_i=\Delta_{R,i}\). Further reducing dueling-side uncertainty for arm \(i\) cannot change its fused gap. The dueling procedure may stop treating \(i\) as an active target.

Let \(K_{m,r}\) contain arms already certified to be controlled by modality \(m\). The targets that modality \(m\) still needs to resolve are

\[G_{m,r}=C_r\setminus K_{\bar m,r}.\]

This is Bottleneck Elimination: compress the target side of the design. Evidence from reward can remove a target from the dueling design, and vice versa, without pretending that the modalities share one parameter.

4. Why a candidate set is not enough

A tempting implementation is to use the unresolved fused candidate set \(C_r\) as both the target set and comparator set for every comparison. That is unsafe.

Imagine an arm \(j\) that has left \(C_r\) because it is poor under reward. The same arm may still be optimal—or near-optimal—under dueling. If it also disappears from the dueling comparator set, the estimated dueling gap of a remaining candidate \(i\) becomes

\[\max_{j\in C_r}(x_j-x_i)^\top\widehat\theta_D,\]

even though the true gap maximizes over all arms. The learner may underestimate \(\Delta_{D,i}\), certify \(i\) too early, and return the wrong answer. An arm can be irrelevant as a joint output while remaining essential as a modality-wise witness. Under unaligned feedback, target status and evidential status are different roles.

5. Keep witnesses—and prune them too

For each modality \(m\in\{R,D\}\), maintain a witness set \(W_{m,r}\). A witness need not remain in the fused candidate set. It stays because it may still attain the maximum that defines a modality-wise gap.

A witness \(j\) is removed only when another witness \(k\) strictly dominates it with a valid confidence certificate:

\[(x_k-x_j)^\top\widehat\theta_{m,r}-\operatorname{CR}_{m,r}(k,j)>0.\]

The modality-wise optimum can therefore never be pruned on the good confidence event. At the same time, confidently dominated arms do not need to remain as comparators forever. After each phase, the witness set itself is compressed.

The complete direction set is

\[\mathcal Y_{m,r}=\{x_j-x_i:\ i\in G_{m,r},\ j\in W_{m,r-1},\ j\neq i\}.\]
Target side\(C_r\to G_{m,r}\)

Bottleneck elimination removes target–modality pairs that can no longer control the fused gap.

Comparator side\([K]\to W_{m,r-1}\)

Witness elimination removes arms that can no longer define a relevant modality-wise gap.

The current allocation uses the previous phase's witness set. This ordering matters: the design is fixed before observing the fresh data used to update witnesses.

6. The phase-wise guarantee

The safety of the construction can be stated in one lemma. Let \(\gamma_r\) be the phase resolution and \(\delta_r=3\delta/(\pi^2r^2)\).

Lemma — Phase-wise fused-elimination guarantee

Fix a phase \(r\). Conditioned on the history before phase \(r\), and on the validity of the logistic reference point inherited from preceding phases, with probability at least \(1-\delta_r\), the following statements hold simultaneously for \(m\in\{R,D\}\):

  1. For every \(i\in G_{m,r}\), \[\left|\widehat\Delta_{m,i}^{(r)}-\Delta_{m,i}\right|\leq\gamma_r,\qquad \widehat\Delta_{m,i}^{(r)}=\max_{j\in W_{m,r}}(x_j-x_i)^\top\widehat\theta_{m,r}.\]
  2. Every witness removed from \(W_{m,r-1}\) is strictly suboptimal under modality \(m\); in particular, \(i_m^\star\in W_{m,r}\).
  3. If \(U_{\bar m,i}^{(r)}<L_{m,i}^{(r)}\), then \(\Delta_{\bar m,i}<\Delta_{m,i}\), and therefore \(\Delta_i=\Delta_{m,i}\).

Consequently, each active target's interval contains its true modality-wise gap, and every witness or bottleneck elimination in the phase is consistent with the true gaps.

Statement 2 protects the comparator side: pruning never deletes the true modality-wise optimum. Statement 3 protects the target side: bottleneck compression occurs only after one modality is certified not to control the maximum.

Why witness elimination does not worsen the order

Compare the same targets with and without witness compression:

\[\mathcal Y_{m,r}\subseteq\mathcal Y^{\mathrm{no\text{-}wit}}_{m,r}\subseteq\mathcal Y^{\mathrm{full}}_r.\]

For \(A\subseteq B\), the reward-side design objective is monotone:

\[\min_{\nu_R}\max_{y\in A}\|y\|^2_{M_R(\nu_R)^{-1}}\leq\min_{\nu_R}\max_{y\in B}\|y\|^2_{M_R(\nu_R)^{-1}}.\]

The same relation holds for the active-direction branch of the dueling Fisher design. Witness compression therefore cannot increase the phase-wise directional design value. The additional confidence budget for witness certificates changes logarithmic factors, but introduces no new polynomial-order term into the sample-complexity upper bound. The deterministic worst-case theorem retains every arm as a possible witness, so adaptive witness gains do not make the stated bound look smaller; importantly, they do not make its order larger either.

7. What the mechanism costs—and buys

The ablation compares four fused variants. With \(Z=[K]\), their direction sets are \(C\times Z\) (no compression), \(C\times W\) (witness only), \(G\times Z\) (bottleneck only), and \(G\times W\) (full WIT-BOTELIM). Estimators, confidence schedules, stopping rules, and design machinery are held fixed.

OperationWhat it costsWhat it removesMedian query eliminationKey takeaway
No compression
C × Z		No extra pruning stateNothingBaselineSimple, but repeatedly designs for settled directions.
Witness only
C × W		Dominance certificates and a witness set for each modalityIrrelevant comparators\(\varepsilon\)-one: \(28.3\%\)
\(\varepsilon\)-all: \(31.0\%\)		Most typical savings come from comparator-side compression.
Bottleneck only
G × Z		Cross-modal gap intervals and bottleneck certificatesResolved target–modality pairs\(\varepsilon\)-one: \(0.7\%\)
\(\varepsilon\)-all: \(8.2\%\)		Small on typical one-arm paths; more useful when every arm must be classified.
Full method
G × W		Both states and moderately more learner-side optimizationTargets and comparators\(\varepsilon\)-one: \(28.5\%\)
\(\varepsilon\)-all: \(42.3\%\)		The mechanisms are complementary, especially for exact-set recovery.

Against two fully independent RAGE-style procedures, the average end-to-end gain is modest for \(\varepsilon\)-one—about \(2.7\%\) over the tested scaling grid—but reaches about \(23.8\%\) for \(\varepsilon\)-all. Exact-set recovery creates more opportunities for a certificate on one modality to simplify the other.

The late phases reveal why direction compression matters. In the representative \(60^\circ\), \(\varepsilon\)-all instance, phase 2 shrinks roughly \(1024/1024\) reward/dueling directions to \(61/31\). By phase 5, the median phase cost falls from about \(30.06\) million samples without compression to \(15.83\) million with the full rule. Since phase resolution tightens geometrically, the last unresolved directions are also the most expensive ones to keep by mistake.

The trade-off is computational state for statistical thrift.

Witness–Bottleneck Elimination maintains more structure and asks the design solver a more carefully filtered question. In return, it spends fewer reward or preference queries on directions that have already lost their ability to change the answer.

Conclusion

RAGE's enduring idea is not merely to allocate samples well. It is to repeatedly redefine the problem being allocated over. Fusing bandits makes that redefinition two-dimensional: we must decide both which candidate–modality pairs remain unresolved and which arms still matter as witnesses inside each modality.

Bottleneck elimination says, “this modality can no longer control the fused gap.” Witness elimination says, “this comparator can no longer define a modality-wise gap.” Together they turn fusion into a precise operation on the experimental-design target set.

References

← Back to Artifacts & Blogs
研究笔记

Fusing Bandits
中的 Elimination

我们应该何时停止测量？从 RAGE 到 Witness–Bottleneck Elimination，高效的关键是证明某个方向已经无法改变答案。

郭道远2026 年 9 月约 12 分钟

Experimental design 追问下一次应该测量哪里；elimination 追问一个同样重要的问题：我们可以安全地停止测量什么？

1. RAGE 的核心是一个闭环

在 transductive linear best-arm identification 中，arm \(z\) 的价值是 \(z^\top\theta^\star\)，但 learner 可以沿另一组 probes \(\mathcal X\) 收集带噪观测。真正困难的对象并不是单个 arm，而是 \(z-z'\) 这样的 direction：learner 必须判断这些方向与未知参数内积的符号。

RAGE 把这种几何结构写成 phase-wise 闭环：

active arms→target directions→optimal design→estimate→eliminate

第 \(r\) 个 phase 的分辨率按几何速度缩小。RAGE 在存活 arms 之间构造 pairwise directions，求一个控制最坏方向不确定性的 experimental design，收集一批观测，再删除已经可以确认是 suboptimal 的 arms。下一个 phase 面对的统计问题因此更小。

最后这一步不是清理工作。没有 elimination，每一轮都要继续保护那些符号早已确定的方向。Design 是否节省样本，取决于 elimination rule 能否正确判断哪些 comparisons 仍然有机会改变最终答案。

RAGE-GLM 把相同架构带入 transductive linear logistic bandits：least-squares geometry 被 likelihood 与 Fisher-information geometry 替代，并加入让 logistic estimator 可靠的 warm-up；但组织原则仍然是 phase-wise——为尚未解决的 directions 设计、估计，然后删除。

共同核心：RAGE 与 RAGE-GLM 的 observation model 和 confidence machinery 不同，但二者之所以具有自适应性，都是因为 elimination rule 会在每个 phase 后重写 target set。

2. Fusion 改变了“无关”的含义

现在让每个 arm \(i\) 接受两种 feedback：数值型 reward 对应参数 \(\theta_R\)，pairwise dueling 对应参数 \(\theta_D\)。二者不必对齐。定义 modality-wise gap 与 fused gap：

\[\Delta_{m,i}=\max_j (x_j-x_i)^\top\theta_m,\qquad \Delta_i=\max\{\Delta_{R,i},\Delta_{D,i}\}.\]

一个 arm 只有在两侧都落在 \(\varepsilon\) 内时，才是 jointly \(\varepsilon\)-optimal。运行两个独立的 RAGE-style procedures 可以保证正确，却忽略了一个可利用的事实：两侧最终服务于同一个分类问题。一侧拿到的 certificate，可能使另一侧的一些测量失去意义。

\[\text{哪些 target--comparator directions 仍然可能改变 }\Delta_i<\varepsilon\text{ 的判断？}\]

3. 第一次压缩：找出 bottleneck

由于 \(\Delta_i\) 是两个 gap 的最大值，两侧不一定需要被估到相同精度。假设当前 confidence intervals 已经证明

\[U_{D,i}^{(r)}<L_{R,i}^{(r)}.\]

那么 \(\Delta_{D,i}<\Delta_{R,i}\)，reward 是 bottleneck，且 \(\Delta_i=\Delta_{R,i}\)。继续缩小 arm \(i\) 在 dueling 侧的不确定性已经无法改变 fused gap；dueling procedure 可以不再把 \(i\) 当作 active target。

令 \(K_{m,r}\) 表示已经确认由 modality \(m\) 控制的 arms。modality \(m\) 仍需处理的 targets 为

\[G_{m,r}=C_r\setminus K_{\bar m,r}.\]

这就是 Bottleneck Elimination：压缩 design 的 target 侧。Reward 侧的证据可以删除 dueling design 中的一个 target，反之亦然；这个过程不需要假装两种 modalities 共享同一个参数。

4. 为什么 candidate set 还不够

一种看似自然的实现，是把尚未解决的 fused candidate set \(C_r\) 同时当作每个 comparison 的 target set 和 comparator set。这并不安全。

设 arm \(j\) 因为 reward 很差，已经离开 \(C_r\)；但它在 dueling 中可能仍然 optimal 或 near-optimal。如果它也从 dueling 的 comparator set 消失，那么 remaining candidate \(i\) 的 dueling gap 会被估成

\[\max_{j\in C_r}(x_j-x_i)^\top\widehat\theta_D,\]

而真实 gap 是对所有 arms 取最大值。Learner 可能低估 \(\Delta_{D,i}\)，过早 certify \(i\)，最终返回错误答案。一个 arm 可以不再是合理的 joint output，却仍然是必要的 modality-wise witness。这正是 unaligned feedback 带来的区别：target 身份与证据身份是两种不同角色。

5. 保留 witness，并继续剪枝

对每个 modality \(m\in\{R,D\}\)，维护 witness set \(W_{m,r}\)。Witness 不必仍在 fused candidate set 中；它被保留，是因为它仍可能取得定义某个 modality-wise gap 的最大值。

只有当另一 witness \(k\) 通过有效的 confidence certificate 严格支配 \(j\) 时，才删除 \(j\)：

\[(x_k-x_j)^\top\widehat\theta_{m,r}-\operatorname{CR}_{m,r}(k,j)>0.\]

因此在 good confidence event 上，modality-wise optimum 永远不会被删除；与此同时，已经确定被支配的 arms 也不必永远充当 comparator。每个 phase 结束后，witness set 本身也会被压缩。

完整的 direction set 是

\[\mathcal Y_{m,r}=\{x_j-x_i:\ i\in G_{m,r},\ j\in W_{m,r-1},\ j\neq i\}.\]
Target 侧\(C_r\to G_{m,r}\)

Bottleneck elimination 删除已经无法控制 fused gap 的 target–modality pairs。

Comparator 侧\([K]\to W_{m,r-1}\)

Witness elimination 删除已经无法定义相关 modality-wise gap 的 arms。

当前 allocation 使用上一 phase 的 witness set。这个顺序很重要：design 在看到用于更新 witnesses 的新观测之前就已经固定。

6. Phase-wise 理论保证

整个构造的安全性可以浓缩为一个 lemma。令 \(\gamma_r\) 为 phase resolution，\(\delta_r=3\delta/(\pi^2r^2)\)。

Lemma — Phase-wise fused-elimination guarantee

固定任意 phase \(r\)。条件于 phase \(r\) 之前的 history，以及先前 phases 继承的 logistic reference point 有效，则至少以 \(1-\delta_r\) 的概率，以下陈述对 \(m\in\{R,D\}\) 同时成立：

  1. 对每个 \(i\in G_{m,r}\)，\[\left|\widehat\Delta_{m,i}^{(r)}-\Delta_{m,i}\right|\leq\gamma_r,\qquad \widehat\Delta_{m,i}^{(r)}=\max_{j\in W_{m,r}}(x_j-x_i)^\top\widehat\theta_{m,r}.\]
  2. 从 \(W_{m,r-1}\) 中删除的每个 witness 在 modality \(m\) 下都是 strictly suboptimal；特别地，\(i_m^\star\in W_{m,r}\)。
  3. 若 \(U_{\bar m,i}^{(r)}<L_{m,i}^{(r)}\)，则 \(\Delta_{\bar m,i}<\Delta_{m,i}\)，因此 \(\Delta_i=\Delta_{m,i}\)。

所以每个 active target 的区间都包含真实 modality-wise gap，并且该 phase 中所有 witness 或 bottleneck elimination 都与真实 gap 一致。

第 2 条保护 comparator 侧：剪枝永远不会删除真正的 modality-wise optimum。第 3 条保护 target 侧：只有当某一 modality 被确认不可能控制最大值后，才进行 bottleneck compression。

为什么 witness elimination 不会增大复杂度量级

比较相同 targets 在使用与不使用 witness compression 时的方向集合：

\[\mathcal Y_{m,r}\subseteq\mathcal Y^{\mathrm{no\text{-}wit}}_{m,r}\subseteq\mathcal Y^{\mathrm{full}}_r.\]

对 \(A\subseteq B\)，reward-side design objective 具有单调性：

\[\min_{\nu_R}\max_{y\in A}\|y\|^2_{M_R(\nu_R)^{-1}}\leq\min_{\nu_R}\max_{y\in B}\|y\|^2_{M_R(\nu_R)^{-1}}.\]

相同关系也适用于 dueling Fisher design 的 active-direction branch。因此 witness compression 不可能增大 phase-wise directional design value。为 witness certificate 分配额外 confidence budget 只会改变对数因子，不会在 sample-complexity upper bound 中引入新的多项式量级项。Deterministic worst-case theorem 会保留每个 arm 作为可能的 witness，所以自适应 witness 收益不会让书面上界显得更小；重要的是，它也不会让上界的量级变大。

7. 机制付出了什么，又换来了什么

Ablation 比较了四个 fused variants。令 \(Z=[K]\)，对应的 direction sets 分别是 \(C\times Z\)（无压缩）、\(C\times W\)（仅 witness）、\(G\times Z\)（仅 bottleneck）与 \(G\times W\)（完整 WIT-BOTELIM）。Estimator、confidence schedule、stopping rule 与 design machinery 保持一致。

操作消耗删除对象Median query eliminationKey takeaway
无压缩
C × Z		不维护额外剪枝状态无Baseline简单，但会重复为已经确定的 directions 做 design。
仅 Witness
C × W		每个 modality 维护 dominance certificates 与 witness set无关 comparators\(\varepsilon\)-one：\(28.3\%\)
\(\varepsilon\)-all：\(31.0\%\)		典型轨迹的大部分收益来自 comparator-side compression。
仅 Bottleneck
G × Z		维护 cross-modal gap intervals 与 bottleneck certificates已解决的 target–modality pairs\(\varepsilon\)-one：\(0.7\%\)
\(\varepsilon\)-all：\(8.2\%\)		One-arm 典型轨迹上较小；当所有 arms 都要分类时更有用。
完整方法
G × W		同时维护两类状态，并增加适度的 learner-side optimizationTargets 与 comparators\(\varepsilon\)-one：\(28.5\%\)
\(\varepsilon\)-all：\(42.3\%\)		两种机制互补，尤其适合 exact-set recovery。

相对于两个完全独立的 RAGE-style procedures，端到端平均收益在 \(\varepsilon\)-one 的测试网格上较小，约为 \(2.7\%\)；在 \(\varepsilon\)-all 上则达到约 \(23.8\%\)。Exact-set recovery 提供了更多机会，让一侧的 certificate 简化另一侧。

后期 phase 最能解释 direction compression 的价值。在代表性的 \(60^\circ\)、\(\varepsilon\)-all instance 中，phase 2 把大约 \(1024/1024\) 个 reward/dueling directions 压缩到 \(61/31\)。到 phase 5，median phase cost 从无压缩时约 \(30.06\) million samples 降到完整方法的 \(15.83\) million。Phase resolution 以几何速度收紧，因此最后剩下的 hard directions，恰恰也是被错误保留时最昂贵的 directions。

这个 trade-off 是用计算状态换取统计节省。

Witness–Bottleneck Elimination 维护更多结构，并向 design solver 提出一个过滤得更仔细的问题；作为回报，它减少了浪费在那些已经不可能改变答案的 directions 上的 reward 或 preference queries。

结论

RAGE 最持久的思想不只是“更好地分配样本”，而是不断重新定义样本分配所面对的问题。Fused feedback 让这种重新定义变成二维的：我们既要判断哪些 candidate–modality pairs 尚未解决，也要判断哪些 arms 在每个 modality 内仍然具有 witness 价值。

Bottleneck elimination 说：“这个 modality 已经不可能控制 fused gap。”Witness elimination 说：“这个 comparator 已经不可能定义 modality-wise gap。”二者合在一起，fusion 就变成了对 experimental-design target set 的精确操作。

参考资料

← 返回 Artifacts & Blogs