Ist das ein Q-Learning-Algorithmus oder nur Brute Force?

Ich habe mit einem Algorithmus gespielt, der lernt, wie man Tictactoe spielt. Der grundlegende Pseudocode lautet:

repeat many thousand times {
  repeat until game is over {
    if(board layout is unknown or exploring) {
      move randomly
    } else {
      move in location which historically gives highest reward
    }
  }

  for each step in the game {
    determine board layout for current step
    if(board layout is unknown) {
      add board layout to memory
    }
    update reward for board layout based on game outcome
  }
}

now play a human and win :-)

Exploration: Am Anfang erforscht der Algorithmus aggressiv und dies reduziert sich linear. Nach etwa tausend Spielen wird nur in 10% der Züge erforscht. Alle anderen Bewegungen basieren auf der Ausnutzung früherer Belohnungen.

Belohnungen: Wenn das Spiel zu einem Sieg geführt hat, vergeben Sie 10 Punkte. Wenn das Spiel zu einem Unentschieden führte, 0 Punkte, sonst -5 Punkte. Tatsächlich können diese Belohnungen "abgestimmt" werden, sodass, wenn das Spiel kürzer war und gewonnen wurde, mehr Punkte vergeben werden oder wenn es länger war, weniger Punkte vergeben werden. Auf diese Weise gewinnt der Algorithmus lieber schnell. Das bedeutet, dass es lernt, so schnell wie möglich zu gewinnen, anstatt später zu gewinnen. Das ist wichtig, damit es nicht verpasst, sofort zu gewinnen - wenn es einen solchen Zug verpasst, würde der Gegner wahrscheinlich a) dorthin ziehen, um zu vermeiden, dass die KI das nächste Mal gewinnt, und b) den Algorithmus für dumm halten, weil er einen "offensichtlichen" verpasst hat " Sieg.

Dieser Algorithmus lernt tatsächlich, also kann ich ihn als Maching-Lernalgorithmus klassifizieren.

Ich denke, aber ich bin nicht sicher, ob es sich um einen verstärkten Lernalgorithmus handelt. Laut https://www.cse.unsw.edu.au/~cs9417ml/RL1/tdlearning.html handelt es sich jedoch nicht um zeitliches Differenzlernen, da die Belohnungen erst am Ende geschätzt werden und geschätzt werden sollten die Belohnung, wie es geht. Das könnte bedeuten, dass es sich nicht um verstärktes Lernen handelt.

Frage 1: Kann ich erfolgreich argumentieren, dass ich die Belohnung basierend auf der Geschichte schätze und trotzdem behaupte, dass der Algorithmus verstärktes Lernen oder sogar Q-Learning ist?

Frage 2: Wenn ich die Belohnungssuche, die auf dem Board-Layout basiert, durch ein neuronales Netzwerk ersetze, in dem das Board-Layout die Eingabe und die Belohnung die Ausgabe ist, könnte der Algorithmus als tiefgreifendes Verstärkungslernen angesehen werden?

Frage 3: Ich würde nicht glauben, dass ich entweder eine Lernrate oder einen Rabattfaktor habe. Ist das wichtig?

Mir ist aufgefallen, dass der Algorithmus ziemlich nutzlos ist, wenn ich ihn nicht mit mindestens jeder Bewegung trainiere, die ein Gegner versucht. In gewisser Weise fühlt es sich so an, als würde man brutale Gewalt anwenden, anstatt wirklich "zu lernen". Dies lässt mich fragen, ob maschinelles Lernen Tictactoe wirklich lernt oder nicht. Ich bin damit einverstanden, dass die Verwendung eines neuronalen Netzwerks zum Erlernen der Bilderkennung als Lernen eingestuft werden kann, da es, wenn es ein unbekanntes Bild sieht, seine Klassifizierung angeben kann. Aber das ist ziemlich nutzlos für Spiele wie Tictactoe, bei denen ähnlich aussehende Board-Layouts völlig unabhängig sind (eines kann zu einem Sieg führen, das andere kann zu einem Verlust führen). Damit...

Frage 4: Können Tictactoe-Algorithmen als echtes Lernen und nicht nur als Brute Force eingestuft werden?

Update: in Bezug auf Belohnungen ... Wenn der Algorithmus entscheidet, wohin er gehen soll, berechnet er die Belohnung für jede Position wie folgt:

var total = winRewards + drawRewards + lossRewards;
move.reward = (100*(winRewards/total)) + (10*(drawRewards/total)) + (-1*(lossRewards/total));

