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

Question

Même si je sais que SARSA est conforme à la politique, tandis que Apprentissage par questions-réponses (Q-learning) est hors politique, il est difficile (pour moi) de voir une différence entre ces deux algorithmes lorsque l'on examine leurs formules.

Selon le livre Apprentissage par renforcement : Une introduction (par Sutton et Barto). Dans l'algorithme SARSA, étant donné une politique, la fonction action-valeur Q correspondante (dans l'état s et l'action a, au pas de temps t), c'est-à-dire Q(s _t , a _t ), peut être mis à jour comme suit

Q(s _t , a _t ) = Q(s _t , a _t ) + *(r _t + *Q(s) _t+1 , a _t+1 ) - Q(s _t , a _t ))

En revanche, l'étape de mise à jour de l'algorithme d'apprentissage Q est la suivante

Q(s _t , a _t ) = Q(s _t , a _t ) + *(r _t + *max _a Q(s _t+1 , a) - Q(s _t , a _t ))

qui peut également s'écrire

Q(s _t , a _t ) = (1 - ) * Q(s _t , a _t ) + * (r _t + *max _a Q(s _t+1 , a))

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

La différence entre ces deux algorithmes réside-t-elle dans le fait que SARSA ne recherche que la valeur de la politique suivante alors que Q-learning recherche la valeur de la politique suivante ? maximum valeur de la police ?

TLDR (et ma propre réponse)

Merci à tous ceux qui ont répondu à cette question depuis que je l'ai posée. J'ai fait une repo github jouer avec le Q-Learning et comprendre empiriquement quelle est la différence. Tout se résume à la façon dont vous choisissez la meilleure action suivante qui, d'un point de vue algorithmique, peut être un moyen , max o meilleur selon la manière dont vous avez choisi de la mettre en œuvre.

L'autre différence principale est la suivante quand cette sélection se produit (par ex, en ligne vs hors ligne ) et comment et pourquoi cela affecte l'apprentissage. Si vous lisez ces lignes en 2019 et que vous êtes plutôt du genre à mettre la main à la pâte, le meilleur moyen de comprendre les différences est probablement de jouer avec un problème de jouet RL.

Une dernière important Il est à noter que Suton & Barto, ainsi que Wikipedia, ont souvent des mixte, confus o erroné des représentations de formules en ce qui concerne les état suivant action et récompense optimales/maximales :

r(t+1)

est en fait

r(t)

Answer 1

Lorsque j'ai appris cette partie, je l'ai trouvée très confuse aussi, alors j'ai rassemblé les deux pseudo-codes de R.Sutton et A.G.Barto dans l'espoir de rendre la différence plus claire.

Les cases bleues mettent en évidence la partie où les deux algorithmes diffèrent réellement. Les chiffres mettent en évidence les différences plus détaillées qui seront expliquées ultérieurement.

TL;NR :

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

