🤖 AI

Toward Learning POMDPs Beyond Full-Rank Actions and State Observability

Dit artikel presenteert een methode voor het leren van de expliciete transitie- en observatiematrices van een Partially Observable Markov Decision Process (POMDP) uit sequentiële data door gebruik te maken van spectrale benaderingen en tensorontbinding onder milde rang-aannames, wat agenten in staat stelt om voor diverse doelen te plannen terwijl wordt bewezen dat leren voorbij een specifieke staatspartitie theoretisch onmogelijk is.

Oorspronkelijke auteurs: Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

Gepubliceerd 2026-07-22

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Seiji Shaw, Travis Manderson, Chad Kessens, Nicholas Roy

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 probeert te leren navigeren door een spookachtig, pikdonker landhuis. Je kunt de kamers niet zien, maar je hoort gekraak, voelt tocht en botst tegen meubels aan. Elke keer dat de robot een stap zet, krijgt hij een klein aanwijzing over waar hij zich mogelijk bevindt. Dit is de wereld van "gedeeltelijk observeerbare" systemen: de agent (de robot) weet welke acties hij kan ondernemen en wat hij waarneemt, maar hij kent de ware kaart van het huis niet en weet ook niet precies waar hij op elk gegeven moment staat. Om slim te kunnen handelen, moet de robot een mentaal model van deze verborgen wereld opbouwen. Decennialang hebben wetenschappers manieren ontwikkeld om dit model te raden, maar ze liepen vaak tegen een muur aan: de modellen die ze bouwden waren als "black boxes". Ze konden wel voorspellen wat er hierna zou gebeuren, maar ze konden niet uitleggen waarom of gemakkelijk hun plannen aanpassen als het doel veranderde (zoals overschakelen van "zoek de kat" naar "zoek de schat").

Dit artikel pakt dat black box-probleem aan. De onderzoekers, werkend bij MIT en het Army Research Laboratory, wilden agenten leren om de werkelijke "spelregels" te leren—de specifieke kansen om van de ene verborgen kamer naar de andere te bewegen en de specifieke aanwijzingen die elke kamer afgeeft. Ze richten zich op een speciaal soort wiskundige puzzel genaamd een POMDP (Partially Observable Markov Decision Process). Denk aan een POMDP als een bordspel waarbij je het bord niet kunt zien, alleen de dobbelsteenworpen en de stukken waar je op terechtkomt. Het doel is om de lay-out van het bord te ontdekken door het spel steeds opnieuw te spelen. De grote vraag die zij stellen is: Kunnen we de exacte lay-out van het bord leren kennen, zelfs wanneer sommige kamers van buitenaf precies hetzelfde lijken?

De belangrijkste ontdekking van het team is een slimme nieuwe manier om deze verborgen kaarten te leren, maar met een zeer belangrijke kanttekening. Ze ontdekten dat als de acties van de robot "full-rank" zijn (een chique manier om te zeggen dat de acties divers genoeg zijn om het systeem op te schudden en niet in lussen vast te lopen), de robot de ware kansen kan leren voor het bewegen tussen groepen kamers. Echter, ze bewezen dat als twee verschillende kamers voor elke mogelijke actie exact dezelfde aanwijzingen geven, de robot ze nooit uit elkaar kan houden door alleen maar rond te lopen. Het is als proberen het verschil te zien tussen twee identieke tweelingen die dezelfde kleding dragen en met dezelfde stem spreken; hoeveel vragen je ze ook stelt, je kunt nooit zeker weten welke welke is.

Dus, wat hebben ze eigenlijk gedaan? Ze combineerden twee bestaande wiskundige trucs. De eerste truc, genaamd Predictive State Representations (PSR), is erg goed in het voorspellen van de toekomst maar slecht in het verklaren van het verleden. De tweede truc, waarbij "tensor decomposition" wordt gebruikt, is als een hoogtechnologische detective die gemengde signalen kan scheiden om de oorspronkelijke bronnen te vinden. De auteurs realiseerden zich dat als ze de PSR-methode eerst gebruikten om een ruwe schets van de wereld te krijgen, ze vervolgens de tensor-methode konden gebruiken om die schets te "roteren" totdat deze overeenkwam met de werkelijke lay-out van de wereld.

Hier komt de magie: in veel realistische scenario's, zoals een robotarm die een kopje probeert op te pakken, kan de robot soms falen (glijden) of vaker slagen. Deze "rommelige" acties zijn eigenlijk nuttig omdat ze genoeg variatie creëren in de data om de wiskunde te laten werken. De auteurs toonden aan dat ze door deze full-rank acties te gebruiken, hun methode kan leren over de transitie- en observatiematrices (de spelregels) tot aan een "partitie". Dit betekent dat de robot leert dat "Kamer A en Kamer B in dezelfde groep zitten omdat ze identiek lijken," en hij leert de regels voor het bewegen tussen deze groepen. Als elke kamer een unieke vingerafdruk heeft, leert de robot de volledige kaart perfect kennen. Als sommige kamers tweelingen zijn, leert hij de kaart van de groepen kennen.

