💻 computer science

Active Reward Machine Inference From Raw State Trajectories

Dit artikel introduceert een methode om reward machines, die complexe multi-stap taken modelleren, direct te leren uit ruwe staatstrajecten zonder toegang tot beloningen of labels, en breidt dit uit naar een actief leerkader om de data-efficiëntie te maximaliseren.

Oorspronkelijke auteurs: Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Gepubliceerd 2026-04-10

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mohamad Louai Shehab, Antoine Aspeel, Necmiye Ozay

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een robot wilt leren een complexe klus te doen, zoals een magazijn beheersen. De robot moet eerst een pakketje oppakken, dan een gevaarlijk gebied vermijden en het pakketje uiteindelijk afleveren. Dit is geen simpele "ga naar links" opdracht; het is een verhaal met verschillende hoofdstukken.

In de wereld van robotica noemen we dit een Reward Machine (Beloningstelsel). Het is als een onzichtbare leidraad die de robot vertelt: "Je bent nu in hoofdstuk 1, als je dit pakketje pakt, ga je naar hoofdstuk 2."

Het probleem is meestal: Wie schrijft die leidraad?
Tot nu toe moesten mensen dit handmatig doen. Ze moesten elke stap, elke regel en elk "als-dan"-scenario opschrijven. Dat is lastig, foutgevoelig en tijdrovend. Wat als de robot zelf kan leren hoe het verhaal eruit ziet, alleen door te kijken naar hoe een expert het doet?

Dit artikel van Shehab en collega's geeft het antwoord: Ja, dat kan, zelfs als we niets anders hebben dan een video van de robot die loopt.

Hier is hoe het werkt, vertaald naar alledaagse taal:

1. Het Grote Raadsel: Kijken zonder te Kijken

Stel je voor dat je een film ziet van iemand die een puzzel oplost. Je ziet alleen hun handen die stukjes verplaatsen (de staten), maar je ziet niet:

Wat de puzzelstukjes eigenlijk voorstellen (geen labels).
Hoeveel punten ze krijgen (geen beloningen).
Welke "hoofdstuk" ze in zitten (geen knopen in de machine).

Je hebt alleen de beweging. De vraag is: Kunnen we de regels van de puzzel afleiden puur uit die bewegingen?

De auteurs zeggen: "Ja, maar we moeten slim zoeken." Als we gewoon alle mogelijke bewegingen bekijken, wordt het te veel werk (te veel data om op te slaan).

2. De Oplossing: De "Slimme Vraag" (Actief Leren)

Stel je voor dat je een detective bent die een verdachte probeert te ontmaskeren. Je kunt niet elke mogelijke vraag stellen aan elke mogelijke getuige (dat zou eeuwig duren). In plaats daarvan kies je de belangrijkste vragen.

De oude manier (Exhaustief): Je vraagt aan elke getuige wat ze hebben gezien, schrijft alles op in een gigantisch notitieblok en probeert dan de regels te vinden. Het notitieblok wordt zo groot dat je er niet meer in kunt.
De nieuwe manier (Actief Leren): Je kijkt naar de getuigen die het meest verwarring stichten. Je vraagt: "Als getuige A dit zegt en getuige B dat, wat gebeurt er dan?" Als het antwoord laat zien dat twee mogelijke theorieën over de regels niet kloppen, heb je die theorieën direct weggegooid.

De auteurs hebben een algoritme bedacht dat precies dit doet:

Het kijkt naar de bewegingen van de robot.
Het probeert een "regelspelletje" (een Reward Machine) te bouwen dat past bij die bewegingen.
Als er te veel mogelijke regelspelletjes zijn, vraagt het systeem specifiek om extra voorbeelden (trajecten) die de meeste verwarring wegnemen.
Hierdoor wordt de lijst met mogelijke antwoorden snel korter, zonder dat je alles hoeft op te slaan.

3. De Analogie: De Verborgen Landkaart

Stel je voor dat je in een stad loopt waar alle straten onbekend zijn. Je ziet een lokale die perfect door de stad loopt, maar je ziet geen borden.

Je ziet dat hij bij de bakker stopt, dan naar de postkantoor gaat, en dan een gevaarlijke steeg vermijdt.
Je weet niet dat "bakker" = "Pakket ophalen" of dat "steeg" = "Gevaar".
Maar door te kijken naar de volgorde, kun je een kaart tekenen.

Deze paper zegt: "We kunnen die kaart tekenen zonder dat we de namen van de plekken kennen." We weten alleen dat "Plek X" en "Plek Y" verschillende dingen zijn, omdat de lokale daar anders reageert.

4. Waarom is dit geweldig?

