Präferenz-basierte Monte-Carlo Baumsuche

• Antragsteller: Professor Dr. Johannes Fürnkranz
• Fachliche Zuordnung: Bild- und Sprachverarbeitung, Computergraphik und Visualisierung, Human Computer Interaction, Ubiquitous und Wearable Computing
• Förderung: Förderung von 2015 bis 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 280805726

Multi-armed Bandits sind ein klassisches Szenario im maschinellen Lernen, bei dem der Lerner herausfinden muß, welche aus einer Menge von Aktionen den höchsten Langzeit-Reward liefert. In jüngerer Zeit wurde dieses Szenario in zwei Richtungen erweitert: Auf der einen Seite ersetzen präferenz-basierte, sogenannte Dueling Bandits die Annahme eines quantitativen, numerischen Feedback-Signals durch die schwächere Annahme eines qualitativen, vergleichenden Feedbacks. Auf der anderen Seite erlaubt Monte-Carlo Baumsuche (MCTS), den einfachen Fall eines Entscheidungsproblem mit nur einem Zustand auf den realistischeren Fall eines sequenziellen Entscheidungsproblems zu erweitern.In diesem Projekt werden wir präferenz-basierte Monte-Carlo Baumsuche untersuchen, was sowohl als eine Erweiterung von MCTS auf Probleme mit qualitativem Feedback als auch als eine Erweiterung von Dueling Bandits auf sequenzielle Entscheidungsprobleme gesehen werden kann. Aufbauend auf neuen Methoden des Präferenz-Lernens ist die Grundidee, MCTS-Verfahren auf qualitative Policy-Modelle wie z.B. Ranking-Verfahren aufzusetzen. Während eine erste Anpassung von MCTS an ein präferenz-basiertes Setting ohne größeren Aufwand möglich zu sein scheint, müssen eine Menge von praktischen Problemen in diesem Szenario gelöst werden. Insbesondere würde eine naive Implementierung, die einfach an jedem Entscheidungsknoten jedes Roll-Out zur numerischen Bewertung einer einzelnen Aktion durch einen Vergleich zweier Aktionen ersetzt, zu einem exponentiellen Anstieg in der Anzahl der generierten Trajektorien führen. Unser Hauptziel ist daher, diese Probleme zu lösen und theoretischeund methodologische Grundlagen eines präferenz-basierten Ansatzes für MCTS zu legen.Um die entwickelten Techniken in realistischen Anwendungen zu testen, werden die theoretischen Arbeiten mit zwei Fallstudien begleitet: General Game Playing, wo MCTS den Stand der Forschung darstellt, aber eine präferenz-basierte Erweiterung nützlich zu sein scheint, und Empfehlungssysteme, die wir als sequenzielle Entscheidungsprobleme betrachten, bei denen exaktes numerisches Feedback oft nicht verfügbar ist.

• DFG-Verfahren: Sachbeihilfen