REINFORCE

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

Une politique est une fonction quelconque π qui à chaque état s du système^[Lequel ?] associe une distribution de probabilité sur les actions^[Quoi ?]. On note π(a|s) la probabilité d'exécuter l'action a dans l'état s. Dans l'algorithme REINFORCE, on représente une politique avec un vecteur θ $\in$ $\mathbb {R} ^{d}$ . Les nombres dans le vecteur θ sont des paramètres dans une expression analytique qui représente la politique. On écrit π(a|s,θ) la probabilité d'exécution l'action a dans l'état s, quand il s'agit de la politique représentée par le vecteur θ.

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 :

$\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 donnée page 328 de^{[C'est-à-dire ?]} [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. Ainsi, à chaque épisode, c'est comme si nous étions dans un labyrinthe et que l'on avançait^{[style à revoir]} en ayant prédéterminé nos mouvements défini par θ . À la fin de l'épisode, on analyse ce qu'il s'est passé et ajuste le vecteur paramètre θ de la politique.

Génération d'un épisode

L'algorithme consiste à générer plusieurs épisodes $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, ..., $T$
$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))
$A_{0},A_{1},...,A_{T-1}$ sont les actions choisies (par exemple, aller à droite, à gauche, en haut, .... à droite)
$R_{1},...,R_{T}$ sont les récompenses obtenues par l'agent (par exemple, 1€, -3€, ... 4€).

Considérons un tel épisode $S_{0},A_{0},R_{1},...,S_{T-1},A_{T-1},R_{T}$ .

Mise à jour des paramètres de la politique

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 θ. A chaque étape de l'épisode, on calcule G qui est le total des récompenses depuis cette étape jusqu'à la fin de épisode. Cela permet de ne considérer que les récompenses futures et présentes.

Ce calcul de G permet de réajuster θ. Le vecteur θ est mis à jour à 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 :

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

Intuitivement, si la première composante de $\nabla \pi (A_{t}|S_{t},\theta )$ est positive, cela veut dire que si on augmente $\theta _{1}$ , alors la probabilité $\pi (A_{t}|S_{t},\theta )$ augmente. Donc, dans la mise à jour de θ, $\theta _{1}$ augmente.

Pseudo Code REINFORCE Monte Carlo policy gradient

Entrée : politique différentiable de paramétrisation π(a|s, θ), taux d'apprentissage α > 0                                 Sortie : paramètre de la politique θ optimisé                                                                                              Initialisation θ  $\in$   $\mathbb {R} ^{d}$                                                                                                                                                                       Pour chaque épisode : 
      Générer  $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:
            $G=\sum _{k=t+1}^{T}\gamma ^{k-t-1}R_{k}$                                                                                                       
            $\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 $\theta =\theta +\alpha \gamma ^{t}G\nabla ln(\pi (A_{t}|S_{t},\theta ))$ , ici, la mise à jour devient $\theta =\theta +\alpha \gamma ^{t}(G-v(S_{t},w))\nabla ln(\pi (A_{t}|S_{t},\theta ))$ où $v(S_{t},w)$ est l'approximation de la valeur de l'état $S_{t}$ , approximation paramétrée par le vecteur poids $w$ . En d'autres termes, l'impact de la récompense est réajustée en fonction de la valeur $v(S_{t},w)$ . Au lieu de pondérer le vecteur gradient par G, on le pondère désormais par $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 $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 θ  $\in$   $\mathbb {R} ^{d}$ , w  $\in$   $\mathbb {R} ^{d}$                                                                                                                                                                  Pour chaque épisode : 
      Générer  $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:
            $G=\sum _{k=t+1}^{T}\gamma ^{k-t-1}R_{k}$     
            $\omega =\omega +\alpha (G-v(S_{t},w))\nabla v(S_{t},w)$                                                                                                   
            $\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

(en) Ronald J. Williams, « Simple statistical gradient-following algorithms for connectionist reinforcement learning », Machine Learning, vol. 8, n^o 3,‎ 1^er mai 1992, p. 229–256 (ISSN 1573-0565, DOI 10.1007/BF00992696).
(en) Richard S. Sutton et Andrew G. Barto, Reinforcement Learning: An Introduction, A Bradford Book, coll. « Adaptive Computation and Machine Learning series », 13 novembre 2018 (ISBN 978-0-262-03924-6, lire en ligne).

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[:0-1] (en) Ronald J. Williams, « Simple statistical gradient-following algorithms for connectionist reinforcement learning », Machine Learning, vol. 8, n^o 3,‎ 1^er mai 1992, p. 229–256 (ISSN 1573-0565, DOI 10.1007/BF00992696).

[:1-2] (en) Richard S. Sutton et Andrew G. Barto, Reinforcement Learning: An Introduction, A Bradford Book, coll. « Adaptive Computation and Machine Learning series », 13 novembre 2018 (ISBN 978-0-262-03924-6, lire en ligne).