Neue Strategien für Abstraktionspolitiken verbessern Monte-Carlo-Bäume
Monte‑Carlo‑Tree‑Search (MCTS) ist ein leistungsstarkes Verfahren, doch seine Stichprobeneffizienz lässt zu wünschen übrig. Um dieses Problem zu mildern, bauen Forscher parallel zu MCTS Zustands‑ und Aktionsabstraktionen auf, sodass Informationen zwischen Knoten derselben Ebene ausgetauscht werden können.
Der klassische Einsatz von Abstraktionen besteht darin, den Upper Confidence Bound (UCB) eines abstrakten Knotens zu verbessern, indem Besuche und Rückgaben zusammengefasst werden. Dabei wird jedoch übersehen, dass mehrere Aktionen, die denselben Elternknoten haben, im selben abstrakten Knoten landen können. In diesem Fall erhalten alle diese Aktionen denselben UCB‑Wert, was ein Tiebreaking erfordert.
In modernen Abstraktionsalgorithmen wie dem „pruned On the Go Abstractions“ (pruned OGA) wurde dieses Problem bislang nicht erkannt, und ein zufälliges Tiebreaking wurde implizit gewählt. Die vorliegende Arbeit schlägt mehrere alternative intra‑Abstraktionspolitiken vor und bewertet sie empirisch. In den meisten getesteten Umgebungen und Parametern übertreffen die neuen Strategien die zufällige Baseline deutlich.