Programmation Dynamique Monte-Carlo

Lors de notre dernier article, nous avons vu le processus de décision markovien qui utilise la programmation dynamique. Pour rappel, cette méthode est utilisée lorsque nous connaissons l’ensemble des états et des actions possibles dans un environnement. Pour chacune des actions prises, nous allons attribuer une récompense et notre objectif est donc de choisir les actions qui maximisent notre récompense. Cependant, avec cette méthode, nous avons quelques inconvénients. En effet, afin de pouvoir obtenir la récompense la plus importante, nous allons essayer tous les états possibles. Nous sommes donc dans un système par force brute. Cela nous amène à un second problème. En effet, plus l’environnement sera important, et plus le nombre d’états et d’actions sera important.

Approche par Monte-Carlo

Une approche par Monte-Carlo peut être intéressante. Dans cette approche, nous n’avons pas besoin de connaître l’ensemble des états se situant après l’état actuel. Nous les mettons à jour et les découvrons au fur et à mesure, lorsque nous les visitons. Ainsi, il nous reste plus qu'à aborder la partie liée au choix des actions. En effet, la question que l’on peut se poser est comment allons nous choisir telle ou telle action. Dans une approche Monte-Carlo, nous allons choisir l’action de manière aléatoire au début. Puis, une fois que notre système aura gagné de l’expérience, une approche plus intelligente pourra prendre le dessus. Ainsi, notre système va collecter de l’expérience afin de devenir meilleur. Afin de modéliser ce système d’un point de vue mathématique, nous allons utiliser les équations de Bellman afin de pouvoir estimer la récompense de chaque état. Cette approche va nous permettre d’obtenir, au fur et à mesure, la meilleure stratégie possible.

Q Learning

Nous allons introduire une nouvelle méthode appelée Q Learning. Le Q est pour “Qualité” et sa valeur se base sur la découverte de récompense sur le long-terme que nous allons obtenir en prenant une action a dans un état s. La politique de cette méthode consiste à choisir la qualité maximum, parmi l’ensemble des possibilités que nous allons avoir.

Modification apportée

Les différents changements que nous avons avec cette méthode, comparer à la méthode que nous avons abordé dans l’article précédent, est que nous allons avoir des estimations et non des valeurs parfaites. En effet, nous allons prendre des actions de manière aléatoire. Lors de l’exploration, nous n’allons pas forcément tester l’ensemble des possibilités présentes. De plus, avec cette méthode, nous allons apprendre à partir de l'expérience que nous allons obtenir sans savoir après coup quelle est la meilleure action. Ce que nous allons faire, c’est calculer la valeur attendue en fonction de la politique défini sur l’état actuel. Enfin, la meilleure valeur estimée correspond à la meilleure politique estimée ce qui correspond donc aux meilleures valeurs déterminées.

La politique de notre système

Dans ce système, nous allons avoir des tables de correspondance pour chaque état nous donnant la meilleure action possible. Pour ce faire, nous allons commencer avec une politique aléatoire. Puis, nous allons réaliser différentes actions, gagner de l’expérience et ainsi permettre à notre système de s’améliorer. Il va ainsi apprendre de ses erreurs et choisir, au fur et à mesure, les meilleures solutions possibles. De ce fait, en ayant de meilleur valeur estimée, nous obtenons une meilleure politique.

La fonction de retour de G

Le retour de notre méthode va nous donner la récompense de notre action immédiate, avec l’ensemble des récompenses futures actualisées en fonction de notre politique actuelle. Nous notons par G le retour de notre fonction. Ainsi, nous allons obtenir :

Ici, nous avons le résultat immédiat “r”, suivi de l’ensemble des gains que nous allons obtenir multiplier par le paramètre gamma. Pour rappel, le paramètre Gamma correspond à la manière dont nous allons gérer nos gains (long-terme versus court-terme). Nous aborderons plus en détail ce point un peu plus tard dans cet article. Afin d’estimer le résultat d’un état, nous allons, dans un premier temps, récupérer un ensemble de couples (state, G). Afin de définir la valeur de retour G, il nous suffit de réaliser la moyenne nous permettant d’obtenir une approximation de notre résultat.

Algorithme pour calculer la valeur de retour

• Initialisation de G à 0
• Création du tableau et initialisation à vide (etats_et_retour = [])
• Regarder dans la liste des états/récompenses celle qui correspond
  • Ajouter le couple (état, G) dans etats_et_retour
  • G = r + gamma * G
• Renverser etats_et_retour dans l’ordre original

Dilemme Exploration et Exploitation

Lors du dernier article, nous avons abordé ces notions. Pour rappel, il s’agit de définir quand est-ce que nous allons arrêter la phase d’exploration de notre algorithme. En effet, étant donné que notre système ne connaît pas les conséquences des actions présentées dans l’environnement, il a besoin de les apprendre. Cependant, il faut imposer une certaine limite et dire à notre système qu’il a suffisamment appris. Pour plus de détail, je vous renvoie à mon ancien article. Pour ce faire, nous allons utiliser l’epsilon greedy qui est un hyper paramètre. Il correspond à la probabilité que notre système explore une nouvelle action.

Implémentation

Afin de permettre à notre système de changer de l’état d’exploration à l’état d’exploitation, il nous suffit de générer un nombre aléatoire p compris entre 0 et 1. Si p < (1 - epsilon), dans ce cas-là, nous allons prendre l’action définie par notre politique. Nous allons donc exploiter nos connaissances. Sinon, nous allons prendre une action aléatoire.

Algorithme Monte-Carlo Q Learning

Pour finir cet article, nous allons voir un algorithme implémentant l’approche par Monte-Carlo Q Learning.

• Initialisation de notre politique (policy) par un choix aléatoire des actions
• Initialisation pour tous les états et les actions de Q[(s,a)] a 0
• Initialisation des résultats pour chaque état/action possible (returns[s,a]) par une liste vide.
• Boucle N fois (suffisamment de valeur pour converger)
  • Parcours de notre environnement et récupère la liste des résultats des états/actions
  • Pour (s, A, G) dans la liste de résultats
    • Si nous n’avons pas vu la paire (s,a)
      • Nous ajoutons G à la liste returns[s,a]
      • Q[s][a] = mean(returns[s,a])
    • Pour tous les états possibles non-finaux s
      • policy[s] = l’action avec la plus grande valeur de Q pour l’état s
• Pour tous les états s
  • V[s] = la plus grande valeur de Q pour l’état s correspondant
• Retour de V et de la policy