Learning Dynamics and Reinforcement in Stochastic Games
dc.contributor.author | Holler, John | |
dc.date.accessioned | 2020-05-08T14:35:25Z | |
dc.date.available | NO_RESTRICTION | |
dc.date.available | 2020-05-08T14:35:25Z | |
dc.date.issued | 2020 | |
dc.date.submitted | 2020 | |
dc.identifier.uri | https://hdl.handle.net/2027.42/155158 | |
dc.description.abstract | The theory of Reinforcement Learning provides learning algorithms that are guaranteed to converge to optimal behavior in single-agent learning environments. While these algorithms often do not scale well to large problems without modification, a vast amount of recent research has combined them with function approximators with remarkable success in a diverse range of large-scale and complex problems. Motivated by this success in single-agent learning environments, the first half of this work aims to study convergent learning algorithms in multi-agent environments. The theory of multi-agent learning is itself a rich subject, however classically it has confined itself to learning in iterated games where there are no state dynamics. In contrast, this work examines learning in stochastic games, where agents play one another in a temporally extended game that has nontrivial state dynamics. We do so by first defining two classes of stochastic games: Stochastic Potential Games (SPGs) and Global Stochastic Potential Games (GSPGs). We show that both games admit pure Nash equilibria, as well as further refinements of their equilibrium sets. We discuss possible applications of these games in the context of congestion and traffic routing scenarios. Finally, we define learning algorithms that 1. converge to pure Nash equilibria and 2. converge to further refinements of Nash equilibria. In the final chapter we combine a simple type of multi-agent learning - individual Q-learning - with neural networks in order to solve a large scale vehicle routing and assignment problem. Individual Q-learning is a heuristic learning algorithm that, even in small multi-agent problems, does not provide convergence guarantees. Nonetheless, we observe good performance of this algorithm in this setting. | |
dc.language.iso | en_US | |
dc.subject | game theory | |
dc.subject | reinforcement learning | |
dc.subject | deep learning | |
dc.subject | learning in games | |
dc.subject | stochastic games | |
dc.title | Learning Dynamics and Reinforcement in Stochastic Games | |
dc.type | Thesis | |
dc.description.thesisdegreename | PhD | en_US |
dc.description.thesisdegreediscipline | Mathematics | |
dc.description.thesisdegreegrantor | University of Michigan, Horace H. Rackham School of Graduate Studies | |
dc.contributor.committeemember | Strauss, Martin J | |
dc.contributor.committeemember | Baveja, Satinder Singh | |
dc.contributor.committeemember | Leslie, David | |
dc.contributor.committeemember | Smith, Karen E | |
dc.subject.hlbsecondlevel | Mathematics | |
dc.subject.hlbtoplevel | Science | |
dc.description.bitstreamurl | https://deepblue.lib.umich.edu/bitstream/2027.42/155158/1/johnholl_1.pdf | |
dc.owningcollname | Dissertations and Theses (Ph.D. and Master's) |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.