Contrôle Monte Carlo Sur Politique

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 une part de hasard — essayant occasionnellement des actions alternatives afin de favoriser l'exploration.

Analogie

Imaginez que vous êtes dans une boutique de glaces où trois parfums sont disponibles : chocolat, vanille et fraise. Vous adorez le chocolat, donc c'est généralement ce 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 visite.

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

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ù :

Autrement dit, 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, empruntons le concept d'exploration $\varepsilon$-gloutonne 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, se rapprochant progressivement de 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