Pith. sign in

REVIEW 2 major objections 6 minor 23 references

Best-Arm Identification with Generative Proxy

T0 review · 2 major / 6 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Cheap AI Predictions Cut Costly Experiments by Up to 61%

desk verdict Solid contribution to proxy-augmented BAI; the Gaussian assumption is the main limitation but is transparent and standard. read the letter →

arxiv 2607.06879 v1 pith:I2AWVRLA submitted 2026-07-08 cs.LG stat.ML

Tianyi Ma , Hanzhang Qin , Ruihao Zhu , Jierui Zuo This is my paper
classification cs.LGstat.ML
keywords identificationproxybest-armcorrelationcostlymodelproberesidual
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper proves that a cheap but imperfect AI-generated proxy score can be safely used to reduce the number of expensive real-world experiments needed to identify the best option among a finite set. The core mechanism is a control-variate adjustment: if one knows the correlation between the proxy and the true reward, one can subtract the predictable part of the reward noise, reducing the effective variance of each observation from 1 to 1 - rho^2. The difficulty is that this correlation is unknown and must be learned from the same expensive samples one is trying to save. The paper shows that naively plugging in an estimated correlation is dangerous because it can underestimate the residual variance, leading to premature and incorrect decisions. Instead, the proposed PROBE algorithm uses ordinary least squares to maintain a one-sided upper certificate on the residual variance, exploiting the exact chi-square law of the OLS residual to guarantee correctness regardless of the true unknown correlation. The result is a method that achieves the same sample efficiency as an oracle that knows the correlation in advance, up to a constant factor and a fixed calibration cost.

What carries the argument

The key machinery is the residual-variance upper certificate U(s, v_hat, eta) derived from the chi-square law of the OLS residual variance estimator. Given a batch of s observations, the statistic (s-2) * v_hat / v follows a chi-square distribution with s-2 degrees of freedom, regardless of the unknown correlation rho. This scale-free property allows PROBE to construct a valid upper bound on v = 1 - rho^2 that holds with high probability, which then determines the batch size for the next elimination round. A calibration stage initializes the certificate within a factor (1 + kappa) of the true variance, and a monotone minimum update preserves this sandwich bound throughout the algorithm's run

What would settle it

A direct falsifier would be an instance where the reward-proxy pairs follow the specified bivariate Gaussian model, the correlation rho is large (say 0.8 or higher), and PROBE either fails to identify the best arm with probability at least 1-delta, or requires a number of samples that grows faster than the oracle benchmark by more than the stated constant factor. Another falsifier would be a demonstration that the OLS residual variance estimator's distribution deviates significantly from chi-square under the model, breaking the upper certificate and causing premature arm elimination.

Watch

Extended reading notes

Core claim

The central discovery is that the exact chi-square distribution of the OLS residual variance estimator provides a correlation-free, one-sided upper certificate on the true residual variance. This certificate can be used to size future sampling batches without ever needing to directly estimate or bound the reward-proxy correlation rho, thereby sidestepping the anti-conservatism and divergence problems that plague plug-in or conservative confidence bound approaches to rho. By maintaining this certificate through a monotone update and decoupling mean estimation from variance calibration via a one-round lag, the algorithm achieves oracle-level sample complexity with provable correctness.

Load-bearing premise

The entire mathematical guarantee rests on the bivariate Gaussian observation model, where both the reward and the proxy score are assumed to be jointly normally distributed with unit variances. The exact chi-square law of the OLS residual variance, which makes the upper certificate valid and correlation-free, depends on this Gaussian assumption. If the reward or proxy distribution is non-Gaussian, the chi-square distribution no longer holds exactly, and the correctness proof

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. This paper studies fixed-confidence best-arm identification (BAI) in a setting where each costly reward pull is paired with a cheap proxy score (e.g., from an LLM or predictive model). The proxy mean is assumed known (estimated offline cheaply), but the reward-proxy correlation is unknown and must be learned online. The authors show that a control-variate adjustment reduces the problem to a heteroscedastic BAI problem with residual variance 1−ρ². The main algorithmic challenge is that a plug-in estimate of the residual variance is anti-conservative, risking incorrect eliminations. The authors propose PROBE, a phase-elimination algorithm that maintains a one-sided upper certificate on the residual variance via an OLS fit, exploiting the exact chi-square law of the residual variance estimator. PROBE is proven to be δ-PAC and achieves the known-correlation oracle sample complexity up to a multiplicative factor (1+κ) and an additive calibration cost of order Õ(K/κ²). The guarantee extends to the (ε,δ)-PAC setting. Experiments on synthetic data and an auto-loan pricing replay confirm the predicted variance reduction.

