Algorithme acteur-critique

En apprentissage par renforcement, l'algorithme acteur-critique est un algorithme de difference temporelle utilisant la descente de gradients. Cet algorithme est composé de deux méthodes : Acteur et Critique.

Contexte modifier

L'algorithme REINFORCE avec ligne de base n'est pas considéré comme une méthode acteur-critique car la ligne de base n'est pas utilisé pour mettre à jour les valeurs des états, à l'inverse de la méthode acteur-critique.

Principes modifier

Acteur modifier

L'aspect acteur de cet algorithme permet de décider quelle est l'action à choisir pour un agent. Il y aura une mise à jour de la distribution de la politique suggéré par « critique ».

L'acteur est un approximateur de fonction (comme un réseau de neurones) et sa tâche est de produire la meilleure action pour un état donné.

Critique modifier

Cet aspect va venir évaluer l'action prise par "acteur". Il va informer à quel point l'action prise est bonne et comment l'ajuster. Le critique est un autre approximateur de fonction, qui reçoit en entrée l'environnement et l'action de l'acteur, les concatène et produit la valeur d'action (valeur Q) pour la paire donnée.

Il va donc y avoir un estimation de la fonction de valeur en évaluant la valeur de l'action prise ou de la valeur de l'état. Cette estimation est l'erreur de différence temporelle (ou Temporal Difference) : $\delta _{t}=r_{t+1}+\gamma V(s_{t+1})-V(s_{t})$ où V est la valeur actuelle implémenté par le critique, r la récompense à un état t, s l'état du s. Cette erreur permet de réajuster les paramètres de la politique et de la fonction état-valeur.

Principe One-step Actor-Critic (épisodique) modifier

Le but du One-step Actor-Critique est de modifier le paramètre θ de la politique par rapport au réajustement du paramètre ω du vecteur poids de la fonction état-valeur. Ici, par rapport à REINFORCE, l'algorithme donne des informations positives ou négatives directement après le choix de l'action dans l'état dans lequel nous nous trouvons.

Le vecteur θ de paramètres de la politique et le vecteur ω de paramètres de la fonction état-valeur sont initialisés 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 θ et des poids ω aléatoires.

