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.
翻译:由最近两个玩家,零和游戏的解决和玩耍的成功驱动,游戏人工智能工作日益侧重于产生平衡战略的算法。然而,这种方法在产生普通和游戏或两个以上玩家的两种以上玩家的合格玩家方面效果不如在普通和游戏,零和游戏中产生两个以上玩家的合格玩家。一个吸引人的替代办法是考虑适应性算法,确保后视表现优于经修改的行为本可以取得什么。这种方法还导致游戏理论分析,但从共同学习动态而不是均衡因素代理行为产生的相关游戏中产生。我们制定并倡导在一般顺序决策环境中进行这种后视合理性构建学习。为此,我们重新审查广泛形式游戏中的介质平衡和偏差类型,从而获得更完整的理解和解决过去的错误。我们提出了一系列实例,说明文献中每种类型的平衡的独特优缺点和弱点,并证明没有任何可感性概念包含所有其他的相近性。在对偏差和平衡因素中,我们发展和倡导在总体顺序决策环境中进行这种偏差和平衡性学习。为此,我们重新审视广泛形式游戏的偏差和偏差类别,从而在C的直序中进一步理解,使C的逻辑上更趋直正反的逻辑上更趋直判法。