Exploring Large Strategy Spaces in Empirical Game Modeling

Empirical analyses of complex games necessarily focus on a restricted set of strategies, and thus the value of empirical game models depends on effective methods for selectively exploring a space of strategies. We formulate an iterative framework for strategy exploration, and experimentally evaluate an array of generic exploration policies on three games: one infinite game with known analytic solution, and two relatively large empirical games generated by simulation. Policies based on iteratively finding a beneficial deviation or best response to the equilibrium among previously explored strategies perform generally well, although we find that some stochastic introduction of suboptimal responses can often lead to more effective exploration in early stages of the process.