Monte Carlo-Controle

Door de stap beleidsevaluatie in het standaard beleiditeratie-algoritme te vervangen door de Monte Carlo-schattingstechnieken die in het vorige hoofdstuk zijn beschreven, kunnen we al een nieuwe variant van beleiditeratie afleiden—een die vertrouwt op gesamplede ervaring in plaats van dynamisch programmeren.

Er is echter een belangrijke beperking. In traditionele beleiditeratie is de stap beleidsverbetering afhankelijk van toegang tot een volledig model van de omgeving. Specifiek, om het beleid bij te werken, gebruiken we de volgende uitdrukking:

Deze vergelijking gaat ervan uit dat we de overgangswaarschijnlijkheden $p(s', r | s, a)$ kennen. Maar dat is precies het probleem: Monte Carlo-methoden zijn ontworpen voor modelvrije situaties, waarin de overgangsdynamiek van de omgeving onbekend is. Als er een volledig model beschikbaar is, kunnen we net zo goed overal dynamisch programmeren gebruiken, ook voor beleidsevaluatie, omdat dat efficiënter en nauwkeuriger zou zijn.

Daarom is het vervangen van Monte Carlo-methoden voor waardeschatting een stap richting modelvrij reinforcement learning, maar we moeten ook een manier vinden om beleidsverbetering uit te voeren zonder kennis van het model. Dit vereist een verschuiving van toestandswaardefunctie naar actiewaardefunctie.

Waarom actiewaarden?

Door gebruik te maken van actiewaarden is het mogelijk om beleidsverbetering uit te voeren zonder een model van de omgeving nodig te hebben. In plaats van te vertrouwen op overgangswaarschijnlijkheden om verwachte opbrengsten te berekenen, kunnen we direct acties selecteren die de hoogste waarde lijken op te leveren. De stap beleidsverbetering wordt dan:

En het is niet moeilijk te bewijzen dat het nieuwe beleid niet slechter is dan het oude, aangezien de beleidsverbeteringstelling nog steeds kan worden toegepast:

En, net als bij DP, garandeert deze stelling dat ofwel $\pi_{k+1}$ beter is dan $\pi_k$, of dat ze beide gelijk en optimaal zijn.

Schatting van de actie-waardefunctie

Het schattingsproces is vrijwel identiek aan de toestandswaardefunctie. Alle ideeën die worden gebruikt bij het schatten van toestandswaarden, kunnen ook worden toegepast op het schatten van actiewaarden.

Pseudocode

Op deze manier zouden de geschatte actie-waarden na voldoende iteraties de werkelijke actie-waarden moeten benaderen.

Hiermee kun je al een methode bouwen vergelijkbaar met beleidsiteratie die niet afhankelijk is van een model. Hiervoor vervang je de stappen beleidsevaluatie en beleidsverbetering door de hierboven beschreven processen.

Optimalisatie

Hoewel de evaluatiestap kan worden uitgevoerd met Monte Carlo-schatting zoals beschreven, is deze doorgaans computationeel inefficiënt. Zoals je al hebt gezien, vereisen Monte Carlo-methoden meestal een groot aantal steekproeven om redelijk nauwkeurige schattingen te produceren. Als we een structuur volgen die vergelijkbaar is met beleid-iteratie, wordt deze inefficiëntie vergroot: na elke beleidsverbetering moeten we de Monte Carlo-schatting opnieuw uitvoeren om het nieuwe beleid te herwaarderen — wat leidt tot aanzienlijke overhead en trage leercycli.

Een natuurlijker alternatief is om het beleid direct bij te werken na het verwerken van elke episode. In plaats van te wachten tot een volledige cyclus van beleidsevaluatie is voltooid, laten we de agent zijn gedrag episode na episode verfijnen met behulp van de meest recente schattingen van actie-waarden.

Dit resulteert in een methode die meer lijkt op waarde-iteratie: het combineren van aspecten van evaluatie en verbetering in één stap. Dit verhoogt de steekproefefficiëntie en versnelt de berekening.

Pseudocode

Dit algoritme volgt een GPI-raamwerk, aangezien het stappen voor beleidsevaluatie en beleidsverbetering bevat, en het wordt Monte Carlo-controle genoemd. Het grootste nadeel van deze specifieke implementatie is de aanname van exploring starts. In de volgende hoofdstukken wordt uitgelegd waarom dit een probleem is en hoe hiermee omgegaan kan worden.