Networked Game-Theoretical Learning in Autonomous Systems

Abstract

This thesis addresses the present-day challenges in multi-agent autonomous systems to develop a new generation of learning and optimization algorithms in the lack of perfect information. Multi-agent autonomous systems refer to modern technological systems having individual decision-makers, named as agents, interacting with each other and the outer environment. Game theory is a mathematical concept that defines strategic interactions among multiple decision-makers with selfish goals. Traditional game theory focuses on analyzing the solutions or final outcomes, generally referred to as equilibria, of these interactions. Our goal in this work is to design and analyze decentralized strategic learning algorithms that guarantee convergence to game solutions by using local and networked information. In the first part of the thesis, we concentrate on the development and analysis of robust and efficient communication protocols for decentralized best-response type algorithms in which agents take actions that maximize their expected payoffs computed with respect to their individual beliefs. The proposed communication protocols retain the convergence guarantees to pure Nash equilibria in weakly-acyclic games while reducing communication attempts. We verify the effectiveness of the proposed communication protocols on mobile autonomous teams solving the target assignment problem. The second part of the thesis considers the analysis of multi-agent systems in uncertain and dynamic environments. We first design a decentralized fictitious play (DFP) algorithm. In DFP, agents share information only with their current neighbors in a sequence of time-varying networks, keep estimates of other agents’ empirical frequencies, and take actions to maximize their expected utility functions computed with respect to the estimated empirical frequencies. We prove the con-vergence of the DFP to an approximate NE in near-potential games. Next, we propose a novel networked policy learning algorithm for Markov potential games. We show the convergence of parameterized policies to a first-order stationary point in expectation. We discuss the benefits of networked policies compared to independent (reward-based) learning via numerical experiments.