L'idée derrière les méthodes on-policy est intuitive : un agent apprend en suivant sa politique actuelle et améliore cette politique en fonction des résultats qu'il expérimente. Pour découvrir de meilleures actions et éviter de rester bloqué dans un comportement sous-optimal, l'agent intègre un certain degré d'aléa — essayant occasionnellement des actions alternatives pour favoriser l'exploration.

Analogie

Imaginez que vous êtes dans une boutique de glaces et qu'il y a trois parfums disponibles : chocolat, vanille et fraise. Vous adorez le chocolat, donc c'est généralement celui que vous choisissez. Mais un jour, par curiosité, vous décidez d'essayer la fraise à la place. Il s'avère que la glace à la fraise de cette boutique est incroyablement savoureuse, et vous décidez de la choisir à chaque fois que vous venez ici.

Essayer une nouvelle saveur n'était pas nécessairement le choix le plus logique selon l'expérience passée, mais cela vous a permis de découvrir quelque chose de nouveau. Ce type d'exploration est au cœur des méthodes on-policy.

Politiques stochastiques

Formellement, adopter cette idée signifie remplacer les politiques déterministes (dures) utilisées en programmation dynamique par des politiques stochastiques (souples), notées $\pi(a | s)$, où :

En d'autres termes, chaque action dans chaque état a une probabilité non nulle d'être sélectionnée. Cela garantit que toutes les parties de l'environnement peuvent éventuellement être explorées, ce qui est essentiel lors de l'apprentissage par l'expérience.

Politiques $\Large\varepsilon$-gloutonnes

Pour intégrer l'exploration dans la politique, utilisons le concept d'exploration $\varepsilon$-gloutonne issu du problème du bandit manchot. Cela permet de définir une politique stochastique qui équilibre l'exploitation de la meilleure action connue et l'exploration d'alternatives :

Cette politique agit de manière gloutonne la plupart du temps — choisissant l'action avec la valeur estimée la plus élevée — mais avec une probabilité $\varepsilon$, elle sélectionne une action aléatoire, garantissant que toutes les actions ont une chance non nulle d'être choisies (y compris la gloutonne, via un échantillonnage uniforme).

À première vue, cette approche semble problématique : puisque la politique ne devient jamais purement gloutonne, elle ne convergera jamais vers la politique optimale exacte. Ainsi, elle ne satisfait pas strictement les conditions du GPI si l'on attend l'optimalité exacte à la limite.

Cependant, le GPI n'exige pas que la politique devienne optimale immédiatement — il requiert seulement que chaque politique s'améliore (ou reste identique) par rapport à la précédente, progressant ainsi vers l'optimalité. La politique $\varepsilon$-gloutonne satisfait cette condition : elle améliore la politique en moyenne et assure une exploration continue pour de meilleures estimations.

Pour résoudre le problème de convergence vers la politique réellement optimale, on peut réduire progressivement $\varepsilon$ au fil du temps. Cette stratégie permet à la politique de devenir de plus en plus gloutonne à mesure que l'apprentissage progresse. Aux premiers stades, l'exploration permet de recueillir des expériences variées, tandis qu'aux stades ultérieurs, l'agent exploite ses connaissances améliorées. Avec une décroissance appropriée de $\varepsilon$, la méthode converge vers une politique optimale à la limite.

Pseudocode