Lernen in Neuronalen Agenten

Aus II-Wiki
Version vom 10. Juli 2009, 17:24 Uhr von Sonne (Diskussion | Beiträge) (Neuronale Value Approximation am Beispiel TD-Gammons: Zuggenerator eingefügt)
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Begriffliche Grundlagen

Übersicht über wesentliche Aspekte des Lernens

LiNA-WesentlicheLernAspekte.jpg

Verhalten

Entspricht dem natürlichsprachlichen Begriff des Verhaltens und umfasst alle strukturierten Interaktionen mit der Umwelt. Dabei kann man, sofern man das möchte, zwischen komplexem Verhalten und Basisverhalten unterscheiden (wobei sich komplexes Verhalten aus Basisverhalten zusammensetzt)

Agent

Ein Agent ist eine physische oder virtuelle Entität (Ferber 2001),

  1. die selbständig in einer Umwelt agieren kann
  2. die direkt mit anderen Agenten kommunizieren kann
  3. die durch eine Menge von Absichten angetrieben wird (in Form von individ. Zielen, Befriedigungs-/Überlebensfunktionen, die sie versucht zu optimieren)
  4. die eigene Ressourcen besitzt
  5. die fähig ist, ihre Umwelt wahrzunehmen (nur in einem best. Ausmaß!)
  6. die nur eine partielle Repräsentation der Umwelt (Modell) besitzt
  7. die bestimmte Fähigkeiten besitzt (oder erwirbt) und Dienste offerieren kann
  8. die sich ggf. selbst reproduzieren kann
  9. deren Verhalten darauf ausgerichtet ist, ihre Ziele unter Berücksichtigung der ihr zur Verfügung stehenden Ressourcen und Fähigkeiten zu befriedigen und die dabei auf ihre Wahrnehmung, ihre internen Modelle und ihre Kommunikation mit anderen Agenten (oder Menschen) angewiesen ist

Lernprozesse

  • Zweck der Informationsverarbeitung: situationsgerechtes Verhalten in der Umwelt
  • Zwecke des Lernens: Veränderung des Verhaltens und damit Vergrößerung des Einsatzbereichs in dem Agent eingesetzt werden kann
  • Realisierung des Lernprozesses: Umstrukturierung der Steuerarchitektur

Perception-Action-Cycle

  • Wahrnehmungs-Handlungs-Zyklus
  • Lernen erfordert eine sensorische Beobachtung der Umwelt und eine Aufgabe bzw. zielgerichtete Handlung, deren Erfolg/Misserfolg für den Agenten erkennbar sein muss
  • Resultat: Selbstoptimierung des Verhaltens (um bestmöglich die gestellte Aufgabe zu erfüllen)

Stability-Plasticity Dilemma

Ist das Problem auf neue Situationen reagieren zu können und diese zu lernen, dabei aber bereits angesammeltes Wissen zu bewahren.

Exploration-Exploitation Dilemma

Ebenfalls ein Standardproblem von lernenden Systemen. Um neues Wissen über meine Umwelt zu erlangen müsste ich ständig explorieren, andererseits sollte ich aber auch ständig bekannte Aktionen ausführen um bereits gelerntes Wissen anzuwenden (exploitation) Lösungsansätze kommen später

Ebenen des Lernens und der Wissensrepräsentation

prozedurales Wissen:

  • Verhaltenswissen bzw. Sensomotorische Intelligenz
  • Beschreibt für eine ganz konkrete sensorische Situation die möglichen Aktionen des Agenten
  • "Gewusst WIE"

deklaratives Wissen:

  • deliberatives oder auch kognitives Wissen
  • stellt Repräsentation der Umwelt dar
  • dient der Planung von Verhalten
  • "Gewusst WAS"

Aus deklarativem Wissen können Subziele einer Handlungsstrategie festgelegt werden, welche dann mit Hilfe des prozeduralen Wissens abgearbeitet werden. Zum Beispiel könnte ein, mittels deklarativem Wissen erstelltes Subziel, auf dem Weg ein Wasserglas zu greifen, sein, den Arm auszustrecken. Das prozedurale Wissen beschreibt dann wie die Muskeln anzusteuern sind, um den Arm nach vorne zu bekommen.

Vergleich:
LiNA-VergleichProzeduralDeklarativ.jpg

Konditionierungslernen

  • ein grundlegendes Lernprinzip im Perception-Action-Cycle

klassische Konditionierung

  • ein unkonditionierter Stimulus (US) erzeugt immer eine sichtbare Reaktion (UR) und ist angeboren, wie ein Reflex
    • z.B Nahrung -> Speichelfluss
  • ein konditionierter Stimulus (CS) erzeugt zunächst keine sichtbare Reaktion (CR)
    • z.B. Glockenschlag
  • durch die kombinierte Anwendung von US und CS ist es möglich, ein CR auszubilden, welches dem UR ähnelt bzw. mit ihm identisch ist
  • Folge: durch die alleinige Anwendung des CS kommt es zur sichtbaren Reaktion UR
    • z.B. Die Fütterung eines Hundes (US) löst bei diesem zunächst Speichelfluss (UR) aus. Ertönt bei jeder Futtergabe ein Glockenschlag (CS) führt dies dazu, dass nach einiger Zeit der Glockenschlag allein ausreicht um den Speichelfluss zu aktivieren. (CR=UR)

