AutoQD: Automatic Discovery of Diverse Behaviors with Quality-Diversity Optimization

Dit paper introduceert AutoQD, een theoretisch onderbouwde methode die Markov-beslissingsprocessen en random Fourier-features gebruikt om automatisch gedragsbeschrijvers te genereren voor Quality-Diversity-optimatie, waardoor diverse hoogpresterende beleidsregels kunnen worden ontdekt zonder handmatige domeinkennis.

De kern

AutoQD: De "Autonome Ontdekker" voor Robotgedrag

Stel je voor dat je een robot wilt leren lopen. Traditionele methoden proberen de robot één perfecte manier te leren om te lopen, alsof je een kind alleen maar leert om recht vooruit te lopen. Maar wat als de grond glad wordt? Of wat als de robot een been kwijtraakt? Dan faalt die ene "perfecte" manier.

Wat we eigenlijk nodig hebben, is een verzameling van verschillende manieren om te bewegen: lopen, huppelen, kruipen, of zelfs een unieke dans. Dit noemen we Quality-Diversity (Kwaliteit-Variatie). Het probleem is echter: hoe vertel je een computer welke verschillen er zijn?

Tot nu toe moesten mensen dit zelf uitzoeken. Ze moesten handmatig zeggen: "Kijk naar de voetafdrukken" of "Kijk naar de hoek van de knieën". Dit is als proberen een heel orkest te beschrijven door alleen naar de viool te kijken. Het kost veel tijd, vereist veel kennis, en je mist misschien wel de coolste instrumenten.

AutoQD is de oplossing. Het is een slim algoritme dat zelf leert wat "anders" is, zonder dat mensen hoeven te zeggen waar ze naar moeten kijken.

Hoe werkt het? (De Metafoor van de "Geestelijke vingerafdruk")

Stel je voor dat elke robotbeweging een unieke geestelijke vingerafdruk heeft. Als een robot loopt, laat hij een spoor achter in de wereld (welke delen van de grond hij aanraakt, hoe snel hij beweegt, etc.).

1. De Vingerprint (Occupancy Measure):
   AutoQD kijkt niet naar de robot zelf, maar naar het spoor dat hij achterlaat. In de wetenschap noemen ze dit een "occupancy measure". Het is alsof we een foto maken van alle plekken waar de robot geweest is. Twee robots die heel verschillend bewegen, zullen ook heel verschillende foto's van hun sporen hebben.

2. De Vertaler (Random Fourier Features):
   De computer kan deze foto's niet direct vergelijken; ze zijn te complex. AutoQD gebruikt een slimme truc (genaamd Random Fourier Features) om deze complexe foto's om te zetten in een simpele lijst met getallen. Je kunt dit zien als het vertalen van een ingewikkeld gedicht naar een simpele code. Deze code is de "vingerafdruk" van het gedrag.

3. De Kaartmaker (CMA-MAE & PCA):
   Nu hebben we duizenden robots met hun eigen code. AutoQD plakt deze codes op een grote kaart.

   • De Kaart: De computer zoekt automatisch de belangrijkste richtingen op deze kaart. Waar liggen de grootste verschillen? Misschien is de ene richting "hoe hoog je springt" en de andere "hoe snel je draait".
   • De Automatische Kompas: In plaats dat een mens zegt "kijk naar de knieën", maakt AutoQD zelf een kompas dat de meest interessante richtingen aangeeft. Het zorgt ervoor dat de robot probeert nieuwe plekken op de kaart te ontdekken die nog leeg zijn.

Waarom is dit zo cool?

• Geen Menselijke Vooroordelen: Mensen denken vaak in vaste patronen (bijv. "lopen"). AutoQD denkt niet zo. Het kan ontdekken dat een robot soms beter vooruit komt door op zijn buik te glijden of door op één been te springen. Het vindt verrassende oplossingen die een mens misschien nooit zou bedenken.
• Veiligheid in Verandering: Omdat AutoQD een hele bibliotheek van verschillende manieren om te bewegen verzamelt, is de robot klaar voor alles. Als de omgeving verandert (bijvoorbeeld: de robot moet over een modderige vloer), hoeft hij niet opnieuw te leren. Hij zoekt gewoon in zijn bibliotheek naar de strategie die het beste werkt op modder.
• Wiskundig Bewezen: De auteurs bewijzen met wiskunde dat hun methode echt de echte verschillen tussen gedragingen meet, en niet zomaar willekeurige getallen.

Het Resultaat

In hun experimenten lieten ze AutoQD los op verschillende robotproblemen (zoals een robot die moet huppelen, zwemmen of lopen).

