acceptodds
Under review as a conference paper at ICLR 2027

Online Learning with Improving Proxies: A Multi-Fidelity Bandit Approach

Abstract

In many online learning problems, reliable evaluation can be costly, motivating inexpensive proxy feedback that approximates a trusted target. While proxy quality is often treated as static, learned evaluators may improve through continued training, self-generated supervision, or computational refinement, creating a trade-off between further proxy investment and trusted feedback. Motivated by such self-evolving evaluators, including LLM-based judges, we study a multi-fidelity multi-armed bandit with a stationary high-fidelity target and a low-fidelity source whose discrepancy evolves with use. We introduce an a priori bound on the average proxy-target mismatch, derive improvement-aware confidence bounds, and propose the Threshold-Based Adaptive Continuation Companion (TACC), which determines whether to continue low-fidelity evaluation or escalate to high fidelity. We establish an instance-dependent regret bound showing that limited low-fidelity continuation eliminates the logarithmic high-fidelity term for a class of suboptimal arms, and a lower bound capturing the cost of proxy improvement. Experiments on synthetic bandits and NAS-Bench-201 evaluate when adaptive continuation improves performance.

Primary area:
learning theory
Keywords:
multi-fidelity multi-armed bandits, improving proxy feedback, sequential decision-making, regret analysis, self-improving evaluators, uncertainty quantification

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_KSu3OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper introduces a two-fidelity bandit framework in which the high-fidelity target is stationary while the discrepancy of a cheaper low-fidelity evaluator evolves with use. It proposes TACC, an optimistic algorithm that may continue low-fidelity sampling for a bounded period after reaching the usual switching threshold, when the anticipated reduction in proxy-target mismatch makes continuation worthwhile. The authors provide an instance-dependent upper regret bound and a lower bound capturing both proxy-improvement and statistical identification costs. The empirical evaluation includes synthetic bandits, NAS-Bench-201, and LLM-as-a-judge experiments.

Critical strengths
  1. A novel and well-motivated framework: The paper identifies an interesting limitation of standard multi-fidelity bandit models, which generally treat the low-to-high-fidelity discrepancy as fixed even when the inexpensive evaluator may improve through various means. The proposed TACC algorithm captures the resulting allocation problem through bounded low-fidelity continuation after the nominal switching threshold. Its theoretical analysis identifies a class of arms for which this continuation can be useful with a bounded amount of additional low-fidelity sampling. This provides a clear theoretical explanation of when exploiting evaluator improvement can reduce regret.

  2. Broad empirical evaluation: The paper evaluates the method on synthetic instances, NAS-Bench-201 learning trajectories, controlled LLM-as-a-judge settings, and an experiment based on trained weak-judge checkpoints, with further experiments in the appendix. These experiments showcase that the paper’s key modeling ingredients, such as improved proxy feedback and offline-calibrated mismatch certificates, can arise and be utilized in realistic systems.

Critical weaknesses
  1. The guarantees rely on strong assumptions: Assumption 3.1 requires a known, fixed certificate that uniformly bounds cumulative low-to-high-fidelity mismatch for every arm and sample count. This certificate is what permits time-varying low-fidelity observations to be converted into valid confidence intervals for the stationary high-fidelity target, thereby avoiding the difficult problem of learning the evaluator’s evolution online. Although the experiments demonstrate promising offline calibration, obtaining a uniformly valid certificate in deployment may be difficult. Assumption 5.1 additionally requires that a low-fidelity certificate remain valid until the window ends, for which the practical justification is unclear. While the authors mention an alternative derivation in Appendix C, this does not remove this issue for TACC itself: it introduces a different reference algorithm and replaces the continuation assumption with an additional one. This is the main issue that affects my current score.

  2. The tightness of the regret analysis remains unclear: The lower bound captures the minimum of a low-fidelity route, involving both a masking period and statistical identification, and a high-fidelity identification route. In contrast, TACC’s upper bound is expressed using the parameters γ\gamma and S0S_0 and the arm classes AγA_\gamma, CγdC_\gamma^d, and HγH_\gamma. The appendix provides qualitative comparisons and a particular two-arm family on which TACC is optimal up to a constant factor, but it does not establish that the upper and lower bounds generally match. A clearer characterization of the gap between them would make it easier to assess the optimality of the proposed algorithm or the tightness of the lower bound.

Questions for authors
  1. TACC requires several parameters, including δ,γ,η\delta, \gamma, \eta, and S0S_0. Can some of these be selected internally or removed?

  2. What practical conditions justify Assumption 5.1? Does this assumption hold in the experiments provided in the manuscript?

  3. Can the authors clarify the general relationship between the upper and lower bounds?

1 comment

We appreciate the reviewer's careful assessment and valuable feedback.

Q1. Are Assumptions 3.1 and 5.1 practical?

