Technische Samenvatting: Policy Gradient-methoden voor niet-Markoviaans Versterkend Leren

Probleemstelling

Versterkend Leren (RL) vertrouwt traditioneel op het raamwerk van het Markov-beslissingsproces (MDP), waarbij wordt aangenomen dat dynamica en beloningen uitsluitend afhankelijk zijn van de huidige toestand en actie. Veel real-world omgevingen—zoals gedeeltelijk waarneembare systemen, dialoogagenten, aanbevelingssystemen en financiële markten—zijn echter van nature Niet-Markoviaanse Beslissingsprocessen (NMDP's). In deze omgevingen hangen waarnemingen en beloningen af van de volledige interactiegeschiedenis.

Het direct conditioneren van beleidsregels op de volledige geschiedenis is computationeel onuitvoerbaar omdat de geschiedenisruimte exponentieel groeit. Hoewel bestaande benaderingen proberen de geschiedenis te comprimeren, lopen ze vaak tegen beperkingen aan:

• Vaste Dynamica: Sommige methoden veronderstellen dat de interne toestandsdynamica van de agent vaststaat en optimaliseren alleen het controlebeleid (bijv. Dong et al., 2022).
• Voorspellende Doelstellingen: Andere methoden leren staatrepresentaties door het optimaliseren van aanvullende voorspellende doelstellingen (bijv. het voorspellen van toekomstige waarnemingen), wat mogelijk hoge-dimensionale representaties vereist en niet direct aansluit bij het uiteindelijke doel van het maximaliseren van de cumulatieve beloning (bijv. Subramanian et al., 2022).

Dit artikel adresseert de uitdaging om in NMDP's gezamenlijk een compacte staatrepresentatie en een controlebeleid te leren, zonder te vertrouwen op vaste dynamica of tussenliggende voorspellende doelstellingen.

Methodologie

Agent State-Markov (ASM) Beleidsregels

De auteurs introduceren een klasse van Agent State-Markov (ASM) beleidsregels. In dit kader onderhoudt de agent een interne toestand $S_t$ die recursief wordt bijgewerkt op basis van de vorige toestand, de vorige actie en de huidige waarneming:
$$S_t \sim \nu_t(\cdot \mid S_{t-1}, A_{t-1}, O_t)$$
Het controlebeleid $\phi$ koppelt vervolgens de huidige agenttoestand aan een actie:
$$A_t \sim \phi_t(\cdot \mid S_t)$$
Het paar $(\nu, \phi)$ vormt het ASM-beleid. Cruciaal is dat de auteurs voorstellen om de parameters van zowel de toestandsdynamica $\nu$ als het controlebeleid $\phi$ gezamenlijk te optimaliseren om de verwachte cumulatieve beloning te maximaliseren, in plaats van $\nu$ vast te zetten of deze via voorspelling te leren.

Theoretische Bijdragen

Het artikel stelt een Policy Gradient-stelling op voor ASM-beleidsregels, waarbij klassieke resultaten worden uitgebreid tot zowel episodische als oneindig-horizont afgekapte NMDP's.

1. Gradientexpressie: Voor een geparametriseerd ASM-beleid $\pi_\theta$ wordt de gradient van de verwachte opbrengst $J(\theta)$ afgeleid als:
   $$\nabla_\theta J(\theta) = \mathbb{E}_{\pi_\theta} \left[ \sum_{t} R_{t:\infty} \nabla_\theta \log \pi_\theta(S_t, A_t \mid S_{t-1}, A_{t-1}, O_t) \right]$$
   waarbij $R_{t:\infty}$ de toekomstige opbrengst (reward-to-go) voorstelt.
2. Factorisatie: Vanwege de structuur van ASM-beleidsregels, factoriseert de log-kans-term in de toestandsdynamica en het controlebeleid:
   $$\nabla_\theta \log \pi_\theta = \nabla_\theta \log \nu_\theta + \nabla_\theta \log \phi_\theta$$
   Dit maakt een aparte maar simultane update van de staatrepresentatie en het beleid mogelijk.
3. Convergentiegaranties: Onder standaard aannames van gladheid en begrensdheid bewijzen de auteurs:
   • Convergentie in eindige tijd: De tijd-gemiddelde kwadratische gradientnorm convergeert met een snelheid van $\tilde{O}(H^{3.5}/\sqrt{K})$ voor episodische taken (waarbij $H$ de horizon is en $K$ het aantal iteraties).
   • Bijna-zekere convergentie: Met afnemende stapgroottes convergeert de gradientnorm bijna zeker naar nul.
   • Vergelijkbare garanties worden vastgesteld voor de oneindig-horizont afgekapte setting, waarbij de effectieve horizon wordt bepaald door de afkoppelfactor $\gamma$.

Algorithmus: ASMPG

Op basis van de gradientstelling stellen de auteurs het Agent State-Markov Policy Gradient (ASMPG)-algoritme voor. Dit is een online, REINFORCE-achtig algoritme dat:

• Trajecten bemonsterd met het huidige ASM-beleid.
• De gradient schatting berekent met gebruikmaking van de recursieve structuur van de agenttoestand.
• De parameters van zowel het toestandsdynamica-netwerk als het beleidsnetwerk bijwerkt met behulp van stochastische gradientascentie.

Experimentele Resultaten

De auteurs evalueerden ASMPG op vijf niet-Markoviaanse omgevingen:

1. CheeseMaze: Een deeltjes waarneembare navigatietaken met aliasing waarnemingen.
2. HallwayNavigation: Een deterministische doolhofopgave waarbij lokale muurconfiguraties ambigu zijn.
3. HealthcareTreatment: Een behandelingsplanningstaak met verborgen toxiciteits- en resistentievariabelen.
4. MachineRepair: Een onderhoudstaak met verborgen slijtniveaus die machine-degradatie beïnvloeden.
5. VelocityOnlyCartPole: Een controletaak waarbij alleen snelheid (niet positie) wordt waargenomen.

Vergelijking: ASMPG werd vergeleken met AIS-KL en AIS-MMD (Subramanian et al., 2022), die staatrepresentaties leren via voorspellende doelstellingen (Benaderde Informatiestaten).

Vondsten:

• In alle vijf omgevingen behaalde ASMPG hogere gemiddelde beloningen per stap of per episode in vergelijking met de voorspellende baselines.
• Het prestatieverschil was vooral opmerkelijk in taken die langetermijngeheugen vereisen, zoals CheeseMaze, MachineRepair en VelocityOnlyCartPole.
• De resultaten suggereren dat het direct optimaliseren van de toestandsdynamica voor de beloningsdoelstelling effectiever is dan optimaliseren voor voorspellende toereikendheid.

Betekenis en Claims

Het artikel claimt dat de primaire bijdrage een beloningsgerichte formulering is voor niet-Markoviaans RL. Door de agenttoestandsdynamica te behandelen als een leerbare component die gezamenlijk wordt geoptimaliseerd met het controlebeleid, omzeilt de methode de noodzaak van aanvullende voorspellende doelstellingen of vaste staatrepresentaties.

Belangrijke claims zijn:

• Theoretische Validiteit: De afleiding van een policy gradient-stelling voor algemene NMDP's biedt een rigoureuze basis voor gezamenlijke optimalisatie, waarbij klassieke MDP-resultaten worden uitgebreid.
• Praktische Effectiviteit: Empirische resultaten tonen aan dat beloningsgerichte gezamenlijke optimalisatie beter presteert dan methoden die vertrouwen op voorspellende staatrepresentaties, zelfs wanneer de representatiegroottes vergelijkbaar zijn.
• Optimaliteitsvoorwaarden: Het artikel merkt op dat als er een "ideale" agenttoestandsdynamica bestaat (een die een toereikende statistiek is voor beloningen en toekomstige waarnemingen), het beperken van de zoekruimte tot ASM-beleidsregels geen verlies van optimaliteit met zich meebrengt.

De auteurs erkennen dat de voorgestelde methode vertrouwen op REINFORCE-achtige schatters, die kunnen lijden onder hoge variantie. Zij identificeren de ontwikkeling van actor-critic-varianten voor ASM-beleidsregels als een natuurlijke richting voor toekomstig werk om de variantie te verminderen terwijl het beloningsgerichte doel behouden blijft.