Simulation-Based Optimization with Non-Parametric State Space Approximation using Reinforcement Learning

Abstract

Entscheidungsprozesse spielen in vielen Anwendungen eine große Rolle. Diese lassen sich aber wegen der stochastischen Natur und der vorhandenen Komplexität teilweise schwer analytisch lösen. Simulationsbasierte Optimierung zusammen mit Methoden des maschinellen Lernens stellen eine Lösungsmöglichkeit dar, ohne auf eine explizite Formulierung angewiesen zu sein. In dem gewählten Ansatz werden die zu optimierenden Probleme als Markov Decision Process modelliert und durch Reinforcement Learning gelöst. Bei hinreichend komplexen Problemen muss der Zustandsraum aber durch eine geeignete Methode approximiert werden. Aktuelle Ansätze basierend auf künstlichen neuronalen Netzwerken ermöglichen leistungsfähige Algorithmen, die allerdings oftmals von Stabilitätsproblemen begleitet sind. Zusätzlich korreliert die Leistungsfähigkeit sehr stark mit einer richtigen Wahl der Hyperparameter, welche problemabhängig sind. Dadurch wird ein Einsatz als Optimierungsmethode für noch unbekannte Probleme erschwert. Diese Arbeit adressiert die Notwendigkeit von zuverlässigen Optimierungsmethoden in diesem Feld. Es werden algorithmische Ansätze entwickelt, die auf Ideen und Konzepte der nicht-parametrischen Methoden beruhen. Während parametrische Modelle meistens eine feste Annahme über die zugrundeliegende Datenverteilung treffen, verzichten nicht-parametrische Methoden auf solche Vorgaben. Dadurch können sie sich flexibel an die tatsächliche Struktur der Daten anpassen. Ereignisdiskrete Simulationmodelle besitzen oft einen Zustandsraum, dessen Struktur sehr ungleichförmig ausgeprägt ist. Die tatsächliche Größe und Komplexität ist a priori unklar. Es stellt sich heraus, dass diese Modelle vom gewählten Ansatz stark profitieren können und auch die notwendige Menge an Daten ermöglichen, um optimale Lösungsstrategien zu extrahieren. Die betrachteten Forschungsfragen zielen auf die Anwendbarkeit dieser nicht-parametrischen Verfahren als Lösungsmethode für die zugrundeliegenden Markov Decision Processes.Die Anwendbarkeit wird anhand mehrerer stochastisch anspruchsvollen Case-Studies demonstriert, welche in Logistik, Medizin und Operational Research relevant sind. Die mögliche Leistungsfähigkeit der Algorithmen, sowie deren methodischen Grenzen werden mit Simulationen quantifiziert. Die Methoden sind vor allem in Kombination mit einer guten Modellierung der Problemstellung sehr leistungsfähig. Die Qualität der Lösungsstrategien erreicht in fast allen der 10 diversen Problemstellungen ein hohes Niveau und übertrifft oftmals Deep Reinforcement Learning (DQN). Die extrahierten Entscheidungen bleiben dabei nachvollziehbar und sind auch für risiko-sensible Problemstellungen geeignet, wo künstliche neuronale Netze problematische Intransparenz aufweisen. Ebenfalls ist eine Integration ins Framework der Policy Gradient Methoden möglich, wo die vorgestellte State-Space Approximation als stabile Baseline eingesetzt werden kann. Dies ermöglicht sehr leistungsfähige Algorithmen aus Basis der Actor-Critic Architektur.

Decision processes play a major role in a wide range of applications. Due to their stochastic nature and the existing complexity, these processes are sometimes difficult to solve analytically. Simulation-based optimization together with machine learning methods represent a possible solution without having to rely on an explicit formulation. In the selected approach, the optimization problems are modeled as Markov decision processes and solved using reinforcement learning. For large and complex problems, the state space has to be approximated by a suitable method. Current approaches based on artificial neural networks enable powerful algorithms, but they often are associated with stability issues. In addition, the performance is highly correlated with the correct choice of hyperparameters, which are problem-dependent. This makes it difficult to use reinforcement learning as an optimization method for yet unknown problems. This thesis addresses the need for reliable optimization methods in this field. It develops algorithmic approaches based on ideas and concepts from non-parametric methods. While parametric models often make a specific assumption about the underlying data distribution, non-parametric methods do not. This allows them to adapt flexibly to the actual structure of the data. Discrete-event simulation models can have a state space whose structure is very irregular. The actual size and complexity is a priori unclear. It turns out that these models can benefit greatly from the chosen approach and also provide the necessary amount of data to extract optimal solution strategies. The research questions address the applicability of these non-parametric methods as a solution method for the underlying Markov decision processes.The applicability is demonstrated on several stochastically challenging case studies that are highly relevant in logistics, medicine and operational research. The possible performance of the algorithms, as well as their methodological limitations, are quantified with simulations. The methods prove to be very powerful, when combined with a good modeling of the problem. The quality of the solution strategies reaches a high level in almost all of the 10 very diverse problem definitions and often outperforms Deep Reinforcement Learning (DQN). The extracted decisions remain comprehensible and are also suitable for risk-sensitive problems where artificial neural networks show problematic intransparency. Furthermore, an integration into the framework of policy gradient methods is possible, where the presented state-space approximation can be used as a stable baseline. This enables very powerful algorithms based on the Actor-Critic architecture.