Kartenstapel

Ausgangsproblem:

Wenn man zu viele states hat, ist es nicht mehr möglich alle States abzuspeichern -> keine Tabular Methoden möglich (wo alles noch in Tabellen gespeichert wird). Somit auch nicht mehr möglich den value eines states zu berechnen (state-value function -> siehe „Allgemeiner Recap“)

Ziel:

Wir versuchen den Value eines states zu „approximieren“. Approximieren bedeutet, dass wir der Wert nun mittels Funktionen abgeschätzt wird was er ca. sein könnte (bsp.: lineare Approximation). -> Somit kein Speicher Problem mehr.

Nachteil:

1. Haben nicht mehr 100% Genauigkeit, aber der Trade-of wird eingegangen.

2. Wenn wir den state-value mit einer Schätz-Funktion schätzen, kann es sein, dass wir mit dieser jedoch nicht alle States gleich gut abschätzen (siehe Grafik).

Welche Lösung?

Wir gewichten die states, welche states besser abgeschätzt werden sollen. aka. Wir sagen welche states uns wichtig sind und welche, im Gegensatz, ruhig weniger gut abgeschätzt werden sollen.

Wir gehen davon aus, dass wir „on-policy“ sind und somit eine „on-policy distribution“ haben (= Verteilung, welche besagt mit welcher Wahrscheinlichkeit der Agent die states „encountered“).

Berechnung:

1. Berechnung der „number of time steps spent, on average, in s”

1. “fraction of time spent in s” - Wahrscheinlichkeit für jeden State (on-policy distribution)

Ursprünglich haben wir ja unsere action-value werte immer in einer Tabelle upgedatet. Da wir jetzt aber so viele States haben können wir keine Tabelle mehr machen (zu viel Rechenleistung), daher müssen wir die ja jetzt schätzen. Und was kann am besten mit Wahrscheinlichkeiten umgehen? Damm right – Neuronal Networks. Also werden diese in Zukunft nun unsere action-values berechnen.

Nun updaten wir aber nicht mehr die action-value tabelle, sondern direkt unser Model (training). Und da Ein Model ja Gewichte hat („weight vectors“), welche durch Gradienten stetig angepasst werden müssen wir „the weight vector a little bit in the direction [moven] where it minimizes the error the most“.

1. Nehmen die Ausgangsformel des Gradienten-Abstiegs-Verfahren her

2. Nehmen eine Loss-Funktion her (MSE)

3. Setzen diese ein und „machen die Formel schöner“

4. Da wir einen Teil der Formel nicht kennen (state-value), setzen wir einen Erwartungswert des Returns ein (Erklärung siehe weiter unten)

Ausgangsformel:

Loss formel

eigentlich haben wir keins – ist nur die Frage wie jetzt das Update der Models mit Q-Learning aussieht.

Beim beim Trainieren von NNs gehen wir von der Grundannahme aus, dass die Trainingsdaten „i.i.d“ (independent & identically distributed) sind. Dies ist insofern nicht der Fall, da die observations bzw. states von einer episode mit sehr hoher Wahrscheinlichkeit miteinander korrelieren. Wenn z.b. der Agent nur im Kreis fährt, dann sind alle states – die der agent in dieser episode encountered hat - stark voneinander abhängig.

Ziel:

Stichwort: Buffer. Wir speichern alle States (aus allen Episoden) in einem Buffer und ziehen dann fürs Training eine best. Anzahl davon zufällig daraus (= batch). Somit bekommen wir (mehr oder weniger) states die voneinander unabhängig sind. Ein State könnte dann von Episode 1 sein, während der nächste dann von Episode 10 ist. Der Buffer hat eine gewisse Größe, welche im Vorhinein festgelegt wird (weiterer Hyperparameter – yeah^^). Ist der Buffer voll, überschreiben sich die states darin -> Vorteil, dass ich mit besserem Training auch immer bessere Ergebnisse bekomme, auf welche ich dann weitertrainiere, und die alten, nicht so guten States werden überschrieben.

Nachteil:

• Weiterer Schritt zum Berechnen = mehr Rechenleistung notwendig

• Wenn Buffer Größe zu klein gewählt wird, dann ist die Wsh größer, dass die states noch miteinander korrelieren.

• Wenn Buffer Größe zu groß, dann habe ich noch immer viel „alten bullshit“ drin, welcher fürs training gesampelt werden könnte, obwohl ich schon viel bessere States hätte. (Grundlage für „Prioritzied Replay Buffer DQN“)

1. Der Agent spielt eine gewisse Anzahl an Episoden

2. Alle „state transitions“ (state, action, next state, reward) warden im buffer gespeichert

3. Wir ziehen daraus fürs Training zufällig eine best. Anzahl an states (batch)

Dafür müssen wir nun ein bisschen weiter ausholen:

Unser NN soll ja alle action-values für einen gewissen state berechnen (aus denen wir dann den besten nehmen). Um den Besten ausfindig zu machen, wird jeder action-value mit dem „maximum Q-value“ verglichen (= Subtraktion) und jener Wert der dem „maximum Q-value“ am nähesten ist (= kleinste Differenz) ist dann somit der beste Wert.

[Wird mit der Bellman Equation gemacht -> siehe Basic Recap]

Um diesen „maximum Q-value“ in einem NN zu berechnen, müssen wir einen zweiten Durchlauf in NN machen, bei welchen wir den nächsten state als input reingeben, um die möglichen aktionen des nächsten states zu bekommen Dann alles in die bellman equation rein und – TADAA (lol)

Es gibt dabei jedoch ein Problem! Wir verwenden hier bei beiden Durchläufen dasselbe neuronale Netz mit denselben Gewichten. Wenn wir nun unser NN und somit unsere Gewichte updaten, daten wir damit in weiterer Folge unsere Q-Values (action-values) ab, da wir diese ja nun präziser berechnen können, UND gleichzeitig damit aber auch unsere „maximum Q-values“ (oder auch „target Q-values“ genannt).

