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 cruciale 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, 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 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 Actiewaarde Functie

Het schattingsproces is vrijwel identiek aan de toestandswaardefunctie. 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 actie-waarden na voldoende iteraties de werkelijke actie-waarden 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 vergelijkbaar is met 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 leercurves.

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