Imperfect-Recall Abstractions with Bounds in Games
Imperfect-Recall Abstractions with Bounds in Games
复制标题
DOI：
10.1145/2940716.2940736
复制
发表时间：
2014-09
期刊：
影响因子：
--
通讯作者：
Christian Kroer;T. Sandholm
中科院分区：
文献类型：
--
作者：
Christian Kroer;T. Sandholm
不完美回忆抽象已成为不完美信息游戏中实际大规模均衡计算的领先范例。然而，人们对不完美召回抽象知之甚少，并且只知道对解决方案质量的弱算法特定保证。当在原始（完美回忆）游戏中实现时，我们为纳什均衡和在不完美回忆抽象中计算的近似自颤均衡开发了第一个通用的、与算法无关的解决方案质量保证。我们的结果是针对一类游戏，该游戏概括了先前已知的唯一一类不完美回忆抽象，并且已经获得了此类结果。此外，我们的分析在两种方式上更加严格，每种方式都可以导致解决方案质量误差范围呈指数级减少。然后，我们证明，对于满足某些属性的扩展形式游戏，计算单个游戏级别的边界最小化抽象的问题可简化为聚类问题，其中边界的增加是距离函数。这种减少导致了第一个具有解决方案质量界限的不完美召回抽象算法。我们继续展示抽象问题类别的划分。如果考虑抽象的所有信息集的收益都处于相同的规模，则输入形成一个度量空间，这会立即产生一个用于抽象的 2 美元近似算法。相反，如果不满足这个条件，我们表明输入不形成度量空间。最后，我们提供计算实验来评估抽象技术的实际用途。他们表明，在这种抽象上运行反事实后悔最小化会在原始游戏中产生良好的策略。
Imperfect-recall abstraction has emerged as the leading paradigm for practical large-scale equilibrium computation in imperfect-information games. However, imperfect-recall abstractions are poorly understood, and only weak algorithm-specific guarantees on solution quality are known. We develop the first general, algorithm-agnostic, solution quality guarantees for Nash equilibria and approximate self-trembling equilibria computed in imperfect-recall abstractions, when implemented in the original (perfect-recall) game. Our results are for a class of games that generalizes the only previously known class of imperfect-recall abstractions for which any such results have been obtained. Further, our analysis is tighter in two ways, each of which can lead to an exponential reduction in the solution quality error bound. We then show that for extensive-form games that satisfy certain properties, the problem of computing a bound-minimizing abstraction for a single level of the game reduces to a clustering problem, where the increase in our bound is the distance function. This reduction leads to the first imperfect-recall abstraction algorithm with solution quality bounds. We proceed to show a divide in the class of abstraction problems. If payoffs are at the same scale at all information sets considered for abstraction, the input forms a metric space, and this immediately yields a $2$-approximation algorithm for abstraction. Conversely, if this condition is not satisfied, we show that the input does not form a metric space. Finally, we provide computational experiments to evaluate the practical usefulness of the abstraction techniques. They show that running counterfactual regret minimization on such abstractions leads to good strategies in the original games.