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

Même si je sais que SARSA est politique, tout en Q-learning est hors de la politique, quand on regarde leurs formules, il est difficile (pour moi) de voir la différence entre ces deux algorithmes.

Selon le livre L'Apprentissage Par Renforcement: Une Introduction (par Sutton et Barto). Dans l'algorithme SARSA, donné un la politique, l'action correspondante de la valeur de la fonction Q (dans l'état s et action, à timestep t), i.e. Q(st,t), peut être mis à jour comme suit

Q(st,t) = Q(st,t) + α*(rt + γ*Q(st+1,t+1) - Q(st,t))

D'autre part, l'étape de mise à jour pour le Q-learning de l'algorithme est le suivant

Q(st,t) = Q(st,t) + α*(rt + γ*maxa Q(st+1, a) - Q(st, t))

qui peut aussi être écrit comme

Q(st,t) = (1 - α) * Q(st,t) + α * (rt + γ*maxa Q(st+1, a))

où γ (gamma) est le facteur d'actualisation et rt est la récompense reçue de l'environnement à timestep t.

Est la différence entre ces deux algorithmes le fait que SARSA ne regarde que le côté politique de la valeur alors que le Q-learning regarde la prochaine maximum valeur de la stratégie?

TLDR (et ma propre réponse)

Merci à tous ceux qui ont répondu à cette question depuis que j'ai demandé. J'ai fait un dépôt github jouer avec Q-Learning et empiriquement compris quelle est la différence. Tous les montants de la façon dont vous sélectionnez votre prochain meilleur de l'action, qui, à partir d'un point de vue algorithmique peut être un dire, max ou meilleur d'action en fonction de la façon dont vous avez choisi de la mettre en œuvre.

L'autre principale différence est quand de sélection de ce qui se passe (par exemple, en ligne vs hors ligne) et comment/pourquoi qui affecte l'apprentissage. Si vous lisez ceci en 2019 et plus de mains sur la personne, en jouant avec un RL jouet problème est probablement la meilleure façon de comprendre les différences.

Une dernière important noter est que les deux Suton & Barto ainsi que Wikipédia ont souvent mixte, déroutant ou mal de formule représentations en ce qui concerne la état suivant le meilleur/max action et de récompenser:

r(t+1)

est en fait

r(t)

Espère que cela aide quelqu'un jamais être bloqué au ce.

