Was ist der Unterschied zwischen Q-Learning und SARSA?

Obwohl ich weiß, dass SARSA nicht den Richtlinien entspricht, während Q-Learning nicht den Richtlinien entspricht, ist es (für mich) schwierig, bei der Betrachtung ihrer Formeln einen Unterschied zwischen diesen beiden Algorithmen festzustellen.

Nach dem Buch Reinforcement Learning: An Introduction (von Sutton und Barto). In dem SARSA-Algorithmus kann bei gegebener Richtlinie die entsprechende Aktionswertfunktion Q (im Zustand s und Aktion a zum Zeitpunkt t), dh Q (s _t , a _t ), wie folgt aktualisiert werden

Q (s _t , a _t ) = Q (s _t , a _t ) + α * (r _t + γ * Q (s _{t + 1} , a _{t + 1} ) - Q (s _t , a _t ))

Andererseits ist der Aktualisierungsschritt für den Q-Learning-Algorithmus der folgende

Q (s _t , a _t ) = Q (s _t , a _t ) + α * (r _t + γ * max _a Q (s _{t + 1} , a) - Q (s _t , a _t ))

was auch geschrieben werden kann als

Q (s _t , a _t ) = (1 - α) * Q (s _t , a _t ) + α * (r _t + γ * max _a Q (s _{t + 1} , a))

Dabei ist γ (Gamma) der Abzinsungsfaktor und r _t die Belohnung, die zum Zeitpunkt t von der Umgebung erhalten wird.

Ist der Unterschied zwischen diesen beiden Algorithmen die Tatsache, dass SARSA nur den nächsten Richtlinienwert nachschlägt, während Q-Learning den nächsten maximalen Richtlinienwert nachschlägt ?

TLDR (und meine eigene Antwort)

Vielen Dank an alle, die diese Frage beantwortet haben, seit ich sie zum ersten Mal gestellt habe. Ich habe ein Github-Repo mit Q-Learning gemacht und empirisch verstanden, was der Unterschied ist. Alles hängt davon ab, wie Sie Ihre nächstbeste Aktion auswählen. Unter algorithmischen Gesichtspunkten kann dies eine mittlere , maximale oder beste Aktion sein, je nachdem, wie Sie sie implementiert haben.

Der andere Hauptunterschied ist , wenn diese Auswahl geschieht (zB Online - vs offline ) und wie / warum das Lernen auswirkt. Wenn Sie dies im Jahr 2019 lesen und eher eine praktische Person sind, ist das Spielen mit einem RL-Spielzeugproblem wahrscheinlich der beste Weg, um die Unterschiede zu verstehen.

Ein letzter wichtiger Hinweis ist, dass sowohl Suton & Barto als auch Wikipedia häufig gemischte, verwirrende oder falsche formelhafte Darstellungen in Bezug auf die beste / maximale Aktion und Belohnung des nächsten Staates haben :

r (t + 1)

ist in der Tat

r (t)

Hoffe, das hilft jedem, der jemals daran hängen bleibt.

Ja, das ist der einzige Unterschied. On-Policy-SARSA lernt Aktionswerte in Bezug auf die Richtlinie, der es folgt, während Off-Policy-Q-Learning dies in Bezug auf die gierige Richtlinie tut. Unter bestimmten Bedingungen konvergieren beide zur Realwertfunktion, jedoch mit unterschiedlichen Raten. Q-Learning konvergiert tendenziell etwas langsamer, kann jedoch weiter lernen, während Richtlinien geändert werden. Es ist auch nicht garantiert, dass Q-Learning in Kombination mit linearer Approximation konvergiert.

In der Praxis berechnet Q-Learning gemäß der ε-gierigen Richtlinie die Differenz zwischen Q (s, a) und dem maximalen Aktionswert, während SARSA die Differenz zwischen Q (s, a) und der gewichteten Summe der durchschnittlichen Aktion berechnet Wert und das Maximum:

Q-Learning: Q (s _{t + 1} , a _{t + 1} ) = max _a Q (s _{t + 1} , a)

SARSA: Q (s _{t + 1} , a _{t + 1} ) = ε · bedeutet _a Q (s _{t + 1} , a) + (1 - ε) · max _a Q (s _{t + 1} , a)

