Convergence of Multi-Agent Learning with a Finite Step Size in General-Sum Games

Understand

Learning in a multi-agent system is challenging because agents are simultaneously learning and the environment is not stationary, undermining convergence guarantees.

• To address this challenge, this paper presents a new gradient-based learning algorithm, called Gradient Ascent with Shrinking Policy Prediction (GA-SPP), which augments the basic gradient ascent approach with the concept of shrinking policy prediction.
• The key idea behind this algorithm is that an agent adjusts its strategy in response to the forecasted strategy of the other agent, instead of its current one.
• GA-SPP is shown formally to have Nash convergence in larger settings than existing gradient-based multi-agent learning methods.