Strategy Exploration in Empirical Games

Empirical analyses of complex games necessarily focus ona 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 experimentallyevaluate an array of generic exploration policies on threegames: one infinite game with known analytic solution, andtwo relatively large empirical games generated by simulation. Policies based on iteratively finding a beneficial deviation or best response to the minimum-regret profile amongpreviously explored strategies perform generally well on theprofile-regret measure, although we find that some stochastic introduction of suboptimal responses can often lead tomore effective exploration in early stages of the process. Anovel formation-based policy performs well on all measuresby producing low-regret approximate formations earlier thanthe deviation-based policies.

Authors

• Patrick Jordan Yahoo!
• L. Julian Schvartzman
• Michael Wellman

Keywords

• Empirical game theory
• strategy exploration