-> Detektion von Beziehungen zwischen Ereignissen in der Umwelt

instrumentale Konditionierung

  • Aktionen die in bestimmten Situationen zu Befriedigung führen werden häufiger ausgeführt als solche die zu Unzufriedenheit führen, d.h. unmittelbar auf eine Handlung folgt eine Konsequenz
  • die Handlung fungiert somit als Instrument für die Konsequenz
    • z.B. eine Ratte die eine Taste berührt und daraufhin Futter bekommt, wird dies wiederholt tun, wohingegen sie es vermeiden wird die Taste zu berühren, wenn sie daraufhin einen Stromschlag bekommt

-> Detektion von Beziehungen zwischen Verhalten und nachfolgendem Ereignis in der Umwelt

Reinforcement Learning

Grundidee des RL

Für jede ausgeführte Handlung (oder auch am Ende eines Handlungsstranges) erhält ein Agent eine Belohnung oder Bestrafung (Reinforcement). Diese akkumuliert sich über die Zeit. Ziel des Reinforcementlearnings ist es nun, durch Lernen solche Entscheidungsstrategien zu finden, so dass die akkumulierten Reinforcements optimal werden.

Charakterisierung des RL

  • Lernparadigma:
    • irgendwo zwischen überwachtem Lernen und unüberwachtem Lernen
    • nutzt ebenfalls ein Feedback, aber nur zur Bewertung des Verhaltens
      • alleinige Aussage, ob das Verhalten gut war oder schlecht, aber nicht, wie es hätte sein müssen
  • Grundsatz (noch mal in einem Satz):
    • autonomes Lernen komplexer Wahrnehmungs-Verhaltens-Muster basierend auf einem unspezifischen skalaren Signal, welches das Systemverhalten bewertet
  • Findet Anwendung in: Robotik, Optimaler Regelung, Spielen uvm.

General RL-Task

Dies ist eine Grafik mit Rahmen und Knoten, die Hyperlinks enthalten könnten.
  • Ziel: lernen die Aktionen auszuführen, die zum größten Langzeit-Reward führen
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_t = \sum_{k=0}^\infty \gamma^k \cdot r_{t+k+1} }
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle R_t } ... Langzeitreward
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma } ... Discountfaktor [0,1] ... schwächt den Einfluss ferner Rewards ab
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r_t } ... reward zum Zeitpunkt t
  • Durchführung: Ausführung einer Aktion und beobachten des Ergebnisses
    • Anpassen der Policy, welche die Aktion ausgewählt hat, je nach dem ob das Reward positiv oder negativ ausgefallen ist, damit die Aktion öfter ausgeführt wird oder weniger oft, wenn der selbe Zustand wieder erreicht werden sollte.
  • Die beste Aktion in einem Zeitschritt führt nicht immer zum besten Langzeitergebnis!

schwache und starke RL-Verfahren

schwache RL-Verfahren

  • Haben nur eine begrenzte zeitliche Sicht
  • suchen nur eine lokal optimale Policy
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma \rightarrow 0 }
  • Wählen immer die für ihre Sicht optimale Aktion aus
  • z.B. Räuberschach

starke RL-Verfahren

  • besitzen zeitlich unbegrenzte Sicht
  • Versuchen eine global optimale Policy zu erlernen
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma \rightarrow 1 }
  • Maximierung der Summe aller Rewards
  • z.B. Schach, Backgammon

RL als MDP

  • MDP (Makrov Decision Processes)
  • Annahmen
    • es gibt nur eine endliche Menge an Zuständen
    • es gibt eine endliche Menge an ausführbaren Aktionen
    • Der Zustand kann zu jeden Zeitpunkt beobachtet werden und es ist möglich eine Aktion auszuwählen für den Zustand anhand einer Policy
    • Nach der Ausführung der Aktion gibt es ein reward
    • Der Zustand wird durch die Aktion in den nächsten Zustand überführt
  • Markov Annahme
    • Der nächste Zustand wird ausschließlich durch den aktuellen Zustand und die auszuführende Aktion bestimmt
  • Damit kann der zu erwartende Reward anhand des aktuellen Zustandes berechnet werden

Basiskomponenten eines RL-Agenten

LiNA-BasicComponentsOfRlAgent.jpg

Policy

  • Entscheidungsfunktion die angibt welche Aktion ausgeführt werden soll wenn sich der Agent in einem bestimmten Zustand befindet
  • Die Policy bestimmt das Verhalten und die Performance des Agenten alleine
  • Alle anderen Komponenten existieren nur damit die Policy verbessert und angepasst werden kann

Reinforcement Funktion

  • Definiert die Ziele des Agenten
  • Wird vom Entwickler vorgegeben
  • Ist eine Funktion die den Zustand bewertet und angibt wie erwünscht er ist -> definiert was gut und was schlecht ist
  • Darf während des Lernens nicht geändert werden, sonst kann man keine Policy erreichen
  • Das Reward sagt dem Agenten WAS erreicht werden soll, aber nicht WIE

