REINFORCE

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

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 ${\displaystyle \pi }$ qui à chaque état ${\displaystyle s}$ du système associe une distribution de probabilité sur les actions. On note ${\displaystyle \pi (a|s)}$ la probabilité d'exécuter l'action ${\displaystyle a}$ dans l'état ${\displaystyle s}$. Dans l'algorithme REINFORCE, on représente une politique avec un vecteur θ ${\displaystyle \in }$ ${\displaystyle \mathbb {R} ^{d}}$. Pour souligner que la politique dépend du vecteur ${\displaystyle \theta }$, on la note π(·^[Quoi ?], θ). Les nombres dans le vecteur ${\displaystyle \theta }$ sont des paramètres dans une expression analytique qui représente la politique. On écrit ${\displaystyle \pi (a|s,\theta )}$ la probabilité d'exécution de l'action ${\displaystyle a}$ dans l'état ${\displaystyle s}$, quand il s'agit de la politique paramétrisée par le vecteur ${\displaystyle \theta }$.

Exemple

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

${\displaystyle \pi (a|s,\theta )={\frac {e^{x_{1}(s)\theta _{1,a}+x_{2}(s)\theta _{2,a}}}{\sum _{a'}e^{x_{1}(s)\theta _{1,a'}+x_{2}(s)\theta _{2,a'}}}}}$

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

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

L'algorithme consiste à générer plusieurs épisodes ${\displaystyle S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}}$ en utilisant la politique courante π(·|·, θ) où

• les instants sont 0, 1, ..., ${\displaystyle T}$
• ${\displaystyle S_{0},S_{1},...,S_{T-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))
• ${\displaystyle A_{0},A_{1},...,A_{T-1}}$sont les actions choisies (par exemple, aller à droite, à gauche, en haut, .... à droite)
• ${\displaystyle R_{1},...,R_{T}}$ sont les récompenses obtenues par l'agent (par exemple, 1€, -3€, ... 4€).

Considérons un tel épisode ${\displaystyle S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}}$. Plus précisément, ${\displaystyle S_{0}}$ est l'état initial. Puis, l'agent choisit une action ${\displaystyle A_{0}}$ selon la distribution de probabilité ${\displaystyle \pi (\cdot \mid S_{0},\theta )}$. Puis l'agent reçoit une récompense ${\displaystyle R_{1}}$et va dans l'état ${\displaystyle S_{1}}$. Puis, l'agent choisit une action ${\displaystyle A_{2}}$ selon la distribution de probabilité ${\displaystyle \pi (\cdot \mid S_{1},\theta )}$, etc.

Mise à jour des paramètres de la politique

L'algorithme modifie la politique courante en fonction de l'expérience acquise pendant l'épisode ${\displaystyle S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}}$. 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 :

${\displaystyle G=\sum _{k=t+1}^{T}R_{k}}$.

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

${\displaystyle G=\sum _{k=t+1}^{T}\gamma ^{k-t-1}R_{k}}$

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

${\displaystyle \theta :=\theta +\alpha \gamma ^{t}G\nabla ln(\pi (A_{t}|S_{t},\theta ))}$

où ${\displaystyle \alpha }$ est un taux d'apprentissage, et où ${\displaystyle \nabla ln(\pi (A_{t}|S_{t},\theta ))}$ est le vecteur gradient de ${\displaystyle ln(\pi (A_{t}|S_{t},\theta ))}$ (vecteur gradient sur les variables ${\displaystyle \theta }$). Le taux d'apprentissage ${\displaystyle \alpha }$ est compris entre 0 et 1. Les valeurs limites s'interprètent de la façon suivante : si ${\displaystyle \alpha =0}$, alors le vecteur ${\displaystyle \theta }$ n'est pas mis à jour et l'agent n'apprend pas ; si ${\displaystyle \alpha =1}$, 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 ${\displaystyle \alpha }$ et G. Ce vecteur gradient ${\displaystyle \nabla ln(\pi (A_{t}|S_{t},\theta ))}$ est égal à :

${\displaystyle \nabla ln(\pi (A_{t}|S_{t},\theta ))={\frac {\nabla \pi (A_{t}|S_{t},\theta )}{\pi (A_{t}|S_{t},\theta )}}}$.

Donnons une explication intuitive de la mise à jour. Supposons que G est positif. Ainsi, il est plus souhaitable de jouer ${\displaystyle A_{t}}$ dans l'état ${\displaystyle S_{t}}$. Autrement on aimerait modifier θ afin d'augmenter ${\displaystyle \pi (A_{t}|S_{t},\theta )}$. La mise à jour renforce bien cela. En effet, si la première composante de ${\displaystyle \nabla \pi (A_{t}|S_{t},\theta )}$ est positive, cela veut dire que si on augmente ${\displaystyle \theta _{1}}$, alors la probabilité ${\displaystyle \pi (A_{t}|S_{t},\theta )}$ augmente. Et la mise à jour augmente bien ${\displaystyle \theta _{1}}$. Si la première composante de ${\displaystyle \nabla \pi (A_{t}|S_{t},\theta )}$ est négative, c'est décroitre ${\displaystyle \theta _{1}}$qui augmente ${\displaystyle \nabla \pi (A_{t}|S_{t},\theta )}$, et la mise à jour décroit ${\displaystyle \theta _{1}}$. Si G est négatif, la mise à jour de θ diminue ${\displaystyle \pi (A_{t}|S_{t},\theta )}$.

Pseudo Code REINFORCE Monte Carlo policy gradient

Entrée : politique différentiable π(·|·, θ) de paramétrisation θ, taux d'apprentissage α > 0
Sortie : paramètre de la politique θ optimisé
Initialisation θ ${\displaystyle \in }$ ${\displaystyle \mathbb {R} ^{d}}$
Pour chaque épisode : 
      Générer ${\displaystyle S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}}$ en suivant la politique π(·|·, θ)     
      Pour chaque étape de chaque épisode t = 0, 1, ..., T-1:
           ${\displaystyle G:=\sum _{k=t+1}^{T}\gamma ^{k-t-1}R_{k}}$
           ${\displaystyle \theta :=\theta +\alpha \gamma ^{t}G\nabla ln(\pi (A_{t}|S_{t},\theta ))}$
Retourner θ

REINFORCE avec ligne conductrice

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 ${\displaystyle \theta =\theta +\alpha \gamma ^{t}G\nabla ln(\pi (A_{t}|S_{t},\theta ))}$, ici, la mise à jour devient ${\displaystyle \theta =\theta +\alpha \gamma ^{t}(G-v(S_{t},w))\nabla ln(\pi (A_{t}|S_{t},\theta ))}$ où ${\displaystyle v(S_{t},w)}$ est l'approximation de la valeur de l'état ${\displaystyle S_{t}}$, approximation paramétrée par le vecteur poids ${\displaystyle w}$. En d'autres termes, l'impact de la récompense est réajustée en fonction de la valeur ${\displaystyle v(S_{t},w)}$. Au lieu de pondérer le vecteur gradient par G, on le pondère désormais par ${\displaystyle G-v(S_{t},w)}$^[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 ${\displaystyle G-v(S_{t},w)}$.

À 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 θ ${\displaystyle \in }$ ${\displaystyle \mathbb {R} ^{d}}$, w ${\displaystyle \in }$ ${\displaystyle \mathbb {R} ^{d}}$  
Pour chaque épisode : 
      Générer ${\displaystyle S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}}$ en suivant la politique π(a|s, θ)     
      Pour chaque étape de chaque épisode t = 0, 1, .., T-1:
           ${\displaystyle G=\sum _{k=t+1}^{T}\gamma ^{k-t-1}R_{k}}$    
           ${\displaystyle \omega =\omega +\alpha (G-v(S_{t},w))\nabla v(S_{t},w)}$
           ${\displaystyle \theta =\theta +\alpha \gamma ^{t}(G-v(S_{t},w))\nabla ln(\pi (A_{t}|S_{t},\theta ))}$
Retourner θ, w

Notes et références

• Portail de l'informatique théorique