Reinforcement Learning im Cournot Duopol

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 Lernal­gorithmen 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 Christo­pher J.C.H, Watkins [17, S, 95 ff,]. Letztere ist als Q-Learning in die Lite­ratur eingegangen, erstere werde ich im Folgenden kurz als RE bezeichnen. Diese Implementierungen werden in die Modellwelt des bekannten Cournot­Spiels 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 Parametrisie­rung der beiden verschiedenen Implementierungen erörtert. Es sind Arbeiten bekannt, in denen Agenten, die Q-Learning anwenden, kooperierendes Ver­halten 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 Ergeb­nisse bekannt, die darauf hindeuten, dass Agenten kooperieren. Es ist Ziel dieser Arbeit, die Unterschiede zwischen RE und Q-Learning herauszuarbei­ten, 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 Ergeb­nisse von Simulationsläufen beschrieben, die für RE und Q-Learning weite Parameterbereiehe automatisiert testen. Im letzten Kapitel wird eine theo­retische 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 Pa­rametrisierungen für Reinforcement Learning dargestellt. Die Arbeit ist des­halb 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 ei­ne 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 be­kommt 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 bezeich­net, 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 In­genieurwissenschaften ü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 Reinforce­ment Learning (deutsch: Verstärkendes Lernen) bezeiehnete Lern-Modell aus der Psychologie und den Sozialwissensehaften, kann mit Hilfe der Agenten­Theorie, 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 ge­schehen 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 Pro­bleme 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 bewuss­ten Abweichen davon zu finden. Der Preis des Findens neuer Verhaltenswei­sen 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 wur­de 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 wieder­holten Gefangenendilemma optimal^[2] verhalten. Der zweite Ansatz ist, sta­tistische 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 Agen­ten 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 wer­den als Erfahrung bezeichnet und als numerische Werte präsentiert. Obwohl weder einfach noch unwichtig, ist es nicht Aufgabe des Modells, die Trans­formation 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 Theo­rie von Markoff-Ketten^[4], und unterstellen immer die Markoff-Eigensehaft^[5], Darüber hinaus bezeichnen sie Umwelten als stationär, wenn sieh die Wahr­scheinlichkeiten 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 Wahr­scheinlichkeitsverteilung im Zustand s über die Aktionen A. Die Funk­tion [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 Wahrscheinlichkei­ten gespeichert hat, mit denen er seine Aktionen wählt. Prozesse mit diesen Eigenschaften sind schon lange bekannt und sind Grundlage für den im Wei­teren entwickelten Lern-Algorithmus.

2.2.1 Lernmodell

Q-Learning basiert auf Markoff-Entseheidungsprozessen (MDP) und erwei­tert sie um die Aspekte unvollständiger Information und Approximation. In der Realität sind Zustandsübergangsfunktionen meist unbekannt. Agenten­basierte Modelle sind ein Ansatz, um mit diesem Informationsmangel umzu­gehen. 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 ei­nem 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 abdiskon­tierte 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 set­zen, W(s) oder Q*(s,o) zu berechnen, dann die Poliev zu ändern und die Zustand -und Aktionswerte neu zu bestimmen. Mann kann dann verschiede­ne [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 schritt­weise 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 Beloh­nung r), so beschreibt man ein einfaches Lernmodell. Watkins hat es als „Pri­mitive 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 Me­thode, die, wie andere Ansätze^[8] auch, nach jeder Interaktion oder Episode von Interaktionen^[9] die Zustandswerte V oder Aktionswerte Q schätzt. Nor­malerweise 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 insen­sitiv [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 Upda­te 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 ver­schlechtert, 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 Akti­on 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 Ak­tionen 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 eingefah­ren, 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öchs­ten Q-Wert gespielt, während mit 1—6 gleichverteilt eine andere Aktion gezo­gen 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 Ver­lauf, 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 Un­terschiede 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 wer­den.

Beim Q-Lerning bedient man sieh normalerweise der Softmax-Methode, weil sie geeignet ist (vgl, [13, S, 30]) auch zwischen der schlechtesten und der zweit­besten 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 berech­net werden.

In Abbildung 2 wurde für 36 Q-Werte eine einfache Dreieeksfunktion zugrun­de 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 Wahrscheinlich­keiten 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 zugrundeliegen­den Funktion immer stärker in den Vordergrund, Der Agent wird jetzt im­mer 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 rea­listische 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 gewech­selt wird.

2.2.4 Parameter

Zusammenfassend möchte ich nochmal die Parameter des Q-Learnings auf­listen, die bei der eigentlichen Simulation genauer untersucht werden sollen,

Lernrate In (3) gibt die Lernrate а an, wie stark neue Werte in den ak­tuellen 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 erziel­bare 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 Wahrscheinlichkei­ten aus. Je weiter sie sinkt, desto stärker schlagen sieh diese unterschiedli­chen 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 ge­machter 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 intera­giert 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“, Ol­denbourg Verlag München

^[5] Die aktuelle Übergangswahrscheinlichkeit ist ausschließlich abhängig vom letzten Zu­stand. Für MDP heißt das formal, dass sich die Gleichung für die Übergangswahrscheinlich­keit 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ätz­werte handelt.

^[12] Abbildung 13 im Anhang zeigt eine konkrete Implementierung von Update-Q.