Significance. The paper addresses a timely and practically important problem: leveraging cheap but noisy AI/LLM-generated proxy scores to reduce the number of costly online experiments needed for decision-making. The core technical insight—using the exact chi-square law of the OLS residual variance to construct a valid upper certificate, rather than a plug-in correlation estimate—is elegant and well-motivated. The theoretical guarantee is clean, with an explicit price parameter κ for not knowing the correlation. The auto-loan replay experiment with LLM and tabular proxies demonstrates substantial practical gains (up to 61% sample savings), directly validating the theoretical predictions. The proof strategy via a 'clean event' is standard but correctly executed and self-contained.

major comments (2)
  1. The bivariate Gaussian observation model (Equation 2) is load-bearing for the entire theoretical framework. The exact chi-square law of the OLS residual variance estimator (Proposition 2), which underpins the upper certificate U(s, v̂, η) in Equation 7, requires Gaussianity. The conditional Gaussianity of the OLS intercept and the leverage bound (Lemma 2) also rely on Gaussian tail bounds. While this is a transparent and standard modeling choice in the bandit literature, the paper's phrasing in the abstract and Section 3.1—'whose exact χ² law keeps the certificate valid regardless of the unknown correlation'—could be misread as implying distribution-free validity. The authors should explicitly state in the main text (not just implicitly via the model definition) that the δ-PAC guarantee is contingent on the Gaussian assumption, and briefly discuss the gap between this theory and the Bern
  2. The auto-loan replay experiment (Section 6) uses Bernoulli acceptance rewards, which violate the Gaussian assumption central to the theory. While the empirical results are compelling and show the algorithm works well in practice, the paper would benefit from a brief discussion of why PROBE remains robust in this non-Gaussian setting (e.g., asymptotic normality of OLS, or conservative nature of the certificate). This would strengthen the bridge between theory and practice.
minor comments (6)
  1. Section 1.1: The phrase 'whose exact χ² law keeps the certificate valid regardless of the unknown correlation' should be qualified to note it also requires the Gaussian observation model.
  2. Algorithm 1: The notation s_{i,r} is used for the cumulative sample count, but it is initially set to 1 + t_cal and then updated as s_{i,r+1} = s_{i,r} + t_{i,r}. This is slightly confusing since t_{i,r} is the batch size for round r. Consider clarifying that s_{i,r} tracks the starting index of the round-r batch.
  3. Table 1: The column 'Correct' reports 1.000 for all methods, which is good but could be more precise (e.g., 3000/3000).
  4. Section 5.1: The proxy means are described as 'deliberately ordered in the opposite direction from the reward means.' It would help to explicitly state that this demonstrates the proxy's utility comes from within-arm covariance, not mean ranking, which is a key point.
  5. Typo in Section 1.1: 'eO(K/κ²)' should be 'Õ(K/κ²)' for consistency with the rest of the paper.
  6. The paper cites 'GPT-5.5 (OpenAI 2026)' and 'Qwen2.5-7B (Qwen et al. 2025)'. Ensure these references are complete and accurate for the camera-ready version.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: derivation is self-contained from standard probability theory

full rationale

The paper's derivation chain is: (1) bivariate Gaussian model (Eq. 2) → (2) control-variate variance reduction to 1−ρ² (Proposition 1, a standard calculation) → (3) OLS reformulation with exact χ² law for residual variance (Proposition 2, standard linear regression theory) → (4) one-sided upper certificate U(s,v̂,η) from χ² lower tail (Eq. 7) → (5) phase-elimination algorithm with monotone updates and one-round lag → (6) δ-PAC guarantee matching oracle complexity up to 1+κ (Theorem 1). Each step follows from the previous by standard mathematics. The oracle benchmark (Eq. 4) is the classical BAI complexity with variance v_i substituted for 1—no fitting or circular definition. The sample complexity bound in Theorem 1 is derived from concentration inequalities and the clean event, not from fitting parameters to data. The citation to Ji et al. (2025) is for adopting the bivariate Gaussian observation model, which is a standard distributional assumption, not a novel construction whose validity depends on this paper's results. The Angelopoulos et al. (2023a) citation for control variates references a well-known variance-reduction technique. No step reduces to its inputs by construction, no prediction is a renamed fit, and no self-citation chain is load-bearing for the central theorem. The gap between Gaussian theory and Bernoulli-reward experiments is a modeling limitation (correctness risk), not circularity.

