Laten we beginnen met het herzien van een bekend concept: de toestandswaardefunctie, aangeduid als $v_\pi(s)$. Deze kan worden gedefinieerd als

Het doel in dit hoofdstuk is om deze functie te schatten op basis van data, waarbij we uitgaan van een vaste strategie $\pi$, maar geen toegang hebben tot het model van de omgeving.

Monte Carlo-schatting

Monte Carlo-methoden benaderen deze schattingstaak door episodes te bemonsteren van ervaringen onder de strategie $\pi$, en vervolgens deze steekproeven te gebruiken om empirische schattingen van $v_\pi(s)$ te vormen.

In het algemeen kan het proces worden opgesplitst in de volgende stappen:

1. Genereer een episode met behulp van strategie $\pi$;
2. Sla de verkregen opbrengstwaarde op voor elke toestand die in de episode voorkomt;
3. Herhaal stap 1-2 gedurende enige tijd;
4. Bereken de nieuwe waarden door de opbrengsten voor elke toestand te middelen.

Het Verzamelen van de Opbrengsten

Monte Carlo-schatting van de waardefunctie vereist het verzamelen van de opbrengsten uit gegenereerde episodes. Voor het berekenen van deze opbrengsten kunnen twee primaire benaderingen worden gebruikt:

• Eerste-bezoek: voor elke toestand $s$ die in een episode wordt tegengekomen, wordt alleen de opbrengst na het eerste voorkomen meegenomen. Latere voorkomens van dezelfde toestand binnen dezelfde episode worden genegeerd voor schattingsdoeleinden;
• Elk-bezoek: elk voorkomen van een toestand $s$ binnen een episode wordt gebruikt. Dat wil zeggen, de opbrengst na elk bezoek aan de toestand wordt meegenomen in de schatting, zelfs als de toestand meerdere keren in dezelfde episode voorkomt.

Verkennende Starttoestanden

Stel je een eenvoudige eendimensionale wereld voor, weergegeven door een lijn die zich uitstrekt van -10 tot +10. De agent begint op positie 0, en het huidige beleid bepaalt dat hij bij elke tijdstap altijd naar rechts beweegt.

Als we proberen episodes te genereren onder dit beleid, wat gebeurt er dan? De agent zal voortdurend naar het positieve uiteinde van de lijn bewegen — en bezoekt toestanden zoals 1, 2, 3, enzovoort — maar zal nooit negatieve toestanden bezoeken. Hierdoor kunnen we geen waarde-functies schatten voor toestanden links van het nulpunt, simpelweg omdat de agent deze nooit ervaart.

Het belangrijkste probleem is dus: als bepaalde delen van de toestandsruimte nooit worden verkend, blijven hun waardeschattingen onnauwkeurig of ongedefinieerd. Een veelgebruikte oplossing voor dit probleem is het gebruik van explorerende starts.

Met explorerende starts begint elke episode niet bij een vaste starttoestand zoals 0, maar bij een willekeurig geselecteerde toestand. Zodra de episode begint, volgt de agent zijn huidige beleid zoals gebruikelijk. Na verloop van tijd, door te starten vanuit verschillende punten in de toestandsruimte, kan de agent alle toestanden bezoeken — niet alleen de toestanden waar zijn beleid hem normaal gesproken naartoe zou leiden. Dit stelt de Monte Carlo-methode in staat om nauwkeurigere en completere waardeschattingen te produceren voor de gehele toestandsruimte.

Pseudocode

Deze pseudocode gebruikt de every-visit benadering samen met exploring starts.