Value/Action Funktion

  • Value V(s) ist eine Funktion welche angibt welchen Reward man erhalten würde wenn man sich im Zustand S befindet und der Policy folgt
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^\pi (s) = E_\pi \lbrace R_t \mid s_t = s \rbrace }
  • Action-Value Q(s,a) ist eine Funktion die angibt welchen Reward man erhalten würde wenn man sich im Zustand S befindet die Aktion a ausführt und dann der Policy folgt
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\pi (s,a) = E_\pi \lbrace R_t \mid s_t = s , a_t = a \rbrace }
  • Reinforcements bestimmen wie erwünscht der aktuelle Zustand ist
    • sie werden direkt aus der Umgebung bezogen
  • Values hingegen geben die Langzeit-Erwünschtheit an, nachdem die, am wahrscheinlichsten erreichten, Zustände mit ihren jeweiligen Reinforcements errechnet wurden
    • sie sind nur Schätzungen aus der Beobachtungsfolge, welche ein Agent über die gesamte Zeit macht
    • somit kann nicht nur kurzsichtig agiert werden sondern auch langfristig
    • kann approximiert werden durch Lookup Tabellen oder MLP/RBF-Netzwerke
  • Eine der Hauptaufgaben des RL ist es die Value-Funktion durch Lernen effizient zu approximieren

Umgebungsmodell

  • immitiert das Verhalten der Umgebung
  • kann durch den Entwickler vorgegeben werden oder selbst erlernt werden
  • hilft den neuen Zustand vorherzusagen wenn man eine bestimmte Aktion ausführt
  • nicht jeder RL-Agent besitzt ein Umgebungsmodell, aber es erhöt die Geschwindigkeit mit der ein Agent die optimale Policy lernt
  • modellfreie RL-Agenten finden die selbe Lösung, es dauert nur länger

Umgebung

  • muss wenigstens teilweise beobachtbar sein
  • Umgebung gibt die möglichen Aktionen mit vor

State (Zustand):

  • Alle notwendigen Parameter der Umgebung, die die Entscheidung beeinflussen eine Aktion auszuwählen, sind dem Agenten zugänglich
  • wie z.B. globale Positionsinformation

Situation:

  • Der Agent hat nur Zugriff auf einen Teil der Parameter, so dass der aktuelle Zustand nicht immer eindeutig beschrieben werden kann
  • z.B. navigation mit IR oder Ultraschall Sensoren

Schätzung des States:

  1. Zusätzliche Sensoreinflüsse nutzen
  2. Weg ab Startpunkt merken
  3. Aus mehreren Umgebungsbeobachtungen und einem Umgebungsmodell State schätzen

Optimale Policies finden

Policy Iteration

  • hier wird die optimale Policy gesucht, indem verschiedene Strategien direkt miteinander verglichen und bewertet werden

Value/Action-Value Iteration

  • indirekte Suche nach der besten Policy durch die Value-Funktion
  • dazu wird für jeden Zustand (oder jedes Zustands-Aktions-Paar) die Value-Funktion berechnet und das Maximum als beste Policy festgelegt
  • bei komplexen Umgebungen führt dies aber schnell zu einem sehr großen Rechenaufwand und Speicherbedarf

Value/Action-Value Iteration

Das Bellman'sche Optimalitätsprinzip

  • Der Teilplan eines optimalen Plans ist ebenfalls optimal!
  • Eine optimale Policy hat die Eigenschaft, dass für einen beliebigen Zustand und beliebige Aktionen, alle nachfolgenden Entscheidungen wieder eine optimale Policy generieren -> Gebirgswanderung
LiNA-Gebirgswanderung.jpg

Die Bellman'sche Gleichung

  • Values sind Funktionen des Zustandes oder der Zustands-Aktions-Paare und schätzen wie gut es für einen Agenten ist, sich in diesem Zustand zu befinden oder diese Zustands-Aktions-Auswahl zu treffen (unter Berücksichtigung einer speziellen Policy)
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^\pi (s_t) = E \lbrace r_{t+1} + \gamma \cdot V^\pi (s_{t+1}) \rbrace }
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\pi (s_t,a_t) = E \lbrace r_{t+1} + \gamma \cdot Q^\pi (s_{t+1},a_{t+1}) \rbrace }

