Door de stap beleidsevaluatie in het standaard beleiditeratie-algoritme te vervangen door de Monte Carlo-schattingstechnieken die in het vorige hoofdstuk zijn beschreven, kan al een nieuwe variant van beleiditeratie worden afgeleid—één 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. Om het beleid bij te werken, gebruiken we specifiek 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 toepassen, ook voor beleidsevaluatie, omdat dat efficiënter en nauwkeuriger zou zijn.

Daarom, hoewel het vervangen van waarde-inschatting door Monte Carlo-methoden een stap is richting modelvrij reinforcement learning, moeten we ook een manier vinden om beleidsverbetering uit te voeren zonder kennis van het model. Dit vereist een verschuiving van toestandswaardefunctie naar actie-waardefunctie.

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 theorema van beleidsverbetering nog steeds kan worden toegepast:

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

Schatting van de Actiewaarde Functie

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

Pseudocode

Op deze manier zullen de geschatte actie-waarden na voldoende iteraties de werkelijke actie-waarden 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 eerder aangegeven, 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 versterkt: na elke beleidsverbetering moeten we de Monte Carlo-schatting opnieuw uitvoeren om het nieuwe beleid te herwaarderen — wat leidt tot aanzienlijke overhead en trage leercurves.

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 beleidswaardering is voltooid, laten we de agent zijn gedrag episode per episode verfijnen, gebruikmakend van de meest recente schattingen van actie-waarden.

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 control 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.