Variance-Optimal Control Variates for Learning with Black-box Feedback

Zihao Zhao; Shuhan Zhang; Kai Wang

cs.LGOct 3, 2026

Variance-Optimal Control Variates for Learning with Black-box Feedback

Authors: Zihao Zhao, Shuhan Zhang, Kai Wang

Organizations: School of Computational Science and Engineering Georgia Institute of Technology

Abstract

Modern models increasingly learn through black-box oracles such as humans, optimization solvers, and external tools that provide feedback without exposing their internal mechanisms. A common remedy is to learn an (action-)value function as a control variate. In this paper, we first observe that even an exact action-value function can be arbitrarily far from variance-optimal. We show that this gap arises because the value function minimizes the noise in each action's own gradient term, while an action can still affect the rest of the gradient estimator through shared parameters. A simple unbiased correction, at no extra oracle cost, can still reduce its variance by an arbitrarily large factor. Motivated by this, we then prove that the residual variance can be decomposed exactly by actions with no cross terms. This decomposition yields a closed-form variance-minimizing correction for neural-network parameters, which can be computed by a simple projection. Empirically, our correction consistently reduces the variance left by the value function and improves learning across all tasks. The source code for all experiments is available at https://github.com/Zihao-Kevin/black_box_opt.

Figures & tables

	REINFORCE	Exact local marg.	Learned surrogate	Ours
Black-box oracle calls	${\mathcal{O}}(1)$	${\mathcal{O}}(dV)$	${\mathcal{O}}(1)$	${\mathcal{O}}(1)$
Unbiased gradient	✓	✓	×	✓
Variance of estimator	High	Low	Low	Variance-optimized †
Credit assignment	Uniform	Customized	Customized	Customized

Table 1: Trade-offs for optimizing discrete predictions through an expensive black-box oracle.

d

is the number of actions and

V

the number of values each action can take. † Variance-optimal within the realizable family of Theorem 4.5 .

Figure 1: Variance across decisions in the LLM MCP task at different stages of training. The

x

-axis indexes the 4 decision slots, and the

y

-axis reports the corresponding variance on a log scale. Solid curves use the true reward table, while dotted curves use the fitted reward model.

Figure 2: Training performance on three black-box tasks. We compare our methods with baselines. The exact gradient curve shows training with the exact gradient of the expected black-box objective and is included only as an oracle reference.

Figure 3: More offline data improves the fitted reward model and strengthens variance reduction.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Family	Generation rule
Uniform	Uniform random machine permutation per job; durations uniform in $1$ – $99$ .
Bottleneck	As Uniform, but multiply durations on one uniformly chosen machine by $4$ .
Heterogeneous	Uniform routes; durations uniform in $1$ – $25$ , multiplied by a shared per-job factor uniform in $\{1,2,4\}$ and by a further $4$ independently with probability $0.15$ per operation.
Correlated routes	One shared uniform random route, with $\max(1,\lfloor m/5\rfloor)$ uniformly sampled swaps of distinct positions per job; durations uniform in $1$ – $99$ .

Appendix

Table 2: Synthetic job-shop families. Integer ranges are inclusive; draws are independent except for the shared quantities specified below.

Variance Reduction

Variance reduction develops methods that make Monte Carlo estimates, gradients, and experimental comparisons more precise with limited data or computation.

See all 107 papers

On the Variance of Temporal Difference Learning and its Reduction Using Control Variates
Jun 18, 2026Hsiao-Ru Pan, Bernhard SchölkopfValue Function Estimation Temporal-Difference Learning
Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich
Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards
Oct 11, 2026Yibo Wang, Yuanxin Liu, Zhaoran WangReinforcement Learning with Verifiable Rewards Policy Gradient Methods
ABC: Advantage-Based Control Variates for Reinforcement Learning with Verifiable Rewards
Sep 28, 2026Hsiao-Ru Pan, Florent Draye, Bernhard SchölkopfReinforcement Learning Actor-Critic Methods
MPI-IS · ELLIS Institute Tübingen

Jun 18, 2026J/K move · Enter open · S save

On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Hsiao-Ru Pan, Bernhard Schölkopf

Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich

Value Function Estimation Temporal-Difference Learning Variance Reduction

Open paper AskPDF arXiv

We analyze the variance of temporal difference (TD) learning using the phased setting with tabular representation, and show that one of the mechanisms behind its ability to reduce variance is by effectively aggregating over a larger number of independent trajectories. Based on this insight, we demonstrate that (1) the variance of TD is asymptotically bounded from above by Monte Carlo (MC) estimators, and (2) shorter horizon updates incurs less variance for a fixed number of samples. Beyond TD, we show that Direct Advantage Estimation (DAE), a method for estimating the advantage function, can be seen as a type of regression-adjusted control variate, which achieves a tighter bound on the variance compared to TD in the large-sample limit. Finally, we numerically illustrate the behaviors of these estimators with carefully designed environments.

Abstract

Variance Reduction

Explore similar work

On the Variance of Temporal Difference Learning and its Reduction Using Control Variates

Variance-Optimal State Resampling for Reinforcement Learning with Verifiable Rewards

ABC: Advantage-Based Control Variates for Reinforcement Learning with Verifiable Rewards