Optimale Value-Funktionen

  • Optimale Policies haben alle eine optimale Zustands-Value-Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^\ast (s)} bzw. Zustands-Aktions-Value-Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\ast (s,a)} gemeinsam
  • Idee (1): Der Zustands-Value, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert für die beste Aktion ausgehend von diesem Zustand, unter Berücksichtigung der optimalen Policy, sein
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V^\ast (s) \stackrel{!}= \underset{a \in A(s)}{\mathrm{max}} \left[ Q^{\pi^\ast} (s,a) \right] = \underset{a}{\mathrm{max}} \left[ E \lbrace r_{t+1} + \gamma \cdot V^\ast (s_{t+1}) \mid s_t = s, a_t = a \rbrace \right] }
  • Idee (2): Der Aktions-Value eines Zustands-Aktions-Paares, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert der besten Aktion des darauffolgenden Zustandes, unter Berücksichtigung der optimalen Policy, sein
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\ast (s,a) \stackrel{!}= \underset{a_{t+1} \in A(s_{t+1})}{\mathrm{max}} \left[ Q^{\pi^\ast} (s,a) \right] = E \lbrace r_{t+1} + \gamma \cdot \underset{a'}{\mathrm{max}} \left [ Q^\ast (s_{t+1},a') \right] \mid s_t = s, a_t = a \rbrace }
    • dies bildet die Vorraussetzung für Q-Learning
  • Fazit: Wählt man immer die Aktion mit dem größten Aktions-Value, so sollte sich auch der long term Reward maximieren

Q-Learning

  • Idee: Bellman'sche Gleichung in eine Updateregel umwandeln, indem zwei aufeinanderfolgende Zeitschritte betrachtet werden
    • Policy Bewertung: Value-Funktion lernen
    • Policy Verbesserung: Maximum-Suche bezüglich der gelernten Value-Funktion
    • erneute Wiederholung führt zur optimalen Value-Funktion

Q-Learning-Algorithmus:

  • Initialisierung aller geschätzten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat Q(s,a)} mit 0 [Anm.: Bei unendlich häufiger Ausführung des Algorithmus nähern sich die geschätzen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat Q} den optimalen (welche den long-term reward maximieren) Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\ast} an.]
  • beobachte den aktuellen State Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s=s_t}
  • Wiederhole:
    • Wähle eine Aktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a=a_t} im aktuellen Zustand entsprechend der Policy (z.B. greedy Auswahl der Aktionen mit maximalem Q-Wert oder Bolzmann Auswahl) und führe sie aus
    • Erhalte den sofortigen reward
    • Beobachte den neuen Zustand Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s'=s_{t+1}}
    • Update des geschätzten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat Q} nach folgender Update-Gleichung:
      Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat Q_{k+1}(s,a):=\hat Q_{k}(s,a)+\beta \cdot \left ( r+ \gamma \cdot \max_{a' \in A} \left (\hat Q_k(s',a') \right ) -\hat Q_k(s,a) \right )}
    • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle s \leftarrow s'} (s' zu neuem aktuellen Zustand machen)
  • bis die Zustände erschöpfend durchsucht wurden, d.h. bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \hat Q} gegen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q^\ast} konvergiert

Die Updateregel ist wie folgt zu interpretieren:

Die neue Schätzung des Q-Values einer Aktion a (welche soeben durchgeführt wurde) im vorigen Zustand s (Der Zustand vor dem Ausführen der Aktion a) setzt sich aus der alten Schätzung dieses Wertes zusammen plus einen Anpassungsterm, welcher mit einer skalaren Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \beta} gewichtet ist, welche die Lerngeschwindigkeit beeinflusst. Der Anpassungsterm ist der, durch Ausführung von a, erhaltene Reward + dem maximal möglichen Q-Value des Zustandes in dem ich mich aktuell befinde, minus dem Q-Value des vorigen Zustandes. Der Faktor Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma} sorgt dafür, dass die Q-Werte mit steigender Entfernung (im Sinne von aufeinander folgenden Zuständen) zu einem Zustand, in welchem es einen großen Reward gibt, stetig fallen. Damit kann eine Art Q-Value Gradientenaufstieg in Richtung von besonders positiven Zuständen erfolgen (oder eben eine Abwendung von besonders Negativen). Die Subtraktion des Q-Values am Ende sorgt nur dafür, dass diese nicht ins Endlose steigen. Sieht man gut, wenn man Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \beta=1} annimmt.

Möglichkeiten zur Repräsentation der geschätzten Q-Funktion:

  • Tabellierte State-Action-Paare
    • exponentiell wachsender Speicherbedarf
  • neuronale Funktionsapproximatoren
    • adaptive Vektorquantisierung
    • "supervised" Learning
    • brauche für jede Aktion einen Funktionsapproximator

Exploration/Exploitation revisited

Wie schon mal angesprochen sollte man nicht immer nur exploren aber auch nicht nur exploiten

Zwei Verfahren besprochen, das Dilemma "schön" zu lösen:

Epsilon-Greedy:

  • mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1-\epsilon} wird die Aktion ausgewählt, welche den höchsten Reward verspricht (welcher der höchste Q-Wert anhängt)
  • mit Wahrscheinlichkeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \epsilon} wird eine zufällige Aktion ausgewählt

Boltzmann-Aktionsauswahl:

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(a_i)=\frac{\mathrm e^{\left(\frac{\hat Q(s,a_i)}{T(t)}\right )}}{\sum_{j=1}^{M}\mathrm e^{\left(\frac{\hat Q(s,a_j)}{T(t)}\right)}}}
  • Boltzmann Temperatur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(t)} bestimmt den Grad der Zufälligkeit der Aktionsauswahl
  • für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T \rightarrow \infty } ist die Auswahl unabhängig vom Q-Wert (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P(a_i)=1/M} mit M - Anzahl der möglichen Aktionen)
    • entspricht einem ausgeprägten Entdeckungsverhalten
  • für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T \rightarrow 0 } werden Aktionen mit hohem Q-Wert ausgewählt und Aktionen mit kleinem Q-Wert vernachlässigt
    • keinerlei Entdeckungsverhalten
  • Mittelweg: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(t) = \frac{T_{start}}{1 + \alpha \cdot t}}
    • es werden gelegentlich Aktionen ausgeführt, die nicht der Policy entsprechen

