Diese Arbeit untersucht den Einsatz agentenbasierter Lernalgorithmen im wiederholten Cournot-Spiel. Es werden zwei unterschiedliche Implementierungen (eine nach Roth-Erev, die andere nach Watkins Q-Learning) des sogenannten Reinforcement Learning untersucht. Diese Implementierungen werden in die Modellwelt des bekannten Cournot-Spiels gesetzt, um gegeneinander zu spielen. Es sind Arbeiten bekannt, in denen Q-Learning Agengenten, kooperierendes Verhalten lernen. Es ist Ziel dieser Arbeit, die Unterschiede theoretisch herauszuarbeiten und praktisch in Java zu implementieren. Dabei soll die Frage geklärt werden, warum nur Q-Learning kooperierendes Verhalten erzeugt.
Inhaltsverzeichnis
1 Einführung
2 Computersimuliertes Lernen
2.1 Das Basismodell
2.2 Q-Learning
2.2.1 Lernmodell
2.2.2 Primitives Lernen
2.2.3 Entscheidungen treffen
2.2.4 Parameter
2.3 Roth-Erev Methode
2.3.1 Entscheidungen treffen
2.3.2 Parameter
3 Vergleich der Modelle
4 Implementierung für das Cour not-Spiel
4.1 Komplexität
4.2 Agentenbasiertes Design
4.3 Stationäre Umwelt
4.4 Dynamische Umwelt
4.4.1 Standard Q-Learning Parameterbereiehe
4.4.2 Standard Q-Learning Sequenzen
4.4.3 Zustandsloses Q-Learning
4.4.4 Roth-Erev
5 Kooperationsähnliches Verhalten
6 Zusammenfassung
7 Literatur
8 Anhang
1 Einführung
Diese Arbeit untersucht den Einsatz einer Klasse agentenbasierter Lernalgorithmen im wiederholten Cournot-Spiel, Es werden zwei unterschiedliche Implementierungen des sogenannten Reinforcement Learning untersucht, die eine von Alvin E, Roth und Ido Erev [12, S, 171 ff,], die andere von Christopher J.C.H, Watkins [17, S, 95 ff,]. Letztere ist als Q-Learning in die Literatur eingegangen, erstere werde ich im Folgenden kurz als RE bezeichnen. Diese Implementierungen werden in die Modellwelt des bekannten CournotSpiels gesetzt, um gegeneinander zu spielen. Es soll das Verhalten über den Spielverlauf untersucht werden, um folgende Fragen zu beantworten: Gibt es Konvergenz zu stabilen Punkten, wenn ja, wie geschieht dies und wann stellt sie sieh ein? Diese Fragen werden immer in Abhängigkeit der Parametrisierung der beiden verschiedenen Implementierungen erörtert. Es sind Arbeiten bekannt, in denen Agenten, die Q-Learning anwenden, kooperierendes Verhalten zeigen. Dies wird z.B, von Waltman und Kavmak in [15] beschrieben, aber auch von Kimbrough und Lu in [9], F ür RE dagegen sind keine Ergebnisse bekannt, die darauf hindeuten, dass Agenten kooperieren. Es ist Ziel dieser Arbeit, die Unterschiede zwischen RE und Q-Learning herauszuarbeiten, um die Frage zu klären, warum Q-Learning kooperierendes Verhalten erzeugt,
Kapitel 2 gibt Auskunft, über die Theorien hinter RE und Q-Learning, Ein Vergleich der Methoden erfolgt in Kapitel 3, In Kapitel 4 werden die Ergebnisse von Simulationsläufen beschrieben, die für RE und Q-Learning weite Parameterbereiehe automatisiert testen. Im letzten Kapitel wird eine theoretische Arbeit besprochen, die über eine Simplifizierung des Cournot-Spiels zum Gefangenendilemma, die Erklärung für das Verhalten von Q-Learning und Kooperation gibt.
In Kapitel 4, dem umfangreichsten Punkt dieser Arbeit, sind praktische Parametrisierungen für Reinforcement Learning dargestellt. Die Arbeit ist deshalb von experimentellem Interesse, Trotzdem möchte ich hierbei interessante theoretische Fragestellungen nicht außer Acht lassen, die sieh beim Umgang mit agentenbasierten Modellen stellen: Wie kann es sein, dass einfache Agen- tenprogramme auf einmal zur Kooperation fähig sind, ohne dass irgendwo eine derartige „Kooperationsstrategie“ implementiert wurde. Ich möchte nicht so weit wie Robert Axelrod [1, S, 21] gehen, der seinen Agenten Verhalten wie „nett sein“ oder „sieh Entschuldigen können“ zusprieht, aber man bekommt eine Ahnung, wie durch Interaktion aus einfachen Regeln komplexes Verhalten entstehen kann,
Hinweis zur Notation
Bei der Diskussion des Roth-Erev Modells weicht die Notation vom Rest der Arbeit ab, Marktmengen werden von mir, wie z.B. auch in [4], mit q bezeichnet, Roth und Erev benutzen aber, in ihrem Modell in [5] und [12], dieses q als Wert der Propensity, In dieser Arbeit wird ausschließlich in Kapitel 2,3, die Variable q für die Propensity im RE stehen, wobei sie dort meist in Abhängigkeit von der Periode t, für eine bestimmte Aktion k, in der Form qk(t) notiert wird. Wird eine Propensity in anderen Kapiteln mit q verwendet, weise ich extra darauf hin.
2 Computersimuliertes Lernen
Menschliches Verhalten abzubilden, ist Ziel eines Teilgebiets der Künstlichen Intelligenz, der sogenannten Agententheorie. Es wird, anders als in den Ingenieurwissenschaften üblich, kein Top-Down Ansatz verfolgt, sondern ein Bottom-Up, Dabei wird erwartet, dass sieh ein bestimmtes Ergebnis oder Verhalten auf Makroebene durch einfaches Design von autonom handelnden Subjekten, sogenannten Agenten, erzielt wird, Wooldridge und Jennings [18, S, 2] beschreiben die Haupteigensehaften von Agenten als:
- Autonomie: Agenten haben Kontrolle über ihre Aktionen und Zustände
- Soziale Fähigkeit: Agenten treten mit anderen Agenten in Interaktion
- Reaktivität: Agenten reagieren zeitnah auf ihre Umgebung
Diese einfachen Fähigkeiten reichen aus, um ein Verhalten zu entwickeln, dass von vielen Menschen als intelligent bezeichnet wird - wobei man bekanntlich keine genaue Definition von Intelligenz[1] geben kann. Lernen in der Art, dass versucht wird, Belohnungen zu wiederholen und Strafen zu meiden, ist als Ausdruck von Intelligenz allgemein akzeptiert [17, S, 1], Das als Reinforcement Learning (deutsch: Verstärkendes Lernen) bezeiehnete Lern-Modell aus der Psychologie und den Sozialwissensehaften, kann mit Hilfe der AgentenTheorie, als (agentenbasierter) Algorithmus implementiert werden. Wie in der Skinner-Box bekommt ein Agent Belohnungen, die optimales Verhalten verstärken sollen und wird somit konditioniert. Die wichtige Annahme dabei ist, dass durch diese Art von Lernen Agenten programmiert werden können, eine bestimmte Aufgabe zu lösen, ohne dass spezifziert wird, wie dies geschehen soll. Solche Agenten brauchen kein Modell über ihre Umgebung, Sie müssen nur lernfähig und mit obigen Eigenschaften ausgestattet sein. Nach der Agententheorie kann ein so programmierter Agent für verschiedene Probleme schnell gute Lösungen finden.
Ein Problem, dem der lernende Agent dabei gegenübersteht, ist, die Balance zwischen dem Weiterverfolgen bekannter, guter Strategien und dem bewussten Abweichen davon zu finden. Der Preis des Findens neuer Verhaltensweisen ist der entgangene Gewinn, der durch Verfolgen bekannter Strategien erreicht werden würde. In der Literatur (z.B. in [7], [13]) bezeichnet man dieses Dilemma als den Tradeoff zwischen Exploration vs. Exploitation. Wie noch beschrieben wird, verwenden die beiden von mir genauer betrachteten Modelle, unterschiedliche Ansätze für dieses Problem,
Im Wesentlichen werden zwei Arten zum Lösen von Reinforcement Learning Problemen unterschieden: Ein, als Genetische Programmierung bekannter Ansatz, um in großen Suchräumen optimale Strategien zu finden. Dies wurde von Axelrod zur Simulation seiner bekannten Tournaments [1, S, 17-20] verfolgt. Dabei nutzte er den Genetischen Algorithmus nach Holland, um zu zeigen, dass so Agenten programmiert werden können, die sich im wiederholten Gefangenendilemma optimal[2] verhalten. Der zweite Ansatz ist, statistische Techniken anzuwenden, um den Nutzen einer Aktion für bestimmte Umweltzustände zu schätzen. Diese letzte Methode soll im Weiteren genauer beschrieben werden.
2.1 Das Basismodell
Ein Agenwieteragiert mit seiner Umgebung, durch Wählen einer Aktion, Die Umgebung ändert sich aufgrund dieser Aktion und präsentiert dem Agenten so eine neue Situation, Einen guten Überblick über die Grundannahmen des Modells geben Kaelbling [7, S, 238-240] und mit vielen Beispielen auch Sutton und Barto [13, S, 52-59], Die Informationen, die dem Agenten aus der Umgebung zur Verfügung stehen, sind der Status der Umgebung und die Antwort der Umgebung auf seine letzte Aktion, Diese Informationen werden als Erfahrung bezeichnet und als numerische Werte präsentiert. Obwohl weder einfach noch unwichtig, ist es nicht Aufgabe des Modells, die Transformation von einem realen Umweltzustand in rechnerkompatible Werte zu beschreiben. Mit jedem Iterationsschritt beobachtet der Agent den Zustand
2.1 Das Basismoddl
Aktion
s der Umgebung. Er wählt eine bestimmte Aktion a, die die Umgebung in einen neuen Zustand s' versetzt. Der Wert dieser Zustandsänderung wird dem Agenten numeriseli als Signal r mitgeteilt und als Verstärker oder Belohnung bezeiehnet. Die Eigensehaften des Modells aus [7, S. 239] sind:
- eine diskrete Menge von Umweltzuständen S
- eine diskrete Menge von Aktionen A und
- eine Menge von skalaren Belohnungssignalen r
In [7, S. 239] wird ein kleiner beispielhafter Interaktionsverlaufs aus Sieht eines solehen Agenten besehrieben. Diesen möchte ich nutzen, um wichtige Annahmen und Begriffe des Modells zu erläutern.
1: Umgebung: Du bist in Zustand 11, Du hast 4 mögliche. Aktionen Agent: ich wähle Aktion 1
2: Umgebung: Du erhälst ein Verstärkungssignal von r = 7, Du bist jetzt in Zustand 22, Du hast 4 mögliche Aktionen Agent: ich wähle Aktion 3
3: Umgebung: Du erhälst ein Verstärkungssignal von r = —3, Du bist jetzt in Zustand 11, Du hast 4 mögliche Aktionen Agent: ich wähle Aktion 1
4: Umgebung: Du erhälst ein Verstärkungssignal von r = 5, Du bist jetzt in Zustand 33, Du hast 4 mögliche Aktionen
Die Aufgabe des Agenten ist es nun, durch Verfolgung eines Verhaltens[3], eine auf Dauer ausgeriehtete Maximierung der Summe der Verstärkungssignale zu erzielen. Der Agent versucht in Periode t eine Aktion at so zu wählen, dass die abdiskontierte erwartete zukünftige Summe der Belohnungen Rt maximiert (vgl. [13, S, 57-58]) wird, wobei:
Abbildung in dieser Leseprobe nicht enthalten
Für eine Diskontrate [Abbildung in dieser Leseprobe nicht enthalten]1 hat diese unendliche Summe einen endlichen Wert, solange r auch endlich ist. Wenn ein Agent lernt, sollten in unserem Beispiel die Werte r immer öfter positiv werden und dabei anwaehsen.
2.2 Q-Learning
Gibt es eine endliche Anzahl an Umweltzuständen S und eine endliche Zahl von Aktionen A, um von einem Zustand in einen anderen zu wechseln, so faßt man Reinforcement Learning als einen Markoff-Entseheidungsprozess (engl, Markov-Decision-Process, MDP) auf. Diese Prozesse basieren auf der Theorie von Markoff-Ketten[4], und unterstellen immer die Markoff-Eigensehaft[5], Darüber hinaus bezeichnen sie Umwelten als stationär, wenn sieh die Wahrscheinlichkeiten eines Zustands Übergangs nicht ändern, sonst als dynamisch.
Mit dieser Theorie und einer Erweiterung des Basismodells (vgl. Kaelbling [7, S. 248]) um folgende Punkte:
- eine Belohnungsfunktion[Abbildung in dieser Leseprobe nicht enthalten] gibt uns einen skalaren Wert für den Fall in Zustand s die Aktion о zu wählen.
- eine Zustandsübergangsfunktion [Abbildung in dieser Leseprobe nicht enthalten] ist eine Wahrscheinlichkeitsverteilung im Zustand s über die Aktionen A. Die Funktion [Abbildung in dieser Leseprobe nicht enthalten] beschreibt die Wahrscheinlichkeit, in Zustand s einen Übergang zu Zustand s' durch Aktion о zu wählen.
hat man die Grundlage des Lernmodells von Reinforcement Learning. Die Zustandsübergangsfunktion wird als Policy π bezeichnet oder, spieltheore- tiseh, als Strategie. Spricht man davon, dass der Agent eine bestimmte Poliev verfolgt[6], so heißt das, dass der Agent für jeden Zustand Wahrscheinlichkeiten gespeichert hat, mit denen er seine Aktionen wählt. Prozesse mit diesen Eigenschaften sind schon lange bekannt und sind Grundlage für den im Weiteren entwickelten Lern-Algorithmus.
2.2.1 Lernmodell
Q-Learning basiert auf Markoff-Entseheidungsprozessen (MDP) und erweitert sie um die Aspekte unvollständiger Information und Approximation. In der Realität sind Zustandsübergangsfunktionen meist unbekannt. Agentenbasierte Modelle sind ein Ansatz, um mit diesem Informationsmangel umzugehen. Ein Agent soll eine Poliev finden, die seine Belohnung maximiert. Ihm bleibt nichts anderes übrig, als aus den Interaktionen mit der Umwelt, über die er nur rudimentäre Informationen in Form von s und r hat, eine initiale Poliev schrittweise zu verbessern. Alle Reinforeement-Algorithmen beruhen deswegen darauf, Werte zu schätzen, die quantifizieren, wie gut es ist, in einem zu Zustand sein oder eine Aktion in einem Zustand zu wählen. Dazu bedient sieh nach [13, S. 69] zweier wichtiger Messwerte:
Abbildung in dieser Leseprobe nicht enthalten
die den Wert eines Zustands s unter der Poliev π angibt. Es ist die abdiskontierte Summe der erwarteten Belohnungen, wenn im Zustand s gestartet wird und zukünftig immer Poliev π angewendet wird. Dies ist der (abdiskontierte) Erwartungswert der Belohnungen bei aktueller Wahrscheinlichkeitsverteilung 7r(s,o).
Die Aktionswertefunktion der Poliev π
Abbildung in dieser Leseprobe nicht enthalten
die den Wert einer Aktion [Abbildung in dieser Leseprobe nicht enthalten]im Zustand s unter der Poliev π angibt. Es ist die abdiskontierte Summe der erwarteten Belohnung, wenn im Zustand s gestartet wird, dort Aktion о gewählt und zukünftig immer Poliev π verfolgt wird. Im Idealfall hat der Agent nach t Perioden eine Poliev π* gelernt, die ihm erlaubt, in jedem Zustand die Aktion zu kennen, die die höchste Belohnung bringen wird. Es gelten dann folgende Aussagen:
- Der Agent spielt eine optimale Poliev π*, wenn für alle Zustände gilt:
Abbildung in dieser Leseprobe nicht enthalten
- Der Agent konvergiert gegen eine optimale Poliev π*, wenn gilt:
Abbildung in dieser Leseprobe nicht enthalten
Die Agententheorie konzentriert sieh darauf, Verfahren zu finden, die Werte I/1ľ(s) und Qw(s,a) durch wiederholte Interaktion schätzen und daraus die optimale Poliev π* finden, die für jeden Zustand und Aktion die höchste erwartet Belohnung erzeugt. Wie dies geschehen kann, wird im Folgenden dargestellt.
2.2.2 Primitives Lernen
Kann ein Agent die optimale Poliev π* finden, kann er sein Schicksal erfüllen und seine Belohnungen sind optimal. Dabei kann es mehr als eine beste Poliev geben, die die selben Zustandswerte erzeugen. Um dies anzuzeigen schreibt man U*(s) oder Q*(s,a).
Ein naiver Ansatz zur Berechnung von π* is, eine beliebigen Poliev π zu setzen, W(s) oder Q*(s,o) zu berechnen, dann die Poliev zu ändern und die Zustand -und Aktionswerte neu zu bestimmen. Mann kann dann verschiedene [Abbildung in dieser Leseprobe nicht enthalten] vergleichen und festellen, ob [Abbildung in dieser Leseprobe nicht enthalten] ist. Natürlich ist es hoffnungslos ineffizient, durch Trial and Error alle möglichen Kombinationen zu realisieren und die Ergebnisse zu vergleichen. Es muß also Wege geben, durch schrittweise Verbesserung, effizient eine optimale Poliev zu erlernen.
Es gibt verschiedene Methoden[7] einer schrittweisen Poliev-Optimierung, die versuchen, die Belohnungsfunktion und die Zustands Übergangsfunktion zu schätzen. Für einen agentenorientierten Ansatz sind sie deshalb ungeeignet, da sie zuviel Wissen über ihre Umgebung verlangen.
Konzentriert man sieh dagegen auf die Informationen, die vor dem W ählen einer Aktion zu Verfügung stehen (der Zustand s), und der Information, die nach der Aktion [Abbildung in dieser Leseprobe nicht enthalten] zur Verfügung steht (der Folgezustand s' und die Belohnung r), so beschreibt man ein einfaches Lernmodell. Watkins hat es als „Primitive Learning“ [13, Kap. 7, S. 81 ff.] eingeführt, es ist aber als Q-Learning in die Literatur eingegangen. Dabei handelt es sieh zunächst um eine Methode, die, wie andere Ansätze[8] auch, nach jeder Interaktion oder Episode von Interaktionen[9] die Zustandswerte V oder Aktionswerte Q schätzt. Normalerweise folgt der Agent bei diesen Sehätzmethoden seiner gerade aktuell geschätzten besten Poliev. Wie Watkins interessanterweise zeigt [17, S. 96], findet der Agent bei Q-Learning die optimale Poliev auch, ohne tatsächlich die beste Aktion a* zu spielen, Stattdessen wählt er andere Aktionen, um zu experimentieren. Deshalb bezeichnet man Q-Learning als exploration insensitiv [7, S, 254], Im Folgenden nutze ich die Notation und zitiere aus Kaelbling [7, S, 253 f,], Herleitung und Beweise der getroffenen Aussagen in Watkins [17, S, 81 ff, und Beweis Appendix I, S, 220 ff,].
In seiner einfachsten Form, dem one-step Q-Learning, schätzt die Aktionswert Q direkt Q* (siehe Kap, 2,2,1), Wiederholt der Agent, nach jeder Interakion mit der Umwelt[10] folgendes Update auf seine Q-Werte:
Abbildung in dieser Leseprobe nicht enthalten
dann konvergieren die Q-Werte[11] mit Wahrscheinlichkeit 1 zu Q*, wenn alle Zustände unendlich oft besucht werden und die Lernrate monoton abnimmt [17, Appendix S, 227],
Die Werte die ein Agent beobachten kann, sind s, o, r und s1. Der Wert a! ist die Aktion mit dem höchsten Q-Wert im Folgezustand und muss beim Update in der Q-Map gesucht werden. Da die Q-Werte Aktionswerte schätzen, ist die Differenz max[Abbildung in dieser Leseprobe nicht enthalten]nicht nur ein Zustandsvergleich, sondern vielmehr ein Wert, der angibt wie gut es ist, im Zustand s einer Aktion о zu folgen und im Folgezustand s' die beste Aktion zu spielen. Ist sie negativ, dann heißt das nichts anderes, als das man sieh selbst im besten Fall verschlechtert, wenn man [Abbildung in dieser Leseprobe nicht enthalten] in s spielt. Ist diese Differenz positiv, dann kann sieh der Agent verbessern, wenn er im Folgezustand auch dieser besten Aktion folgt. Der Agent bildet einen Wert für zukünftiges Optimalverhalten und 7 regelt seine Gewichtung zur Belohnung r innerhalb der Updateregel Der Pseudocode des vom Agenten implementierten Algorithmus wird nach [13, S, 149] im Folgenden angegeben:
Pseudocode für Q-Learning
1 Initialisiere alle Q-Werte
2 Wiederhole bis Abbruchkriterium
2.1 wähle Aktion а für den aktuellen Zustand s
2.2 beobachte r und s' als Reaktion auf а
2.3 update Q-Wert[12] nach Gleichung 8
Punkt 2,1 des Algorithmus definiert nicht, wie genau der Agent aus seinen Q-Werten die Aktion des nächsten Zugs bestimmt. Dies wird im nächsten Kapitel diskutiert,
2.2.3 Entscheidungen treffen
Beim Lernen ist es wichtig, dass der Agent anfangs viele verschiedene Aktionen probiert, später aber immer mehr dazuübergeht, von den gemachten Erfahrungen zu profitieren. Weder darf die Probierphase zu kurz sein, sonst werden superiore Aktionen nicht gefunden, noch darf sie zu lang sein, sonst werden durch unpassende Aktionen zu lange geringe Belohnungen eingefahren, Wie eingangs Kap, 2 geschildert, bezeichnet man dies in der Literatur als das Problem Exploration vs, Exploitation, Die zwei wichtigsten Methoden sind: 6-greedy Mit der Wahrscheinlichkeit von e wird die Aktion mit dem höchsten Q-Wert gespielt, während mit 1—6 gleichverteilt eine andere Aktion gezogen wird. Diese Methode ist einfach und reehenteehniseh nicht aufwendig, hat aber den Nachteil, dass sie mit gleicher Wahrscheinlichkeit auch die Aktionen wählt, die den zweitbesten aber auch den schlechtesten Q-Wert haben.
Softmax Die Wahrscheinlichkeit, eine Aktion о in Zustand s zu ziehen, wird durch eine Boltzmann-Verteilung abgebildet, die hohen Q-Werten auch hohe Wahrscheinlichkeiten nach folgender Gleichung zugeordnet:
Abbildung in dieser Leseprobe nicht enthalten
Naürlieh gilt die so erzeugte Wahrscheinlichkeitsverteilung, entsprechend der Q-Map, für jeweils nur einen Umweltzustand s. Wie stark sieh Unterschiede in den Q-Werten auf die Wahrscheinlichkeitsverteilung niedersehlagen, h ängt von einer Variable ab, die als Temperatur T bezeichnet wird. Für ihren Verlauf, abhängig von der Periode t, legt man [15, S, 21] eine Funktion der Art[Abbildung in dieser Leseprobe nicht enthalten]zugrunde, die sieh, von einer maximalen Temperatur T, abhängig von b asvpmtotiseh 0 annähert, Anfangs ist die Temperatur hoch und Unterschiede in den Q-Werten werden zu einer Gleich Verteilung hin nivelliert. Im weiteren Verlauf kühlt sie immer weiter ab, die Struktur der Q-Werte drückt sieh immer stärker in der Wahrscheinlichkeitsverteilung aus, bis bei sehr niedrigen Temperaturen Unterschiede sogar verstärkt abgebildet werden.
Beim Q-Lerning bedient man sieh normalerweise der Softmax-Methode, weil sie geeignet ist (vgl, [13, S, 30]) auch zwischen der schlechtesten und der zweitbesten Aktion zu unterscheiden. Leider ist sie rechenintensiver und macht den Algorithmus daher langsamer, denn für jede Periode muß die Summe über eine Exponentialfunktion mit zeitintensiven Fließkommazahlen berechnet werden.
In Abbildung 2 wurde für 36 Q-Werte eine einfache Dreieeksfunktion zugrunde gelegt, d.h, bis zu Index 18 steigen die Q-Werte um jeweils eine Einheit, um dann genauso zu fallen. Zu sehen ist die Entwicklung der Wahrscheinlichkeiten für diese Q-Werte in 20 Perioden, für eine Temperatur, die von 80 Grad asymptotisch zu 0 fällt. Bei hohen Temperaturen (T > 50) handelt es sieh fast noch um eine Gleichverteilung, die Charakteristik der Dreieeksfunktion deutet sieh nur leicht an. Der Agent wird hier also noch viel experimentieren, da selbst hohe Q-Werte nicht zu einer wesentlich höheren Wahrscheinlichkeit führen. Mit weiterem Erkalten treten die Eigenschaften der zugrundeliegenden Funktion immer stärker in den Vordergrund, Der Agent wird jetzt immer stärker seine Erfahrungen ausnutzen und kaum noch Aktionen wählen,
Abbildung in dieser Leseprobe nicht enthalten
Wirkung der Boltzmann-Statistik auf eine Dreiecksfunktion, wobei die Temperatur asymptotisch zu 0 fallt,. die wenig belohnt wurden. Am Ende wird fast nur noch die beste Aktion (höchster Q-Wert bei 18) gespielt. Dabei bestimmt aber im wesentlichen das Verhältnis [Abbildung in dieser Leseprobe nicht enthalten] wann der Agent von Exploration zu Exploitation übergeht, d.h, bei niedrigen Q-Werten muß die Temperatur stärker fallen. Für realistische Anwendungen ist die Anzahl der Spielperioden zu beachten. Die Temperaturfunktion kann schon nach wenigen hundert Runden nahe 0 sein, und der Agent ist kaum noch experimentierbereit. Die Basis b für die von mir untersuchten Q-Learning Simulationen des Cournot-Spiels befindet sieh meist im Bereich[Abbildung in dieser Leseprobe nicht enthalten] da mehrere hunderttausend Runden lang gespielt wird. Hier muss Wissen aus der Umwelt als genaue Wahl des Parameters einfließen, denn man muß wissen, wie hoch r erwartet werden kann und wie oft eine Aktion besucht werden muß, damit sie hoch genug ist, um beim Erkalten nicht Zufallstreffer der ersten Runden zu verstärken.
Im Verlauf dieser Arbeit verwende ich den Begriff eines charakterisierenden Bereichs der Temperaturfunktion für diejenige Temperatur T, die so stark gefallen ist, das Unterschiede in den Q-Werten zu solchen Veränderungen der Wahrscheinlichkeiten führen, dass der höchste Q-Werte einer Situation s mit einer Wahrscheinlichkeit [Abbildung in dieser Leseprobe nicht enthalten]gespielt wird. Dies soll den Übergang markieren, bei dem von Exploration zu Exploitation gewechselt wird.
2.2.4 Parameter
Zusammenfassend möchte ich nochmal die Parameter des Q-Learnings auflisten, die bei der eigentlichen Simulation genauer untersucht werden sollen,
Lernrate In (3) gibt die Lernrate а an, wie stark neue Werte in den aktuellen Q-Wert eingehen, Werte von [Abbildung in dieser Leseprobe nicht enthalten] geben dem alten Q-Wert ein hohes Gewicht - der Agent ist sozusagen konservativ, während bei [Abbildung in dieser Leseprobe nicht enthalten] aussehließlieh neu gemachte den Q-Wert bestimmen,
Weitsichtigkeit in (3) definiert j, wie stark der zukünftig maximal erzielbare Q-Wert in die Neuschätzung von Q eingeht. Ist er groß [Abbildung in dieser Leseprobe nicht enthalten] so geht dieser zukünftige Q-Wert gleichgewichtet mit der aktuellen Belohnung [Abbildung in dieser Leseprobe nicht enthalten] ein, und man bezeichnet den Agenten als weitsichtig[15, S, 16], Ist[Abbildung in dieser Leseprobe nicht enthalten]so geht nur die aktuelle Belohnung in die Neuschätzung von Q ein - der Agent ist kurzsichtig,
Temperatur Für das Aussehen der Wahrscheinlichkeitsverteilung über die möglichen Aktionen o im Zustand s ist die Temperatur maßgeblich. Ist sie extrem hoch, wirkt sie nivillierend, und sie ähnelt einer Gleichverteilung, d.h. Unterschiede in den Q-Werten drücken sieh kaum in den Wahrscheinlichkeiten aus. Je weiter sie sinkt, desto stärker schlagen sieh diese unterschiedlichen Q-Werte auch in unterschiedlichen Wahrscheinlichkeiten nieder, bis sie für Temperaturen um den Gefrierpunkt sogar Unterschiede verstärkt. Der Parameter [Abbildung in dieser Leseprobe nicht enthalten] gibt dabei an, wie hoch die Starttemperatur ist. Wie schnell sie sinkt, wird von[Abbildung in dieser Leseprobe nicht enthalten]bestimmt,
2.3 Roth-Erev Methode
Eine intuitive Methode, Reinforcement Learning für wiederholte Spiele zu modellieren, wurde von Roth und Erev in zwei Veröffentlichungen [5] und [12] vorgestellt. Dabei bedienen sie sieh im Wesentlichen der experimentellen Ergebnisse der Psychologie der letzten Jahrzehnte, Vor allem sollen folgende Zusammenhänge[12, S, 171] abgebildet werden:
- The Law of Effect - die Wahrscheinlichkeit, eine einmal hoch belohnte Aktion zu wählen, soll steigen
- Power Law of Practice - gemachte Erfahrungen wiegen schwerer als neue
Bei der folgenden Diskussion halte ich mich an die Notation von Roth und Erev, die sieh von der des Q-Learning unterscheidet. Die Werte werden abhängig von der Periode t notiert und Aktionen werden mit к indiziert. Außerdem steht q hier nicht für Marktmengen, sondern für den Wert gemachter Erfahrungen, der im Weiteren erklärt wird.
[...]
[1] Touring gibt in dem nach ihm benannten Test an, dass ein Programm intelligent ist, wenn ein Mensch nicht unterscheiden kann, ob er mit einem Copmuterprogramm interagiert oder mit einem Menschen.
[2] Im Wesentlichen konnte er zeigen, dass auch seine Agenten Strategien entwickelten, die vergleichbar mit einer Tit-For-Tat Strategie waren.
[3] Im Sinne von Regeln, die definieren, wie Umweltzustände und Aktionen zugeordnet werden
[4] Siehe dazu [S. 60 ff.] in Leiner, B. (1995) „Grundlagen statistischer Methoden“, Oldenbourg Verlag München
[5] Die aktuelle Übergangswahrscheinlichkeit ist ausschließlich abhängig vom letzten Zustand. Für MDP heißt das formal, dass sich die Gleichung für die Übergangswahrscheinlichkeit von Zustand s auf s’ von[Abbildung in dieser Leseprobe nicht enthalten] zu [Abbildung in dieser Leseprobe nicht enthalten] verkürzt.
[6] Oft werden Agenten, die eine bestimmte Policy anwenden, mit Adjektiven beschrieben. So gibt es z.B. den „netten“ Agenten, weil er mit hoher Wahrscheinlichkeit Aktionen wählt, die als Kooperation gedeutet werden können.
[7] In [13, Kap. 4, 5 und 6, S. 89 ff.] beschreiben Sutton und Barto [13, Kap. 4, 5 und 6, S. 89 ff.] die Dynamische Programmierung und einen als Value Iteration bezeichneten Algorithmus.
[8] Sutton und Barto beschreiben in [13, Kap. 6] z.B. eine solche Methode, die als Temporal-Difference Learning bezeichnet wird.
[9] Die Monte Carlo Methoden [13, Kap. 5, S. 111] schätzen erst am Ende einer Interaktion oder am Ende einer bestimmten Anzahl von Interaktionen.
[10] Die getroffenen Aussagen gelten nur für Umwelten die als stationäre Markoff-Ketten aufgefaßt werden.
[11] Manche Autoren benutzen die Notation Q, um anzudeuten, dass es sich um Schätzwerte handelt.
[12] Abbildung 13 im Anhang zeigt eine konkrete Implementierung von Update-Q.
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.