Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments

Dit paper introduceert 'Joint MDPs' (JMDPs) als een formalisme voor omgevingen met gekoppelde dynamica, waarbij een multi-action sample-overgangsmodel de gezamenlijke verdeling van tegenwerkelijke uitkomsten definieert en zo dynamic programming-algoritmen met convergentiegaranties mogelijk maakt voor hogere orde momenten van de return.

De kern

Stel je voor dat je een speler bent in een complex computerspel, zoals een racegame of een strategische simulatie. Je staat op een kruispunt en moet een beslissing nemen: ga je linksaf of rechtsaf?

In de traditionele wereld van kunstmatige intelligentie (Reinforcement Learning), kijkt de computer meestal alleen naar één optie tegelijk. Hij denkt: "Als ik links ga, wat is de kans dat ik win?" en daarna apart: "Als ik rechts ga, wat is de kans dat ik win?" Hij behandelt deze twee scenario's alsof ze in twee totaal verschillende universums gebeuren. Hij vergeet dat in het echte leven, als je links of rechts had gekozen, de regen, de wind en de andere auto's op dat exacte moment hetzelfde waren geweest.

Dit artikel introduceert een nieuwe manier om hierover na te denken, genaamd Joint MDPs (of JMDPs). Laten we dit uitleggen met een paar simpele analogieën.

1. Het probleem: De "Wat-zou-er-gebeurd-zijn"-moeilijkheid

Stel je voor dat je een weerman bent die een voorspelling doet.

• De oude manier (MDP): Je zegt: "Als het regent, is de kans op modder 80%." En apart: "Als het droog is, is de kans op modder 10%." Je weet niet hoe de modder zou zijn als het zowel had geregend als droog was geweest op hetzelfde moment. Je mist de link tussen de twee scenario's.
• De nieuwe manier (JMDP): De auteur zegt: "Laten we aannemen dat we een 'multiverse-machine' hebben. We kunnen tegelijkertijd kijken naar wat er gebeurt als je links gaat én wat er gebeurt als je rechts gaat, onder exact dezelfde weersomstandigheden."

In de echte wereld (en in geavanceerde simulaties) gebeurt dit vaak. Als je een simulator hebt, kun je één keer op 'start' drukken en kijken wat er gebeurt als je links slaat, en tegelijkertijd (in de computer) kijken wat er gebeurt als je rechts slaat, terwijl de 'wind' (de externe factor) precies hetzelfde blijft. De oude methoden konden dit niet goed gebruiken; de nieuwe methode (JMDP) pakt deze verborgen verbindingen op.

2. De oplossing: De "Tweeling-Test"

De kern van dit papier is het idee van gekoppelde dynamica.

Stel je voor dat je twee identieke tweelingen bent die op een kruispunt staan.

• Tweeling A loopt links.
• Tweeling B loopt rechts.

Omdat ze op hetzelfde moment starten, raken ze dezelfde plensbakken, dezelfde struikelstenen en dezelfde regenbuien. Als Tweeling A struikelt, is dat waarschijnlijk omdat er een steen lag. Als Tweeling B niet struikelt, is dat misschien omdat hij een andere weg koos, maar de steen was er toch.

De oude methoden zagen alleen: "Tweeling A viel, Tweeling B viel niet." Ze zagen niet dat ze beiden over dezelfde steen liepen.
De JMDP-methode houdt rekening met die gedeelde steen. Het zegt: "Omdat ze dezelfde omstandigheden deelden, weten we precies hoe groot het verschil is tussen hun prestaties."

3. Waarom is dit nuttig? (De "Gap" en "Risico")

Waarom maakt dit uit? Omdat het ons helpt om betere beslissingen te nemen, vooral als het om risico gaat.

• Het verschil (De Gap): Soms willen we niet weten wat de gemiddelde winst is, maar hoe groot het verschil is tussen optie A en optie B. Als optie A en B vaak samen goed of slecht presteren (omdat ze dezelfde externe factoren delen), is het risico dat je een slechte keuze maakt anders dan wanneer ze onafhankelijk zijn.
• Risico's: Stel je voor dat je een investering doet. Als de beurs crasht, gaan alle investeringen naar beneden. Als je alleen naar de gemiddelde prestatie van elke investering apart kijkt, mis je het feit dat ze allemaal samen instorten. De nieuwe methode ziet die "samen-instorting" (de correlatie) en helpt je om te voorkomen dat je alles verliest.

4. Hoe werkt het in de praktijk?

De auteurs hebben wiskundige formules bedacht (ze noemen ze "Bellman-operatoren", maar laten we ze "voorspellingsformules" noemen) die deze verbindingen kunnen berekenen.

