Lexikografische Bandits: Regret-Minimierung trifft Arm-Identifikation

In einem neuen Beitrag auf arXiv wird ein bedeutender Fortschritt im Bereich der mehrdimensionalen Entscheidungsfindung vorgestellt. Die Autoren untersuchen lexikografische Bandits, ein Modell, bei dem mehrere Belohnungsziele in einer festen Prioritätenreihenfolge optimiert werden. Während frühere Arbeiten sich hauptsächlich auf die Minimierung von Regret konzentrierten, schließen die Forscher hier die Lücke zwischen Regret‑Minimierung und der Identifikation des besten Arms.

Der erste vorgeschlagene Algorithmus arbeitet mit einer schrittweisen Eliminierung von suboptimalen Armen. Dabei wird jede Prioritätsstufe einzeln behandelt – von der höchsten bis zur niedrigsten. Durch diese schichtweise Vorgehensweise erreicht der Algorithmus eine Stichprobenkomplexität und Regret‑Grenzen, die mit den besten bekannten Ergebnissen für ein einzelnes Ziel vergleichbar sind.

Der zweite Ansatz nutzt hingegen die Belohnungsinformationen aller Ziele in jedem Zug. Durch die gleichzeitige Berücksichtigung der Kreuzabhängigkeiten zwischen den Zielen kann er die Leistung deutlich steigern. Interessanterweise übertrifft dieser Algorithmus sogar die bekannte untere Schranke für das klassische, ein‑Ziel‑Bandit‑Problem, was die Vorteile des Informationsaustauschs zwischen den Zielen unterstreicht.

Experimentelle Tests bestätigen die theoretischen Erkenntnisse: Beide Algorithmen liefern in simulierten Szenarien eine deutlich bessere Leistung als etablierte Baselines. Damit wird gezeigt, dass die Kombination von Regret‑Minimierung und Arm‑Identifikation in lexikografischen Bandits nicht nur möglich, sondern auch praktisch vorteilhaft ist.