Hindsight and Sequential Rationality of Correlated Play
Hindsight and Sequential Rationality of Correlated Play
复制标题
DOI：
10.1609/aaai.v35i6.16702
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Dustin Morrill;Ryan D'Orazio;Reca Sarfati;Marc Lanctot;James Wright;A. Greenwald;Michael H. Bowling
中科院分区：
文献类型：
--
作者：
Dustin Morrill;Ryan D'Orazio;Reca Sarfati;Marc Lanctot;James Wright;A. Greenwald;Michael H. Bowling
在最近两人零和博弈求解和博弈的成功推动下，游戏方面的人工智能工作越来越专注于产生基于均衡的策略的算法。然而，与两人零和博弈相比，这种方法在培养一般和博弈或两人以上博弈中的合格玩家方面效果不佳。一个吸引人的选择是考虑自适应算法，这些算法确保了事后的强大性能，而不是通过修改行为可以达到的效果。这种方法也导致了博弈论分析，但在相关的游戏中，产生于联合学习动力学，而不是均衡时的因数代理行为。我们发展并倡导在一般的顺序决策环境中学习的这种事后理性框架。为此，我们重新考察了扩展形式博弈中的中介均衡和偏差类型，从而获得了更完整的理解，并解决了过去的误解。我们提供了一组例子，说明了文献中每种类型的均衡的不同的优点和缺点，并证明了没有一个容易处理的概念包含所有其他的。这条探索路线的最终结果是定义了与反事实后悔最小化(CFR)家族中的算法相对应的偏差和均衡类，将它们与文献中的所有其他算法联系起来。更详细地研究CFR进一步导致了相关游戏中合理性的新递归定义，该定义以一种自然适用于事后评估的方式扩展了顺序合理性。
Driven by recent successes in two-player, zero-sum game solving and playing, artificial intelligence work on games has increasingly focused on algorithms that produce equilibrium-based strategies. However, this approach has been less effective at producing competent players in general-sum games or those with more than two players than in two-player, zero-sum games. An appealing alternative is to consider adaptive algorithms that ensure strong performance in hindsight relative to what could have been achieved with modified behavior. This approach also leads to a game-theoretic analysis, but in the correlated play that arises from joint learning dynamics rather than factored agent behavior at equilibrium. We develop and advocate for this hindsight rationality framing of learning in general sequential decision-making settings. To this end, we re-examine mediated equilibrium and deviation types in extensive-form games, thereby gaining a more complete understanding and resolving past misconceptions. We present a set of examples illustrating the distinct strengths and weaknesses of each type of equilibrium in the literature, and prove that no tractable concept subsumes all others. This line of inquiry culminates in the definition of the deviation and equilibrium classes that correspond to algorithms in the counterfactual regret minimization (CFR) family, relating them to all others in the literature. Examining CFR in greater detail further leads to a new recursive definition of rationality in correlated play that extends sequential rationality in a way that naturally applies to hindsight evaluation.