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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Steady Expansion Double Oracle for Extensive-Form Games

  • Bo Chen,
  • Quan Yuan,
  • Guiyang Luo,
  • Jinglin Li,
  • Yilin Liu,
  • Rui Pan,
  • Xingyi Li

摘要

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.