Geen handmatig werk: Robots hoeven niet meer door mensen te worden geprogrammeerd voor elke nieuwe taak. Ze leren het zelf door te kijken.
Snelheid en geheugen: De oude methodes probeerden alles te onthouden, wat leidde tot enorme computers die vastliepen. De nieuwe methode (Actief Leren) is als een slimme zoektocht: ze vragen alleen wat ze echt nodig hebben. In de tests van de auteurs bespaarde dit veel geheugen en was het twee keer zo snel.
Robuustheid: Het werkt zelfs als de robot soms een beetje slippt of als de omgeving niet perfect is.

Samenvatting in één zin

De auteurs hebben een slimme manier bedacht om robots te leren complexe taken te begrijpen door alleen te kijken naar hoe experts die taken uitvoeren, waarbij ze slimme vragen stellen om tijd en computerkracht te besparen, net als een detective die de waarheid vindt door de juiste vragen te stellen in plaats van alles te lezen.

Dit is een enorme stap voorwaarts voor robots die in de echte wereld moeten werken, waar we niet altijd tijd hebben om alles handmatig in te voeren.

Titel: Actieve Inferentie van Reward Machines vanuit Ruwe State Trajecten

Auteurs: Mohamad Louai Shehab, Antoine Aspeel, en Necmiye Ozay (Universiteit van Michigan en Onafhankelijk Onderzoeker).

1. Probleemstelling

Reward Machines (RM's) zijn automata-achtige structuren die het geheugen vastleggen dat nodig is voor het uitvoeren van multi-stadia taken in de robotica. Ze vertalen complexe, temporale taken naar een eindige toestandsautomaton, waarbij overgangen worden geactiveerd door hoog-niveau gebeurtenissen (proposities). Hoewel RM's krachtig zijn voor het synthetiseren van robotbeleid, is het handmatig specificeren van de onderliggende automaton en de bijbehorende labelfunctie (die ruwe toestanden koppelt aan hoog-niveau proposities) vaak arbeidsintensief en vatbaar voor fouten.

Bestaande methoden voor het leren van RM's vertrouwen vaak op:

Ground-truth labels of beloningen.
Vooraf gedefinieerde labelfuncties.
Actieve leerorakels die toegang hebben tot interne knopen van de machine.

Het kernprobleem dat dit paper adresseert, is het leren van een Reward Machine direct vanuit ruwe state-trajecten, zonder enige toegang tot:

Beloningen (rewards).
Labels of proposities.
De interne knopen of structuur van de machine.
Een vooraf gedefinieerde labelfunctie.

De uitdaging is dat dit probleem "ill-posed" is: er kunnen meerdere RM's bestaan die hetzelfde optimale beleid genereren. Het doel is dus om een minimale, beleid-equivalente RM te leren die consistent is met de waargenomen agentgedragingen.

2. Methodologie

De auteurs stellen een raamwerk voor dat bestaat uit drie hoofdbestanden: een theoretische analyse van voldoende data, een SAT-gebaseerde inferentie methode, en een actieve leerstrategie.

A. Formele Definitie en Equivalentie

Product MDP: De auteurs combineren een Markov Decision Process (MDP) met een Reward Machine via een labelfunctie $L$ . Dit creëert een product-MDP waar het optimale beleid $\pi^*_{Prod}$ wordt berekend.
History Policy ( $\pi_h$ ): Omdat de interne toestanden van de RM onbekend zijn, wordt het gedrag van de agent beschreven door een "history policy". Dit is een beleid dat alleen kijkt naar de geschiedenis van waargenomen toestanden ( $\tau$ ) en de huidige staat ( $s$ ), en niet naar de interne RM-knoop.
Beleid-Equivalentie: Twee gelabelde RM's worden als equivalent beschouwd als ze hetzelfde history-policy induceren voor een gegeven MDP. Het doel is om een RM te vinden die equivalent is aan de "ware" (ground-truth) RM.

B. SAT-gebaseerde Inferentie (Probleem 1)

Om de overgangsfunctie ( $\delta_u$ ) en de labelfunctie ( $L$ ) te leren, formuleren de auteurs het probleem als een Boolean Satisfiability (SAT) probleem.

Encodering: De overgangen en labels worden gecodeerd als binaire variabelen.
Negatieve Voorbeelden: Het kerninzicht is dat als twee trajecten $\tau$ en $\tau'$ leiden tot verschillende acties in het history-policy (d.w.z. $\pi_h(a|s, \tau) \neq \pi_h(a|s, \tau')$ ), dan moeten deze trajecten de RM naar verschillende knopen leiden. Dit vormt een "negatief voorbeeld" dat een constraint oplegt in de SAT-oplossing.
Voldoende Diepte ( $l^*$ ): De auteurs bewijzen (Propositie 1) dat er een kritieke diepte $l^* = |S| \cdot u_{max}^2$ bestaat (waarbij $|S|$ het aantal toestanden en $u_{max}$ het maximale aantal RM-knopen is). Zodra de history-policy tot deze diepte bekend is, zijn verdere trajecten niet nodig om de oplossingset te verkleinen; de SAT-probleemoplossing is dan volledig.