Dans chaque épisode, nous initialisons S (le premier état de l'épisode) et I = 1 qui sera un coefficients de déclin. L'algorithme choisit une action A en suivant la politique π(.|S, θ) , puis observe l'état suivant S' et sa récompense associées. Puis nous mettons à jour les paramètres qui permettent de choisir les actions.

Mise à jour des paramètres de la politique et des paramètres de la fonction état-valeur modifier

Dans cette version, nous mettons à jour les paramètres de la politique et les poids de la fonction état-valeur. Cela permet d'obtenir des paramètres plus juste pour le choix des prochaines actions. Contrairement à Reinforce avec ligne de base, qui "utilise un fil d'Ariane", la méthode Actor-Critic donne des informations sur le choix de l'action selectionnée et rectifie le paramètre θ de la politique et le paramètre ω de la fonction état-valeur directement après. En effet, le calcul de $\delta =R+\gamma v(S',w)-v(S,w)$ permet de réajuster le paramètre ω de poids de la fonction état-valeur $\omega =\omega +\alpha '\delta \nabla v(S_{t},w)$ mais aussi le paramètre θ de la politique $\theta =\theta +\alpha I\delta \nabla ln(\pi (A_{t}|S_{t},\theta ))$ . Ce n'est pas le cas dans REINFORCE qui ne dépend que des récompenses R et d'un taux d'apprentissage α.

Ainsi, lors de chaque épisode et jusqu'à ce que l'état soit terminal, le choix de l'action suivante dépendra de la modification immédiate du paramètre ω de la fonction état-valeur et du paramètre θ de la politique.

Pseudo Code One-step Actor-Critic (épisodique) modifier

On donne ici la version de Actor-Critic donnée page 332 de ^[1].

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 : 
      Initialisation de S (premier état de chaque épisode)
      I = 1
      Tant que S n'est pas terminal :
           A ~ π(.|S, θ), choisir A et observer S' et R
            $\delta =R+\gamma v(S',w)-v(S,w)$ 
            $\omega =\omega +\alpha '\delta \nabla v(S_{t},w)$ 
            $\theta =\theta +\alpha I\delta \nabla ln(\pi (A_{t}|S_{t},\theta ))$ 
           I =  $\gamma$ I
           S = S'
Retourner θ, w

Principe Actor-Critique avec traces d'éligibilités (épisodique) modifier

Ici ,en plus de réajuster à chaque étape de chaque épisode, nous réajustons l'impact de la descente des gradients pour le calcul des paramètres de la politique et de la fonction état-valeur. On initialise les vecteur d'éligibilité z et z' à 0.

Dans cette version, en plus de mettre à jour les paramètres de la politique et de la fonction état-valeur, nous mettons aussi à jour le poids de la descente de gradient.

Mise à jour des paramètres de la politique et des paramètres de la fonction état-valeur modifier

Danc cette version de l'algorithme, on calcule $z=\gamma \lambda z+\nabla v(S,w)$ et $z=\gamma \lambda 'z'+I\nabla ln(\pi (A|S,\theta ))$ . Cela permet de donner un certain poids au calcul : $\nabla ln(\pi (A_{t}|S_{t},\theta ))={\frac {\nabla \pi (A_{t}|S_{t},\theta )}{\pi (A_{t}|S_{t},\theta )}}$ .

Après avoir calculé z et z', on peut calculer $\omega =\omega +\alpha '\delta z'$ et $\theta =\theta +\alpha \delta z$ .

Pseudo Code Actor-Critique avec traces d'éligibilités (épisodique) modifier

On donne ici la version de Actor-Critic donnée page 332 de^[1] .

Entrée : politique différentiable de paramétrisation π(a|s, θ),
         fonction état-valeur v(s,w), 
         taux d'apprentissage α > 0 , α' > 0, 
         déclin des traces λ  $\in [0,1]$ , λ'  $\in [0,1]$ 
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 : 
      Initialisation de S (premier état de chaque épisode)
      z = 0 (vector d'éligibilité)
      z' = 0 (vector d'éligibilité)
      I = 1
      Tant que S n'est pas terminal :
           A ~ π(.|S, θ), choisir A et observer S' et R
            $\delta =R+\gamma v(S',w)-v(S,w)$ 
           z =  $\gamma \lambda z+\nabla v(S,w)$ 
           z' =  $\gamma \lambda 'z'+I\nabla ln(\pi (A|S,\theta ))$ 
            $\omega =\omega +\alpha '\delta z'$ 
            $\theta =\theta +\alpha \delta z$ 
           I =  $\gamma$ I
           S = S'
Retourner θ, w

Pseudo Code Actor-Critique avec traces d'éligibilités (continue) modifier

On donne ici la version de Actor-Critic donnée page 333 de ^[1].

Entrée : politique différentiable de paramétrisation π(a|s, θ),
         fonction état-valeur v(s,w), 
         taux d'apprentissage α > 0 , α' > 0, α" > 0 
         déclin des traces λ  $\in [0,1]$ , λ'  $\in [0,1]$ 
Sortie : paramètre de la politique θ optimisé et poids de la fonction état-valeur w optimisé 

Initialisation R'  $\in \mathbb {R} ^{d}$ 
Initialisation θ  $\in$   $\mathbb {R} ^{d}$ , w  $\in$   $\mathbb {R} ^{d}$ 
Initialisation de S (premier état de chaque épisode)

z = 0 (vector d'éligibilité)
z' = 0 (vector d'éligibilité)

Boucle infinie (pour chaque étape):
           A ~ π(.|S, θ), choisir A et observer S' et R
            $\delta =R-R'+\gamma v(S',w)-v(S,w)$ 
            $R'=R'+\alpha ''\delta$ 
           z =  $\lambda z+\nabla v(S,w)$ 
           z' =  $\lambda 'z'+I\nabla ln(\pi (A|S,\theta ))$ 
            $\omega =\omega +\alpha '\delta z'$ 
            $\theta =\theta +\alpha \delta z$ 
           S = S'
Retourner θ, w

Notes et références modifier

↑ ^{a b et c} (en) Richard S. Sutton and Andrew G.Barton, Reinforcement Learning : An Introduction, A Bradford Book, 2018, Second Edition éd. (ISBN 9780262039246, lire en ligne)

Portail de l'informatique théorique

[:0-1] {a b et c} (en) Richard S. Sutton and Andrew G.Barton, Reinforcement Learning : An Introduction, A Bradford Book, 2018, Second Edition éd. (ISBN 9780262039246, lire en ligne)

[1]