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

arXiv: https://arxiv.org/abs/2605.08558 · HTML: https://mlsanity.com/paper/2605.08558/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 42 references that are in the map.
- First posted on arXiv 8 May 2026.

## Builds on (most cited first, 26 of 26)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Judging LLM-as-a-Judge with MT-Bench and Chatbot Arena](https://mlsanity.com/paper/2306.05685/) (2023)
- [Constitutional AI: Harmlessness from AI Feedback](https://mlsanity.com/paper/2212.08073/) (2022)
- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Self-Rewarding Language Models](https://mlsanity.com/paper/2401.10020/) (2024)
- [Annotation Artifacts in Natural Language Inference Data](https://mlsanity.com/paper/1803.02324/) (2018)
- [Hypothesis Only Baselines in Natural Language Inference](https://mlsanity.com/paper/1805.01042/) (2018)
- [Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challenges](https://mlsanity.com/paper/1507.08025/) (2015)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [An Empirical Study of LLM-as-a-Judge for LLM Evaluation: Fine-tuned Judge Model is not a General Substitute for GPT-4](https://mlsanity.com/paper/2403.02839/) (2024)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [Rotting Bandits](https://mlsanity.com/paper/1702.07274/) (2017)
- [A Survey on Practical Applications of Multi-Armed and Contextual Bandits](https://mlsanity.com/paper/1904.10040/) (2019)
- [Parameter-free online learning via model selection](https://mlsanity.com/paper/1801.00101/) (2017)
- [Multi-fidelity Gaussian Process Bandit Optimisation](https://mlsanity.com/paper/1603.06288/) (2016)
- [The Multi-fidelity Multi-armed Bandit](https://mlsanity.com/paper/1610.09726/) (2016)
- [Stochastic Rising Bandits](https://mlsanity.com/paper/2212.03798/) (2022)
- [Data-Driven Online Model Selection With Regret Guarantees](https://mlsanity.com/paper/2306.02869/) (2023)
- [Optimal Multi-Fidelity Best-Arm Identification](https://mlsanity.com/paper/2406.03033/) (2024)
- [Best Arm Identification for Stochastic Rising Bandits](https://mlsanity.com/paper/2302.07510/) (2023)
- [Multi-Fidelity Multi-Armed Bandits Revisited](https://mlsanity.com/paper/2306.07761/) (2023)
- [Put CASH on Bandits: A Max K-Armed Problem for Automated Machine Learning](https://mlsanity.com/paper/2505.05226/) (2025)
- [Functional Bandits](https://mlsanity.com/paper/1405.2432/) (2014)
- [Functional multi-armed bandit and the best function identification problems](https://mlsanity.com/paper/2503.00509/) (2025)
- [Managing Self-Learning Experts under Per-Round Budget Constraints](https://mlsanity.com/paper/2510.22654/) (2025)

## Abstract (arXiv)

As an extension of the classical multi-armed bandit problem, multi-fidelity multi-armed bandits (MF-MAB) enable individual arms to be evaluated using diverse feedback sources that vary in both cost and accuracy. Prior stochastic models typically assume fixed low-to-high fidelity discrepancies, whereas modern proxy sources, such as learning-based simulators and Large Language Models (LLMs), can be improved using additional calibration. We investigate adaptive MF-MAB with improving proxy sources, and focus on the canonical two-fidelity case in which the low-fidelity source becomes more informative with repeated use. To capture this dynamic, we introduce a selected-average mismatch bound that converts dynamic low-fidelity observations into improvement-aware confidence bounds for the high-fidelity target. We propose the Threshold-Based Adaptive Continuation Companion (TACC), an optimistic algorithm that uses a bounded continuation rule to decide when low-fidelity sampling remains cost-effective and when to escalate. We prove an instance-dependent regret bound showing that, for detected intermediate arms, adaptive continuation replaces logarithmic high-fidelity confirmation with bounded low-fidelity continuation. Experiments on synthetic bandits and an LLM-as-a-judge policy-evaluation task examine when continuation improves cost-weighted regret.