Vor einem halben Jahr habe ich das erste Mal die KI-Technologie Reinforcement Learning erwähnt – auf Deutsch: Bestärkendes Lernen.

Mittlerweile habe ich mich ein wenig tiefer eingearbeitet und ein kleines Beispiel programmiert, um auch ein besseres Gefühl für die Technologie zu gewinnen. Anhand dieses Mini-Progamms möchte ich Reinforcement Learning vorstellen.

Worum gehts?

Bei RL geht es im einfachsten Fall um einen Agenten, der die beste Strategie (Policy) ermittelt, um in einer Umgebung (Environment) ein Ziel (Goal-State) zu erreichen. Dabei kann er durch festgelegte Aktionen (Action) von einem Zustand (State) in den anderen wechseln, bis er letztlich den Goal-State erreicht.

Klingt noch ein wenig abstrakt. Nehmen wir ein einfaches Beispiel:
Wir haben eine Schachbrett ähnliche Fläche, in der sich ganz unten rechts (Feld „10,10“) der Agent befindet. Der Agent kann immer einen Schritt nach oben, unten, rechts oder links gehen. Er soll die beste Kombination von Schritten zum leuchtenden Ziel-Zustand (+) finden und dabei vermeiden in die schwarzen Löcher (-) zu fallen.

Wie kann Software das bewerkstelligen?

 

 

 

Da gibt es mehrere Wege. Wenn der Programmierer das Schachbrett genau kennt, wenn er weiß, wo gute und schlechte Ziel-Zustände liegen und er genau weiß, welche Aktionen was bewirken, dann kann man alle Aktionen als Baum aufeinanderfolgender Status darstellen. Beispielsweise:

Der Agent ist auf…

• A1, von hier kann ich nach:
  • A2, von hier kann ich nach:
    • A3, von hier kann ich nach…
    • B2, von hier kann ich nach…
  • B1, von hier kann ich nach:
    • B2, von hier …
    • C1, von hier …

In so einem Baum kann das Programm dann solange suchen, bis es den gewünschten Ziel-Zustand gefunden hat. Dabei merkt es sich den Weg dorthin (bspw. A1 -> A2 -> B2 -> …) und hat dann die Lösung.

Beim Reinforcement Learning (RL) geht man aber davon aus, dass man die Umgebung gar nicht so genau kennt, und vor allem: man kann nie sicher sein, dass eine Aktion immer in den gewünschten Zustand führt: Stellen wir uns vor, der Agent ist ein Roboter mit 4 Rädern, bei denen eines der linken Räder etwas klemmt. Wenn sich der Roboter entscheidet nach oben zu fahren, dann landet er unter Umständen gar nicht im oberen Feld, sondern im Feld links.

Planning and Learning under Uncertainty

Eine schöne technische Einführung bietet der Artificial Intelligence MOOC von Sebastian Thrun und Peter Norvig.

So funktioniert Reinforcement Learning

Der Agent kennt also nur seine Aktionen und muss einfach ausprobieren, mit welchen Aktionen er am besten zum Ziel kommt. Er fährt wild drauf los und erreicht irgendwann zufällig ein Ziel. Nehmen wir an, er bekommt 100 Punkte, wenn er das (+) Ziel erreicht und er ist von Feld rechts daneben (Feld „4,3“) ins Ziel gekommen.

Der Agent merkt sich dann für die letzte von ihm ausgeführte Aktion – bspw. nach links zu gehen – dass diese gar nicht so schlecht war. Bekommt er im (+) Ziel 100 Punkte, dann merkt er sich, für die Aktion „links“ im Feld „4,3“ bspw. 89,10 Punkte (warum der Wert so „krumm“ ist: siehe ganz unten).

Dann startet der Agent nochmal neu aus seinem Start-Feld „10,10“ und sucht wieder zufällig seinen Weg, bis er ins Ziel kommt. Trifft er dabei nochmal auf Feld „4,3“, dann merkt er sich, dass auch die Aktion, die ihn dahin geführt hat, gar nicht so schlecht war. Bspw. merkt er sich für die Aktion „nach oben“ in Feld „4,4“ den Wert 78,625.

Und so weiter und so fort. Im letzten Bild sieht man, dass im Feld „4,3“ und „5,3“ je ein Pfeil „<“ zu sehen ist. Dieser stellt in meinem Programm dar, dass dies die beste Aktion war, die in den letzten Durchläufen gemerkt wurden. Es kann ja auch sein, dass der Agent in Feld „4,3“ mal den Schritt nach oben gemacht hat. Dafür hat er dann aber keine Punkte bekommen.

Nach 30 Durchläufen kann das Ganze in etwa so aussehen:

Je heller ein Feld ist, desto mehr Belohnungs-Punkte hat sich der Agent dafür gemerkt. Man sieht, dass sich ein Weg abzeichnet, oder vielmehr ist es eine Strategie – eine Policy, die der Agent verfolgen kann. Beim nächsten Durchlauf fährt der Agent wieder zufällig los und trifft er dann irgendwann auf ein Feld, in dem er sich schon Punkte gemerkt hat. Jetzt kann er der gemerkten Strategie weiterfolgen, indem er die gewinnbringendsten Aktionen wählt.

Da der Agent immer zufällig losfährt, kann das Ergebnis nach 30 Durchläufen auch ganz anders aussehen:

Man sieht schon, dass es notwendig ist, einige Durchläufe zu machen, um für alle Felder von Start bis zum Ziel eine passende Aktion zu finden. Ab 50 Durchläufen hat der Agent fast immer eine passende Strategie/Policy von Start bis zum Ziel gefunden.

Exploitation versus Exploration

Da das Schachbrett nicht so groß und recht einfach gestrickt ist, findet der Agent meistens eine der optimalen Route ohne Umwege. In obigen Beispiel hat der Agent aber einen kleinen Schlenker eingebaut. Zufällig hat er sich in Feld „9,7“ für die Aktion „rechts“ entschieden, und ist dann im Feld „10,7“ gelandet. Im Feld „10,7“ war schon die Aktion „nach oben“ aus einem vorherigen Durchlauf als die Beste gespeichert. Der Schlenker war nicht mehr vermeidbar.

Ursache dieses Problems ist, dass sich der Agent „zu schnell“ auf eine Aktion festlegt, die er dann zukünftig nutzt. Man nennt das auch die Frage nach „Exploitation versus Exploration“ –  zwischen Verwertung (einer gefundenen Strategie) und der Erkundung (von weiteren Strategien).¹

Das Problem lässt sich in RL angehen, indem man einen Exploration-Wert festlegt. Dieser regelt, ab wann sich der Agent in einem Zustand auf eine gefundene Aktion festlegt: Erst wenn eine Aktion x-mal ausgeführt (und bewertet) wurde, legt sich der Agent auf diese Aktion fest.

Im letzten Bild 7 ist zu erkennen, dass „Num of Done“ auf 1 gesetzt war – also reicht bereits 1 Aktion um sich festzulegen. Beim Wert 10 sieht das Bild bereits ganz anders aus:

Man sieht auch schön, wie immer mehr Felder des Grids bewertet werden, da er viel mehr Wege erkundet. D.h. sollte der Agent aus irgendeinem Grund vom Weg abkommen, hat er jetzt viel mehr Chancen wieder auf den richtigen Weg zu finden. Landet der Agent bspw. aus irgendeinem Grund in Feld „4,8“, dann kommt er im Gegensatz zu der Policy in Bild 7 schnell wieder Richtung Ziel.²

Mit noch mehr Durchläufen und einem noch höheren „Num of Done“ Wert füllt sich dann das ganze Grid:

Mehr Unsicherheit

Was in den bisherigen Beispielen noch nicht eingebaut war, ist die Unsicherheit, die beim Ausführen einer Aktion herrschen kann. Der Wert für „Target Prob“ (Target Probability), also die Wahrscheinlichkeit, dass eine gewählte Aktion zum anvisierten Feld führt, war immer auf 1,0 gesetzt. Setze ich ihn auf 0,6, dann ist in meinem Programm die Wahrscheinlichkeit nach links oder rechts zu rutschen bei je 0,2 (0,6 + 0,2 links + 0,2 rechts = 1,0 Gesamt-Wahrscheinlichkeit)

Interessant sind nun die Felder neben den „Löchern“. Rechts und links neben einem Loch ist die Wahrscheinlichkeit reinzufallen recht hoch, wenn ich direkt nach oben fahre. In Bild 9 war das noch die optimale Strategie. In Bild 10 ist es besser, erstmal vom Loch wegzufahren.

Warum heißt das ganze „Bestärkendes Lernen“?

Zu Beginn schrieb ich, dass wir uns für Feld „4,3“ den Wert 89,10 merken. Warum ist der Wert so krumm?
Der Wert wird letztlich berechnet durch eine Kombination

1. der bisher gemerkten Werte für die ausgeführte Aktion,
2. PLUS die Belohnung aus dem erreichten Feld (wie die 100 aus dem (+) Feld).

Fertig. Deshalb heißt es auch bestärkendes Lernen, denn der bisher gelernte Belohnungs-Wert für eine Aktion hat Einfluss auf die weitere Steigerung des Wertes in den folgenden Durchläufen: Er wird weiter bestärkt  – oder auch nicht.