• Vergelijking: Andere methoden die mensen handmatig moesten programmeren, of methoden die probeerden alleen maar "verschillend" te zijn zonder te kijken naar kwaliteit, faalden vaak.
• AutoQD: Deze vond duizenden manieren om te bewegen. Sommige waren heel efficiënt, andere heel raar, maar ze waren allemaal uniek.
• Adaptatie: Toen ze de robots in een nieuwe, moeilijke situatie zetten (bijvoorbeeld met meer wrijving), bleek dat de AutoQD-robots veel sneller en beter konden aanpassen dan de anderen. Ze hadden immers al een "backup-plan" voor bijna elke situatie in hun bibliotheek.

Kortom: AutoQD is als een creatieve regisseur die niet zegt "speel dit toneelstuk zo", maar de acteurs vrij laat om te improviseren, en dan zelf de beste, meest verschillende scènes verzamelt in een archief. Zo hebben we altijd een oplossing klaar, wat de situatie ook wordt.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "AutoQD: Automatic Discovery of Diverse Behaviors with Quality-Diversity Optimization", geschreven in het Nederlands.

Probleemstelling

Kwaliteit-Diversiteit (QD) optimalisatie-algoritmen zijn succesvol in het ontdekken van verzamelingen oplossingen die zowel hoog presteren als behavioraal divers zijn. Echter, traditionele QD-methoden, vooral binnen Reinforcement Learning (QD-RL), lijden onder een fundamentele beperking: ze zijn afhankelijk van handgemaakte behaviorale beschrijvers (Behavior Descriptors - BDs).

• Afhankelijkheid van domeinkennis: BDs zijn functies die beleidsstrategieën (policies) afbeelden op lage-dimensionale vectoren. Het ontwerpen hiervan vereist uitgebreide domeinkennis (bijv. contactpatronen van voeten voor een robot).
• Beperking van exploratie: Handgemaakte BDs beperken de exploratie tot vooraf gedefinieerde dimensies van diversiteit. Dit kan leiden tot het missen van interessante, onverwachte gedragsvariaties die buiten deze vooraf bepaalde ruimte vallen.
• Schalingsproblemen: Naarmate taken complexer worden, wordt het handmatig definiëren van relevante BDs steeds moeilijker en minder schaalbaar.

Het doel is dus een methode te vinden die automatisch en zonder domeinkennis betekenisvolle behaviorale beschrijvers genereert om diverse, hoogwaardige beleidsstrategieën te ontdekken.

Methodologie: AutoQD

De auteurs stellen AutoQD voor, een theoretisch onderbouwde aanpak die beleidsstrategieën automatisch vertaalt naar behaviorale beschrijvers via bezettingsmaten (occupancy measures).

1. Theoretische Basis: Bezettingsmaten en MMD

• Bezettingsmaten ($\rho_\pi$): In plaats van directe observaties te gebruiken, gebruikt AutoQD de bezettingsmaat van een beleid $\pi$. Dit is de verwachte, afgepaste frequentie van bezoeken aan state-action paren $(s, a)$. Onder standaard aannames in volledig waarneembare omgevingen bestaat er een één-op-één-correspondentie tussen een beleid en zijn bezettingsmaat, waardoor deze een volledige karakterisering van het gedrag vormt.
• Maximum Mean Discrepancy (MMD): Om verschillen tussen gedragspatronen te kwantificeren, gebruiken de auteurs de MMD. Dit is een metriek die de afstand tussen twee kansverdelingen (hier: de bezettingsmaten van twee verschillende beleidsstrategieën) meet.
• Random Fourier Features (RFF): Omdat de MMD met een Gaussische kern correspondeert met een oneindig dimensionale feature space, benaderen ze deze met Random Fourier Features. Dit zorgt voor een eindig-dimensionale embedding $\psi_\pi$ van het beleid.
  • De Euclidische afstand tussen deze embeddings benadert de MMD-afstand tussen de onderliggende bezettingsmaten.
  • Stelling 1: De auteurs bewijzen dat deze benadering convergeert naar de ware MMD-afstand naarmate het aantal gesamplede trajecten ($n$) en de embedding-dimensie ($D$) toenemen.

2. Het AutoQD Algoritme

Het algoritme werkt iteratief en combineert QD-optimalisatie met het verfijnen van de beschrijvers:

1. Embedding: Beleidsstrategieën worden geëvalueerd in de omgeving. De verzamelde trajecten worden omgezet in een embedding $\psi_\pi$ via de RFF-methode (Eq. 6 in het paper), waarbij alle state-action paren in een traject worden gewogen met de disconteringsfactor $\gamma$.
2. Projectie (cwPCA): Om de hoge-dimensionale embeddings bruikbaar te maken voor QD-algoritmen (die een discrete archive gebruiken), worden ze geprojecteerd naar een lage-dimensionale ruimte ($k \ll D$) met een affiene transformatie: $\text{desc}(\pi) = A\psi_\pi + b$.
   • De parameters $A$ en $b$ worden bepaald via Calibrated Weighted PCA (cwPCA).
   • Gewogen PCA: De PCA wordt uitgevoerd op de embeddings, gewogen op basis van hun fitness (opbrengst). Dit zorgt ervoor dat de belangrijkste gedragsdimensies die bijdragen aan hoogpresterende beleidsstrategieën worden benadrukt.
   • Calibratie: De output wordt geschaald naar het bereik $[-1, 1]$ om stabiele grenzen voor de QD-archive te garanderen.
