acceptodds
Under review as a conference paper at ICLR 2027

Further Variance Reduction via Uncertainty Propagation and Heuristic Pathologies in the AIVAT Family of Techniques

Abstract

How should an agent's performance in a multiagent environment be evaluated when there is a limited sample size or a high cost of running a trial? The AIVAT family of variance reduction techniques was proposed to address this challenge by introducing unbiased low-variance estimators of agents' expected payoffs. An important component of AIVAT is a heuristic value function that discriminates between low- and high-value counterfactual histories. A notable gap in the literature is that there is little to no constraint or guideline on how the heuristic value function should be chosen or how uncertainty in its output should be handled. In our main contribution, we show how the heuristic uncertainty can be propagated to quantify the uncertainty of AIVAT estimates. It is then possible to further reduce the variance using inverse-variance weighted averaging, but AIVAT's unbiasedness guarantee may have to be sacrificed. In our secondary contribution, we parameterize the heuristic value function to highlight AIVAT's potential vulnerabilities: by directly applying gradient descent/ascent on the sample variance or the test statistic, a) the sample variance can be set pathologically low, and b) one can p-hack to draw a desired statistical conclusion. The key takeaway is that the heuristic value function should be fixed prior to observing the evaluation data! In our experiments, we use a dataset of poker and Goofspiel games to demonstrate our heuristic uncertainty and pathology results, with the former yielding a 43.0% reduction in the number of samples needed to draw statistical conclusions.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
variance reduction, agent evaluation, control variates, uncertainty propagation, heuristic value function

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_BcKDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

Evaluating a player’s performance can require many games because the observed results are noisy. This paper studies how uncertainty in heuristic predictions can help reduce this noise in AIVAT estimates. The proposed method gives more weight to estimates with lower predicted uncertainty. Experiments on poker and Goofspiel report lower standard errors. In particular, the authors estimate that the poker evaluation needs 43% fewer samples than uniform averaging with the same Gaussian process model. The paper also shows that choosing heuristics after seeing the evaluation data can lead to opposite conclusions about the same players. This finding highlights the need to fix the heuristic before using the data to evaluate performance.

Critical strengths

The paper addresses a useful problem: evaluating game-playing agents with fewer samples. It proposes a clear way to use uncertainty and reports lower standard errors in poker and Goofspiel. It also gives concrete examples showing how reusing evaluation data can produce misleading results, offering practical guidance for reliable evaluation.

Critical weaknesses

(i) The link between uncertainty in the heuristic and the actual variation across games is not fully justified. This leaves the statistical basis of the proposed weights unclear to me.

(ii) Although the paper acknowledges possible bias, its claim that Gaussian processes avoid this bias needs stronger support. Lower standard errors alone do not guarantee better accuracy.

(iii) I think the claim in lines 284–288 that Gaussian processes give unbiased weighted estimates appears incorrect without further assumptions. The following example also raises a concern about applying Proposition 1 to the proposed weights.

Consider the MIVAT special case with one chance event leading to three states, each with probability 1/31/3, followed by deterministic payoffs

u=(0,0,3),μ=E[u(Z)]=1.u=(0,0,3), \qquad \mu=\mathbb{E}[u(Z)]=1.

Suppose the GP model is fixed before evaluation and has posterior mean m=(0,0,0)m=(0,0,0) and covariance

Σ=diag⁡(7,7,1)\Sigma=\operatorname{diag}(7,7,1)

for the heuristic outputs at these states. This is a valid Gaussian distribution on a finite set of states. Using the posterior mean as the heuristic, the MIVAT estimate at state ii is

