Best-Arm Identification with Generative Proxy

• URL: http://arxiv.org/abs/2607.06879v1
• Date: Wed, 08 Jul 2026 00:41:43 GMT
• Title: Best-Arm Identification with Generative Proxy
• Abstract summary: We study fixed-confidence best-arm identification in which each costly reward pull is paired with a cheap but correlated proxy score.<n>We propose PROBE, a phase-elimination algorithm that maintains an upper certificate on the residual variance with an ordinary least squares fit.<n>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.
• Score: 10.674965991983974
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions [51.50375419691955]
  Distributionally robust Markov decision processes provide a principled framework for sequential decision making under model uncertainty.<n>We study how many samples are necessary and sufficient to learn an $varepsilon$-optimal robust policy under the average-reward criterion.
  arXiv  Detail & Related papers  (2026-08-06T19:49:48Z)
• CASP: Learning-Augmented Offline Approximation with Verifiable Certificates and Bounded-Loss PAC Guarantees [1.7545090618311434]
  Machine-learned predictions can speed up offline NP-hard optimization, but asking a predictor what to do amounts to asking it to solve the problem.<n> CASP (Certificate-Augmented Solution Pruning) instead asks which parts of the search space may be ignored, and accepts each answer only after a sound-time verifier has checked it.<n>With trained predictors, unverified pruning loses up to $26%$ of the optimum under distribution shift, while the verified deployment of the same predictions loses nothing.
  arXiv  Detail & Related papers  (2026-07-16T04:02:15Z)
• Resample or Reroute? Budget-Aware Test-Time Model Selection for Large Language Models [0.10152838128195468]
  This work formulates budget-aware test-time model selection for large language models.<n>Online resample-or-reroute (RoR) allocation policy driven by estimated marginal correctness per unit cost is proposed.<n> experiments on newly regenerated correctness tensors from an eleven-model open-weight pool over four benchmarks of differing difficulty show that the proposed RoR policy attains a favorable cost-quality robustness front relative to single-route, one-commit-router, budget-aware best-of-K, cascade, and random-allocation baselines.
  arXiv  Detail & Related papers  (2026-07-09T16:34:15Z)
• Anytime PAC-Bayes for Constrained Density-Ratio Networks under Covariate Shift [0.0]
  PAC-Bayes is instantiated on the weighted risk in a fixed-time regime that yields Bernoulli-KL bounds.<n>A patch test against analytic ground truth with a real-data deployment validates the framework.<n>A single fixed-time coverage failure is recorded, with per-split coverage aligning one-to-one with the magnitude of the label shift.
  arXiv  Detail & Related papers  (2026-05-17T01:07:17Z)
• Correction and Corruption: A Two-Rate View of Error Flow in LLM Protocols [51.56484100374058]
  We propose a paired-outcome measurement interface for auditing a single protocol step on exact-match tasks.<n>For each instance, the interface records a baseline correctness bit and a post-step correctness bit.<n>These rates predict accuracy changes and define a reusable empirical interface testable across seeds, mixtures, and pipelines.
  arXiv  Detail & Related papers  (2026-04-20T13:25:40Z)
• Reinforcement Learning from Multi-Source Imperfect Preferences: Best-of-Both-Regimes Regret [71.69884486156359]
  We study episodic RL from emphmulti-source imperfect preferences through a cumulative imperfection budget.<n>We propose a unified algorithm with regret $tildeO(sqrtK/M+)$, which exhibits a best-of-both-regimes behavior.
  arXiv  Detail & Related papers  (2026-03-20T19:34:53Z)
• $V_1$: Unifying Generation and Self-Verification for Parallel Reasoners [69.66089681814013]
  $V_$ is a framework that unifies generation and verification through efficient pairwise ranking.<n>$V_$-Infer improves Pass@1 by up to $10%$ over pointwise verification.<n>$V_$-PairRL achieves $7$--$9%$ test-time scaling gains over standard RL and pointwise joint training.
  arXiv  Detail & Related papers  (2026-03-04T17:22:16Z)
• Best Arm Identification with LLM Judges and Limited Human [18.85883540190321]
  We study fixed-confidence best-arm identification (BAI) where a cheap but potentially biased proxy is available for every sample.<n>We develop an estimator for the mean of each arm that combines proxy scores with inverse-propensity-weighted residuals.<n>Based on the estimator and confidence sequence, we propose an algorithm that adaptively selects and audits arms.
  arXiv  Detail & Related papers  (2026-01-29T09:50:34Z)
• ZIP-RC: Optimizing Test-Time Compute via Zero-Overhead Joint Reward-Cost Prediction [57.799425838564]
  We present ZIP-RC, an adaptive inference method that equips models with zero-overhead inference-time predictions of reward and cost.<n> ZIP-RC improves accuracy by up to 12% over majority voting at equal or lower average cost.
  arXiv  Detail & Related papers  (2025-12-01T09:44:31Z)
• Reinforcement Learning with Verifiable yet Noisy Rewards under Imperfect Verifiers [90.50039419576807]
  Reinforcement Learning with Verifiable Rewards (RLVR) trains policies against automated verifiers to avoid costly human labeling.<n>To reduce vulnerability to verifier hacking, many RLVR systems collapse rewards to binary $0,1$ during training.<n>This choice carries a cost: it introduces textitfalse negatives (rejecting correct answers, FNs) and textitfalse positives (accepting incorrect ones, FPs)
  arXiv  Detail & Related papers  (2025-10-01T13:56:44Z)
• Probabilistically Tightened Linear Relaxation-based Perturbation Analysis for Neural Network Verification [83.25968588249776]
  We present a novel framework that combines over-approximation techniques from LiRPA-based approaches with a sampling-based method to compute tight intermediate reachable sets.<n>With negligible computational overhead, $textttPT-LiRPA$ exploiting the estimated reachable sets, significantly tightens the lower and upper linear bounds of a neural network's output.
  arXiv  Detail & Related papers  (2025-07-07T18:45:53Z)
• Measuring Model Fairness under Noisy Covariates: A Theoretical Perspective [26.704446184314506]
  We study the problem of measuring the fairness of a machine learning model under noisy information. We present a theoretical analysis that aims to characterize weaker conditions under which accurate fairness evaluation is possible.
  arXiv  Detail & Related papers  (2021-05-20T18:36:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.