Communication complexity as a lower bound for learning in games
Communication complexity as a lower bound for learning in games
复制标题
通信复杂性作为游戏学习的下限
DOI：
10.1145/1015330.1015351
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
T. Sandholm
中科院分区：
文献类型：
--
作者：
Vincent Conitzer;T. Sandholm
人工智能和机器学习社区中快速增长的研究机构致力于游戏中的学习，其中有多个具有不同兴趣的学习者。这项研究增加了经济学中关于游戏学习的更成熟的研究。部分由于领域的冲突，在这个领域对学习算法的要求有很大的不同。本文的目标是演示如何通信复杂性可以被用作所需的学习时间或成本的下限。因为这个下界不承担任何要求的学习算法，它是普遍的，适用于任何一组的要求下的学习algorithm.We的通信复杂性的各种解决方案的概念，从博弈论，即纳什均衡，迭代优势策略（严格和弱），向后归纳。这给出了可以用这种方法获得的游戏中学习的最小下限。
A fast-growing body of research in the AI and machine learning communities addresses learning in games, where there are multiple learners with different interests. This research adds to more established research on learning in games conducted in economics. In part because of a clash of fields, there are widely varying requirements on learning algorithms in this domain. The goal of this paper is to demonstrate how communication complexity can be used as a lower bound on the required learning time or cost. Because this lower bound does not assume any requirements on the learning algorithm, it is universal, applying under any set of requirements on the learning algorithm.We characterize exactly the communication complexity of various solution concepts from game theory, namely Nash equilibrium, iterated dominant strategies (both strict and weak), and backwards induction. This gives the tighest lower bounds on learning in games that can be obtained with this method.