SARSA-Learning

  • ähnlich dem Q-Learning
  • Unterschied: nehme den Q-Wert des Weges den ich gegangen bin (Q-Learning nimmt den maximalen Q-Wert zum lernen)
  • State -> Action -> Reinforcement -> State -> Action
  • Die Update Regel der Q Werte lautet:
    Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q_{k+1}(s,a) := (1-\beta) \cdot Q_k(s,a) + \beta ( r+ \gamma \cdot Q_k(s',a')) }
  • mit einer Greedy-Policy konvergiert dieses Verfahren gegen das Q-Learning

On-Policy und Off-Policy

On-Policy:

  • Policy, welche die Aktionsauswahl steuert, ist identisch mit der Policy, mit der gelernt werden soll
  • typischer Vertreter: SARSA-Learning

Off-Policy:

  • Policy, welche die Aktionsauswahl steuert, muss nicht identisch mit der Policy sein, mit der gelernt werden soll
  • typischer Vertreter: Q-Learning (z.B. Stochastische Policy für Aktionsauswahl, Greedy-Policy zum Lernen)
  • Vorteil: Lern-Policy kann "gierig" sein, wärend die Policy für die Aktionsauswahl die Möglichkeit hat, alle möglichen Aktionen auszuprobieren

Eligibility Traces

Grundidee

  • Ziel: Rückverteilung der temporealen Differenz von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta V} bzw. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta Q} auf alle Zustände bzw. Zustands-Aktionspaare die zu der aktuellen Situation beigetragen haben
  • Einsatz: Vor allem bei Delayed RL-Problemen (Zielanfahrten, Spiele)
  • erhöhen die Lerngeschwindigkeit des RL-Verfahrens da alle durchlaufenen Zustände und Aktionen aktualisiert werden
  • Die Updateregeln ändern sich zu:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q(s,a):=Q(s,a)+\beta \cdot \underbrace{\left ( r+ \gamma \cdot \max_{a' \in A} \left ( Q(s',a') \right ) - Q(s,a) \right )}_{\Delta Q} \cdot e(s,a)}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V(s) := V(s) + \beta \underbrace{( r+ \gamma \cdot V(s') - V(s))}_{\Delta V} \cdot e(s) }

Realisierungen des Traces

  • erfordert geeignete Markierung aller durchlaufenen V- und Q-Values

Accumulating Trace:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_{t}(s,a)=\left\{\begin{matrix}\gamma \cdot \lambda \cdot e_{t-1}(s,a)&\mathit{wenn}\ s\neq s_{t}\\\gamma \cdot \lambda \cdot e_{t-1}(s,a)+1&\mathit{wenn}\ s=s_{t}\end{matrix}\right.}

  • berücksichtigt Häufigkeit und Aktualität des Zustandes bzw. Zustands-Aktions-Paars
  • Diese Version kann instabil werden da Werte >1 möglich sind

Replacing Trace:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_{t}(s)=\left\{\begin{matrix}\gamma \cdot \lambda \cdot e_{t-1}(s)&\mathit{wenn}\ s\neq s_{t}\\1&\mathit{wenn}\ s=s_{t}\end{matrix}\right.}

  • berücksichtigt nur Aktualität des Zustandes bzw. Zustands-Aktions-Paars (wird dadurch schneller und robuster)

Einfluss von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda} :

  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda =0 } → TD(0): Alle Traces sind deaktiviert -> Normales TD Lernen
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0 < \lambda < 1 } : Normale abklingende Traces
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lambda = 1} : Abklingen des Traces wird nur noch durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \gamma} hervorgerufen

Besonderheiten:

  • Bei der Ausführung von Off-Policy Aktionen muss der Trace deaktiviert werden, da der Zustand durch Befolgen einer anderen Policy erreicht wurde

Typische Probleme beim RL

POMDPs

  • Partially Observable Markov Decision Process
  • wird benötigt wenn Umgebung nur teilweise beobachtbar ist
  • Lösungsansätze:
    • Ignorieren und hoffen
    • Hinzunahme von weiteren Beobachtungen (Geschwindigkeit, Beschleunigung)
    • Benutzung impliziter interner Zeitinformationen (durch Traces)
    • Hinzunahme fester/variabler Zeitfenster (zur Bewahrung der Sensorinformationen)
    • Karte bauen (sollte aber eigentlich vermieden werden)

