Learning in Markov Decision Processes with Exogenous Dynamics

Each language version is independently generated for its own context, not a direct translation.

Samenvatting: Hoe een slimme agent leert omgaan met wat hij niet kan controleren

Stel je voor dat je een taxi bestuurt in een drukke stad. Je hebt twee dingen onder controle:

Je eigen auto: Je kunt sturen, gas geven, remmen en kiezen welke route je neemt.
Het verkeer: Rode lichten, file, regen en andere bestuurders. Dit is niet iets wat jij kunt beïnvloeden. Het gebeurt gewoon, of je nu links of rechts draait.

In de wereld van kunstmatige intelligentie (AI) en robotica proberen computers vaak te leren door alles tegelijk te bestuderen. Ze denken: "Als ik links draai, gebeurt er X. Als ik rechts draai, gebeurt er Y." Maar als het verkeer (de exogene dynamiek) willekeurig is, raakt de computer in de war. Hij probeert patronen te vinden tussen zijn stuur en de file, terwijl die file niets met zijn sturen te maken heeft. Dit kost enorm veel tijd en data om te leren.

De auteurs van dit paper, Davide Maran en collega's, hebben een nieuwe manier bedacht om dit probleem op te lossen. Ze noemen dit PCMDP (Partially Controllable Markov Decision Process). Laten we het uitleggen met een paar simpele metaforen.

1. Het Probleem: De Verkeersagent die alles probeert te regelen

Stel je een beginnende taxi-chauffeur voor die denkt dat hij de file kan oplossen door harder te remmen. Hij probeert duizenden keren te remmen, linksaf te slaan of rechtsaf, en kijkt telkens of de file weg is.

Het resultaat: Hij leert heel langzaam. Hij ziet dat soms de file weggaat als hij remt, en soms niet. Hij kan het onderscheid niet maken tussen zijn eigen acties en het toeval.
De wiskundige naam: Dit is een standaard "Markov Decision Process" (MDP). De computer probeert de hele wereld te modelleren, inclusief de dingen die hij niet kan aanraken.

2. De Oplossing: De "Scheiding van Krachten"

De auteurs zeggen: "Wacht even! Waarom proberen we te leren dat we de file kunnen beïnvloeden? Dat kunnen we niet. We moeten alleen leren hoe we onze auto besturen, terwijl we accepteren dat het verkeer gewoon zijn gang gaat."

Ze splitsen de wereld in twee delen:

De "Interne" wereld (Endogeen): Alles wat je kunt aanraken (je auto, je budget, je waterreservoir). Dit is vaak voorspelbaar. Als je gas geeft, gaat je auto sneller.
De "Externe" wereld (Exogeen): Alles wat je niet kunt aanraken (het weer, de beurskoersen, het verkeer). Dit is willekeurig en onafhankelijk van jou.

3. De Nieuwe Algoritmes: EXAVI en EXAQ

De paper introduceert twee slimme methoden (algoritmes) die deze scheiding gebruiken om veel sneller te leren.

EXAVI (De Slimme Planningsmachine)

Hoe het werkt: Stel je voor dat je een kaart hebt van de stad. Je weet precies hoe je auto werkt (je kunt remmen, sturen). Maar je weet niet precies hoe het verkeer zich gedraagt.
De truc: In plaats van te proberen te raden hoe je auto en het verkeer samen werken, leert de machine alleen het verkeer.
De analogie: Een gewone AI probeert te leren: "Als ik linksaf sla, komt er een file op." (Dit is onzin, want de file komt er anyway).
De nieuwe AI zegt: "Ik weet hoe mijn auto werkt. Ik hoef alleen maar te kijken: 'Hoe gedraagt het verkeer zich als ik linksaf sla?' en 'Hoe gedraagt het zich als ik rechtsaf sla?'"
Omdat het verkeer niet verandert door je actie, hoeft de AI niet te "proberen" om het verkeer te zien. Hij kan gewoon rustig kijken hoe het verkeer zich gedraagt, ongeacht wat hij doet. Dit maakt het leren veel sneller.

EXAQ (De Slimme Leraar)

Hoe het werkt: Dit is een methode die niet eerst een kaart maakt, maar direct leert door ervaring (zoals een mens die rijdt).
De truc: Normaal gesproken leert een AI: "Ik deed A, en toen gebeurde B. Dus A leidt tot B."
De nieuwe AI zegt: "Ik deed A, en het verkeer veranderde naar X. Nu weet ik dat voor elke mogelijke positie van mijn auto, als het verkeer X is, het resultaat hetzelfde zal zijn."
De analogie: Stel je voor dat je een leraar bent. Een gewone leraar leert één leerling per keer. Deze nieuwe leraar leert alle leerlingen tegelijk over hetzelfde onderwerp. Als hij ziet hoe het weer (exogeen) verandert, past hij zijn les direct toe op alle mogelijke situaties van de auto (endogeen). Hij "vermenigvuldigt" zijn kennis.