Thank you for raising this concern. Following the offline calibration approach in Appendix D.3, we ran an additional ImageNet16-120 replay using 199-epoch learning curves. We calibrated the certificate on cumulative absolute mismatch, as required by Assumption 3.1, using architectures separate from evaluation. With a 90% coverage target, 33/40, 33/40, and 36/40 held-out groups were covered across three new partitions. Each group contained 20 arms and counted as covered only when the certificate held for every arm and count in the replay. Q4 reports stability checks and algorithm performance on these same groups.

For the Appendix D.11 checkpoint replay, a wider bound increased full-replay coverage from 0/5 to 5/5 arms. Under this bound, TACC had higher mean regret than DNC at the same γ\gamma. These checks assess certificate coverage over the evaluated trajectories. Q4 reports our separate checks of Assumption 5.1, while Appendix C provides a separate regret bound for RDFE.

Q2. How do the upper and lower regret bounds match, and when optimal?

Thank you for highlighting this connection. We address it in our response to c3R3 Q3, including how MkM_k relates to TACC’s certification time and where the bounds match. We will add this explanation to Section 5 and Appendix B.3, with the scope of the matching result stated explicitly.

Q3. Selection of parameters

We can choose γ\gamma, η\eta, and S0S_0 on tuning data and set δ\delta to the desired confidence level. These remain inputs to TACC. Appendix D.4 suggests S0≤⌊λ(H)/λ(L)⌋S_0\leq\lfloor\lambda^{(H)}/\lambda^{(L)}\rfloor and reports regret sensitivity in Table 3. In an additional delayed-improvement experiment, increasing η\eta from 10−410^{-4} to 10−210^{-2} reduced mean continuation queries from 112.5 to 92.6 at γ=0.25\gamma=0.25.

Q4. Satisfaction of Assumption 5.1 in practice and experiments

In Sections 6.1 and 6.2, the effective gap Δk(L)(n)\Delta_k^{(L)}(n) is nondecreasing, so Assumption 5.1 holds. Additional checks found no decrease across 6,980 synthetic suboptimal-arm trajectories and the three suboptimal NLI arms.

We also checked coverage, stability, and performance together on 199-epoch NAS learning curves, using γ=0.0277\gamma=0.0277, S0=30S_0=30, and the empirical confidence radius. The stability window lies within the recorded curves. A group passed both checks only when the certificate covered every arm and all suboptimal arms satisfied the stability condition.

For ImageNet16-120, the results on groups passing both checks were:

SplitPassing groupsTACCDNC
133/40157.05160.69
232/40153.35155.26
336/40168.41170.93

The table reports mean cost-weighted pseudo-regret at Λ=6,000\Lambda=6{,}000. TACC had lower mean regret in each partition, with paired 95% bootstrap intervals for the differences below zero. The same direction held when all 40 groups were included.

For CIFAR-10-valid and CIFAR-100, 18–22 and 4–6 groups passed both checks, respectively, and TACC matched DNC at the same threshold. Fixed continuation also matched TACC on ImageNet16-120, while separately tuned TACC and DNC matched across all three datasets. These results show where the assumptions hold in the replay and where continuation helps at the specified threshold. We will include these checks in the revision.

Q5. The relationship between the upper and lower bounds

Our response to c3R3 Q3 explains the relationship between the bounds and the two-arm matching construction in Corollary B.13. We will present its parameter choices alongside the bound comparison in the revision.

Reviewer_tK2ROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies an interesting problem of multi-fidelity bandit, in which a learner needs to decide whether to query low- or high-fidelity arms given budget constraint. This is particularly relevant, and I like the motivation in which for current peer review, it is important to balance between AI reviews (low-fidelity) and human experts reviews (high-fidelity). The paper develops an algorithm to this end and provides a regret analysis. Experiments on a few datasets show that this method outperforms prior multi-fidelity bandit baselines.

Critical strengths
  • The paper looks at a very relevant and interesting problem, and formulates for example, the human-AI mixed reviews as a multi-fidelity bandit problem.

  • To the reviewer's knowledge, this paper studies a more general theoretical model in which the proxy-target mismatch can change (rather than being fixed in prior work). The theoretical analysis looks valid, though I did not check the details in the appendix.

  • The paper is generally well written and easy to read.

Critical weaknesses
  • The whole paper relies on Assumption 3.1 which is about a known mismatch certificate. However, how could this be estimated in practice? Although the authors provide some high-level discussions on it, it is still unclear how to implement this. Use human-AI reviews as an example. What if reviewers and LLMs (arms) are changing overtime (which is very likely the case)? Would this estimation of UkU_k change as well?

  • The math in the appendix should be better organized. It is suggested to have a roadmap showing how different lemmas/propositions leads the theorems/corollaries. Also, the numbering of equations is not consistent. Many important equations were not numbered. Also, the figures in the appendix are greatly different in size.

