transentis consulting

Das Beer Game mit künstlicher Intelligenz spielen

Eine Einführung in die Agentbasierte Modellierung und das Reinforcement Learning, angewandt auf das Beer Game
  • Oliver Grasl
    Oliver Grasl
    Sunday, May 31, 2020
Eine Einführung in die agentbasierte Modellierung und das Reinforcement Learning, angewandt auf das Beer Game
Das berüchtigte Beer Distribution Game wurde ursprünglich in den späten 1950er Jahren von Jay Forrester am MIT entwickelt, um die Konzepte dynamischer Systeme vorzustellen. In diesem Fall ist das dynamische System eine Lieferkette, die Bier von einer Brauerei an den Endverbraucher liefert. Was das Spiel so faszinierend macht, ist, dass die Struktur der Lieferkette und die Spielregeln einfach sind, das resultierende Verhalten jedoch ziemlich komplex ist.
Das Beer Game ist gut dokumentiert:
Wir haben hier alle unsere Beer Game Ressourcen gesammelt.
Die agentenbasierte Modellierung ist ein Ansatz zur Erstellung von Simulationsmodellen von realen Systemen. Bei der agentenbasierten Modellierung werden Objekte durch Agenten erfasst, die ein Verhalten in Reaktion auf interne oder externe Ereignisse zeigen. Wir werden Agenten verwenden, um die Spieler im Beer Game zu repräsentieren.
Sobald wir die Agenten haben, können wir verschiedene Bestellstrategien untersuchen und versuchen, eine Strategie zu finden, die es den Agenten ermöglicht, das Bierspiel zu spielen und die Spielleistung zu optimieren.
Wir haben ein GitHub-Repository für das Beer Game eingerichtet, das alle Simulationsmodelle und einige Jupyter Notebooks enthält, die erklären, wie man sie verwendet. Insbesondere gibt es ein Notizbuch An Agent-based Approach to Modeling The Beer Game (Ein agentenbasierter Ansatz zur Modellierung des Bierspiels), das durch die verschiedenen Phasen der Simulation führt.
Aber mit den Agenten können wir etwas noch Interessanteres machen: Anstatt den Agenten eine Reihe von vordefinierten Verhaltensweisen zu geben, können wir die Agenten mithilfe von Machine Learning-Techniken, insbesondere einer Technik, die als Reinforcement Learning bekannt ist, trainieren, das Beer Game zu spielen.
Reinforcement Learning ist eine Machine Learning-Technik, die sich auf das Lernen aus Interaktion konzentriert. Der Maschine wird nicht gesagt, welche Aktion sie ausführen soll, sondern sie muss durch Ausprobieren herausfinden, welche Aktion die beste Wirkung haben.

Eine kurze Einführung in das Beer Game

Um die Herausforderung des Managements der Lieferkette im Bierverteilung zu verstehen, lassen Sie uns einen genaueren Blick auf ihre Struktur werfen: Die Lieferkette führt von der Brauerei über einen Verteiler und Großhändler zum Wiederverkäufer, der das Bier an seine Kunden, die Endverbraucher, verkauft.
Ziel des Spiels ist es, die Nachfrage des Verbrauchers nach Bier direkt oder zumindest mit möglichst geringer Verzögerung zu befriedigen und dabei das Inventar jedes Spielers so klein wie möglich zu halten.
Die folgende Skizze veranschaulicht die Lieferkette und den damit verbundenen Informationsfluss:
Zu Beginn liegt die Verbrauchernachfrage nach Bier stabil bei 100 Einheiten pro Woche und die gesamte Lieferkette befindet sich in einem stabilen Zustand. Jedes Mitglied der Lieferkette hat ein Inventar von 400 Einheiten.
Die Regeln des Spiels sind einfach - in jeder Runde führt jeder Spieler die folgenden vier Schritte aus:
  • Check deliveries (Lieferungen prüfen). Er prüft, wie viele Biereinheiten von seinem Lieferanten in der Lieferkette an ihn geliefert werden.
  • Check incoming orders (Bestelleingang prüfen). Er prüft, wie viele Biereinheiten sein Kunde in der Lieferkette bestellt hat.
  • Deliver beer (Bier liefern). Er liefert so viel Bier, wie er kann, um die Nachfrage der Kunden zu befriedigen (Hinweis: In unserer Implementierung des obigen Spiels wird dieser Schr
    itt automatisch für Sie ausgeführt).
  • Place outgoing order (Laufende Bestellung aufgeben). Der schwierige Schritt besteht darin, zu entscheiden, wie viele Biereinheiten der Spieler von seinem Lieferanten benötigt, um sein Inventar aufrechtzuerhalten und sicherzustellen, dass er genug Bier hat, um zukünftige Nachfrage zu erfüllen.
Wenn Sie das Spiel noch nie gespielt haben oder die Spieldynamik im Detail verstehen wollen, lesen Sie unbedingt den begleitenden Beitrag Das Beer Game verstehen.
Nachdem wir nun die Struktur des Spiels kennen, wollen wir uns mit der agentenbasierten Modellierung beschäftigen und sehen, wie wir Agenten zum Spielen verwenden können.

Eine kurze Einführung in die agentenbasierte Modellierung

Das Grundkonzept hinter agentenbasierten Modellen ist ganz einfach:
  • Eine Umgebung wird mit einer Menge von Agenten bevölkert.
  • Agenten und die Umgebung haben jeweils einen Satz von (numerischen) Eigenschaften und jeder Agent muss sich immer in einem definierten internen Zustand befinden (z.B. aktiv, faul, defekt, ...).
  • Agenten können Aktionen ausführen und miteinander und mit der Umgebung interagieren, indem sie Signale senden - die Agenten reagieren auf diese Ereignisse, indem sie ihre Eigenschaften aktualisieren und/oder ihren Zustand ändern.