C. Actieve Uitbreiding (Active Extension)

Een groot probleem bij de SAT-methode is dat het aantal mogelijke trajecten exponentieel groeit met de diepte, wat leidt tot onoplosbare geheugen- en rekentijdproblemen.

Observatie: Niet alle trajecten zijn even informatief. Veel trajecten leiden tot dezelfde knopen in de RM en voegen geen nieuwe constraints toe.
Actieve Leerstrategie (Algorithm 1): In plaats van alle trajecten te enumereren, selecteert het algoritme actief specifieke trajectparen om te "queryen" (controleren op verschillen in het history-policy).
- Het algoritme kiest trajectparen die de huidige set van kandidaat-oplossingen het meest effectief splitsen (volume-removal).
- Het doel is om een paar te vinden waarbij ongeveer de helft van de kandidaat-RM's naar dezelfde knoop gaat en de andere helft naar een andere. Als dit paar een negatief voorbeeld blijkt te zijn, wordt de helft van de hypotheses verwijderd.
- Dit proces wordt iteratief herhaald totdat de oplossingset convergeert naar de ground-truth (tot op hernoeming).

3. Belangrijkste Resultaten

De methode werd getest in twee Grid World omgevingen:

Pick_n_drop: Een magazijntaak waarbij een robot een object moet oppakken, een veilige zone moet vermijden en het moet afleveren.
PatrolABCD: Een patrouilletaak waarbij kamers in een specifieke volgorde (A $\to$ B $\to$ C $\to$ D) moeten worden bezocht.

Kernresultaten:

Correcte Inferentie: Het algoritme slaagde erin om de ground-truth Reward Machine en de labelfunctie (tot op hernoeming van knopen en labels) te herstellen in beide taken.
Efficiëntie van Actieve Leer:
- In de "PatrolABCD" taak had een exhaustieve benadering (alle trajecten tot diepte 9) meer dan 414 miljoen negatieve voorbeelden, wat leidde tot een geheugenvraag van 24,76 GB.
- De actieve methode bereikte dezelfde oplossingset (tot op hernoeming) met slechts 0,292 miljoen negatieve voorbeelden en een geheugenvraag van 0,147 GB (een reductie van twee orden van grootte).
- De totale rekentijd werd met ongeveer 2x versneld (3544s vs 7185s) terwijl de methode doorging tot een diepere horizon (diepte 13 vs 9).
Convergentie: De actieve methode convergeerde in 100% van de trials naar de juiste oplossingset bij diepte 12 (voor pick_n_drop) en 96,6% bij diepte 13 (voor patrolABCD), terwijl een willekeurige baseline faalde om de oplossing te vinden zelfs bij diepte 20.

4. Bijdragen en Significantie

Technische Bijdragen:

Informatie-arme setting: Dit is het eerste werk dat zowel de labelfunctie als de Reward Machine leert puur vanuit ruwe state-trajecten, zonder enige voorafgaande symbolische kennis of observatie van beloningen.
Theoretische grens: Het bewijs van een voldoende diepte ( $l^*$ ) garandeert dat het probleem oplosbaar is met beperkte data.
Actieve leer voor automata-inferentie: De introductie van een volume-removal strategie specifiek voor het verkleinen van de hypothesis space van Reward Machines, wat de "curse of dimensionality" bij het enumereren van trajecten doorbreekt.

Significantie:

Autonomie: Het stelt robots in staat om de logische structuur van complexe, multi-stadia taken autonoom te ontdekken zonder menselijke tussenkomst bij het definiëren van regels.
Schaalbaarheid: Door de actieve query-strategie wordt het mogelijk om Reward Machines te leren in omgevingen waar een exhaustieve analyse van alle mogelijke paden computationeel onhaalbaar zou zijn.
Fundamenteel inzicht: Het werk draagt bij aan het begrip van waarom geheugen nodig is in sequentiële besluitvorming, specifiek voor het vastleggen van taakvooruitgang (task progress) in plaats van alleen epistemische onzekerheid.

Beperkingen en Toekomst:
Het huidige raamwerk gaat uit van discrete toestandsruimtes en vereist toegang tot het history-policy (of een schatting daarvan). Toekomstig werk richt zich op het schalen naar continue ruimtes, het integreren van perceptuele representaties (bijv. via diep leren) en het ontwikkelen van robuustheid tegen schattingsfouten in het beleid.