论文标题
游戏中没有重新学习
No-Regret Learning in Games is Turing Complete
论文作者
论文摘要
游戏是用于多代理机器学习设置的天然模型，例如生成对抗网络（GAN）。这些游戏中算法相互作用的理想结果被编码为游戏理论平衡概念，例如纳什和粗相关的平衡。由于直接计算平衡通常是不切实际的，因此通常旨在设计迭代融合到平衡的学习算法。越来越多的负面结果使人们对这个目标产生了怀疑，从非争论到混乱甚至任意行为。在本文中，我们在此列表中添加了强烈的负面结果：游戏中的学习正在完成。具体而言，我们证明了矩阵游戏中复制器动态的完整性，这是最简单的设置之一。我们的结果暗示了在游戏中学习算法的可及性问题的不可证明性，其中一种特殊情况正在确定平衡收敛。
Games are natural models for multi-agent machine learning settings, such as generative adversarial networks (GANs). The desirable outcomes from algorithmic interactions in these games are encoded as game theoretic equilibrium concepts, e.g. Nash and coarse correlated equilibria. As directly computing an equilibrium is typically impractical, one often aims to design learning algorithms that iteratively converge to equilibria. A growing body of negative results casts doubt on this goal, from non-convergence to chaotic and even arbitrary behaviour. In this paper we add a strong negative result to this list: learning in games is Turing complete. Specifically, we prove Turing completeness of the replicator dynamic on matrix games, one of the simplest possible settings. Our results imply the undecicability of reachability problems for learning algorithms in games, a special case of which is determining equilibrium convergence.