Assumptions & free parameters 1 free parameters · 3 assumptions · 0 invented entities

The paper does not invent new entities. It introduces one free parameter κ, which is a standard algorithmic tolerance parameter. The main axioms are the Gaussian and unit-variance assumptions on the reward-proxy pair.

free parameters (1)
  • κ = 1.0 (in experiments)
    The tolerance parameter for the residual variance certificate. It is a user-chosen constant, not fitted to data, but it is a free parameter that trades off calibration cost and sample complexity tightness.
assumptions (3)
  • domain assumption Bivariate Gaussian observation model (Eq. 2)
    The reward and proxy are assumed to follow a joint normal distribution. This is load-bearing because the exact chi-square distribution of the OLS residual variance, which underpins the upper certificate, requires Gaussian errors.
  • domain assumption Known proxy marginal mean
    Assumed estimable to arbitrary accuracy offline due to cheap proxy calls. This is the asymmetry that enables the control-variate adjustment.
  • domain assumption Unit reward variance
    The model assumes Var(X_i,l) = 1. The paper mentions rewards are scaled to unit variance in experiments, but this is a structural assumption in the theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Best-Arm Identification with Generative Proxy." pith.science (2026). https://pith.science/paper/I2AWVRLA

@misc{pith2026260706879,
  author       = {Pith},
  title        = {Pith review of: Best-Arm Identification with Generative Proxy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/I2AWVRLA}},
  note         = {Machine review of arXiv:2607.06879}
}
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 $\rho$ 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-\rho^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 $\delta$-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 $(\epsilon,\delta)$-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.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    PPI++: Efficient Prediction-Powered Inference

    4889–4897. Angelopoulos, Anastasios N., Stephen Bates, Clara Fannjiang, Michael I. Jordan, Tijana Zrnic. 2023a. Prediction-powered inference.Science382(6671) 669–674. doi:10.1126/science.adi6000. Angelopoulos, Anastasios N., John C. Duchi, Tijana Zrnic. 2023b. PPI++: Efficient prediction-powered inference. doi:10.48550/arXiv.2311.01453. Ao, Ruicheng, Hong...

    work page Pith review arXiv doi:10.1126/science.adi6000

  2. [2]

    doi:10.1287/mnsc.2020.3729

    Predicting with proxies: Transfer learning in high dimension.Management Science 67(5) 2964–2984. doi:10.1287/mnsc.2020.3729. Bechhofer, Robert E

    work page doi:10.1287/mnsc.2020.3729 2020

  3. [3]

    The Annals of Mathematical Statistics , author =

    A single-sample multiple decision procedure for ranking means of normal populations with known variances.The Annals of Mathematical Statistics25(1) 16–39. doi:10.1214/ aoms/1177728845. Brand, James, Ayelet Israeli, Donald Ngwe

    work page arXiv

  4. [4]

    doi:10.2139/ssrn.4395751

    Using LLMs for market research. doi:10.2139/ssrn.4395751. Harvard Business School Marketing Unit Working Paper No. 23-062. Bubeck, S´ ebastien, Tengyao Wang, Nitin Viswanathan

    work page doi:10.2139/ssrn.4395751

  5. [5]

    doi:10.1023/A:1008349927281

    Simulation budget allocation for further enhancing the efficiency of ordinal optimization.Discrete Event Dynamic Systems10(3) 251–270. doi:10.1023/A:1008349927281. Columbia University Center for Pricing and Revenue Management

    work page doi:10.1023/a:1008349927281

  6. [6]

    Satisficing Regret Minimization in Bandits: Constant Rate and Light-Tailed Distribution

    Satisficing regret minimization in bandits: Constant rate and light-tailed distribution.arXiv preprint arXiv:2406.06802. Fiez, Tanner, Lalit Jain, Kevin G. Jamieson, Lillian Ratliff

    work page Pith review arXiv

  7. [7]

    Glasserman, Paul

    PMLR, 998–1027. Glasserman, Paul. 2003.Monte Carlo Methods in Financial Engineering,Stochastic Modelling and Applied Probability, vol

    work page 2003

  8. [8]

    2003.Monte Carlo Methods in Financial Engineering

    Springer, New York, NY. doi:10.1007/978-0-387-21617-1. Goli, Ali, Amandeep Singh

    work page doi:10.1007/978-0-387-21617-1

