PC & Mobile

Double Q-Learning the Easy Way – Vers la science des données

Double Q-Learning the Easy Way - Vers la science des données


Q-learning (Watkins, 1989) est considéré comme l'une des avancées majeures de l'algorithme d'apprentissage par renforcement avec contrôle TD.

Cependant, dans son article, Double Q-Learning, Hado van Hasselt explique comment Q-Learning fonctionne très mal dans certains environnements stochastiques. Il a souligné que la faible performance était due à une surestimation importante des valeurs d’action due à l’utilisation de Max Q (s ’, a) dans Q-learning.

Pour remédier à ce problème, il a proposé la méthode Double Q-Learning.

Le problème

Considérons un MDP ayant quatre états, dont deux sont des états terminaux.
L’état A est toujours considéré à l’état initial et comporte deux actions, droite ou gauche. L'action Right ne donne aucune récompense et atterrit dans l'état terminal C.
L'action Gauche déplace l'agent vers l'état B avec une récompense nulle.

L’état B ayant un certain nombre d’actions, il déplace l’agent vers l’état terminal D. Cependant, (c’est important), la récompense R de chaque action de B à D a un effet positif. valeur aléatoire qui suit une distribution normale avec une moyenne de -0,5 et une variance de 1,0.

On sait que la valeur attendue de R est négative (-0,5). Cela signifie que sur un grand nombre d'expériences, la valeur moyenne de R est inférieure à zéro.

Sur la base de cette hypothèse, il est clair que le déplacement à gauche de A est toujours une mauvaise idée. Cependant, étant donné que certaines des valeurs de R sont positives, Q-Learning aura tort de considérer que le fait de quitter la gauche de A maximise la récompense. En réalité, c'est une mauvaise décision, car même si cela fonctionne pour certains épisodes, à long terme, c'est une récompense négative.

Alors pourquoi Q-Learning surestime-t-il?
Pour répondre à cette question, considérons le scénario suivant:
Soit X1 et X2 deux variables aléatoires représentant la récompense de deux actions à l'état B. Etant donné qu'elles sont des variables aléatoires, nous allons calculer leurs valeurs attendues E (X1) et E (X2). Il y a un problème cependant, nous ne connaissons pas les valeurs attendues. Nous pouvons donc utiliser des estimations de ces valeurs attendues en calculant la moyenne incrémentielle 𝝁1 et 2. Ces estimations sont non biaisées car, à mesure que le nombre d'échantillons augmente, la moyenne de l'ensemble des valeurs se rapproche de E (X1) et E (X2), comme le montre le tableau ci-dessous.

Cependant, Q-Learning utilise Max Q (s ’, a), représenté dans le tableau par Max (). Le tableau (voir les cellules rouges) montre clairement que E (Max (𝝁)) est différent de Max E (X). Cela indique que Max () n'est pas un bon estimateur pour Max E (X). C'est biaisé!
En d’autres termes, lors de la mise à jour de Q (s, a) avec Max Q (s ’, a), Q (s, a) n’avance pas vers la valeur attendue des actions à l’état B qui est -0,5.

Ce scénario permet de comprendre pourquoi Q-Learning surestime les valeurs. Une démonstration mathématique formelle peut être trouvée dans l'article.

La solution

La solution proposée consiste à maintenir deux fonctions Q-value QA et QB, chacune d’elles bénéficiant d’une mise à jour de l’autre pour l’état suivant.
La mise à jour consiste à rechercher l’action a * qui optimise le contrôle qualité dans l’état suivant (Q (s ', a *) = Q max (s', a)), puis utilise un * pour obtenir la valeur de QB (s ', a *) pour mettre à jour le QA (s, a).

Le pseudo-code ci-dessous montre le comportement de l'algorithme. Notez qu'il existe un code python à la fin de l'article qui compare les deux méthodes.
La ligne 3 de l'algorithme montre comment choisir une action parmi les deux fonctions de valeur Q. Par exemple, il est possible de fusionner les deux Q (moyenne des valeurs pour chaque action), puis d’appliquer epsilon-glouton.

L'algorithme met à jour à la fois QA et QB d'une manière équiprobable.

Algorithme tiré de Double Q-learning de Hado van Hasselt

Les graphiques ci-dessous montrent une comparaison entre Double Q-Learning et Q-Learning lorsque le nombre d'actions à l'état B est 10 et 100 consécutives.
Il est clair que le Double Q-Learning converge plus rapidement que le Q-learning.
Notez que lorsque le nombre d'actions en B augmente, Q-learning nécessite beaucoup plus de formation que Double Q-Learning.

Pourquoi ça marche?

Van Hasselt prouve dans son document que E (Q2 (s ’, a *)) ≤ Max Q1 (s’, a *).
Donc, sur un nombre suffisant d’expériences, la valeur attendue de Q2 (s ’, a *) est inférieure ou égale à Max Q1 (s’, a *), ce qui signifie que Q1 (s, a) n’est pas mis à jour avec une valeur maximale.

Le tableau ci-dessous montre l'évolution des valeurs Q de l'action de gauche dans l'état A à mesure que le nombre d'épisodes augmente.
Notez que dans Q-Learning, Q (A, Gauche) est positif car il est affecté par les récompenses positives existant à l'état B. En raison de cette valeur positive, l'algorithme est plus intéressé par l'action gauche afin de maximiser les récompenses. Comme vous pouvez le constater, le pourcentage d’actions de gauche augmente jusqu’au 50ème épisode.
Dans Double Q-Learning, Q1 (A, Gauche) et Q2 (A, Gauche) commencent légèrement en négatif.
En conséquence, le pourcentage d’action gauche commence à diminuer très tôt, permettant ainsi de gagner du temps d’entraînement.

Conclusion

Le document montre que le double Q-learning peut parfois sous-estimer les valeurs d’action, tout en évitant la faille du biais de surestimation que Q-learning fait. Cela montre aussi que ce type de problèmes est double Double-Q-learning atteint beaucoup plus rapidement de bons niveaux de performance.

Code python

Le code Python suivant simule à la fois Double Q-Learning et Q-Learning et génère un tableau et un graphique comparatif pour les deux méthodes.

Articles Liés

Show More

SupportIvy

SupportIvy.com : Un lieu pour partager le savoir et mieux comprendre le monde. Meilleure plate-forme de support gratuit pour vous, Documentation &Tutoriels par les experts.

Related Articles

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Close
Close