  We tackle a fundamental problem in empirical game-theoretic analysis (EGTA),
that of learning equilibria of simulation-based games. Such games cannot be
described in analytical form; instead, a black-box simulator can be queried to
obtain noisy samples of utilities. Our approach to EGTA is in the spirit of
probably approximately correct learning. We design algorithms that learn
so-called empirical games, which uniformly approximate the utilities of
simulation-based games with finite-sample guarantees. These algorithms can be
instantiated with various concentration inequalities. Building on earlier work,
we first apply Hoeffding's bound, but as the size of the game grows, this bound
eventually becomes statistically intractable; hence, we also use the Rademacher
complexity. Our main results state: with high probability, all equilibria of
the simulation-based game are approximate equilibria in the empirical game
(perfect recall); and conversely, all approximate equilibria in the empirical
game are approximate equilibria in the simulation-based game (approximately
perfect precision). We evaluate our algorithms on several synthetic games,
showing that they make frugal use of data, produce accurate estimates more
often than the theory predicts, and are robust to different forms of noise.