Jetzt kommt wieder das SGD hinein, da man sich das alles als eine „Gradienten-Landschaft“ vorstellen muss. Wie ein Gebirge, wo die Gipfel eine hohe Fehlerrate und ein Tal eine geringe Fehlerrate darstellt. Unser Q-Value ist dabei unsere Ausgangslage (wo man sich auf der Landschaft befindet) und unser „target Q-Value“ ist der tiefste Punkt. Es ist wichtig im Hinterkopf zu behalten, dass wir hier ja bei den „Approximation Methods“ sind -> bedeutet wir schätzen hier so gut wie alles.

Hier müssten wir nun Richtung Punkt C um unser Minima zu erreichen, ok, haben wir ja erledigt, doch jetzt updaten wir das ganze (NN):

Uff, nun schaut das die Landschaft gleich ganz anders aus. Das heißt, wrong way, jetzt müssen wir dann wieder in die andere Richtung (Punkt A) optimieren. Machen wir jetzt wieder unser Update, so schaut die Landschaft zB. wieder wie bei der ersten Abbildung aus und wir hüpfen nun die ganze Zeit vor und zurück. Wie können wir das verhindern? Ach das ist easy – lies weiter! (Fabian wieder out)

Einführung eines zweiten NNs („target-network“), welches den target Q-Value berechnet und sich nur alle x-Schritte updatet (neuer Hyperparameter 😉).

Vorgehensweise

Wir führen ein zweites NN ein, welches nur den „target Q-Value“ berechnet (auch „target-network“ genannt). Dieses wird dann immer für eine bestimmte Zeit „eingefroren“ (= kein Update), damit man sich diesem Ziel nähern kann. Nach einer gewissen Anzahl an Schritten x, wird dann das target-network aktualisiert.

Wir haben somit zwei Netzwerke:

• Eines was unseren Q-Value berechnet und sich kontinuierlich updatet

• Ein zweites, welches den target-Q-Value berechnet und sich nur alle x-Schritte updatet.

Nachteil:

Hyperparameter: Je länger das target-network gefreezed ist, desto geringer ist die Wsh, dass wir - wie die Katze - uns im Kreis bewegen. Gleichzeitig wollen wir aber auch wieder das target-network updaten (also unser Ziel), damit wir präzise wissen, wohin wir wollen. (wieder mal ein trade-off).

Ausgangslage:

Wie beim Kapitel „DQNs – Problem – non-i.i.d.“ angesprochen, kann es sein, dass wir beim Ziehen der Samples für unseren Batch (fürs Trainieren) aus unserem Buffer, States ziehen, welche keinen Reward beinhalten, obwohl wir welche im Buffer hätten. Weiters wird derzeit beim Trainieren lediglich mit einem einzigen Schritt (state) durchgeführt (bzw. nur der nächste Zustand betrachtet)

-> d.h. es wird nur der unmittelbare Reward berücksichtigt. Was wenn wir aber ein bisschen „weiter in die Zukunft schauen“ wollen, um eine aktion besser zu bewerten (action-value) zu können und somit unseren Lernprozess schneller machen können?

Ziel:

Statt nur den unmittelbar nächsten Zutand zu betrachten, ziehen wir n-nächste Zustände (n-steps) heran. Wir sammeln quasi mehr Rewards ein, bevor wir alles speichern und trainieren (= den Return fürs Training ausrechnen).

Konkret bedeutet das, dass wir – BEVOR wir unsere Erfahrung im Buffer speichern – n-steps im environment ausführen (= aktionen tätigen).

Von denen bekommen wir die Rewards. Dann wieder alles wie gehabt (in Buffer speichern, batch ziehen, …) Bei der Berechnung des Returns (für die Gradienten) können wir diesen nun aber präziser berechnen, weil wir weniger Rewards schätzen müssen, weil wir diese ja tatsächlich haben. Wir können somit einen genaueren Return (bzw. Erwartungswert des Returns) berechnen

• welcher ja für die Berechnung der Gradienten benutzt wird

• welche für das Training des Models verwendet wird

• welche für die Berechnung der q-values verwendet werden

• welche für die Entscheidungsfindung essentiell sind

• was der Sinn von Reinforcement Learning ist, dass der Agent die „richtige“ Entscheidung trifft.

Vorteil:

• schnelleres Lernen

Nachteil:

• Wieder ein Hyperparameter 😉 Und hier die Frage wie groß man n-steps wählt. Wenn man zu groß wählt, ist man ja quasi wieder fast bei einem Monte-Carlo Prinzip, welches sich erst updatet, nachdem es eine ganze episode durchhat. Das wäre der Fall, wenn n-steps so hoch gewählt wird, dass der agent schon wieder einmal durch ist. Wenn zu gering, dann bekomme ich wenige rewards (ist ja der sinn mehr rewards für ein genaueres training zu haben).

Wir verwenden beim Berechnen des Action-Values (Q-Value) den max Q-Operator (-> Fragen? -> siehe Basics Recap). Damit fangen wir uns einen Bias ein, welcher zu Problemen während des Trainings führen kann. Ein kleines Beispiel:

Der Agent kann in Zustand A die Aktionen links oder rechts auswählen und bekommt dafür jedoch jeweils nur einen Reward von 0. Im Zustand B bekommt er einen gesampelten Reward (nach Normalverteilung -> N), welcher im durchschnitt jedoch bei -0,1 liegt (mit einer Varianz von 1). Eigentlich wäre es ja gescheit, wenn der Agent nach rechts geht, weil dort bekommt er im Durchschnitt „insgesamt“ einen besseren Reward, als wenn er nach links gehen wird. Es kann aber sein, dass der Agent, wenn er nach links geht, zufällig einen Reward von max. 0.9 bekommt (durchschnitt -0,1 + Varianz 1 = 0,9). Daher denkt der Agent „Oh links ist ja ziemlich nice“, auch wenn diese Entscheidung (links gehen) im Durchschnitt nicht so gut ist (als rechts zu gehen). Dies ist der max Q-Funktion geschuldet, welche ja immer den besten Q-Value sucht. Im Endeffekt müsste der Agent dann so oft die Erfahrung machen, dass er im Durchschnitt beim Rechts gehen einen besseren Reward als nach links gehen bekommt. Dieser „positive Bias“ verzögert damit das Lernen sehr stark. Wie gesagt liegt das Problem in der max Q-Funktion. Diese wählt nämlich sowohl den höchsten Q-Value aus UND evaluiert gleichzeitig die beste Aktion.

