L'idea alla base dei metodi on-policy è intuitiva: un agente apprende seguendo la propria politica attuale e la migliora in base agli esiti che sperimenta. Per scoprire azioni migliori ed evitare di rimanere bloccato in comportamenti subottimali, l'agente incorpora un certo grado di casualità — provando occasionalmente azioni alternative per favorire l'esplorazione.

Analogia

Immagina di trovarti in una gelateria dove sono disponibili tre gusti: cioccolato, vaniglia e fragola. Ami il cioccolato, quindi di solito scegli quello. Ma un giorno, per curiosità, decidi di provare la fragola. Scopri che il gelato alla fragola di questa gelateria è incredibilmente buono e decidi di sceglierlo ogni volta che torni.

Provare un nuovo gusto non era necessariamente la scelta più logica basata sull'esperienza passata, ma ti ha dato l'opportunità di scoprire qualcosa di nuovo. Questo tipo di esplorazione è al centro dei metodi on-policy.

Politiche Stocastiche

Formalmente, adottare questa idea significa sostituire le politiche deterministiche (rigide) utilizzate nella programmazione dinamica con politiche stocastiche (flessibili), indicate come $\pi(a | s)$, dove:

In altre parole, ogni azione in ogni stato ha una probabilità diversa da zero di essere selezionata. Questo garantisce che tutte le parti dell'ambiente possano essere esplorate, aspetto essenziale quando si apprende dall'esperienza.

Politiche $\Large\varepsilon$-greedy

Per incorporare l'esplorazione nella politica, adottiamo il concetto di esplorazione $\varepsilon$-greedy dal problema multi-armed bandit. Questo ci permette di definire una politica stocastica che bilancia lo sfruttamento dell'azione migliore conosciuta con l'esplorazione di alternative:

Questa politica si comporta in modo greedy la maggior parte delle volte — scegliendo l'azione con il valore stimato più alto — ma con probabilità $\varepsilon$ seleziona un'azione casuale, garantendo che tutte le azioni abbiano una probabilità diversa da zero di essere scelte (inclusa nuovamente quella greedy, tramite campionamento uniforme).

A prima vista, questo approccio può sembrare problematico: poiché la politica non diventa mai puramente greedy, non convergerà mai esattamente alla politica ottimale. Pertanto, non soddisfa rigorosamente le condizioni per la GPI se ci si aspetta l'ottimalità esatta nel limite.

Tuttavia, la GPI non richiede che la politica diventi ottimale immediatamente — richiede solo che ogni politica migliori (o rimanga invariata) rispetto alla precedente, avvicinandosi progressivamente all'ottimalità. La politica $\varepsilon$-greedy soddisfa questa condizione: migliora la politica in media e garantisce un'esplorazione continua per supportare stime migliori.

Per affrontare il problema della convergenza verso la politica veramente ottimale, è possibile ridurre gradualmente $\varepsilon$ nel tempo. Questa strategia consente alla politica di diventare sempre più greedy man mano che l'apprendimento procede. Nelle fasi iniziali, l'esplorazione aiuta a raccogliere esperienze diversificate, mentre nelle fasi successive l'agente sfrutta la conoscenza migliorata. Con un $\varepsilon$ che decresce adeguatamente, il metodo converge a una politica ottimale nel limite.

Pseudocodice