Komplexitätsproblem

  • Lange Traninigszeiten der Agenten, selbst bei einfachen Aufgaben
  • Ursache: Komplexität des Algo's
    • hängt exponentiell von der Größe des Eingangsraumes und der Anzahl der auszuführenden Aktionen entsprechend der optimalen Policy ab
  • Komplexität wird maximal bei delayed RL (Reinforcement erst nach Erreichen des Ziels) oder tabula rasa RL (Values mit 0 initialisiert)
  • Lösungsansätze:
    • Agent erhält für jede Aktion ein Reinforcement
    • Value-Funktionen optimischtisch realisieren (etwas über dem maximal möglichen Return)
    • angemessene Explorationsstrategien
    • Änderung der Value-Funktion nach jeder Aktion (nicht erst nach Erreichen des Ziels)
    • Eingangsraum zunächst eng um Zielzustand begrenzen und dann immer mehr erweitern
    • Anlernen durch externen Experten (Experte agiert zunächst als Policy)

Neuronale Umsetzung von RL-Agenten

  • State- und Action- Space ist immer reichlich groß -> effizienter die Funktion mittels neuronaler Verfahren zu approximieren
  • Mapping vom State auf eine Action wird gelernt
  • Zwei prinzipielle Ansätze:
  1. Partitionierung des Eingangsraumes mittels Vektorquanitsierern (self organizing feature maps, (growing) neural gas), dann wird mittels Q-Tabular - Learning weitergearbeitet
    • Auch benachbarte Neuronen können mitlernen (hat Vor- und Nachteile!)
  2. alleiniger Einsatz von Funktionsapproximatoren (Multilayerperceptrons, Radiale Basisfunktionsnetze, Regressionsnetze...)

prinzipieller Aufbau

LiNA-RLmitNeuronalenVektorquantisierern.jpg

State Map:

  • empfängt Sensorwerte aus dem kontinuierlichen Input Space (IS) und wandelt sie mittels Vektorquanitisierer in einen diskreten State Space um
  • jede Parzelle repräsentiert dann einen State, oder eine Stategruppierung

Motor Map:

  • kodiert alle möglichen Aktionen des aktuell möglichen State in Form von einfachen Elementaraktionen (z.B. geradeausfahren, rechtsrum...)
  • Hier sollte dann theoretisch auch irgendwie ein neuronaler Funktionsapproximator seine Arbeit verrichten. Dazu steht aber im Script nix gescheites.
    • Eine Möglichkeit wäre, dass er das Mapping von den Partitionen der State Map auf eine Aktion der Motor Map macht.
    • Dann gäbe es aber nur eine Motormap, in der ALLE überhaupt möglichen Aktionen stehen
    • Eine andere Möglichkeit, welche so auch im Script angedeutet ist, ist, dass es pro Parzelle der State Map einen Funktionsapproximator gibt, welcher dann... ich hab keine Ahnung was macht - zumal im Abschnitt Q-Learning Algorithm auch kein NN vorkommt

Neuronale Value Approximation am Beispiel TD-Gammons

  • nutzt TD-Lernen, daher der Name
  • MLP oder RBF-Netz, mit einer oder mehreren Hidden-Schichten
  • Input: speziell kodierte Brettsituation
  • Output: erwarteter Value für jede angelegte Brettsituation
  • Vorgehen:
    • Vor dem Spiel: Netz lernt den Wert einer jeden Situation
    • Während des Spiels: Netz bekommt alle möglichen Züge mittels Zuggenerator präsentiert und gibt geschätzten Wert dieser Züge zurück -> bester Zug ausgewählt
    • Nach dem Spiel: Flasche Sekt aus dem Kühlschrank holen und sich seines Sieges freuen

Inputcodierung:

  • 198 Neuronen:
    • 192 Neuronen für die Brettkonfiguration
      • 24 Punkte * 2 Farben * 4 Neuronen für die Anzahl an Steinen auf dem Punkt
      • Anzahl aktivierter Neuronen pro Punkt entspricht bis 3 der Anzahl an Steinen auf diesem Punkt - 4 aktivierte Neuronen heißt 4 oder mehr Steine auf diesem Punkt
    • 2 Neuronen für die Barkonfiguration - Aktivierung von 1/2 je Stein und Farbe
    • 2 Neuronen für die im Aus befindlichen Steine - Aktivierung von 1/15 je Stein und Farbe
    • 2 Neuronen für aktiven Spieler

Outputcodierung:

  • ursprünglich 1 Neuron -> Siegwahrscheinlichkeit/Value/Bewertung der Brettsituation
    • später 4 Neuronen
      • 1 Neuron für einfachen Sieg
      • 1 Neuron für zweifachen Sieg
      • 1 Neuron für weiß gewinnt
      • 1 Neuron für schwarz gewinnt

Zuggenerator:

  • Rekursive Generierung aller gültigen Folgezüge
  • damit Züge bei verschiedenen Würfelaugen nicht vergessen werden: erneuter Durchlauf mit vertauschter Augenzahl
  • so entstehen 20-60 gültige Züge pro Würfelkombination

