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 dit 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 toepassen, ook voor beleidsevaluatie, omdat dit 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 voor beleidsverbetering wordt dan:

En het is niet moeilijk te bewijzen dat het nieuwe beleid niet slechter is dan het oude, aangezien de beleidsverbeterstelling 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.

Actiewaarde-functie Schatting

Het schattingsproces is vrijwel identiek aan de toestandswaarde-functie. Alle concepten die worden gebruikt bij het schatten van toestandswaarden, kunnen ook worden toegepast op het schatten van actiewaarden.

Pseudocode

Op deze manier zouden de geschatte actiewaarden na voldoende iteraties de werkelijke actiewaarden moeten benaderen.

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

Optimalisatie

Hoewel de stap waardering 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 lijkt op beleidsiteratie, 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 leercurve.

Een meer natuurlijke benadering is om het beleid direct bij te werken na het verwerken van elke episode. In plaats van te wachten tot een volledige cyclus van beleidswaardering is voltooid, laten we de agent zijn gedrag episode per episode verfijnen, gebruikmakend van de meest recente schattingen van de actiewaarden.

Dit resulteert in een methode die meer lijkt op waarde-iteratie: het combineren van aspecten van waardering en verbetering in één enkele stap. Dit verhoogt de efficiëntie van steekproeven 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.