Het idee achter on-policy methoden is intuïtief: een agent leert door zijn huidige beleid te volgen en verbetert dat beleid op basis van de uitkomsten die hij ervaart. Om betere acties te ontdekken en te voorkomen dat hij vastloopt in suboptimaal gedrag, verwerkt de agent een zekere mate van willekeur — af en toe probeert hij alternatieve acties om verkenning te stimuleren.

Analogie

Stel je voor dat je in een ijssalon bent en er zijn drie smaken beschikbaar: chocolade, vanille en aardbei. Je houdt van chocolade, dus dat kies je meestal. Maar op een dag besluit je uit nieuwsgierigheid om in plaats daarvan aardbei te proberen. Het blijkt dat het aardbeienijs in deze winkel ongelooflijk lekker is, en je besluit het voortaan te kiezen wanneer je deze winkel bezoekt.

Het proberen van een nieuwe smaak was niet per se de meest logische keuze op basis van eerdere ervaringen, maar het bood de mogelijkheid om iets nieuws te ontdekken. Dit soort verkenning vormt de kern van on-policy methoden.

Stochastische beleidsregels

Formeel betekent het aannemen van dit idee het vervangen van de deterministische (harde) beleidsregels die in dynamisch programmeren worden gebruikt door stochastische (zachte) beleidsregels, aangeduid als $\pi(a | s)$, waarbij:

Met andere woorden, elke actie in elke toestand heeft een niet-nul kans om geselecteerd te worden. Dit zorgt ervoor dat alle delen van de omgeving uiteindelijk kunnen worden verkend, wat essentieel is bij het leren uit ervaring.

$\Large\varepsilon$-gulzige beleidsvormen

Om exploratie in het beleid te verwerken, wordt het concept van $\varepsilon$-gulzige exploratie uit het multi-armed bandit probleem overgenomen. Hiermee kan een stochastisch beleid worden gedefinieerd dat het benutten van de best bekende actie afwisselt met het verkennen van alternatieven:

Dit beleid gedraagt zich meestal gulzig — het kiest de actie met de hoogste geschatte waarde — maar met kans $\varepsilon$ wordt een willekeurige actie geselecteerd, zodat alle acties een niet-nul kans hebben om gekozen te worden (ook de gulzige actie opnieuw, via uniforme steekproeven).

Op het eerste gezicht lijkt deze aanpak problematisch: omdat het beleid nooit volledig gulzig wordt, zal het nooit exact naar het optimale beleid convergeren. Het voldoet dus niet strikt aan de voorwaarden voor GPI als exacte optimaliteit in de limiet wordt verwacht.

Echter, GPI vereist niet dat het beleid direct optimaal wordt — het vereist alleen dat elk beleid verbeterd (of gelijk blijft) ten opzichte van het vorige, en zo geleidelijk richting optimaliteit beweegt. Het $\varepsilon$-gulzige beleid voldoet aan deze voorwaarde: het verbetert het beleid gemiddeld genomen en zorgt voor voortdurende exploratie om betere schattingen te ondersteunen.

Om het probleem van convergentie naar het werkelijk optimale beleid aan te pakken, kan $\varepsilon$ geleidelijk worden verminderd in de tijd. Deze strategie zorgt ervoor dat het beleid steeds gulziger wordt naarmate het leerproces vordert. In de beginfase helpt exploratie om diverse ervaringen te verzamelen, terwijl in latere fasen de agent zijn verbeterde kennis benut. Met een correct afnemende $\varepsilon$ convergeert de methode in de limiet naar een optimaal beleid.

Pseudocode