Self-learning restriction-based governance of multi-agent systems

Oesterle, Michael

PDF
Michael Oesterle - PhD Thesis.pdf - Veröffentlichte Version
Download (7MB)

URN:	urn:nbn:de:bsz:180-madoc-675476
Dokumenttyp:	Dissertation
Erscheinungsjahr:	2024
Ort der Veröffentlichung:	Mannheim
Hochschule:	Universität Mannheim
Gutachter:	Stuckenschmidt, Heiner
Datum der mündl. Prüfung:	3 Juli 2024
Sprache der Veröffentlichung:	Englisch
Einrichtung:	Außerfakultäre Einrichtungen > Institut für Enterprise Systems (InES)
Lizenz:	Creative Commons Namensnennung 4.0 International (CC BY 4.0)
Fachgebiet:	500 Naturwissenschaften
Freie Schlagwörter (Englisch):	Multi-Agent System , Governance , Restriction , Machine Learning , Fairness
Abstract:	The purpose of this thesis is the scientific investigation of a specific form of governance for multi-agent systems: The dynamic restriction of action spaces for achieving a system-level objective. Governance in multi-agent systems addresses the well-known challenges associated with managing and coordinating the behavior of autonomous agents. Particularly in competitive systems, self-interested individual optimization often leads to outcomes that deviate from socially optimal results. There are two major existing approaches to solve this problem: Rewarding or sanctioning certain behaviors through monetary incentives (called reward shaping) or providing agents with special capabilities for cooperation (we call this approach cooperative capabilities). However, both approaches exhibit certain failure modes; reward shaping assumes inter-agent comparability of rewards and unlimited governance means, while cooperative capabilities require that the agents’ action policy can be altered and that agents actually want to cooperate. Another crucial factor that causes difficulties for existing governance approaches is fairness in the face of heterogeneous agents. This motivates a novel approach to multi-agent governance, based solely on restricting action spaces in reaction to observations of the system. Such governance does not need to know about or influence the agents’ inner workings, nor does it have to hand out rewards to steer agent behavior. As the prime example of "improvement through restriction", Braess’ Paradox--the fact that closing a road can improve traffic flow in a congested network—-, serves as a recurring illustration of the power of restriction-based governance. We develop a unified theoretical framework, called Action-Space Restricted Multi-Agent System (ARMAS), which can be applied to any system modeled as a Partially Observable Stochastic Game. In this model, we propose various governance learning mechanisms for subclasses of ARMAS since the general problem of learning an optimal governance policy—-being equivalent to Reinforcement Learning in non-stationary environments—-cannot be expected to admit an efficient solution. In addition to the learning algorithms, we propose an implementation of ARMAS, which is compatible with major multi-agent learning frameworks, and we evaluate our approach concerning efficacy and fairness in comparison to reward shaping. Our results demonstrate that restriction-based governance can indeed manage and coordinate the behavior of autonomous agents, leading to significant enhancements in social welfare compared to a baseline approach that does not employ action space restrictions, while avoiding problems associated with reward-based governance approaches.
Übersetzter Titel:	Selbstlernende restriktionsbasierte Steuerung von Multiagentensystemen (Deutsch)
Übersetzung des Abstracts:	Das Ziel dieser Dissertation ist die wissenschaftliche Untersuchung einer spezifischen Form der Steuerung von Multiagentensystemen: die dynamische Einschränkung von Aktionsräumen zur Erreichung eines systemübergreifenden Ziels. Governance im Kontext von Multiagentensystemen befasst sich mit den Herausforderungen, die mit der Steuerung und Koordination des Verhaltens autonomer Agenten verbunden sind. Insbesondere in wettbewerbsorientierten Systemen führt individuelle eigennützige Optimierung häufig zu Ergebnissen, die von sozial optimalen Resultaten abweichen. Es existieren zwei vorherrschende Ansätze zur Lösung dieses Problems: das Belohnen oder Sanktionieren bestimmter Verhaltensweisen durch monetäre Anreize (bekannt als Reward Shaping) oder die Ausstattung der Agenten mit speziellen Koordinationsfähigkeiten (wir nennen diesen Ansatz Cooperative Capabilities). Beide Ansätze weisen jedoch bestimmte Probleme auf; Reward Shaping setzt die Vergleichbarkeit von Belohnungen zwischen den Agenten sowie unbegrenzte Steuerungsmittel voraus, während Cooperative Capabilities erfordern, dass die Handlungsstrategien der Agenten geändert werden können und dass die Agenten tatsächlich kooperieren wollen. Ein weiterer entscheidender Faktor, der bestehende Steuerungsansätze erschwert, ist Fairness im Hinblick auf heterogene Agenten. Dies motiviert einen neuen Ansatz zur Steuerung von Multiagentensystemen, der allein auf der Einschränkung von Aktionsräumen als Reaktion auf Beobachtungen des Systems basiert. Eine solche Governance muss die interne Funktionsweise der Agenten nicht kennen oder beeinflussen, noch muss sie Belohnungen verteilen, um das Verhalten der Agenten zu steuern. Als Paradebeispiel für "Verbesserung durch Einschränkung" dient das Braess-Paradoxon – die Tatsache, dass das Sperren einer Straße den Verkehrsfluss in einem Netzwerk verbessern kann – wiederholt dazu, das Potential einer einschränkungsbasierten Steuerung zu illustrieren. Wir entwickeln ein einheitliches theoretisches Framework, genannt Action-Space Restricted Multi-Agent System (ARMAS), das auf jedes System angewendet werden kann, das als Teilweise Beobachtbares Stochastisches Spiel (Partially Observable Stochastic Game) modelliert wird. In diesem Modell konstruieren wir verschiedene Steuerungslernmechanismen für Subklassen von ARMAS, da das allgemeine Problem des Erlernens einer optimalen Steuerung – äquivalent zu Reinforcement Learning in nicht-stationären Umgebungen – nicht effizient lösbar sein dürfte. Neben den Lernalgorithmen zeigen wir eine Implementierung von ARMAS, die mit wichtigen Multiagenten-Lernframeworks kompatibel ist, und wir evaluieren unseren Ansatz hinsichtlich Wirksamkeit und Fairness im Vergleich zu Reward Shaping. Unsere Ergebnisse zeigen, dass die einschränkungsbasierte Governance das Verhalten autonomer Agenten tatsächlich koordinieren kann, was zu signifikanten Verbesserungen der sozialen Wohlfahrt im Vergleich zu einem Referenzansatz führt, der keine Handlungsraumeinschränkungen verwendet, und dabei Probleme ver- meidet, die mit belohnungsbasierten Steuerungsansätzen verbunden sind. (Deutsch)