InformationsquelleAutor | 2011-07-27
  1. 42

    Oui, c'est la seule différence. Sur la politique de SARSA apprend les valeurs d'action relatif à la politique qu'elle suit, tandis que la politique de Q-Learning est-il par rapport à la gourmande politique. Sous certaines conditions communes, ils ont tous deux convergent vers la valeur réelle de la fonction, mais à des taux différents. Q-l'Apprentissage tend à converger vers un peu plus lent, mais a la capabilitiy pour continuer l'apprentissage, alors que l'évolution des politiques. Aussi, le Q-Learning n'est pas garantie de convergence lorsqu'il est combiné avec de l'approximation linéaire.

    En termes pratiques, en vertu de l'ε-gourmand politique, Q-Learning calcule la différence entre Q(s,a) et le maximum de la valeur de l'action, tandis que SARSA calcule la différence entre Q(s,a) et de la somme pondérée de la moyenne de la valeur de l'action et la maximale:

    Q-Learning: Q(st+1,t+1) = maxaQ(st+1,a)

    SARSA: Q(st+1,t+1) = ε·moyenneaQ(st+1,a) + (1-ε)·maxaQ(st+1,a)

    • Ok, alors comment ne Sarsa, puis de choisir un Politique ? Je vois que Qlearning la volonté de toujours aller après la politique qui promet de l'action pour vous emmener à la prochaine meilleure Politique. Quels sont les critères pour la sélection de la prochaine Politique Sarsa (en gros ce que je veux savoir, c'est comment évaluer une Politique de Q(S,A) comment choisir la meilleure action ). N'est-il pas le même, c'est à dire le choix de l'État S, l'action, qui sera la plus élevée (max) Q(S,A) ?
    • La politique est la règle pour le choix de la prochaine action. C'est quelque chose que vous avez besoin de choisir le moment de la mise en œuvre de l'algorithme. Le plus simple de la politique est le gourmand — où l'agent choisit toujours la meilleure action. Avec cette politique, SARSA et Q-Learning sont les mêmes. Un meilleur choix pour l'apprentissage de l'ε-gourmand de la politique, où certaines de ces mesures sont choisis au hasard.
    • Ok, c'est pourquoi j'ai posé la question en premier lieu, dans ce cas, ils ont tous les deux sont les mêmes. Merci beaucoup ! Je suis à l'aide d'e-Gourmand. Donc Qlearning ne diffèrent que dans le cas de Hors-la Politique, où les actions sont choisies de façon aléatoire encore la mise à jour avec le Q-learning maximise la Politique de valeurs ?
    • En vertu de l'ε-gourmand de la politique, de la valeur attendue sous SARSA est la somme pondérée de la moyenne de la valeur de l'action et de la meilleure valeur de l'action: Q(s_t+1,a_t+1)=ε·moyenne(Q(s,a))+(1-ε)·max(Q(s,a)). Le manuel donne dans le chapitre 5.4 Sur la Politique de Monte-Carlo de Contrôle.
    InformationsquelleAutor Don Reba
  2. 37

    Quand j'étais à l'apprentissage de la présente partie, je l'ai trouvé très déroutant trop, j'ai donc mis ensemble, les deux pseudo-codes de R. Sutton and A. G. Barto en espérant faire la différence plus clair.

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

    Bleu boîtes de mettre en évidence la partie où les deux algorithmes différents. Les numéros de mettre en évidence la plus détaillée de la différence sera expliqué ultérieurement.

    TL;NR:

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

    où π est une ε-gourmand politique (par exemple, ε > 0 avec l'exploration), et m est un gourmand de la politique (par exemple, ε = 0, PAS d'exploration).

    1. Donné que le Q-learning est l'utilisation des stratégies différentes pour le choix de la prochaine action' et la mise à jour de Q. En d'autres termes, c'est d'essayer d'évaluer π tout en suivant une autre politique μ, c'est donc un hors-la politique de l'algorithme.

    2. En revanche, SARSA utilise π tout le temps, donc c'est une politique de l'algorithme.

    Explication plus détaillée:

    1. La différence la plus importante entre les deux est de savoir comment Q est mise à jour après chaque action. SARSA utilise le Q' à la suite d'une ε-gourmand politique exactement, comme Un " est tirée. En revanche, le Q-learning utilise le maximum d'Q' sur toutes les actions possibles pour la prochaine étape. Ce la fait ressembler à la suite d'une gourmande politique avec ε=0, c'est à dire AUCUN exploration dans cette partie.

    2. Toutefois, lorsque le fait de prendre une action, Q-learning utilise encore les mesures prises à partir d'un ε-gourmand politique. C'est pourquoi "Choisir ...", c'est à l'intérieur de la répéter en boucle.

    3. À la suite de la boucle de logique dans le Q-learning, le " reste de l'ε-gourmand politique.

    • Félicitations pour la beauté des graphismes et photos. Des années après que j'ai posé cette question, je suis venu à réaliser que l'état et l'action de l'itération, la valeur de la stratégie d'itération et de mise à jour, sont deux processus différents. Malheureusement, Sutton et Barto n'est pas très claire à ce sujet. Comment vous décider sur les actions affecte les algorithmes comme vous l'avez expliqué. Max action dans le Q-Learning implique généralement le choix de l'action de la prochaine meilleure Q(s,a) par exemple, gourmand. Dans Sarsa ce n'est pas le cas, soit vous suivez la politique (en ligne) ou vous explorez une nouvelle fonction aléatoire. Votre description est sur place!
    • Ne devrait pas π et μ être échangé dans la phrase "1. <...> En d'autres termes, c'est d'essayer d'évaluer π tout en suivant une autre politique μ" à "essayer d'évaluer μ tout en suivant une autre politique π"?
    • non, c'est l'évaluation de π. μ est le gourmand de la politique, juste pour la sélection d'une action.
    • Mais dans le tableau, vous avez écrit que la mise à jour Q comme si elle était à la suite de μ (évalue μ) alors qu'en fait la suite de ε-gourmand politique π.
    • Peut les hors-la politique de méthode choisir Une " du comportement humain (π) et mise à jour de Q à partir d'un gourmand de la politique (μ)?
    • pas sûr de votre question, π est la politique qui doit être appris ici, si c'est déjà définie (par exemple, quel que soit le comportement de l'homme est), alors qu'est-ce qui doit être appris?
    • Je ne peux pas le faire non plus. Est Q la cible à tirer ici? π et μ sont donnés politiques?
    • selon David Silver diaporama (page31). Un des avantages de l'arrêt de la politique de contrôle est qu'il peut utiliser le comportement de l'homme pour générer l'action suivante (A_t+1).
    • Q-learning est juste l'un des hors-la politique des algorithmes d'apprentissage. Il pourrait y avoir d'autres hors-la politique de l'algorithme, par exemple, impliquant le comportement humain s.
    • oui, dans David Silver de la diapositive, il utilise des notations différentes pour cible la politique et le comportement politique.
    • Un autre point que je veux faire, même si, dans le choix de la prochaine action, à la fois SARSA et Q l'utilisation de l'apprentissage epsilon-gourmand politique, si toutes les valeurs de Q sont les mêmes, ils doivent choisir la même action si ignorant le hasard dans epsilon-gourmand. Cependant, les valeurs de Q deviendra de plus en plus différents, à un certain moment au cours de l'apprentissage, car la mise à jour de l'équation est différente pour SARSA et Q-learning, donc ils pourraient se retrouver dans le choix des actions, même si l'aide de la même epsilon-gourmand de la politique d'amélioration de la stratégie. En un mot, l'itération de la politique seront différents.

    InformationsquelleAutor zyxue
  3. 6

    Quelle est la différence mathématiquement?

    Comme cela est déjà décrit dans la plupart des autres réponses, la différence entre les deux mises à jour mathématiquement est, en effet, que, lors de la mise à jour de la Q-valeur pour un état-action paire (St,t):

    • 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, puis utilise Q(St+1,t+1) (actualisé par gamma) que le rendement futur prévu dans le calcul de la mise à jour de la cible.
    • Q-apprentissage n'utilise pas le comportement politique, de choisir une action supplémentaire t+1. Au lieu de cela, il estime les rendements futurs prévus dans la règle de mise à jour comme maxA Q(St+1, A). Le max opérateur utilisé ici peut être considéré comme "à la suite de" l'complètement avide de la politique. L'agent n'est pas fait à la suite de la gourmande de la politique si; il est dit que, dans la règle de mise à jour, "supposons que je commencerais à la suite de la gourmande de la politique à partir de maintenant, quelles seraient mes attentes de rendement futur alors?".

    Qu'est-ce que cela signifie intuitivement?

    Comme mentionné dans d'autres réponses, la différence est décrit ci-dessus, au moyen d'une terminologie technique, qui Sarsa est un sur la politique algorithme d'apprentissage, et Q-learning est un hors de la politique algorithme d'apprentissage.

    Dans la limite (donnée une quantité infinie de temps pour générer de l'expérience et d'apprendre), et sous certaines hypothèses supplémentaires, cela signifie que Sarsa et Q-learning converger les différentes solutions "optimales" politiques:

    • Sarsa convergeront vers une solution optimale dans l'hypothèse que nous continuons à suivre la même politique qui a été utilisé pour générer l'expérience. Ce sera souvent une politique de certains éléments (au lieu de "stupide") à l'aléatoire, à l'instar de epsilon-gourmand, parce que sinon, nous ne pouvons pas garantir que nous allons converger à quoi que ce soit.
    • Q-Learning convergeront vers une solution optimale dans l'hypothèse que, après la génération de l'expérience et de la formation, nous passer de l'un à l'gourmand politique.

    Lors de l'utilisation de l'algorithme?

    Un algorithme de type Sarsa est généralement préférable dans les situations où nous nous soucions de l'agent pendant le processus de l'apprentissage et de générer de l'expérience. Considérons, par exemple, que l'agent est cher robot qui va briser si elle tombe en bas d'une falaise. Nous préférons ne pas faire tomber trop souvent pendant le processus d'apprentissage, parce que c'est cher. Par conséquent, nous nous soucions de ses performances au cours du processus d'apprentissage. Cependant, nous savons aussi que nous en avons besoin pour agir de façon aléatoire, parfois (par exemple, epsilon-gourmand). Cela signifie qu'il est très dangereux pour le robot de marcher aux côtés de la falaise, car il peut décider d'agir de façon aléatoire (avec une probabilité epsilon) et de tomber. Donc, nous préférerions pour apprendre rapidement qu'il est dangereux d'être proche de la falaise; même si une gourmande politique serait capable de marcher à vos côtés sans tomber, nous savons que nous sommes à la suite d'un epsilon-gourmand politique avec de l'aléatoire, et nous nous soucions de l'optimisation de nos performances étant donné que nous savons que nous allons être stupide parfois. C'est une situation où Sarsa serait préférable.

    Un algorithme de type Q-learning serait préférable, dans des situations où nous ne se soucient pas de l'agent pendant le processus de formation, mais nous voulons juste qu'il pour en savoir optimale gourmand de la politique que nous allons passer à la suite. Considérons, par exemple, que nous avons jouer à quelques jeux (où nous n'avons pas l'esprit de la perdre à cause de l'aléatoire, des fois), et par la suite jouer un tournoi important (où nous allons arrêter d'apprendre, et de passer de l'epsilon-gourmand le gourmand de la politique). C'est là Q-learning serait mieux.

    InformationsquelleAutor Dennis Soemers
  4. 3

    Il y a un indice d'erreur dans votre formule pour le Q-Learning.
    Page 148 de Sutton et Barto est.

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

    La typo est dans l'argument de la max:

    les indices sont st+1 et une,
    alors que dans votre question, elles sont st+1 et+1 (ils sont corrects pour SARSA).

    Espère que cela aide un peu.

    InformationsquelleAutor Alvin
  5. 0

    Dans Le Q-Learning

    C'est votre:
    Q-Learning: Q(St,At) = Q(St,At) + a [ R(t+1) + rabais * max Q(St+1,À) - Q(St,At) ]

    doit être modifié pour
    Q-Learning: Q(St,At) = Q(St,At) + a [ R(t+1) + rabais * max Q(St+1,un) - Q(St,At) ]

    Comme vous l'avez dit, vous devez trouver le maximum de valeur Q pour la mise à jour de l'eq. en changeant la un, Alors vous aurez un nouveau Q(St,At). SOIGNEUSEMENT, les un que vous donner le maximum de Q-valeur n'est pas la prochaine action. À ce stade, vous ne connaissez que le prochain état (St+1), et avant de passer à la prochaine ronde, vous souhaitez mettre à jour la St 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

    • Mise à jour Q-valeur à l'aide de l'eq.

    • St <-- St+1

    Jusqu'à St est la borne

    • En fait, ils ont confondu le public; il n'est pas R[t+1] il est R[t], mais ils ne sont en effet montrer que R[t+1] à un moment donné dans le livre. Cependant (et ne prenez pas mon mot pour lui, essayez-le vous-même) si vous définissez R[t+1] la récompense valeurs ne sont pas à l'échelle entre 0 et 1, et même pire, vous vous exécutez dans l'algorithme d'itérations de problèmes, puisque Q[t] = R[t] lorsque l'état est la borne, qui ne sera jamais vrai si l'utilisation de R[t+1]. Wikipédia s'il avait mal (j'ai édité) et Sutton et Barto utiliser les deux variantes dans le livre sans vraiment expliquer pourquoi.
    InformationsquelleAutor comx