Cultaptation – Das Ergebnis und ein Beispiel

Cultaptation – Das Ergebnis und ein Beispiel

von Günther Rosenbaum

Lange hat es gedauert – doch mittlerweile ist die Gewinnerstrategie des Cultaptation Wettbewerbs
ermittelt worden und die Autoren haben ihren Preis auf der EHBEA 2009 conference in St Andrews
entgegengenommen. Die Strategie “Discountmachine” der Autoren Dan Cownden und Tim
Lillicrap hat mit gutem Abstand gegenüber den Konkurrenten gewonnen.

Zitat[1]:

“There are a number of ways in which this strategy stands out and that may have contributed
to its success. The first is that it attempts to characterise the environment in a highly
comprehensive way, extracting a lot of information from its prior experiences, and is responsive to
that information. The second is that this strategy explicitly makes decisions based on expected
lifetime outcomes, rather than immediate payoff benefits. Finally, the strategy is noteworthy for
the sophistication of the mathematics it uses to calculate expected payoffs.“

Manche Dinge in diesem Wettbewerb scheinen auf der Hand zu liegen – denn jedem ist es irgendwie
klar, dass das Kopieren einer “guten” Aktion (leider kopiert man aber nicht immer nur
gute Aktionen) einfacher ist als das Finden einer guten Strategie durch wiederholte Trial &
Error Versuche.

Dazu noch ein weiteres, etwas längeres Zitat aus den Wettbewerbsregeln[2], welches den Stand der
aktuellen Forschungen wiedergibt; ich möchte jedem empfehlen, diesen Absatz vorab und in Ruhe
durchzulesen:

“It is commonly assumed that social learning is inherently worthwhile. Individuals are
deemed to benefit by copying because they take a short cut to acquiring adaptive information,
saving themselves the costs of asocial (e.g. trial-and-error) learning. Copying, it is assumed, has
the advantage that individuals do not need to re-invent technology, devise novel solutions, or
evaluate environments for themselves. Intuitive though this argument may be, it is flawed (Boyd
& Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Giraldeau et al. 2003). Copying
others per se is not a recipe for success. This is easy to understand if social learning is
regarded as a form of parasitism on information (Giraldeau et al. 2003): asocial learners are
information producers, while social learners are information scroungers. Game-theoretical models of
producer-scrounger interactions reveal that scroungers do better than producers only when fellow
scroungers are rare, while at equilibrium their payoffs are equal (Barnard & Sibly 1981).
Similarly, theoretical analyses of the evolution of social learning in a changing environment (e.g.
Boyd & Richerson 1985; Boyd & Richerson 1995; Rogers 1988; Feldman et al. 1996) reveal that
social learners have higher fitness than asocial learners when copying is rare, because most
‘demonstrators’ are asocial learners who will have sampled accurate information about the
environment at some cost. As the frequency of social learning increases, the value of copying
declines, because the proportion of asocial learners producing reliable information appropriate to
the observer is decreasing. An equilibrium is reached with a mixture of social and asocial learning
(Enquist et al. 2007). These mathematical analyses, together with more conceptual theory (e.g.
Galef 1995), imply that copying others indiscriminately is not adaptive; rather, individuals must
use social learning selectively, and learn asocially some of the time. Natural selection in animals
capable of social learning ought to have fashioned specific adaptive social learning strategies
that dictate the circumstances under which individuals will exploit information provided by others
(Boyd & Richerson 1985; Henrich & McElreath 2003; Laland 2004; Schlag 1998). At present, it
is not clear which social learning strategy, if any, is best. The tournament has been set up to
address this question.“

Es galt also eine Strategie zu finden, die

• den optimalen Zeitpunkt und die optimale Häufigkeit von sozialem Lernen (Observe) nutzt,
• die gelernten und ausgeführten Aktionen der Vergangenheit analysiert und daraus
  Schlussfolgerungen für die Zukunft zieht,
• bei Bedarf auch gelegentlich asoziales (Innovate) Lernen nutzt.

Bevor ich aber die Ergebnisse noch etwas detaillierter betrachte, möchte ich meine eigene
Strategie etwas erläutern; wer möchte, kann sich auch den Java und Mathlab Code im Detail
anschauen[5].

In der paarweisen Simulation (nur die betrachte ich hier) treten jeweils 2 gegnerische
Strategien über 10000 Runden gegeneinander an – die besser an die Umgebung angepasste Strategie
wird sich dabei häufiger vermehren und den Gegner in seine Schranken verweisen! (Für den genauen
Ablauf der Simulationen siehe [2])

Jede Strategie hat folgende 3 Aktionsmöglichkeiten in jeder Runde:

1. EXPLOIT (benutzen)Dies ist die wichtigste und vermutlich häufigste aller Aktionen.
   
   Indem ich eine in einer früheren Runde gelernte Aktion meines Repertoires benutze, erhalte ich
   einen Ertrag und stärke damit meine Fitness (wenn der Ertrag genügend hoch ist) … und bei höherer
   Fitness ist meine Fortpflanzungsrate höher.
2. OBSERVE (nachahmen, kopieren, soziales Lernen)
   
   Bei Observe lerne ich eine der Aktionen, die ein zufällig ausgewählter Simulationsteilnehmer in der
   Vorrunde ausgeführt hatte. Wenn ich davon ausgehe, dass dessen Strategie eine ertragreiche Aktion
   gewählt hatte und ich diese Aktion noch nicht kannte, dann habe ich jetzt auch eine gute Aktion in
   meinem Repertoire.
   
   Leider (oder vielleicht glücklicherweise) ist das Abschauen auch fehlerbehaftet; der Ertrag ist
   etwas verfälscht und manchmal geht das Abkupfern völlig in die Hose – ich erhalte dann eine
   zufällige Aktion (ähnlich zu Innovate!).
   
   In der zweiten Stufe des Wettbewerbes war es auch möglich, dass ein OBSERVE nicht nur eine Aktion
   erlernt, sondern bis zu 6 Aktionen!
3. INNOVATE (Trial&Error, asoziales Lernen)
   
   Hierbei erlerne ich zufällig eine der 100 Aktionen (inklusive des Ertrages) der
   Simulationsumgebung. Dies kann eine gute, schlechte oder sogar schon bekannte Aktion sein. Die
   Erträge einer gelernten Aktion ändern sich über die Zeit mit einer festen, aber unbekannten
   Wahrscheinlichkeit.

Dummerweise weiß ich auch nicht im voraus, welche Werte die Erträge annehmen können – ist 20
schon ein hoher Ertrag oder erst 150? Eine Aktion, die momentan 50 bringt, kann in wenigen Runden
nur noch 0 wert sein – denn diese Erträge sind Zufallsvariablen.

Eine vermutlich gute Aktion werde ich häufig so lange benutzen (Exploit), bis sich plötzlich der
Ertrag verändert: Man beachte, dass man in diesem Fall wieder so etwas wie ein Innovate ausführt –
die Aktion erhält einen neuen, zufälligen Ertragswert!

Mehrere unabhängige Wahrscheinlichkeitsverteilungen beeinflussen die Umwelt während einer
Simulationsreihe; diese Verteilungen werden vor einem Durchgang fixiert und ändern sich dann für
eine ganze Testreihe nicht mehr (ein Individuum kann also während seiner Lebenszeit von
durchschnittlich 50 Jahren diese Parameter zu schätzen versuchen). Dummerweise kannte man vor dem
Wettbewerb nur einige grobe Eckwerte dieser Parameter – einige Dinge sind auch im Nachhinein noch
nicht komplett offengelegt.

Jedes Individuum innerhalb der Simulation hat jede Runde (aber unabhängig vom Alter!) eine
Sterbewahrscheinlichkeit von 2%. – stirbt jemand, so sofort wieder ein Kind geboren. Um die
Strategie des Kindes festzulegen, wird ein “Vorfahre” aus allen 100 Individuen (eigene
und gegnerische) zufällig gewählt – wobei die Auswahlwahrscheinlichkeit proportional zur Fitness
(durchschnittlicher Ertrag pro Runde) gewählt wird. Zusätzlich tritt mit 2% Wahrscheinlichkeit noch
eine Mutation auf, bei der der Nachfolger eine gegnerische Strategie nutzt.

Jedes Individuum hat nur die Informationen aller gelernten oder ausgeführten Aktionen seit
seiner Geburt als Entscheidungskriterium für seinen nächsten Zug zur Verfügung: Wie würdet ihr
jetzt eine gute Strategie formulieren, die möglichst fit ist, um sich gut fortzupflanzen und die
sich gegen die Mutanten erfolgreich wehrt?

Aufgrund der vielen Unbekannten dreht man sich da immer wieder im Kreis…

Meine Strategie “StabilityObserver” habe ich dann folgendermaßen festgelegt:

• Um immer etwa 2% Innovationen (und damit “frisches Blut”) im eigenen Volk zu haben,
  wurde in der ersten Runde eines jeden Individuums immer INNOVATE ausgeführt.(Natürlich muss man
  nicht selbst Innovate ausführen – es genügt auch, dass gegnerische Individuen dies tun und man dies
  dann kopiert). Die zweite und dritte Runde bestanden dann aus OBSERVE und EXPLOIT.
• Die Strategie schätzt die Stabilität ihrer Umgebung (payoff mutation rate), indem sie
  berechnet, wie lange die ausgeführten Aktionen in ihrer Vergangenheit ihren Ertrag nicht gewechselt
  haben. Der Mittelwert hiervon ist in etwa der Kehrwert der payoff mutation rate.