\qquad p=(1/3,1/3,1/3)^\top.$$ Let $e_i$ be the $i$th coordinate vector. The correction coefficient is $c_i=p-e_i$. Applying the paper's uncertainty propagation and weighting rules gives $$s_i^2=c_i^\top\Sigma c_i, \qquad (s_1^2,s_2^2,s_3^2)=(4,4,2), \qquad (w_1,w_2,w_3)=(1/4,1/4,1/2).$$ For independent game histories $Z_1,\ldots,Z_T$, the weighted estimate therefore satisfies, almost surely, $$\hat{\mu}_{T} = \frac{\sum_{t=1}^{T} w_{Z_t}\hat{v}(Z_t)}{\sum_{t=1}^{T} w_{Z_t}} \longrightarrow \frac{E[w_Z\hat{v}(Z)]}{E[w_Z]} = \frac{(1/2)\cdot 3}{1/4+1/4+1/2} = \frac{3}{2}.$$ Thus, the estimate converges to $1.5$, although the true expected payoff is $1$. The bias does not disappear as the sample size increases. The weighting can also increase sampling variance. With two independent games, the weighted estimate takes values $0$, $2$, and $3$ with probabilities $4/9$, $4/9$, and $1/9$, respectively. Hence, $$\mathbb{E}[\hat\mu_2]=\frac{11}{9}, \qquad \operatorname{Var}(\hat\mu_2)=\frac{104}{81}>1.$$ By comparison, uniform averaging gives $$\mathbb{E} \left[\frac{\hat v(Z_1)+\hat v(Z_2)}{2}\right]=1, \qquad \operatorname{Var} \left[ \frac{\hat v(Z_1)+\hat v(Z_2)}{2} \right]=1.$$ Could the authors explain which stated assumption rules out this example? In particular, why does the GP property cited in lines 284–288 guarantee unbiasedness when evaluating a fixed game? Why does Proposition 1 apply when the weights use uncertainty in the heuristic, rather than the sampling variance across games? If the intended guarantee instead averages over a Bayesian model of the game's payoffs, please state this explicitly and explain how it supports the experimental conclusions.
Questions for authors

As shown above in the Weekness

3 comments
AuthorsOpenReview ↗

Thank you for your review.

(i) The link between uncertainty in the heuristic and the actual variation across games is not fully justified. This leaves the statistical basis of the proposed weights unclear to me.

The link we propose is that the heuristic value function can have different confidence in its estimates (e.g., for poker, folded hands, showdown hands, big pots). In our poker experiments, we found that the hands that reached later stages received less weight, and the weights did not depend much on the pot size.

(ii) Although the paper acknowledges possible bias, its claim that Gaussian processes avoid this bias needs stronger support. Lower standard errors alone do not guarantee better accuracy.

The mean squared error is the variance plus the squared bias, so lowering the variance at the cost of small bias usually helps the estimator achieve higher accuracy. In our main experimental results on poker and Goofspiel, we demonstrated empirical evidence that our technique increases the accuracy.

See also our answer to your next question.

(iii) I think the claim in lines 284–288 that Gaussian processes give unbiased weighted estimates appears incorrect without further assumptions. The following example also raises a concern about applying Proposition 1 to the proposed weights.

Proposition 1 applies when the heuristic uncertainty reflects the actual variances of the estimates, which does not hold in the reviewer's example. In the example, the model is most confident where it is most wrong.

Proposition 2 in the paper predicts the reviewer's example: an asymptotic bias of 1/2. The zero-covariance property in Lines 284-288 holds under the Gaussian prior, i.e., on average over the model of the game's payoffs. For a fixed game, the estimator can still be biased, which is precisely the tradeoff we stated in our abstract. Proposition 2 at least gives the asymptotic bias, and we estimate and report it for every IVW result, in which we found the bias to be small in our main results.

We will sharpen the wording in the paper. In particular, we will tone down the remark after Proposition 2.

We hope the rebuttal adequately addresses your concerns.

Thank you for your response and for clarifying that the estimator can be biased for a fixed game. However, my main concerns remain. It is still unclear why uncertainty from the GP can be used as the variance across games, and therefore why Proposition 1 applies to the proposed weights. The explanation based on a Gaussian prior also needs a clear connection to the experimental setting. Moreover, lower reported standard errors and a small estimated bias do not provide enough evidence of better accuracy. So, I will keep my original score.

AuthorsOpenReview ↗

There still seems to be some misunderstanding about the main result (demonstrated better accuracy)

Thank you for your continued engagement!

It seems to us that there is still some misunderstanding regarding our accuracy results, as indicated by the reviewer writing "Moreover, lower reported standard errors and a small estimated bias do not provide enough evidence of better accuracy.". Accuracy can be quantified by the mean squared error of the estimator (which equals mathematically the variance plus the squared bias); in our paper, our estimator is shown to have higher accuracy. For poker, one can see this in Table 1: our 75^2 + 3^2 < 85^2 < 88^2. Analogously with the identical mathematical comparison, Table 5 shows that our technique has higher accuracy in the Goofspiel variants as well. We will spell this math out explicitly in the text for both tables in the final version of the paper so the reader does not have to do the math themselves; we take responsibility for not spelling it out explicitly in the submitted version. In summary, it seems that either the reviewer is misunderstanding this or we are missing something about what the reviewer is trying to say (e.g., perhaps the reviewer uses "accuracy" to mean something else than mean squared error of the estimator). Can you please help clarify? Or, if our response above helps clarify this, please consider increasing your overall score accordingly.

