Embed Size (px)
Citation preview
Reinforcement Learning zur Lösung multidimensionaler Yield-Management-Probleme
Oliver Wendt / Michael Schwind
Institut für Wirtschaftsinformatik der Universität Frankfurt
Lehrstuhl für Betriebswirtschaftslehre insb. Wirtschaftsinformatik
und Informationsmanagement
1 Abstract / Zusammenfassung ......................................................................... 2
2 Einleitung ....................................................................................................... 2
2.1 Die Problemstellungen des Yield Management ......................................................... 3
2.2 Yield Management für Informationsprodukte und Informationsdienstleistungen..... 4
3 Stochastische Dynamische Programmierung als Lösungsansatz................... 5
3.1 Einsatz Künstlicher Neuronaler Netze zur Repräsentation der Restwertfunktion ..... 8
3.2 Einsatz evolutionärer Verfahren zur Verbesserung der Restwertfunktion............... 12
4 Bekräftigungslernen für Yield-Management-Prozesse ................................ 17
4.1 Grundgedanke des Bekräftigungslernens................................................................. 18
4.2 Stochastische Dynamische Programmierung ........................................................... 18
4.3 Monte-Carlo-Methode.............................................................................................. 23
4.3.1 On-Policy-Methode.......................................................................................... 24
4.3.2 Off-Policy-Methode ......................................................................................... 25
4.4 Temporal Difference Learning................................................................................. 26
4.5 Q-Learning ............................................................................................................... 27
4.6 Anpassung des Bekräftigungslernens an die Problemstellung des Yield Management ......................................................................................................................... 28
4.7 Vergleich der Ergebnisse des Bekräftigungslernens mit denen der Genetischen Algorithmen ......................................................................................................................... 29
5 Zusammenfassung und Ausblick ................................................................. 30
1
0 Abstract / Zusammenfassung
Auch wenn die Preistheorie seit jeher einen Kernbereich wirtschaftswissenschaftlicher For-schung darstellt, sind viele Dienstleistungsprozesse im Gegensatz zu industrieller Produktion von hohen Fixkosten aber vernachlässigbaren variablen Kosten gekennzeichnet, so dass die Preisentscheidung vor allem durch die Opportunitätskosten einer alternativen Ressourcen-verwendung determiniert wird. Insbesondere im Airline-Bereich werden seit ca. 20 Jahren unter der Bezeichnung Yield Management derartige Probleme meist mit heuristischen Verfah-ren adressiert. Der vorliegende Beitrag zeigt auf, dass einerseits der Übertragung derartiger Methoden auf Probleme der Bepreisung von Informationsdienstleistungen nichts im Wege steht, andererseits die Komplementarität verschiedener, gemeinsam beanspruchter Ressourcen zu immensen Komplexitätsproblemen der Bepreisung führt, die sich nicht durch eine lineare Addition einzelner Restwertfunktionen bewältigen lassen. Der Einsatz Künstlicher Neurona-ler Netze zur (gemeinsamen) Repräsentation der hierfür nötigen multidimensionalen Rest-wertfunktionen und Genetischer Algorithmen zur Verbesserung dieser Funktionen bietet noch keinen zufrieden stellenden Ausweg. Erst die Anpassung von Methoden des Reinforcement Learning (dt. Bekräftigungslernen) bietet viel versprechende Ergebnisse zur effizienten adap-tiven Bepreisung des Ressourceneinsatzes in multidimensionalen Yield-Management-Problemen.
1 Einleitung
Koordination ökonomischer Aktivitäten verlangt in erster Linie die effiziente Allokation knapper Ressourcen zu alternativen Verwendungen. Die Möglichkeit, diese Allokation über die Festlegung von Preisen zu erreichen, die die relative Knappheit einzelner Güter anzeigen, gilt in Marktwirtschaften als nahezu unumstritten. Die klassische mikro-ökonomische Theo-rie, vgl. [Debr59], [Mali74], [HiKi76], unterstellt in ihren Marktpreismodellen allerdings Konsumgüter, die ihren Wert (Nutzenstiftungspotenzial) bis zu dem Zeitpunkt behalten, an dem sie vom Konsumenten verzehrt werden und ab dann ihre Existenz verlieren. Je nachdem, wie leicht das eigene Produkt durch Produkte von Konkurrenten substituierbar ist, gelingt es dem einzelnen Anbieter mehr oder weniger gut, einen Preis am Markt durchzusetzen, der über den variablen Selbstkosten des Gutes liegt.
Auch wenn die Bepreisung solcher Konsumgütern noch den Großteil der Marketingliteratur zur Preistheorie dominiert, vgl. z.B. [NiDH94], [Simo92], ist seit langem bekannt, dass diese Modelle weder zur Bepreisung verderblicher Waren noch zur Bepreisung von Dienstleistun-gen sinnvoll verwendet werden können und hier somit auch keine effiziente Ressourcenallo-kation sicherstellen können.
Das so genannte Yield-Management versucht, diese Lücke durch dynamische Preisbildungs- oder Kontingentierungsansätze in Theorie wie Praxis zu schließen und wird z.B. im Airline-Bereich (vgl. [ChGJ99]) seit Jahren erfolgreich zur Gewinnmaximierung eingesetzt.
Im Folgenden wird gezeigt, dass die Probleme der gewinnmaximalen Bepreisung von Infor-mation eine hohe Analogie zu den im Yield-Management untersuchten Problemstellungen aufweisen und skizziert, wie eine Übertragung der Methoden auf informationswirtschaftliche Probleme vorzunehmen ist.
2
1.1 Die Problemstellungen des Yield Management Die mangelnde Anwendbarkeit der klassischen Preistheorie liegt in vielen Branchen darin begründet, dass die Menge des in einem Zeitraum verfügbaren Angebots nach oben limitiert ist und nur zu prohibitiv hohen Kosten ausgeweitet werden kann. Sind Produktionsprozesse aber durch hohe Kapazitätsbereitstellungskosten und hohe dynamische Bereitschafts-kosten, vgl. [Bert90], gekennzeichnet, sind die variablen Grenzkosten einer zusätzlichen Leis-tungseinheit innerhalb der gegebenen Kapazitäten meist gering. Entsprechend resultieren ho-he Deckungsbeiträge.
Da jede zusätzliche Nachfrage mit einem positiven Deckungsbeitrag zur Deckung der irrever-sibel vordisponierten Kapazitätskosten beiträgt, bietet eine entsprechende Preis-/Mengensteuerung erhebliches Gewinnsteigerungspotenzial. Dieses ist umso eher der Fall, je höher die sprungfixen Kosten der Bereitstellung zusätzlicher Produktionskapazitäten sind (z.B. ein Zusatzflug).
Vor diesem Hintergrund kann in Anlehnung an Belobaba und Vogel Yield Management defi-niert werden als die:
Summe aller Verfahren, welche durch eine integrierte Preis- und Kapazitätssteu-erung, die richtigen Einheiten eines zukünftig bereitzustellenden Kapazitätstyps dem richtigen Kundentyp so zuordnen, dass der Deckungsbeitrag der Betriebsein-heit maximiert wird. (vgl. [Belo89], [Voge89])
Kimes [Kime89] identifiziert folgende Charakteristika von Produktionsprozessen als beson-ders viel versprechende Rahmenbedingungen für den Einsatz von Yield-Management-Metho-den:
• relativ fixe Produktionskapazitäten
• Möglichkeit zur Marktsegmentierung
• Nichtlagerbarkeit und Verderblichkeit der Produkteinheiten
• Produktverkauf vor Produktionsbeginn
• hohe Volatilität der Nachfrage
• niedrige Grenzkosten zusätzlicher Leistungseinheiten / hohe sprungfixe Kapazitätsände-rungskosten
Beispiele für “verderbliche“ Produkte, deren Wert im Zeitablauf sinkt oder zu einem konkre-ten Zeitpunkt gänzlich verfällt, sind vielfältig. Während bei Lebensmitteln und Bekleidungs- / Modeartikeln Schlussverkäufe und Preisreduktionen eher ad hoc zum Einsatz kommen, wid-met sich die Literatur vornehmlich dem Luftverkehrs- und Hotelbereich: Auch wenn bereits Anfang der 70er Jahre erste Ansätze zur Überbuchungssteuerung entwickelt wurden, kann ein systematischer Praxiseinsatz der Yield Management-Methoden erst seit der Deregulierung des US-amerikanischen Luftverkehrsmarkts 1979, unter der Vorreiterrolle von American Airlines beobachtet werden. Aufgrund zahlreicher positiver Erfahrungsberichte aus der Luftverkehrs-branche, vgl. z.B. [SmLD92], findet das Konzept seit Ende der 80er Jahre zunehmende An-wendung in anderen Bereichen der Logistik- und Transportindustrie sowie der Hotelindustrie, bei Mietwagenfirmen oder Reiseveranstaltern, vgl. z.B. [WeBo92]. Gegen Ende der 90er Jah-re finden sich zunehmend Applikationen zur Ressourcenallokation im Telekommuni-kationsbereich, vgl z. B. [Huma01].
3
Die Aufzählung der Beispiele macht bereits deutlich, dass der Begriff der "Verderblichkeit" offenbar einerseits auf Waren (z.B. Lebensmittel) angewandt wird, andererseits aber auch auf Dienstleistungen, oder besser gesagt: auf das periodenbezogene Potenzial, eine Dienstleistung zu erbringen, welches verdirbt, wenn es nicht genutzt wird. Nicht der entsprechende Potenzi-alfaktor (Sitz, Hotelzimmer, Mietwagen) selbst verdirbt hierbei, sondern nur die Möglichkeit, ihn in dieser einen Bezugsperiode noch zur Generierung von Erlösen einsetzen zu können. In der nächsten Periode steht der Potenzialfaktor (im Gegensatz zu dem verdorbenen Lebensmit-tel) wieder unverändert zur Verfügung. Weil der Begriff des Yield-Management als Maximie-rung des Durchschnittsertrags missverstanden werden kann, werden die Konzepte in der neue-ren Literatur treffender als ”Perishable Asset Revenue Management” oder ”Profit Mana-gement”, vgl. z.B. [WeBo92], [Remm94], [BePo00] bezeichnet1.
1.2 Yield Management für Informationsprodukte und Infor-mationsdienstleistungen
Der an dieser Stelle verwendete Begriff „Informationsprodukt“ lässt sich anhand einer auf Peer-2-Peer Servern abrufbaren beliebig replizierbaren Musik-Datei, dem bedarfsgerecht ge-nerierten Chart der aktuellen Kursentwicklung eines Wertpapiers oder eines im WWW abruf-baren Stadtplans verdeutlichen und unter einer Informationsdienstleistung kann man im hier präsentierten Kontext z. B. die Bewertung der Risikostruktur seines Wertpapierportfolios (nach festgelegten Verfahren) oder die Tourenplanung für eine von ihm vorgegebene Menge zu beliefernder Kunden verstehen. Verglichen mit physischen Dienstleistungen lassen sich folgende Hauptunterschiede festhalten:
•
•
•
Prozesse der Informationsproduktion gelten in vielen Fällen als unterbrechbar (preempti-ve), ihr Zwischenstand kann, zumindest wenn es sich um einen technischen Träger der In-formationsverarbeitung handelt (Computer), leicht zwischengespeichert werden, weshalb Betriebssysteme meist ein sog. Round Robin Scheduling einsetzen. Bei einem Hotelauf-enthalt sinkt dagegen die Zahlungsbereitschaft des Kunden auf Null, wenn sein Zimmer zwischenzeitlich anderen, höher priorisierten Gästen zugeteilt wird und er dafür als Kom-pensation am nächsten Tag zwei Zimmer erhält.
Variable Kosten der Produktion sind nochmals deutlich geringer als in der Hotel- oder Airline-Branche. Es fallen fast ausschließlich Bereitstellungskosten der Potenzialfaktoren an: Der humane Träger der IV (Mitarbeiter) wird auch bei Untätigkeit nicht auf Gehalt verzichten wollen, moderne Rechner weisen zwar im „idle mode“, also bei Nichtnutzung des Prozessors, einen geringeren Energieverbrauch auf, aber auch dies kann aus ökonomi-scher Sicht vernachlässigt werden.
Die sog. Indeterminiertheit vieler Informationsverarbeitungsprozesse impliziert, dass vor Start des Produktionsprozesses die genaue Dauer der Ressourcennutzung (im Gegensatz zu einer Hotel- oder Flugbuchung) oft nicht genau bestimmt werden kann, da diese z.B. bei einem Sortierverfahren von der Vorsortierung der Daten oder bei der Berechnung des historischen Kurscharts eines Aktienportfolios von der Zahl der Papiere und der Trans-aktionshäufigkeit des Kunden abhängt. Dennoch kann dieses Problem oft durch Verwen-dung geeigneter Wahrscheinlichkeitsverteilungen umgangen werden.
1 Da sich diese Begriffe in der Praxis bislang nicht durchsetzen konnten und "Revenue Management" die Kos-
tenseite vernachlässigt, halten wir weiterhin am Begriff Yield Management fest.
4
2 Stochastische Dynamische Programmierung als Lösungsansatz
Die zur Lösung des Yield-Management-Problems in der Literatur entwickelten Verfahren beziehen sich zum überwiegenden Teil auf den Airline-Kontext und lassen sich anhand ihrer theoretischen Fundierung und Komplexität grundsätzlich einteilen in pragmatische Lösungs-verfahren (also Heuristiken) und Optimierungsverfahren. Als die prominentesten Vertreter der ersten Klasse sind die geschachtelte Kontingentierung (nested booking classes) [Horn91] sowie das Konzept des Expected Marginal Seat Revenue (EMSR) (vgl. [Belo87] u. [Belo 89]) zu nennen. Beiden Konzepten liegt eine Aufteilung der Anzahl verfügbarer Plätze in Bu-chungsklassen zugrunde, deren Größe vor dem Buchungsprozesse festgelegt und ggf. wäh-rend dieses Prozesses angepasst werden muss. Im Buchungsprozess nutzen Anfragen mit hö-herem Deckungsbeitrag, sofern ihre Klasse bereits gefüllt ist, Kapazität aus geringwertigeren Klassen, nicht jedoch umgekehrt. Während die Festlegung der Klassengrenzen bei der ge-schachtelten Kontingentierung meist durch Simulation mit historischen Anfragen bestimmt wird, bestimmt EMSR den Punkt, an welchem der Grenzertrag einer zusätzlichen Kapazitäts-einheit in der höherwertigen Klasse unter den erwarteten Erlös in der nächst geringwertigeren Klasse fällt, da die Wahrscheinlichkeit einer entsprechenden Zahl von Anfragen für die hö-herwertige Klasse entsprechend gering ist.
Da Yield-Management ein wiederkehrendes dynamisches Entscheidungsproblem unter Unsi-cherheit darstellt, führen statische Lösungsalgorithmen der linearen Programmierung nicht zur optimalen Lösung des Entscheidungsproblems, vgl. [Kime89]. Vielmehr gehört Yield-Management zu der Klasse von Problemen, die sich mit stochastischer dynamischer Pro-grammierung bewältigen lassen, vgl. [AlBM86].
Alle im Yield-Management maßgeblichen Entscheidungsprobleme, sind als Baumstruktur darstellbar, bei der die Kanten des Baums die Entscheidungen (Aktionen a1, a2, ..., an ∈ A= Aktionsraum) repräsentieren und die Knoten die Systemzustände (s, s’, s’’, ..., s
n ∈ S = Zu-standsraum) bezeichnen (vgl. Abb. 12). Im Rahmen der Optimierung von Entscheidungsfin-dungen ist ein im Weiteren ein Parameter notwendig, der den Erfolg (Reward) (r1, r2, ..., r n ∈ R = Ertragsfunktion) einer getroffen Entscheidungen beschreibt. Der Erwartungswert für den Erfolg bei der nächsten Entscheidung kann wie folgt geschrieben werden:
{ }',, 11' ssssaarE ttttass ====ℜ ++
Gleichung 1:
In jedem Knoten wird eine Entscheidung über die zu wählende Kante getroffen. Man kann nun zusätzlich der Auswahl der einzelnen Aktionen (Kanten) a priori eine bestimmte Wahr-scheinlichkeit zuordnen:
{ }aassssP ttta
ss ==== + ,'Pr 1'Gleichung 2:
Hierfür kommt im Entscheidungsbaum ein weiterer Parameter πi zum Einsatz, welcher als Politik bezeichnet wird.2
Allen hier betrachteten Entscheidungsprozessen wird die so genannte Markov-Eigenschaft [Pute94] unterstellt. Diese besagt, dass die Wahrscheinlichkeit für die Zustandsübergänge von s nach s’ usw. in den einzelnen Stufen des Baums unabhängig von den vorhergehenden Um-weltzuständen und Entscheidungen sind. Nur so kann dem Entscheidungsprozess eine Pfadu-nabhängigkeit zugeschrieben werden, die es ermöglicht, das Problem schrittweise, mithilfe der dynamischen stochastischen Programmierung zu lösen.
5
2 Die Vorgehensweise bei der Auswahl der Kanten, also die Entscheidungspolitik, hat direkte Auswirkungen
auf die Wahrscheinlichkeit, mit der ein Pfad im Entscheidungsbaum durchlaufen wird.
Im Folgenden soll eine mathematisch optimale Lösung des zeitpunktbezogenen Yield-Management Problems anhand der stochastischen dynamischen Programmierung anschaulich ermittelt werden, vgl. [Wend91]:
Man stelle sich einen von seiner Sitzplatzkapazität auf sechs Sitzplätze in der ersten Klasse beschränktes Verkehrsflugzeug vor, das zu einem bestimmten zukünftigen Zeitpunkt von Ort A nach Ort B fliegen wird. Die Sitzplätze können einzeln oder zu mehreren verkauft werden, das heißt zu jedem Zeitpunkt vor Abflug kann die Restkapazität in der 1. Klasse einen von folgenden sieben Werten annehmen, die den Zustandsraum S bilden: S:= {0, 1, 2, 3, 4, 5, 6}.
Der Yield Manager für diesen Flug erhält nun Kapazitätsanfragen, die er entweder akzeptie-ren oder ablehnen kann und die sich sowohl durch die Anzahl der nachgefragten Sitze als auch durch den Preis unterscheiden. Im folgendem wird vereinfachend davon ausgegangen, dass es nur drei verschiedene Typen von Sitzplatzanfragen (F1, F2 und F3) gibt. Deren Attri-bute und Anfragewahrscheinlichkeiten sind in folgender Tabelle zusammengefasst:
Typ Wahrschein- lichkeit
Angefragte Sitz-plätze
Erlös
F1 0.5 1 Sitz 1 Geldeinheit
F2 0.3 2 Sitze 4 Geldeinheiten
F3 0.2 3 Sitze 9 Geldeinheiten
Tabelle 1: Beispielhafte Verteilung von Buchungsanfragen
Es soll ferner angenommen werden, es gäbe keine Unsicherheit über die Anzahl der bis zum Abflug noch eingehenden Anfragen, das heißt die Zahl der noch folgenden Teilentschei-dungen ist zu jedem Entscheidungszeitpunkt bekannt. Es kann somit jeder Anfrage ein (rück-wärts zählender) Index k zugeordnet werden, der aussagt, dass nach Anfrage k noch k-1 Sitz-platzanfragen kommen werden.
Um eine optimale Annahmeentscheidung zu treffen, müsste der Entscheidungsträger auf jeder Stufe k nicht nur den Typ seiner Anfrage und die zur Verfügung stehende Restkapazität i ken-nen, sondern auch den Wert Vk-1(i) der für die k-1 verbleibenden Anfragen verfügbaren Rest-kapazität i im Falle der Ablehnung der Anfrage k sowie den Wert Vk-1( i - Sitzanzahlk) der um die Sitzanzahl der aktuellen Anfrage reduzierten Restkapazität im Falle des Akzeptierens der zur Disposition stehenden Anfrage.
Er könnte dann abwägen ob:
Gleichung 3: )()( 11 iVSitzanzahliVErlös kkkk −− ≥−+
Ist dies der Fall, wird die Anfrage akzeptiert, andernfalls wird sie abgelehnt. Ausgehend von V0(i), das null sein muss für alle möglichen Restkapazitäten i, kann die optimale Annahme-politik für Stufe k=1 und damit der Wert V1(i) für jedes i berechnet werden, wobei die optima-le Annahmepolitik für diese Stufe lautet:
Akzeptiere jede Anfrage, welche kleiner oder gleich der Restkapazität ist, wenn keine weite-ren Anfragen mehr eingehen. Mittels oben angegebener Wahrscheinlichkeitsverteilung kann für jede übrig gebliebene Restkapazität i der erwartete Restwert V1(i) bestimmt werden.
6
Hierauf aufbauend kann nun die optimale Annahmepolitik für Stufe k=2 berechnet werden. Auf Stufe k=2 stellt sich erstmalig die Frage nach einem Aufsparen von Kapazität für Stufe k=1: Der erwartete Ertrag auf Stufe k=2 setzt sich (je nach Annahmepolitik) zusammen aus dem auf dieser Stufe generierten erwarteten Erlös r (i, a) und dem Wert der für Stufe k=1 üb-rigbleibenden Restkapazität V1(j), wobei j die neue (bei Annahme reduzierte) Restkapazität angibt (die Werte für V1 wurden gerade berechnet):
∑+=ja jVjaipairiV )](),,(),([max:)( 12Gleichung 4:
Restwert V*(i) bei optimaler Annahmestrategie
0
2
4
6
8
10
12
14
16
18
0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30verbleibende Zahl N von Anfragen
Res
twer
t V*(
i) ei
ner K
apaz
ität i
i = 6
i = 5
i = 4
i = 3
i = 2
i = 1
Abb. 1: Wert einer gegebenen Restkapazität im Zeitablauf
Indem für jeden möglichen Zustand i und jede mögliche Annahmepolitik a der Wert der Ka-pazität verglichen wird, ist für jeden Zustand i die optimale Annahmevorschrift zu ermitteln. Hierbei stellt p die Übergangswahrscheinlichkeit von Kapazität i auf Kapazität j unter An-nahmepolitik a dar. Setzt man diesen Iterationsprozess fort, lässt sich für jede beliebige Stufe k die optimale Yield Management-Politik bestimmen. Abb. 1 vermittelt eine Vorstellung vom asymptotischen Verlauf des maximalen Wertes einer gegebenen Restkapazität i bei unter-schiedlicher Anzahl N verbleibender Kapazitätsanfragen (für unseren Beispielfall aus Tab. 1). Trotz der Optimalität dieses Lösungsansatzes hat er aufgrund der erheblichen Anforderungen an die Rechnerkapazität bislang wenig Eingang in die Yield Management-Praxis gefunden. Ein Hauptgrund hierfür ist in der bislang mangelhaften Skalierbarkeit des Ansatzes für Prob-leme des so genannten Network Yield Management zu sehen, in welchen der Kunde nicht die Nutzung einer einzelnen Ressource nachfragt, sondern die eines Ressourcenbündels, also z.B. eines Multi-Leg-Fluges oder eines mehrtägigen Aufenthalts im Hotel. Hier verbietet die Komplexität des Suchraums eine Bestimmung der Restwertfunktionen einer gegebenen Kapa-zität schon bei kleinen Problemgrößen, da für jede mögliche Kombination von Restkapazitä-ten der Ressourcen eine eigene Restwertfunktion berechnet werden müsste. Andererseits führt die in der YM-Praxis vorgenommene lineare Addition der Preise für die einzelnen Ressourcen im sog. „Bid Pricing“ zu suboptimalen Ergebnissen [TaRy96].
Dies gilt analog auch bei Prozessen der Informationsproduktion. Der Zustandsraum des Mar-kovprozesses erlangt eine kombinatorische Komplexität, die eine optimale Lösung aus-schließt: auch hier fragt der Nachfrager eines Informationsproduktes in den seltensten Fällen die direkte Nutzung des entsprechenden Potenzialfaktors an, sondern die Erstellung eines In-
7
formationsprodukts, welche einen Produktionsprozess auslöst, der eine Fülle von Potenzial-faktoren unterschiedlich stark beansprucht, die ihrerseits in einer Fülle unterschiedlicher Pro-duktionsprozesse eingesetzt werden könnten, falls dieser spezifische Auftrag abgelehnt wür-de.
Die theoretische Literatur zu Markovprozessen hat der generellen Problematik großer Zu-standsräume durch Verfahren zur Clusterung Rechnung getragen [Noll78], [Doer84], eine Adaption dieser Verfahren auf die hier vorliegende multidimensionale Problematik wird dort allerdings nicht thematisiert.
2.1 Einsatz Künstlicher Neuronaler Netze zur Repräsenta-tion der Restwertfunktion
Ein möglicher Weg zur Bewältigung des Komplexitätsproblems der Ermittlung optimaler Restwertfunktionen besteht im Einsatz Künstlicher Neuronaler Netze (KNN) [Holl75], ent-weder zur Repräsentation der Restwertfunktion V oder aber zur Repräsentation der Entschei-dungsfunktion selbst. Beide Wege sollen kurz skizziert werden:
Im Grundmodell des KNN, das als ein aus Grundoperatoren (vgl. Abb. 2) zusammengesetztes nichtlineares Regressionsnetz (vgl. Abb. 3) angesehen werden kann, ist jedes Neuron ledig-lich in der Lage, die von anderen Neuronen empfangenen Signale zu gewichten und gemäß einer Transfer-Funktion in seinen eigenen Output zu transferieren. Die Kanten des Netzes fungieren somit als unidirektionale Signalpfade, die von einem gegebenen Neuron ausgehen-den Signale sind auf allen Kanten identisch.
Transferfunktion
Localm em ory
“activate”X 1 X 2 X n
y O utput s ignal
Copies of output s ignal
Input s ignals
Abb. 2: Funktionsweise eines einzelnen Neurons.
8
Eingabeschicht(input layer)
0 bis n verdeckteSchichten(hidden layer)
Ausgabeschicht(output layer)
Abb. 3: Ein Feedforward-Netzwerk mit 4 Schichten.
Durch die Zusammenschaltung einer großen Zahl von Einzelneuronen zu einem Netz entsteht die Möglichkeit der Abbildung beliebig komplexer Funktionen von Inputsignalmustern (am Input-Layer angelegt) auf Outputsignalmuster.
Da Feed-Forward-KNN mit mindestens drei Layern (bei ausreichender Neuronenzahl im bzw. in den Hidden Layern) prinzipiell in der Lage sind, jegliche funktionale Abbildung des Input-Layer in den Output-Layer zu repräsentieren [Bish95], muss dies mithin auch für unsere Restwertfunktion V* gelten.
Welche Gestalt Input- und Output-Layer hierbei annehmen müssen, liegt ebenfalls auf der Hand: Für jede Komponente des Ressourcenvektors r (also jede Ressource) repräsentiert ein Input-Neuron die im Bewertungszeitpunkt verfügbare Ressourcenmenge (vgl. hierzu Abb. 4). Dies kann entweder entsprechend ihrer absoluten Menge, oder, was sich zwecks Beibehaltung der in KNN üblichen Skalierung der Wertebereiche anbieten mag, relativ zur Gesamtmenge der maximalen Verfügbarkeit der entsprechenden Ressource geschehen. Neben diesen k Neu-ronen für die k Ressourcen wird ferner ein „Zeitneuron“ benötigt, welches (ggf. ebenfalls pro-zentual) die verbleibende „Buchungszeit“ oder die verbleibende Zahl künftiger Anfragen in das KNN einspeist.
Ein einziges Outputneuron repräsentiert den aus den Werten der Inputneuronen eindeutig be-stimmten Restwert. Da auch Outputneuronen bei den meisten KNN-Typen einen Wert im Intervall [-1; 1] liefern, muss auch hier eine geeignete Skalierung in die relevante monetäre Größe vorgenommen werden.
Im Anfragezeitpunkt bestimmt das KNN den Restwert für zwei unterschiedliche Ressourcen-vektoren, nämlich zum einen den Vektor der verbleibenden Ressourcen bei Annahme, zum anderen bei Ablehnung der gegenwärtigen Anfrage. Anhand dieser Differenz bestimmt sich dann wie gewohnt der Reservationspreis für die Anfrage.
9
Abb. 4: Beispielhafte Bewertung einer Reduktion der Kapazität von Ressource x5, x6 und x7
durch einen nachgefragten Auftrag; seine erwarteten Opportunitätskosten betragen 3200-2300=900 Geldeinheiten
Mit dieser Topologie ist es möglich, bereits mit 5 Neuronen im Hidden-Layer per Backpropa-gation folgendes Approximationsverhalten an die oben dargestellte Test-Restwertfunktion zu erzielen:
10
MLP-3-5-1
0
0.01
0.02
0.03
0.04
0.05
0.06
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)MLP-3-5-1
-0.010
0.010.020.03
0.040.05
0.060.07
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.06-0.04
-0.020
0.02
0.040.06
0.080.1
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.06-0.04
-0.020
0.02
0.040.06
0.080.1
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.04-0.02
00.020.04
0.060.08
0.10.12
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.04-0.02
00.020.04
0.060.08
0.10.12
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.020
0.020.040.06
0.080.1
0.120.14
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
MLP-3-5-1
-0.020
0.020.040.06
0.080.1
0.120.14
1 2 3 4 5 6 7 8 9 10
verbleibende Anfragen
Res
twer
t V*(
i)
Abb. 5: Typisches Ergebnis eines mittels Backpropagation trainierten KNN 3-5-1 nach 20000,
40000, 60000, 80000, 100000, 120000, 140000 und 160000 Anpassungsschritten
Leider gehen die bekannten Lernregeln für KNN davon aus, dass der korrekte Output-Vektor für einen am KNN angelegten Input-Vektor nach getroffener Entscheidung bekannt wird und somit die Abweichung des vom KNN ausgegebenen Output-Vektors zu diesem korrekten Vektor bestimmt werden kann und das Ausmaß dieses Fehlers zur Korrektur der Neuronenge-wichte verwertet werden kann.
Eine solche direkte Rückkopplung erscheint in unserem Anwendungsfall des Yield Manage-ment jedoch nicht möglich: erst am Ende eines gesamten Anfragestroms zeigt sich ein durch das KNN (oder besser: mit Hilfe seiner Restwertfunktion) erwirtschafteter Gesamtdeckungs-beitrag. Von diesem ist aber keineswegs bekannt, wie weit er vom Gesamtdeckungsbeitrag
11
entfernt ist, der mit Hilfe der optimalen Restwertfunktion hätte erwirtschaftet werden können. Zu dessen Ermittlung wäre ja gerade die Wertiteration eines hochdimensionalen Markovschen Entscheidungsprozesses vonnöten, deren prohibitiv hohe Komplexität uns aber erst ein KNN als heuristische Alternative in Erwägung ziehen ließ. Das oben dargestellte Training ist also nur möglich, da wir vorher die korrekte Funktion mittels stochastischer dynamischer Pro-grammierung bestimmt haben.
Wenn somit auch eine absolute Bestimmung der korrekten Restwertfunktion ausscheidet, so ist dennoch der Vergleich unterschiedlicher Restwertfunktionen bezüglich ihrer Leistungs-fähigkeit möglich: verschiedene KNN werden aufgrund ihrer Restwertfunktionen für den glei-chen Anfragestrom unterschiedliche Entscheidungen treffen und somit unterschiedliche Ge-samtdeckungsbeiträge erwirtschaften, d.h. mittels einer Simulation des Anfrageprozesses können „ex post“ sehr wohl Qualitätsunterschiede verschiedener Restwertfunktionen ermittelt werden.
Folglich ist das Problem des Auffindens eines optimalen KNN (also eines, welches diejenige Restwertfunktion repräsentiert, deren Anwendung den maximalen durchschnittlichen Gesamt-deckungsbeitrag erwirtschaftet) prinzipiell analog zu einem Parameteroptimierungsproblem: Der Suchraum dieses Parameteroptimierungsproblems ist der Vektorraum aller Gewichtungs-vektoren aller Neuronen des KNN, der Zielfunktionswert für eine gegebene Parameterkombi-nation der durchschnittliche Deckungsbeitrag, der mit einem KNN mit diesen Gewichtungen dann erzielt wird, wenn genau dieses KNN in einem Annahmeprozess zur Anwendung ge-langt.
2.2 Einsatz evolutionärer Verfahren zur Verbesserung der Restwertfunktion
Betrachten wir dieses Metaproblem der (globalen) Parameteroptimierung, so hängt die Aus-wahl sinnvoller Optimierungsstrategien, wie bei allen globalen Optimierungsproblemen, u. U. stark von den bislang leider unbekannten Struktureigenschaften des Suchraums ab.
Ist dieser unimodal, so könnte prinzipiell ein Gradientenverfahren3 angewandt werden. Die-ses wird aber bedingt durch den hochdimensionalen Suchraum einem auf den Prinzipien der Evolutionsstrategien [Schw95] oder Genetischer Algorithmen (GA) [Gold89] aufbauenden Verfahren hoffnungslos unterliegen: Diese starten, die Suche ausgehend von einer Population von sog. Individuen, also Punkten im Suchraum (hier: KNNs), bestimmen deren Fitness und unterwerfen sie einem Evolutionsprozess, indem solche Individuen mit höherer Fitness häufi-ger „gepaart“ werden, als solche mit geringer Fitness. Die „Kinder“ dieser Paarungsversuche konkurrieren schließlich in der nächsten Generation um weitere Reproduktionsversuche.
Die bei der „Paarung“ anzuwendenden Crossover-Operatoren (CO) stellen das Kernstück und auch den kritischsten Erfolgsfaktor des Verfahrens dar: Bei vielen Reihenfolge- und Zuord-nungsproblemen ist es kaum möglich, strukturelle Eigenschaften zweier Ausgangslösungen so auf eine neue Lösung zu vererben, dass diese alle Nebenbedingungen erfüllt. Diese Schwie-rigkeit wird hier aber nicht auftreten, da jede mögliche Rekombination von Gewichten der zweier KNN wiederum eine valide Restwertfunktion repräsentiert.
3 Hierbei wäre jedes Gewicht einzeln zu verändern und dann das neue KNN mit der maximalen Verbesserung
des Gesamtdeckungsbeitrags als neuer Ausgangspunkt der weiteren Suche zu wählen.
12
Die Anwendung nicht populationsbasierter, lokaler Suchverfahren wirft dagegen die Frage nach der dynamischen Festlegung einer optimalen Stichprobengröße im Suchverfahren auf: Ist die Zahl der für ein gegebenes KNN durchgeführten Simulationen zu gering, besteht die Gefahr, aufgrund von Schätzfehlern den Vektor aller Gewichte w zugunsten einer schlechte-ren Parametrisierung w’ zu verwerfen. Durch eine Erhöhung der Stichprobengröße lässt sich zwar dieses Risiko reduzieren, andererseits sinkt hierdurch die Zahl der verschiedenen Para-metrisierungen, die in einem gegebenen Zeitraum untersucht werden können.
Vor diesem Hintergrund wurden verschiedene infrage kommende KNN-Topologien proto-typisch implementiert und getestet, wobei für diese Tests zuerst einfache Problemstellungen mit lediglich bis zu zwei Ressourcen herangezogen werden, für die sich die optimalen Wert-funktionen V* noch analytisch errechnen lassen und somit die Approximation dieser Funktion durch das KNN und die Abweichung zum Optimum leicht bewertet werden konnte. Hierbei kam die oben erläuterte KNN Architektur zum Einsatz.
Für den die KNN „züchtenden“ GA wurde folgende Ablaufstruktur gewählt:
Zuerst wird eine Population von 10 KNN mit zufälligen Gewichtungsmatrizen erzeugt. Diese werden zur Generierung von 100 Nachkommen herangezogen. Aus Effizienzgründen wurde auf ein aufwendiges Selektionsverfahren verzichtet. Vielmehr wird die Population nach ab-steigender Fitness sortiert und sodann für jede Anwendung des CO ein Elternteil zufällig aus der Population ausgewählt. Der Partner wird sodann lediglich aus denjenigen Individuen se-lektiert, die eine niedrigere Positionsnummer als das bereits gewählte Individuum aufweisen. Dies führt insgesamt zu der gewünschten höheren Selektionswahrscheinlichkeit für qualitativ hochwertige Individuen.
Als CO kommt ein modifizierter 1-Point-Crossover zum Einsatz: Für jeden Layer werden die Zeilen der Gewichtungsmatrizen der beiden zu paarenden KNN zunächst nach einer zufällig gewählten Spalte "geschnitten" und mit den restlichen Zeilen resp. Spalten des Partners re-kombiniert. Dabei stellt jede mögliche Rekombination von Gewichten zweier KNN wiederum eine zulässige Restwertfunktion dar.
Abb. 6: Beispielhafter 1-point-Crossover zweier KNN
13
Vor dem Crossover werden 10% der Individuen einer Mutation unterzogen, welche in jeder Gewichtungsmatrix eine zufällige Zeile oder Spalte auswählt und alle Gewichte dieser Zeile oder Spalte mit einem zufälligen Offset aus dem Intervall [-0.5; +0.5] überlagert.
Zur Bestimmung der Fitness jedes einzelnen KNN der Population werden 100 Anfragepro-zesse simuliert, in den hier gewählten Beispielen zunächst jeweils à 10 Anfragen.
Schließlich wird die Population gemäß dieser Fitness-Werte sortiert und auf die ursprüngliche Größe von zehn reduziert.
Die folgende Abbildung zeigt den Einfluss von Populationsgröße und Sampling-Rate auf die durchschnittliche Fitness der nach 100 Generationen evolvierten Restwertfunktionen. Die Sampling-Rate gibt an, wie viele Anfrageströme (von hier jeweils 10 Anfragen) aus der Ver-teilung der erwarteten Nachfrage „gezogen“ werden, um durch Mittelwertbildung den Schätz-fehler bei der Fitnessbestimmung des Entscheidungsverhaltens einer einzelnen Restwertfunk-tion zu reduzieren. Ist die Sampling-Rate zu klein, so kann der GA ein schlechteres Indivi-duum einem besseren vorziehen, weil das bessere zufällig „einen schlechten Tag“ hatte und 10 minderwertige Anfragen bewerten musste und folglich (trotz richtigen Entscheidungsver-haltens) einen niedrigen Deckungsbeitrag erwirtschaftet.
Abb. 7: Einfluss von Populationsgröße und Sampling-Rate auf die Qualität der „gezüchteten“
Restwertfunktionen (GA mit 100 Generationen)
Jeder Punkt repräsentiert das Ergebnis eines einzelnen GA nach 100 Generationen, die Fläche eine geglättete Mittelwertschätzung für den erwarteten durchschnittlichen Deckungsbeitrags nach 100 Generationen für jede vorgegebene Populationsgröße und Sampling-Rate. Die Ab-bildung zeigt eindeutig den positiven Einfluss der Populationsgröße und Sampling-Rate auf die Ergebnisqualität, ist aber insofern irreführend, als sie den hierfür nötigen Rechenaufwand vernachlässigt: Während bei einer Populationsgröße von 5 und einer Sampling-Rate von 5 pro Generation 5*10=50 „Kinder-KNNs“ erzeugt werden und diese KNNs jeweils 5 mal be-wertet werden müssen (was für den gesamten GA zu insgesamt 100*50*5= 25000 evaluierten Nachfrageströmen führt), sind dies bei einer Populationsgröße von 20 und einer Sampling-Rate von 100 immerhin schon 100*200*100 = 2000000 Evaluationen, also fast schon der hundertfache Rechenaufwand.
14
Da bei den hier verwendeten einfachen Crossover- und Mutations-Operatoren der Aufwand der Erzeugung neuer Individuen hauptsächlich in der Bewertung liegt, wird in den folgenden Abbildungen der obige Zusammenhang nicht für eine feste Zahl von 100 Generationen son-dern für ein „Budget“ von 100000 und 200000 Evaluationen dargestellt: Man erkennt, dass für 100000 Evaluationen die beste erwartete Qualität bei kleine Sampling-Rate und kleinen Populationen erzielt wird. Für 200000 Evaluationen ändert sich dieses Bild in Richtung einer Vorteilhaftigkeit größerer Populationen, allerdings bleibt erstaunlicherweise die Vorteilhaftig-keit kleiner Sampling-Raten erhalten.
Abb. 8: Einfluss von Populationsgröße und Sampling-Rate auf die Qualität der „gezüchteten“
Restwertfunktionen (GA mit 100000 Evaluationen)
Abb. 9: Einfluss von Populationsgröße und Sampling-Rate auf die Qualität der „gezüchteten“
Restwertfunktionen (GA mit 200000 Evaluationen)
15
Dieses Ergebnis bedeutet, dass es sinnvoller zu sein scheint, zusätzliche Rechenzeit in eine Vergrößerung der Population oder eine Verlängerung der Laufzeit des GA, nicht jedoch in eine Erhöhung der Präzision der Zielfunktionsermittlung zu investieren. Dies ist nicht nur von praktischem Interesse für die Parametrisierung des GA im Kontext des Yield Management, sondern unterstreicht eindrucksvoll die Leistungsfähigkeit des intrinsischen Parallelismus eines GA bei der Optimierung „verrauschter“ Zielfunktionen.
Um die Skalierbarkeit unseres Ansatzes für Probleme des Network Yield Management zu testen, wurde ein Problemgenerator für zufällige Anfrageströme einer beliebigen Zahl n benö-tigter Ressourcen spezifiziert. Hierbei wurde zunächst vereinfachend davon ausgegangen, dass 10 unterschiedliche Nachfragetypen, z.B. für 10 unterschiedliche Serviceleistungen mit festem Ressourcenbedarf existieren. Für jeden der 10 Anfragetypen und jede Ressourcen-klasse wird der Bedarf zufällig zwischen 0 und 9 Einheiten bestimmt. Der durch die Anfrage generierte Deckungsbeitrag wird ebenfalls zwischen 0 und 9 zufällig ermittelt (Beschränkung auf Integer-Werte).
Ein solcher Pool mit 10 Anfragetypen und 4 benötigten Ressourcen könnte z.B. wie folgt ge-neriert worden sein:
Kapazitätsbedarf
Deckungsbeitrag Res.1 Res.2 Res.3 Res.4
7.0 9 9 7 4
9.0 1 1 6 4
1.0 4 5 3 4
8.0 9 1 4 6
3.0 6 6 9 3
8.0 6 9 0 5
1.0 4 3 7 7
6.0 2 6 6 0
7.0 6 2 5 0
2.0 7 9 4 3 Tabelle 2: Beispielhafter Pool von 10 unterschiedlichen Anfragetypen mit Ressourcenbedarf
in vier Dimensionen
Bei dieser Problemgröße lässt sich der Zustandraum des Markovschen Entscheidungs-prozesses noch problemlos abbilden, d.h. die optimale Restwertfunktion kann noch berechnet werden, im Beispiel lässt sich z.B. für eine Anfangsverfügbarkeit von [10, 10, 10, 10] bei 10 Anfragen ein maximaler erwarteter Gewinn von 13.067 bestimmen.
Die folgende Grafik zeigt die relative Performanz des GA+KNN-Verfahrens im Vergleich zur Optimallösung: Wie sich leicht erkennen lässt, nimmt diese mit steigender Anzahl von Res-sourcen deutlich ab, wobei zugegebenermaßen der Rechenaufwand für die Ermittlung der Optimallösung exponentiell zunimmt, wohingegen der Rechenaufwand für das GA+KNN-Verfahren mit 500000 Evaluationen konstant gehalten wurde.
16
Abb. 10: Relative Performance des GA in Abhängigkeit von layer size und Anzahl von Ressourcen
Der Abfall der Leistungsfähigkeit des GA+KNN-Verfahrens liegt hierbei in der oben bereits angesprochenen Schwierigkeit begründet, viel versprechende Restwertfunktionen im Such-raum der Gewichtungsvektoren zu finden. Während der GA relativ schnell lernt, dass eine Annahme aller Anfragen zu deutlich besseren Resultaten führt als die vollständige Ableh-nung, kann sich das Individuum, welches dies „herausfindet“, in der Population meist so stark vermehren, dass die Diversifikation und somit der weitere Fortschritt stark leidet.
3 Bekräftigungslernen für Yield-Management-Prozesse
Offensichtlich ist die Tatsache, dass das domänenspezifische Wissen über die strukturellen Eigenschaften der Restwertfunktionen (z.B. ihre Monotonie bzgl. der Zeit- und Ressourcen-dimensionen) in keiner Form in den Suchprozess eingeht, und die Qualität einer Restwert-funktion erst nach ihrer (nicht zielgerichteten) Veränderung durch Mutation und Crossover mittels Simulation evaluiert werden kann, mit steigender Zahl benötigter Ressourcen immer problematischer.
Aus diesem Grund scheint die Suche nach alternativen adaptiven Lernverfahren angezeigt, die entweder die KNN-Repräsentation der Restwertfunktion durch eine problemspezifischere er-setzen, oder aber das GA-Verfahren zur Manipulation dieser Repräsentation durch ein geeig-netes Verfahren ablösen.
In diesem Bereich bietet insbesondere das Forschungsgebiet des sog. Bekräftigungslernens lohnenswerte Ansätze einer Problemlösung. Es handelt sich hierbei um eine simulations-basierte Methode, die aber (im Gegensatz zu unserem GA-KNN-Verfahren) auf der Bell-mann-Gleichung aufbaut, die der stochastischen dynamischen Programmierung als Grundlage dient, vgl. [SuBa99] [BeTs96].
17
3.1 Grundgedanke des Bekräftigungslernens Betrachtet man die oben eingeführten Kernelemente der Entscheidungsoptimierung, – Zu-stände, Aktionen und Bekräftigungen, kann ihnen neben der Interpretation als Ent-scheidungsbaum die folgende Deutung zugeordnet werden [SuBa99, S.52]:
• Ein bekräftigungslernender Agent (RL-Agent) ist mit seiner Umgebung durch eine Sensorik verbunden.
• In jedem Interaktionsschritt erhält der Agent als Input eine Rückmeldung über den Umweltzustand st+1 und den Bekräftigungswert (Reward) rt+1 seiner letzten Aktion a t .
• Der Agent wählt eine Aktion at+1 als Output, die den Umweltzustand st+2 ändert.
• Der Agent bekommt den Wert der Aktion erneut durch ein Bekräftigungssignal rt+2 mitgeteilt.
• Ziel des Agenten ist es, längerfristig die Summe der erhaltenen Bekräftigungssignale zu optimieren.
Reward
st+1
rt+1
Umgebung
RL-Agent
Aktion a t
Zustand st
Abb. 11: Der bekräftigungslernende Agent in Interaktion mit seiner Umgebung
Es stellt sich nun die Frage wie ein Agent unter Verwendung stochastischer dynamischer Programmierung seinen Weg durch den Entscheidungsbaum findet.
3.2 Stochastische Dynamische Programmierung Will man den optimalen Pfad durch einen Entscheidungsbaum ermitteln, steht man vor dem Problem, alle Kanten des Baums durchlaufen zu müssen. So kann man sich z.B. bei einer gierigen myopischen Entscheidungsstrategie, also der Auswahl der jeweils nächsten Kante mit dem größten Bekräftigungswert r i (Greedy-Strategie) nicht sicher sein, den op-timalen Pfad innerhalb des Entscheidungsbaums zu wählen. Es besteht nämlich die Gefahr durch eine zunächst günstige Verzweigung von Knoten s’ zu Knoten s’’ einen im weiteren Verlauf ungünstigen Teilbaum auszuwählen. Dieses Problem führt zum bereits erwähnten exponentiellen Wachstum der Problemgröße mit der Dimension des Zustandsraums4. Bellman [Bell57] löst das Problem der falschen Verzweigungen indem er rekursiv in jeder Zustandsebene s für alle Knoten eine optimale Entscheidung ermittelt.
Hierzu führen wir zwei Begriffe ein:
18
4 Bellman’s Curse of Dimensionality: “At high dimensions every object is far to another”
}{
==== ∑∞
=++
01 ||)(
ktkt
ktt ssrEssREsV γππ
πGleichung 5:
• Der Zustandswert V
π(s)sich aus dem diskontierten Zustandswert Vπ(s’) des nächsten Zustandes s’ addiert zum erwarteten Bekräftigungswert r in t+1 ergibt. So sind zum Beispiel in Abb. 12 drei mögliche Aktionen a von Zustand s aus zu erkennen, die ihrerseits jeweils zwei unter-schiedliche Bekräftigungssignale r(t+1) der Umwelt hervorrufen können und in einen der Zustände s’ in der nächsten Entscheidungsebene übergehen. Die Definition der Zustandswertfunktion als Erwartungswert resultiert aus der Zuordnung von Wahr-scheinlichkeiten πi zu den einzelnen Entscheidungen a, im Zusammenhang mit der verwendeten Politik. Wichtig ist hier, dass bei der Ermittlung der Zustandswerte nach der Bellmanschen Gleichung (Gl. 5) die Zustandswerte Vπ(s’) aller möglichen Ent-scheidungen a gewichtet mit πi in die rekursive Berechnung von V
π(s) eingehen. Da-bei kann die Rekursion durch den Entscheidungsbaum sowohl von den Blättern begin-nend rückwärts, als auch ausgehend von der Wurzel vorwärts erfolgen. Der Diskont-faktor γ ist nicht unbedingt notwendig, erweist sich jedoch als nützlich für das Kon-vergenzverhalten des Bekräftigungslernens.
einer Politik π ist definiert als der Erwartungswert, welcher
Abb. 12: Zu
Gleichung 6:
• π von de a abhängig. Wie in Abb. 13 und aus Gl. 6 ersichtlich, ist für den Zustandsübergang s nach s’ die Auswahl eines Entscheidungspfades durch
die nicht gewählten Pfade gehen daher nicht in die Berechnung von Q
π(s, a) ein. Auf der Entscheidungsebene s’ wird aber wieder die Bellmansche Gleichung
ittlung des Zustandswerts des in s’ verbleibenden Entscheidungsbaums ver-
standsübergangsdiagramm für V
π(s)
s’
rt+1
a
s
Vπ(s’)
π
Vπ(s)
Der Aktionswert Q (s, a) einer Politik ist im Gegensatz zum Zustandswert zusätzlich r in s gewählten Aktion
π
=== ∑
=++
01 ,|),(
kttkt
k aassrEasQ γππ ∞
a festgelegt,
zur Ermwendet.
19
Qπ(s,a)s,a
rt+1
s’ Vπ(s’)
π
a’
Abb. 13: Zustandsübergangsdiagramm für Q
π(s, a)
Ziel des Bekräftigungslernens ist es, den Pfad durch den Entscheidungsbaum zu finden, auf dem die Summe der Bekräftigungssignale maximal wird. Dazu benötigen wir jeweils eine Definition für den optimalen Zustandswert sowie für den optimalen Aktionswert.
{ })'(),(max)( ** sVasrsVa
γ+=
Gleichung 7:
{ }aasssVrEasQ tttt ==+= ++ ,|)(),( 1*
1* γGleichung 8:
• Der optimale Zustandswert ermittelt sich rekursiv auf der Basis der Bellmanschen Gleichung (Gl. 5) mit dem Unterschied, dass nicht alle Entscheidungsalternativen ge-wichtet mit den durch die Politik π vorgegebenen Wahrscheinlichkeiten in die Be-rechnung eingehen, sondern nur diejenige Alternative, bei der der diskontierte Zu-standswert der unteren Entscheidungsschicht zusammen mit dem Bekräftigungssignal r(a, s) der Aktion a den höchsten Zustandswert V* (s) ergibt (Gl. 7).
[ ]∑∑ +ℜ=
==+= +++'
'''
111 )'(max,|)(max)(s
ass
assas
tttktak sVPaasssVrEsV πγγ (Gl. 8).
• Analog zu Gl. 7 ist der optimale Aktionswert Q*(s, a) einer Politik π der diskontierte optimale Zustandswert einer durch a gewählten Aktion zuzüglich des Bekräftigungs-signals r(a,
ichun :
20
σ≤−+∈ |)()(|max 1 sVsV kkSsGleichung 10:
Bisher sind wi
s)Gle g 9
ung von V* (s) kann auch alternativ zu Gl. 7 als Näherungswert durch die wiederholte Berechnung von Vk+1(s) nach Gl. 9 als so genannte Wertiteration erfolgen.
m ert kleiner als ein Schwellwert σ wird (Gl. 10).
r davon ausge e Entscheidungspolitik zu Beginn vorgegeben ist und bis zum ten wird. Denkbar ist jedoch auch eine An-
olitik während der Auswertung, um nicht den gesamten Entscheidungsbaum
Die Berechn
Die Iteration erfolgt so lange, bis die Differenz von neu berechnetem Zustandswert zuvorhergehenden W
gangen, dass di Ende der Auswertung beibehal
passung der Pzur Bewertung der Politik evaluieren zu müssen. Ein solches Verfahren trägt die Bezeich-nung Politikiteration, da sich hier nicht nur die Zustandswerte ändern, sondern auch die Entscheidungspolitik variiert. Bei der Politikiteration muss zunächst festgestellt werden, ob eine Änderung der Politik π zu π’ im Zustand s zu einer Verbesserung von V
π(s) führt und ob diese Verbesserung auch für die Anwendung der Politik π’ auf alle weiteren Ent-
[ ]∑ +ℜ=='
'' )'(maxarg),(maxarg)('s
ass
assaa
sVPasQs ππ γπ
[' aaπ
scheidungssituationen gilt. Mit Hilfe des so genannten Politikverbesserungstheorems5, kann man zeigen, dass für zwei deterministische Politiken π und π’ eine ständige Verbes-serung von Politik π’ möglich ist, sofern die Wertfunktion V
π(s) der Politik π im Knoten s bekannt ist und sofern man in jedem besuchten Zustand s die für den nächsten Entschei-dungsschritt optimale Politik auswählt (Gl. 11): Gleichung 11:
π VV→ Vπ
π→greedy(V)
Evaluation
und Verbesserung in Richtung einer Greedy-Strategie ist in Abb. 15 als Algorithmus for-muliert, bei dem die Zweiteilung in Evaluation (Gl. 11) und Verbesserung (Gl. 12) deut-ich zu erkennen ist.
Verbesserung•
•
π∗ V*
]∑ +ℜ= ' )'()( sVPsV πγ
, dass sobald V
π(s) zu π' optimiert at (Verbesserung), eine n itteln kann (Evaluation) um damit
π' wiederum zu π'' optimieren, usw. Der in Abb. 14 dargestellte Wechsel von Evaluation
l
Abb. 14: Wechsel von Eval und Verbesserung bei der Politikiteration
Gleichung 12: '
''s
ssss
Dies bedeutet man eine Politik π unter Verwendung von eue Wertfunktion V
π'(s) ermh
uation
5 Ein kurzer Beweis hierzu findet sich in [SuBa99, S.95]
21
Abb. 1
Ein Nfach ddoch zEvaluaSchritGleichu
Der W
Abb. 1
6 Konvergen
1. Initialisierung
V(s) ∈ ℜ und π(s) ∈ A(s) beliebig für alle s ∈ S
2. Politikevaluation
Wiederhole
∆ 0←
Für jedes s ∈ S:
[ ]( ))(;max
)'()()(
)(''
)('
sVv
sVssVv
ssss
sss
−∆←∆
+ℜΡ←
←
∑ γππV
bis ∆ < θ (eine kleine positive Zahl)
3. Politikverbesserung
Politik-stabil ← wahr
Für jedes s ∈ S:
5: Politikiterationsalgorithmus
[ ]∑ +ℜ='
'''
' )'(max)(s
ass
assa
sVPsV ππ γ
achteil der Politikiteration ist, dass in der Evaluationsphase einige Zustände mehr-urchlaufen werden müssen bis V
π(s) hinreichend genau ermittelt ist6. Man kann je-eigen, dass das Politikverbesserungsverfahren auch dann konvergiert, wenn in der tionsphase der Zustandsraum nur genau einmal durchlaufen wird. Damit fallen
t 2 und 3 der Politik (Gl. 13). ng 13:
iteration zur Wertiteration zusammen
ertiterationsalgorithmus ist in Abb. 16 dargestellt:
Initialisiere ν beliebig, z.B. V(s) = 0, für alle s ∈ S +
Für jede
Wiederhole
←∆ 0
s s ∈ S:
[ ]( ))(;max
)'(max)( '' '
sVv
sVsV asss
assa
−∆←∆
+ℜΡ← ∑ γ
)(sVv ←
bis ∆ < θ (eine kleine positive Zahl)
ationsalgorithmus
6: Der Wertiter
z gegen den exakten Wert wird nur als Grenzwert erreicht.
22
3.3 Monte-Carlo-Methode Ein Nachteil der bisher beschrieben Verfahren zur Ermittlung von V(s) mittels der dyna-mischen Programmierung ist, dass alle Zustände im Entscheidungsbaum durchlaufen wer-den müssen um die Wertfunktion eines Zustands s zu ermitteln (full-backup). Da es meist ausreicht V(s) nur grob zu schätzen, kann man sich hier einer Monte-Carlo (MC) Methode bedienen. Dazu wird nicht der komplette Entscheidungsbaum durchlaufen sondern nur einzelne Pfade, so genannte Episoden; in Abb. 17 sind dies die Kantentupel (r1, r3, r7) und (r1, r4, r8). Beim Durchschreiten der Episoden in der Evaluationsphase werden dann einfach die Mittel der Bekräftigungswerte auf den durchlaufenen Kanten als Schätzer für die Zustandswerte benutzt. Zwei Vorgehensweisen haben sich hier etabliert:
• Die first-visit MC-Methode:
34,4)( =sV π
5,5)'( =sV π
6)''( =sV π
9)''( =sV π
r7 = 6
r3 = 5 r4 = 4r1 = 2 r8 = 9
Abb. 17: Beispiel für den Durchlauf zweier Episoden in der first-visit MC-Methode
Bei ihr werden ausgehend von den Blättern des Entscheidungsbaums die bereits ausgewählten Episoden durchlaufen und jeweils der Mittelwert der vohergehenden Bekräftigungswerte eingetragen. Im Beispiel Abb. 17 ist das zunächst der Pfad (r7, r3, r1) mit den Werten (6; 5,5; 4,34). Wird beim Durchlaufen einer Episode ein bereits aufgesuchter Zustand s erreicht, so bleibt der bei dem ersten Besuch für V(s) eingetragene Mittelwert bestehen (first-visit). Im Beispiel ist dies bei der zweiten Episode (r8, r4, r1) für die Zustandswerte Vπ(s’) = 5,5 und Vπ(s) = 4,34 der Fall.
Abb.18 zeigt ausführlich den Algorithmus zur First-visit-Methode.
Initialisiere
π ← zu evaluierende Politik
V ← beliebige Zustandswertfunktion
returns(s) ← leere Liste, für alle s ∈ S
Wiederhole endlos:
(a) Generiere eine Episode unter Verwendung von π
(b) Für jeden Zustand s der auf der Episode liegt:
R ← Bekräftigungswert bei erstem Durchlaufen von s
Füge R in returns(s) ein
V(s) ← gemittelte(returns(s))
23
Abb. 18: Der first-visit Monte-Carlo Algorithmus
• Die every-visit MC-Methode:
Diese unterscheidet sich nur durch die Update-Strategie der Zustandswerte von der first-visit MC-Methode. Im Gegensatz zur first-visit MC-Methode wird ein bereits be-suchter Zustand s bei der Every-visit-MC-Methode nach einer Update-Regel verbes-sert, z.B. der konstant-α MC-Methode:
[ ])()()( ttttneu sVRsVsV −+= απ
Gleichung 14:
Für α = 0,2 ergibt sich dann für das oben beschriebene Beispiel folgende Zuordnung von Zustandswerten:
34,4)( =sValtπ 5,5)'( =sValt
π 6)''( =sV altπ
47,4)( =sVneuπ 7,5)'( =sV neu
π 9)''( =sV neuπ
Bisher wurde noch nichts über die Auswahl der Episoden bei der MC-Methode gesagt. Die Auswahlstrategie ist jedoch entscheidend für eine möglichst genaue Schätzung der Zustands-werte, da die MC-Methode nur exemplarisch Pfade aus dem Entscheidungsbaum auswählt und diese auswertet (sample-backup). Bei der Auswahl der Episoden bietet sich die gleiche Vorgehensweise an, wie bei der Politikiteration.
Zunächst wird ausgehend von einer beliebigen Entscheidungspolitik im Rahmen der Evalua-tionsphase eine Episode im Entscheidungsbaum generiert. Entlang dieser Episode werden dann mit der First- bzw. Every-visit-Methode die Aktionswerte der Zustände errechnet. In der Verbesserungsphase erfolgt daraufhin eine Optimierung der gewählten Politik durch die An-passung des Entscheidungsfindungsprozesses in Richtung der jeweils maximalen Aktionswer-te. Dieser Vorgang wird analog zur Politikiteration zyklisch durchlaufen (Abb. 14). Ein wich-tiger Aspekt der MC-Methode ist die Art der Politikgestaltung für ein erfolgreiches Generie-ren von Episoden. Verwendet man deterministische Entscheidungspolitiken, so wird der da-mit erzeugte Pfad im Entscheidungsbaum immer derselbe sein. Die zur Erzielung eines Lern-effekts benötigte Exploration findet hier nicht statt. Um dies zu erreichen, muss der MC-Algorithmus noch mit einem stochastischen Element ausgestattet werden. Dies erfolgt in der Praxis auf zwei verschiedene Arten, durch eine so genannte On-Policy- oder eine Off-Policy-Methode
3.3.1 On-Policy-Methode
Bei dieser Variante der MC-Methode basiert das stochastische Element bei der Pfadauswahl auf dem Umstand, dass in einem Zustand s mit einer geringen Wahrscheinlichkeit )(/ sAε nicht die Entscheidungsvariante mit dem größten Aktionswert Q(s,a) ausgewählt wird, son-dern eine der verbleibenden suboptimalen Entscheidungen. Dies führt dazu, dass bei dieser als ε-greedy bezeichneten Politik auch Pfade mit zunächst schlechter geschätztem Aktionswert gewählt werden können. Da bei der Auswahlpolitik keine Episode gänzlich ausgeschlossen ist, ist das Durchlaufen aller Pfade im Grenzfall garantiert7. Abb. 19 zeigt den zugehörigen
24
Algorithmus für die Evaluationsphase. Ein wichtiges Merkmal des hier gezeigten Algorith-
7 Dies begründet die alternative Benennung der Politik als ε-soft policy.
mus ist außerdem, dass die Schätzpolitik identisch ist mit der zu verbessernden Politik ist (On-Policy)8.
3
D
s
Scπ’t
vomjekaihmde
G
Dπ
8 I
9 D
Initialisiere für alle s ∈ S , a ∈ A(s) = 0:
e Liste
Politik
Wie erh
eine Episode unter Verwendung von π
en von s,a
s(s,a))
Q(s,a) ← beliebig
returns(s,a) ← leer
π ← eine beliebige ε-soft
d ole endlos:
(a) generiere
(b) Für jedes Paar s,a, das in dieser Episode auftritt:
R ← Bekräftigungswert bei erstem Durchlauf
Füge R in returns(s,a) ein
Q(s,a) ← gemittelte(return
(c) Für jedes s in dieser Episode:
Abb. 19: Der ε-soft On-Policy Monte-Carlo Algorithmus
.3.2 Off-Policy-Methode
er Vorteil der Off-Policy-Methode liegt in der Möglichkeit, anhand eines bereits mit der
leichung 15:
amit lässt sich nun der Off-Policy-MC-Algorithmus formulieren, bei dem die Schätzpolitik
hätzpolitik π hinreichend evaluierten Entscheidungsbaums eine andere Verhaltenspolitik erkunden und verbessern zu können, ohne alle Q-Werte neu berechnen zu müssen. Dabei ellt sich die Frage, ob bei der Trennung von Schätz- und Verhaltenspolitik Rückschlüsse n den Aktionswerten der einen Politik auf die Q-Werte der anderen möglich sind. Ordnet an den Knoten s des Baums Wahrscheinlichkeiten p i(s) bzw. p i’(s) zu mit denen sie den weiligen Zustand unter der Schätzpolitik π bzw. der Verhaltenspolitik π’ aufsuchen, so nn man den unverzerrten Schätzer für V(s) aus beiden ε-soft Politiken9 mit dem Verhältnis rer Besuchswahrscheinlichkeiten beschreiben. Nach einigen weiteren Umformungen erhält an das Verhältnis der Übergangswahrscheinlichkeiten, das unabhängig von der Dynamik s beobachteten Systems ist (Gl. 15):
−)()( sTti isp
über das Verhältnis ω die Verhaltenspolitik π’ schätzt (Abb. 20).
∏ ==
),(')(' tkkk
kk
ti assp π1 ),( asπ
m Unterschied zu der im nächsten Abschnitt beschriebenen Off-Policy Methode, bei der die zur Ermittlung der Q-Werte benutzte Politik (Schätzpolitik) und die zu verbessernde Zielpolitik (Verhaltenspolitik) unterschied-lich sind.
ie Politiken dürfen in keinen Zustand s die Besuchswahrscheinlichkeit 0 haben, sie müssen daher ε-soft sein.
25
Initialisiere für alle s ∈ S , a ∈ A(s):
von Q(s,a)
he Politik
iederh
e Politik π ' um eine Episode zu generieren:
1 ; a1 ; .... sT-1 ; aT-1 ; rT ; sT
(b) τ ← letzter Zeitpunkt, zu dem aτ ≠ π (sτ)
isode zum Zeitpunkt τ oder später auftritt:
Q(s,a) ← beliebig
Z(s,a) ← 0, Zähler
D(s,a) ← 0, Nenner
π ← eine beliebige, deterministisc
W ole endlos:
(a) Wähle ein
s0 ; a0 ; r1 ; s
(c) Setze für jedes Paar s,a, das in dieser Ep
t ← Zeitpunkt des ersten Auftretens von s,a, so dass gilt t ≥ τ
∏ +=←
1 ),('tkkk asπ
ω −1 1T
tRasZasZ ω+← ),(),(
ω+← ),(),( asDasD
),(),(),(
asDasZasQ ←
(d) Für jedes s ∈ S: π (s) ← arg max a Q(s,a)
26
Abb. 20: Der Off-Policy Monte-Carlo Algorithmus
3.4 Temporal Difference Learning rammierung die optimale Aktion a für ene k ausgewählt werden kann, sofern
wir nur über die Evaluation einer Politik mit dem TD(0)-Verfahren Aussa-gen gemacht, eine Methode zur Politikverbesserung wurde noch nicht betrachtet. Für das
)]()([)()( 11 ttttt sVsVrsVsV −++← ++ γαπ
alle Aktionen im Baum bis zu diesem Zeitpunkt t ausgewertet wurden (full-backup), ist die MC-Methode darauf angewiesen, zumindest eine Episode auf der der Zustand s liegt exemplarisch zu durchlaufen, um die neuen Q-Werte zu bestimmen (sample-backup) und eine optimale Entscheidung zu treffen. Temporal Difference Learning versucht nun die Nachteile der beiden Verfahren zu meiden und ihre Vorteile zu kombinieren. Ausgehend von der konstant-α MC-Methode kann man den Horizont einer Episode auf einen Ent-scheidungsschritt verkürzen und darauf vertrauen, dass das Verfahren dennoch konver-giert, was für hinreichend kleine α auch der Fall ist (Gl. 16): Gleichung 16:
Während bei der stochastischen dynamischen Progden nächsten Zustand s auf einer Entscheidungseb
Bisher haben
TD(0)-Verfahren gilt hier dasselbe wie für die MC-Methoden; ein ständiger Wechsel aus Politikevaluation und Verbesserung im Aktionswerteraum, wie bereits aus Abb. 12 be-kannt, stellt das geeignete Verfahren dar. Wir schreiben daher Gl. 16 in Q-Werten (Gl. 17):
Gleichung 17: [ ]),(),(),(),( asQasQrasQasQ 111 ttttttttt −++← +++ γα
Daraus lässt sich nun leicht ein Politikiterationsalgorithmus für das TD(0)-Verfahren her-
bb. 21: On-Policy-Temporal-Difference-Algorithmus
3.5 Q-Learning nte des oben beschriebenen TD(0) Politikiterationsalgorithmus ist
Gleichung 18
darg -greedy Politik als
leiten (Abb. 21). Schätzpolitik und Verhaltenspolitik sind in diesem Fall gleich (ε-greedy), so dass das Verfahren zur den On-Policy Verfahren gezählt werden kann.
A
Die Off-Policy Variadas wohl bedeutendste Verfahren für das Bekräftigungslernen. Es wurde 1989 von Wat-kins [Watk89] formuliert und trägt den Namen Q-Learning. Hierbei findet eine Annähe-rung an die optimale Aktionswertfunktion direkt und unabhängig von der Evalua-tionspolitik statt, indem nur der Pfad mit dem größten Aktionswert in die Berechnung der einperiodigen Differenz eingeht:
(),( sQasQ ← [ ]),(),(max), 1 tttatttt asQasQra −++ +γα
Für den hier estellten Algorithmus (Abb. 22) wurde wieder die εSchätzpolitik gewählt:
Initialisiere Q(s,a) beliebig
en Schritt der Episode):
er aus Q abgeleiteten Politik (z.B. ε-greedy)
Wiederhole für jede Episode
Initialisiere s Wiederhole (für jed
Wähle a aus s unter Verwendung ein
Führe Aktion a aus und beobachte r, s’
[ ]),()' asQa,'(max),(),( ' sQrasQasQ a −++← γα
Initialisiere Q(s,a) beliebig
r Verwendung einer aus Q abgeleiteten Politik (z.B. ε-greedy)
aus Q abgeleiteten Politik (z.B. ε-greedy)
Wiederhole für jede Episode
Initialisiere s
Wähle a aus s unte
Wiederhole (für jeden Schritt der Episode):
Führe Aktion a aus und beobachte r, s’
Wähle a’ aus s’ unter Verwendung einer
[ ]),()','(),(),( asQasQrasQasQ −++← γα
s ← s’ ; a ← a’; bis s Endwert ist
Abb. 22: Der Q-Learning Algorithmus
27
3.6 Anpassung des Bekräftigungslernens an die Problem-stellung des Yield Management
Werti stwertfunktion10 für alle möglichen Zustände bestimmt, und hierauf aufbauend ebenso mit Stage 1 und allen weiteren Stufen des
V(7,5) + 1; V(7,6)] gesetzt werden. Muss beim nächsten Anfrageprozess beispielsweise auf Stage 9 eine
angepasst werden, wo-
urelle Abwei-chung der Nachfrage festgestellt wird. Dies muss "außerhalb" des Annahme-Verfahrens er-
epräsentation höherdimensionaler Zu-
Zunächst wurde eine Ersetzung der in der dynamischen Programmierung üblichen Wertite-ration durch ein Temporal-Difference-Learning TD(0) durchgeführt. Während die klassische
teration, bei Stage 0 beginnend, die komplette Re
Entscheidungsprozesses verfährt, verzichtet TD(0) vollständig auf diese Initialisierung der Restwertfunktion, sondern beginnt mit einer willkürlichen Funktion (z.B. V(stage, state) = 0 für alle Stages und States) und verbessert diese falsche Funktion im Entscheidungsablauf.
Auf Basis der falschen Restwertfunktion werden selbstverständlich Fehlentscheidungen ge-troffen, wie z.B. die Annahme eines Typs F1 aus unserem Standardbeispiel aus Abb. 1 zu Stage 8, da V(7, 5)+1 > V(7,6), solange V für alle Stages und states Null beträgt.
Allerdings wird sofort nach der Annahme nun ein Update für den Ausgangszustand dieser Entscheidung durchgeführt, d.h. unter der Annahme, dass V(7,5) und V(7,6) korrekt wären, und lediglich Anfragen vom Typ F1 zu beantworten wären, könnte V(8,6) = max [
Entscheidung getroffen werden, in welcher V(8,6) benötigt wird, so hat das Verfahren aus dem letzten Durchlauf bereits gelernt, dass dieser Wert nicht Null ist.
Da nun aber neben F1 noch weitere Anfragetypen mit anderen Erlösen auftreten und anderer-seits auch die Werte für Stage 7, die als Grundlage dieser Berechnung dienten, sich im Zeitab-lauf weiter ändern werden, muss auch der Wert V(8,6) immer wiederbei die Regel des in TD(0) anzuwendenden Updates lediglich den Parameter α enthält, der die Gewichtung des gerade ermittelten zum bisherigen Wert vorschreibt. Wird diese Lernrate zu hoch gewählt, so "überreagiert" das System auf einzelne Anfragen und "vergisst" die Historie zu schnell, ist er andererseits zu niedrig, so werden auf Basis der falschen Anfangswerte zu viele Fehlentscheidungen getroffen, bevor die korrekten Werte gelernt wurden.
Ein weiterer Vorteil des Reinforcement Learning ist hier bereits implizit zu erkennen: Die bei klassischer dynamischer Programmierung in einem Initialisierungslauf gelernte Restwertfunk-tion ist statisch, muss also reinitialisiert werden, sobald eine signifikante strukt
folgen! Bei Reinforcement Learning stellt sich das Verfahren mittels der getroffenen Ent-scheidungen und vorgenommenen Anpassungen der Wertfunktionen selbständig auf die fest-gestellten Veränderungen der Nachfrage ein: Würde z.B. F3 im obigen Beispiel plötzlich ü-berhaupt nicht mehr angefragt, würde sich (je nach Lernfaktor α) die Funktionswerte so an-passen, dass ein F2 in jedem Fall angenommen wird.
Unsere Implementierung erfolgte durch Anpassung der in Java realisierten Module für Mar-kovsche Entscheidungsprozesse und KNNs. Die Verwendung von KNNs ist nötig, da natür-lich auch Reinforcement-Learning das Problem der Rstandsräume nicht entschärfen kann. Trotzdem besteht ein wesentlicher Vorteil der Verfahren nun darin, dass z.B. bei Repräsentation der Restwertfunktion in einem KNN dieses direkt im Entscheidungsablauf per Backpropagation mit den neuen Restwerten trainiert werden kann. Dass diese Trainingssamples zu Beginn des Trainings fast genauso falsch sind wie die in dem
10 Wertfunktion des Bekräftigungslernens (RL) und Restwertfunktion des Yield-Management (YM) sind hier
gleichzusetzen, die unterschiedliche Nomenklatur entstammt den unterschiedlichen Perspektiven. Beim YM zählt nur die verwertbare Restkapazität, beim RL wird die Summe der Bekräftigungen allgemein als Wert angesehen.
28
KNN repräsentierte Wertfunktion, verzögert lediglich das Training, behindert aber nicht die langfristige Konvergenz. Ein entscheidender Vorteil besteht aber darin, dass dieses iterative Training des KNN im Anfrageprozess die Anwendung der GA überflüssig macht, weil das Feedback direkt bei jeder Entscheidung und nicht erst nach einem komplett durchlaufenen Anfrageprozess in entsprechende Lernimpulse rückgekoppelt werden kann.
3.7 Vergleich der Ergebnisse des Bekräftigungslernens mit denen der Genetischen Algorithmen
sione gleich der Leistungsfähigkeit mit klassischer Dynamischer Programmierung durchführen, weil alle möglichen Zustände und
Serviceleistungen mit festem
Für unsere oben beschriebenen Testprobleme mit moderater Zahl von Ressourcen-Dimen-n (1 - 4) lässt sich auch für TD(0) wieder ein direkter Ver
ihr Restwert für alle Stufen direkt repräsentiert werden können.
Der Problemgenerator wurde für zufällige Anfrageströme einer beliebigen Zahl n benötigter Ressourcen spezifiziert. Hierbei wurde zunächst vereinfachend davon ausgegangen, dass 10 unterschiedliche Nachfragetypen, z.B. für 10 unterschiedliche Ressourcenbedarf existieren. Für jeden der 10 Anfragetypen und jede Ressourcenklasse wird der Bedarf zufällig zwischen 0 und 9 Einheiten bestimmt. Der durch die Anfrage generierte Deckungsbeitrag wird ebenfalls zwischen 0 und 9 zufällig ermittelt (Beschränkung auf Inte-ger-Werte).
Abb. 23: Relative Performance des TD(0) Reinforcement Learning in Abhängigkeit von Anzahl
der Ressourcen und der Evaluationen
Wie aus Abb. 24 zu erkennen, wird schon nach 20.000 Evaluationen eine Qualität erreicht, urchs
negative Korre festzustellen ist. die im D chnitt mehr als 95% des Optimalwertes entspricht wobei keinerlei signifikante
lation mit der Zahl der Ressourcen
29
Abb. 24: Relative Performance des TD(0) Reinforcement Learning mit in 3-Layer-KNN reprä-
sentierter Restwertfunktion (links für 50.000 Evaluationen, rechts für 500.000 Evaluatio-nen)
Für eine als KNN repräsentierte Restwertfunktion reichen dagegen bei höherdimensionalen Restwertfunktionen 50.000 Evaluationen noch nicht aus, um eine gute Approximation zu er-reichen. Selbst bei 500.000 Evaluationen ist das Training nur bei kleinem Hiddenlayer halb-wegs abgeschlossen. Durch eine höhere Lernrate α kann diese Konvergenz beschleunigt wer-den. Entsprechende Tests werden zurzeit durchgeführt.
Wird nochmals die oben ausgeführte, in Abb. 7 dargestellte relative Performanz des GA+KNN-Verfahrens im Vergleich zur Optimallösung betrachtet, die mit 500000 Evalu-ationen erzielt werden konnte, so erkennt man in Abb. 24 deutlich die Überlegenheit des hier verwendeten TD(0)-Verfahrens.
Die viel versprechenden Konvergenzresultate zum TD(0) Learning widerlegen also unsere ur-sprüngliche Befürchtung, dass ein direktes Lernen aus den Einzelentscheidungen des KNN nicht sinnvoll realisiert werden kann und daher auf GA oder ein anderes Verfahren ausge-wichen werden muss, welches die gesamte Restwertfunktion „blind“ verändert, um dann den veränderten Funktionsverlauf mittels einer neuen Simulation erneut zu evaluieren.
Wie bereits oben ausgeführt, besteht ein weiterer wesentlicher Vorteil des Reinforcement Learning in der Tatsache, dass eine direkte Anpassung an eine sich ändernde Nachfragestruk-tur erfolgt und die vorher nötige komplette Reinitialisierung der Restwertfunktion überflüssig wird. Allerdings erfordert die Anpassung ein geeignetes "Tuning" der Lernrate. Erste Tests sprechen dafür, dass auch eine dynamische Anpassung der Lernrate sinnvoll sein kann, falls Phasen höherer Volatilität der Nachfrage z.B. durch ein einmaliges Ereignis ausgelöst werden und ein schnelles Reagieren nötig ist.
4 Zusammenfassung und Ausblick
Zusammenfassend lässt sich festhalten, dass die Probleme der dynamischen Bepreisung von (automatisierter) Informationsproduktion für eine anonyme Marktnachfrage große Ähnlich-keiten mit dem im Yield-Management anderer Dienstleistungen aufweisen. Allerdings lassen sich auch zahlreiche Besonderheiten feststellen, die eine direkte Übernahme der Yield-Management Verfahren erschweren. Trotzdem scheint keines der aufgeworfenen Probleme unüberwindbar. Im Gegenteil: Die Adaption erscheint deutlich leichter zu leisten als eine An-passung der klassischen betriebswirtschaftlichen Preistheorie.
30
Die größten Schwierigkeiten einer Anwendung liegen im informationellen wie im materiellen Bereich in der Komplementarität bestimmter Potenzialfaktoren, die entweder gleichzeitig verfügbar sein müssen oder sequentiell zur Abarbeitung der Verarbeitungsprozesse benötigt werden. Somit treten die aus dem Bereich der Produktionsablaufplanung bekannten Schedu-ling-Probleme in ihrer gesamten Komplexität auch hier im Rahmen der optimalen Kapazitäts-bepreisung auf und müssen mittels geeigneter heuristischer Verfahren gelöst werden.
Beim Vergleich der Reinforcement-Learning-Ansätze mit den zuvor implementierten GA+KNN-Verfahren und den klassischen Verfahren der Preisfindung in stochastischen Ent-scheidungsprozessen wurde die starke Überlegenheit des Reinforcement Learning doku-mentiert. Allerdings wurden generierte Test-Probleme mit moderater Zahl von Ressourcen-Dimensionen (1 - 4) verwendet, um auch für TD(0) alle möglichen Zustände und ihren Rest-wert für alle Stufen direkt repräsentieren zu können und so einen direkten Vergleich der Leis-tungsfähigkeit mit klassischer Dynamischer Programmierung durchführen zu können.
Wie aus der obigen Abbildung 24 zu erkennen, ist, wenn man die Zustände nicht direkt reprä-sentiert, sondern ein einfaches Multi-Layer-Perceptron (MLP) trainiert, die Qualität z.B. bei 50.000 Evaluationen deutlich geringer. Diese steigt bei einer höheren Zahl von Evaluationen beim MLP-KNN nochmals deutlich an, allerdings zeigt sich, dass für den Praxiseinsatz des Verfahrens die Effizienz dieser Repräsentation durch weitere Anpassungen deutlich gesteigert werden muss oder aber andere Wege der Zustandsraumkompression eingeschlagen werden müssen.
Hierzu bietet sich insbesondere die Adaption der folgenden drei Verfahren auf die Problem-stellung des Yield Management und die Lösungsmethode des Reinforcement Learning an:
•
•
•
Methoden der Vektorquantisierung ([Lloy82], [MacQ67]), welche in häufig durchschrit-tenen Bereichen der Restwertfunktion eine deutlich feinere Granularität der Repräsentati-on aufweisen als in selten durchschrittenen.
Kohonen Maps (vgl. [Koho82a], [Koho82b], [Koho95], [RiMS90]), in welchen im Ge-gensatz zum bisher eingesetzten MLP nur benachbarte Neuronen miteinander wechsel-wirken,
Neural Gas-Algorithmen (vgl. [Mart93], [MaSc94]), welche ebenfalls nur benachbarte Neuronen in den Lernprozess einbeziehen, statt einer festgelegten Nachbarschaft auf ei-nem Gitter allerdings die euklidische Metrik dazu verwenden, die Stärke der Wechselwir-kung zwischen den Nachbarn zu bestimmen.
Bislang werden lediglich Nutzenkomplementaritäten zwischen den von einem Akteur nachge-fragten Einzelgütern eines Güterbündels untersucht, also gerade von allen Netzeffekten zwi-schen verschiedenen Nachfragern abstrahiert. Eine Integration der hier untersuchten ange-botsseitigen Komplementaritäten mit nachfrageseitigen Verbundeffekten wäre ein lohnens-wertes wenngleich ambitioniertes Forschungsvorhaben. Prinzipiell sollte aber auch hier einem Einsatz von Reinforcement Learning nichts entgegenstehen.
Eine weitere Perspektive eröffnet sich für den hier aufgezeigten Ansatz des Bekräftigungs-lernens zur Lösung der Yield-Management-Problematik, wenn der Ressourcenallokationspro-zess über eine Gemeinschaft mehrerer lernfähiger Agenten abläuft. Der Einsatz von Multi-agentensystemen mit RL-lernenden Akteuren [HuWe98] konnte u. a. im Bereich des klassi-schen Yield-Managements für den Luftfahrtsektor erfolgreich getestet werden [GoBT99]. Eine Fortentwicklung des hier präsentierten Verfahrens in diese Richtung scheint daher loh-nenswert.
31
[AlBM86] Alstrup, J.; Boas, S.; Madsen, O. et al.: Booking Policy for Flights with two Types of Passengers; European Jour-nal of Operational Research 27, S. 274-288
[Bell57] Bellman, Richard E.: Dynamic Programming, Princeton Uni-versity Press, Princeton, 1957
[Belo87] Belobaba, P.: Air Travel Demand and Airline Seat Inventory Management, Ph.D. Thesis, Massachusetts Institute of Technology, Cambridge MA, 1987
[Belo89] Belobaba, P.: Application of a Probabilistic Decision Model to Airline Seat Inventory Control, Operations Research 37, 1989, S. 183-197
[BePo00] Bertsimas, Dimitris; Popescu, Ioana: Revenue Management in a Dynamic Network Environment, eingereicht bei Transportation Science, 2000
[Bert90] Bertsch, L.: Expertengestützte Dienstleistungskostenrechnung, Poeschel, Stuttgart, 1990
[BeTs96] Bertsekas, Dimitri; Tsitsiklis, John: Neuro-Dynamic Pro-gramming, Athena Scientific, Belmont, MA, 1996
[Bish95] Bishop, Christopher M.: Neural Networks for Pattern Recog-nition, Oxford University Press, Oxford, 1995
[ChGJ99] Chen, Victoria C.; Günther, Dirk; Johnson, Ellis: Airline Yield Management: Optimal Bid Prices for Single Hub Problems without Cancellations, eingereicht bei Journal of Transportation Science, 1999
[Debr59] Debreu, G.: Theory of Value, John Wiley and Sons, New York, 1959
[Doer84] Doerninger, W.: Approximating General Markovian Decision Problems by Clustering their State- and Action-Spaces; Math. Operationsforschung und Statistik; Ser. Optimization 15, 1984, S. 135-144
[GoBT99] Gosavi, Abhijit; Bandla, Naveen; Tapas, Das K.: A Rein-forcement Learning Approach to Airline Seat Alloca-tion for Multiple Fare Classes with Overbooking, ein-gereicht bei Management Science, 1999
[Gold89] Goldberg, D. E.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison Wesley, Reading, MA, 1989
[HiKi76] Hildenbrand, W; Kirman A. P.: Introduction to equilibrium analysis, Amsterdam (North-Holland), 1976
[Holl75] Holland, J. H.: Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biol-ogy, Control and Artificial Intelligence. University of Michigan Press, Ann Arbor, MI
32
[Horn91] Hornick, S.: Value Based Revenue Management – A New Paradigm for Airline Seat Inventory Control, In Behrendt, R.; Bertsch, L. H.; Hrsg., Advanced Soft-ware Technology in Air Transport 91, AIT-Verlag, Halbergmoos, 1991
[Huma01] Humair, Salal: Yield Management for Telecommunication Networks: Defining a New Landscape, In: Disserta-tion, MIT, 2001
[HuWe98] Hu, Junling; Wellman, Michael P.: Multiagent Reinforcement Learning: Theoretical Framework and an Algorithm. In: Proceedings of the Fifteenth International Confer-ence on Machine Learning, Madison 1998, S. 242-250
[Kime89] Kimes, S.: Yield Management, A Tool for Capacity-Constrained Firms, Journal of Operations Management 4, 1989, S. 348-363
[Koho82a] Kohonen, T.: Self-organized Formation of Topologically Cor-rect Feature Maps, In: Biological Cybernetics (43), 1982, S. 59-69
[Koho82b] Kohonen, T.: Analysis of a Simple Self-Organizing Process, In: Biological Cybernetics 44, 1982, S. 135-140.
[MacQ67] MacQueen, J.: Some methods for classification an analysis of multivariate observations; In: LeCam, L.; Neyman, J. (eds.): Proc. of the 5th Berkeley Symposium on Mathematical Statistics, and Probability (1), Berkeley, University of California Press, CA, 1967, S. 281-297
[Mali74] Malinvaud, E.: Lectures on Microeconomic Theory, Amster-dam (North Holland), 4th ed., 1974
[Mart93] Martinez, T. M.: Competitive Hebbian Learning Rule Forms Perfectly Topology Preserving Maps, In ICANN ’93: International Conference on Neural Networks, Springer, Amsterdam, S. 427-434
[Masc94] Martinez, T. M.; Schulten, K. S.: A “Neural-Gas” Network Learns Topologies; In: Kohonen, T.; Mäkisara, K.; Simula, O.; Kangas, J.; Hrsg., Artificial Neural Net-works, S. 397-402, North Holland, Amsterdam
[NiDH94] Nieschlag, R; Dichtel E.; Hörschgen H.: Marketing; 17. Auf-lage, Duncker & Humboldt, Berlin, 1994
[NoHa78] Nollau, V.; Hahnewald-Busch, A.: An Approximation Proce-dure for Stochastic Dynamic Progamming in Count-able State Spaces; Math. Operationsforschung und Statistik; Ser. Optimization 9, 1978, S. 109-117
[Pute94] Puterman, Martin L.: Markov Decision Problems, Wiley, New York, 1994
33
[Remm94] Remmers, J.: Yield Management im Tourismus, In: Schertler Hrsg. Tourismus als Informationsgeschäft, Ueberreu-ter, Wien, 1994
[RiMS90] Ritter, H.; Martinetz, T.; Schulten, K.: Neuronale Netze: Eine Einführung in die Neuroinformatik selbst-organisierender Netzwerke; Addison-Wesley, 1990
[Schw95] Schwefel, Hans-Paul: Evolution and Optimum Seeking, Wiley-Interscience, New York, 1995
[Simo92] Simon, H.: Preismanagement, 2. Auflage, Gabler, Wiesbaden, 1992
[SmLD92] Smith, B.; Leimkuhler, J; Darrow, R.: Yield Management at American Airlines; Interfaces 1, 1992, S. 8-31
[SuBa99] Sutton, Richard S.; Barto, Andrew G.: Reinforcement Learn-ing: An Introduction, MIT Press, Cambridge (MA), 1999
[TaRy96] Talluri, K.; Ryzin, G: An Analysis of Bid-Price Controls for Network Revenue Management; Working Paper of the Management Science and Operations Management Division; Columbia Business School, Columbia Uni-versity New York, 1996
[Voge89] Vogel, H.: Yield Management-Optimale Kapazität für jedes Marktsegment zum richtigen Preis, Fremdenverkehrs-wirtschaft International 22, 1998
[Watk89] Watkins, C. J.: Learning from Delayed Rewards, Dissertation, Cambridge (UK), 1989
[WeBo92] Wetherford, L.; Bodily S.: A Taxonomy and Research Over-view of Perishable-Asset Revenue Management: Yield Management, Overbooking and Pricing, Operations Research 40, 1992, S. 831-844
[Wend91] Wendt, O.: Optimal Pricing of Airfreight Capacity; In Behrendt, R.; Bertsch, L. H.; Hrsg., Advanced Soft-ware Technology in Air Transport 91, AIT-Verlag, Halbergmoos, 1991
34