Ziel:

Wir müssen die Funktion in zwei Schritte aufteilen:

• Den höchsten Q-Value finden (argmax-Funktion)

• Evaluation der Aktion, welche den höchsten Q-Value hat.

Im Kapitel „DQN – Problem – Update des NNs“ haben wir ja ein zweites NN eingeführt, welches ursprünglich für die Berechnung des target Q-Value verwendet wird. Nun können wir dieses „missbrauchen“, um die „Evaluation der Aktion mit den höchsten Q-Value“ durchzuführen. Konkret bedeutet dies, dass das

1. Netzwerk die Aktion mit dem höchsten Q-Value Wert wählt, während das

2. Netzwerk (target-network) diese dann durchführt, um die Q-Values für den nächsten Zustand zu schätzen.

Vorher:

Update:

Nachher:

Wie beim Kapitel „DQNs – Problem – non-i.i.d.“ angesprochen, kann es sein, dass wir beim Ziehen der Samples für unseren Batch (fürs Trainieren) aus unserem Buffer, States ziehen, welche „wichtiger“ fürs Training sind als andere. Ein „Vanilla DQN“ (eines ohne dieses wunderbare Update) wählt ein Element aus dem Replay Buffer mit derselben Wsh aus.

Ziel:

Die Erfahrungen werden nach „Wichtigkeit“ gewichtet. Die wichtigsten Erfahrungen werden dann für das Training hergenommen.

Frage: Wie kann man bestimmen, welche Erfahrung wichtiger ist und welche nicht?

Lösung: Man nimmt sich den Loss-Fehler her und leitet daraus ab, wie viel man aus einer Erfahrung noch lernen kann („Temporary Difference Error“ (TD)). Ist der TD-Fehler hoch kann man noch viel daraus lernen bzw. optimieren und wenn wenig, dann ist man da schon sehr gut unterwegs. Das ist Ziel ist jedoch auf Basis dieser eine Wahrscheinlichkeit zu erstellen, bei welcher Erfahrungen mit höherer Priorität eine höhere Chance haben, ausgewählt zu werden.

Genaue Vorgehensweise -> siehe „Vorgehensweise – detail“.

Nachdem eine Erfahrung ausgewählt und für das Training verwendet wurde, wird der TD-Fehler aktualisiert, um die Differenz zwischen den geschätzten und den tatsächlichen Q-Values zu berücksichtigen. Dieser aktualisierte TD-Fehler wird dann verwendet, um die Priorität im Buffer zu aktualisieren.

• Eindeutig mehr Rechenleistung

• Der TD-Fehler aktualisiert sich nur, wenn die jeweilige Erfahrung zum Trainieren verwendet wird.

1. Berechnen des TD-Errors

2. Auf Basis derer eine Wahrscheinlichkeit berechnen

3. Darüber ein „Stochastic Proportional Sampling“ laufen lassen Wir berechnen uns den Temporary Difference Error (TD). Dafür rechnen wir hier den geschätzten Q-Value für eine bestimmte Aktion im aktuellen Zustand gegen den geschätzten Q-Value für die beste Aktion im nächsten Zustand.

Da wir aber jetzt nicht einfach immer nur die Erfahrung mit der höchsten Priorität nehmen (deterministisches Prioritization), sondern anderen Erfahrungen auch eine Chance geben wollen, müssen wir eine Wahrscheinlichkeit aufbauen.

Das Ziel ist hierbei eine Wahrscheinlichkeit aufzubauen, welche proportional zur Priorität (also TD-Error) steht.

Das bedeutet, dass Erfahrungen mit höherer Priorität eine höhere Wahrscheinlichkeit haben, ausgewählt zu werden, während Erfahrungen mit weniger Priorität weniger Wsh haben. Zunächst müssen wir dafür alle TD-Error Werte normalisieren. Dafür wir die Priorität einer Erfahrung durch die Gesamtsumme aller Prioritäten dividiert.

Alpha ist dabei ein Parameter, welcher angibt wie glatt/gleichverteilt die Verteilung aussehen soll. Bsp.: Ein Alpha von 0 bedeutet, dass alle Werte gleichverteilt sind (was ja eig nicht Sinn der Sache ist) und je höher, desto mehr die Verteilung bei P(i) (also TD-Error).

Nun wird ein stochastic proportional sampling angewandt. Dabei wird eine Zufallszahl zwischen 0-1 generiert und dann jene Erfahrung ausgewählt, deren kumulative Wahrscheinlichkeit diesen Wert überschreitet.

Die ganze Geschichte hat jedoch noch einen weiteren Hacken:

Wir führen uns damit einen neuen Bias ein. Dieser kommt daher, dass unsere Wahrscheinlichkeit proportional zur Priorität der einzelnen Erfahrung ist. Dadurch ist sie jedoch nicht mehr direkt proportional zu ihrer tatsächlichen Wahrscheinlichkeit (da wären ja quasi alle gleich). Und dies kann zu Verzerrungen führen.

Diesem können wir aber entgegen gehen, indem wir „importance sampling weights“ einführen. Diese werden verwendet, um den Verlust bei der Aktualisierung der Netzwerkparameter zu gewichten, wodurch der Einfluss des Bias reduziert wird.

Hierbei ist N die Gesamtanzahl der Erfahrungen im Replay Buffer und Pi die Priorität der Erfahrung i. Wenn β=0, werden die Importance Sampling Gewichte auf 1 gesetzt, was bedeutet, dass keine Korrektur vorgenommen wird. Je größer der Wert von β, desto stärker werden die Prioritäten korrigiert.