• Stap 1: Ze kijken naar de onmiddellijke toekomst. Wat gebeurt er als ik links ga vs. rechts ga, met dezelfde wind?
• Stap 2: Ze kijken naar de lange termijn. Maar hier maken ze een slimme aanname: na de eerste stap gaan de twee werelden weer uit elkaar. De wind voor de volgende stap is weer willekeurig. Dit voorkomt dat de wiskunde te ingewikkeld wordt (een "exponentiële explosie" van mogelijke werelden).
• Stap 3: Ze bouwen algoritmen die dit kunnen leren, zelfs als de wereld heel groot is (met neurale netwerken, net als bij het leren van een AI om Pong te spelen).

Samenvatting in één zin

Dit papier introduceert een slimme nieuwe manier voor computers om te leren, waarbij ze niet alleen kijken naar wat er gebeurt als ze één keuze maken, maar tegelijkertijd kijken naar wat er zou gebeuren als ze alle keuzes tegelijk hadden gemaakt onder dezelfde omstandigheden, zodat ze de echte risico's en kansen veel nauwkeurijker kunnen inschatten.

Het is alsof je van een speler die blindelings probeert, verandert in een strateeg die alle mogelijke toekomstige paden in één oogopslag kan zien en begrijpt hoe ze met elkaar verbonden zijn.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Joint MDPs and Reinforcement Learning in Coupled-Dynamics Environments" in het Nederlands.

Titel: Joint MDPs en Versterkende Leer in Omgevingen met Gekoppelde Dynamica

1. Het Probleem

In het veld van Distributionele Versterkende Leer (Distributional Reinforcement Learning - DRL) wordt de focus vaak gelegd op het leren van de verdeling van de opbrengst (return) voor individuele acties, oftewel de marginale wetten. Echter, veel cruciale beslissingskwaliteiten zijn intrinsiek gezamenlijk (joint) over verschillende acties heen. Voorbeelden hiervan zijn:

• De opbrengstgaps ($G = Z(s, a) - Z(s, \tilde{a})$) en hun verdeling.
• Kansen op superioriteit ($P(Z(s, a) > Z(s, \tilde{a}))$).
• Risicogevoelige maatstaven zoals Conditional Value-at-Risk (CVaR) van deze gaps.

De klassieke Markov Beslissingsproces (MDP) formalisme is ontoereikend voor deze doeleinden. Een standaard MDP specificeert alleen de marginale verdelingen van beloningen en overgangen voor elke actie afzonderlijk. Het laat de gezamenlijke wet (joint law) van de tegenstrijdige (counterfactual) uitkomsten voor meerdere acties die vanuit dezelfde staat worden genomen, ongespecificeerd. Zonder een specifieke "koppelingsconventie" (coupling convention) zijn gezamenlijke objecten zoals de verdeling van een gap niet goed gedefinieerd, zelfs niet als de marginale verdelingen bekend zijn.

In veel simulatieomgevingen (zoals scenario-based simulaties) is het echter mogelijk om tegenstrijdige uitkomsten voor meerdere acties te genereren onder dezelfde exogene ruis (shared exogenous randomness). Bestaande DRL-methoden negeren deze structuur en behandelen acties als onafhankelijk, wat leidt tot een verlies van informatie die essentieel is voor risicobeheer en vergelijkende analyse.

2. Methodologie

De auteurs stellen een nieuw formalisme en bijbehorende algoritmen voor om deze beperkingen op te lossen:

A. Joint MDPs (JMDPs)
De kern van de bijdrage is de introductie van Joint MDPs (JMDPs). Een JMDP breidt een standaard MDP uit met een multi-actie sample transition model.

