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

arXiv: https://arxiv.org/abs/2610.04766 · HTML: https://mlsanity.com/paper/2610.04766/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 3 Oct 2026.

## Builds on (most cited first, 30 of 30)

- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Understanding R1-Zero-Like Training: A Critical Perspective](https://mlsanity.com/paper/2503.20783/) (2025)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (2017)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Smart "Predict, then Optimize"](https://mlsanity.com/paper/1710.08005/) (2017)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Melding the Data-Decisions Pipeline: Decision-Focused Learning for Combinatorial Optimization](https://mlsanity.com/paper/1809.05504/) (2018)
- [Differentiation of Blackbox Combinatorial Solvers](https://mlsanity.com/paper/1912.02175/) (2019)
- [Decision-Focused Learning: Foundations, State of the Art, Benchmark and Future Opportunities](https://mlsanity.com/paper/2307.13565/) (2023)
- [Neural Variational Inference and Learning in Belief Networks](https://mlsanity.com/paper/1402.0030/) (2014)
- [Backpropagation through the Void: Optimizing control variates for black-box gradient estimation](https://mlsanity.com/paper/1711.00123/) (2017)
- [Implicit MLE: Backpropagating Through Discrete Exponential Family Distributions](https://mlsanity.com/paper/2106.01798/) (2021)
- [The Optimal Reward Baseline for Gradient-Based Reinforcement Learning](https://mlsanity.com/paper/1301.2315/) (2013)
- [Variational inference for Monte Carlo objectives](https://mlsanity.com/paper/1602.06725/) (2016)
- [Q-Prop: Sample-Efficient Policy Gradient with An Off-Policy Critic](https://mlsanity.com/paper/1611.02247/) (2016)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [Variance Reduction for Policy Gradient with Action-Dependent Factorized Baselines](https://mlsanity.com/paper/1803.07246/) (2018)
- [The Mirage of Action-Dependent Baselines in Reinforcement Learning](https://mlsanity.com/paper/1802.10031/) (2018)
- [MuProp: Unbiased Backpropagation for Stochastic Neural Networks](https://mlsanity.com/paper/1511.05176/) (2015)
- [DisARM: An Antithetic Gradient Estimator for Binary Latent Variables](https://mlsanity.com/paper/2006.10680/) (2020)
- [Rao-Blackwellized Stochastic Gradients for Discrete Distributions](https://mlsanity.com/paper/1810.04777/) (2018)
- [Gradient Estimation with Discrete Stein Operators](https://mlsanity.com/paper/2202.09497/) (2022)
- [Trajectory-wise Control Variates for Variance Reduction in Policy Gradient Methods](https://mlsanity.com/paper/1908.03263/) (2019)
- [Differentiable Sampling of Categorical Distributions Using the CatLog-Derivative Trick](https://mlsanity.com/paper/2311.12569/) (2023)
- [Score Function Gradient Estimation to Widen the Applicability of Decision-Focused Learning](https://mlsanity.com/paper/2307.05213/) (2023)
- [ARMS: Antithetic-REINFORCE-Multi-Sample Gradient for Binary Variables](https://mlsanity.com/paper/2105.14141/) (2021)
- [Double Control Variates for Gradient Estimation in Discrete Latent Variable Models](https://mlsanity.com/paper/2111.05300/) (2021)
- [The Optimal Token Baseline: Variance Reduction for Long-Horizon LLM-RL](https://mlsanity.com/paper/2602.07078/) (2026)

## Abstract (arXiv)

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.