Regret Circuits: Composability of Regret Minimizers
Regret Circuits: Composability of Regret Minimizers
复制标题
DOI：
--
复制
发表时间：
2018-11
期刊：
影响因子：
--
通讯作者：
Gabriele Farina;Christian Kroer;T. Sandholm
中科院分区：
文献类型：
--
作者：
Gabriele Farina;Christian Kroer;T. Sandholm
遗憾最小化是解决大规模问题的有力工具；它最近在大规模广泛形式的游戏解决中取得了突破性的成果。这是通过将单纯形遗憾最小化器组合成扩展形式博弈策略空间的整体遗憾最小化框架来实现的。在本文中，我们研究了遗憾最小化器的一般可组合性。我们推导出一种微积分，用于为复合凸集构建遗憾最小化器，这些复合凸集是通过对更简单的凸集进行保凸操作获得的。我们表明，较简单集合的局部遗憾最小化器可以与附加遗憾最小化器组合成复合集的聚合遗憾最小化器。作为一个应用程序，我们展示了可以从我们的框架轻松构建 CFR 框架。我们还展示了将减少（限制）操作纳入我们的框架的方法。其一，它们能够为具有可跨越决策点的一般凸策略约束的扩展形式博弈构建 CFR 泛化。
Regret minimization is a powerful tool for solving large-scale problems; it was recently used in breakthrough results for large-scale extensive-form game solving. This was achieved by composing simplex regret minimizers into an overall regret-minimization framework for extensive-form game strategy spaces. In this paper we study the general composability of regret minimizers. We derive a calculus for constructing regret minimizers for composite convex sets that are obtained from convexity-preserving operations on simpler convex sets. We show that local regret minimizers for the simpler sets can be combined with additional regret minimizers into an aggregate regret minimizer for the composite set. As one application, we show that the CFR framework can be constructed easily from our framework. We also show ways to include curtailing (constraining) operations into our framework. For one, they enables the construction of CFR generalization for extensive-form games with general convex strategy constraints that can cut across decision points.