• Wenn die Stabilität der Umgebung gering ist (die Erträge bleiben nur kurze Zeit stabil), dann
  macht es keinen Sinn Zeit zu verschwenden und immer wieder etwas Neues zu lernen. In diesem Fall
  sollten die vorhandenen Aktionen einfach benutzt werden (und seltener gelernt werden).
• Ist die Stabilität der Umgebung sehr hoch, so wechseln die Erträge der Aktionen nur sehr
  selten. Um zu vermeiden, dass wir eine ungünstige Aktion zu lange benutzen, wird jede 10te Runde
  ein OBSERVE eingeschoben – ansonsten wird die beste bekannte Aktion mit EXPLOIT benutzt.
• Bei mittlerer Stabilität wird immer dann ein OBSERVE eingeschoben, wenn der Ertrag der aktuell
  ausgeübten Aktion unterhalb des oberen Quartils aller bisher in der eigenen Lebensdauer gesehenen
  Erträge rutscht. Nach einem OBSERVE kommt aber immer erst ein EXPLOIT.
• Die Umsetzung dieser Vorgaben ins Programm geschah eher qualitativ – die echten Zahlenwerte für
  die Begriffe/Parameter in der obigen Beschreibung habe ich dann durch Testsimulationen heuristisch
  bestimmt(wobei die Bereiche gleitend ineinander übergehen).

Warum heißt die Strategie “StabilityObserver”? Nun, weil sie einerseits die Stabilität
ihrer Umwelt “beobachtet” und andererseits fast ausschließlich durch “OBSERVE”
lernt!

Einen Link auf die eingereichten Wettbewerbsunterlagen mit Java-Code sowie die Umsetzung auf
Matlab-Code findet Ihr am Ende dieses Berichtes [5].

Nun, diese Strategie hat es nur (immerhin?) bis auf Platz 11 von 104 Einsendungen geschafft.
Aber wie sah die Strategie des Siegers “Discountmachine” aus?

Hier eine grobe Beschreibung der Siegstrategie; Zitat[ 1]:

Our creature does three major things:

First it estimates/calculates, what we believe to be all the
pertinent parameters of the simulation as well as a few other quantities that we believe to be
useful. These are P_c, the mean of the payoff distribution, the mean of of the observed values, the
correlation between observe and exploit values of the same action, N_observe, and where applicable
the number of data points used to make these estimates.

Second it uses some of these parameters to estimate the expected
payoff for performing each action in its repertoire. Once it has a best exploit chosen from its
repertoire it compares the value of Exploiting to the value of Observing using a geometric
discounting scheme based on our estimate of P_c and the given probability of death.

Lastly a machine learned function, takes into account N_observe and
the estimates on the reliability of observing and P_c to adjust the value of Observing accordingly.
Our creature then chooses whichever action has the higher perceived value, Observing or Exploiting.
As a side note our creature only Innovates when it has an empty repertoire and observe doesn’t
work, which typically is only on the first turn of a simulation.

Worin liegt nun der Unterschied zu meiner Strategie?

So wie es aussieht, werden hier wohl die verschiedenen variablen Parameter der Umwelt recht
genau geschätzt (ich habe nur einen einzigen Parameter grob geschätzt).

Anschließend versucht man, die erwarteten zukünftigen Erträge einer EXPLOIT und einer OBSERVE
Aktion abzuschätzen.

Ein vereinfachtes Beispiel:

Gehen wir von einer recht variablen Umgebung aus, in welcher Aktionen im Mittel nur etwa 5
Runden stabil sind. Führe ich nun z.B. 5-mal eine Aktion mit dem Ertrag 100 aus, so habe ich hier
also eine Fitness von 500/5 = 100.

Führe ich aber zuerst ein OBSERVE (hat immer Ertrag 0) durch und lerne tatsächlich eine bessere
Aktion mit Ertrag 110, so erhalte ich eine Fitness von 0+110+110+110+110+110/6 = 550/6 = ca. 92.
OBSERVE wäre hier also die schlechtere Alternative!

Hat man also gute Schätzwerte der Parameter, so kann man recht gute Entscheidungen treffen (wohl
noch unterstützt durch entsprechende Abzinsung der zukünftigen Erträge).

Bei mir ist das ungenauer, mehr auf qualitativer denn auf quantitativer Weise geschehen. Zu
guter Letzt habe ich die vermeintlich geringen Effekte der “Kopierfehler” einfach
ignoriert.

Eine extrem vereinfachte Form des Wettbewerbes (kein OBSERVE, stabile Umgebung,
Verteilungsfamilie der Aktionswerte bekannt, etc. …) wurde in [3] nach dem Wettbewerb
mathematisch analysiert: Als Kind lernen (INNOVATE), mit mathematischen Methoden den optimalen
Stoppzeitpunkt für den Abbruch des Lernens bestimmen und dann bis zum Lebensende arbeiten (EXPLOIT)
… das ist dort die traurige Wahrheit für ein optimales Individuum!