Generell macht es Sinn β<1 zu initialisieren und dann über die Zeit β->1 gehen zu lassen.

Wie viele wahrscheinlich in der Übung gemerkt haben, dauert das Trainieren übelst lange (vor allem wenn man einen Prioritized Replay Buffer eingebaut hat). Gibt es nicht eine Möglichkeit das Lernen etwas zu beschleunigen?

Neustrukturierung des NN. Wir schätzen die Q-Values nicht direkt für eine Aktion, sondern zerlegen sie in 2 Bestandteile:

• Value

• Advantage

Value = erwartete Reward (Return) für einen best. Zustand, unabhängig von der ausgewählten Aktion Advantage = zusätzliche Nutzen, den jede Aktion im Vergleich zum Durchschnitt der Aktionen in diesem Zustand bietet. Dies geht vor allem dann, wenn wir uns in einem Environment befinden, welches nicht aktiv durch die Aktionen verändert wird.

Durch die Zerlegung in zwei neuronale Netzwerke, kann der Value und Advantage separat voneinander gelernt werden -> Effizienter, da weniger Zeit dafür draufgeht, sich auf die genaue Bewertung jeder einzelner Aktion in jedem Zustand zu konzentrieren.

• V(s) der Wert des Zustands s, der vom Wert-Netzwerk geschätzt wird.

• A(s,a) der Vorteil der Aktion a im Zustand s, der vom Vorteils-Netzwerk geschätzt wird. Hier ist A, aber noch nicht eindeutig, weil wir die Aktion ja immer im Vergleich im Vergleich zum Durchschnitt aller anderen Aktionen sehen. Daher müssen wir den Durchschnitt nochmal subtrahieren.

  
  

Manchmal ist die Espilon-Greedy Policy nicht die effektivste. Ein kleines Beispiel:

Hier hat der Agent eine Route gefunden, welche vom Start (Grün) zum Ziel (rot) führt. Weiters sieht man recht gut wie hoch die Wsh ist, dass der Agent nun die jeweiligen Felder (States) antreffen wird.

Wie man sieht, ist dies jedoch noch lange nicht der effektivste Weg, um ans Ziel zu gelangen. Denn der Epsilon-Greedy Algorithmus hat einen entscheidenden Nachteil: Sobald er einmal eine „erfolgreiche“ policy entdeckt hat, wird diese exploitet und davon „entfernte“ states werden fast gar nicht mehr besucht. Wie man in der Abbildung sieht, würde es in manchen States durchaus noch Sinn machen zu exploren (z.b. in jenen, wo man mit einer anderen Richtung schneller zum Ziel käme). Wir brauchen somit eine andere Art von Exploration.

Ziel:

Wir ändern den Epsilon-Greedy Ansatz insofern, indem wir eine „deterministische Wahrscheinlichkeit“ ersetzen. Dafür werden stochastische Rauschkomponenten in die Aktionswerte eingeführt. Man kann sich das als Störung oder Unsicherheit vorstellen, welche den Aktionswerten hinzugefügt werde, um eine gewisse Unsicherheit beim Agent einzuführen.

Das ist Ziel ist es somit, dass der Agent immer noch eine gewisse Ungewissheit in seinen Aktionen miteinbezieht und somit ein ausgewogeneres Exploration-Exploitation Verhältnis zu schaffen.

1. Aktionswerte als stochastische Größen modellieren

2. Parametrisierte Rauschkomponenten einfügen

3. Dann wird eine Aktion ausgewählt

4. Im Training werden dann zusätzlich die Parameter der Rauschkomponenten angepasst

5. Aktionswerte als stochastische Größen modellieren Dies bedeutet, dass wir statt feste Aktionswerte nun annehmen, dass Q-Values eine zufällige Variable ist, die einer gewissen Wahrscheinlichkeitsverteilung folgt.

6. Parametrisierte Rauschkomponenten einfügen Diese sind Funktionen mit einstellbaren Parametern, welche die Stärke des Rauschens steuern.

Inspiration kommt von der Biologie nach dem „Fight or Flight“-Prinzip. Statt unnötig lange mich mit diversesten Rechnungen auseinanderzusetzen (aka diverse Bewertungsfunktionen) kann ich doch direkt meine policy updaten. Würde einiges an Zeit sparen.

Ein Ansatz der „direct policy methods“ ist die „Policy Gradient Method“. Hier wird eine sogenannte „parametrisierte Policy“ angewandt, was bedeutet, dass die policy als Funktion dargestellt wird, welche durch Parameter beeinflusst wird. Wir arbeiten hier wieder mit NNs und verwenden das Gradienten-Verfahren, um unser Modell zu trainieren, um die idealen Parameter für unsere Policy zu bekommen.

Um die Policy direkt evaluieren zu können, verwenden wir eine Güte-Funktion (J), welche angibt wie gut unsere Parameter sind, die wir für die Policy verwenden. Den Wert den wir bekommen soll dementsprechend so hoch wie möglich sein. Wir wollen somit keinen Fehler minimieren, sondern unseren Güte-Wert stetig erhöhen (endlich mal ein optimistischer Ansatz 😊). Wir suche somit beim Trainieren den Gradienten, welcher und die Richtung für den höchsten Anstieg gibt -> daher verwenden wir beim Gradienten Verfahren nun nicht den Abstieg, sondern den Aufstieg = Stochastic Gradient-Aufstieg-Verfahren.

Auch hier können wir den Gradienten wieder nur schätzen -> deswegen rechnen wir uns den Erwartungswert des Gradienten aus.

• Die Policy darf nicht deterministisch oder 0 sein, da sonst keine Exploration möglich ist (aka alle Aktionen dürfen nicht die gleiche Wsh oder festgelegte Wahrscheinlichkeiten haben. Denn sonst wird immer nur eine Aktion ausgeführt).