Questions for authors
  • Can the authors discuss how the problem studies in this paper differs from the Bayesian optimization (BO) literature? For BO, a learner might use partial training to decide if future computation is needed.

  • For the baseline comparison, would use the same threshold for DNS as in TACC? This raises the question of if the outperformance of TACC partially comes from a poor tuning of baselines.

1 comment

We thank the reviewer for the helpful questions and suggestions.

Q1. How can the certificate be estimated, and what happens when LLMs or reviewers change?

Appendix D.3 gives an offline calibration example. Similarly, for human–AI reviews, we would estimate cumulative mismatch from paired LLM and human scores, add an uncertainty margin, and check coverage on held-out items. We would keep Uk(n)U_k(n) fixed within each run. If the LLM or reviewer population changes, we would recalibrate before starting a new run, updating the high-fidelity target if the human scoring standard has changed. These checks assess coverage for the calibrated setting.

Q2. Appendix organization, equation numbering, and figure formatting

Thank you for these suggestions. We will reorganize the appendix to make the proofs easier to follow. The current proof structure is:

  • Upper bound: Lemma B.1 establishes valid confidence intervals. Propositions B.5–B.7 give the selection conditions and sampling bounds used in Theorem 5.3 and Corollary 5.4. Proposition B.8 compares the bound with the static threshold rule.
  • Lower bound: Lemmas B.9–B.10 construct the hard instances and derive their sampling cost, leading to Theorem 5.6 and Corollary B.11. Corollary B.13 gives an example where both bounds have the same dependence on the problem parameters. We have also numbered important equations consistently and standardized the appendix figures in the revision.

Q3. How does this differ from partial-training Bayesian optimization?

We thank the reviewer for highlighting this connection. Partial-training BO (Swersky et al., 2014; Falkner et al., 2018; Wistuba et al., 2022) typically evaluates performance by the quality of the best configuration found. Our cost-weighted cumulative regret accounts for the cost and suboptimality of each query throughout learning. Thus, two methods finding the same best configuration can incur different regret if one spends more on suboptimal candidates.

TACC separates statistical uncertainty from evolving proxy mismatch using a fixed mismatch certificate. Its continuation rule uses the anticipated reduction in the mismatch bound to decide whether further low-fidelity queries are worthwhile, with at most S0S_0 extra queries per arm. We will clarify this connection in Related Work.

Q4. Do DNC and TACC use the same threshold, and are the baselines sufficiently tuned?

Yes. DNC and TACC use the same threshold γ\gamma in Section 6.2 (Figure 2) to test the effect of continuation.

To check the effect of tuning, we tested 12 configurations for each method and selected the one with the lowest mean regret on tuning seeds. We then evaluated the selected configurations on separate seeds, using the same budget Λ\Lambda for all methods within each setting.

Sets A and B follow Section 6.1, with high-fidelity costs of 10 and 50. We also tested delayed proxy improvement and two NLI replays, using residual bias (Section 6.2) and successive weak-judge checkpoints (Appendix D.11).

SettingTACCDNCMF-UCB
Set A2759.97 ± 37.102804.76 ± 41.872889.73 ± 39.70
Set B10716.33 ± 258.7410939.17 ± 267.609034.36 ± 243.36
Delayed improvement1859.88 ± 67.441836.19 ± 105.141712.19 ± 137.63
Residual NLI replay5020.97 ± 436.495006.38 ± 436.446445.37 ± 28.49
Checkpoint NLI replay5668.81 ± 479.975224.50 ± 457.57672.95 ± 99.86

The table reports mean cost-weighted pseudo-regret ± standard error over 36 evaluation seeds for Sets A and B and 72 for the others. Lower values are better.

TACC retained the lowest mean regret in Set A. In the residual NLI replay, its mean regret was 0.3% higher than DNC’s and lower than MF-UCB’s. MF-UCB had lower mean regret in Set B and the checkpoint replay. For delayed improvement, paired 95% bootstrap intervals for both comparisons with TACC included zero. We will include these comparisons to clarify the effect of baseline tuning.

References

Swersky, K., Snoek, J., & Adams, R. P. (2014). Freeze-thaw Bayesian optimization. arXiv:1406.3896.

Falkner, S., Klein, A., & Hutter, F. (2018). BOHB: Robust and efficient hyperparameter optimization at scale. ICML.

Wistuba, M., Kadra, A., & Grabocka, J. (2022). Supervising the multi-fidelity race of hyperparameter configurations. NeurIPS.

Reviewer_c3R3OpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies a multi-fidelity multi-armed bandit problem in which each arm can be queried at two fidelities. The high-fidelity mean remains stationary, while the low-fidelity mean evolves with the number of low-fidelity queries of that arm. The learner is given a bound on the discrepancy between the average low-fidelity mean and the high-fidelity target. The authors propose an algorithm that minimizes cost-weighted regret, which weights the suboptimality gap of each selected arm by the cost of the corresponding query. They establish an instance-dependent regret bound and a lower bound, and empirically evaluate the algorithm.

