Inhaltszusammenfassung:
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.
Abstract:
Sequential decision-making represents a class of online learning problems where a learning agent interacts with an environment consecutively to optimize a long-term metric. At each round of decision-making, the agent takes action and receives feedback from the environment. The agent's strategy is to improve the decision-making based on observed feedback. The decision-making problem is challenging as often partial feedback information is available to the agent during the learning process; at each round, the agent receives the feedback related to the action taken and does not observe the outcome of any other untaken actions. Besides, the agent has to learn in a random environment without prior knowledge about the statistical characteristics of the random variables involved in the problem. The problem becomes more complicated by considering various real-world constraints during the decision-making process. Therefore, appropriate decision-making strategies are required to address the challenges and solve the problem efficiently.
This thesis contributes to the field of online decision-making under uncertainty by formulating novel decision-making problems and developing several algorithms. The proposed methods build upon the multi-armed bandit framework that portrays the exploration-exploitation dilemma, where the agent decides between exploring options to acquire new knowledge and selecting an option by exploiting the existing knowledge. More specifically, this thesis introduces several multi-armed bandit frameworks with various feedback models and objectives, and uses the developed frameworks to model and solve real-world problems.
Chapter 3 formulates a budget-limited bandit problem in a dynamic environment where pulling each arm is costly. The developed bandit framework is used to model the computational offloading problem of users' mobile devices to edge servers. To this end, the required time and energy for data transmission and processing are analyzed. We propose an adaptive policy to solve the formulated problem and prove a regret bound on its performance. We use the algorithm to solve a computation offloading problem through simulation and compare its performance with several bandit-based algorithms.
In Chapter 4, we introduce a contextual bandit problem with costly observations, where features' states can be observed in exchange for a known and fixed cost. We propose two algorithms for simultaneous and sequential state observations. We prove that the algorithms achieve sublinear regret bounds concerning time. In addition, we evaluate the proposed algorithms in a medical context by applying them to recommend tests and treatments to patients with breast cancer. The results show that our algorithms outperform several context-aware and context-agnostic algorithms.
Chapter 5 extends the contextual bandit model proposed in the previous chapter by considering random costs of state observations as well as non-stationary reward and cost generating processes. We propose an algorithm that learns the optimal observations and actions simultaneously. We analyze the proposed algorithm theoretically by proving a sublinear regret bound concerning time. The solution is validated on the real-world problem of ranking nursery school applications and compared with conventional benchmarks.
In Chapter 6, we develop a combinatorial semi-bandit framework with causally related rewards, where we model the causal relations by a directed graph in a stationary structural equation model. We propose a policy that determines the causal relations by learning the network's topology and exploits this knowledge to optimize decision-making. We prove that the proposed algorithm achieves a sublinear regret bound in time. Numerical experiments using synthetic data demonstrate the superiority of our proposed algorithm over several combinatorial bandit algorithms. In addition, we employ the proposed framework to analyze the development of Covid-19 in Italy.
Finally, Chapter 7 builds upon the framework developed in the previous chapter and extends the model by considering non-stationary environments with delayed feedback, while structural dependencies still exist amongst the arms' reward distributions. We develop a policy that learns the structural dependencies from delayed feedback and utilizes that to optimize the decision-making while adapting to environmental changes. We analyze the algorithm theoretically by proving a regret bound. We evaluate our method using synthetic and real-world datasets and apply our algorithm to detect the regions in Italy that contribute the most to the spread of Covid-19.
Uncertainty
Print-on-Demand