acceptodds
Withdrawn from ICLR 2027

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

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

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 correctio} 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 [here](https://anonymous.4open.science/r/black_box_opt-B4C6/).

Primary area:
optimization
Keywords:
Control variates, action-dependent baseline, black-box optimization, variance reduction

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_MhLVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper observes that under shared parameters, the action-value baseline QQ is not vaiance-optimal for the sum of per-decision gradient contributions, and proposes a closed-form row-wise projection correction. Experiments on three black-box tasks show variance reduction and improved learning.

Critical strengths
  1. The core observation is that per-decision optimality is not equal to joint optimality under shared parameters.
  2. Lemma 4.3 gives a clean action-wise decomposition; Theorem 4.5 reduces the correction to simple row-wise projections, avoiding an extra network or covariance solve.
  3. The three tasks span continuous, discrete, and combinatorial settings, and Figure 1 directly tests the decomposition.
Critical weaknesses
  1. The abstract promises a “variance-optimal” correction, but Theorem 4.5 only guarantees optimality within a single row’s input span. The unrestricted optimum is explicitly just a benchmark (Remark A.3). This scope should be stated in the abstract, not buried in the appendix.
  2. The core observation—per-decision optimality ≠ joint optimality under shared parameters—is standard. Lemma 4.3 is a telescoping identity, and Theorem 4.5 is essentially an orthogonal projection onto a one-dimensional subspace. Corollary A.4 largely recovers known results [1], [2]. The contribution is useful, but the “framework” language overstates it.
  3. Algorithm 1 costs O(d∣V∣)\mathcal{O}(d|\mathcal{V}|) model evaluations per step and grows exponentially with dd unless continuations are enumerated or sampled. All experiments use exact enumeration (≤625 sequences), which is not the long-horizon LLM setting the paper invokes. The sampled variant appears in only one sentence (Remark A.5), with no experiments or variance analysis.
  4. RELAX performs surprisingly poorly in Figure 2, with no tuning details given. It is unclear how the exact gradient is computed for MCP and JobShop; if by enumeration, it is the full expectation, not an oracle. Learning gains are also reported only qualitatively, without final performance or AUC.
  5. Notation is inconsistent and there are some typo errors.

[1] Action-dependent Control Variates for Policy Optimization via Stein Identity [2] Evaluating the Variance of Likelihood-Ratio Gradient Estimators

Questions for authors

See weaknesses.

Reviewer_WfjyOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
1
Soundness
2
Read review
Paper summary

The paper analysis a particular variance reduction technique for control variates in policy gradient estimators in an autoregressive setup. The main contribution goes as follows. Rewriting the estimator with martingale differences (error sequence, using the autoregressive nature of the problem) a variance representation for the policy gradient sum is obtained (Lemma 4.3). A direct consequence is a variance representation for changed control variates (Theorem 4.4), which is optimised by the trivial noise-less estimator. The key idea is to use a parametric family of control variates and minimise over the parametric family the variance representation. Under sufficient assumptions (that ensure the use of projection remains unbiased) this can be done by performing an L2L^2-projection from the error-sequence towards the parametric family. The method is applied in a few toy examples, yielding convincing results.

Critical strengths
  1. The insight on coordinate wise vs. sequences of actions is interesting, even though perhaps not surprising. Ex 4.2 is instructive.
  2. The variance reduction approach through the variance decomposition is creative and seems to lead to good practical results. It is an interesting (but perhaps restrictive) insight that the projection step of a parameterised family onto the error sequence can give an unbiased estimator.
Critical weaknesses
  1. The mathematical writing is weak. It seems to be a new phenomenon in the age of AI that authors struggle to pin down the abstract idea behind concrete computations. Written properly in terms of standard probability theory (filtrations for the action sequence, Doob decomposition with martingale differences, conditional expectations as L2L^2-projections) the results are elementary, super short, and much more easy to write and read (but still interesting!). The paper only looks complicated because all quantities are written out and the laws behind the expectations are barely written rigorously.
  2. The theoretical results are oracle results (g^\hat g contains ff). In contrast, the algorithm uses sampled quantities f^\hat f. I am pretty sure one can also obtain sample bounds without assuming access to the oracle. At the very least this must be discussed in the paper.
  3. I am a bit sceptical about the estimation of f^\hat f in the algorithm. I fear the algorithm would require pretty large buffers D\mathcal D to have a reasonable estimate f^\hat f of ff. If the estimate is not sufficiently good, the estimator will actually have larger variance than REINFORCE. I doubt the algorithm would work with initially empty buffer, except in particularly simple situations. A discussion is missing.
  4. The authors should work on their writing and remove all compiling errors before submitting a paper to a (major!) conference!
Questions for authors
  1. How do you initialise the buffer?
  2. Remark A.3, Theorem 4.4: I guess this choice is not practical because it results in the original unknown gradient, not because ξ\xi is hard to compute.
  3. You use a particular NN structure and projection for Theorem 4.5. Can this be generalised?
  4. the ξ\xi involve the oracle Q, not estimated Q. The algorithm thus needs to estimate ξ\xi from data and then perform the projection towards an estimated gradient. This leads to a gap between theory and practice. Is it possible to derive sample bounds?
Reviewer_pdEVOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

In some settings, like reinforcement learning (RL), model updates approximate the gradient of a loss via an expectation involving a score function. These updates can be noisy without some kind of adjustment, and 'control variates' are usually introduced to address this issue.

The authors point out that a standard choice of control variate based on the action-value function is not generally variance-optimal when different decisions share model parameters. Although this choice minimizes the variance of each decision's gradient contribution individually, it may be arbitrarily suboptimal for the variance of their sum due to correlations between contributions. The authors derive a correction that they claim accounts for these correlations and minimizes the variance within a certain family of control variates.

Critical strengths

The issue the authors identify---the fact that parameter-sharing can change what control variate ought to be used in REINFORCE-like updates---is quite interesting. It is also interesting that they propose a concrete strategy to address it.

Critical weaknesses

This paper's biggest problem is that it is very hard to understand. The motivation is kind of unclear---although RL, and the use of oracles in non-RL settings, are presented as motivation, the paper seems to study an only tangentially related problem. The problem setting is also highly nonstandard, and it is not clear to me why the authors made various choices in both their theoretical formulation and numerical experiments. Was the setting made for mathematical tractability? If so, the authors should say so explicitly. More broadly, the authors should do a better job connecting the approach they actually take with existing work.

The paper's results would be more convincing if there were more, and more complex, numerical experiments. If it really is the case that the authors' method is best, they should see large improvements when applying it to problems with longer decision sequences and more complex action spaces. The nonstandard experiment settings make it difficult to evaluate whether the method actually works well.

Also, I am not totally convinced regarding the optimality of the authors' proposal, although I admittedly do not understand the details well. How does the proposed method compare to other related control variate constructions? Relatedly, the subspace projection step in Sec. 4.4 seems a bit ad-hoc.

Questions for authors
  1. Can the authors explain in more detail how the subspace projection step in Sec. 4.4 is optimal?
  2. Does the proposed method work on more realistic RL problems?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.