Optimaler Algorithmus zur Lösung von n-armigen Banditenproblemen?

13

Ich habe über eine Reihe von Algorithmen zur Lösung von Problemen mit n-bewaffneten Banditen wie -greedy, Softmax und UCB1 gelesen, habe jedoch einige Probleme, herauszufinden, welcher Ansatz zur Minimierung von Bedauern am besten geeignet ist.ϵ

Gibt es einen bekannten optimalen Algorithmus zur Lösung des n-bewaffneten Banditenproblems? Gibt es eine Auswahl an Algorithmen, die in der Praxis am besten zu funktionieren scheinen?

machine-learning reinforcement-learning multiarmed-bandit JS01
quelle
Vermutlich gibt es keine anerkannte optimale Lösung, wie es die Wikipedia-Seite sonst sagen würde, und es gäbe keine experimentelle Sourceforge-Seite
Henry
Sollte das nicht in der Theoretischen Informatik SE sein?
1
@mbq da verstärkendes lernen ein zweig des maschinellen lernens ist, glaube ich nicht;)
steffen
@steffen Klar, der Name schien "tcsy".
@mbq Ich verstehe es nicht. Was bedeutet "tscy"?
steffen

Antworten:

9

Hier sind zwei Umfragepapiere, die ich kürzlich gefunden habe. Ich habe sie noch nicht gelesen, aber die Abstracts klingen vielversprechend.

Joanns Vermorel und Mehryar Mohri: Mehrarmige Banditenalgorithmen und empirische Bewertung (2005)

Aus dem Abstract:

Das mehrarmige Banditenproblem für einen Spieler besteht darin, zu entscheiden, welchen Arm eines K-Slot-Automaten er ziehen soll, um seine Gesamtbelohnung in einer Reihe von Versuchen zu maximieren. Viele reale Lern- und Optimierungsprobleme können auf diese Weise modelliert werden. In den letzten zwei Jahrzehnten wurden verschiedene Strategien oder Algorithmen als Lösung für dieses Problem vorgeschlagen. Nach unserem Kenntnisstand gab es jedoch keine gemeinsame Bewertung dieser Algorithmen.

Volodymyr Kuleshov und Doina Precup: Algorithmen für das mehrarmige Banditenproblem (2000) Aus dem Abstract:

Zweitens variiert die Leistung der meisten Algorithmen dramatisch mit den Parametern des Banditenproblems. Unsere Studie identifiziert für jeden Algorithmus die Einstellungen, bei denen die Leistung gut ist, und die Einstellungen, bei denen die Leistung schlecht ist.

steffen
quelle