Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games
Online Convex Optimization for Sequential Decision Processes and Extensive-Form Games
复制标题
DOI：
10.1609/aaai.v33i01.33011917
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Gabriele Farina;Christian Kroer;T. Sandholm
中科院分区：
文献类型：
--
作者：
Gabriele Farina;Christian Kroer;T. Sandholm
遗憾的最小化是解决大型广泛形式游戏的强大工具。最先进的方法依赖于在每个决策点最大程度地减少本地遗憾。在这项工作中，我们得出了一个新的框架，以最大程度地减少对顺序决策问题的最小化和广泛形式的游戏，并在每个决策点和一般凸面损失上都有一般紧凑型凸的集合，而不是先前的工作，而先前的工作是简单的决策点和线性损失。我们称我们的框架层层遗憾分解。它将CFR算法概括为更通用的设置。此外，我们的框架即使在已知的环境中也可以提供新的CFR证明，这是从分解多层遗憾的角度得出的，从而导致对算法的解释可以更简单。我们对凸紧组和凸损失的概括使我们能够为几个问题开发新的算法：正则顺序决策，零和零广泛的大型游戏中的正则NASH平衡，并计算近似广泛形式的完美平衡。我们的概括还导致了第一个遗憾的最小化算法，用于根据最小化当地遗憾计算降低正常形式的量子反应平衡。实验表明，我们的框架会导致算法以可与计算NASH平衡的反事实后悔最小化的最快变体相当的速率扩展，因此我们的方法导致了在极大的大型游戏中计算量子响应平衡的第一个算法。我们的（四边形）正则平衡发现的算法是比NASH平衡发现最快的算法快的数量级。这表明基于纳什均衡发现作为未来工作的降低正则化的降低，遗憾的是最小化算法。最后，我们证明我们的框架可以采用一种新型的可扩展对手剥削方法。
Regret minimization is a powerful tool for solving large-scale extensive-form games. State-of-the-art methods rely on minimizing regret locally at each decision point. In this work we derive a new framework for regret minimization on sequential decision problems and extensive-form games with general compact convex sets at each decision point and general convex losses, as opposed to prior work which has been for simplex decision points and linear losses. We call our framework laminar regret decomposition. It generalizes the CFR algorithm to this more general setting. Furthermore, our framework enables a new proof of CFR even in the known setting, which is derived from a perspective of decomposing polytope regret, thereby leading to an arguably simpler interpretation of the algorithm. Our generalization to convex compact sets and convex losses allows us to develop new algorithms for several problems: regularized sequential decision making, regularized Nash equilibria in zero-sum extensive-form games, and computing approximate extensive-form perfect equilibria. Our generalization also leads to the first regret-minimization algorithm for computing reduced-normal-form quantal response equilibria based on minimizing local regrets. Experiments show that our framework leads to algorithms that scale at a rate comparable to the fastest variants of counterfactual regret minimization for computing Nash equilibrium, and therefore our approach leads to the first algorithm for computing quantal response equilibria in extremely large games. Our algorithms for (quadratically) regularized equilibrium finding are orders of magnitude faster than the fastest algorithms for Nash equilibrium finding; this suggests regret-minimization algorithms based on decreasing regularization for Nash equilibrium finding as future work. Finally we show that our framework enables a new kind of scalable opponent exploitation approach.