Thank you again for the discussion!

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

In this paper, the heuristic value function in AIVAT family for evaluation of agents in games is analyzed. Starting from the observation that the estimator is linear in the heuristic output, the paper has two contributions. If the games are aggregated by inverse variance weighing, it reduces the standard error of the estimated payoff, perhaps at the cost of introducing bias. On the other hand, the authors also show a interesting corner case of these heuristics. If they try giving each history its own heuristic and optimize it after seeing the evaluation data, then they are able to show that every player has both won and lost. They then conclude that the heuristic must be fixed before seeing the evaluation data.

Critical strengths
  1. The paper identifies uncertainty in heuristic value functions as an additional consideration in AIVAT based evaluation. It provides an affine formulation that makes covariance propagation tractable. The proposed weighting scheme is useful when reliable heuristic value functions are difficult to construct. The reported reduction in standard error suggests that the approach could be practically useful if its uncertainty estimates and bias properties are known.

  2. This is a clear demonstration of evaluation data leakage risk. The experiments show that optimizing the outputs against the evaluation data used for can produce very significant and contradictory conclusions. Making these pathological cases explicit is a useful caution for users of these variance reduced estimates.

Critical weaknesses

The main method can produce a biased result. IVW undersamples some hands relative to others, and the hands that are undersampled depend on the results themselves. That will shift the final win rate. So the smaller error bars might not be trustworthy.

Questions for authors

Which hands receive low IVW weights? If they are mostly big pots, the method may change what’s measured, not just reduce noise? i.e. even in the empirical setup there seems to be some existence of bias?

1 comment
AuthorsOpenReview ↗

Thank you for your review.

The main method can produce a biased result.

Using a biased estimator that nonetheless achieves lower variance is an accepted method in the field of statistics.

IVW undersamples some hands relative to others, and the hands that are undersampled depend on the results themselves. That will shift the final win rate. So the smaller error bars might not be trustworthy.

What the reviewer points out is a true feature of biased estimators in general, and we are clear about that in the paper. However, as we also discuss in the paper, we contend that it is unclear how a player could even play to manipulate such a weighting scheme, since the bias depends on the correlation between the IVW weights and the expected utility estimates. It would require them to play differently while predicting the confidence of the heuristic value function chosen by the evaluator in its outputs for different histories. Despite the possible bias, our technique can increase accuracy of an existing estimator by lowering the mean squared error, which may be desirable.

Which hands receive low IVW weights? If they are mostly big pots, the method may change what’s measured, not just reduce noise? i.e. even in the empirical setup there seems to be some existence of bias?

Interestingly, in poker, we found that the pot size does not have much of an impact on the IVW weights. Instead, the weights heavily depend on the stage of the game on which the hand ends: hands that reached later stages received less weight. In our poker result, the estimated bias was 3 mbb/h (as stated in the paper), which is tiny.

We will add these discussions to the paper.

We hope the rebuttal adequately addresses your concerns.

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

The paper extends existing techniques of variance reduction for estimating agents’ performance in extensive-form games. Compared to prior AIVAT family techniques, the introduced method focuses on generalized heuristic functions that are assumed to produce not only the estimated values but also a variance of the estimate. Using the fact that the AIVAT is affine in the heuristic outputs, the paper extends AIVAT by averaging the per-trial estimates with the well-established inverse-variance weighting (IVW), which puts less weight on estimates of higher variance. The paper then shows that such an estimate is not necessarily unbiased and gives the asymptotic value of such bias. In a simplified MIVAT setup, the experimental results on the Pluribus poker data show that IVW reduces the standard error of the mean when a Gaussian process regressor is used, but still lags behind AIVAT, which has an access to evaluated player’s policy. As a second contribution, the authors demonstrate that the heuristic function should be fixed before seeing the evaluation data to avoid sample-variance and t-statistic hacking, which in their experiments lets every player appear to both win and lose with tiny p-values.

Critical strengths

Exploring the effect of a heuristic function on the variance of the sample mean of an agent’s performance is interesting and points to a promising direction for future work in utilizing the uncertainty of self-play value functions to reduce the variance of AIVAT. This could make a real difference in the number of games needed for evaluation. Also, highlighting the need to be cautious about overfitting the value function on the game plays used for evaluation is appreciated. Finally, the paper is well-written and easy to follow.

Critical weaknesses