Aktivitätsausbreitung und Lernen:

  • Outputaktivität der Hidden-Neuronen:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y_i= \frac{1}{1+e^{-\sum_j w_{ij} \cdot x_j}}}
  • TD-Lernalgorithmus:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline w_{t+1} = \underline w_{t} + \beta \left ( r_{t+1} + \gamma V(t+1) - V(t) \right )\underline e_t}
  • Update der eligibility-Traces:
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \underline e_t = \gamma \cdot \lambda \cdot \underline e_{t-1} + \nabla_{\underline w_t} \cdot V(s_t)} wobei
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \nabla_{\underline w_t} V(s_t)} ... Beitrag des Gewichtes w zu V
  • Gewichtsinitialisierung zufällig (damit ist kein Regelwissen initial vorhanden)
  • gelernt wird alternierend beidseitig (das Netz spielt gegen sich selbst abwechselnd als schwarzer und weißer Spieler)

Learning Classifier Systems

  • LCS kommen aus der Symbolischen KI
  • Sind entstanden dadurch das Expertensysteme mit Genetischen Algortihmen verbunden wurden um Regeln schneller zu erlernen.
  • Ein LCS besteht aus drei Hauptkomponenten
    • Ein Regel und Nachrichten System
      • Regelt die Interaktion mit der Umgebung
      • Übersetzt die reellen Zahlen der Umgebung in abstrakte Nachrichten
      • Repräsentiert die aktuelle Policy welche in Form von Klassifizierern vorliegt
    • Ein Credit Aufteilungssystem (zum Bewerten der Wissensbasis)
      • Verteil die eingehenden Rewards auf alle Regeln
      • Realisiert die Lern-Policy
    • Ein System zum entwickeln von Klassifizieren
      • Aufgabe ist das explorieren und spezialisieren der Zustand-Aktionsraum Repräsentation
  • Detektoren
    • erkennen Features in complexen reellwertigen eingaben von der Umgebung
    • Übersetzen diese Eingaben in einen Vektor aus {1,0}
  • Classifier
    • Jeder Classifier beschreibt eine Regel
      • Jede Regel besteht aus einer Menge von Bedingungen (Vektor von {0,1,#} # ... Joker)
      • Eine Aktion ein Vektor von {0,1}
      • Eine Stärke
  • Effektors
    • Übersetzen Nachrichten in Aktionen die Ausgeführt werden sollen
  • Aktionsauswahl
    • Alle Nachrichten der Umgebung werden gegen alle classifier geprüft
    • Auf einen Zustand können mehrere Regeln zutreffen
    • Alle Classifier auf die eine Nachricht zutrifft nehmen an einer Auktion teil
      • Jeder passende Classifier muss dafür ein gebot abgeben das sich nach seiner Stärker und seiner spezifizität richtet
        Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle B_i(t) = k \cdot S_i(t) \cdot f(specificity) }
  • Creditverteilung
    • Alle Clasifier müssen ihr Gebot bezahlen
      Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i(t+1) = S_i(t) - B_i(t) \cdot Tax_{bid} }
    • Jeder Classifier muss eine Kopfsteuer Zahlen
      Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i(t+1) = S_i(t) - S_i(t) \cdot Tax_{life} }
    • Der Gewinnende Klassifier muss sein Gebot bezahlen und bekommt das Reward sowie einen Anteil des folgenden Gebotes
      Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S_i(t+1)= S_i(t) + R_i(t+1) - B_i + \gamma \cdot B_j(t+1) }


  • Anpassung der Classifier
    • Deterministisch
      • Wenn kein Classifier auf die Nachricht passt wird einfach ein neuer angelegt mit einer zufälligen Aktion
      • Die Stärke wird auf den Durchschnitt aller bereits vorhandenen Regeln gesetzt
    • Genetischer Algorithmus
      • Die Stärksten Classifiert werden ausgewählt
      • Werden gemischt (Übernehmen von Teilen aus dem einen und dem anderen CLassifier um einen neuen zu erstellen)
      • Und Mutiert (Werte werden zufällige geändert)

Multiagenten Systeme

Wesentliche Arten von Agenten

  • Reaktiv
    • feste Abbildung von Sensoren auf Aktoren
  • Operand
    • Verfügen über innere Zustände und können Wissen über folgen speichern
  • Planend / deliberativ
    • verfügen über Umweldmodell und wägen Folgen ihrer Handlung ab
  • Hybride
    • Kombinieren Reaktives und deliberatives Verhalten
  • Kognitive
    • Verfügen über komplexe Situationsbeschreibungen und können somit zwischen verschiedenen Zielen abwägen

Arten von Multi-Agenten Systemen

  • Koordinierung mehrerer physischer Agenten (Rudel/Schwärme)
  • Koordinierung mehrerer Agenten in einem Körper

MAS vs. Monolith

  • MAS
    • Vorteile:
      • bessere Teilperformanze, skalierbar, Beherrschbar
      • einfache Agenten
      • einfache Erweiterbarkeit
    • Nachteile
      • Festlegung der Agenten
      • geeignete Zerlegung des Problems muss gefunden werden
      • geeignete Koordination der Agenten
      • Reward-Dekomposition notwendig
  • Monolith
    • Vorteile:
      • optimale Performanze
      • notwendige Abbildung zwischen Sensoren und Aktoren wird selbst gefunden
      • Teilaspekte und Koordinierung können durch Designer gewichtet werden
    • Nachteile:
      • kompliziertes Design und verteilen des Rewards
      • kombinatorische Explosion des Zustandsraumes
      • schlechte Erweiterbarkeit