Welche Ereignisse Agent sendet oder empfängt, muss nicht deterministisch sein - Sie können dies z. B. von einer Wahrscheinlichkeitsverteilung abhängig machen, die auf dem aktuellen Zustand des Agenten und seiner Umgebung und die Aktion, für die er sich entscheidet, basiert.
Agentenbasierte Simulationen laufen in Zeitschritten ab - in jedem Zeitschritt empfangen alle Agenten zunächst die Ereignisse, die an sie gesendet wurden, dann handeln sie und senden neue Ereignisse. Typischerweise werden die Ereignisse dann im nächsten Zeitschritt empfangen, obwohl in einigen Fällen "sofortige" Ereignisse sinnvoll sind.
Um eine agentenbasierte Simulation zu erstellen, müssen wir also:
  • Die relevanten Agenten identifizieren
  • Die Eigenschaften der Agenten identifizieren
  • Eine Aktionsmethode, die beschreibt, was der Agent in jedem Zeitschritt tut, z. B. interne Aufgaben ausführen und Ereignisse an andere Agenten senden
  • Handler für jede Art von Ereignis, auf die Ihr Agent reagieren soll, definieren
  • Für jeden Agenten einen Initialisierer, der den Anfangszustand des Agenten festlegt, umsetzen
Die Definition des Modells ist noch einfacher:
  • Die Umgebungseigenschaften definieren und diese bei Bedarf aktualisieren
  • Dem Modell sagen, welche Arten von Agenten es gibt
Um die Simulation zu konfigurieren, müssen wir dann nur noch die Anfangswerte der Eigenschaften festlegen und die ersten Agenten instanziieren.
Lassen Sie uns das Bierspiel mit Agenten modellieren. Jeder Spieler im Spiel wird durch Agent modelliert, sodass wir fünf Agenten haben: Verbraucher und die Agenten, die Teil der Lieferkette sind, d. h. Einzelhändler, Großhändler, Verteiler und Brauerei.
Die Lieferkettenagenten sind trotzdem wichtig - sie haben einen internen Zustand, der zeigt:
  • Inventar, d. h. wie viel Bier der Agent auf Lager hat.
  • Ausstehende Bestellung, d.h. wie viel Bier der Agent bei seinem Lieferanten bestellt, aber noch nicht erhalten hat.
  • Rückstand, d.h. wie viel Bier der Verbraucher des Agenten bestellt hat, das der Agent aber noch nicht geliefert hat.
In jedem Zeitschritt muss der Agent auf die folgenden Ereignisse reagieren:
  • Lieferung. Das Bier, das vom Lieferanten des Agenten geliefert wird.
  • Bestellung. Das Bier, das vom Kunden des Agenten bestellt wird.
Am Ende jedes Zeitschrittes, nachdem der Agent Lieferungen und Bestellungen erhalten hat, muss er eine Bestellentscheidung treffen, die dann als Bestellung an seinen Lieferanten weitergegeben wird.
Die Erfahrung zeigt, dass bei einem typischen Spiel die Anzahl der von den Spielern aufgegebenen Bestellungen viel höher ist als nötig: Die Grafik unten zeigt, was passiert, wenn der Verbraucher seine Bestellung nur einmal zu Beginn des Spiels von 100 Biereinheiten auf 400 Einheiten ändert und sie dann bei der neuen Einstellung belässt. Dies führt zu einem riesigen "Peitschenhieb", der sich durch die Lieferkette zieht und die Brauerei dazu veranlasst, in Spitzenlastzeiten über 30.000 Biereinheiten zu produzieren!
Mit diesem Bestellverhalten liegen die Lieferkettenkosten weit vom Ziel entfernt:
Es ist eigentlich ziemlich einfach, Bestellpolitiken zu definieren, die zu einem verbesserten Verhalten führen (lesen Sie am besten Das Beer Game verstehen für Details).
Eine einfache Strategie ist die Verwaltung des Bestellsaldo, d. h. der Differenz zwischen eingehenden Bestellungen (d.h. denen die vom Kunden kommen) und ausgehenden Bestellungen (d.h. denen, die an den Lieferanten gehen). Einfach gesagt, würden wir erwarten, dass der Saldo eine Konstante ist, die dem gewünschten Inventar entspricht, eine sinnvolle Bestellstrategie wäre dann:
Int(Max(Eingehende Bestellung+(2 * Eingehende Bestellung + Zielinventar - Bestellungsinventar)/Inventaranpassungszeit),0))
Die folgenden Diagramme zeigen, wie sich Bestellungen, Inventare und Kosten bei dieser Strategie entwickeln.
Diese Politik ist schön einfach und fast schon gut genug, um das Ziel zu erreichen, die Lieferkettenkosten unter 30.000$ zu halten.
Ziel ist es nun, mithilfe von Machine Learning eine Bestellpolitik zu finden, die die aktuellen Lieferkettenkosten in der Nähe der Lieferkettenzielkosten hält, im Folgenden werden wir dies mit einem Reinforcement Learning-Ansatz tun.

Eine kurze Einführung in das Reinforcement Learning

