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
Sunday, May 31, 2020

Eine Einführung in die agentbasierte Modellierung und das Reinforcement Learning, angewandt auf das Beer Game

Das berüchtigte Beer 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:

Unsere Lieblingsbeschreibung des Spiels steht in Peter Senges Die fünfte Disziplin
John Stermans Business Dynamics analysiert das Spiel mit systemdynamischen Bestands- und Flussmodellen
Das Beer Game verstehen, ein weiterer Blogbeitrag auf dieser Seite bietet eine eingehende Analyse des Spiels.

Wir haben in unserer Fallstudie Spielen Sie das Beer Game 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 Beer Game 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 Distibution Game (Ein agentenbasierter Ansatz zur Modellierung des Beer Games), 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:

Training Artificial Intelligence to Play the Beer Distribution Game Graph 1 DE

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 Schritt 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.

Training Artificial Intelligence to Play the Beer Game Graph 2

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 Beer Game 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.

Training Artificial Intelligence to Play the Beer Game Graph 3

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!

Training Artificial Intelligence to Play the Beer Game Graph 4

Mit diesem Bestellverhalten liegen die Lieferkettenkosten weit vom Ziel entfernt:

Training Artificial Intelligence to Train and Test Machine Learning Applications Graph 5

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 das Management 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.

Training Artificial Intelligence to Play the Beer Game Graph 6

Diese Politik ist schön einfach und fast schon gut genug, um das Ziel zu erreichen, die Lieferkettenkosten unter 30.000$ zu halten.

Training Artificial Intelligence to Play the Beer Game Graph 7

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.

Training Artificial Intelligence to Play the Beer Game Graph 8

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

t

erhält der Agent eine Repräsentation des Umgebungszustandes,

S_t \in \mathcal{S}

, und wählt auf dieser Basis eine Aktion,

A_t \in \mathcal{A}

. Einen Zeitschritt später erhält der Agent (teilweise) als Folge seiner Aktion eine Belohnung

R_t \in \mathcal{R} \subset \mathbb{R}

Training Artificial Intelligence to Play the Beer Game Graph 9

Die Wechselwirkung führt dann zu einer Trajektorie, die wie folgt aussieht:

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 (

\mathcal{S}

\mathcal{A}

und

\mathcal{R}

) eine endliche Anzahl von Elementen und die Zufallsvariablen

R_t

und

S_t

haben wohldefinierte Wahrscheinlichkeitsverteilungen, die nur vom vorhergehenden Zustand und der Aktion abhängen:

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',s \in \mathcal{S}, r \in \mathcal{R}

, und

a \in \mathcal{A}(s)

. Die Function

p

definiert die Dynamik des MEP, die eine Wahrscheinlichkeit für jede Wahl von

s

und

a

\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

p

, können wir alles berechnen, was wir über das Verhalten eines Agenten wissen müssen, z. B. die Zustandsübergangswahrscheinlichkeiten:

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

s

und die Aktion

a

wählen:

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:

G_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}

0 \leq \gamma \leq 1

Absizungssatz ist (der benötigt wird, um sicherzustellen, dass

G

konvergiert in unendlichen MEP).

Beachten Sie, dass

G

auch rekursiv definiert werden kann:

G_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

t

der Politik

\pi

folgt, dann ist

\pi(a \mid s)

die Wahrscheinlichkeit, dass

A_t=a

, wenn

S_t=s

Beachten Sie, dass

\pi

sich von der oben definierten Wahrscheinlichkeitsverteilung

p

unterscheidet - die Wahrscheinlichkeitsverteilung

p

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.

Training Artificial Intelligence to Play the Beer Game Graph 10

Mit

\pi

und

p

können wir die Wahrscheinlichkeit berechnen, mit der ein Agent in einen bestimmten Zustand

s'

übergeht, wenn er sich im Zustand

s

befindet:

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

s

zur Zeit

t

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

p

können wir nun den Wert berechnen, den wir von der Politik zu erzielen erwarten: Die Wertfunktion eines Zustands

s

unter einer Politik

\pi

, bezeichnet mit

v_\pi (s)

, ist der erwartete Ertrag, wenn man in

s

startet und danach

\pi

folgt.

Für unsere MEP können wir

v_\pi

definieren durch:

v_\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

a

im Zustand

s

unter einer Politik

\pi

wie folgt definieren:

q_\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_\pi

wird die Aktionswertfunktion für die Politik

\pi

genannt. Sie stellt den erwarteten Wert unserer Politik dar, wenn wir im Zustand

s

beginnen, dann die Aktion

a

ausführen und danach der Politik

\pi

folgen. Der wichtige Punkt hier ist, dass

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

s

s'

übergegangen sind.

\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

s

s'

bewegen, genauer gesagt:

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+1

, aber beginnend zum Zeitpunkt

t

im Zustand

s

. Um dies zu berechnen, müssen wir die Wertfunktion für jeden möglichen zukünftigen Zustand

s'

berechnen, gewichtet mit der Wahrscheinlichkeit, diesen Zustand tatsächlich zu erreichen:

