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.
Tianyi Ma, Hanzhang Qin, Ruihao Zhu et al.· 1 citation
In this paper, we study contextual stochastic optimization (CSO), where decisions are made under uncertainty and the distribution of random parameters can be partially inferred from covariates observed prior to decision-making. In many practical settings, these distributions also depend on the decisions themselves, a phenomenon known as the
decision-dependent effect
. Most existing studies address this issue by imposing structural assumptions on the relationship between decisions and the underlying distributions. However, such assumptions may lead to model misspecification when the true relationship deviates from the assumed form. A prominent alternative is the weighted sample average approximation (wSAA) method proposed by Bertsimas and Kallus (2019), which adapts sample weights based on their similarity to the current decision–context pair. Nevertheless, because these weights are typically computed using complex machine learning models and depend on the decision variables in decision-dependent settings, solving the resulting optimization problem becomes computationally challenging. To overcome this challenge, we extend the wSAA framework from the loss function to its gradient, leading to the notion of the
contextual gradient
. We show that the contextual gradient serves as a meaningful indicator of optimality and leverage this property to develop the
contextual gradient descent (CGD)
algorithm. Our analysis establishes that CGD converges to a neighborhood of the global optimum when the loss function exhibits sufficient strong convexity. Moreover, the derived bounds reveal a key insight: the strength of convexity in the loss function can compensate for the uncertainty introduced by decision-dependent effects. Extensive numerical experiments on both synthetic and real-world datasets demonstrate that CGD consistently outperforms existing methods for contextual optimization under decision-dependent uncertainty.
Wenxuan Liu, Xiangting Liu, Maoqi Liu et al.· Production and operations ma...· 0 citations
To the authors' knowledge, AdmitOR is the first label-free admission mechanism designed around an explicitly calibrated false-discovery target, and the transfer failure identifies a necessary condition for extending it to wild streams.
Junbo Jacob Lian, Hui-Ling Chen, Hanzhang Qin et al.· 0 citations