Effiziente Simple-Regret-Algorithmen für stochastische kontextuelle Banditen

Ein neuer Beitrag auf arXiv präsentiert die ersten effizienten Algorithmen, die im Bereich der stochastischen kontextuellen Banditen das Simple‑Regret‑Kriterium adressieren. Dabei liegt der Fokus auf logistischen Banditen, für die bislang keine solchen Resultate bekannt waren.

Der vorgeschlagene Ansatz kombiniert Techniken aus kontextuellen linearen Banditen mit selbstkonsordanten Analysen und erzielt einen Simple‑Regret‑Wert von Õ(d/√T). Besonders bemerkenswert ist, dass der führende Term dieser Schranke nicht von der konstanten κ = O(exp(S))

Für endliche Aktionsmengen ist der Algorithmus vollständig handhabbar. Zusätzlich wird eine neue Variante des Thompson‑Sampling-Ansatzes vorgestellt, die erstmals eine Simple‑Regret‑Garantie für randomisierte Algorithmen in stochastischen kontextuellen linearen Banditen liefert: Õ(d³⁄²/√T). Diese Methode lässt sich elegant auf das logistische Setting übertragen und erzielt dieselbe Schranke ohne Abhängigkeit von κ.