où π est une politique ε-greedy (par exemple ε > 0 avec exploration), et μ est une politique greedy (par exemple ε == 0, PAS d'exploration).

1. Étant donné que l'apprentissage Q utilise différentes politiques pour choisir l'action suivante A' et mettre à jour Q. En d'autres termes, il tente d'évaluer π tout en suivant une autre politique μ, il s'agit donc d'un algorithme hors politique.

2. En revanche, SARSA utilise π en permanence, ce qui en fait un algorithme "on-policy".

Explication plus détaillée :

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 exactement le Q' d'une politique ε-greedy, puisque A' en est tiré. En revanche, l'apprentissage Q utilise le maximum de Q' sur toutes les actions possibles pour l'étape suivante. Cela donne l'impression de suivre une politique avide avec ε=0, c'est-à-dire qu'il n'y a PAS d'exploration dans cette partie.

2. Toutefois, lorsqu'une action est réellement entreprise, l'apprentissage Q utilise toujours l'action prise dans le cadre d'une politique ε-greedy. C'est pourquoi "Choose A ..." se trouve à l'intérieur de la boucle de répétition.

3. En suivant la logique de boucle de l'apprentissage Q, A' est toujours issu de la politique ε-greedy.

Answer 2

Oui, c'est la seule différence. SARSA apprend les valeurs des actions par rapport à la politique qu'il suit, tandis que Q-Learning le fait par rapport à la politique gourmande. Dans certaines conditions communes, ils convergent tous deux vers la fonction de valeur réelle, mais à des rythmes différents. Le Q-Learning tend à converger un peu plus lentement, mais il a la capacité de continuer à apprendre tout en changeant de politique. En outre, la convergence du Q-Learning n'est pas garantie lorsqu'il est combiné à une approximation linéaire.

En pratique, dans le cadre de la politique ε-greedy, Q-Learning calcule la différence entre Q(s,a) et la valeur d'action maximale, tandis que SARSA calcule la différence entre Q(s,a) et la somme pondérée de la valeur d'action moyenne et de la valeur maximale :

Q-Learning : Q(s _t+1 ,a _t+1 ) = max _a Q(s _t+1 ,a)

SARSA : Q(s _t+1 ,a _t+1 ) = ε-moyenne _a Q(s _t+1 a) + (1-ε)-max _a Q(s _t+1 ,a)

Answer 3

Quelle est la différence mathématique ?

Comme cela a déjà été décrit dans la plupart des autres réponses, la différence entre les deux mises à jour, d'un point de vue mathématique, réside dans le fait que, lors de la mise à jour du Q -valeur pour une paire état-action (S _t , A _t ) :

• Sarsa utilise la politique de comportement (c'est-à-dire la politique utilisée par l'agent pour générer de l'expérience dans l'environnement, qui est typiquement epsilon -greedy) pour sélectionner une action supplémentaire A _t+1 et utilise ensuite Q(S _t+1 , A _t+1 ) (actualisé par gamma ) comme rendements futurs escomptés dans le calcul de l'objectif de mise à jour.
• Q -l'apprentissage n'utilise pas la politique de comportement pour sélectionner une action supplémentaire A _t+1 . Au lieu de cela, il estime les rendements futurs attendus dans la règle de mise à jour comme suit max _A Q(S _t+1 , A) . Les max utilisé ici peut être considéré comme "suivant" la politique complètement gourmande. Cependant, l'agent ne suit pas réellement la politique d'appât du gain ; elle dit seulement, dans la règle de mise à jour, "supposons que je commence à suivre la politique gourmande à partir de maintenant, quels seraient alors mes rendements futurs attendus".

---

Qu'est-ce que cela signifie intuitivement ?

Comme indiqué dans d'autres réponses, la différence décrite ci-dessus signifie, selon la terminologie technique, que Sarsa est une sur la politique algorithme d'apprentissage, et l'apprentissage Q est un algorithme d'apprentissage. hors politique algorithme d'apprentissage.

Dans la limite (avec un temps infini pour générer de l'expérience et apprendre), et sous certaines hypothèses supplémentaires, Cela signifie que Sarsa et Q-learning convergent vers différentes solutions / politiques "optimales". :

• Sarsa convergera vers une solution optimale dans l'hypothèse où nous continuons à suivre la même politique que celle qui a été utilisée pour générer l'expérience . Il s'agira souvent d'une politique comportant une part de hasard (plutôt "stupide"), comme par exemple epsilon -car sinon, nous ne pouvons pas garantir que nous convergerons vers quoi que ce soit.
• Q-Learning convergera vers une solution optimale dans l'hypothèse où, après avoir acquis de l'expérience et de la formation, nous passons à la politique gourmande. .

---

Quand utiliser quel algorithme ?

Un algorithme comme Sarsa est généralement préférable dans les situations où nous nous intéressons à la performance de l'agent pendant le processus d'apprentissage / de génération d'expérience . Considérons, par exemple, que l'agent est un robot coûteux qui se brisera s'il tombe d'une falaise. Nous préférons qu'il ne tombe pas trop souvent au cours du processus d'apprentissage, car il est coûteux. Par conséquent, nous nous soucions de ses performances au cours du processus d'apprentissage. Cependant, nous savons également que nous avons besoin qu'il agisse parfois de manière aléatoire (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 une probabilité epsilon) et tomber. Nous préférons donc qu'il apprenne rapidement qu'il est dangereux de se trouver à proximité de la falaise ; même si une politique gourmande serait capable de marcher à ses côtés sans tomber, nous savons que nous suivons une politique gourmande epsilon avec un caractère aléatoire, et nous nous soucions d'optimiser nos performances étant donné que nous savons que nous serons parfois stupides . Il s'agit d'une situation où le Sarsa serait préférable.

Un algorithme comme Apprentissage par questions-réponses (Q-learning) serait préférable dans les situations où nous ne nous soucions pas de la performance de l'agent pendant le processus d'apprentissage, mais où nous voulons simplement qu'il apprenne une politique optimale et avide que nous adopterons par la suite. Considérons, par exemple, que nous jouons quelques parties d'entraînement (au cours desquelles nous ne craignons pas de perdre parfois en raison du hasard), puis que nous participons à un tournoi important (au cours duquel nous cesserons d'apprendre et passerons de la politique epsilon-greedy à la politique greedy). C'est dans ce cas que l'apprentissage Q serait plus efficace.

Answer 4

Il y a une erreur d'index dans votre formule pour le 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 coquille se trouve dans l'argument du maximum :

les index sont st+1 et a, alors que dans votre question, il s'agit de st+1 et at+1 (ce qui est correct pour SARSA).

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

Answer 5

Dans Q-Learning

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

doit être remplacé par Q-Learning : Q(St,At) = Q(St,At) + a [ R(t+1) + remise * max Q(St+1, a ) - Q(St,At) ]

Comme vous l'avez dit, vous devez trouver la valeur maximale de Q pour l'équation de mise à jour en modifiant le paramètre a Vous aurez alors un nouveau Q(St,At). ATTENTION, les a 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 de passer au tour suivant, vous voulez mettre à jour le St par le St+1 (St <-- St+1).

Pour chaque boucle ;

• choisir At parmi les St à l'aide de la valeur Q

• prendre At et observer Rt+1 et St+1

• Mettre à jour la valeur Q à l'aide de l'équation.

• St <-- St+1

Jusqu'à ce que St soit en phase terminale