"Mr. Smith, wo sind sie?" oder auch "Koordinierung der Agenten"

  • Grundarten:
    • Wettbewerb
    • Kooperation
    • Kombination von Kooperatiuon und Wettbewerb

Zentrale Kontrollstrategie

  • Agenten haben kein Wissen über die Ziele der anderen Agenten
  • nur eine Zentrale Struktur besitzt Wissen ober die Agenten (a.k.a. "M")
  • Agenten liefern Aktionsvorschläge
  • Zentrale Struktur realisiert die Auswahl der resultierenden Aktionen

Verteilte Kontrollstrategie

  • Agenten haben Wissen über gegenseitige Existenz
  • Agenten verhandeln über resultierende Aktion
  • Koordination mittels Blackboard
    • Agenten schreiben ihre Vorschläge auf das Blackboard
    • Agenten können die Vorschläge der anderen Agenten einsehen und ihre Anpassen
    • Selektion der auszuführenden Aktion erfolgt am Blackboard

Hierachische organisierte Agenten

  • Subsumption Architektur
    • strenge Hierachie vom Designer festgelegt
    • Jeder Agent entscheidet anhand der aktuellen Situation, ob sein Aktionsvorschlag auszuführen ist
    • indirekte Kommunikation zwischen den Agenten durch das Regelsystem
    • starre Verhaltensgenerierung entsprechend dem Regelsystem
    • Neudesign erforderlich wenn neue Agenten eingefügt werden sollen

Gleichberechtigte Agenten

  • strenge lokale Kooperation zwischen den Agenten
  • Überlagerung aller Aktionsvorschläge zu einer resultierenden Aktion

Adaptive Aktionsauswahl mittels W-Lernen

--> Siehe nächstes Kapitel

W-Lernen

  • Wertesystem welches die zu erwartende Gesamt-Belohnung bzw -Verlust bei der Aktionsauswahl berücksichtigt
  • Damit kann ein Agent einen kleinen Verlust tolerieren während er damit einen großen Verlust für das gesamte System verhindert
  • Die Q-Werte werden genutzt um die W-Werte zu ermitteln
  • Agenten sind selbständig
  • es können Aktionen ausgewählt werden die kein Agent vorgeschlagen hat
  • leicht um weitere Agenten erweiterbar
  • höhere Robustheit gegenüber dem Ausfall von Angenten
  • Je nach Policy erfolgt die Auswahl des gewinnenden Agenten, bzw. Aktionen anhand der W-Werte
    • Praktisch immer Auswahl des maximalen W-Wert
  • Ermittlung der W-Werte
    • gleiche Aktionsräume => Berechnung der Werte aus den Q-Werten => statische W-Werte
    • unterschiedliche Aktionsräume => RL-ähnlicher Lernprozess => dynamsiche W-Werte

statische W-Werte

  • alle notwendigen Werte sind schon bekannt (da aus Q-Werte berechnet wird)
  • kein Zeitaufwendiges Lernen notwendig
  • leichte Auswertung
  • Vier grundsätzliche realiserbare Auswahlstrategien
    1. Maximize best Happiness
      • egositisches Konzept
        Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_i(s) = \max_{a \in A} Q_i(s,a) }
    2. Maximize collective Happiness
      • Suche nach dem größten Gesamtgewinn aller Agenten bei Auswahl einer bestimmten Aktion
        Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_a(s) = \sum_{i} Q_i(s,a)}
    3. Maximize best Profit
      • Suche nach dem größten Profit (maximaler Gewinn bei kleinstem Verlust)
    4. Minimize worst Unhappiness
      • Suche nach dem größten Verlust um ihn zu Vermeiden
      • Idee ist die Auswahl des Agenten, der durch seine Nichtausführung den größten Verlust einfahren würde (bzw. Gewinn entgeht)
        Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_{ik}= Q_i(s,a_{suggested}) - Q_i(s,a_k) }

dynamische W-Werte

  • Agent lernt die Folgen der Aktionsausführung eines anderen Experten
  • Agent beobachtet, in welchen Folgezustand die Aktion eines anderen Agenten ihn gebracht hat un ermittelt den ihm dadurch entstandenen Verlust gegenüber seiner Aktion
  • W-Werte werden aus realerzielten Rewards gelernt
  • Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle W_{ik}(s) \leftarrow Q_i(s,a_{sugg}) - (r_i + \gamma \cdot \max_bQ_i(s',b)) }
  • Lernen erfolgt nur für die Verlierer des Wettkampfs
  • W-Lernen wählt damit den Agenten aus der den kleinsten Verlust für die anderen Agenten verursacht
  • Vorteil:
    • anwendbar auf beliebige Agenten mit unterschiedlichen Aktionsräumen
    • beliebige Agentenanzahl
  • Nachteil:
    • iteratives Lernen der W-Werte bedingt wiederholtes Erleben von Aktionen