【CMU博士论文】不完全信息博弈中的博弈决策学习动力学、均衡计算和复杂性，358页pdf

设计能够进行策略性推理并在信息不完整和对抗行为存在的情况下作出最优决策的机器，是人工智能的基本目标。在常态形式的博弈中，我们对博弈理论决策的理解已经相当先进。在这种策略性互动中，所有玩家一次性、同时地采取行动，从预定的有限集合中选择（可能是随机的）一个行动。相比之下，这篇论文关注的是更为现实的不完全信息扩展形式博弈，这是一种树形决策问题，决策者可能会面临多次决策，这些决策与观察到的关于以前的决策如何影响（部分隐藏且可能具有对抗性的）多智能体环境交错进行。本论文旨在解决这个领域已经认可的一些未解问题，并为不完全信息扩展形式博弈中的策略性、博弈理论决策提供坚实的理论和算法基础。我们强调以下贡献。

• 我们解决了长期以来的开放问题，即是否能通过有效的、非耦合的学习动态产生扩展形式的相关均衡，得出无条件的积极结果。 • 我们解决了在两人博弈中计算扩展形式完美均衡的复杂性问题，这是一个公认的开放问题，我们证明了它与纳什均衡的复杂性相匹配。 • 我们建立了具有最新 OT (log T /T) 收敛到粗相关均衡的学习动态，从而作为推论改进了常态形式博弈的已知界限。 • 我们发现了经典的乘法权重更新算法的内核化版本。这种算法引导粗相关均衡的学习动态产生了理论上最新的依赖于不完全信息博弈规模的结果。 • 我们给出了关于相关策略几何形状的基本结果，确定了新的重要博弈类别，其中最优（例如，福利最大化）的相关解决概念可以在多项式时间内计算，为扩展形式的相关性提供了积极的复杂性结果。 • 我们提供了第一个保证收敛到福利最大化相关解决概念的学习算法，并展示了它们在实证性能上的最新状态。 我们提供了最新的算法，这使得我们首次能够在具有多达五十亿终端状态的大型博弈中找到纳什均衡的精确摇摆手修正。 • 我们研究了在零和对抗团队博弈中计算最优团队策略的问题，并为这个设置提供了最新的算法和积极的复杂性结果。 • 我们提供了可以融合玩家模型的学习动态，以产生强大、适合人类的策略。这些动态是训练外交博弈人工智能的关键组成部分，外交博弈是一个涉及人类合作和竞争的7人游戏。