Performance-Driven Environment Abstraction with Multi-Timescale Learning

Technische Samenvatting: Prestatiegestuurde Omgevingsabstractie met Multi-Timescale Learning

Probleemformulering
Het artikel behandelt de uitdaging van besluitvorming in grootschalige Markov Beslissingsprocessen (MDP's) waarbij plannen direct in de oorspronkelijke toestandsruimte computationeel onhaalbaar is. Terwijl bestaande benaderingen vaak vertrouwen op informatie-theoretische compressie of structurele heuristieken die geometrische of topologische eigenschappen behouden, betoogt dit werk dat de juiste abstractie inherent taakafhankelijk is. De auteurs stellen een raamwerk voor van prestatiegestuurde toestandsabstractie. Het kerndoel is om een toestandsaggregatie (het partitioneren van de toestandsruimte in "supertoestanden") en een bijbehorende policy te vinden die de kwaliteit van de besluitvorming maximaliseren terwijl de representatiecomplexiteit wordt geminimaliseerd.

Een cruciale beperking in deze formulering is de Same-Action-Distribution (SAD)-beperking: alle toestanden binnen een enkele geaggregeerde supertoestand moeten dezelfde actieverdeling delen. Hoewel dit de zoekruimte voor de policy verkleint, introduceert het benaderingsfouten. Het papier streeft naar een balans tussen de complexiteit van de abstractie (aantal supertoestanden) en het prestatieverlies veroorzaakt door de SAD-beperking en de waarde-functie-approximatie.

Methodologie
De voorgestelde oplossing is een multi-timescale reinforcement learning raamwerk dat zowel de policy als een boomgestructureerde omgevingsabstractie gezamenlijk aanpast.

1. Theoretische Fundering:

   • De auteurs leiden een prestatie-grens af voor besluitvorming onder een vaste aggregatie. Deze grens scheidt de totale suboptimaliteit in twee afzonderlijke bronnen:
     • Waarde-functie-approximatiefout ($\epsilon_\Gamma$): De fout die voortvloeit uit het representeren van de optimale waarde-functie met stuksgewijs constante waarden over de supertoestanden.
     • Actie-delen-verlies ($\delta_\Gamma$): Het prestatieverlies dat specifiek wordt veroorzaakt door de SAD-beperking, voortvloeiend uit de niet-commutativiteit van maximalisatie en middeling (d.w.z. het afdwingen van een enkele actieverdeling voor een groep toestanden die optimaal gezien verschillende acties zouden vereisen).
   • Een berekenbare bovengrens wordt afgeleid op basis van de Bellman-residufout, die dient als een proxy voor de onbekende optimale waarde-functie.

2. Boomgestuurde Adaptieve Aggregatie:

   • De toestandsruimte wordt gerepresenteerd door een hiërarchische boom (specifiek quadtrees in de experimenten). Bladknopen van de boom definiëren de huidige supertoestanden.
   • Q-Estimatie: Om structurele wijzigingen te sturen, houdt het algoritme Q-waarde schattingen bij de bladknopen bij. Cruciaal is dat het ook schattingen bijhoudt voor de potentiële kinderen van expandeerbare knopen. Dit stelt het systeem in staat om het potentiële voordeel van het verfijnen van een regio te evalueren zonder zich volledig aan een expansie te verbinden.
   • Expansie- en Inklapcriteria:
     • Expansie (Verfijning): Een bladknote wordt uitgebreid als de geschatte winst in Q-waarde prestaties (door kinderen toe te staan unieke actieverdelingen te adopteren) groter is dan een drempelwaarde die bepaald wordt door de regularisatieparameter $\lambda$ en de kortingsfactor $\beta$.
     • Inklappen (Vergroving): Een ouderknote wordt ingeklapt als het samenvoegen van de kinderen niet resulteert in een significante daling van de prestaties ten opzichte van de kosten van het onderhouden van aparte knoten.
   • Multi-Timescale Learning: Het raamwerk opereert op drie tijdschalen:
     • Snelste: De geaggregeerde Actor-Critic actualiseert de policy en de waarde-functie voor de huidige vaste partitie.
     • Intermediair: Q-schattingen voor structurele updates worden verfijnd.
     • Langzaamste: De boomstructuur (partitie) wordt bijgewerkt op basis van de Q-schattingen. Dit zorgt ervoor dat de policy convergeert onder een quasi-statische abstractie voordat de structuur verandert.

Belangrijkste Bijdragen
Het paper identificeert drie primaire bijdragen:

1. Prestatiegrens: Een theoretische grens voor besluitvorming onder omgevingsabstractie die de waarde-approximatiefout expliciet scheidt van het verlies veroorzaakt door de SAD-beperking.
2. Q-waarde Gestuurd Criterium: Een principieel criterium voor het verfijnen en aggregeren van boomgestuurde abstracties, afgeleid van de theoretische analyse en geïmplementeerd via Q-waarde discrepanties.
3. Multi-Timescale Algoritme: Een verenigd leeralgoritme dat zowel de policy als de abstractiestructuur gezamenlijk aanpast, wat een continue herstructurering van de toestandsruimte mogelijk maakt om een balans te vinden tussen prestaties en complexiteit.

Resultaten
De methode werd geëvalueerd op discrete navigatietaken (grid worlds, mazes, Mars terrein kaarten) en een continue controle-taak (Mountain Car), waarbij het werd vergeleken met flat Actor-Critic, quantizer-gebaseerde hiërarchische Actor-Critic, en Conditional Abstraction Trees (CAT).

• Toestandscompressie: Het algoritme bereikte substantiële toestandscompressie (bijv. het reduceren van 1024 toestanden naar 232 supertoestanden in een 32x32 maze) terwijl de taakrelevante topologische structuren behouden bleven.
• Sample Efficiëntie en Snelheid: De voorgestelde Tree-AC-Replan variant (warm gestart met een eerder geleerde abstractie) vertoonde aanzienlijk snellere convergentie en replanning-mogelijkheden vergeleken met baselines, vooral wanneer taakparameters (zoals doellocaties) veranderden.
• Adaptiviteit: Het systeem slaagde erin zich aan te passen aan nieuwe taken door regio's nabij nieuwe doelen te verfijnen en regio's die geen hoge resolutie meer vereisten te vergroven.
• Trade-offs: Experimenten toonden een U-vormige relatie tussen de initiële boomdiepte en het aantal episodes dat nodig is om een doel-succespercentage te bereiken, wat wijst op een optimale intermediaire granulariteit voor initialisatie. De Pareto-front analyse liet zien dat de methode effectief de balans vindt tussen abstractiegrootte en policy-prestaties.

Betekenis en Claims
Het paper claimt dat de automatische constructie van hiërarchische representaties een fundamenteel onderdeel is van intelligentie. Door weg te bewegen van geometrie-behoudende abstracties naar prestatiegestuurde abstracties, adresseert het voorgestelde raamwerk de kloof in de bestaande literatuur waar abstracties vaak domeinspecifiek zijn of een gebrek hebben aan expliciete optimalisatie voor downstream taakprestaties.

De auteurs benadrukken dat hun aanpak theoretische garanties biedt met betrekking tot prestatieverlies, iets wat eerdere heuristiek-gebaseerde methoden misten. Het vermogen om de policy en de abstractiestructuur gezamenlijk te leren, stelt agenten in staat complexe taken te beheren terwijl ze adaptief blijven aan evoluerende omgevingen. Het werk suggereert dat dit raamwerk een stap is naar schaalbare autonomie waarbij plannen in de oorspronkelijke toestandsruimte onhaalbaar is, en biedt een mechanisme om de "resolutie" van het wereldmodel van de agent dynamisch aan te passen op basis van directe prestatiebehoeften.