Reinforcement Learning ist eine Machine Learning-Technik, die sich auf das Lernen aus Interaktion konzentriert: Agenten interagieren mit ihrer Umgebung gemäß ihrer "Aktionspolitik" und erhalten Belohnungen für ihre Aktionen. Das Ziel von Reinforcement Learning-Algorithmen ist es, die richtigen Aktionspolitiken zu lernen, d. h. Politiken zu finden, die die Belohnungen, die die Agenten für ihre Aktionen erhalten, maximieren.
Es gibt verschiedene Ansätze zum Reinforcement Learning und wir werden in diesem Notebook einen einfachen Ansatz verwenden, der als Q-Learning bekannt ist.
Beim Q-Learning hat jeder Agent eine "Q-Table" (Q-Tabelle), die die erwartete Gesamtbelohnung definiert, die ein Agent für das Ausführen einer bestimmten Aktion erhält, wenn er sich in einem bestimmten Zustand befindet. Agenten beginnen zunächst mit einer "leeren" Q-Table und lernen dann durch Versuch und Irrtum das richtige Verhalten.
Agenten beginnen mit einer "leeren" Q-Table und füllen diese dann durch Lernen durch Versuch und Irrtum. Bei jedem Schritt wählt ein Agent immer die Aktion, die zu der höchsten Belohnung führt.
Die folgenden Abschnitte tauchen ein wenig tiefer in die Mathematik hinter dem Reinforcement Learning ein. Dies ist recht anschaulich, weil es zeigt, wie man mit Unsicherheit umgehen kann und auch, wie man mit (extrinsischen) Belohnungssystemen umgeht - zwei Fähigkeiten, die in jedem Unternehmen sehr wichtig sind. Fühlen Sie sich frei, zum nächsten Kapitel zu springen, wenn Sie nicht am mathematischen Formalismus interessiert sind.
Die folgende Darstellung des Reinforcement Learnings lehnt sich eng an die Darstellung im bahnbrechenden Buch Reinforcement Learning von Richard S. Sutton und Andrew G. Barto an.
Um Reinforcement Learning berechenbar zu machen, müssen wir einen geeigneten Formalismus finden. Ein solcher Formalismus ist die Modellierung solcher Agent-Umwelt Interaktionen als Markow-Entscheidungsprobleme (MEPs).
In jedem Zeitschritt tt erhält der Agent eine Repräsentation des Umgebungszustandes, StSS_t \in \mathcal{S}, und wählt auf dieser Basis eine Aktion, AtAA_t \in \mathcal{A}. Einen Zeitschritt später erhält der Agent (teilweise) als Folge seiner Aktion eine Belohnung RtRRR_t \in \mathcal{R} \subset \mathbb{R}.
Die Wechselwirkung führt dann zu einer Trajektorie, die wie folgt aussieht: S0,A0,R1,S1,A1,R2,S2,A2,R3,...S_0,A_0,R_1,S_1,A_1,R_2,S_2,A_2,R_3,...
In einem endlichen MEP haben die Mengen von Zuständen, Aktionen und Belohnungen (S\mathcal{S}, A\mathcal{A} und R\mathcal{R} eine endliche Anzahl von Elementen und die Zufallsvariablen RtR_t und StS_t haben wohldefinierte Wahrscheinlichkeitsverteilungen, die nur vom vorhergehenden Zustand und der Aktion abhängen:
p(s,rs,a)=Pr{St=s,Rt=rSt1=s,At1=a}p\left(s',r \mid s,a\right) = Pr\{S_t=s', R_t=r \mid S_{t-1}=s, A_{t-1}=a\}
für alle s,sS,rRs',s \in \mathcal{S}, r \in \mathcal{R}, und aA(s)a \in \mathcal{A}(s). Die Function pp definiert die Dynamik des MEP, die eine Wahrscheinlichkeit für jede Wahl von ss und aa:
sSrRp(s,rs,a)=1,sS,aA(s)\sum_{s' \in \mathcal{S}} \sum_{r \in \mathcal{R}} p\left(s',r \mid s,a\right) = 1, \forall s \in \mathcal{S}, a \in \mathcal{A}(s)
Mit pp, können wir alles berechnen, was wir über das Verhalten eines Agenten wissen müssen, z. B. die Zustandsübergangswahrscheinlichkeiten:
p(ss,a)=Pr{St=sSt1=s,At1=a}=rRp(s,rs,a)p\left(s' \mid s,a\right) = Pr\{S_t=s'\mid S_{t-1}=s, A_{t-1}=a\}=\sum_{r \in \mathcal{R}} p\left(s',r \mid s,a\right)
Insbesondere können wir die erwartete Belohnung berechnen, wenn wir uns im Zustand ss und die Aktion aa wählen:
r(s,a)=E[RtSt1=s,At1=a]=rRrsSp(s,rs,a)r\left(s,a\right) = \mathbb{E} \lbrack R_t \mid S_{t-1}=s, A_{t-1}=a \rbrack = \sum_{r \in \mathcal{R}} r \sum_{s' \in \mathcal{S}} p\left(s',r \mid s,a\right)
Ziele und Belohnungen
Um unsere Agenten zum Lernen zu bringen, müssen wir nicht nur die Belohnung definieren, die ein Agent für das Ausführen einer Aktion erhält, sondern wir müssen den Agenten auch sagen, dass sie die Summe der Belohnungen über ihre Lebenszeit maximieren sollen, d. h. die Lebenszeitbelohnung.
Formal können wir das Ziel des Reinforcement Learning als Maximierung der erwarteten Lebenszeitbelohnung definieren, die wie folgt definiert ist:
GtRt+1+γRt+2+γ2Rt+3+=k=0γkRt+k+1G_t \doteq R_{t+1}+\gamma R_{t+2}+\gamma^2 R_{t+3} +\dots = \sum_{k=0}^\infty \gamma^k R_{t+k+1}
wo 0γ10 \leq \gamma \leq 1 ist Absizungssatz (der benötigt wird, um sicherzustellen, dass GG konvergiert in unendlichen MEP).
Beachten Sie, dass GG auch rekursiv definiert werden kann:
Gt=Rt+1+γGt+1G_t = R_{t+1}+\gamma G_{t+1}
Aktionspolitiken
Jetzt, da wir wissen, dass wir die lebenslange Belohnung optimieren möchten, müssen wir unserem Agenten helfen, eine optimale Politik zu erlernen. Eine Politik ist eine Zuordnung von Zuständen zur Wahrscheinlichkeit der Auswahl einer möglichen Aktion.
Wenn der Agent zum Zeitpunkt tt der Politik π\pi folgt, dann ist π(as)\pi(a \mid s) die Wahrscheinlichkeit, dass At=aA_t=a, wenn St=sS_t=s.
Beachten Sie, dass π\pi sich von der oben definierten Wahrscheinlichkeitsverteilung pp unterscheidet - die Wahrscheinlichkeitsverteilung pp gibt uns Informationen über die Umgebung, sie sagt uns, welche Belohnung der Agent für das Ausführen bestimmter Aktionen erhält und in welchen Zustand der Agent übergehen wird; die Wahrscheinlichkeitsverteilung π\pi gibt uns Informationen über den Agenten selbst, sie sagt uns die Wahrscheinlichkeit, dass ein Agent in einer bestimmten Situation eine bestimmte Aktion wählt.
Dies wird im folgenden Diagramm dargestellt.
Mit π\pi und pp können wir die Wahrscheinlichkeit berechnen, mit der ein Agent in einen bestimmten Zustand ss' übergeht, wenn er sich im Zustand ss befindet:
pπ(ss)=aπ(as)rp(s,rs,a)p_\pi (s' \mid s) = \sum_a \pi(a \mid s) \sum_{r} p\left(s',r \mid s,a\right)
und die erwartete Belohnung beim Übergang vom Zustand ss zur Zeit tt:
rπ(s)=Eπ[Rt+1St=s]=rraπ(as)sp(s,rs,a)r_\pi (s) = \mathbb{E}_{\pi}\lbrack R_{t+1} \mid S_t=s \rbrack = \sum_{r} r \sum_a \pi(a \mid s) \sum_{s'} p\left(s',r \mid s,a\right)
Wertfunktionen
Mithilfe der Aktionspolitik π\pi und der Umgebungsdynamik pp können wir nun den Wert berechnen, den wir von der Politik zu erzielen erwarten: Die Wertfunktion eines Zustands ss unter einer Politik π\pi, bezeichnet mit vπ(s)v_\pi (s), ist der erwartete Ertrag, wenn man in ss startet und danach π\pi folgt.
Für unsere MEP können wir vπv_\pi definieren durch:
vπ(s)Eπ[GtSt=s]=Eπ[k=0γkRt+k+1St=s],sSv_\pi (s) \doteq \mathbb{E}_{\pi}\lbrack G_t \mid S_t=s \rbrack = \mathbb{E}_{\pi}\lbrack \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t=s \rbrack, \forall s \in S
Wir können dann den Wert der Ausführung einer Aktion aa im Zustand ss unter einer Politik π\pi wie folgt definieren:
qπ(s,a)Eπ[GtSt=s,At=a]=Eπ[k=0γkRt+k+1St=s,At=a],sS,aAq_\pi (s,a) \doteq \mathbb{E}_{\pi}\lbrack G_t \mid S_t=s, A_t=a \rbrack = \mathbb{E}_{\pi}\lbrack \sum_{k=0}^\infty \gamma^k R_{t+k+1} \mid S_t=s, A_t=a \rbrack, \forall s \in S, a \in A
qπq_\piwird die Aktionswertfunktion für die Politik π\pi genannt. Sie stellt den erwarteten Wert unserer Politik dar, wenn wir im Zustand ss beginnen, dann die Aktion aa ausführen und danach der Politik π\pi folgen. Der wichtige Punkt hier ist, dass qπq_\pi nicht nur die unmittelbare Belohnung erfasst, die wir für unsere nächste Aktion erhalten, sondern auch die erwartete Belohnung, die der Agent danach erhalten wird.
Bellman-Gleichung
Angesichts der rekursiven Natur der Lebenszeitbelohnung können wir die Frage beantworten, wie der Wert des aktuellen Zustands eines Agenten mit dem Wert seines zukünftigen Zustands zusammenhängt, wenn er einer Politik folgt und jetzt eine Aktion ausführt: Schließlich ändert sich aus konzeptioneller Sicht nichts, sobald wir von ss zu ss' übergegangen sind.
vπ(s)Eπ[GtSt=s]=Eπ[Rt+1+γGt+1St=s]=Eπ[Rt+1St=s]+γEπ[Gt+1St=s]\begin{aligned} v_\pi (s) & \doteq \mathbb{E}_\pi \lbrack G_t \mid S_t=s \rbrack \\ & = \mathbb{E}_{\pi}\lbrack R_{t+1}+\gamma G_{t+1} \mid S_t=s \rbrack \\ & = \mathbb{E}_{\pi}\lbrack R_{t+1} \mid S_t=s \rbrack +\gamma \mathbb{E}_{\pi}\lbrack G_{t+1} \mid S_t=s \rbrack \end{aligned}
Der erste Summand ist hier einfach die Belohnung, die wir erwarten, wenn wir eine Aktion ausführen und uns von ss zu ss' bewegen, genauer gesagt:
rπ(s)=Eπ[Rt+1St=s]=rraπ(as)sp(s,rs,a)r_\pi (s) = \mathbb{E}_{\pi}\lbrack R_{t+1} \mid S_t=s \rbrack = \sum_{r} r \sum_a \pi(a \mid s) \sum_{s'} p\left(s',r \mid s,a\right)
Der zweite Teil ist etwas komplizierter - er definiert die erwartete Lebenszeitbelohnung ab dem Zeitpunkt t+1t+1, aber beginnend zum Zeitpunkt tt im Zustand ss. Um dies zu berechnen, müssen wir die Wertfunktion für jeden möglichen zukünftigen Zustand ss' berechnen, gewichtet mit der Wahrscheinlichkeit, diesen Zustand tatsächlich zu erreichen:
Eπ[Gt+1St=s]=svπ(s)pπ(ss)=svπ(s)aπ(as)rp(s,rs,a)\mathbb{E}_{\pi}\lbrack G_{t+1} \mid S_t=s \rbrack = \sum_{s'} v_\pi (s') p_\pi (s' \mid s) = \sum_{s'} v_\pi (s') \sum_a \pi(a \mid s) \sum_{r} p\left(s',r \mid s,a\right)
Der zweite Teil der Gleichung wird im folgenden Diagramm dargestellt.
Setzen wir diese Begriffe zusammen und ordnen die Summen neu an, wir enden mit:
vπ(s)=aπ(as)srp(s,rs,a)[r+γvπ(s)]v_\pi (s) = \sum_a \pi(a \mid s)\sum_{s'} \sum_{r} p\left(s',r \mid s,a\right)\lbrack r+\gamma v_\pi (s')\rbrack
Dies ist bekannt als die Bellman-Gleichung für vπv_\pi. Sie drückt eine Beziehung zwischen dem Wert eines Zustands und den Werten der Folgezustände aus: Der Wert des Startzustands muss gleich dem (abgezinsten) Wert des erwarteten nächsten Zustands sein, plus der erwarteten Belohnung, um diesen Zustand zu erreichen.
Optimale Politiken und die optimale Wertfunktion
Da wir nun über Politiken und Wertfunktionen Bescheid wissen, können wir versuchen, die bestmögliche, optimale Wertfunktion zu finden, d. h. diejenige, die langfristig die höchste Belohnung erzielt.
Mithilfe von Wertfunktionen können wir eine Reihenfolge von Politiken definieren: ππ\pi \geq \pi' nur wenn vπ(s)vπ(s)v_\pi (s) \geq v_{\pi'} (s) für alle sSs \in \mathcal{S}.
Es wird immer mindestens eine Politik geben, die besser als oder gleich allen anderen Politiken ist - dies ist eine optimale Politik. Bezeichnen wir diese mit π\pi_*, die die optimale Zustandswertfunktion vv_* hat, definiert als:
v(s)maxπvπ(s)v_* (s) \doteq \max\limits_\pi v_\pi (s)
Optimale Politiken haben die gleiche optimale Aktionswertfunktion qq_*, definiert als
q(s)maxπqπ(s,a)=E[Rt+1+γv(St+1)St=s,At=a]\begin{aligned} q_* (s) & \doteq \max\limits_\pi q_\pi (s,a) \\ & = \mathbb{E}\lbrack R_{t+1}+\gamma v_* (S_{t+1}) \mid S_t=s, A_t=a \rbrack \end{aligned}
Da vv_* die Wertfunktion für eine Politik ist, muss sie die Bellman-Gleichung erfüllen. Da es sich jedoch um die optimale Wertfunktion handelt, können wir diese tatsächlich in einer speziellen Form schreiben, ohne auf eine bestimmte Politik Bezug zu nehmen. Diese Form wird die Bellman-Optimalitätsgleichung genannt:
v(s)=maxπqπ(s,a)=maxaEπ[Rt+1+γGt+1St=s,At=a]=maxaEπ[Rt+1+γv(St+1)St=s,At=a]=maxas,rp(s,rs,a)[r+γv(s)]\begin{aligned} v_* (s) & = \max\limits_\pi q_\pi (s,a) \\ & = \max\limits_a \mathbb{E}_{\pi_*}\lbrack R_{t+1}+\gamma G_{t+1} \mid S_t=s, A_t=a \rbrack \\ & = \max\limits_a \mathbb{E}_{\pi_*}\lbrack R_{t+1}+\gamma v_* (S_{t+1}) \mid S_t=s, A_t=a \rbrack \\ &= \max\limits_a \sum_{s', r} p\left(s',r \mid s,a\right)\lbrack r+\gamma v_* (s')\rbrack \end{aligned}
Intuitiv drückt die Bellman-Optimalitätsgleichung die Tatsache aus, dass der Wert eines Zustands unter einer optimalen Politik gleich dem erwarteten Ertrag für die beste Aktion aus diesem Zustand sein muss.
Die Bellman-Optimalitätsgleichung für qq_* ist:
q(s,a)=E[Rt+1+γmaxaq(St+1,a)St=s,At=a]=s,rp(s,rs,a)[r+γmaxaq(s,a)]\begin{aligned} q_* (s,a) & = \mathbb{E}\lbrack R_{t+1}+\gamma \max\limits_{a'} q_* (S_{t+1},a') \mid S_t=s, A_t=a \rbrack \\ &= \sum_{s', r} p\left(s',r \mid s,a\right)\lbrack r+\gamma \max\limits_{a'} q_* (s',a')\rbrack \end{aligned}
Lösung der Bellman-Gleichung:Temporal Difference Learning/Q-Learning
Reinforcement Learning läuft dann im Wesentlichen darauf hinaus, die Bellman-Optimalitätsgleichung zu lösen. Für endliche MEP wird es immer eine solche Lösung geben - denn die Bellman-Optimalitätsgleichung definiert ein System von Gleichungen, eine für jeden Zustand. Wenn es also nn Zustände gibt, hat man am Ende nnGleichungen in nn Unbekannten.
Sobald man vv_* hat, ist es einfach, die optimale Politik abzuleiten: Für jeden Zustand ss gibt es mindestens einen Zustand, für den das Maximum in der Bellman-Optimalitätsgleichung erhalten wird. Jede Politik, die nur diesen Aktionen eine Wahrscheinlichkeit ungleich Null zuweist, ist eine optimale Politik.
Wenn Sie qq_* haben, ist die Wahl einer optimalen Politik noch einfacher - Sie müssen einfach eine Aktion finden, die q(s,a)q_* (s,a) maximiert:
π(as)>0,aargmaxaq(s,a)π(as)=0,aargmaxaq(s,a)\begin{aligned} \pi_* (a \mid s) & > 0, a \in argmax_a q_*(s,a) \\ \pi_* (a \mid s) & = 0, a \notin argmax_a q_*(s,a) \end{aligned}
Da der Zustandsraum extrem groß sein kann, ist es selten praktisch, eine genaue Lösung für vv_* oder qq_* zu finden. Glücklicherweise gibt es eine Reihe von Ansätzen, um ungefähre Lösungen zu finden.
Eine Möglichkeit, vv zu schätzen, ist die Verwendung eines Monte-Carlo-Ansatzes: Wir beginnen mit einer anfänglichen Näherung VV für vv (d.h. für die erwartete Gesamtbelohnung, die diesem Zustand folgt) und durchlaufen dann unsere Simulation eine große Anzahl von Malen - jedes Mal, wenn wir die Simulation laufen lassen, wandern wir durch eine andere Trajektorie, die durch π\pi_* und die Umgebungsdynamik pp definiert ist.
Während jedes Laufs wird der aktuelle Wert für GtG_t (d. h. die tatsächliche Gesamtbelohnung nach diesem Zustand) für jeden Zustand und Zeitschritt zwischengespeichert. Am Ende des Laufs aktualisieren wir V(St)V(S_t) anhand der folgenden Formel, wobei α\alpha eine Konstante ist, die definiert, wie schnell wir uns auf den neuen Wert zubewegen:
V(St)V(St)+α[GtV(St)]V(S_t) \gets V(S_t) + \alpha \lbrack G_t - V(S_t) \rbrack
Der Monte-Carlo-Ansatz funktioniert gut, aber er hat ein Problem: Sie müssen bis zum Ende jeder Simulation warten, um GtG_t tatsächlich zu berechnen, was bedeutet, dass dieser Prozess sehr langsam ist.
Glücklicherweise gibt es einen viel schnelleren Ansatz, der es uns erlaubt, VV nach jedem Zeitschritt zu aktualisieren. Dieser Ansatz funktioniert dank der rekursiven Natur der Bellman-Gleichung.
Wenn wir uns daran erinnern, dass Gt=Rt+1+γGt+1G_t = R_{t+1}+\gamma G_{t+1}, können wir die folgende Formel verwenden, um VV nach jedem Zeitschritt zu aktualisieren:
V(St)V(St)+α[Rt+1+γV(St+1)V(St)]V(S_t) \gets V(S_t) + \alpha \lbrack R_{t+1}+\gamma V(S_{t+1}) - V(S_t) \rbrack
Dieser Lernansatz wird als Temporal Difference Learning bezeichnet, weil er Werte von VV vergleicht, die durch eine (kurze) zeitliche Differenz getrennt sind.
In diesem Notizbuch konzentrieren wir uns auf eine Variante von Temporal Difference Learning, die als Q-Learning bekannt ist, weil sie eine Lösung für qq_* anstelle von vv_* findet:
Q(St,At)Q(St,At)+α[Rt+1+γmaxaQ(St+1,a)Q(St,At)]Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha \lbrack R_{t+1}+\gamma \max\limits_a Q(S_{t+1},a) - Q(S_t,A_t) \rbrack
Unter dieser Voraussetzung können wir den grundlegenden Q-Learning-Algorithmus wie folgt definieren:
Beginnen Sie mit einem anfänglichen (zufälligen) Q(s,a)Q(s,a) und stellen Sie sicher, dass Q(terminalstate,.)=0Q(terminal state,.) = 0
Lassen Sie die Simulation eine große Anzahl von Malen (Episoden) laufen, mit der folgenden Zyklus für jede Episode:
  1. Initialisieren Sie S
  2. Erstellen Sie einen Zyklus für jeden Schritt der Episode:Wählen Sie A aus S mit ϵ\epsilon-gierige Politik basierend auf Q
    1. Führen Sie Aktion A aus, beobachten Sie R, S'
    2. Q(St,At)Q(St,At)+α[Rt+1+γmaxaQ(St+1,a)Q(St,At)]Q(S_t,A_t) \gets Q(S_t,A_t) + \alpha \lbrack R_{t+1}+\gamma \max\limits_a Q(S_{t+1},a) - Q(S_t,A_t) \rbrack
    SSS \gets S'
  3. Bis S endständig ist oder die Simulation ein vordefiniertes Ende erreicht
Wir verwenden die ϵ\epsilon-gierige Politik in Schritt 2.A, um sicherzustellen, dass unser Algorithmus nicht in einem lokalen Optimum blockiert wird: Wir verwenden ein kleines ϵ>0\epsilon > 0, das eine Wahrscheinlichkeit definiert, dass wir eine zufällige Aktion anstelle einer durch unsere Politik definierten Aktion wählen werden(ϵ\epsilon-gieriger-Ansatz).
Die Schrittgröße α(0,1]\alpha \in (0, 1\rbrack definiert, wie schnell wir uns von unserem aktuellen Wert von QQ zu einem neuen Wert bewegen und γ\gamma ist der Abzinsungsfaktor.

Anwendung von Q-Learning auf das Beer Game

Wenden wir nun die obige Theorie auf unsere Bierspiel-Agenten an. Unsere "Erkenntnisse" bestehen daraus, die richtigen Werte für die Funktion Q(S,A)Q(S,A) zu finden, die dem Agenten sagt, welche Aktion er ausführen soll, wenn er sich im Zustand A befindet.
Wir setzen ϵ=0.1\epsilon=0.1 und α=0.2\alpha=0.2. Da das Bierspiel über eine endliche Menge von 24 Runden läuft, können wir γ=1\gamma=1 setzen.
Wir speichern QQ in einer Q-Table, die im Wesentlichen eine Matrix ist, die durch den Zustand des Agenten und mögliche Aktionen indiziert ist. Für jeden Eintrag speichern wir den Wert Q(S,A)Q(S,A), der unsere Näherung an den optimalen Wert q(s,a)q(s,a) ist, d. h. den Wert, den wir erwarten zu erreichen, wenn wir uns im Zustand ssbefinden und die Aktion aa wählen.
Da die Anzahl der Zustände und Aktionen potenziell unendlich ist (Agent kann eine beliebige Menge Bier bestellen), verwenden wir eine sparse Q-Table, d. h. eine Tabelle, die leer ist und nur die Werte speichert, die vom Standardwert abweichen. Unsere Implementierung der Q-Table sparseQTable speichert Werte in einem Wörterbuch, dessen Schlüssel durch das Tupel (s,a)(s,a) definiert ist. Für das Bierspiel setzen wir den Standardwert auf 0, d. h. wir erwarten den Wert 0 bei einer Aktion, die wir noch nie ausprobiert haben.
Neben dem Hinzufügen und Lesen von Werten bietet die Q-Table zwei wichtige Methoden:
  • best_action (state) Diese Methode liefert die beste Aktion für einen gegebenen Zustand, d.h. die Aktion, die Q(S,A)Q(S,A) für einen gegebenen Zustand SSmaximiert.
  • max_action_value (state)   Diese Methode gibt den besten Wert zurück, der für einen gegebenen Zustand erreicht werden kann, d. h. Q(S,best_action(S))Q(S, best\_action(S)).
Jeder Lieferkettenagent hat seine eigene Q-Table und wir erfassen den Zustand des Agenten über einen einzigen Wert, nämlich den oben eingeführten Bestellsaldo.
Die Implementierung des eigentlichen Trainingsalgorithmus ist bemerkenswert einfach, weshalb wir den kompletten Code unten beigefügt haben.
Jeder Agent merkt sich seinen last_state und seine last_action, die gleich der Reihenfolge des Bieres ist, das der Agent platziert.
# read the last action value from the q table last_action_value = self.q_table.read_value( self.last_state, self.last_action ) # define the current state, which is the last order balance # modified by the incoming order current_state = self.agent.order_balance-self.agent.incoming_order # work out the next action value for the current state, which is the order # balance minus the new incoming order max_next_action_value = self.q_table.max_action_value((current_state,)) # work out the new action value based on the q-learning algorithm introduced above # - this is necessary because the reward is calculated at the end of the step, # i.e the update can only be done in the next timestep. new_action_value = ( last_action_value + self.agent.model.alpha*( self.agent.reward + self.agent.model.gamma * max_next_action_value - last_action_value ) ) # update the action value for the last state and the last action self.q_table.add_value(self.last_state, self.last_action, new_action_value) # now decide on which action to take, either by looking up the best value # in the q-table or by choosing a random number (𝜖-greedy approach) if random.uniform(0, 1) < self.agent.model.epsilon: # once in a while we choose a random amount to ensure # we are not locked into a local maximum order_amount = random.randint(0, round(1.5*self.agent.incoming_order)) else: # look up the best action for this state in the q-table order_amount = self.q_table.best_action((current_state,)) # now remember the state and action taken, # as a starting point for the next round self.last_state = (current_state,) self.last_action = order_amount
Wie Sie sehen, ist dies einfach eine konkrete Implementierung des oben definierten abstrakten Q-Learning-Algorithmus.
Als nächstes müssen wir uns Gedanken über die Belohnung machen, die wir den Agenten für ihre Leistung geben wollen. Wir müssen hier ziemlich vorsichtig sein, weil wir wissen, wie eine gute Bestellstrategie aussehen sollte, und wir wollen vermeiden, die Strategie direkt in die Belohnungen zu codieren.
Im Prinzip ist es recht einfach, Belohnungen zu definieren: Das Ziel des Spiels ist es, sowohl die Lieferkettengesamtkosten als auch die individuellen Lieferkettenkosten innerhalb bestimmter Ziele zu halten. Um dies auf effiziente Weise zu erreichen, ist es sinnvoll, einige Meilensteine auf dem Weg zu definieren und auch ein Spiel zu beenden, sobald die Agenten ihr Ziel verfehlen.
Natürlich müssen wir dann den Agenten eine hohe Belohnung geben, wenn sie diese Ziele erreichen - die Belohnungen werden am Ende jeder Runde in der end_round-Methode des Simulationsmodells verteilt.
if (agent.order_balance < 0 or agent.order_balance > 1400): self.game_over = True # run one more round to pickup the rewards, then stop self.game_over_round = time + 1 reward = -10000 elif agent.outgoing_order < agent.incoming_order: reward = -10000
Das einzige Problem hierbei ist, dass dies eine Belohnung ist, die ganz am Ende des Spiels kommt und die Dinge sehr schief gehen können, lange bevor wir das Ende erreichen.
Welche Hinweise können wir den Agenten mit auf den Weg geben?
Als erstes können wir die Agenten bestrafen, sobald sie das Spielziel verfehlen (was sehr früh im Spiel passieren kann). In diesem Fall bestrafen wir die Agenten und stoppen das Spiel für diese Episode, um zu vermeiden, dass die Q-Table mit unnötigen Informationen gefüllt wird. Wir bestrafen die Agenten auch, wenn sie nicht mindestens so viel bestellen wie die eingehende Bestellung.
if (agent.order_balance < 0 or agent.order_balance > 1400): self.game_over = True self.game_over_round = time + 1 # run one more round to pickup the rewards, then stop reward = -10000 elif agent.outgoing_order < agent.incoming_order: reward = -10000
Leider lässt uns das immer noch sehr viele mögliche Pfade, insbesondere angesichts der Tatsache, dass wir nicht nur einen Agenten, sondern eine ganze Versorgungsleitung trainieren. Um den Lernprozess ein wenig zu beschleunigen und unsere Q-Table klein zu halten, definieren wir also einige Meilensteine auf dem Weg:
if time == 3: if 750 >= agent.order_balance >= 600: reward += 2000 if time == 5: if 900 >= agent.order_balance >= 700: reward += 2000 if time == 10: if 1150 >= agent.order_balance >= 1000: reward += 2000 if time == 15: if 1250 >= agent.order_balance >= 1100: reward += 2000 if time == 20: if 1250 >= agent.order_balance >= 1150: reward += 2000
Schauen wir uns nun an, wie das in der Praxis funktioniert. Der folgende Code lässt das Bierspiel über zehn Episoden laufen und gibt die Gesamtbelohnung der Lieferkette zurück ... auf lange Sicht möchten wir, dass die Belohnung immer weniger negativ wird.
bptk.train_simulations( episodes=10, scenario_managers=["smBeergameQlOB"], scenarios=["train_agents"], agents=["controlling"], agent_states=["active"], agent_properties=["supply_chain_reward"], agent_property_types=["total"], return_df=False, progress_bar=True )
Mit dem trainierten Modell erhalten wir die folgenden Ergebnisse:
Wir können sehen, dass die Agenten nach zehn Trainingsepisoden nicht viel gelernt haben ... der Einzelhändler bestellt viel zu viel, was sehr hohe Kosten verursacht.
Tatsächlich dauert das Training der Agenten ziemlich viele Episoden und es sind etwa 50.000 Episoden nötig, um zufriedenstellende Ergebnisse zu erzielen (das ist immer noch wenig, wenn man die Anzahl der möglichen Pfade bedenkt, die im Grunde unendlich ist, weil die Agenten jede Menge Bier bestellen könnten). Da es 2-3 Stunden dauert, so viele Episoden laufen zu lassen (auf einem Macbook Pro mit 16 GB RAM), haben wir vortrainierte Q-Tables für 12500, 25000, 37500 und 50000 bereitgestellt, mit denen Sie experimentieren können (sehen Sie den Datenordner in unserem GitHub-Repository).
Jetzt können wir einen Blick auf die Ergebnisse werfen - nach 37.500 Trainingsepisoden sieht es schon ganz gut aus, aber die Kosten des Einzelhändlers sind immer noch ein wenig hoch.
Die Lieferkettengesamtkosten sind also noch etwas zu hoch:
Also lass uns sehen, was nach 50.000 Episoden passiert:
Nach 50.000 Trainingsrunden liegen die Gesamtkosten innerhalb des Ziels ebenso wie die Einzelkosten:
Es ist interessant, die Ergebnisse unserer regelbasierten Bestellpolitik mit dem Q-Learning-Ansatz zu vergleichen - der mit Q-Learning gelernte Ansatz schneidet tatsächlich besser ab. Während die 'Bestellsaldo'-Politik stabil ist und unabhängig vom Bestellverhalten eines Agenten in der Versorgungsleitung funktioniert, wird der Q-Learning-Algorithmus auf ein bestimmtes Bestellverhalten hin trainiert.

Zusammenfassung

In diesem Beitrag wurde das Konzept der agentenbasierten Simulation und des Reinforcement Learning vorgestellt und auf eine einfache Lieferkettensimulation angewendet, die das Beer Distribution Game simuliert.
Es veranschaulicht, wie Simulationen verwendet werden können, um ein Berechnungsmodell der Realität zu erstellen und wie Reinforcement Learning dann verwendet werden kann, um gute Entscheidungsstrategien zu finden - in unserem Fall schneidet die durch Reinforcement Learning gefundene Strategie tatsächlich besser ab als die regelbasierte Strategie.
Das Hauptproblem beim Reinforcement Learning besteht darin, die richtige Belohnungspolitik zu finden, und am Ende werden die Agenten auf diese Politik trainiert - für unsere Beer Game Simulation bedeutet dies, dass unsere Agenten nun gut darin sind, das Bierspiel für das gegebene Verhalten des Verbrauchers zu spielen. Aber wenn der Verbraucher sein Verhalten ändert, wissen die Agenten nicht, wie sie damit umgehen sollen. Das ist eigentlich ganz ähnlich wie in realen Situationen, wo es ziemlich schwierig ist, sinnvolle extrinsische Belohnungen zu setzen.
In unserem Fall ist die regelbasierte Bestellpolitik so einfach, dass ein extrinsisches Belohnungssystem diese Politik höchstwahrscheinlich einfach als eine Reihe von fremden Belohnungen codieren würde.
Sie können auf den zugrundeliegenden Code, der die Simulation enthält, die vortrainierten Modelle und Jupyter-Notebooks, die zeigen, wie sie verwendet werden, in unserem GitHub-Repository zugreifen.
Upcoming Events

Training AI to Play The Beer Distribution Game

2 hours - 2021-10-27

Mastering The Complexity of Digital Transformation

2 hours - 2021-10-28

Modeling Growth Strategies For Professional Service Firms

2 hours - 2021-11-18

Go to event overview

Recent Blogposts

Meetup: Agile Transformation Tools

Olga Medvedeva - 2021-09-27

Meetup: Understanding The Beer Distribution Game

Olga Medvedeva - 2021-09-01

Introduction to The Business Prototyping Toolkit

Oliver Grasl - 2021-08-17

Go to blog overview

Email newsletter

Subscribe to our newsletter and stay up to date about the latest trends and news.

Name
Email
Subscribe to our newsletter and stay up to date about the latest trends and news.
  • transentis
Contact us

transentis consulting

Geisbergstraße 9

10777 Berlin


+49 30 9203833320

info@transentis.com