Ideen bak on-policy-metoder er intuitiv: en agent lærer ved å følge sin nåværende policy og forbedrer denne policyen basert på utfallet den opplever. For å oppdage bedre handlinger og unngå å bli fastlåst i suboptimal atferd, inkorporerer agenten en viss grad av tilfeldighet — av og til prøver den alternative handlinger for å oppmuntre til utforskning.

Analogi

Tenk deg at du er i en iskrembutikk og det finnes tre smaker tilgjengelig: sjokolade, vanilje og jordbær. Du elsker sjokolade, så det er vanligvis det du velger. Men en dag, av nysgjerrighet, bestemmer du deg for å prøve jordbær i stedet. Det viser seg at jordbærisen i denne butikken er utrolig god, og du bestemmer deg for å velge den hver gang du besøker butikken.

Å prøve en ny smak var kanskje ikke det mest logiske valget basert på tidligere erfaringer, men det ga deg muligheten til å oppdage noe nytt. Og denne typen utforskning ligger i kjernen av on-policy-metoder.

Stokastiske policyer

Formelt innebærer dette å erstatte de deterministiske (harde) policyene som brukes i dynamisk programmering med stokastiske (myke) policyer, betegnet som $\pi(a | s)$, der:

Med andre ord har hver handling i hver tilstand en ikke-null sannsynlighet for å bli valgt. Dette sikrer at alle deler av miljøet til slutt kan utforskes, noe som er essensielt når man lærer av erfaring.

$\Large\varepsilon$-grådige policyer

For å inkludere utforskning i policyen, kan vi låne konseptet $\varepsilon$-grådig utforskning fra multi-armede bandittproblemet. Dette lar oss definere en stokastisk policy som balanserer mellom å utnytte den beste kjente handlingen og å utforske alternativer:

Denne policyen oppfører seg grådig mesteparten av tiden — den velger handlingen med høyest estimert verdi — men med sannsynlighet $\varepsilon$ velges en tilfeldig handling, noe som sikrer at alle handlinger har en ikke-null sannsynlighet for å bli valgt (også den grådige, via uniform trekking).

Ved første øyekast kan denne tilnærmingen virke problematisk: siden policyen aldri blir helt grådig, vil den aldri konvergere til den eksakt optimale policyen. Dermed oppfyller den ikke strengt kravene for GPI hvis vi forventer eksakt optimalitet i grensen.

Imidlertid krever ikke GPI at policyen blir optimal umiddelbart — det kreves kun at hver policy forbedres (eller forblir den samme) sammenlignet med den forrige, og gradvis beveger seg mot optimalitet. $\varepsilon$-grådig policy oppfyller dette kravet: den forbedrer policyen i gjennomsnitt, og sikrer kontinuerlig utforskning for å støtte bedre estimater.

For å løse problemet med konvergens til en virkelig optimal policy, kan vi gradvis redusere $\varepsilon$ over tid. Denne strategien lar policyen bli stadig mer grådig etter hvert som læringen skrider frem. I de tidlige fasene hjelper utforskning med å samle variert erfaring, mens agenten i senere faser utnytter sin forbedrede kunnskap. Med en riktig avtagende $\varepsilon$ vil metoden konvergere til en optimal policy i grensen.

Pseudokode