Pourquoi le Q-learning régulier (et DQN) surestime-t-il les valeurs Q?
La motivation pour l'introduction du double DQN (et du double Q-learning) est que le Q-learning régulier (ou DQN) peut surestimer la valeur Q, mais y a-t-il une brève explication de la raison pour laquelle il est surestimé?
Réponses
La surestimation provient de l'initialisation aléatoire de vos estimations de valeur Q. Évidemment, ceux-ci ne seront pas parfaits (s'ils l'étaient, nous n'aurions pas besoin d'apprendre les vraies valeurs Q!). Dans de nombreuses méthodes d'apprentissage par renforcement basées sur des valeurs telles que SARSA ou Q-learning, les algorithmes impliquent un$\max$opérateur dans la construction de la politique cible. Le cas le plus évident est, comme vous l'avez mentionné, le Q-learning. La mise à jour d'apprentissage est$$Q(s, a) = Q(s, a) + \alpha \left[r(s, a) + \gamma \max_a Q(s', a) - Q(s, a) \right] \;.$$La fonction Q pour le tuple état-action que nous considérons est décalée vers la fonction Q max à l'état suivant où le$\max$ est prise par rapport aux actions.
Maintenant, comme mentionné, nos estimations initiales des valeurs Q sont initialisées au hasard. Cela conduit naturellement à des valeurs incorrectes. La conséquence en est que lorsque nous calculons$\max_aQ(s', a)$nous pourrions choisir des valeurs largement surestimées .
Comme le Q-learning (dans le cas tabulaire) est assuré de converger (sous certaines hypothèses modérées), la principale conséquence du biais de surestimation est qu'il ralentit considérablement la convergence. Ceci peut bien sûr être surmonté avec le Double Q-learning.
La réponse ci-dessus concerne le cas tabulaire Q-Learning. L'idée est la même pour le Deep Q-Learning, sauf que le Deep Q-learning n'a aucune garantie de convergence (lors de l'utilisation d'un NN comme approximateur de fonction) et donc le biais de surestimation est plus un problème car il peut signifier les paramètres du réseau reste bloqué dans des valeurs sous-optimales.
Comme quelqu'un a demandé dans les commentaires de toujours initialiser les valeurs comme étant des nombres très faibles, cela ne fonctionnerait pas vraiment.
Considérez le MDP suivant tiré de Sutton et Barto: Nous commençons dans l'état A, à partir duquel nous pouvons soit aller à droite avec la récompense 0 menant à un état terminal, soit aller à gauche avec la récompense 0 à l'état B.De l'état B, nous pouvons prendre, disons, 100 actions différentes, toutes conduisant à un état terminal et ayant une récompense tirée d'une distribution normale avec une moyenne de -0,1 et une variance de 1.
Maintenant, il est clair que l'action optimale de l'état A est d'aller à droite. Cependant, lorsque nous allons à gauche et entreprenons une action dans l'état B, il y a une probabilité (presque) de 0,5 d'obtenir une récompense supérieure à 0. Maintenant, rappelez-vous que la valeur Q est décalée vers$r(s, a) + \max_a Q(s', a)$; en raison des récompenses stochastiques lors de la transition hors de l'état B et du fait que nous verrons probablement une récompense positive$\max_a Q(s', a)$ sera positif.
Cela signifie que lorsque nous prenons l'action à gauche, la valeur Q (Q (A, gauche)) est décalée vers une valeur positive, ce qui signifie que lorsque nous sommes dans l'état A, la valeur du déplacement vers la gauche sera plus élevée que celle du déplacement vers la droite (ce qui être progressivement décalé vers la vraie valeur de 0) et ainsi en suivant le $\epsilon$- politique gourmande l'action gourmande sera d'aller à gauche alors qu'en fait c'est sous-optimal.
Maintenant, bien sûr, nous savons que les vraies valeurs Q finiront par converger, mais si nous avons, disons, 100 actions, vous pouvez probablement voir que le temps qu'il faudra pour que les valeurs Q convergent vers la vraie valeur sera potentiellement être long car il faudrait continuer à choisir toutes les valeurs surestimées jusqu'à ce que nous ayons une convergence.