REINFORCE

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.

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.

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 )}$.

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 θ

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

• Portail de l'informatique théorique