\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.

Training Artificial Intelligence to Play the Beer Game Graph 11

Setzen wir diese Begriffe zusammen und ordnen die Summen neu an, wir enden mit:

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_\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_\pi (s) \geq v_{\pi'} (s)

für alle

s \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

v_*

hat, definiert als:

v_* (s) \doteq \max\limits_\pi v_\pi (s)

Optimale Politiken haben die gleiche optimale Aktionswertfunktion

q_*

, definiert als

\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}

v_*

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:

\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

q_*

ist:

\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

n

Zustände gibt, hat man am Ende

n

Gleichungen in

n

Unbekannten.

Sobald man

v_*

hat, ist es einfach, die optimale Politik abzuleiten: Für jeden Zustand

s

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

q_*

haben, ist die Wahl einer optimalen Politik noch einfacher - Sie müssen einfach eine Aktion finden, die

q_* (s,a)

maximiert:

\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

v_*

oder

q_*

zu finden. Glücklicherweise gibt es eine Reihe von Ansätzen, um ungefähre Lösungen zu finden.

Eine Möglichkeit,

v

zu schätzen, ist die Verwendung eines Monte-Carlo-Ansatzes: Wir beginnen mit einer anfänglichen Näherung

V

für

v

(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

p

definiert ist.

Während jedes Laufs wird der aktuelle Wert für

G_t

(d. h. die tatsächliche Gesamtbelohnung nach diesem Zustand) für jeden Zustand und Zeitschritt zwischengespeichert. Am Ende des Laufs aktualisieren wir

V(S_t)

anhand der folgenden Formel, wobei

\alpha

eine Konstante ist, die definiert, wie schnell wir uns auf den neuen Wert zubewegen:

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

G_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,

V

nach jedem Zeitschritt zu aktualisieren. Dieser Ansatz funktioniert dank der rekursiven Natur der Bellman-Gleichung.

Wenn wir uns daran erinnern, dass

G_t = R_{t+1}+\gamma G_{t+1}

, können wir die folgende Formel verwenden, um

V

nach jedem Zeitschritt zu aktualisieren:

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

V

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

q_*

anstelle von

v_*

findet:

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)

und stellen Sie sicher, dass

Q(terminal state,.) = 0

Lassen Sie die Simulation eine große Anzahl von Malen (Episoden) laufen, mit der folgenden Zyklus für jede Episode:

Initialisieren Sie S
Erstellen Sie einen Zyklus für jeden Schritt der Episode:
1. Wählen Sie A aus S mit $\epsilon$ -gierige Politik basierend auf Q
2. Führen Sie Aktion A aus, beobachten Sie R, S'
3. $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$
  • $S \gets S'$
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

\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

\alpha \in (0, 1\rbrack

definiert, wie schnell wir uns von unserem aktuellen Wert von

Q

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 Beer Game-Agenten an. Unsere "Erkenntnisse" bestehen daraus, die richtigen Werte für die Funktion

Q(S,A)

zu finden, die dem Agenten sagt, welche Aktion er ausführen soll, wenn er sich im Zustand A befindet.

Wir setzen

\epsilon=0.1

und

\alpha=0.2

. Da das Beer Game über eine endliche Menge von 24 Runden läuft, können wir

\gamma=1

setzen.

Wir speichern

Q

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)

, der unsere Näherung an den optimalen Wert

q(s,a)

ist, d. h. den Wert, den wir erwarten zu erreichen, wenn wir uns im Zustand

s

befinden und die Aktion

a

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)

definiert ist. Für das Beer Game 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)$ für einen gegebenen Zustand $S$ maximiert.
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))$ .

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.

Training Artificial Intelligence to Play the Beer Game Graph 12

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 Beer Game ü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
)

Training Artificial Intelligence to Play the Beer Game Graph 13

Mit dem trainierten Modell erhalten wir die folgenden Ergebnisse:

Training Artificial Intelligence to Play the Beer Game Graph 14

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.

Training Artificial Intelligence to Play the Beer Game Graph 15

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.

Training Artificial Intelligence to Play the Beer Game Graph 16

Die Lieferkettengesamtkosten sind also noch etwas zu hoch:

Training Artificial Intelligence to Play the Beer Game Graph 17

Also lass uns sehen, was nach 50.000 Episoden passiert:

Training Artificial Intelligence to Play the Beer Game Graph 18

Nach 50.000 Trainingsrunden liegen die Gesamtkosten innerhalb des Ziels ebenso wie die Einzelkosten:

Training Artificial Intelligence to Play the Beer Game Graph 19

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.

Training Artificial Intelligence to Play the Beer Game Graph 20

Zusammenfassung

In diesem Beitrag wurde das Konzept der agentenbasierten Simulation und des Reinforcement Learning vorgestellt und auf eine einfache Lieferkettensimulation angewendet, die das Beer 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 Simulation des Beer Games bedeutet dies, dass unsere Agenten nun gut darin sind, das Beer Game 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.

Das Beer Game simulieren Overview Das Beer Game lösen