Quelle est la différence entre Q-learning et SARSA?

quand j'ai appris cette partie, je l'ai trouvée très confuse aussi, donc j'ai rassemblé les deux pseudo-codes de R. Sutton et A. G. Barto espérant faire la différence plus claire.

les boîtes bleues mettent en évidence la partie où les deux algorithmes diffèrent réellement. Les chiffres mettent en évidence la différence plus détaillée qui sera expliquée plus tard.

TL;NR:

|             | SARSA | Q-learning |
|:-----------:|:-----:|:----------:|
| Choosing A' |   π   |      π     |
| Updating Q  |   π   |      μ     |

Où π est une politique de type ε-greedy (par exemple ε > 0 avec exploration), et μ est une politique cupide (par exemple ε == 0, pas d'exploration).

1. étant donné que Q-learning utilise différentes politiques pour choisir la prochaine action A' et mettre à jour Q. en d'autres termes, il essaie d'évaluer π tout en suivant une autre politique μ, donc c'est un algorithme Hors-Politique.

2. en revanche, SARSA utilise π Tout le temps, donc c'est un algorithme de politique.

plus détaillé explication:

1. la différence la plus importante entre les deux est la façon dont Q est mis à jour après chaque action. SARSA utilise le Q' en suivant exactement une politique avide d'argent, comme un' en est tiré. En revanche, Q-learning utilise le Q ' maximum sur toutes les actions possibles pour l'étape suivante. Cela donne l'impression de suivre une politique cupide Avec ε=0, c'est-à-dire QU'il n'y a pas d'exploration dans cette partie.

2. Cependant, en prenant réellement une action, Q-learning encore utilise l'action d'une politique avide d'argent. C'est pourquoi "Choisir Un ..."est à l'intérieur de la répéter en boucle.

3. suivant la logique de boucle de Q-learning, A ' est toujours issu de la Politique d'avarice.

il y a une erreur d'index dans votre formule pour Q-Learning. Page 148 de Sutton et Barto.

Q (st,at) <-- Q (st,at) + alpha * [r (t+1) + gamma * max Q (st+1, a) - Q (st, at)]

La typo est dans l'argument de la max:

J'espère que cela vous aidera un peu.

Quelle est la différence mathématiquement?

• Sarsa utilise le comportement politique (sens, la politique utilisé par l'agent pour générer de l'expérience dans l'environnement, qui est généralement epsilon-gourmand) pour sélectionner une action supplémentaire _t+1 et Q (S _t+1, Un _t+1) (actualisé par gamma) comme prévu retours futurs dans le calcul de la cible de mise à jour.
• Q-l'apprentissage n'utilise pas le comportement politique, de choisir une action supplémentaire _t+1. Au lieu de cela, il estime les rendements futurs attendus dans la règle de mise à jour max Q (S _t+1, A). max opérateur utilisé ici peut être considéré comme "suivant" la Politique complètement avide. L'agent n'est pas fait à la suite de la gourmande de la politique si; il dit seulement, dans la règle de mise à jour, "supposons que je commence à suivre la Politique cupide à partir de maintenant, quels seraient mes retours futurs attendus alors?".

Qu'est-ce que cela signifie intuitivement?

Comme mentionnée dans d'autres réponses, la différence décrite ci-dessus signifie, en utilisant la terminologie technique, que Sarsa est un politique apprentissage de l'algorithme, et Q-learning est un politique algorithme d'apprentissage.

dans la limite (compte tenu d'une quantité infinie de temps pour générer de l'expérience et apprendre), et sous quelques hypothèses supplémentaires, cela signifie que Sarsa et Q-learning convergent vers des solutions différentes / " optimal" les politiques:

• Sarsa convergent une solution optimale en partant du principe que nous suivons toujours la même politique qui a été utilisée pour générer l'expérience. Il s'agit souvent d'une politique comportant un élément d'aléatoire (plutôt "stupide"), comme epsilon - gourmands, parce que sinon nous ne pouvons pas garantir que nous convergerons vers quoi que ce soit.
• Q-Learning convergent une solution optimale dans l'hypothèse où, après avoir généré de l'expérience et de la formation, on passe à la Politique avide.

quand utiliser quel algorithme?

un algorithme comme Sarsa est généralement préférable dans les situations où nous nous soucions de la performance de l'agent au cours du processus d'apprentissage / génération d'expérience. Considérons, par exemple, que l'agent est cher un robot qui se cassera s'il tombe d'une falaise. Nous préférerions qu'elle ne tombe pas trop souvent pendant le processus d'apprentissage, car elle est coûteuse. Par conséquent, nous nous soucions de sa performance pendant le processus d'apprentissage. Cependant, nous savons aussi que nous en avons besoin pour agir de façon aléatoire parfois (par exemple epsilon-greedy). Cela signifie qu'il est très dangereux pour le robot de marcher le long de la falaise, car il peut décider d'agir au hasard (avec Probabilité epsilon) et tomber. Donc, nous préférerions à apprenez rapidement qu'il est dangereux d'être près de la falaise; même si une politique cupide pouvait marcher à ses côtés sans tomber, nous savons que nous suivons une politique epsilon-greedy au hasard, et nous nous soucions d'optimiser notre performance étant donné que nous savons que nous serons stupides parfois. C'est une situation où Sarsa serait préférable.

un algorithme comme Q-learning serait préférable dans les situations où nous ne se soucier de la performance de l'agent pendant le processus de formation, mais nous voulons juste qu'il apprendre une politique avide optimale que nous allons passer à éventuellement. Considérons, par exemple, que nous jouons quelques matchs d'entraînement (où nous ne nous soucions pas de perdre en raison de l'aléatoire parfois), et ensuite jouer un tournoi important (où nous arrêterons d'apprendre et de passer d'epsilon-avide à la Politique avide). C'est là que Q-learning serait mieux.

En Q-Learning

Ceci est votre: Q-Learning: Q (St, At) = Q(St,At) + a [ R(t+1) + discount * max Q (St+1,) - Q (St, At)]

devrait être changée en Q-Learning: Q (St, At) = Q(St,At) + a [ R(t+1) + discount * max Q (St+1,) - Q (St, At)]

comme vous l'avez dit, vous devez trouver la valeur Q maximale pour la mise à jour eq. en changeant l' , alors vous aurez un nouveau Q (St,At). SOIGNEUSEMENT, le qui vous donnent la valeur Q maximale n'est pas la prochaine action. À ce stade, vous ne connaissez que L'état suivant (St+1), et avant d'aller au tour suivant, vous voulez mettre à jour le St par le St+1 (St <-- St+1).

Pour chaque boucle;

• choisir À partir de la St à l'aide de la Q-valeur

• prendre et À respecter la Rt+1 et St+1

• mettre à Jour la Q-valeur à l'aide de l'eq.

• St <-- St+1

Jusqu'à St est la borne