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

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.