• Weiters muss die Policy differenzierbar sein, da man sonst kein Gradienten Verfahren anwenden kann (auf einer Grafik würde das bedeuten, dass es keine Kanten geben darf).

Das O ist unsere Parameter, welche die Policy beeinflussen (wie wir vorhin schon gehört haben). Die Policy beeinflusst die Aktion, die wir auswählen, welche in weiterer Folge den Reward beeinflusst, welchen wir bekommen. Zudem hat die Policy jedoch auch einen Einfluss auf die „visiting state distribution“ – also mit welcher Wsh der agent welche states encountered – welche wieder einen Einfluss auf den Reward hat (in manchen States kann man mehr Reward bekommen als in anderen).

Wie man in der Grafik sehen kann, ist der Effekt auf die Aktion relativ straight forward. Der Einfluss auf die visiting state distribution auf der anderen Seite ist uns jedoch ziemlich unbekannt. Das ist aber ein Problem, wenn wir die Gradienten berechnen wollen, da mit der Information – wie oft bestimmte Zustände während des Lernprozesses besucht wurden – eine Gewichtung der Gradientenschätzung schwierig wird.

Eine Lösung für dieses Problem bietet das „Policy Gradient Theorem“.

Das Prinzip des Policy Gradient Theorem besagt, dass der Gradient unserer Güte-Funktion proportional zu folgender Formel ist:

∇J(θ) = Gradient der Güte-Funktion

∑s = Summe über alle Zustände

μ(s) = stationäre Verteilung der Zustände unter der Policy.

∑a = Summe über alle möglichen Aktionen, die im Zustand s getätigt werden können.

qπ(s,a) = Action-Value Function

∇π(a∣s,θ) = Gradient der Policy in Bezug des Parameters θ

Der Gradient des erwarteten Gewinns in Bezug auf die Policy-Parameter ist proportional zur Summe über alle States, gewichtet mit ihrer stationären Verteilung Summe über alle Aktionen, gewichtet mit dem Wert dieser Aktionen und dem Gradienten der Policy.

Um ein besseres Verständnis zu erlangen, kann man die Formel von rechts nach links interpretieren: Der Gradient der Policy ∇θπ(a∣s,θ) für jede mögliche Aktion a in jedem Zustand s wird mit dem Wert dieser Aktion, gegeben durch die action-value Funktion qπ(s,a), gewichtet. Diese gewichteten Gradienten werden dann über alle Aktionen ∑a und Zustände ∑s summiert. Da wir natürlich die genaue Summe aller Actions und States kennen, wird auch hier wieder ein Schätzwert (Erwartungswert) berechnet.

Damit bleibt die genaue Verteilung der Zustände durch die Policy zwar noch immer unbekannt, aber wird können die Gradienten dennoch berechnen.

Unsere Ausgangslage: (kennen wir von vorhin)

1. Wir fangen gleich mal damit an, dass wir in unseren mathematischen Trickkistensack greifen und die Definition des Erwartungswert rausholen.

Diesen können wir nämlich einsetzen, wenn wir uns ∑s μ(s) anschauen. Da wir hier die Summe aller States berechnen und da ja sowieso einen Erwartungswert rausbekommen (verwenden den Erwartungswert, um die Summe aller States zu approximieren), können wir diese Formel einfach mal ganz böse einsetzen. Das schaut soweit mal so aus:

Die ∇J(θ) fällt weg, weil wir uns jetzt nur noch auf die rechte Seite konzentrieren. Und das ∑s μ(s) ist beim Erwartungswert das ∑x (X=x). Der Rest ist noch der restliche Teil von rechts.

blau:

= der Gradient der Policy, welcher die Richtung angibt, welche die Wahrscheinlichkeit erhöht, dass eine best. Aktion a eintritt, wenn der Agent sich im konkreten Zustand s befindet. aka. Wenn wir in diese Richtung weitergehen, erhöht sich die Wahrscheinlichkeit, dass – wenn sich der Agent im Zustand s befindet - die Aktion a nochmal eintritt.

rot:

= Der Skalar (Return) erhöht bzw. verringert den Gradienten, je nachdem ob die Aktion gut oder schlecht war (viel Return oder weniger Return).

Aka bekommt der Agent viel Return (großer Returnwert) wird der Gradient größer (weil mit größerer Zahl multipliziert). Und wenn der Return klein ist (kleiner Returnwert), wird der Gradient kleiner (weil mit kleinerer Zahl multipliziert).

Ist somit in gewisser Weise ein Indiz, ob die Aktion gut oder schlecht war und ob wie sehr wir diese Aktion wieder haben wollen.

grün:

Dient der Normalisierung, damit die Wahrscheinlichkeit (Länge des Vektors) nicht zu heftig auseinandergeht. Bzw. verfolgt dies dem Ziel, dass wir immer noch Exploration haben. Würde die Verteilung zu sehr auseinandergehen, hätten gute Aktionen eine sehr hohe Wahrscheinlichkeit und schlechte eine sehr viel Geringere. Dadurch, dass wir die Wahrscheinlichkeiten „zusammenhalten“ gewährleisten wir immer noch ein gewisses Maß an Exploration.

Der Schritt des Trainings dauert immer zu lange. Gibt es nicht eine Möglichkeit dies zu beschleunigen?

Ziel:

Einführung eines „Baseline“.

Zunächst brauchen wir eine mathematische Begründung, warum man eine Baseline in die Formel einsetzen darf:

Dafür müssen wir wieder in unseren mathematischen Trickkistensack greifen. Wir berechnen ja die Summe aller Gradienten aus allen Aktionen

Da der Gradient linear ist können wir mathematisch gesehen die Summe und den Gradienten in der Formel vertauschen (oha).

In weiterer Folge kann man die Formel nun so lesen, dass die Summe aller Aktionen einer Policy immer eine Policy sein muss – und in Zahlen ausgedrückt ist das

1. Insgesamt schaut unser mathematischer Gedankengang nun folgendermaßen aus:

Die ganze Formel ändert sich auch nicht, wenn wir einfach einen Term einfügen:

Unsere Ausgangsbasis

kommt uns ja in dieser Formel sehr bekannt vor:

Somit können wir die baseline in die Formel einfügen:

Nach einiger „umadum-Herumformerei“ – ziehen wir die Baseline dann vom Return ab.

REINFORCE ist wie ein Monte-Carlo Algorithmus, bedeutet dass das Training immer nur am Ende einer Episode stattfindet. Was wenn wir aber innerhalb einer Episode trainieren wollen?

Ziel:

Bootstraping

Vorgehensweise:

Statt den kompletten Return (wie beim REINFORCE) verkürzen wir diesen um n-Schritte und bekommen ihn quasi schon vorher. Weiters teilen wir - ähnlich wie ein Dueling DQN – das NN in zwei Teile:

• Actor = lernt wie man acten soll

• Critic = lernt wie viel reward man sich erwarten kann Trainiert werden beide Teile dabei durch einen gemeinsamen Loss, welcher sich aus den beiden Loss(es) der jeweiligen Teile ergibt.

  
  

Zusätzlich müssen wir einen Gewichtungsfaktor w einführen, damit die 2 Losses nicht in zwei unterschiedliche Richtungen gehen (das wäre kontraproduktiv).

Zusätzlich wird ein Advantage Value eingeführt, um den Lernprozess zu verbessern. Der Advantage-Wert ist eine Schätzung des Vorteils oder des Nutzens einer bestimmten Aktion (wie viel trägt die Aktion a zum Return bei) im Vergleich zu anderen Aktionen in einem bestimmten Zustand. Er gibt an, wie viel besser oder schlechter eine bestimmte Aktion im Vergleich zu anderen ist.

Themenwechsel – Gradienten Landschaft (siehe Kapitel „DQNs - Problem – Update des NNs). In der Praxis wurde immer wieder beobachtet, dass es in der Gradienten Landschaft Regionen gibt, welche sich nach dem Updaten sich radikal verändern und somit „wirre Sachen“ passieren. Dies verzögert das Lernen sehr stark. Gleichzeitig gibt es umgekehrt aber auch Regionen, welche nach dem Update stabil bleiben und somit vorhersehbarer sind. Solche Regionen werden auch „Trust Regions“ genannt, da man hier vertrauen kann, dass alles beim selben bleibt.

Ziel:

Wenn der Agent die Gewichte seines NNs updatet, soll er dies wenn möglich in einer „Trust Region“ tun, um die Lernstabilität zu verbessern. Und wenn er in einer ist, dann soll er sich nicht allzu weit bewegen, damit er nicht unabsichtlich aus einer Trust Region rausbewegt.

Vorgehensweise:

Um dies durchzuführen wird die Methode „Proximal Policy Optimization“ (PPO) verwendet:

Es wird eine Clipping-Methode eingeführt, welche den Loss kappt. Dies stellt sicher, dass das Policy-Update nicht zu groß ist (und somit nicht über einen definierten Schwellwert hinaus geht).

Berechnung:

1. Berechnung der r (ratio), um herauszufinden, ob überhaupt geupdatet werden soll

2. Multiplikation mit dem Advantage-Value

3. Einfügen des Clip-Value

4. Berechnung des finalen Losses + Entropie

1. Berechnung der r (ration) Es wird eine neue Größe r (ratio) eingeführt, welche das Verhältnis zwischen neuer und alter policy darstellt. Genauer genommen wird hier berechnet, um wie viel sich die Wahrscheinlichkeit der ausgewählten Aktion (dass sie ausgewählt wird) unter der neuen policy – im Vergleich zu alten policy – geändert hat.

1. Multiplikation mit Advantage-Value

   Meistens wird für die alte policy ein Wert von 1 angegeben. Ist die neue Policy-Wert nun größer wird die ratio über 1 liegen, ansonsten unter 1. Zusätzlich wird die ratio noch mit dem Advantage-Value multipliziert, um miteinzubinden, wie vorteilhaft diese Aktion nun mit der neuen policy im Gegensatz zur alten ist. Somit wird neben der Auswahlwahrscheinlichkeit, auch der Vorteil der Aktion miteinbezogen.

Im Endeffekt kann das Endergebnis dann gemessen werden, ob diese über 1 oder unter 1 liegt. Liegt der Wert über 1 (= die Wsh, dass die Aktion ausgewählt wird hat sich erhöht und hat mehr Nutzen), dann wird ein Update gemacht. Hat sich die Wsh jedoch nicht erhöht und hat weniger Nutzen als in der alten policy, dann wird nicht einmal ein Update gemacht. Somit begeben wir uns nicht erst in die Gefahr, dass man sich aus der Trust-Region herausbewegt.

1. Einfügen des Clip-Values

   Der Clip wird nun in die Berechnung miteingefügt, um den Loss zu kappen.

Hierbei ist clip(x,a,b) eine Funktion, die den Wert von x auf den Bereich [a,b] klippert. Somit wird der ratio-Value zwischen den Bereichen 1 - ε, sowie 1 + ε gekippet.

1. Berechnung des finalen Losses + Entropie

Somit haben wir 2 Losses:

• Loss der Value-Function

• Loss der ceclippt wird Diese müssen wir nun noch miteinander kombinieren.

Wie man hier sieht wird hier noch das Maß der Entropie eingeführt – Warum?

Entropie ist ein Maß der „Unordnung“ (oder pures Chaos (wenn Wert 1)). Durch diese Optimierung kann man in die Gefahr laufen, dass die policy am Schluss zu deterministisch wird, was man um jeden Preis verhindern will. Deswegen wird im Loss noch ein gewisses Maß an Unordnung hineingenommen, um mit der Entropie ein gewisses Maß an Exploration hochzuhalten. Die Entropie kann somit als Gegenkraft verstanden werden, welche schaut, dass die policy nicht zu deterministisch wird.

Die Entropie kann dabei Werte von 0-1 annehmen.

