Abstract
Sequentielle Entscheidungsfindung ist eine Kategorie von Online-Lernproblemen, bei denen ein Lernagent fortlaufend mit einer Umgebung interagiert, um eine langfristige Metrik zu optimieren. In jeder Entscheidungsrunde ergreift der Agent Aktionen und erhält Rückmeldungen aus der Umwelt. Die Strategie des Agenten besteht darin, die Entscheidungsfindung auf der Basis des beobachteten Feedbacks zu verbessern. Das Entscheidungsfindungsproblem ist eine Herausforderung, da dem Agenten während des Lernprozesses oft nur partielle Feedback-Informationen zur Verfügung stehen; in jeder Runde erhält der Agent das Feedback für die durchgeführte Aktion und beobachtet nicht das Ergebnis anderer nicht durchgeführter Aktionen. Außerdem muss der Agent in einer zufälligen Umgebung lernen, ohne dass er die statistischen Eigenschaften der Zufallsvariablen kennt, die in das Problem involviert sind. Das Problem wird noch komplizierter, wenn während des Entscheidungsfindungsprozesses verschiedene Sachzwänge berücksichtigt werden. Daher sind geeignete Entscheidungsstrategien erforderlich, um die Herausforderungen zu meistern und das Problem effizient zu lösen. Diese Arbeit leistet einen Beitrag zum Gebiet der Online-Entscheidungsfindung unter Unsicherheit, indem sie neuartige Entscheidungsprobleme formuliert und mehrere Algorithmen entwickelt. Die vorgeschlagenen Methoden bauen auf dem mehrarmigen Banditen auf, der das Explorations-Ausbeutungs-Dilemma abbildet, bei dem der Agent zwischen der Erkundung von Optionen, um neues Wissen zu erwerben, und der Auswahl einer Option durch Ausbeutung des vorhandenen Wissens entscheidet. Konkret werden in dieser Arbeit mehrere Multi-Armed-Bandit-Frameworks mit verschiedenen Feedbackmodellen und Zielen vorgestellt und die entwickelten Frameworks zur Modellierung und Lösung realer Probleme eingesetzt. Kapitel 3 formuliert ein budgetbegrenztes Bandit-Problem in einer dynamischen Umgebung, in der das Ziehen jedes Arms kostspielig ist. Der entwickelte Bandit-Rahmen wird verwendet, um das Problem der Verlagerung von Rechenleistung von mobilen Geräten der Benutzer auf Edge-Server zu modellieren. Zu diesem Zweck werden die erforderliche Zeit und Energie für die Datenübertragung und -verarbeitung analysiert. Wir schlagen eine adaptive Strategie vor, um das formulierte Problem zu lösen und beweisen eine Bedauernsgrenze für seine Leistung. Wir verwenden den Algorithmus, um ein Problem der Rechenauslagerung durch Simulation zu lösen und vergleichen seine Leistung mit mehreren Bandit-basierten Algorithmen. In Kapitel 4 führen wir ein kontextuelles Bandit-Problem mit kostspieligen Beobachtungen ein, bei dem die Zustände von Merkmalen im Austausch für einen bekannten und festen Preis beobachtet werden können. Wir schlagen zwei Algorithmen für simultane und sequentielle Zustandsbeobachtungen vor. Wir beweisen, dass die Algorithmen sublineare Bedauernsschranken bezüglich der Zeit erreichen. Darüber hinaus evaluieren wir die vorgeschlagenen Algorithmen in einem medizinischen Kontext, indem wir sie zur Empfehlung von Tests und Behandlungen für Patienten mit Brustkrebs einsetzen. Die Ergebnisse zeigen, dass unsere Algorithmen mehrere kontextabhängige und kontextagnostische Algorithmen übertreffen. Kapitel 5 erweitert das bisherige kontextuelle Bandit-Modell durch die Berücksichtigung zufälliger Kosten von Zustandsbeobachtungen sowie nicht-stationärer Belohnungs- und Kostenerzeugungsprozesse. Wir schlagen einen Algorithmus vor, der die optimalen Beobachtungen und Handlungen gleichzeitig erlernt. Wir analysieren den vorgeschlagenen Algorithmus theoretisch, indem wir eine sublineare Bedauernsgrenze bezüglich der Zeit beweisen. Die Lösung wird anhand des realen Problems der Rangfolge von Kindergartenanwendungen validiert und mit herkömmlichen Benchmarks verglichen. In Kapitel 6 entwickeln wir einen kombinatorischen Semi-Bandit-Rahmen mit kausal verbundenen Belohnungen, in dem wir die kausalen Beziehungen durch einen gerichteten Graphen in einem stationären Strukturgleichungsmodell modellieren. Wir schlagen eine Strategie vor, die die kausalen Beziehungen durch Lernen der Topologie des Netzwerks bestimmt und dieses Wissen zur Optimierung der Entscheidungsfindung nutzt. Wir beweisen, dass der vorgeschlagene Algorithmus eine zeitlich sublineare Regressionsgrenze erreicht. Numerische Experimente mit synthetischen Daten zeigen die Überlegenheit des von uns vorgeschlagenen Algorithmus gegenüber mehreren kombinatorischen Bandit-Algorithmen. Darüber hinaus verwenden wir den vorgeschlagenen Rahmen, um die Entwicklung von Covid-19 in Italien zu analysieren. Schließlich baut Kapitel 7 auf dem im vorigen Kapitel entwickelten Rahmen auf und erweitert das Modell auf nicht-stationäre Umgebungen mit verzögerter Rückkopplung, wobei immer noch strukturelle Abhängigkeiten zwischen den Belohnungsverteilungen der Arme bestehen. Wir entwickeln eine Strategie, die die kausalen Beziehungen aus dem verzögerten Feedback lernt und diese zur Optimierung der Entscheidungsfindung bei gleichzeitiger Anpassung an Umweltveränderungen nutzt. Wir analysieren den Algorithmus theoretisch, indem wir eine Bedauernsgrenze nachweisen. Wir evaluieren unsere Methode anhand synthetischer und realer Datensätze und wenden unseren Algorithmus an, um die Regionen in Italien zu ermitteln, die am meisten zur Verbreitung von Covid-19 beitragen.
Author and committee
dc:creator, dc:contributor.*- Author
-
- Ghoorchian, Saeed
Identifiers
dc:identifier.*- Identifier
- hdl:10900/152080