Show all 23 references
  1. [9]

    doi:10.1287/mksc.2023.0306

    Frontiers: Can large language models capture human preferences?Marketing Science43(4) 709–722. doi:10.1287/mksc.2023.0306. Grover, Aditya, Todor Markov, Peter Attia, Norman Jin, Nicolas Perkins, Bryan Cheong, Michael Chen, Zi Yang, Stephen Harris, William Chueh, Stefano Ermon

    2023 doi

  2. [10]

    doi:10.48550/arXiv.2312.15524

    The challenge of using LLMs to simulate human behavior: A causal inference perspective. doi:10.48550/arXiv.2312.15524. Gupta, Samarth, Gauri Joshi, Osman Yagan

    doi

  3. [11]

    IEEE Journal on Selected Areas in Information Theory2(2) 549–563

    Best-arm identification in correlated multi-armed bandits. IEEE Journal on Selected Areas in Information Theory2(2) 549–563. doi:10.1109/JSAIT.2021.3082028. Hollmann, Noah, Samuel M¨ uller, Katharina Eggensperger, Frank Hutter

    2021 doi

  4. [12]

    doi:10.1007/s42524-021-0152-6

    Review on ranking and selection: A new perspective.Frontiers of Engineering Management8(3) 321–343. doi:10.1007/s42524-021-0152-6. Jamieson, Kevin, Matthew Malloy, Robert Nowak, S´ ebastien Bubeck

    doi

  5. [13]

    doi:10.48550/arXiv.2506.16658

    Multi-armed bandits with machine learning-generated surrogate rewards. doi:10.48550/arXiv.2506.16658. Kalyanakrishnan, Shivaram, Ambuj Tewari, Peter Auer, Peter Stone

    doi arXiv

  6. [14]

    doi:10.1145/ 502109.502111

    A fully sequential procedure for indifference-zone selection in simulation.ACM Transactions on Modeling and Computer Simulation11(3) 251–273. doi:10.1145/ 502109.502111. Li, Zhekai, Tianyi Ma, Cheng Hua, Ruihao Zhu

  7. [15]

    doi:10.48550/arXiv.2510.00073

    Identifying all ϵ-best arms in (misspecified) linear bandits. doi:10.48550/arXiv.2510.00073. Locatelli, Andrea, Maurilio Gutzeit, Alexandra Carpentier

    doi

  8. [16]

    Working Paper 33344, National Bureau of Economic Research

    Large language models: An applied econometric framework. Working Paper 33344, National Bureau of Economic Research. doi:10.3386/w33344. Mannor, Shie, John N. Tsitsiklis

    doi

  9. [17]

    doi:10.48550/arXiv.2402

    Optimal thresholding linear bandit. doi:10.48550/arXiv.2402. 09467. OpenAI

    doi

  10. [18]

    doi:10.1287/mnsc.2014

    The effectiveness of field price discretion: Empirical evidence from auto lending.Management Science61(8) 1741–1759. doi:10.1287/mnsc.2014

    2014 doi

  11. [19]

    doi:10.48550/arXiv.2412.15115

    Qwen2.5 technical report. doi:10.48550/arXiv.2412.15115. 24 R´ eda, Cl´ emence, Emilie Kaufmann, Andr´ ee Delahaye-Duriez. 2021a. Top-m identification for linear bandits. Proceedings of the 24th International Conference on Artificial Intelligence and Statistics,Proceedings of ...

    doi arXiv

  12. [20]

    doi:10.1287/mksc.2025.0009

    Large language models for market research: A data-augmentation approach.Marketing Science0(0). doi:10.1287/mksc.2025.0009. Articles in Advance. Wu, Yuhang, Yingfei Wang, Chu Wang, Zeyu Zheng

    2025 doi

  13. [21]

    doi:10.48550/arXiv.2405.05445

    Large language model enhanced machine learning estimators for classification. doi:10.48550/arXiv.2405.05445. Yang, Le, Vincent Y. F. Tan, Wang Chi Cheung

    doi arXiv

  14. [22]

    doi:10.1287/mksc.2024.0990

    LOLA: LLM-assisted online learning algorithm for content experiments.Marketing Science44(5) 995–1016. doi:10.1287/mksc.2024.0990. Yin, Qichuan, Linwei Xin

    2024 doi

  15. [23]

    doi:10.2139/ssrn.6078686

    Synthetic but not infinite: How much LLM-generated data to use in market research. doi:10.2139/ssrn.6078686. Available at SSRN 6078686. Zhang, Yixuan, Ruihao Zhu, Qiaomin Xie

    doi

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.