Technische Samenvatting: Minimale Markovisering via Stabiele Quotiënten in Holonomie-Cover Beslissingsprocessen

1. Probleemstelling

Reinforcement learning (RL) rust fundamenteel op de Markov-eigenschap, waarbij toekomstige beloningen en transities uitsluitend afhangen van de huidige staat. In Partially Observable Markov Decision Processes (POMDP's) is de huidige observatie vaak onvoldoende om de toekomst te voorspellen, wat het onderhoud van een historie-afhankelijke statistiek (bijv. een belief state) noodzakelijk maakt om de Markov-eigenschap te herstellen. Echter, de minimale dergelijke statistiek — de kleinste recursief bijwerkbare representatie die de Markov-eigenschap behoudt — is over het algemeen onbekend en moeilijk te karakteriseren.

Bestaande benaderingen richten zich vaak op expressieve of efficiënte historie-representaties (bijv. RNN's, Transformers) of belief-compressie, maar zij garanderen niet dat het resulterende geheugen-geaugmenteerde proces strikt Markoviaans is, noch identificeren zij de minimale voldoende statistiek. Dit artikel adresseert de specifieke uitdaging van het identificeren van de minimale Markov-voldoende statistiek voor een gestructureerde klasse van POMDP's waarbij verborgen dynamica worden beheerst door permutatie-gebaseerd transport.

2. Methodologie

2.1 Holonomy-Cover Decision Processes (HCDP's)

De auteurs introduceren Holonomy-Cover Decision Processes (HCDP's) als een gestructureerde familie van POMDP's. In een HCDP:

• Bestaat de latente staat uit een geobserveerde component ($o$) en een ongeobserveerde verborgen modus ($i$).
• De zichtbare dynamica zijn Markov: de transitiekans van observatie $o'$ gegeven $o$ en actie $a$ is onafhankelijk van de verborgen modus.
• Verborgen Transport: Telkens wanneer een transitie plaatsvindt van $o$ naar $o'$ via actie $a$, wordt de verborgen modus deterministisch gepermuteerd door een vaste permutatie $\sigma_{o,a,o'}$.
• Pad-afhankelijkheid: Hoewel het zichtbare pad Markoviaans is, hangt de geaccumuleerde verborgen modus af van de geordende compositie van deze permutaties. Bijgevolg kunnen twee historieën die eindigen op dezelfde observatie verschillende verborgen modi induceren, wat leidt tot verschillende beloningen of optimale beslissingen.

2.2 Constructie van het Stabiele Quotiënt

De kern van de methodologische bijdrage is de constructie van het stabiele quotiënt, dat dient als de minimale exacte observatie-wijze Markov-staat.

• Partitie-verfijning: De auteurs definiëren een partitiefamilie over de verborgen modi voor elke observatie. Zij introduceren een monotone operator $T$ die deze partities verfijnt op basis van twee criteria:
  1. Beloningsconsistentie: Modi moeten identieke onmiddellijke beloningen opleveren voor alle acties.
  2. Opvolger-consistentie: Voor elke haalbare transitie moeten de getransporteerde modi in dezelfde opvolger-partitieklasse landen.
• Stabilisatie: Startend vanaf een beloningsgebaseerde partitie, wordt de operator $T$ geïtereerd. Theorem 3.5 bewijst dat dit proces in een eindig aantal stappen stabiliseert naar een meest grove stabiele familie $\Pi^\star$.
• Exactheid: Theorem 3.8 stelt vast dat het stabiele quotiënt de meest grove exacte observatie-wijze abstractie is. Elke andere exacte abstractie moet dit stabiele quotiënt verfijnen.
• Markovisering: Theorem 3.9 bewijst dat het paar van de huidige observatie $o$ en de stabiele klasse $c = [i]_o$ een exacte, eindige, waarde-behoudende Markov-staat vormt. De transitiedynamica en beloningen op deze quotiënt-staattoom zijn welgedefinieerd en onafhankelijk van de specifieke verborgen representant binnen de klasse.

2.3 Holonomy Memory Reinforcement Learning (HMRL)

Om dit theoretische resultaat in de praktijk te gebruiken, stellen de auteurs HMRL voor, een algoritmisch framework:

• Representatie: Geheugen wordt gerepresenteerd door de huidige stabiele klasse.
• Update: De klasse wordt bijgewerkt via geordende edge-transporten (permutaties) terwijl de agent de observatie-graaf doorloopt.
• Diagnostiek en Herstel: Omdat de initiële klasse vaak onbekend is, hanteert HMRL een kalibreer-dan-herstart strategie. Onder een resetbare diagnostische interface (die herhaalde probes van de latente staat toestaat), indiceert het algoritme lokale klasse-prototypes en edge-transporten.
• Theoretische Garanties: Theorem 4.6 toont aan dat de fout in klasse-inferentie exponentieel afneemt met de diagnostische herhalingen. Theorem 5.2 en Corollary 5.4 demonstreren dat zodra de lokale klasse-tracking gesynchroniseerd is (via kalibratie), het geleerde proces isomorf is aan het canonieke quotiënt-MDP, waardoor standaard eindige-MDP RL-garanties kunnen worden overgedragen naar de herstelde staat.

2.4 Niet-Abelse Geheugenbarrière

Het artikel analyseert de noodzaak van geordend geheugen. Theorem 6.4 en Corollary 6.5 bewijzen dat voor niet-abelse transportgroepen (waar de volgorde van operaties ertoe doet), geheugenrepresentaties gebaseerd op louter commutatieve loop-tellingen (bijv. tellen hoe vaak een loop werd doorlopen) onvoldoende zijn. Dergelijke "geabelianiseerde" geheugens voegen onderscheidende historieën samen die verschillende optimale acties vereisen, wat leidt tot suboptimale prestaties. In tegen plaats vermijdt geordende stabiele-klasse tracking dit verlies met eindig geheugen.

3. Belangrijkste Bijdragen

1. Formulering en Identificatie: Het artikel formuleert HCDP's en identificeert het stabiele quotiënt als de minimale Markov-voldoende statistiek onder exacte observatie-wijze abstracties. Het biedt een overeenkomende geheugenkarakterisering ($\max_o |C_o|$ symbolen) voor exacte bekende-klasse tracking.
2. Diagnostisch Herstel: Het scheidt passieve niet-identificeerbaarheid van diagnostisch herstel. Onder resetbare gekalibreerde diagnostiek identificeert de methode klassen en transporten tot op observatie-wijze herlabeling, en biedt het voorwaarden waaronder garanties van eindige-MDP RL kunnen worden overgedragen naar de herstelde staat.
3. Niet-Abelse Ondergrens: De auteurs bewijzen een niet-abelse ondergrens voor count-factorized geheugens, waarmee zij aantonen dat geordende stabiele-klasse tracking noodzakelijk is om informatieverlies in niet-commutatieve transportsettings te voorkomen.
4. Algoritmisch Framework: Het voorstel van HMRL, dat structurele quotiënt-ontdekking integreert met standaard RL-backbones via een kalibratie-en-herstart protocol.

4. Experimentele Resultaten

De auteurs valideren hun theorie met behulp van twee gecontroleerde omgevingen: ChainCover en LoopGuess.

• ChainCover (Structurele Exactheid):

  • Een acyclische diepte-6 constructie met 216 ruwe latente staten.
  • Het algoritme slaagde erin de staattoom te comprimeren naar 25 exacte quotiënt-staten zonder enige belonings-, transitie- of optimale-waarde inconsistentie.
  • Het verfijningsproces stabiliseerde in ronde 7, wat overeenkomt met de analytische voorspellingen.

• LoopGuess (Niet-Abelse Controle):

  • Een niet-abelse omgeving waar zichtbare loops de symmetrische groep $S_3$ genereren.
  • Prestaties: HMRL bereikte een 1.000 finale succes en perfecte gepaarde-orde nauwkeurigheid (het onderscheiden van historieën met identieke loop-tellingen maar verschillende volgordes).
  • Geheugenefficiëntie: HMRL gebruikte slechts 3 beslissingstijd geheugen-staten, wat overeenkomt met de prestaties van de "Quotient-Q oracle" (die toegang heeft tot de ware stabiele klasse).
  • Baselines:
    • Count-Q (commutatieve loop-tellingen) faalde en bleef rond het niveau van toeval (0.34) bij historieën met dezelfde telling maar verschillende orde.
    • History-Q (volledig loop-woord) behaalde een hoge nauwkeurigheid maar vereiste meer dan $10^3$ bezochte geheugen-staten, wat de inefficiëntie ten opzichte van het minimale quotiënt demonstreert.
    • Raw-Q oracle (volledige latente staat) behaalde perfect succes maar vereiste 48 staten en vertoonde trager leren.

5. Betekenis en Claims

Het artikel claimt een principiële oplossing te bieden voor het probleem van de "minimale Markov-voldoende statistiek" voor een specifieke, gestructureerde klasse van POMDP's. De betekenis ligt in:

• Theoretische Rigor: Het gaat verder dan heuristische benaderingen (zoals RNN's) om exacte, eindige-toom abstracties te bieden die de Markov-eigenschap en optimale waardefuncties behouden.
• Efficiëntie: Het demonstreert dat complexe historie-afhankelijkheden kunnen worden gecomprimeerd tot een minimale set geheugen-symbolen (de stabiele klassen) zonder verlies van optimaliteit, mits de onderliggende dynamica de HCDP-structuur volgen.
• Orde-gevoeligheid: Het karakteriseert expliciet het falen van commutatieve samenvattingen in niet-abelse settings, wat de noodzaak van geordende transport-tracking rechtvaardigt.
• Praktische Reductie: Het biedt een concrete "kalibreer-dan-herstart" reductie die het mogelijk maakt om standaard eindige-MDP RL-algoritmen toe te passen op partieel observeerbare settings zodra het structurele quotiënt is geïdentificeerd.

De auteurs blijven bescheiden en merken op dat hun resultaten van toepassing zijn op HCDP's en dat het uitbreiden van quotiënt-ontdekking naar ruisige, continue of puur passieve-data settings (zonder resetbare diagnostiek) een openstaande onderzoeksvraag blijft. De experimenten worden gepresenteerd als falsifieerbare controles van de theorie onder bekende model-aannames, in plaats van bewijs dat willekeurige POMDP-benchmarks dergelijke exacte eindige quotiënten toestaan.