Ideen bag on-policy metoder er intuitiv: en agent lærer ved at følge sin nuværende politik og forbedrer denne politik baseret på de resultater, den oplever. For at opdage bedre handlinger og undgå at sidde fast i suboptimal adfærd, indfører agenten en vis grad af tilfældighed — den prøver lejlighedsvis alternative handlinger for at fremme udforskning.

Analogi

Forestil dig, at du er i en isbutik, og der er tre smagsvarianter tilgængelige: chokolade, vanilje og jordbær. Du elsker chokolade, så det vælger du som regel. Men en dag, af nysgerrighed, beslutter du dig for at prøve jordbær i stedet. Det viser sig, at jordbærisen i denne butik er utroligt velsmagende, og du vælger den, hver gang du besøger butikken.

At prøve en ny smag var ikke nødvendigvis det mest logiske valg baseret på tidligere erfaringer, men det gav dig mulighed for at opdage noget nyt. Og denne form for udforskning ligger i kernen af on-policy metoder.

Stokastiske politikker

Formelt betyder det at anvende denne idé, at man erstatter de deterministiske (hårde) politikker, der bruges i dynamisk programmering, med stokastiske (bløde) politikker, betegnet som $\pi(a | s)$, hvor:

Med andre ord har enhver handling i enhver tilstand en ikke-nul sandsynlighed for at blive valgt. Dette sikrer, at alle dele af miljøet på sigt kan blive udforsket, hvilket er essentielt, når man lærer af erfaring.

$\Large\varepsilon$-grådige politikker

For at indarbejde udforskning i politikken, låner vi begrebet $\varepsilon$-grådig udforskning fra multi-armed bandit-problemet. Dette gør det muligt at definere en stokastisk politik, der balancerer udnyttelse af den bedst kendte handling med udforskning af alternativer:

Denne politik opfører sig grådigt det meste af tiden — vælger handlingen med den højeste estimerede værdi — men med sandsynlighed $\varepsilon$ vælges en tilfældig handling, hvilket sikrer, at alle handlinger har en ikke-nul sandsynlighed for at blive valgt (selv den grådige igen, via uniform sampling).

Ved første øjekast kan denne tilgang virke problematisk: da politikken aldrig bliver rent grådig, vil den aldrig konvergere til den præcist optimale politik. Derfor opfylder den ikke strengt betingelserne for GPI, hvis vi forventer nøjagtig optimalitet i grænsen.

Dog kræver GPI ikke, at politikken bliver optimal med det samme — det kræver blot, at hver politik forbedres (eller forbliver den samme) sammenlignet med den forrige, og gradvist bevæger sig mod optimalitet. $\varepsilon$-grådig politik opfylder denne betingelse: den forbedrer politikken i gennemsnit og sikrer løbende udforskning for at understøtte bedre estimater.

For at løse problemet med konvergens til den egentligt optimale politik kan vi gradvist reducere $\varepsilon$ over tid. Denne strategi gør det muligt for politikken at blive mere og mere grådig, efterhånden som læringen skrider frem. I de tidlige faser hjælper udforskning med at indsamle forskelligartede erfaringer, mens agenten i de senere faser udnytter sin forbedrede viden. Med en korrekt aftagende $\varepsilon$ konvergerer metoden til en optimal politik i grænsen.

Pseudokode