4. Waarom is dit zo belangrijk?

In de echte wereld zijn veel problemen zoals dit:

Handelen op de beurs: Jij kunt je portefeuille beheren (interne), maar je kunt de prijs van een aandeel niet bepalen (extern).
Waterreservoirs: Je kunt de sluizen openen (interne), maar je kunt de regen niet laten vallen (extern).
Energie: Je kunt batterijen laden, maar je kunt de zon niet laten schijnen.

De oude methoden proberen alles tegelijk te leren, wat als proberen is om een heel groot raadsel op te lossen terwijl je blinddoekt bent. De nieuwe methoden zeggen: "Oké, dit stukje van het raadsel (het weer/verkeer) is willekeurig. Laten we dat loslaten en ons alleen focussen op het stukje dat we wel kunnen oplossen."

Het Resultaat

De paper toont aan dat deze nieuwe methoden:

Veel minder data nodig hebben: Ze leren in een paar minuten wat de oude methoden in uren of dagen doen.
Beter presteren: Ze vinden sneller de beste strategie.
Wiskundig bewezen: Ze hebben bewezen dat je niet sneller kunt leren dan dit; het is de theoretische limiet van wat mogelijk is.

Kortom: Door te erkennen wat je niet kunt controleren, word je veel slimmer in wat je wel kunt controleren. Het is alsof je stopt met proberen de wind te stoppen, en je gewoon leert hoe je het zeil het beste kunt zetten.

Each language version is independently generated for its own context, not a direct translation.

Titel: Leren in Markov Decision Processes met Exogene Dynamiek (PCMDP)

1. Het Probleem

