Modular Value Function Factorization in Multi-Agent Reinforcement Learning

Loading...
Thumbnail Image
Journal Title
Journal ISSN
Volume Title
Perustieteiden korkeakoulu | Master's thesis
Date
2022-10-17
Department
Major/Subject
Machine Learning, Data Science and Artificial Intelligence
Mcode
SCI3044
Degree programme
Master’s Programme in Computer, Communication and Information Sciences
Language
en
Pages
58+2
Series
Abstract
Real-world problems with multiple actors require them to coordinate while making decisions independently from each other. Typically, the large dimensionality and high unpredictability of the environment hinder the handcrafting or planning of effective behaviors. Multi-agent Reinforcement Learning~(MARL) provides a framework for solving such problems by learning a parameterized policy for each agent that only depends on the state. Common approaches factorize the joint value function of into individual agent utilities enabling them to take independent decisions or learn complex interactions by modeling the utility or payoff functions of the underlying coordination graph. In this thesis, we discover the benefit of exploiting the connection between these two approaches. We propose to leverage the modularity of the embedded coordination graph by formulating the total utility as a sum of subteam mixings and prove that our modular factorization is able to cover the Independent-Global-Max~(IGM) class of joint utility functions. We suggest finding the closest disjoint approximation of non-divisible graphs via graph partitioning, the quality of which we evaluate with a novel value-based partitioning distance measure. We derive theoretical and empirical advantages of our method evincing its benefit over baselines in several one-shot games, designed to highlight the promise of our modular factorization methods.

Todellisen maailman ongelmat, joissa on useita toimijoita, edellyttävät, että ne koordinoivat toimintaansa ja tekevät päätöksiä toisistaan riippumatta. Tyypillisesti ympäristön moniulotteisuus ja arvaamattomuus estävät tehokkaan käyttäytymisen suunnittelun. Monitoimijainen vahvistusoppiminen tarjoaa kehyksen tällaisten ongelmien ratkaisemiseen oppimalla kullekin agentille parametrisoidun käytäntöfunktion, joka riippuu vain ympäristön tilasta. Tyypillisiä lähestymistapoja ovat yhteisen arvofunktion faktorointi yksittäisten agenttien hyötyfunktioiksi, ja tehtävän hyötyfunktion eksplisiittinen mallintaminen koordinaatiograafin avulla. Tässä opinnäytetyössä tutkimme, kuinka yhdistää nämä kaksi tutkimussuuntaa ja mitä hyötyä niiden yhdistämisestä on. Hyödynnämme tehtävän koordinaatiograafin modulaarisuutta esittämällä kokonaishyötyfunktion alaryhmien hyötyfunktioiden summaksi ja hajottamattomien graafien tapauksessa ehdotamme lähimmän hajotetun graafin löytämistä graafipartitiointimenetelmien avulla. Partitiointien laadun mittaamiseksi esittelemme uuden mittafunktion. Näytämme empiirisesti, kuinka modulaarisuuden hyödyntäminen nopeuttaa oppimista suurien toimijamäärien tapauksissa.
Description
Supervisor
Ilin, Alexander
Thesis advisor
D'Eramo, Carlo
Keywords
Multi-agent reinforcement learning, value function factorization, coordination graphs, centralizedtraining decentralized execution
Other note
Citation