• 0 = kein Chaos -> es kann nur ein Wert ausgewählt werden (deterministisch)

• 1 = pures Chaos -> alle Werte sind gleichverteilt

Positiv:

Da der Advantage-Value positiv ist, können wir davon ausgehen, dass die Aktion den expected Return verbessert. In der Grafik sehen wir den Punkt 1. Dies ist besagter Punkt, bei welcher es keinen Unterschied zwischen neuer oder alten policy gibt. Wenn es nun besser ist, gibt es einen Clipp bei 1 + ε. Ab diesem Schwellenwert (definiert durch ε) wird der Loss gekappt, damit der Schritt nicht zu groß ist. Umgekehrt ist es uns egal, da wenn der Loss gegen 0 geht, der Schritt somit sowieso nicht so groß sein wird. Somit werden wir nicht zu über-optimistisch und verlassen im schlimmsten Fall unsere Trust-Region.

Negativ:

Bei einem negativen Advantage Wert haben wir dasselbe Spiel in umgekehrt. Da wir hier von negativen Werten ausgehen, muss es einen clip geben der Richtung 0 kappt, damit auch hier der Schritt in Richtung einer besseren policy (von minus auf 0) nicht zu groß ist.

Angenommen, wir haben ein Spiel mit vielen möglichen Zügen und Zuständen. Wir möchten wissen, welcher Zug am besten ist, um das Spiel zu gewinnen oder ein anderes definiertes Ziel zu erreichen. Aufgrund der Komplexität des Spiels ist es schwierig, alle möglichen Züge zu analysieren und die beste Handlung zu identifizieren.

Ziel:

Die MCTS versucht dieses Problem zu lösen, indem sie eine systematische Methode bietet, um den Raum der möglichen Handlungen zu erkunden und dabei die vielversprechendsten Pfade zu priorisieren. Sie verwendet Simulationen, um zufällige oder heuristische Handlungen auszuprobieren und die Ergebnisse auf einen Baum zurückzuführen, der verschiedene Spielverläufe darstellt. Durch die iterative Erweiterung und Bewertung dieses Baumes kann die MCTS eine gute Annäherung an die beste Handlung liefern, die zu einem erfolgreichen Ergebnis führt.

Vorgehensweise – grob:

• States = nodes / Knoten

• actions = edges / Kanten

• Der MCTS wird in deterministischen Environments angewandt!

Die Monte-Carlo-Tree-Search (MCTS) ist wie ein schlauer Spieler, der in einem Spiel entscheiden muss, welcher Zug der Beste ist. Hier ist eine vereinfachte Erklärung:

1. Baum aufbauen:

   1. Stell dir vor, du beginnst mit einem leeren Baum, der den Startzustand des Spiels darstellt. Das ist wie ein leeres Blatt Papier.

   2. Dieser Startzustand ist wie der Samen, aus dem der Baum wächst. Er ist der Anfang.

2. Den Baum erkunden und erweitern:

   1. Der schlaue Spieler beginnt, den Baum zu füllen, Schritt für Schritt. Er wählt Aktionen aus und sieht, wohin sie ihn führen.

   2. Jedes Mal, wenn er eine Aktion wählt, wächst der Baum um einen neuen Ast. Es ist wie das Zeichnen eines Bildes, während man neue Ideen erkundet.

3. Simulationen durchführen:

   1. Nachdem der Baum gewachsen ist, macht der Spieler sich eine Vorstellung davon, wie das Spiel verlaufen könnte. Er spielt das Spiel in seiner Vorstellung durch, um zu sehen, wie gut seine Züge sein könnten.

   2. Es ist wie das Träumen von verschiedenen Möglichkeiten, wie das Spiel ausgehen könnte.

4. Bewertung und Lernen:

   1. Der Spieler denkt darüber nach, wie gut seine Vorstellungen waren. Er bewertet, wie gut oder schlecht seine Züge waren und was er daraus lernen kann.

   2. Diese Bewertungen helfen ihm, besser zu werden und klügere Entscheidungen zu treffen.

5. Wiederholung des Prozesses:

   1. Der Spieler wiederholt diesen Prozess immer wieder. Er fügt neue Ideen hinzu, denkt über sie nach, spielt sie durch und lernt daraus.

   2. Mit jedem Durchgang wird der Baum größer und der Spieler klüger.

1. Selektion:

   1. Die Selektion beginnt am Wurzelknoten des Baumes.

   2. Von dort aus wird iterativ eine Knoten im Baum ausgewählt, der die Auswahlkriterien erfüllt, normalerweise basierend auf dem UCB1-Algorithmus (Upper Confidence Bound).

   3. Der UCB1-Algorithmus berücksichtigt dabei sowohl die Güte des Pfades (durchschnittliche Belohnung) als auch die Exploration (wie oft der Pfad besucht wurde) und führt zu einem Trade-off zwischen Ausbeutung bekannter Pfade und Exploration neuer Pfade.

   4. Zu Beginn wird der Wurzelknoten verwendet.

2. Expansion:

   1. Sobald ein Knoten erreicht ist, der noch nicht vollständig expandiert wurde (d.h. er hat unbesuchte Kindknoten), wird er erweitert.

   2. Neue Kindknoten werden hinzugefügt, um mögliche zukünftige Spielzüge zu repräsentieren.

   3. Es ist wichtig zu beachten, dass MCTS nur diejenigen Kindknoten expandiert, die im Spiel tatsächlich erreichbar sind, basierend auf den aktuellen Regeln und Zuständen.

3. Simulation:

   1. Für die neu hinzugefügten Kindknoten werden Simulationen durchgeführt, um mögliche Spielverläufe zu bewerten.

   2. Jede Simulation führt zu einem bestimmten Endzustand und einer zugehörigen Belohnung oder Bewertung.

