Stackelberg Equilibrium Approximation in General-Sum Extensive-Form Games with Double-Oracle Sampling Method

The paper presents a new method for approximating Strong Stackelberg Equilibrium in general-sum sequential games with imperfect information and perfect recall. The proposed approach is generic, i.e. does not rely on any specific properties of a particular game model. The method is based on iterative interleaving of the two following phases: (1) guided Monte Carlo Tree Search sampling of the Follower's strategy space and (2) building the Leader's behavior strategy tree for which the sampled Follower's strategy is an optimal response. The above solution scheme is evaluated on interception games played on graphs with respect to expected Leader's utility and time requirements. A comparison with two state-of-the-art exact methods for this genre of games shows that in vast majority of test cases our simulation-based approach leads to optimal Leader's strategies, while excelling both exact methods in terms of time scalability and much lower memory usage.