Multi-agent online decision making with imperfect feedback : theory and application
Abstract/Contents
- Abstract
- Data-driven decision making, lying at the intersection between learning and decision making, has emerged as an important paradigm for engineering, data science and operations research at large. This thesis considers one facet of data-driven decision making, where multiple agents engage in an online learning process and make sequential decisions using data that become available over time. More specifically, we consider a model of multi-agent online strategic decision making, in which the reward structures of agents are given by a general continuous game and the feedback information to each agent is imperfect in one or more ways: each agent's feedback may suffer from some combination of noise corruption, delays and loss. The thesis presents an in-depth inquiry into the last-iterate convergence to Nash equilibria in the presence of such imperfect feedback, when each agent utilizes a no-regret online learning algorithm to maximize its cumulative performance. Last-iterate convergence (i.e. convergence of the actual joint action of all agents) stands in contrast with the more traditionally-studied time-average convergence in the existing literature (i.e. convergence of the time-average of the historical joint actions) and provides a more relevant (albeit more challenging) metric for online decision making problems. Unfortunately, last-iterate convergence (particularly when imperfect feedback is present) is under-explored in the existing work in multi-agent online learning. Rising to this challenge, this thesis aims to bridge the existing gap by answering some of the open questions in this field. In particular, a key high-level insight this thesis aims to articulate is that a broad family of no-regret learning algorithms, known as online mirror descent, can be adapted in multi-agent learning to guarantee last-iterate convergence to Nash equilibria in a general class of games under severely imperfect feedback information. Further, using power control in wireless networks as a motivating application domain, this thesis then harnesses these adapted online learning algorithms and theoretical convergence results to design robust and low-overhead distributed algorithms that operate in realistic environments and that come with strong performance guarantees. In sum, this thesis contributes to the broad landscape of multi-agent online learning by, among other things, making clear that the ambitious agenda of last-iterate convergence is not out of reach and should be the new norm (rather than the exception) for judging an algorithm's performance. A second (at least equally important) perspective that the thesis contributes pertains to distributed algorithm design in control and/or optimization: the often more complex process of developing robust distributed algorithms to achieve a desired/optimal system state can be transformed into the static and often simpler process of designing a game. With this transformation, all the algorithms and convergence results in multi-agent online learning can be immediately harnessed to yield practical algorithms for the problem at hand. This viewpoint has the potential to simplify the algorithm designer's task, whatever domain it may be.
Description
| Type of resource | text |
|---|---|
| Form | electronic resource; remote; computer; online resource |
| Extent | 1 online resource. |
| Place | California |
| Place | [Stanford, California] |
| Publisher | [Stanford University] |
| Copyright date | 2019; ©2019 |
| Publication date | 2019; 2019 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Author | Zhou, Zhengyuan | |
|---|---|---|
| Degree supervisor | Bambos, Nicholas | |
| Thesis advisor | Bambos, Nicholas | |
| Thesis advisor | Glynn, Peter W | |
| Thesis advisor | Weissman, Tsachy | |
| Thesis advisor | Ye, Yinyu | |
| Degree committee member | Glynn, Peter W | |
| Degree committee member | Weissman, Tsachy | |
| Degree committee member | Ye, Yinyu | |
| Associated with | Stanford University, Department of Electrical Engineering. |
Subjects
| Genre | Theses |
|---|---|
| Genre | Text |
Bibliographic information
| Statement of responsibility | Zhengyuan Zhou. |
|---|---|
| Note | Submitted to the Department of Electrical Engineering. |
| Thesis | Thesis Ph.D. Stanford University 2019. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2019 by Zhengyuan Zhou
- License
- This work is licensed under a Creative Commons Attribution Non Commercial 3.0 Unported license (CC BY-NC).
Also listed in
Loading usage metrics...