Technical Summary: Beyond Static Bias: Adaptive Multi-Fidelity Bandits with Improving Proxies

Problem Definition

This work addresses a specific extension of the stochastic multi-armed bandit (MAB) problem known as Multi-Fidelity Multi-Armed Bandits (MF-MAB). In standard MF-MAB settings, arms can be evaluated using multiple feedback sources (fidelities) that trade off cost against accuracy. Traditional frameworks assume a static bias between low-fidelity (cheap) and high-fidelity (expensive) sources; the discrepancy is fixed regardless of how many times the low-fidelity source is queried.

However, modern applications involving learning-based simulators and Large Language Models (LLMs) as evaluators exhibit a different dynamic: the low-fidelity proxy source can improve with additional calibration or repeated use. The paper investigates a budget-constrained MF-MAB setting where:

1. There are $K$ arms with a stationary high-fidelity target mean $\mu^{(H)}_k$.
2. A low-fidelity source provides observations $Y^{(L)}_{k,\tau}$ that evolve based on the number of queries $\tau$ made to that specific arm.
3. The low-fidelity source starts with a mismatch relative to the high-fidelity target, but this mismatch diminishes as the source is queried more frequently (e.g., via calibration).
4. The objective is to minimize cost-weighted pseudo-regret, defined as the cumulative cost incurred by selecting suboptimal arms, rather than just the number of pulls.

The core challenge is determining when to stop querying the improving low-fidelity source and escalate to the expensive high-fidelity source. A static threshold rule might escalate too early, missing the opportunity for the low-fidelity source to become sufficiently accurate through continued cheap sampling.

Methodology

Modeling the Improving Proxy

The authors introduce a selected-average mismatch bound to capture the evolving discrepancy. Instead of assuming a fixed bias $|\mu^{(L)}_k - \mu^{(H)}_k| \le \zeta$, they assume an evolving certificate $U_k(n)$ such that the cumulative mismatch is bounded:
$$\sum_{\tau=1}^n |\mu^{(L)}_k(\tau) - \mu^{(H)}_k| \le U_k(n)$$
This leads to a selected-average mismatch bound $B_k(n) = \sup_{s \ge n} U_k(s)/s$, which bounds the discrepancy between the empirical low-fidelity mean and the true high-fidelity target. As $n$ increases, $B_k(n)$ decreases, reflecting the improving reliability of the proxy.

The TACC Algorithm

The paper proposes the Threshold-Based Adaptive Continuation Companion (TACC) algorithm. TACC operates on a confidence-based template but introduces a novel bounded continuation rule for the low-fidelity source.

1. Confidence Bounds: TACC constructs Upper Confidence Bounds (UCB) for the high-fidelity target $\mu^{(H)}_k$ using both fidelities.
   • High-fidelity UCB: Standard statistical interval.
   • Low-fidelity UCB: Standard statistical interval plus the mismatch correction $B_k(n)$.
2. Arm Selection: The algorithm selects the arm with the highest optimistic score, defined as the minimum of the low-fidelity and high-fidelity UCBs.
3. Fidelity Selection (The Core Innovation):
   • Pre-Threshold: If the low-fidelity statistical uncertainty (radius) is above a threshold $\gamma$, the algorithm continues sampling low fidelity.
   • Post-Threshold: Once the statistical radius falls below $\gamma$, a static rule would immediately escalate to high fidelity. TACC, however, checks if a bounded continuation is cost-effective.
   • Continuation Rule: The algorithm calculates the anticipated decrease in the mismatch correction $V_{k,t}(s)$ if $s$ additional low-fidelity queries are made. If the reduction in mismatch is sufficient to potentially certify the arm's suboptimality without high-fidelity confirmation, and the cost of these additional queries is bounded (specifically, $S_0 \lambda^{(L)} \le \lambda^{(H)}$), TACC continues sampling low fidelity. Otherwise, it escalates to high fidelity.

Key Contributions

1. Problem Formulation: The paper formalizes the MF-MAB setting with improving proxy sources, moving beyond the static bias assumption prevalent in prior literature. It introduces the selected-average mismatch bound to model the dynamic reduction of discrepancy.
2. Algorithm Design: TACC is proposed as an optimistic algorithm that pairs standard arm selection with a bounded post-threshold continuation rule. This rule explicitly decides whether the "improvement" of the low-fidelity source justifies delaying the expensive high-fidelity query.
3. Theoretical Analysis: The authors derive an instance-dependent regret bound. The analysis partitions suboptimal arms into three classes:
   • Easy arms ($A_\gamma$): Certified by low fidelity before the threshold.
   • Intermediate arms ($C_\gamma$): Not certified at the static threshold but become certifiable after bounded low-fidelity continuation.
   • Hard arms ($H_\gamma$): Require high-fidelity confirmation.
     The bound demonstrates that for detected intermediate arms, TACC replaces the logarithmic high-fidelity confirmation cost with a bounded low-fidelity continuation cost.
4. Empirical Validation: Experiments on synthetic bandits and a controlled LLM-as-a-judge policy evaluation task demonstrate that TACC reduces cost-weighted regret compared to static multi-fidelity rules (MF-UCB) and high-fidelity-only baselines (UCB).

Results

Synthetic Experiments

In synthetic settings with 200 and 500 arms, TACC consistently achieved lower cost-weighted regret than UCB, MF-UCB, and static two-fidelity rules. The advantage was most pronounced in scenarios with high high-fidelity costs (e.g., $\lambda^{(H)} = 50$), where avoiding unnecessary high-fidelity confirmations via bounded continuation yielded significant savings.

LLM-as-a-Judge Experiment

The authors evaluated TACC in a policy-evaluation pipeline where arms were prompt-policies for Natural Language Inference (NLI).

• Setup: Low fidelity was a "weak judge" (a smaller LLM) that improved with calibration; high fidelity was a "verifier" (ground truth).
• Findings: TACC outperformed all baselines, including a direct ablation (DNC) that used the same mismatch bounds but lacked the continuation logic. TACC reduced the final cost-weighted regret by approximately 10-20% compared to the best static baselines, confirming that the bounded continuation mechanism effectively leverages the improving nature of the weak judge to avoid premature escalation to the expensive verifier.

Significance and Claims

The paper claims that the primary significance of this work lies in recognizing that proxy sources in modern AI systems are not static. By treating the low-fidelity source as an improving entity, the authors show that the optimal strategy is not merely to switch fidelities based on current uncertainty, but to adaptively continue sampling the cheap source if it is expected to improve sufficiently to resolve ambiguity.

The authors modestly frame their contribution as a canonical two-fidelity model. They acknowledge limitations, noting that the current work assumes a known mismatch bound and focuses on arm-local evolution (where improvement happens only when a specific arm is queried), rather than global model fine-tuning that affects all arms simultaneously. The work serves as a foundational step toward more complex, dynamic fidelity allocation strategies in settings involving LLMs and learning-based simulators.