• In plaats van alleen een overgangskern per actie, definieert een JMDP een kernel $J(\cdot | s)$ die een gezamenlijke verdeling specificeert over een tabel van tegenstrijdige uitkomsten $((R(a), S'(a)))_{a \in A}$ voor alle acties $a$ in een staat $s$.
• Dit model maakt het mogelijk om de afhankelijkheid tussen de uitkomsten van verschillende acties te modelleren, veroorzaakt door gedeelde exogene ruis.

B. Regime van Eén-Stap Koppeling
Om de complexiteit beheersbaar te houden en de "exponentiële explosie" van volledig gekoppelde tegenstrijdige bomen te vermijden, adopteren de auteurs een regime van één-stap koppeling:

• De afhankelijkheid tussen acties is beperkt tot de directe tegenstrijdige uitkomsten op het moment van de query.
• De toekomstige stochastiek wordt als onafhankelijk beschouwd tussen verschillende tegenstrijdige takken, gegeven de volgende staten.
• Dit komt overeen met multi-actie generatieve interfaces die in simulaties gebruikelijk zijn.

C. Bellman-operatoren voor Momenten
De auteurs leiden Bellman-operatoren af voor $n$-de orde momenten van de gezamenlijke opbrengstvector $Z^\pi(s) = (Z^\pi(s, a))_{a \in A}$.

• Ze definiëren een operator $T^\pi_n$ die werkt op verzamelingen van momenten (gemengde momenten zoals $E[Z(s, a) \cdot Z(s, \tilde{a})]$).
• Voor het geval van tweede orde momenten (variantie en covariantie) wordt bewezen dat de operator een contractie is onder een specifieke genormeerde ruimte.
• Dit garandeert de convergentie van iteratieve algoritmen naar een unieke vaste punt, wat de ware gezamenlijke momenten vertegenwoordigt.

D. Algoritmen
Twee hoofdbenaderingen worden gepresenteerd:

1. Dynamic Programming (JIPE-2): Een exacte iteratieve methode voor tabulaire ruimtes die de Bellman-operatoren toepast.
2. Incrementele Schatting (Stochastic Approximation): Een online variant die werkt met steekproeven van de multi-actie interface. Deze methode convergeert bijna zeker (almost surely) onder standaard voorwaarden voor stapgroottes.
3. Functieapproximatie: Voor hoge dimensies wordt een projectie-operator geïntroduceerd die de momenten projecteert op een parametrische ruimte (bijv. neurale netwerken), waarbij voor de tweede orde momenten een positief semi-definiete (PSD) structuur wordt gehandhaafd om geldige covariantiematrices te garanderen.

3. Belangrijkste Bijdragen

• Formalisatie van JMDPs: Een nieuw theoretisch raamwerk dat de ontbrekende koppeling tussen tegenstrijdige acties in MDPs expliciet modelleert.
• Theoretische Convergentie: Bewijzen dat Bellman-operatoren voor gezamenlijke momenten contracties zijn, wat leidt tot gegarandeerde convergentie voor zowel dynamische programmering als incrementele schattingsalgoritmen.
• Berekenbaarheid van Gezamenlijke Grootheden: Het mogelijk maken van de berekening van gap-verdelingen, superioriteitskansen en risicomaatstaven die eerder onbepaald waren in standaard MDP-contexten.
• Scalabiliteit: Demonstratie dat incrementele JIPE-2 gecombineerd met neurale functieapproximatie schaalbaar is naar complexe omgevingen (ALE games).

4. Resultaten

De auteurs valideren hun theorie via experimenten in zowel tabulaire als grote schaal omgevingen:

• Convergentie: In tabulaire omgevingen (zoals een "Windy Gridworld" met gekoppelde wind en een "Coupled-Reward Chain") vertonen de Bellman-residuen een lineaire afname op een logaritmische schaal, wat overeenkomt met de theoretische $\gamma$-contractie.
• Structuurleer: De geleerde covariantie- en correlatiematrices tonen gestructureerde, staat-afhankelijke afhankelijkheden tussen acties die onzichtbaar zijn voor marginale MDP-beschrijvingen.
• Gap-validatie: De methode levert nauwkeurige schattingen voor de gemiddelde en variantie van opbrengstgaps ($E[G]$ en $Var(G)$), wat wordt bevestigd door vergelijking met Monte Carlo-simulaties.
• Risicobound: De methode wordt gebruikt om een bovengrens te berekenen voor de kans op inferioriteit ($P(G \leq 0)$) via de ongelijkheid van Chebyshev. De empirische resultaten tonen aan dat deze grens wordt gerespecteerd.
• Schaalbaarheid: In vier Atari-spellen (Pong, BattleZone, Boxing, Atlantis) met een aangepaste multi-actie interface, slaagt de incrementele JIPE-2 met neurale netwerken erin om de TD-fouten over meerdere ordes van grootte te verlagen, wat aantoont dat de methode werkt in niet-tabulaire, complexe omgevingen.

5. Betekenis en Toekomst

Dit werk opent een nieuw pad in Versterkende Leer door de focus te verleggen van alleen marginale prestaties naar intrinsiek gezamenlijke verdelingen.

• Het biedt een wiskundig onderbouwde basis voor het nemen van beslissingen op basis van risico en vergelijkingen tussen acties, wat essentieel is voor toepassingen waar veiligheid en robuustheid cruciaal zijn.
• Het lost het fundamentele probleem op dat standaard MDP's "vergeten" informatie bevatten over hoe acties onder dezelfde omstandigheden presteren.
• De auteurs wijzen erop dat de volgende logische stap het uitbreiden van deze evaluatie naar besturingsproblemen (control) is, waarbij beleidsverbetering plaatsvindt op basis van deze gezamenlijke distributie-objectieven.

Samenvattend introduceert dit artikel een rigoureuze theoretische en praktische oplossing voor het modelleren en evalueren van versterkende leer in omgevingen waar de uitkomsten van verschillende acties onderling afhankelijk zijn door gedeelde omgevingsruis.