Neues Modell für Online-Algorithmen mit unzuverlässiger Anleitung

Ein neues Forschungsmodell, das Online-Algorithmen mit unzuverlässiger Anleitung (OAG) genannt wird, trennt die Vorhersage- und Algorithmuskomponenten vollständig voneinander. Dadurch entsteht ein klar definiertes Analyse-Framework, das ausschließlich auf dem jeweiligen Problem basiert.

Im Rahmen von Anfrage-Antwort-Spielen erhält ein OAG-Algorithmus bei jeder eingehenden Anfrage einen Leitfaden aus dem Antwortraum des Problems. Idealerweise ist dieser Leitfaden die optimale Antwort, doch mit einer Wahrscheinlichkeit von β kann er absichtlich verfälscht werden. Das Ziel ist es, Algorithmen zu entwickeln, die sowohl bei β = 0 (Konsistenz) als auch bei β = 1 (Robustheit) gute Wettbewerbsquoten erzielen. Die Idee der Glattheit, die in früheren Arbeiten einen speziellen Verlustfunktion erforderte, entsteht nun automatisch, wenn β von 0 auf 1 wechselt.

Ein zentraler Beitrag ist der Drop-or-Trust-Blindly (DTB)-Compiler, der jeden reinen Online-Algorithmus in einen lernunterstützten Algorithmus im OAG-Modell überführt. Der resultierende Algorithmus folgt entweder blind dem eingehenden Leitfaden oder ignoriert ihn vollständig und verhält sich wie der Ausgangsalgorithmus. Die Entscheidung basiert auf dem Ergebnis eines (biasierten) Münzwurfs. Die Autoren beweisen rigoros, dass dieser Ansatz die gewünschten Eigenschaften von Konsistenz und Robustheit gewährleistet.