Distributed multi-agent learning under federated and competitive settings

Qin, Tiancheng

Permalink

https://hdl.handle.net/2142/124485 Copy

Description

Title

Distributed multi-agent learning under federated and competitive settings

Author(s)

Qin, Tiancheng

Issue Date

2024-02-13

Director of Research (if dissertation) or Advisor (if thesis)

Etesami, Rasoul

Doctoral Committee Chair(s)

Etesami, Rasoul

Committee Member(s)

• Srikant, Rayadurgam
• Shamma, Jeff
• Hu, Bin
• Uribe, Cesar A.

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Distributed Learning
• Federated Learning
• Stochastic Game

Abstract

In recent years, the landscape of artificial intelligence (AI) has undergone a transformative evolution, transitioning from traditional single-agent approaches to more sophisticated and collaborative frameworks. The convergence of distributed computing and multi-agent systems has given rise to the powerful and versatile field of distributed multi-agent learning, allowing multiple agents to collaboratively learn and adapt in complex and dynamic environments. This intersection of distributed computing and multi-agent systems has ushered in a new era of intelligent systems capable of tackling intricate problems that were once deemed insurmountable for a single entity. Among the various topics in the field, in this thesis, we focus on two that bear significant importance, namely, Federated Learning and Learning in Stochastic Games. Federated Learning represents a paradigm shift from traditional centralized models, offering a decentralized approach where model training occurs locally on individual devices or servers, and only aggregated updates are shared. This transformative technique not only preserves data privacy but also addresses the challenges posed by the growing volume and diversity of data in our interconnected world. On the other hand, moving further from a collaborative scheme to a potentially competitive one, stochastic games emerge as a powerful framework to model multi-agent decision-making under uncertainty. Unlike traditional games, where players operate in a deterministic environment, stochastic games embrace the inherent unpredictability of real-world scenarios, where chance events and the actions of other players shape the unfolding dynamics. This nuanced approach enables modeling a wide range of complex systems, from economic competitions and environmental negotiations to multi-agent robotic interactions. In this thesis, we first analyze the convergence rate of the local stochastic gradient descent (SGD) algorithm (also known as Federated Averaging), arguably the most well-known and widely-used distributed optimization algorithm for Federated learning. Our contributions can be divided into two categories: (i) analysis of the effect of local steps in the convergence rate of Local SGD and (ii) analysis of the convergence rate of Local SGD for over-parameterized models. After that, we move further to the competitive scheme of stochastic games. Specifically, we study a subclass of $n$-player stochastic games, namely, stochastic games with independent chains and unknown transition matrices, and propose a scalable and independent decentralized learning algorithm that is provably convergent to the set of $\epsilon$-Nash equilibrium policies.

Graduation Semester

2024-05

Type of Resource

Thesis

Copyright and License Information

Copyright 2024 Tiancheng Qin

Owning Collections