Best-Arm Identification with Generative Proxy

2026-07-08 · Source: Machine Learning · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Data Science & Analytics · Depth: Expert, quick

Summary

A new phase-elimination algorithm, PROBE (PRoxy OLS for Best-arm Exploration), addresses the high cost of reward observations in best-arm identification by integrating cheap, correlated proxy scores from machine learning and large language models. While the proxy's marginal mean is known, its correlation ρ with the reward is initially unknown and must be learned online. The core challenge lies in estimating this correlation from the same costly samples used for identification, as a simple plug-in estimate can compromise correctness. PROBE overcomes this by maintaining an upper certificate on the residual variance using an ordinary least squares fit, leveraging its exact chi-square law for validity. The algorithm is proven δ-PAC and achieves the oracle sample complexity for known correlation, with minor adjustments extending its guarantee to the (ε,δ)-PAC setting. Numerical experiments, including an auto-loan pricing replay, validate that PROBE's sample savings directly correlate with the strength of the reward-proxy relationship.

Key takeaway

For Machine Learning Engineers optimizing data-driven decision-making with costly observations, you should consider implementing PROBE. This algorithm allows you to significantly reduce sample complexity by integrating cheap, correlated proxy scores from ML or LLMs. By learning the proxy-reward correlation online, PROBE provides δ-PAC guarantees and substantial sample savings, especially when your proxies exhibit strong correlation. This approach can make best-arm identification feasible in resource-constrained environments.

Key insights

Using cheap generative proxies with online correlation learning significantly reduces sample costs in best-arm identification.

Principles

• Costly reward observations can be augmented by cheap, correlated proxies.
• Unknown proxy-reward correlation ρ must be learned online for optimal gains.
• Control-variate adjustment transforms the problem into heteroscedastic identification.

Method

PROBE is a phase-elimination algorithm that uses ordinary least squares to maintain a valid upper certificate on residual variance, ensuring δ-PAC guarantees despite unknown proxy-reward correlation.

In practice

• Apply PROBE to reduce sample costs in best-arm identification.
• Integrate ML/LLM predictions as cheap proxies for costly rewards.
• Sample savings scale with proxy-reward correlation strength.

Topics

• Best-Arm Identification
• Generative Proxies
• Machine Learning Models
• Large Language Models
• Sample Complexity Reduction
• PROBE Algorithm

Best for: Research Scientist, AI Scientist, Machine Learning Engineer

Related on AIssential

• Classifying by Proxy: Explainable and Reproducible Ensemble of Proxy Tasks for Child Sexual Abuse Imagery Classification — An ensemble of Proxy Tasks enhances CSAI classification with improved explainability, reproducibility, and security.
• An adaptive subsampling method for large-sample feature screening — BanditCR-SIS accelerates model-free feature screening using multi-armed bandits and Chatterjee's rank correlation, drastically cutting computational costs.
• CausShield: Sample Reconstruction-Resilient Vertical FL via Causal Representation Learning — CausShield enhances Vertical Federated Learning privacy by causally separating task-relevant from privacy-sensitive features, outperforming existing defenses in utility and protection.
• RegMix-D: Dynamic Data Mixing via Proxy Training Trajectories — Leveraging full loss trajectories from proxy runs enables dynamic data mixture optimization for LLM pretraining.
• The Role of Contextual Information in Best Arm Identification — Contextual information significantly improves the efficiency of best-arm identification in stochastic bandits by reducing sample complexity.
• Surrogate-Gated Generation and Foundation-Model Embeddings for Bayesian Materials Design — A surrogate-gated generative workflow significantly reduces oracle calls in materials discovery while maintaining performance.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by Machine Learning.