Pourquoi Q-learning ne converge-t-il pas lors de l'utilisation de l'approximation de fonction?

12

L'algorithme tabulaire d'apprentissage Q est garanti pour trouver la fonction Q optimale , Q , à condition que les conditions suivantes (les conditions Robbins-Monro ) concernant le taux d'apprentissage soient remplies

  1. tαt(s,a)=
  2. tαt2(s,a)<

αt(s,a) signifie le taux d'apprentissage utilisé lors de la mise à jour de la valeur Q associée à l'état s et à l'action a au pas de temps t , où 0αt(s,a)<1 est supposé être vrai, pour tous les Etats s et des actions a .

Apparemment, étant donné que 0αt(s,a)<1 , pour que les deux conditions soient vraies, toutes les paires état-action doivent être visitées à l'infini souvent: cela est également indiqué dans le livre Reinforcement Learning: An Introduction , outre le fait que cela devrait être largement connu et que c'est la raison d'être de l'utilisation de la politique ϵ -regedy (ou des politiques similaires) pendant la formation.

Une preuve complète qui montre que Q -learning trouve le Q optimalQ fonction peut être trouvée dans l'article Convergence of Q-learning: A Simple Proof (par Francisco S. Melo). Il utilise des concepts comme la cartographie de contraction afin de définir la fonction Q optimale (voir aussi Qu'est-ce que l'opérateur Bellman dans l'apprentissage par renforcement? ), Qui est un point fixe de cet opérateur de contraction. Il utilise également un théorème (n. 2) concernant le processus aléatoire qui converge vers 0 , compte tenu de quelques hypothèses. (La preuve peut ne pas être facile à suivre si vous n'êtes pas un mathématicien.)

Si un réseau de neurones est utilisé pour représenter Qfonction Q , les garanties de convergence de l'apprentissageQ elles toujours valables? Pourquoi (ou non) Q-learning converge-t-il lors de l'utilisation de l'approximation de fonction? Existe-t-il une preuve formelle d'une telle non-convergence de l'apprentissageQ utilisant l'approximation de fonction?

Je recherche différents types de réponses, de celles qui donnent juste l'intuition derrière la non-convergence du Q learning lors de l'utilisation de l'approximation de fonction à celles qui fournissent une preuve formelle (ou un lien vers un article avec une preuve formelle).

nbro
la source
2
Grande question!
John Doucette
Le livre auquel vous avez fait référence parle de ce problème dans le chapitre 11 afin que vous puissiez le lire. De plus, je ne pense pas qu'il existe une preuve formelle de la raison pour laquelle cela se produit, mais il y a peu d'exemples qui montrent des divergences même dans des environnements simples (par exemple Tsitsiklis et van Roy).
Brale_

Réponses:

8

Voici une réponse de description intuitive:

L'approximation des fonctions peut être effectuée avec n'importe quelle fonction paramétrable. Considérons le problème d'un espace Q(s,a)s est les réels positifs, a est 0 ou 1 , et la vraie fonction Q(s,0)=s2 est Q ( s , 0 ) = s 2 , et Q(s,1)=2s2 , pour tous les États. Si votre approximateur de fonction est Q(s,a)=ms+na+b , il n'existe aucun paramètre pouvant représenter avec précision la vraiefonctionQ (nous essayons d'adapter une ligne à une fonction quadratique). Par conséquent, même si vous choisissez un bon taux d'apprentissage et que vous visitez tous les états indéfiniment, votre fonction d'approximation ne convergera jamais vers la vraiefonctionQ

Et voici un peu plus de détails:

  1. Les réseaux de neurones se rapprochent des fonctions. Une fonction peut être approchée à des degrés plus ou moins élevés en utilisant des polynômes plus ou moins complexes pour l'approcher. Si vous connaissez l'approximation de la série Taylor, cette idée devrait sembler assez naturelle. Sinon, pensez à une fonction comme une onde sinusoïdale sur l'intervalle [0- π/2 ). Vous pouvez l'approcher (mal) avec une ligne droite. Vous pouvez mieux l'approcher avec une courbe quadratique. En augmentant le degré du polynôme que nous utilisons pour approximer la courbe, nous pouvons obtenir quelque chose qui s'adapte de plus en plus à la courbe.
  2. Les réseaux de neurones sont des approximateurs de fonctions universelles . Cela signifie que, si vous avez une fonction, vous pouvez également créer un réseau de neurones suffisamment profond ou large pour pouvoir approximer la fonction que vous avez créée à un degré arbitrairement précis. Cependant, toute topologie de réseau spécifique que vous choisirez ne pourra pas tout savoir fonctions, sauf si elle est infiniment large ou infiniment profonde. Ceci est analogue à la façon dont, si vous choisissez les bons paramètres, une ligne peut s'adapter à deux points, mais pas à 3 points. Si vous choisissez un réseau d'une certaine largeur ou profondeur finie, je peux toujours construire une fonction qui a besoin de quelques neurones de plus pour s'adapter correctement.

  3. Les limites de Q-learning ne tiennent que lorsque la représentation de la fonction Q est exacte . Pour voir pourquoi, supposons que vous ayez choisi d'approximer votre fonction Q avec une interpolation linéaire. Si la vraie fonction peut prendre n'importe quelle forme, alors clairement l'erreur dans notre interpolation peut être rendue illimitée simplement en construisant une fonction de fonction Q de type XOR, et aucune quantité de temps ou de données supplémentaires ne nous permettra de réduire cette erreur . Si vous utilisez un approximateur de fonction et que la vraie fonction que vous essayez d'ajuster n'est pasquelque chose que la fonction peut approximativement bien arbitrairement, alors votre modèle ne convergera pas correctement, même avec un taux d'apprentissage et un taux d'exploration bien choisis. En utilisant la terminologie de la théorie de l'apprentissage informatique, nous pourrions dire que les preuves de convergence pour l'apprentissage Q ont implicitement supposé que la vraie fonction Q est un membre de l'espace d'hypothèses à partir duquel vous choisirez votre modèle.

John Doucette
la source
Où pouvons-nous voir dans la preuve que j'ai mentionnée que "les limites de l'apprentissage Q ne tiennent que lorsque la représentation de la fonction Q est exacte" est-il vrai?
nbro
Donc, nous pouvons approximer n'importe quelle fonction (raisonnable) en utilisant un réseau de neurones (architecture), mais, étant donné une architecture de réseau de neurones fixe (que nous devons choisir au début de la phase d'apprentissage du Q- learning), Q -learning pourrait ne pas converger en utilisant cette architecture spécifique Z , car Z pourrait ne pas être suffisamment expressif pour représenter Q . ZQQZZQ
nbro
@nbro La preuve ne le dit pas explicitement, mais elle suppose une représentation exacte de la fonction Q (c'est-à-dire que les valeurs exactes sont calculées et stockées pour chaque paire état / action). Pour les espaces d'états infinis, il est clair que cette représentation exacte peut être infiniment grande dans le pire des cas (exemple simple: soit Q (s, a) = sth chiffre de pi). Votre deuxième commentaire le résume bien. Plus formellement, si la véritable hypothèse Q * n'est pas un élément de l'espace d'hypothèse H à partir duquel vous sélectionnez un modèle, vous ne pouvez pas converger vers Q *, même avec un temps ou des données infinis.
John Doucette
4

Pour autant que je sache, il est encore un peu difficile de comprendre vraiment clairement et formellement pourquoi / quand nous obtenons un manque de convergence - ou, pire, parfois un danger de divergence. Il est généralement attribué à la "triade mortelle" (voir 11.3 de la deuxième édition du livre de Sutton et Barto), la combinaison de:

  1. Approximation de fonction, ET
  2. Bootstrapping (en utilisant nos propres estimations de valeur dans le calcul de nos objectifs de formation, comme le fait Q -learning), ET
  3. Formation hors politique ( Q -learning est en effet hors politique).

Cela ne nous donne qu'une description (éventuellement non exhaustive) des cas dans lesquels nous avons un manque de convergence et / ou un danger de divergence, mais ne nous dit toujours pas pourquoi cela se produit dans ces cas.


Q

Personnellement, je pense que cette intuition aide à comprendre pourquoi l'algorithme ne peut pas garantir la convergence vers la solution optimale, mais je m'attendrais toujours intuitivement à ce qu'il soit peut-être capable de "converger" vers une solution "stable" qui est la meilleure approximation possible donnée les restrictions inhérentes à la représentation de la fonction choisie. En effet, c'est ce que nous observons dans la pratique lorsque nous passons à la formation sur les politiques (par exemple Sarsa), au moins dans le cas des approximateurs de fonctions linéaires.


Q(s,a)(s,a)Q dans l'attente, ils se mettent généralement à jour vers la «direction» correcte. Intuitivement, cela signifie que, dans le cadre tabulaire, dans l'attente, nous corrigerons lentement, progressivement toutes les erreurs dans les entrées isolément, sans nuire éventuellement aux autres entrées.

Q(s,a)(s,a)Q


maxmax

Q(s,a)

Q(s,a)Q(s,a)+α[maxaQ(s,a)Q(s,a)].

maxaQ(s,a)QQ(s,a)maxaQ(s,a)


Enfin, un autre article (encore plus récent) que je soupçonne pertinent pour cette question est le diagnostic des goulots d'étranglement dans les algorithmes d'apprentissage en profondeur , mais malheureusement je n'ai pas encore eu le temps de le lire suffisamment en détail et de le résumer adéquatement.

Dennis Soemers
la source
1
Mais l'utilisation d'un réseau de neurones n'est-elle pas également due à l'hypothèse que certains états sont très similaires à chacun? Des états très similaires (par exemple, des images successives dans un jeu) ont souvent des actions optimales très similaires (ou identiques), donc je ne suis pas sûr que l'explication du premier article soit valide (je devrais la lire pour bien comprendre leurs principaux points).
nbro
1
@nbro Oui, souvent la généralisation est considérée comme un avantage plutôt qu'un problème précisément pour cette raison. Si cela fonctionne comme «prévu», il peut être très puissant et accélérer l'apprentissage parce que nous transférons tout ce que nous apprenons à des états / actions similaires, plutôt que d'apprendre pour chaque état / action légèrement différent de manière isolée. Mais cela peut aussi conduire à des problèmes, notamment en théorie mais aussi en pratique. C'est comme une "épée à double tranchant" je suppose.
Dennis Soemers
1
@DennisSoemers Réponse super intéressante. Le point d'apprentissage Q non délirant a une tonne de sens. Trouver la bonne fonction Q signifie trouver un point fixe pour votre règle de mise à jour, mais il semble que l'approximation des fonctions puisse conduire à des mises à jour cycliques dans Q-learning si vous y pensez de cette façon.
John Doucette