4. Rückwärtsdurchlauf (Backpropagation):

   1. Nachdem die Simulationen abgeschlossen sind, werden die Ergebnisse auf die Elternknoten zurückgeführt.

   2. Die Belohnungen oder Bewertungen werden aufsummiert und die Statistiken der Knoten (wie Anzahl der Besuche, kumulierte Belohnung) entsprechend aktualisiert.

   3. Diese Aktualisierung der Statistiken ermöglicht es dem Algorithmus, im Laufe der Zeit eine bessere Schätzung der Spielzüge und ihrer potenziellen Belohnungen zu erhalten.

Uns interessieren primär die Kanten, weil am Schluss eines jeden Trees ja die beste Aktion gewählt werden soll.

Für jede Aktion (= Kante) speichern wir folgende 4 Metriken:

1. Durchgang - „Aller Anfang ist schwer“

1.1 Select

Wir haben unseren Wurzelknoten / Anfangsstate. Dementsprechend ist beim select ziemlich klar welcher state genommen wird – ansonsten würde ein Suchalgorithmus (bsp.: UCB1) dafür verwendet (siehe 2.1.)

1.2 Expand:

• Dieser State wird mal in das Model gegeben, um alle möglichen daraus resultierenden Folge-States (bsp.: a3) zu ermitteln.

• Gleichzeitig werden alle Aktionen (Kanten, die zu den Knoten führen) durch ein NN geschickt, um die prio probabilites zu erstellen (bsp.: 0.52). Man kann sich das wie ein erstes „Bauchgefühl“ vorstellen, mit welcher die Aktionen zunächst einmal bewertet werden.

1.3 Evaluate

Nun evaluieren wir den Ausgangs-State, indem jeder Folge-State weitergespielt wird, bis es das Spiel zu Ende geht. Dabei bekommt man in der Regel einen Reward von 1,0,-1 je nachdem ob das Spiel dann gewonnen, unentschieden oder verloren ausging.

1.4 Backup

Jetzt werden unsere Informationen, die wir im vorangegangenen Schritt gesammelt haben, verarbeitet. Dafür gehen wir zunächst von jedem State - den wir durchevaluiert haben – und gehen zur dazugehörigen Aktion und daten die restlichen 3 Metriken ab (N, Q, W). Diese brauchen wir dann wieder im nächsten Durchgang. Außerdem bewerten wir nun den darüber liegenden state, von welchem die aktionen ausgingen, auf Basis unserer gesammelten Informationen (auch wieder diese 3 Metriken).

2. Durchgang – „We’re gonna build this city”

Nun soll der nächste State gewählt werden, welche dann wieder expanded wird, etc. Die Frage ist nur: „Wie entscheiden wir, welchen state wir nehmen?“. In Punkt 1.1. wurde ein Suchalgorithmus angesprochen. Dieser sieht sich nämlich die durchschnittliche Belohnung für die aktion an, sowie einen neuen Wert U an. Exkurs: Was ist der Wert U? Der Wert U beschreibt den „Exploration Bonus“ und ist ein echt interessantes Konzept! Im Grunde gibt dieser Wert uns aus, wie viel Information wir uns von diesem State erhoffen. Wie kann man das definieren? Dazu schauen wir uns mal die Formel dazu an:

Neben der eindeutigen USA Referenz (lol) haben wir hier 3 Teile:

C(put) = Skalierfaktor, welche den Trade-off zwischen Exploration und Exploitation steuert (ist hier aber nicht so wichtig!)

P(s|a) = Prior Probability. Da dieser mit dem Exploration Bonus-Kern (hintere Teil - mir fällt kein besserer Name ein) multipliziert wird, kann gesagt werden, dass wenn die Prior Probability höher ist, ist auch der Exploration Bonus höher und umgekehrt. „Exploration Bonus-Kern“ = Wir haben hier zwei Teile:

• Über den Bruch haben wir die Summe wie viele Aktion insgesamt schon genommen wurden.

• Unter dem Bruch steht die Anzahl wie oft diese konkrete Aktion schon genommen wurde.

Je mehr Aktionen wir generell nehmen, desto höher wird allgemein der “Exploration Bonus-Kern“, da die Zahl über dem Bruch größer wird. ABER: wenn wir uns dann einmal für eine bestimmte Aktion entscheiden, rasselt bei dieser der jeweilige „Exploration Bonus-Kern“ in den Keller, da sich für die best. Aktion die Zahl unter dem Bruch erhöht. Somit verringert sich der Exploration Bonus für diese Aktion generell. Vom Prinzip her ist dies wegen 3 Punkten echt genial:

• Wenn wir diese Aktion einmal genommen haben, kann man davon ausgehen, dass wir genug Informationen bekommen haben und dass nun andere Aktionen mehr Informationen bereithalten.

• Davon ausgehend, dass der Exploration Bonus (U) mit den gemittelten Rewards (Q) addiert wird, kann es aber trotzdem sein, dass eine bestimmte Aktion so einen hohen durchschnittlichen Reward hat. Wenn die Summe eines hohen durchschnitts Rewards + geringer Exploration Bonus (da ja schon einmal gewählt) trotzdem noch der höchste Wert ist, dann wird nochmal diese Aktion gewählt. Da man ja davon ausgehen kann, dass die Aktion so übelst nice ist, dass man diese nochmal nehmen sollte. Prinzipiell favorisiert der Exploration Bonus somit neue, unerforschte Aktionen, hält aber immer noch die Möglichkeit offen, dass übelst gute Aktionen ausgenutzt werden.

• Wurde eine Aktion mal ausgewählt und ist nun der Exploration Bonus sehr low. Über die Zeit wird sich diese jedoch wieder erhöhen, da mit ansteigender Zahl der gesamt gewählten Aktionen, ja die Zahl über den Bruch wieder höher wird. Somit steigt mit der Zeit auch wieder die Wahrscheinlichkeit, dass eine zuvor gewählte Aktion, im späteren Verlauf wieder ausgewählt werden kann.

All in all ist die Einführung des Exploration Bonus echt smart, weil man innerhalb des MCTS priorisiert, was man durchgehen will und was nicht (man hat ja auch nicht ewig Zeit).