Critical strengths

The problem of allocating resources between expensive, reliable feedback and cheaper proxies is interesting and relevant. Allowing proxy accuracy to improve with continued use is a natural extension of the standard multi-fidelity model.

Critical weaknesses

My main concerns are the strength of the assumptions and the interpretation and significance of the theoretical guarantees.

First, the analysis relies on several assumptions and instance-dependent quantities whose practical meaning is difficult to assess. The paper should explain more clearly which natural improvement processes satisfy these conditions.

Second, the paper does not clearly establish the extent of the improvement over existing methods. This is probably related to the fact that comparing the regret bounds is difficult because they involve different instance-dependent quantities.

Finally, the relationship between the upper and lower bounds is not sufficiently developed. Although the paper provides a matching result for a restricted family, it does not give a general characterization of when the proposed algorithm is optimal.

Questions for authors

Could you provide a more intuitive interpretation of the parameters and assumptions appearing in the upper bound?

Could you clarify under which conditions the upper and lower bounds match?

2 comments

We thank the reviewer for the careful evaluation of our work and the helpful recommendations.

Q1. Assumptions, improvement process in practice

Thanks for the comment. We could consider evaluating product or interface designs when real customer feedback is limited and costly to collect, while AI-simulated responses are cheaper and more readily available. The simulator's evaluations can be improved through calibration using previous human feedback. For example, Shadow Bandits (Abdolmaleki et al., 2026) uses matched human and synthetic responses to estimate and correct systematic bias. Such calibration helps estimate the remaining mismatch and assess mismatch bounds. Lee et al. (2026) use a fixed calibration dataset to correct evaluations on new data batches when the judge’s error rates remain stable. This motivates reusing a calibrated mismatch bound within the task population and refinement procedure covered by calibration. Appendix D.3 also gives an offline calibration example. We will clarify these examples when introducing assumptions in revision.

Q2. How do the regret bounds compare with existing methods?

Thank you for pointing it out. We kept the discussion brief in the main text due to the page constraints and will make it more explicit in the revision. Proposition B.8 compares the bounds on the same instance and with the same threshold. For arms that satisfy the continuation conditions, TACC replaces the logarithmic high-fidelity term in the bound with the cost of at most S0S_0 extra low-fidelity queries, yielding a smaller regret bound when these additional queries are cheaper than the high-fidelity exploration they replace. Additional comparisons are reported in our response to tK2R Q4.

Q3. Relationship between the upper and lower bounds

Thank you for raising this point, we will make the comparison more explicit in Section 5 and Appendix B.3.

Theorem 5.6 captures the cheaper of two routes: improving and identifying an arm at low fidelity, or identifying it directly at high fidelity. The masking time MkM_k measures how long observations can remain uninformative under the given certificate. TACC’s upper bound also depends on the actual certification time τk(γ)\tau_k(\gamma). When certification occurs within the continuation window and the continuation test holds, the arm belongs to Cγd\mathcal C_\gamma^d and avoids the logarithmic high-fidelity term in Theorem 5.3.

Corollary B.13 shows how these quantities align in a simpler construction. Under its parameter choices, certification occurs at 4M4M, within the window ending at 6M6M, and the continuation test holds. TACC’s worst-case expected regret is at most 11Δ(M+1)11\Delta(M+1), while the lower bound is Δ(M+1)/16\Delta(M+1)/16. Thus, both bounds have the same dependence on Δ\Delta and MM in this construction.

Q4. Intuitive interpretation of the parameters and assumptions in the upper bound

Yes. A smaller switching threshold γ\gamma delays the switch to high fidelity. A smaller continuation parameter η\eta allows further low-fidelity sampling for more modest anticipated reductions in the mismatch bound. The continuation cap S0S_0 limits this extra low fidelity queries per arm. A smaller δ\delta gives more conservative confidence bounds.

Assumption 3.1 bounds cumulative proxy-target mismatch, allowing low-fidelity observations to inform the high-fidelity target. Assumption 5.1 ensures that, once the low-fidelity information is sufficient to rule out a suboptimal arm, it remains so through the sampling period.

References

Abdolmaleki, M., Ham, D. W., & Jasin, S. (2026). Shadow Bandits: Learning from Synthetic Feedback. Available at SSRN 7645718.

Lee, C., Zeng, T., Jeong, J., Sohn, J.-y., & Lee, K. (2026). How to correctly report LLM-as-a-judge evaluations. In Forty-third International Conference on Machine Learning. URL https://openreview.net/forum?id=VX8H2713oA.

Thank you for your response. However, most of my concerns remain unresolved, so I will maintain my original score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.