Als ich diesen Teil lernte, fand ich ihn auch sehr verwirrend, also habe ich die beiden Pseudocodes von R. Sutton und AGBarto zusammengestellt, um den Unterschied klarer zu machen.

Blaue Kästchen markieren den Teil, in dem sich die beiden Algorithmen tatsächlich unterscheiden. Die Zahlen verdeutlichen den detaillierteren Unterschied, der später erläutert wird.

TL; NR :

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

wobei π eine ε-gierige Politik ist (z. B. ε> 0 mit Exploration) und μ eine gierige Politik ist (z. B. ε == 0, KEINE Exploration).

1. Angesichts der Tatsache, dass Q-Learning unterschiedliche Richtlinien verwendet, um die nächste Aktion A 'auszuwählen und Q zu aktualisieren. Mit anderen Worten, es wird versucht, π zu bewerten, während eine andere Richtlinie μ befolgt wird. Es handelt sich also um einen Algorithmus außerhalb der Richtlinie.

2. Im Gegensatz dazu verwendet SARSA ständig π, daher handelt es sich um einen On-Policy-Algorithmus.

Detailliertere Erklärung :

1. Der wichtigste Unterschied zwischen den beiden besteht darin, wie Q nach jeder Aktion aktualisiert wird. SARSA verwendet das Q 'genau nach einer ε-gierigen Richtlinie, wie A' daraus gezogen wird. Im Gegensatz dazu verwendet Q-Learning das maximale Q 'über alle möglichen Aktionen für den nächsten Schritt. Dies lässt es so aussehen, als würde man einer gierigen Politik mit ε = 0 folgen, dh KEINER Erkundung in diesem Teil.

2. Wenn Q-Learning jedoch tatsächlich eine Aktion ausführt, verwendet es immer noch die Aktion, die aus einer ε-gierigen Richtlinie stammt. Aus diesem Grund befindet sich "Choose A ..." in der Wiederholungsschleife.

3. Nach der Schleifenlogik beim Q-Learning stammt A 'immer noch aus der ε-gierigen Politik.

Was ist der mathematische Unterschied?

Wie bereits in den meisten anderen Antworten beschrieben, besteht der Unterschied zwischen den beiden Aktualisierungen mathematisch tatsächlich darin, dass beim Aktualisieren des Q- Werts für ein Zustands-Aktions-Paar (S _t , A _t ) :

• Sarsa verwendet die Verhaltensrichtlinie (dh die Richtlinie, die vom Agenten verwendet wird, um Erfahrungen in der Umgebung zu generieren, die normalerweise epsilon- grau ist), um eine zusätzliche Aktion A _{t + 1} auszuwählen , und verwendet dann Q (S _{t + 1} , A _{t) +1} ) (abgezinst durch Gamma ) als erwartete zukünftige Rendite bei der Berechnung des Aktualisierungsziels.
• Q- Learning verwendet die Verhaltensrichtlinie nicht, um eine zusätzliche Aktion A _{t + 1} auszuwählen . Stattdessen werden die erwarteten zukünftigen Renditen in der Aktualisierungsregel als max. _A Q (S _{t + 1} , A) geschätzt . Der max Operator hier verwendet wird, als „nach“ der ganz gierig Politik betrachtet werden. Der Agent folgt jedoch nicht der gierigen Richtlinie . In der Aktualisierungsregel heißt es nur: "Angenommen, ich würde von nun an der gierigen Richtlinie folgen. Wie hoch wären dann meine erwarteten zukünftigen Renditen?".

Was bedeutet das intuitiv?

Wie in anderen Antworten erwähnt, bedeutet der oben beschriebene Unterschied unter Verwendung der technischen Terminologie, dass Sarsa ein On-Policy- Lernalgorithmus und Q-Learning ein Off-Policy- Lernalgorithmus ist.

In der Grenze (bei unendlich viel Zeit, um Erfahrung zu sammeln und zu lernen) und unter einigen zusätzlichen Annahmen bedeutet dies, dass Sarsa und Q-Learning zu unterschiedlichen Lösungen / "optimalen" Richtlinien konvergieren :

