  Empirical game-theoretic analysis (EGTA) is primarily focused on learning the
equilibria of simulation-based games. Recent approaches have tackled this
problem by learning a uniform approximation of the game's utilities, and then
applying precision-recall theorems: i.e., all equilibria of the true game are
approximate equilibria in the estimated game, and vice-versa. In this work, we
generalize this approach to all game properties that are well behaved (i.e.,
Lipschitz continuous in utilities), including regret (which defines Nash and
correlated equilibria), adversarial values, and power-mean and Gini social
welfare. Further, we introduce a novel algorithm -- progressive sampling with
pruning (PSP) -- for learning a uniform approximation and thus any well-behaved
property of a game, which prunes strategy profiles once the corresponding
players' utilities are well-estimated, and we analyze its data and query
complexities in terms of the a priori unknown utility variances. We experiment
with our algorithm extensively, showing that 1) the number of queries that PSP
saves is highly sensitive to the utility variance distribution, and 2) PSP
consistently outperforms theoretical upper bounds, achieving significantly
lower query complexities than natural baselines. We conclude with experiments
that uncover some of the remaining difficulties with learning properties of
simulation-based games, in spite of recent advances in statistical EGTA
methodology, including those developed herein.
