2001 ConvergenceofGradientDynamicswi

Subject Headings: Multi-Agent Learning Algorithm; WoLF Algorithm.

Notes

As multiagent environments become more prevalent we need to understand how this changes the agent-based paradigm. One aspect that is heavily affected by the presence of multiple agents is learning. Traditional learning algorithms have core assumptions, such as Markovian transitions, which are violated in these environments. Yet, understanding the behavior of learning algorithms in these domains is critical. Singh, Kearns, and Mansour (2000) examine gradient ascent learning, specifically within a restricted class of repeated matrix games. They prove that when using this technique the average of expected payoffs over time converges. On the other hand, they also show that neither the players’ strategies nor their expected payoffs themselves are guaranteed to converge. In this paper we introduce a variable learning rate for gradient ascent, along with the WoLF (“Win or Learn Fast”) principle for regulating the learning rate. We then prove that this modification to gradient ascent has the stronger notion of convergence, that is, strategies and payoffs converge to a Nash equilibrium.

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2001 ConvergenceofGradientDynamicswi	Michael H. Bowling Manuela M. Veloso			Convergence of Gradient Dynamics with a Variable Learning Rate						2001