  In empirical game-theoretic analysis (EGTA), game models are extended
iteratively through a process of generating new strategies based on learning
from experience with prior strategies. The strategy exploration problem in EGTA
is how to direct this process so to construct effective models with minimal
iteration. A variety of approaches have been proposed in the literature,
including methods based on classic techniques and novel concepts. Comparing the
performance of these alternatives can be surprisingly subtle, depending
sensitively on criteria adopted and measures employed. We investigate some of
the methodological considerations in evaluating strategy exploration, defining
key distinctions and identifying a few general principles based on examples and
experimental observations. In particular, we emphasize the fact that empirical
games create a space of strategies that should be evaluated as a whole. Based
on this fact, we suggest that the minimum regret constrained profile (MRCP)
provides a particularly robust basis for evaluating a space of strategies, and
propose a local search method for MRCP that outperforms previous approaches.
However, the computation of MRCP is not always feasible especially in large
games. In this scenario, we highlight consistency considerations for comparing
across different approaches. Surprisingly, we find that recent works violate
these considerations that are necessary for evaluation, which may result in
misleading conclusions on the performance of different approaches. For proper
evaluation, we propose a new evaluation scheme and demonstrate that our scheme
can reveal the true learning performance of different approaches compared to
previous evaluation methods.
