Aller au contenu

REINFORCE

Un article de Wikipédia, l'encyclopédie libre.

En intelligence artificielle, plus précisément en apprentissage automatique, REINFORCE est un algorithme d'apprentissage par renforcement qui applique directement une méthode de gradient sur la politique. C'est une méthode policy-gradient qui s'oppose aux méthodes qui optimisent la valeur (comme le Q-learning). Il est introduit par Ronald Williams en 1992[1].

Représentation d'une politique

[modifier | modifier le code]

Considérons un système, par exemple un robot qui se déplace sur une grille. Le système est dans un certain état. Par exemple, un état peut être la position du robot sur la grille. Les actions du robot sont par exemple : aller à gauche, aller à droite, aller en haut, aller en bas ou rester sur place. Une politique est une fonction quelconque qui à chaque état du système associe une distribution de probabilité sur les actions. On note la probabilité d'exécuter l'action dans l'état . Dans l'algorithme REINFORCE, on représente une politique avec un vecteur θ . Pour souligner que la politique dépend du vecteur , on la note π(·[Quoi ?], θ). Les nombres dans le vecteur sont des paramètres dans une expression analytique qui représente la politique. On écrit la probabilité d'exécution de l'action dans l'état , quand il s'agit de la politique paramétrisée par le vecteur .

Par exemple, considérons un robot où l'état s est représenté par sa position (x1(s), x2(s)) dans le plan. On peut imaginer que la probabilité d'exécuter l'action a dans l'état s est donnée par

où le vecteur θ est la collection de tous les paramètres θ1,a, θ2,a pour toutes les actions a.

Principe REINFORCE Monte Carlo policy gradient

[modifier | modifier le code]

On donne ici la version de REINFORCE expliquée dans la page 328 du livre de Reinforcement Learning: An Introduction de Sutton et Barto [2]. Le vecteur θ de paramètres de la politique est initialisé aléatoirement. En d'autres termes, l'algorithme démarre avec une politique choisie aléatoirement dans l'espace des politiques paramétrées par θ. L'algorithme effectue plusieurs épisodes. Durant chaque épisode, l'agent suit la politique π(·|·, θ). À la fin de chaque épisode, on analyse ce qu'il s'est passé et on ajuste le vecteur paramètre θ de la politique.

Génération d'un épisode

[modifier | modifier le code]

L'algorithme consiste à générer plusieurs épisodes en utilisant la politique courante π(·|·, θ) où

  • les instants sont 0, 1, ...,
  • sont les états à l'instant 0, 1, ..., T-1 (par exemple, les positions d'un robot dans le plan comme (0, 1), (1, 1), (0, 1), (0, 2), .... (3, 4))
  • sont les actions choisies (par exemple, aller à droite, à gauche, en haut, .... à droite)
  • sont les récompenses obtenues par l'agent (par exemple, 1€, -3€, ... 4€).

Considérons un tel épisode . Plus précisément, est l'état initial. Puis, l'agent choisit une action selon la distribution de probabilité . Puis l'agent reçoit une récompense et va dans l'état . Puis, l'agent choisit une action selon la distribution de probabilité , etc.

Mise à jour des paramètres de la politique

[modifier | modifier le code]

L'algorithme modifie la politique courante en fonction de l'expérience acquise pendant l'épisode . Autrement dit, il s'agit de mettre à jour les poids θ. À chaque étape t de l'épisode, on calcule le gain G à partir de l'étape t. Il s'agit du total des récompenses depuis cette étape t jusqu'à la fin de épisode. Cela permet de ne considérer que les récompenses futures et présentes. Autrement dit :

.

Plus généralement, on considère un gain où les récompenses sont réajustées avec un facteur de dévaluation  :

Ce calcul de G permet de réajuster θ de la façon suivante :

est un taux d'apprentissage, et où est le vecteur gradient de (vecteur gradient sur les variables ). Le taux d'apprentissage est compris entre 0 et 1. Les valeurs limites s'interprètent de la façon suivante : si , alors le vecteur n'est pas mis à jour et l'agent n'apprend pas ; si , l'agent oublie tout ce qu'il a appris jusqu'à présent. Ainsi, le vecteur θ est mis à jour pour chaque étape de l'épisode à partir de son ancienne valeur à laquelle on ajoute le vecteur gradient du logarithme de la politique pondéré par le taux d'apprentissage et G. Ce vecteur gradient est égal à :

.

Donnons une explication intuitive de la mise à jour. Supposons que G est positif. Ainsi, il est plus souhaitable de jouer dans l'état . Autrement on aimerait modifier θ afin d'augmenter . La mise à jour renforce bien cela. En effet, si la première composante de est positive, cela veut dire que si on augmente , alors la probabilité augmente. Et la mise à jour augmente bien . Si la première composante de est négative, c'est décroitre qui augmente , et la mise à jour décroit . Si G est négatif, la mise à jour de θ diminue .

Pseudo Code REINFORCE Monte Carlo policy gradient

[modifier | modifier le code]
Entrée : politique différentiable π(·|·, θ) de paramétrisation θ, taux d'apprentissage α > 0
Sortie : paramètre de la politique θ optimisé
Initialisation θ  
Pour chaque épisode : 
      Générer  en suivant la politique π(·|·, θ)     
      Pour chaque étape de chaque épisode t = 0, 1, ..., T-1:
           
           
Retourner θ

REINFORCE avec ligne conductrice

[modifier | modifier le code]

On donne ici la version de REINFORCE avec ligne conductrice donnée page 330[C'est-à-dire ?] de [2] . La ligne directrice est un peu comme[style à revoir] un fil d 'Ariane dans le labyrinthe contrairement à la méthode Actor-Critic. Ici, nous utilisons la fonction état-valeur comme ligne directrice. Alors que dans REINFORCE Monte Carlo classique où la mise à jour est , ici, la mise à jour devient est l'approximation de la valeur de l'état , approximation paramétrée par le vecteur poids . En d'autres termes, l'impact de la récompense est réajustée en fonction de la valeur . Au lieu de pondérer le vecteur gradient par G, on le pondère désormais par [pas clair].

Le squelette de l'algorithme est similaire. En plus d'initialiser le vecteur θ de paramètres de la politique, on initialise aussi un vecteur de poids ω de la fonction état-valeur aléatoirement. Le calcul de G permet de réajuster θ et mais aussi ω. La mise à jour de ω s'effectue avec une méthode de gradient, où le vecteur gradient est aussi pondéré par .

À la fin, on obtient le paramètre de la politique et ainsi que le paramètre de la fonction état-valeur réajustés.

Entrée : politique différentiable de paramétrisation π(a|s, θ),
         fonction état-valeur v(s,w), taux d'apprentissage α > 0 , α' > 0
Sortie : paramètre de la politique θ optimisé et poids de la fonction état-valeur w optimisé
Initialisation θ  , w    
Pour chaque épisode : 
      Générer  en suivant la politique π(a|s, θ)     
      Pour chaque étape de chaque épisode t = 0, 1, .., T-1:
               
           
           
Retourner θ, w

Notes et références

[modifier | modifier le code]
  1. (en) Ronald J. Williams, « Simple statistical gradient-following algorithms for connectionist reinforcement learning », Machine Learning, vol. 8, no 3,‎ , p. 229–256 (ISSN 1573-0565, DOI 10.1007/BF00992696).
  2. a et b (en) Richard S. Sutton et Andrew G. Barto, Reinforcement Learning: An Introduction, A Bradford Book, coll. « Adaptive Computation and Machine Learning series », (ISBN 978-0-262-03924-6, lire en ligne).