Versterkte leren (Reinforcement Learning - RL) algoritmen worden doorgaans ontworpen voor generieke Markov Decision Processes (MDP's), waarbij elke actie kan leiden tot een willekeurige verdeling van overgangen in de volledige toestandsruimte. In veel praktische systemen (zoals financieel handelen, reservoirbeheer of energienetwerken) is echter slechts een subset van de toestandsvariabelen direct beïnvloedbaar door de agent. De overige componenten evolueren volgens exogene dynamiek (buiten de controle van de agent), zoals beurskoersen, weeromstandigheden of stroomvraag.

Deze exogene factoren veroorzaken twee hoofdproblemen in standaard RL:

Hoog ruis-signaal: De beloningssignalen worden sterk beïnvloed door oncontroleerbare fluctuaties, wat het moeilijk maakt om de bijdrage van de eigen acties te onderscheiden van omgevingsruis.
Ondoeëlijke exploratie: Standaard exploratiestrategieën proberen correlaties te vinden tussen acties en exogene signalen. Omdat deze afhankelijkheden per definitie niet bestaan, is deze exploratie nutteloos en verspillen algoritmen veel steekproeven (samples) aan het schatten van overgangen die de agent niet kan beïnvloeden.
Complexiteit: Het meenemen van exogene variabelen in de volledige toestandsruimte ( $S$ ) leidt tot een exponentiële toename van de complexiteit, waardoor leren inefficiënt wordt.

2. Methodologie: Het PCMDP Framework

De auteurs introduceren een nieuwe structuur: de Partially Controllable Markov Decision Process (PCMDP). Hierbij wordt de toestandsruimte $S$ expliciet gefactoriseerd in twee delen:

Endogene toestand ( $s^\bullet$ ): De controleerbare component. De dynamiek hiervan is vaak deterministisch of eenvoudig stochastisch en bekend voor de agent.
Exogene toestand ( $s^\circ$ ): De oncontroleerbare component. De overgangen hiervan zijn onafhankelijk van de acties van de agent en volgen een onbekende, complexe stochastische dynamiek.

Kernassumptie: De agent heeft volledige kennis van de endogene overgangsdynamiek ( $p^\bullet$ ), maar moet de exogene dynamiek ( $p^\circ$ ) leren.

Op basis van dit framework worden twee nieuwe algoritmen ontwikkeld:

EXAVI (Exogenous-Aware Value Iteration): Een model-based aanpak.
- In plaats van de volledige overgangsmatrix $P(s'|s,a)$ te schatten (zoals bij UCBVI), schat EXAVI alleen de exogene overgangen $p^\circ$ .
- Omdat de exogene dynamiek onafhankelijk is van acties, is geen optimistische exploratie (zoals UCB-bonussen) nodig. De agent hoeft niet actief te "zoeken" naar exogene toestanden; deze evolueren gewoon mee.
- De algoritme gebruikt een geschatte $p^\circ$ gecombineerd met de bekende $p^\bullet$ om de optimale waarde te plotten via Value Iteration.
EXAQ (Exogenous-Aware Q-Learning): Een model-free aanpak.
- Dit is een extensie van Q-Learning die de onafhankelijkheid van de exogene variabelen benut.
- In plaats van één update per bezochte $(s, a)$ -paar, voert EXAQ counterfactual updates uit. Wanneer een exogene overgang wordt waargenomen, worden de Q-waarden voor alle mogelijke endogene toestandscombinaties ( $s^\bullet$ ) die bij die exogene context passen, simultaan bijgewerkt.
- Dit stelt de agent in staat om informatie te delen over de exogene context, wat leidt tot een drastisch snellere convergentie.

3. Belangrijkste Bijdragen

Formulering van PCMDP: Een formeel raamwerk dat controleerbare en oncontroleerbare variabelen expliciet scheidt binnen MDP's.
Theoretische Garanties: De auteurs bewijzen dat de regret (spijtbetaling) voor zowel model-based als model-free algoritmen afhankelijk is van de grootte van de exogene toestandsruimte ( $S^\circ$ $S^{\circ}$ ) en niet van de totale grootte ( $S = S^\bullet \times S^\circ$ $S = S^{∙} \times S^{\circ}$ ).
- De regret van EXAVI schaalt als $\tilde{O}(H^2\sqrt{S^\circ K})$ .
- De regret van EXAQ schaalt als $\tilde{O}(\sqrt{H^5 S^\circ K})$ .
- In vergelijking met standaard MDP-algoritmen (die schalen met $\sqrt{S^\circ S^\bullet}$ ) is dit een aanzienlijke verbetering, vooral wanneer $S^\bullet$ groot is.
Ondergrens (Lower Bound): Er wordt bewezen dat de afhankelijkheid van $\sqrt{S^\circ}$ information-theoretisch optimaal is; het is onmogelijk om een betere schaling te bereiken.
Algoritmen: De ontwikkeling van EXAVI en EXAQ, die geen optimistische exploratiebonussen vereisen voor de exogene component, wat leidt tot lagere sample-complexiteit.

4. Resultaten

De auteurs hebben hun methoden getest in drie omgevingen: een Taxi-omgeving met verkeer, een Optimal Execution taak (handelsstrategie) en een Elevator Dispatching taak.

Taxi-omgeving: EXAVI en EXAQ convergeren bijna onmiddellijk naar het optimale beleid (binnen enkele episodes), terwijl standaard UCBVI en Q-Learning duizenden episodes nodig hebben om vergelijkbare prestaties te halen.
Optimal Execution (Handelsomgeving): In een omgeving met een grote exogene toestandsruimte (1000 prijsniveaus) presteert EXAQ aanzienlijk beter dan standaard Q-Learning en PPO (Proximal Policy Optimization). EXAQ bereikt convergentie binnen de eerste $10^1$ tot $10^2$ episodes, terwijl PPO instabiel is en Q-Learning zeer traag convergeert.
Sample Efficiency: De experimenten tonen aan dat het expliciet modelleren van de partiële controleerbaarheid leidt tot een verbetering in sample-efficiëntie met ordes van grootte. De algoritmen leren de exogene dynamiek effectief zonder onnodige exploratie van de controleerbare ruimte.

5. Significantie en Impact

Dit werk is significant omdat het een brug slaat tussen theoretische RL en complexe real-world problemen waar oncontroleerbare factoren een grote rol spelen.

Efficiëntie: Het lost het probleem op van "spurious correlations" waarbij agents tijd verspillen aan het leren van onbestaande afhankelijkheden tussen acties en exogene signalen.
Toepasbaarheid: De aanpak is direct toepasbaar in domeinen zoals algoritmisch handelen, energiebeheer en logistiek, waar de omgeving grotendeels onvoorspelbaar is maar de agent wel specifieke interne variabelen (zoals voorraad of budget) kan controleren.
Theoretische Vooruitgang: Het paper levert een bewijs dat het scheiden van endogene en exogene dynamiek niet alleen praktisch nuttig is, maar ook theoretisch noodzakelijk is om optimale regret-bounds te bereiken in deze specifieke klasse van problemen.

Kortom, het paper toont aan dat door de structuur van het probleem (partieel controleerbaarheid) expliciet te benutten, RL-agenten veel sneller en efficiënter kunnen leren dan met generieke MDP-methoden.