Ich dividiere durch die Gesamtzahl der Punkte (für jeden Zug), weil es sonst zu lernen scheint, dass ein Ort GROSS ist und anderen keine Chance gibt. Auf diese Weise berechnen wir die Gewinnquote unabhängig davon, wie oft sie gespielt wurde. Es ist im Vergleich zu den anderen normalisiert.

Der Code ist hier verfügbar: https://github.com/maxant/tictactoe/blob/master/ai.js

UPDATE 2: Ich habe seitdem herausgefunden, dass dieser Algorithmus nicht als Brute-Force-Algorithmus eingestuft werden kann, da er nicht so viele Spiele lernt, bevor er Experte wird. Details hier: http://blog.maxant.co.uk/pebble/2018/04/11/1523468336936.html

Fragen zu Definitionen machen immer Spaß. Lassen Sie mich hier versuchen, eine andere Antwort zu geben.

Lassen Sie uns zunächst mathematisch modellieren, was Sie tun. Auf der höchsten Ebene schätzen Sie ein gewisses Maß an "Belohnung"$R(s)$ für jeden Board-Status $s$. Sie tun dies, indem Sie mit der Umgebung interagieren und Ihre internen Parameter (dh die Tabelle von) aktualisieren$R$Werte) zur Verstärkung des günstigen Verhaltens. Folglich sollte Ihr Algorithmus nach den meisten Standarddefinitionen tatsächlich als verstärkendes Lernen eingestuft werden .

Um zu verstehen, welche Art von Verstärkungslernen Sie durchführen und ob es "gut" ist, sollten wir etwas tiefer gehen. Einer der Schlüsselbegriffe beim verstärkten Lernen ist die Wertefunktion $V$ (oder sein Alter Ego, das $Q$Funktion), die die bestmögliche Gesamtbelohnung angibt, die Sie erwarten können, wenn Sie von einem bestimmten Board-Status aus optimal spielen. Wenn Sie zeigen können, dass Ihr Algorithmus zumindest in gewissem Sinne schätzt$V$Sie können eine bestimmte "Güte" -Garantie beanspruchen und diese in einen der bekannten "guten" Algorithmus-Typen einteilen (die alle im Wesentlichen beide auf eine Schätzung abzielen $V$ direkt oder so zu tun, als hätten sie es implizit geschätzt).

Beachten Sie, dass es bei Spielen für zwei Spieler nicht unbedingt eine eindeutige gibt $V$auf etwas zielen. Angenommen, die Belohnung 1 für das Gewinnen, 0 für das Verlieren, 0,5 für ein Unentschieden und kein Rabatt.$V(\text{empty board})$ ist $0.5$ wenn Sie gegen einen optimalen Gegner spielen, aber es ist wahrscheinlich in der Nähe $1$wenn dein Gegner zufällig ist. Wenn Sie gegen einen Menschen spielen, ist Ihr$V$kann je nach Mensch unterschiedlich sein. Jeder weiß, dass der erste Zug in die Mitte der sicherste ist, aber ich selbst habe noch nie mit einem solchen Zug gewonnen - das Spiel endet immer mit einem Unentschieden. Ich habe ein paar Mal gewonnen, indem ich den ersten Zug in die Ecke gemacht habe, weil dies einige Gegner verwirrt und sie in ihrer ersten Runde einen Fehler machen. Davon abgesehen, vorausgesetzt$V$ Das Spiel gegen einen optimalen Gegner zu bezeichnen, ist eine vernünftige Wahl.

Um zu Ihrem Algorithmus zurückzukehren, ist der entscheidende Schritt die Aktualisierung von $R$, die Sie nicht wirklich angegeben haben. Lassen Sie mich annehmen, dass Sie dort einfach die Punktzahlen sammeln. Wenn dies der Fall ist, können wir sagen, dass Sie streng genommen kein Q-Learning durchführen, einfach weil dies nicht der Fall ist$Q$Funktion wird in der klassischen Definition aktualisiert. Es bedeutet immer noch nicht, dass Sie nicht implizit das Richtige schätzen$V$Es ist jedoch ziemlich schwer zu beweisen oder zu widerlegen, ob Sie es irgendwann tun oder nicht.

Lassen Sie mich Ihren Algorithmus zur Klarheit ein wenig optimieren. Anstatt die endgültige Belohnung zu addieren$R(s)$ für jeden Staat $s$Lassen Sie uns die durchschnittliche Belohnung verfolgen, die jemals von jedem Staat erreicht wurde. Offensichtlich sollte die Position, an der Sie immer gewinnen, obwohl sie selten erreicht wird, mehr geschätzt werden als eine Position, an der Sie selten gewinnen, auch wenn Sie sie oft erreichen, sodass wir den Algorithmus durch diese Änderung und den allgemeinen Geist von wahrscheinlich nicht brechen werden Lernen bleibt sowieso gleich. Nach dieser Änderung$R(s)$wird leicht zu interpretieren - es ist die durchschnittliche erwartete Belohnung, die von der Position aus erreichbar ist$s$.

