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 beslutter dig for at vælge 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 er kernen i on-policy metoder.

Stokastiske politikker

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

Med andre ord har hver handling i hver 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, anvendes 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 man forventer nøjagtig optimalitet i grænsen.

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

For at løse problemet med konvergens mod den egentlige optimale politik kan $\varepsilon$ gradvist reduceres over tid. Denne strategi gør politikken mere og mere grådig, efterhånden som læringen skrider frem. I de tidlige faser hjælper udforskning med at indsamle varieret erfaring, mens agenten i de senere faser udnytter sin forbedrede viden. Med en passende aftagende $\varepsilon$ konvergerer metoden til en optimal politik i grænsen.

Pseudokode