Bester Banditenalgorithmus?

Der bekannteste Algorithmus für Banditen ist der Upper Confidence Bound (UCB), der diese Klasse von Algorithmen bekannt gemacht hat. Seitdem gehe ich davon aus, dass es jetzt bessere Algorithmen gibt. Was ist der derzeit beste Algorithmus (in Bezug auf empirische Leistung oder theoretische Grenzen)? Ist dieser Algorithmus in gewissem Sinne optimal?

Eine Veröffentlichung von NIPS 2011 ("Eine empirische Bewertung der Thompson-Probenahme") zeigt in Experimenten, dass die Thompson-Probenahme die UCB schlägt. UCB basiert auf der Auswahl des Hebels, der unter optimistischen Annahmen die höchste Belohnung verspricht (dh die Varianz Ihrer Schätzung der erwarteten Belohnung ist hoch, daher ziehen Sie Hebel, die Sie nicht so gut kennen). Stattdessen ist Thompson Sampling vollständig bayesianisch: Es generiert eine Banditenkonfiguration (dh einen Vektor der erwarteten Belohnungen) aus einer posterioren Verteilung und verhält sich dann so, als ob dies die wahre Konfiguration wäre (dh es zieht den Hebel mit der höchsten erwarteten Belohnung).

Die Bayes - Steuerungsregel ( „ A Mindest Relative Entropy Prinzip für das Lernen und Handeln “, JAIR), eine Verallgemeinerung von Thompson Sampling leitet Thompson Sampling von informationstheoretischen Prinzipien und Kausalität. Insbesondere wird gezeigt, dass die Bayes'sche Kontrollregel die optimale Strategie ist, wenn Sie die KL zwischen Ihrer Strategie und der (unbekannten) optimalen Strategie minimieren möchten und kausale Einschränkungen berücksichtigen. Der Grund, warum dies wichtig ist, ist, dass dies als Erweiterung der Bayes'schen Folgerung auf Aktionen angesehen werden kann: Die Bayes'sche Folgerung kann als die optimale Vorhersagestrategie gezeigt werden, wenn Ihr Leistungskriterium die KL zwischen Ihrem Schätzer und der (unbekannten) wahren Verteilung ist.

UCB ist in der Tat im stochastischen Fall nahezu optimal (bis zu einem log T-Faktor für ein T-Runden-Spiel) und bis zu einer Lücke in der Pinsker-Ungleichung in einem problemabhängigeren Sinne. Die jüngste Veröffentlichung von Audibert und Bubeck beseitigt diese logarithmische Abhängigkeit im schlimmsten Fall, hat jedoch im günstigen Fall eine schlechtere Schranke, wenn verschiedene Waffen gut getrennte Belohnungen haben.

Im Allgemeinen ist UCB ein Kandidat aus einer größeren Familie von Algorithmen. Zu jedem Zeitpunkt im Spiel können Sie alle Arme anzeigen, die nicht "disqualifiziert" sind, dh deren obere Vertrauensgrenze nicht kleiner ist als die untere Vertrauensgrenze eines Arms. Die Auswahl auf der Grundlage einer Verteilung solcher qualifizierter Waffen stellt eine gültige Strategie dar und wird bis hin zu Konstanten ähnlich bedauert.

Empirisch glaube ich nicht, dass es eine signifikante Bewertung vieler verschiedener Strategien gegeben hat, aber ich denke, dass UCB oft recht gut ist.

Die meisten neueren Forschungen haben sich darauf konzentriert, Banditenprobleme über die einfache K-bewaffnete Situation hinaus mit stochastischen Belohnungen auf sehr große (oder unendliche) Aktionsräume mit oder ohne Nebeninformationen und unter stochastischem oder kontroversem Feedback auszudehnen. Es wurde auch in Szenarien gearbeitet, in denen sich die Leistungskriterien unterscheiden (z. B. nur die Ermittlung des besten Arms).

Der aktuelle Stand der Technik lässt sich wie folgt zusammenfassen:

• $R_T = O(\frac{K \log T}{\Delta})$
• $\tilde{R}_T = O(\sqrt{T K \log K})$
• Kontextuell: Es ist kompliziert

$T$$K$$\Delta$