• Sarsa wird zu einer Lösung konvergieren, die unter der Annahme optimal ist, dass wir weiterhin dieselbe Richtlinie befolgen, die zur Generierung der Erfahrung verwendet wurde . Dies ist oft eine Politik mit einem Element von (eher "dummer") Zufälligkeit, wie epsilon- grau, weil wir sonst nicht garantieren können, dass wir überhaupt zu irgendetwas konvergieren.
• Q-Learning wird zu einer Lösung konvergieren, die unter der Annahme optimal ist, dass wir nach dem Generieren von Erfahrung und Training auf die gierige Politik umsteigen .

Wann soll welcher Algorithmus verwendet werden?

Ein Algorithmus wie Sarsa ist normalerweise in Situationen vorzuziehen, in denen wir uns um die Leistung des Agenten während des Lernprozesses / der Generierung von Erfahrung kümmern . Stellen Sie sich zum Beispiel vor, dass der Agent ein teurer Roboter ist, der kaputt geht, wenn er eine Klippe hinunterfällt. Wir möchten, dass es während des Lernprozesses nicht zu oft herunterfällt, weil es teuer ist. Daher kümmern wir uns um die Leistung während des Lernprozesses. Wir wissen jedoch auch, dass wir es brauchen, um manchmal zufällig zu handeln (z. B. epsilon-gierig). Dies bedeutet, dass es für den Roboter sehr gefährlich ist, entlang der Klippe zu laufen, da er sich möglicherweise dazu entschließt, zufällig (mit Wahrscheinlichkeit epsilon) zu handeln und herunterzufallen. Wir würden es also vorziehen, schnell zu lernen, dass es gefährlich ist, in der Nähe der Klippe zu sein.Selbst wenn eine gierige Politik in der Lage wäre, direkt daneben zu gehen, ohne zu fallen, wissen wir, dass wir eine epsilon-gierige Politik mit Zufälligkeit verfolgen, und wir legen Wert darauf, unsere Leistung zu optimieren, da wir wissen, dass wir manchmal dumm sind . Dies ist eine Situation, in der Sarsa vorzuziehen wäre.

Ein Algorithmus wie Q-Learning wäre in Situationen vorzuziehen, in denen wir uns nicht um die Leistung des Agenten während des Schulungsprozesses kümmern, sondern nur eine optimale gierige Richtlinie lernen möchten, zu der wir irgendwann wechseln werden. Stellen Sie sich zum Beispiel vor, wir spielen ein paar Übungsspiele (bei denen es uns manchmal nichts ausmacht, aufgrund von Zufälligkeiten zu verlieren) und spielen anschließend ein wichtiges Turnier (bei dem wir aufhören zu lernen und von epsilon-gierig zu gierig wechseln ). Hier wäre Q-Learning besser.

Ihre Formel für Q-Learning enthält einen Indexfehler. Seite 148 von Sutton und Barto.

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

Der Tippfehler steht im Argument des max:

Die Indizes sind st + 1 und a, während sie in Ihrer Frage st + 1 und bei + 1 sind (diese sind für SARSA korrekt).

Hoffe das hilft ein bisschen.

Im Q-Learning

Dies ist Ihr: Q-Learning: Q (St, At) = Q (St, At) + a [R (t + 1) + Rabatt * max Q (St + 1, At ) - Q (St, At)]

sollte in Q-Learning geändert werden: Q (St, At) = Q (St, At) + a [R (t + 1) + Rabatt * max Q (St + 1, a ) - Q (St, At)]

Wie Sie sagten, müssen Sie den maximalen Q-Wert für die Update-Gl. Wenn Sie das a ändern , erhalten Sie ein neues Q (St, At). SORGFÄLTIG ist das a , das Ihnen den maximalen Q-Wert gibt, nicht die nächste Aktion. Zu diesem Zeitpunkt kennen Sie nur den nächsten Status (St + 1), und bevor Sie zur nächsten Runde gehen, möchten Sie die St um St + 1 aktualisieren (St <- St + 1).

Für jede Schleife;

• Wählen Sie At aus der St mit dem Q-Wert

• nimm At und beobachte Rt + 1 und St + 1

• Aktualisieren Sie den Q-Wert mit der Gl.

• St <- St + 1

Bis St Terminal ist

Der einzige Unterschied zwischen SARSA und Qlearning besteht darin, dass SARSA die nächste Aktion basierend auf der aktuellen Richtlinie ausführt, während qlearning die Aktion mit maximalem Nutzen des nächsten Status ausführt