Steady Expansion Double Oracle for Extensive-Form Games
摘要
Large-scale Extensive-Form Games (EFG) play a crucial role in complex decision scenarios. The Counterfactual Regret Minimization (CFR)-based Extensive-form Double Oracle (XDO) algorithm can linearly solve large-scale EFGs. In practice, however, existing methods often expand policy population using policies that are still in the existing restricted game, so that the solution of the restricted game cannot solve the entire game, resulting in local optimality. We propose a Steady Expansion Double Oracle (SEDO) algorithm, which ensures steady policy population expansion in each iteration by constructing and solving unrestricted-restricted games, ultimately making the restricted game cover the entire game. Importantly, this expansion is achieved while maintaining a similar expected number of iterations as the traditional CFR-based XDO algorithm. Our experimental results in various tabular and neural environments demonstrate that SEDO significantly improves the effectiveness of policy population expansion and achieves lower population exploitability compared to the existing double oracle methods.