The first contribution is straightforward and its gains are limited. The method is mostly a direct application of IVW to AIVAT. Its main novelty is treating the heuristic value function v′v' as stochastic and propagating its variance through the affine form of AIVAT. Critically, the claimed 43%43\% reduction in the number of samples needed is measured against MIVAT-GPR with uniform weights, which performs even worse than no variance reduction at all (Tab. 1). Similarly, AIVAT-GPR with uniform weights is worse than the raw estimate in all three Goofspiel variants (Tab. 5). Thus, IVW is only shown to help heuristics that are close to or worse than no variance reduction, and its effect on strong heuristics remains unclear.

Inconsistent claims about bias. Section 3 argues that the IVW estimator is unbiased for the GPR value function and that “the same holds for other models in Appendix H”. Yet Tab. 4 reports an estimated bias of 80 mbb/h for MIVAT-BR and MIVAT-ARDR, about as large as their SE of 74. This inconsistency, which the paper does not address, suggests that the unbiasedness argument may not be sound.

Obvious second contribution. That the heuristic value function should be fixed before observing the evaluation data is standard practice, and the paper itself states that “we are unaware of existing AIVAT applications that violate this”. Thus, while the cautionary message is useful, the contribution is insufficient for a venue like ICLR.

Questions for authors
  • Does IVW help on top of full AIVAT with a stronger heuristic in Goofspiel?
  • Section 3 claims the estimator is unbiased for the Appendix H models, yet Tab. 4 reports bias for them. How do these fit together?
1 comment
AuthorsOpenReview ↗

Thank you for your review.

The first contribution is straightforward and its gains are limited.

Our technique is simple in the sense that it is a post-processing step that can potentially be applied to existing AIVAT estimators. To our knowledge, no prior work in the literature uses heuristic uncertainty, and the fact that extra-game-theoretical considerations can yield further variance reduction on top of AIVAT is a brand new class of result. Our technique is now the best variance-reduction technique for games, so it is the one that everyone should use. As such, we consider it very significant.

Critically, the claimed reduction in the number of samples needed is measured against MIVAT[/AIVAT]-GPR with uniform weights, which performs even worse than no variance reduction at all

The fact that the prior state of the art can fail miserably is actually the strongest motivation behind our work. We show that heuristic value functions that are poor to the point of being counterproductive can be made useful using our technique. This is important because good heuristic value functions are often hard to come up with. Also, we compare our estimator with MIVAT-WB, which successfully lowers variance and show that our estimator is more accurate than even this baseline.

Thus, IVW is only shown to help heuristics that are close to or worse than no variance reduction, and its effect on strong heuristics remains unclear. Does IVW help on top of full AIVAT with a stronger heuristic in Goofspiel?

In realistic evaluation settings beyond poker, the evaluator may only have access to poor heuristic functions, in which case we showed that IVW can achieve 2x - 5x reduction in the standard error on top of full AIVAT.

We will add new experiments with a stronger heuristic in the camera-ready version of the paper; based on our Proposition 1, we certainly expect that our technique helps there too. We plan to conduct those experiments by solving the game exactly and then adding artificial noise to the estimator. That way we can make the estimator as accurate as we want and we can vary its accuracy.

Inconsistent claims about bias [...] Section 3 claims the estimator is unbiased for the Appendix H models, yet Tab. 4 reports bias for them. How do these fit together?

As we mentioned, when using BR and ARDR for the heuristic value function, we had to make the assumption that Equation 4 reduces to Equation 5 due to the limitations of the model implementations we used. Making this assumption is unsafe, which is precisely the reason why we relegated the results of those experiments to the appendix. They were included in the appendix purely for the sake of curiosity and completeness.

That said, our main result using GPR does not make this assumption, and your observation does not hold for our main results. Our results using GPR should be considered to be the most representative of our technique.

We will sharpen the writing in the paper to make this clear by including the elaborations above.

Obvious second contribution. [...] while the cautionary message is useful, the contribution is insufficient for a venue like ICLR.

We believe our claim is in fact not so obvious. In the control-variate literature, which underlies the design of AIVAT/MIVAT, coefficients are routinely fitted on the very sample being evaluated (cf., Glasserman 2004, Ch. 4, cited in the paper). Additionally, as we pointed out, the unbiasedness results in the MIVAT paper are stated for "any" value function.

We also provide a novel interpretation of our pathology results involving adversarial heuristics. The fact that AIVAT can draw incorrect/targeted conclusions with extremely high confidence is very undesirable, given that AIVAT's goal is to provide an accurate low-variance estimator.

We believe these issues are well worth pointing out explicitly in the literature.

We hope this rebuttal adequately addresses your concerns.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.