On Gradient-Based Learning in Continuous Games
On Gradient-Based Learning in Continuous Games
复制标题
DOI：
10.1137/18m1231298
复制
发表时间：
2018-04
期刊：
影响因子：
--
通讯作者：
Eric V. Mazumdar;L. Ratliff;S. Sastry
中科院分区：
文献类型：
--
作者：
Eric V. Mazumdar;L. Ratliff;S. Sastry
我们从动态系统理论的角度出发，研究了基于梯度学习算法的竞争智能体的限制行为。具体地说，我们介绍了一个基于竞争梯度学习的通用框架，它允许我们分析广泛的学习算法，包括策略梯度强化学习、基于梯度的强盗和某些在线凸优化算法。我们证明了对于势博弈和一般和博弈，当代理采用基于梯度的学习算法时，他们将避免局部纳什均衡的一个不可忽略的子集。对于游戏中基于梯度的学习来说，这是一个非常负面的结果。我们的框架还揭示了在一般和博弈和零和博弈中收敛到非Nash策略的问题，这些策略与潜在的博弈无关，只因算法的选择而产生。策略的存在和频率可能解释了在零和游戏中使用梯度下降时遇到的一些困难(例如，训练生成性对抗网络)。最后，我们引入了一类新的对策，Morse-Smer对策，其梯度动力学对应于类梯度流。这门课包含了一大套常见的游戏。对于Morse-Smer对策，我们证明了基于竞争梯度的学习几乎必然收敛到极限环、纳什均衡或非纳什不动点。为了加强我们的理论贡献，我们提供了实证结果，这些结果突出了纳什均衡的频率，这些均衡几乎肯定是线性二次博弈中政策梯度所避免的。事实上，我们提出的经验结果表明，在五个随机抽样的线性二次博弈中，政策梯度几乎肯定会避免唯一的全局纳什均衡。
We study the limiting behavior of competitive agents employing gradient-based learning algorithms through the lens of dynamical systems theory. Specifically, we introduce a general framework for competitive gradient-based learning that allows us to analyze a wide breadth of learning algorithms including policy gradient reinforcement learning, gradient based bandits, and certain online convex optimization algorithms. We show that for both potential games and general-sum games, when agents employ gradient-based learning algorithms, they will avoid a non-negligible subset of the local Nash equilibria. This is a strongly negative result for gradient-based learning in games. Our framework also sheds light on the issue of convergence to non-Nash strategies in general-sum and zero-sum games which have no relevance to the underlying game, and arise solely due to the choice of algorithm. The existence and frequency of strategies may explain some of the difficulties encountered when using gradient descent in zero-sum games (e.g. to train generative adversarial networks). Finally, we introduce a new class of games, Morse-Smale games, for which the gradient dynamics correspond to gradient-like flows. This class encompasses a large set of commonly encountered games. For Morse-Smale games, we show that competitive gradient-based learning converges to either limit cycles, Nash equilibria, or non-Nash fixed points almost surely. To reinforce our theoretical contributions, we provide empirical results that highlight the frequency of Nash equilibria that are almost surely avoided by policy gradient in linear quadratic games. Indeed, we present empirical results that show that policy gradient almost surely avoids the unique global Nash equilibrium in one out of five randomly sampled linear quadratic games.