Het artikel sluit ook expliciet de mogelijkheid uit dat we ooit het exacte verschil tussen die "tweelingkamers" kunnen leren kennen met slechts één enkele reeks loopdata. Ze construeerden een wiskundig bewijs dat liet zien dat twee volkomen verschillende huislay-outs exact dezelfde sequentie van gekraak en botsingen kunnen produceren. Als de robot het verschil in de aanwijzingen niet kan waarnemen, kan hij het verschil in de kaart niet waarnemen. Dit is geen falen van hun algoritme; het is een fundamentele limiet van het universum.

In hun experimenten testten ze dit op verschillende digitale werelden, waaronder een "Tiger"-spel (waarbij een tijger achter een van de twee deuren zit) en een "Sense-Float-Reset"-domein (een robot die over een lijn beweegt). Ze ontdekten dat hun methode erin slaagde de juiste kansen te leren voor het bewegen tussen de "groepen" staten. Belangrijker nog, omdat ze de werkelijke spelregels leerden in plaats van alleen een black-box voorspeller, konden ze het doel van de robot aanpassen nadat het leren was voltooid. Bijvoorbeeld, ze konden de robot vertellen: "Ga nu naar de lawaaierige middelste kamer," en de robot kon uitzoeken hoe hij daar kwam met de kaart die hij al had opgebouwd. Eerdere methoden zouden het hele proces opnieuw moeten beginnen om een nieuw doel te leren.

De auteurs suggereren dat deze aanpak een belangrijke stap voorwaarts is voor robots die flexibel moeten zijn. Het stelt hen in staat om een model van de wereld te leren dat interpreteerbaar en herbruikbaar is. Ze merken echter voorzichtig op dat dit het beste werkt wanneer de robot over een divers pakket aan acties beschikt. Als de robot te onhandig is of de omgeving te statisch, kan de wiskunde de verborgen staten misschien niet scheiden. Ze wijzen er ook op dat hun huidige methode het beste werkt voor systemen met een klein aantal verborgen staten, aangezien de wiskunde erg zwaar wordt voor enorme, complexe werelden. Maar voor nu hebben ze laten zien dat we achter het gordijn van verborgen staten kunnen kijken, zolang we accepteren dat sommige tweelingen altijd ononderscheidbaar zullen blijven.

Technische Samenvatting: Naar het leren van POMDP's voorbij full-rank acties en staatsobservabiliteit