Diese durchschnittlich erwartete Belohnung ist nicht wirklich die Wertfunktion$V$Wir sind an einer Schätzung interessiert. Unser Ziel$V$sollte uns schließlich die beste erwartete Belohnung für jede Position mitteilen . Interessanterweise entspricht Ihre durchschnittliche Belohnung jedoch Ihrer optimalen Belohnung (wenn Sie ohnehin immer optimale Züge ausführen), wenn Ihre Richtlinie bereits optimal ist. Daher kann es vorkommen, dass Sie die falsche Metrik in Ihrer Richtlinie lernen Algorithmus: Wenn der Lernprozess Ihren Algorithmus ein wenig in Richtung eines optimalen Spiels treibt, während Sie Ihre Richtlinie schrittweise verbessern, wird die Metrik "Durchschnittliche erwartete Belohnung" selbst langsam "korrekter" und Sie beginnen schließlich, zur korrekten Wertfunktion zu konvergieren. Dies ist reine Handbewegung, sollte aber die Behauptung veranschaulichen, dass es schwierig ist zu beweisen oder zu widerlegen, ob Ihr Algorithmus formal lernt, was er lernen sollte. Vielleicht schon.

Lassen Sie uns in jedem Fall Ihren Algorithmus ändern , anstatt die durchschnittliche Belohnung für jeden Status zu verfolgen, um die bisher bestmögliche Belohnung zu verfolgen . Dies bedeutet, dass Sie alle alternativen Bewegungen von jeder Position aus überprüfen und nur aktualisieren$R(s)$Wenn Ihr aktueller Zug später zu einer verbesserten Punktzahl geführt hat (im Vergleich zu alternativen Optionen, die Sie aus diesem Zustand hätten ziehen können). Herzlicher Glückwunsch, jetzt Ihr Algorithmus ist äquivalent zu dem üblichen Q-Learning - Verfahren (es ist die „Wert Iteration“ Methode, um genauer zu sein).

Schließlich ist "ist es Lernen oder rohe Gewalt" eine gültige Frage. Das Wort "Lernen" kann auf mindestens zwei verschiedene Arten interpretiert werden. Erstens kann Lernen ein vereinfachtes Auswendiglernen bedeuten . Wenn ich beispielsweise feststelle, dass der erste Schritt in die Mitte gut ist, kann ich diese Tatsache in eine Tabelle eintragen und später direkt verwenden. Die Leute nennen solche Auswendiglernen "Lernen", aber dieses Lernen ist wirklich ziemlich dumm.

Eine zweite, andere Bedeutung, die oft dem "Lernen" zugeschrieben wird, ist die Verallgemeinerung . Dies ist der Fall, wenn Ihr Algorithmus nicht nur aufschreibt, welche Bewegungen gut sind, sondern diese Informationen auch auf zuvor nicht sichtbare Bewegungen verallgemeinern kann. Dies ist die "intelligente" Art des Lernens.

Q-Learning sowie viele andere RL-Algorithmen werden normalerweise in Form von Aktualisierungen der Tabellen formuliert $V$ oder $Q$. Als solche sind sie von Natur aus "dumme Lern" -Algorithmen, die nicht einmal darauf abzielen, die Zustandsinformationen zu verallgemeinern. Echte Generalisierung (auch als "intelligentes Lernen" bezeichnet) tritt nur dann auf, wenn Sie mit der Modellierung des Status oder der Richtlinie beginnen, indem Sie etwas verwenden, das über eine integrierte Generalisierungsfunktion verfügt, z. B. ein neuronales Netzwerk.

Also, um es zusammenzufassen. Ja, Ihr Algorithmus ist Verstärkungslernen. Nein, es ist kein Q-Learning, aber es wird das mit einer kleinen Änderung. Ja, es ist eher "Brute Force" als "intelligentes Lernen", aber auch das Standard-Q-Learning. Ja, das Hinzufügen von Generalisierung durch Modellieren von Zuständen mit einem neuronalen Netzwerk macht den Algorithmus "intelligenter".

Ein großes Lob dafür, dass Sie einen funktionierenden Tic-Tac-Toe-Algorithmus von Grund auf neu entwickelt haben!

Frage 1: Kann ich erfolgreich argumentieren, dass ich die Belohnung basierend auf der Geschichte schätze und trotzdem behaupte, dass der Algorithmus verstärktes Lernen oder sogar Q-Learning ist?

