Simultaneous Abstraction and Equilibrium Finding in Games
Simultaneous Abstraction and Equilibrium Finding in Games
复制标题
博弈中同时抽象和平衡寻找
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Noam Brown;T. Sandholm
解决可拓形式博弈的一个关键挑战是处理大的，甚至是无限的行动空间。在不完全信息博弈中，主要的方法是在一个更小的抽象版本的博弈中找到一个纳什均衡，这个博弈在每个决策点只包括几个行动，然后将解映射回原始博弈。然而，如果不首先解决博弈，就很难知道哪些动作应该包括在抽象中，并且如果不首先抽象它，解决博弈是不可行的。
我们介绍了一种方法，使行动在运行时添加到抽象的平衡发现相结合的抽象。这允许代理开始学习一个粗略的抽象，然后战略性地插入动作在当前抽象中计算的策略认为重要的点。该算法可以快速地将动作添加到抽象中，同时可以证明不必重新开始平衡查找。它使任何时候收敛到纳什均衡的完整的游戏，即使在无限的游戏。实验表明，它可以在运行的每一个阶段都优于固定的抽象：早期，它的改进速度与粗抽象中的平衡查找一样快，后来它收敛到一个比细粒度抽象中的平衡查找更好的解决方案。
A key challenge in solving extensive-form games is dealing with large, or even infinite, action spaces. In games of imperfect information, the leading approach is to find a Nash equilibrium in a smaller abstract version of the game that includes only a few actions at each decision point, and then map the solution back to the original game. However, it is difficult to know which actions should be included in the abstraction without first solving the game, and it is infeasible to solve the game without first abstracting it.
We introduce a method that combines abstraction with equilibrium finding by enabling actions to be added to the abstraction at run time. This allows an agent to begin learning with a coarse abstraction, and then to strategically insert actions at points that the strategy computed in the current abstraction deems important. The algorithm can quickly add actions to the abstraction while provably not having to restart the equilibrium finding. It enables anytime convergence to a Nash equilibrium of the full game even in infinite games. Experiments show it can outperform fixed abstractions at every stage of the run: early on it improves as quickly as equilibrium finding in coarse abstractions, and later it converges to a better solution than does equilibrium finding in fine-grained abstractions.