Monte Carlo tree search for estimating star discrepancies

Abstract

Aufgrund ihres Vorkommens in der Koksma-Hlawka-Ungleichung ist die Stern-Diskrepanz einer Punktfolge eine kritische Größe bei der Quasi-Monte-Carlo-Integration von Funktionen mit hochdimensionalen Definitionsbereichen. Die Berechnung der Stern-Diskrepanz ist NP-hart, aber es gibt mehrere Algorithmen zur Approximation. Die meisten dieser Algorithmen beruhen auf maschinellem Lernen wie genetischen Algorithmen und Optimierungsalgorithmen wie Threshold Accepting. Letzterer stellt den derzeitigen State-of-the-art dar. Das Ziel dieser Arbeit ist es, einen Monte-Carlo Tree Search (MCTS) Algorithmus zu verwenden, um die Stern-Diskrepanz zu approximieren. MCTS konstruiert mittels einer Heuristik iterativ einen Baum und zeigt in vielen Anwendungen mit hohen Verzweigungsfaktoren gute Ergebnisse. Da die Approximation der Stern-Diskrepanz vor allem bei hochdimensionalen Definitionsbereichen relevant ist, ist dies eine vielversprechende Eigenschaft. Die allgemeine Formulierung des MCTS-Algorithmus lässt viel Flexibilität fürdie konkrete Umsetzung durch die Wahl der Zustände, die an den Knotendes Baumes dargestellt werden, und einige Zugänge für solche Zuständewerden formuliert, implementiert und verglichen. Aufgrund des Umfangs der Arbeit bleiben viele weitere mögliche Verbesserungen unerforscht. Der MCTS-Algorithmus schneidet im Vergleich zu vielen bestehenden Algorithmen gut ab, kann sich aber nicht mit dem Threshold Accepting Algorithmus messen. Bei einer hochdimensionalen Punktfolge gelingt es dem Algorithmus jedoch, bessere Werte zu berechnen als Threshold Accepting, was aufein Potenzial des MCTS-Algorithmus in der weiteren Entwicklung hinweist.

Due to its occurrence in the Koksma-Hlawka inequality, the star-discrepancy of a point sequence is a critical quantity in quasi-Monte-Carlo integrationof functions with high-dimensional domains. The calculation of the star-discrepancy is NP-hard, but several approximation algorithms exist. Most of them rely on machine learning such as genetic algorithms and optimisation algorithms like threshold accepting, the latter comprising the state-of-the-art method. The aim of this thesis is to use a Monte-Carlo Tree Search (MCTS) algorithm to approximate the star-discrepancy. MCTS iteratively constructs a tree using a heuristic and performs well in many applications with high branching factors. Since the approximation of the star-discrepancyis relevant primarily in the case of high-dimensional domains, this is a sought-after property. The general formulation of the MCTS algorithm leaves much flexibility for concrete implementation by choice of the states represented at the nodes of the tree and a variety of such states are formulated, implemented and compared. Due to the scope of the thesis many further possible improvements remain unexplored. The MCTS algorithm compares favourably to many existing algorithms but fails to compete in a meaningful fashion with the threshold accepting algorithm. However, on one high-dimensional point-sequence the algorithm manages to compute better values than the threshold accepting algorithm, indicating much potential for the MCTS algorithm in further adaptations.