Hinzu kommen noch die Faktoren:

1. Discount, damit nicht die gesamten +100 des nächsten Zustands in den gelernten Aktions-Wert einfließen
2. und eine Learning-Rate, die regelt, wie schnell der Wert nach weiteren Durchläufen steigt – je öfter eine Aktion ausgeführt wird, desto langsamer steigt der Wert.

Ein bisschen Punkt- und Strich-Rechnung also.
Das sieht dann programmiertechnisch beispielsweise so aus:

        // number of times executed this action (through all Runs!)
        double saNumberOfTimesDone = actionToUpdate.getNumberOfDone();
        // learning rate alpha (as numberOfDone gets higher, the expected result will increase slower)
        double alpha = 1 / (saNumberOfTimesDone / 100 + 1.0);
        // currentReward of this Run
        double stateReward = 0; 
        // last calculated Utility Reward IN this run
        double utilityReward = actionToUpdate.getExpectedReward();
        // discount
        double gamma = 0.9; // almost no discount for now
        // new utility reward IN this run:
        double newUtilityReward = utilityReward + alpha * (stateReward + gamma * utilityRewardNextState - utilityReward);

Es finden sich also:

1. die Belohnung des erreichten Zustands (utilityRewardNextState, bspw die 100 des (+)-Felds )
2. mal einen Discount (gamma – wir wollen ja nicht die kompletten 100 übernehmen)
3. minus den vorherigen Wert der ausgeführten Aktion, den wir uns gemerkt haben (utilityReward – ist am Anfang noch 0)
4. plus die festgesetzte Belohnung für diesen Zustand (stateReward – ist in dieser Anwendung immer 0 für alle Zustände außer den Ziel-Zuständen)
5. und das Ganze mal die Learning-Rate (alpha – die bestimmt, wieviel von diesem Durchlauf zum bisherigen Wert hinzuaddiert wird, die ist bspw abhängig von der Zahl der Ausführungen)
6. plus nochmal den vorherigen Wert der ausgeführten Aktion (utilityReward)

Das Ganze ergibt dann den neuen Wert der ausgeführten Aktion (newUtilityReward), der im nächsten Durchlauf zum utilityReward wird.

Rechenbeispiel für 2 Durchläufe

In meinem Programm-Beispiel ist das beim 1. Durchlauf (saNumberOfTimesDone = 1):

• alpha = 1 / (1 / 100 + 1.0) = 1 / 1,01 = 0,99
• newUtilityReward =  0 + 0,99 * ( 0 + 0,9 * 100 – 0) = 89,10

Beim 2. Durchlauf (saNumberOfTimesDone = 2) ergibt sich dann ein leicht höherer Wert:

 

• alpha = 1 / (2 / 100 + 1.0) = 1 / 1,01 = 0,98
• newUtilityReward =  89,10 + 0,98 * ( 0 + 0,9 * 100 – 89,10) = 89,98

 

usw.

Ich habe eine recht hohe Learning-Rate alpha gesetzt – deshalb steigt der Wert am Anfang recht schnell und dann langsamer. Je nach Anwendungsfall wird man die Learning-Rate anders setzen.

Es gibt verschiedenste Algorithmen. Peter Norvig gibt in diesem MOOC einen guten Überblick.

Wie geht’s weiter?

Soweit meine kleine Einführung zum Reinforcement Learning. Mal sehen, wie es weitergeht. In dem erwähnten MOOC gibt es noch weitere Beispiele, an denen ich mich orientieren möchte. Interessant finde ich beispielsweise, dass ein Zustand ja nicht unbedingt die Position im Grid sein muss, sondern auch einfach die Richtung zum Ziel ein Zustand sein kann, an dem man Aktionen orientiert. Dadurch lässt sich viel schneller lernen: Wenn ich weiß, ich bin rechts vom Ziel, dann kann ich die einmal gelernte Aktion „nach links“ viel schneller verinnerlichen, als wenn ich für jedes Feld einzeln lernen muss, dass ich „nach links“ gehen muss. Ich denke da lässt sich noch auf einige Arten experimentieren.

Zudem lese ich mich gerade in Automated Planning ein. Reinforcement Learning kann man als Teilgebiet davon sehen. Daher bin ich gespannt, was von hier noch für Anregungen einfließen werden.

1. Das ist nicht nur in der „künstlichen“ Intelligenz eine wichtige Frage – Stichwort „Innovation„…. [↩]
2. Wobei es hier auch wieder einen kleinen Schlenker nach rechts in Feld „5,8“ gibt, das liegt aber auch daran, dass das Feld auch erst wenige 9 Male besucht wurde [↩]