logo

You are here

Warning message

Attention! This event has already passed.

Solving Multi-Agent Sequential Decision Problems Using Learning Automata

Monday, 19 May, 2008 - 10:30
Campus: Brussels Humanities, Sciences & Engineering campus
Faculty: Science and Bio-engineering Sciences
D
2.01
Maarten Peeters
phd defence

Deze doctoraatsverhandeling behandelt de studie van het gedrag van hierarchische leerautomaten in sequentiele beslissingsproblemen.

In het eerste deel van de verhandeling gaan we in op het aspect exploratie. Eerst en vooral tonen we aan dat leerautomaten theoretisch verbonden zijn met policy gradient agenten. Verder tonen we hoe deze policy gradient agenten eenzelfde exploratie kunnen toepassen als de leerautomaten omdat de exploratie van leerautomaten in een multi-agent omgeving ook gegarandeerd convergeert naar een attractor van het beslissingsprobleem. Als we ons beperken tot agenten met 2 acties, dan is het mogelijk om het leerautomaten model theoretisch te verenigen is met de Boltzmann exploratie, een exploratie techniek die veel gebruikt wordt in multi-agent leeralgoritmen. Indien deze constraint echter niet geldt, dan kunnen we aantonen dat leerautomaten beter presteren dan de veelgebruikte Boltzmann functie met een dalende temperatuur.

Indien we leerautomaten samenvoegen tot een complexere structuur zoals een hierarchie kunnen we de exploratie verbeteren omdat de hierarchische leerautomaten geen garantie bieden om de optimale oplossing in een beslissingsprobleem te vinden. Hiervoor hebben we de Hierarchical Exploring Selfish Reinforcement Learners (HESRL) ontwikkeld. HESRL is bedoeld om onafhankelijke agenten goede of zelfs optimale oplossingen te laten leren in stochastische, gedistribueerde systemen. Het algoritme werkt door 2 fases onderling af te wisselen. In de eerste fase (de exploratie-fase) leren de agenten, onafhankelijk van elkaar, een goede oplossing. Hierna vindt een korte synchronisatie-fase plaats waarin de agenten onderhandelen over het uitsluiten van een actie om de zoekruimte te verkleinen. In deze verkleinde zoekruimte start dan een nieuwe onafhankelijke exploratie-fase, opnieuw gevolgd door een exploratie-fase, enz. Voor de synchronisatie-fase hebben we twee algoritmen ontwikkeld, het Top-Down en het Bottom-Up algoritme, die aangeven waar de uitsluitingen beginnen: van boven of van onder in de hierarchie. Gebaseerd op het Bottom-Up uitsluiten hebben we ook een versie van het algoritme ontwikkeld voor problemen waarin agenten hun persoonlijke voorkeuren niet samenvallen, genaamd periodic policies.

Het tweede deel van de doctoraatsverhandeling spits zich toe op hoe de performantie en de snelheid van hierarchische leerautomaten verhoogd kan worden door bootstrapping in het systeem te brengen. Traditioneel gebruiken hierarchische leerautomaten een Full Path update waarbij elke automaat geüpdate wordt met alle beloningen die over het gehele pad verzameld zijn. Bij deze manier van updaten daalt de performantie en snelheid van convergentie drastisch in functie van het aantal stappen dat genomen dient te worden alvorens het spel eindigt. Ook kunnen de leerautomaten enkel hun actieprobabiliteiten aanpassen indien het spel een expliciete eindtoestand bereikt heeft. Deze problemen hebben we opgelost in verschillende stappen. Eerst en vooral hebben we het Intermediate Rewards algoritme geïntroduceerd. Hierbij werden de leerautomaten niet langer geüpdate met alle beloningen van het gekozen pad maar enkel met de belongingen van de rest van het gekozen pad. Dit heeft tot gevolg dat de leerautomaten eigenlijk minder informatie ter beschikking hebben, maar de informatie die ze wel krijgen kunnen ze direct beïnvloeden en is dus relevanter als evaluatie van hun eigen gedrag. Het Intermediate Rewards algoritme heeft dezelfde convergentie garanties als de traditionele Full Path update. Echter, het algoritme heeft nog steeds nood aan een expliciete eindtoestand. Om dit probleem op te lossen hebben we het n-step algoritme geïntroduceerd voor hierarchische leerautomaten. Hierbij gaan de automaten geüpdate worden met de eerste n beloningen die de omgeving teruggeeft. Een laatste algoritme dat het geheel vervolledigt, maakt gebruik van eligibility traces waarbij de leerautomaten enkel onmiddellijke beloningen van de omgeving gaan gebruiken. Empirische studies tonen aan dat dit algoritme zowel qua convergentienauwkeurigheid als qua convergentiesnelheid beter presteren dan de andere technieken.

Tenslotte worden de periodische policies toegepast op een realistische applicatie. We tonen aan dat hierarchische leerautomaten, uitgebreid met sociale vaardigheden, faire oplossingen kunnen vinden in real-time, asynchrone controle en planning in een chemische batch productie. Deze toepassing toont enerzijds de robuustheid van het algoritme in onverwachte situaties en anderzijds dat lerende multi-agent systemen een goede oplossing kunnen bieden voor complexe problemen.