Hindsight rationality is an approach to playing general-sum games that prescribes no-regret learning dynamics for individual agents with respect to a set of deviations, and further describes jointly rational behavior among multiple agents with mediated equilibria. To develop hindsight rational learning in sequential decision-making settings, we formalize behavioral deviations as a general class of deviations that respect the structure of extensive-form games. Integrating the idea of time selection into counterfactual regret minimization (CFR), we introduce the extensive-form regret minimization (EFR) algorithm that achieves hindsight rationality for any given set of behavioral deviations with computation that scales closely with the complexity of the set. We identify behavioral deviation subsets, the partial sequence deviation types, that subsume previously studied types and lead to efficient EFR instances in games with moderate lengths. In addition, we present a thorough empirical analysis of EFR instantiated with different deviation types in benchmark games, where we find that stronger types typically induce better performance.
翻译:事后理性是玩普通和游戏的一种方法,它为个别行为主体规定了一组偏差的不回报学习动态,并进一步共同描述具有调解平衡的多种行为主体之间的理性行为。为了在顺序决策环境中发展后视理性学习,我们将行为偏差正规化为尊重广泛形式游戏结构的一般偏差类别。将时间选择的概念纳入反事实最小化(CFR),我们引入了广泛形式最小化(EFR)算法,实现任何特定行为偏差的后视合理性,其计算尺度与这套游戏的复杂程度十分接近。我们确定了行为偏差子集,即部分序列偏差类型,它包含先前研究过的类型,并导致中长游戏中高效的EFR实例。此外,我们还对基准游戏中不同偏差类型快速化的EFR(EFR)进行了透彻的经验分析,我们发现较强类型通常导致更好的表现。