Einen solchen optimalen “Smart Innovator” habe ich in der eigenen Simulationsumgebung
bei stabiler Umgebung gegen den StabilityObserver antreten lassen: Es ist wohl klar, dass der Smart
Innovator ohne “Observe” keine Chance gegen den StabilityObserver hatte!

In [7] wird der Ansatz des Smart Innovators nochmal etwas modifiziert: Will man die
Fortpflanzungswahrscheinlichkeit optimieren, so muss man manchmal schon als Kind EXPLOIT nutzen.
Tja, kommt man etwas näher an die realen Wettbewerbsbedingungen, so wird es auch schon wieder etwas
komplizierter… Des weiteren muss man beachten, dass “einfache” optimale
Strategien/Nash-Gleichgewichte auch nur einen garantierten Ertrag gegen jeden Gegner garantieren –
bei Wettbewerben muss man allerdings auch und gerade schwache Gegner möglichst hoch besiegen um
eine hohe Gesamtpunktzahl zu erreichen.

Interessant und überraschend war die Strategie des Zweitplazierten “Intergeneration”.
Zitat[1]:

“My main idea is (although it seems not be as good as I expected) that an important
information for the young is, how much is the “good” payoff (with how much I can be
happy). If I have so much or more, I would just EXPLOIT until it changes, otherwise I would 8 times
exploit and once observe.

The important trial is that the old could “say” something
to the young, by “signaling” something to the young. The signal consists of doing an act
whose number is divisible by 8. If the fraction is 1,2,3,4 this means that “payoff 8 is very
good”, 5,6,7,8 means “payoff 20 is very good” and 9,10,11,12 means “payoff 40
is very good”.

If the old does not have this in his repertoire, he innovates. If he has more than one of
these 4 possible “symbol” acts, he uses that with highest payoff — because it is a
higher chance that this will diffuse. Even the “opponent” can help spread out this
signal, without knowing that. “

Huch! Das sieht ja so aus, als wollte da jemand schummeln, denn laut Regeln gibt es eigentlich
keinen Kontakt und Informationsaustausch zwischen verschiedenen Individuen! Luke Rendell, einer der
Organisatoren des Wettbewerbes sagt dazu:

“We thought about whether it was cheating or not but decided to let it go. I am
investigating the properties of this strategy in more detail right now. I think that the
‘signalling’ part of the strategy made very little difference … “

Intergeneration war wohl aber auch der einzige Teilnehmer, der etwas grenzwertige Methoden
benutzte – alle anderen haben sich nicht nur dem Worte sondern auch dem Sinne nach an die Regeln
gehalten.

Es wird sicherlich auch noch eine wissenschaftliche Auswertung der besten Strategien geben – da
bin ich schon drauf gespannt (z.B. [6]); auch die Organisatoren werden hierzu noch Informationen
veröffentlichen (aber im Moment noch nicht verfügbar)!

Die besten Strategien in diesem Wettbewerb waren sicherlich nicht so elegant und allgemein
verständlich wie damals die “Tit for Tat” Strategie im Wettbewerb von Axelrod; viele
Teilnehmer haben zulässige mathematische Methoden benutzt – dies hat natürlich nichts mit Mogeln zu
tun und ist auch bei vielen anderen Spielanalysen und Strategien notwendig!

Möglicherweise könnte es auch einen Folgewettbewerb geben… zumindest klang das so aus einem
Nebensatz in einer Mail von Luke Rendell heraus.

Lassen wir uns überraschen!

Günther Rosenbaum

[1] Social Learning Strategies Tournament

Details of Stage II and Final Results

Luke Rendell and Kevin Laland, University of St Andrews

January 5, 2009

Details of Stage I Results

Luke Rendell and Kevin Laland, University of St Andrews

November 26, 2008

[2] Social Learning Strategies Tournament

Rules for entry

Kevin Laland and Luke Rendell, University of St Andrews

4th January 2008

[3]When
Innovation Matters: An Analysis of Innovation in a Social Learning Game

Ryan Carr, Eric Raboin, Austin Parker, Dana Nau ICCCD 2008 Proceedings

[4]Evolution of social learning does not explain the origin of human cumulative culture

Magnus Enquist, Stefano Ghirlanda, 2006

[5] StabilityObserver (Java) – (Matlab)

[6] Within Epsilon of Optimal Play in the Cultaptation Social Learning Game

Ryan Carr, Eric Raboin, Austin Parker, and Dana Nau (Short Paper)

AAMAS 2009.

[7] Balancing
Innovation and Exploitation in a Social Learning Game

Eric Raboin, Ryan Carr, Austin Parker, Dana Nau, 2008