REINFORCE

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.

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 θ