# Best-Arm Identification with Generative Proxy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 50 references that are in the map.
- First posted on arXiv 8 Jul 2026.

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

- [TabPFN: A Transformer That Solves Small Tabular Classification Problems in a Second](https://mlsanity.com/paper/2207.01848/) (2022)
- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [lil' UCB : An Optimal Exploration Algorithm for Multi-Armed Bandits](https://mlsanity.com/paper/1312.7308/) (2013)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [An optimal algorithm for the Thresholding Bandit Problem](https://mlsanity.com/paper/1605.08671/) (2016)
- [The Challenge of Using LLMs to Simulate Human Behavior: A Causal Inference Perspective](https://mlsanity.com/paper/2312.15524/) (2023)
- [Large Language Models: An Applied Econometric Framework](https://mlsanity.com/paper/2412.07031/) (2024)
- [Best arm identification in multi-armed bandits with delayed feedback](https://mlsanity.com/paper/1803.10937/) (2018)
- [Review on Ranking and Selection: A New Perspective](https://mlsanity.com/paper/2008.00249/) (2020)
- [LOLA: LLM-Assisted Online Learning Algorithm for Content Experiments](https://mlsanity.com/paper/2406.02611/) (2024)
- [Multi-Armed Bandits With Machine Learning-Generated Surrogate Rewards](https://mlsanity.com/paper/2506.16658/) (2025)
- [Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification](https://mlsanity.com/paper/2111.01479/) (2021)
- [Top-m identification for linear bandits](https://mlsanity.com/paper/2103.10070/) (2021)
- [Best Arm Identification with LLM Judges and Limited Human](https://mlsanity.com/paper/2601.21471/) (2026)
- [Variance-Dependent Best Arm Identification](https://mlsanity.com/paper/2106.10417/) (2021)
- [Best-Arm Identification in Correlated Multi-Armed Bandits](https://mlsanity.com/paper/2109.04941/) (2021)
- [Stochastic Multi-Armed Bandits with Control Variates](https://mlsanity.com/paper/2105.03962/) (2021)
- [Exploiting Correlated Auxiliary Feedback in Parameterized Bandits](https://mlsanity.com/paper/2311.02715/) (2023)
- [Best Arm Identification with Possibly Biased Offline Data](https://mlsanity.com/paper/2505.23165/) (2025)
- [Contextual Online Pricing with (Biased) Offline Data](https://mlsanity.com/paper/2507.02762/) (2025)
- [Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution](https://mlsanity.com/paper/2406.06802/) (2024)
- [Large Language Model Enhanced Machine Learning Estimators for Classification](https://mlsanity.com/paper/2405.05445/) (2024)
- [Covariance Adaptive Best Arm Identification](https://mlsanity.com/paper/2306.02630/) (2023)

## Built on by (most cited first, 1 of 1)

- [When May a Model Replace the Experiment? Audits, Licenses, and the Price of Trust in Surrogate-Driven Design](https://mlsanity.com/paper/2608.01378/) (2026)

## Abstract (arXiv)

Best-arm identification is a canonical model for data-driven decision-making, but in many applications each reward observation is costly. Motivated by the growing availability of cheap predictions from machine learning and large language models, we study fixed-confidence best-arm identification in which each costly reward pull is paired with a cheap but correlated proxy score. The marginal mean of the proxy can be estimated offline and is treated as known, whereas its correlation ρ with the reward, which governs how much the proxy helps, is unknown and must be learned online in pair with real rewards. We show that a control-variate adjustment turns this model into a heteroscedastic identification problem whose oracle sample complexity improves by residual variance 1-ρ2. The central difficulty is that the correlation must be learned from the same costly samples that identification consumes online, and that a plug-in estimate of the residual variance is anti-conservative and can compromise correctness. We propose PROBE (PRoxy OLS for Best-arm Exploration), a phase-elimination algorithm that directly maintains an upper certificate on the residual variance with an ordinary least squares fit, whose exact chi-square law keeps the certificate valid regardless of the unknown correlation. We prove that PROBE is δ-PAC and attains the known-correlation oracle sample complexity up to a constant multiplicative factor and a constant additive calibration cost. The guarantee extends to the (ε,δ)-PAC setting under minimal changes to the algorithm. Numerical experiments on synthetic instances and on an auto-loan pricing replay with large language model and tabular proxies confirm that the sample savings of PROBE scale with the strength of the reward-proxy correlation, exactly as the theory predicts.