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
O(1)
O(dV)
O(1)
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,⌊m/5⌋) 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 develops methods that make Monte Carlo estimates, gradients, and experimental comparisons more precise with limited data or computation.
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.
Hsiao-Ru Pan, Bernhard Schölkopf
Max Planck Institute for Intelligent Systems, Tübingen · ELLIS Institute Tübingen · ETH Zürich
Reinforcement learning with verifiable rewards spends much of its rollout budget on states that yield no learning signal. We recast this as a question about the sampling distribution itself: under a fixed rollout budget, which distribution over states minimizes the variance of the policy-gradient estimator? The answer admits a closed-form Neyman allocation, μvarπ(s)∝dπ(s)σπ(s), which connects naturally to GRPO's group-relative advantage and induces an emergent reverse curriculum as the policy improves, with no externally imposed schedule. Building on this principle, we propose VSR (Variance-driven State Resampling), a plug-in modification to GRPO using a prefix replay buffer and a zero-cost variance proxy. On mathematical reasoning benchmarks and long-horizon agentic tasks (Sokoban, BabyAI), VSR outperforms GRPO and GiGPO on most benchmarks with fewer generated tokens per update.
Recent progress in reinforcement learning with verifiable rewards (RLVR) has highlighted the effectiveness of simple critic-free policy-gradient methods such as Group Relative Policy Optimization (GRPO). In contrast, actor-critic methods rely on learned value functions whose approximation error can introduce bias through commonly used advantage estimators such as temporal-difference error. Motivated by this observation, we revisit trajectory-level control variates through an advantage-value formulation, which we call Advantage-Based Control Variates (ABC). This formulation reveals that the covariance structure is closely related to the return decomposition used in Direct Advantage Estimation (DAE). Finally, we combine ABC with DAE into a single actor-critic algorithm and evaluate it in an offline-to-online RLVR setting, where the critic is first trained on previously collected trajectories and adapted during online learning. On mathematical reasoning tasks, ABC achieves performance competitive with GRPO using substantially fewer online optimization steps.