Probleemstelling
Het artikel behandelt de uitdaging om autonome agenten te laten leren en te redeneren over systemen met verborgen toestanden, waarbij deze systemen specifiek worden gemodelleerd als discrete Partially Observable Markov Decision Processes (POMDP's). De agent krijgt de actie- en observatieruimtes aangeboden, maar mist voorafgaande kennis van de toestandsruimte, de transitiedynamiek of de observatiemodellen. Het doel is om het aantal verborgen toestanden en de expliciete transitie- en observatiematrices te schatten op basis van een sequentie van acties en observaties die via willekeurige exploratie zijn verzameld.

Hoewel spectrale methoden zoals Predictive State Representations (PSRs) voldoende statistieken kunnen leren om toekomstige uitkomsten te voorspellen, fungeren zij als black-box modellen. Ze leveren geen expliciete transitie- en observatie-likelihoods op, wat het moeilijk maakt om het model te manipuleren voor nieuwe plannings-taken (bijv. het wijzigen van beloningsfuncties) zonder het hele systeem opnieuw te leren. Daartegenover staan bestaande tensor-decompositie-methoden voor het herstellen van volledige POMDP-modellen, die doorgaans steunen op strikte aannames: dat transitiematrices full-rank zijn en dat elke toestand een unieke observatiedistributie heeft voor elke actie. Deze aannames falen in veel real-world scenario's die te maken hebben met state aliasing (waarbij verschillende toestanden identieke observatiedistributies delen) of acties die probabilistisch kunnen mislukken.

Methodologie
De auteurs stellen een methode voor die spectrale decompositie combineert met tensor-decompositie om POMDP-parameters te leren onder mildere aannames. De aanpak verloopt in drie hoofdfasen:

Constructie van de Hankel-matrix en PSR-leren:
De methode begint met het construeren van een Hankel-matrix uit de geobserveerde actie-observatie-trajecten. Deze matrix codeert de gezamenlijke likelihoods van het verleden en de toekomst van observaties. Door een rang-factorisatie (via Singular Value Decomposition) op deze matrix uit te voeren, leidt het algoritme een lineaire Predictive State Representation (PSR) af. Dit levert een set lineaire update-matrices ( $M_{ao}$ ), een initiële vector ( $m_0$ ) en een finale vector ( $m_\infty$ ) op. Deze componenten vertegenwoordigen de systeemdynamica tot aan een onbekende gelijkenistransformatie $P$ .
Herstel van de gelijkenistransformatie:
Om de expliciete transitie ( $T^a$ ) en observatie ( $O_{ao}$ ) matrices te herstellen, moet het algoritme de gelijkenistransformatie $P$ schatten. De auteurs herformuleren tensor-decompositie-technieken om $P$ te schatten.
- Eerst worden observaties gemarginaliseerd om transitie-matrices te verkrijgen tot aan de transformatie: $\sum_o M_{ao} = P T^a P^{-1}$ .
- Voor acties met full-rank transitie-matrices wordt de product $M_{ao} M_a^{-1} = P O_{ao} P^{-1}$ berekend.
- Omdat $O_{ao}$ diagonaal zijn, komen de eigenwaarden van deze producten overeen met de diagonale elementen. Om ambiguïteit te doorbreken die wordt veroorzaakt door herhaalde eigenwaarden (wat voorkomt wanneer toestanden dezelfde observatiedistributies delen), gebruikt de methode een gezamenlijke diagonalisatie van een gewogen som van deze matrices. Willekeurige gewichten worden gesampled om ervoor te zorgen dat eigenwaarden bijna zeker verschillend zijn voor toestanden met unieke observatiedistributies over alle full-rank acties.
Leren tot aan observability-partities:
Het artikel introduceert het concept van een Full-Rank Observability Partition. Als meerdere toestanden exact dezelfde observatiedistributie delen voor alle acties met full-rank transities, kunnen zij niet van elkaar onderscheiden worden op basis van sequentiële data alleen. Het algoritme herstelt de gelijkenistransformatie $P$ tot aan deze partitie. Bijgevolg levert het geleerde model expliciete transitie- en observatiematrices tussen partities van toestanden in plaats van individuele toestanden. Voor toestanden binnen een enkele partitie leert het model de geaggregeerde dynamica.

Belangrijkste bijdragen

Verzachte aannames: De methode breidt tensor-decompositie-benaderingen uit naar het leren van POMDP's waarbij toestanden gealiased kunnen zijn (het delen van observatiedistributies) en waar transitie-matrices niet noodzakelijkerwijs full-rank zijn voor elke actie, mits het product van de voorwaartse en achterwaartse matrices full-rank is.
Expliciet modelherstel: In tegen tegenstelling tot PSR's herstelt de methode expliciete transitie- en observatiematrices (tot aan een partitie), wat het mogelijk maakt om na de initiële leerfase nieuwe beloningsfuncties en doelen te specificeren zonder opnieuw te trainen.
Theoretische limieten: De auteurs bewijzen dat het leren van transitie- en observatiedynamica voorbij de observability-partitie onmogelijk is vanuit een enkele sequentiële data-traject. Zij construeren een tegenvoorbeeld dat aantoont dat twee verschillende POMDP's met verschillende interne dynamica identieke observatiedistributies opleveren voor alle actiesequenties, waarmee de theoretische limiet van identificeerbaarheid wordt vastgesteld.

Experimentele resultaten
De auteurs evalueren hun methode op verschillende domeinen, waaronder het "Sense-Float-Reset" domein (met state aliasing), het Tiger-probleem en de T-Maze.

Convergentie: De methode slaagt erin de onderliggende observatiemodellen en partitie-niveau transitie-matrices te herstellen, waarbij zij convergeren naar de grondwaarheid naarmate het aantal exploratie-interacties toeneemt. In contrast hiermee convergeert Expectation-Maximization (EM) vaak naar lokale minima die weliswaar observaties correct voorspellen, maar onjuiste modelparameters opleveren.
Planningsprestaties: Wanneer de methode wordt gebruikt met een standaard planner (PO-UCT), bereiken de geleerde partitie-niveau POMDP's een planningsprestatie die vergelijkbaar is met de grondwaarheid-modellen en PSR's.
Specificatie van beloningen: In nieuwe "Noisy Hallway" en "Directional Hallway" domeinen demonstreren de auteurs dat de expliciete transitie- en observatie-likelihoods het mogelijk maken om een agent naar specifieke latente toestanden te leiden (bijv. een middelste gang-toestand met ambigue observaties) door beloningen toe te kennen aan toestanden in plaats van enkel aan observatie-actie paren. Deze capaciteit is niet beschikbaar bij standaard PSR's of EM-gebaseerde modellen die falen in het herstellen van de juiste staatstructuur.

Betekenis en claims
Het artikel claimt dat de methode de kloof overbrugt tussen de voorspellende kracht van PSR's en de interpreteerbaarheid van expliciete POMDP-modellen. Door te leren tot aan een observability-partitie, vangt de methode een bredere klasse van real-world systemen (met name in robotica waarbij acties kunnen falen of toestanden gealiased kunnen zijn) dan voorgaande tensor-gebaseerde methoden.

De auteurs beweren bescheiden dat hoewel hun methode niet de exacte interne structuur van gealiaseerde toestanden kan herstellen uit sequentiële data, zij de maximale hoeveelheid informatie herstelt die theoretisch mogelijk is. Het vermogen om het geleerde model te manipuleren voor nieuwe taken (via expliciete beloningsspecificatie) wordt benadrukt als een primair voordeel ten opzichte van black-box voorspellende modellen. Het werk suggereert dat voor veel praktische toepassingen het leren van de dynamica tussen observability-partities voldoende is voor effectieve planning en redeneren.

Meer zoals dit