Neues Reduktionsverfahren verbessert Bandit-Algorithmen bei adversarialen Kontexten

In einer kürzlich veröffentlichten Arbeit auf arXiv wird ein innovatives Verfahren vorgestellt, das die Leistung von kontextuellen Bandit-Algorithmen mit Kostenbeschränkungen in Umgebungen mit gegnerisch gewählten Kontexten deutlich steigert. Das Ziel ist es, gleichzeitig die Regret‑Kosten und die kumulative Verletzung der Budgetbeschränkung zu minimieren.

Die Autoren gehen von einer Realisierbarkeitsannahme aus: Sobald ein Kontext beobachtet wird, werden die Belohnungen und Kosten für jede Aktion aus festen, aber unbekannten Verteilungen gezogen, deren Erwartungswerte in bekannten Funktionsklassen liegen. Im fortlaufenden Setting arbeitet der Algorithmus über die gesamte Zeitspanne hinweg, auch nachdem das Budget erschöpft ist.

Aufbauend auf dem SquareCB-Framework von Foster et al. (2018) wird ein einfaches, modulare Verfahren entwickelt, das Online‑Regressionsorakel nutzt, um das eingeschränkte Problem in ein unbeschränktes kontextuelles Bandit‑Problem mit adaptiv definierten Surrogatbelohnungen zu überführen. Im Gegensatz zu den meisten bisherigen Arbeiten, die sich auf stochastische Kontexte konzentrieren, liefert diese Reduktion verbesserte Garantien für das allgemeinere adversariale Kontextsetting und bietet gleichzeitig eine kompakte und transparente Analyse.