Neuer Algorithmus erzielt polynomialen Regret bei adversarialen linearen Bandits

Ein neuer Ansatz für lineare Kontextbandits mit adversarialen Verlusten und stochastischen Aktionsmengen hat die Forschung vor einen großen Schritt gebracht. Der Algorithmus reduziert das Problem auf misspezifizierungsresistente adversariale lineare Bandits mit festen Aktionsmengen und benötigt weder die Kontextverteilung noch einen Kontext-Simulator.

Er erreicht einen Regret‑Wert von O~(min{d²√T, √(d³T log K)}) und arbeitet in polynomieller Zeit poly(d, C, T). Dabei steht d für die Merkmalsdimension, C für die maximale Anzahl linearer Nebenbedingungen pro Runde, K für die maximale Anzahl möglicher Aktionen und T für die Gesamtzahl der Spielzüge.

Damit wird die offene Frage von Liu et al. (2023) beantwortet: Es ist möglich, einen poly(d) √T-Regret in polynomieller Zeit zu erreichen, ohne dass die Regret‑Grenze von der Anzahl der Aktionen abhängt.

Besonders für kombinatorische Bandits, bei denen die Aktionsmengen durch eine polynomielle Anzahl linearer Einschränkungen beschrieben werden, ist dieser Algorithmus der erste, der poly(d) √T-Regret in polynomieller Zeit erzielt. Bisher konnten keine anderen Verfahren sogar ein o(T)-Regret in polynomieller Zeit erreichen.

Falls ein Simulator zur Verfügung steht, kann der Regret‑Wert weiter verbessert werden auf O~(d √L*), wobei L* die kumulative Verlustsumme der besten Politik darstellt.