Das Wichtigste zuerst, dies ist definitiv kein Q-Learning.

Ich denke jedoch, dass es als Reinforcement Learning klassifiziert wird. Sie haben diese Schlüsselkomponenten von RL implementiert:

• Ein Status (die aktuelle Karte), der bei jedem Schritt als Eingabe verwendet wird.

• Eine Aktion (gewünschte Anordnung der nächsten Karte), die als Ausgabe verwendet wird. Wenn die Aktion effektiv darin besteht, den nächsten Status direkt auszuwählen, wird dies manchmal als Nachzustandsdarstellung bezeichnet. Es wird häufig in RL für deterministische Spiele verwendet.

• Von der Umgebung generierte Belohnungen, bei denen das Ziel des Agenten darin besteht, die erwartete Belohnung zu maximieren.

• Ein Algorithmus, der Daten über Zustände, Aktionen und Belohnungen erfasst und lernt, die erwartete Belohnung zu optimieren, indem er Erfahrungen in der Umgebung sammelt.

Ihr Algorithmus ist der Monte-Carlo-Steuerung , einem Standard-RL-Ansatz, IMO am nächsten .

Einer der großen Vorteile von Q Learning besteht darin, dass es auch während der Erkundung eine optimale Richtlinie lernt. Dies wird als Off-Policy- Lernen bezeichnet, während Ihr Algorithmus On-Policy ist, dh er lernt die Werte seines aktuellen Verhaltens kennen. Aus diesem Grund müssen Sie die Explorationsrate im Laufe der Zeit reduzieren - und das kann ein Problem sein, da der Zeitplan für die Explorationsrate ein Hyperparameter Ihres Lernalgorithmus ist, der möglicherweise sorgfältig angepasst werden muss.

Frage 2: Wenn ich die Belohnungssuche, die auf dem Board-Layout basiert, durch ein neuronales Netzwerk ersetze, in dem das Board-Layout die Eingabe und die Belohnung die Ausgabe ist, könnte der Algorithmus als tiefgreifendes Verstärkungslernen angesehen werden?

Ja, ich nehme an, es wäre technisch. Es ist jedoch unwahrscheinlich, dass sich nur durch Hinzufügen eines neuronalen Netzwerks zur Schätzung von Aktionswerten gut auf komplexere Probleme skalieren lässt, es sei denn, Sie fügen einige der komplexeren Elemente hinzu, z. B. die Verwendung von Lernen mit zeitlichen Unterschieden oder Richtliniengradienten.

Frage 3: Ich würde nicht glauben, dass ich entweder eine Lernrate oder einen Rabattfaktor habe. Ist das wichtig?

Ein Abzinsungsfaktor ist für episodische Probleme nicht wichtig. Dies ist nur bei kontinuierlichen Problemen erforderlich, bei denen Sie einen Zeithorizont benötigen, da sonst die vorhergesagte Belohnung unendlich wäre (obwohl Sie den Rabattmechanismus in der Praxis auch durch einen durchschnittlichen Belohnungsansatz ersetzen könnten).

Die Lernrate ist eine wichtige Lücke. Sie erklären nicht, was Sie an seiner Stelle haben. Sie haben gesagt update reward for board layout based on game outcome- dieser Aktualisierungsschritt enthält normalerweise die Lernrate. Für Tic-Tac-Toe und Q-Learning können Sie die Lernrate jedoch auf 1,0 einstellen, was meiner Meinung nach Ihrem Ansatz entspricht und funktioniert. Ich habe Beispielcode geschrieben, der genau das tut - siehe diese Zeile, in der die Lernrate auf 1,0 gesetzt wird . Komplexere Szenarien, insbesondere in nicht deterministischen Umgebungen, würden jedoch mit einer so hohen Lernrate schlecht lernen.

Frage 4: Können Tictactoe-Algorithmen als echtes Lernen und nicht nur als Brute Force eingestuft werden?

Ihr Algorithmus lernt definitiv etwas aus Erfahrung, wenn auch ineffizient im Vergleich zu einem Menschen. Viele der grundlegenderen RL-Algorithmen weisen jedoch ähnliche Probleme auf und müssen häufig jeden möglichen Status eines Systems mehrmals anzeigen, bevor sie zu einer Antwort konvergieren.

Ich würde sagen, dass eine umfassende Baumsuche von der aktuellen Position während des Spiels "Brute Force" war. In einem einfachen Spiel wie Tictactoe ist dies wahrscheinlich effizienter als RL. Da Spiele jedoch immer ausgefeilter werden, wird der Ansatz des maschinellen Lernens mit der Suche konkurrenzfähig. Oft werden sowohl RL als auch irgendeine Form der Suche zusammen verwendet.