Convergence of Gradient Dynamics with a Variable Learning Rate

Abstract

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. 1.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 43 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.