Convergence of Gradient Dynamics with a Variable Learning Rate
- Michael Bowling, University of Alberta
- Manuela Veloso
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 theWoLF (“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.
Citation
M. Bowling, M. Veloso. "Convergence of Gradient Dynamics with a Variable Learning Rate". International Conference on Machine Learning (ICML), Williams College, pp 27-34, June 2001.| Keywords: | |
| Category: | In Conference |
BibTeX
@incollection{Bowling+Veloso:ICML01,
author = {Michael Bowling and Manuela Veloso},
title = {Convergence of Gradient Dynamics with a Variable Learning Rate},
Pages = {27-34},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2001,
}Last Updated: April 24, 2007Submitted by AICML Admin Assistant