3. QD-Optimalisatie: De gegenereerde beschrijvers worden gebruikt door CMA-MAE (een state-of-the-art blackbox QD-algoritme gebaseerd op CMA-ES). CMA-MAE zoekt naar diverse beleidsstrategieën die de "QD-score" maximaliseren (de som van de prestaties van alle unieke cellen in de archive).
4. Iteratie: Periodiek worden de embeddings uit de uitgebreide archive gebruikt om de cwPCA-projectie ($A$ en $b$) bij te werken, zodat de beschrijvers zich aanpassen aan de ontdekte gedragsruimte.

Belangrijkste Bijdragen

1. Automatische Generatie van BDs: Een methode ontwikkeld om behaviorale beschrijvers automatisch te genereren op basis van bezettingsmaten, zonder handmatige specificatie.
2. Theoretische Garantie: Een formele stelling (Theorem 1) die aantoont dat de afstand tussen de RFF-embeddings de ware MMD-afstand tussen bezettingsmaten betrouwbaar benadert, met een foutmarge die exponentieel afneemt met het aantal samples en de embedding-dimensie.
3. Iteratief Algoritme: Een algoritme dat QD-optimalisatie en het verfijnen van behaviorale beschrijvers afwisselt, waardoor het systeem zich kan aanpassen aan de ontdekte gedragsruimte.
4. Empirische Validatie: Uitgebreide experimenten die aantonen dat AutoQD diverse en hoogpresterende beleidsstrategieën kan ontdekken in complexe continue controle-taken.

Resultaten

De auteurs hebben AutoQD getest op zes standaard continue controle-taken uit de Gymnasium/MuJoCo bibliotheek (o.a. Ant, HalfCheetah, Walker2d, BipedalWalker) en vergeleken met vijf baselines (RegularQD, Aurora, LSTM-Aurora, DvD-ES, SMERL).

• Prestatiemetingen: AutoQD presteerde consistent beter dan de baselines op de Ground-Truth QD Score en de Quality-Weighted Vendi Score (qVS) in de meeste omgevingen.
  • Uitzondering: In HalfCheetah en Walker2d behaalde AutoQD niet de hoogste scores op alle metrieken. In HalfCheetah ontdekte het diverse, maar minder efficiënte "schuivende" bewegingen. In Walker2d concentreerde het zich te veel op de onderste gewrichten.
• Robuustheid en Adaptatie: Een cruciale test betrof de adaptatie aan veranderende dynamieken (wrijvingscoëfficiënt en massa).
  • AutoQD's populatie behield een hogere prestatie onder veranderende omstandigheden dan de baselines.
  • Het had de hoogste Area Under the Curve (AUC) voor adaptatie.
  • Figuur 4 toont aan dat AutoQD meer "succesvolle" beleidsstrategieën bevatte (die een hoge opbrengst behielden bij veranderde omstandigheden) dan andere methoden, vooral onder strikte criteria.
• Kwalitatieve Analyse: Visualisaties tonen dat AutoQD diverse bewegingspatronen ontdekt, zoals verschillende loopstijlen bij BipedalWalker en S-vormige bewegingen bij Swimmer, zonder dat deze vooraf waren gedefinieerd.

Betekenis en Conclusie

AutoQD opent nieuwe mogelijkheden voor open-ended learning en geautomatiseerde gedragsontdekking in sequentiële besluitvorming.

• Onafhankelijkheid van Domeinkennis: Het elimineert de noodzaak voor menselijke experts om gedetailleerde behaviorale beschrijvers te definiëren, wat de toepasbaarheid vergroot op complexe, onbekende domeinen.
• Theoretische Fundamente: Door te koppelen aan bezettingsmaten en MMD, biedt het een wiskundig onderbouwde manier om "gedrag" te definiëren, in tegenstelling tot eerdere methoden die vaak op heuristieken of proxy-objectieven (zoals state-reconstructie) leunden.
• Toekomstperspectief: Hoewel AutoQD momenteel wordt gebruikt met CMA-MAE, is het compatibel met andere QD-algoritmen. Toekomstig werk richt zich op het integreren met gradient-based QD-methoden en het toepassen op omgevingen met beeldgebaseerde observaties.

Kortom, AutoQD biedt een krachtig, theoretisch onderbouwd raamwerk voor het automatisch ontdekken van een breed scala aan hoogpresterende gedragingen in complexe omgevingen, wat essentieel is voor het bouwen van robuuste en adaptieve autonome systemen.