Optymalny algorytm rozwiązywania problemów n-uzbrojonych bandytów?

13

Czytałem o wielu algorytmów rozwiązywania problemów n uzbrojonych bandyckie jak -greedy, Softmax i UCB1, ale mam pewne problemy z sortowaniem przez co jest najlepsze podejście do minimalizacji żal.ϵ

Czy istnieje znany optymalny algorytm rozwiązywania problemu n-uzbrojonego bandyty? Czy istnieje wybór algorytmu, który wydaje się działać najlepiej w praktyce?

machine-learning reinforcement-learning multiarmed-bandit JS01
źródło
Prawdopodobnie nie ma uznanego optymalnego rozwiązania, ponieważ inaczej powiedzieliby to strona Wikipedii i nie byłoby eksperymentalnej strony Sourceforge
Henry
Czy nie powinno to być w Theoretical Computer Science SE?
1
@mbq, ponieważ uczenie się przez wzmocnienie jest dziedziną uczenia maszynowego, nie sądzę;)
steffen
@steffen Pewnie, nazwa wydawała się „tcsy”.
@mbq Nie rozumiem. Co znaczy „tscy”?
steffen

Odpowiedzi:

9

Oto dwa artykuły z badań, które niedawno znalazłem. Jeszcze ich nie czytałem, ale streszczenia brzmią obiecująco.

Joann`s Vermorel i Mehryar Mohri: Algorytmy wielorękiego bandyty i ocena empiryczna (2005)

Z streszczenia:

Problemem wielorękiego bandyty dla hazardzisty jest decyzja, które ramię automatu K-automatu należy pociągnąć, aby zmaksymalizować całkowitą nagrodę w serii prób. W ten sposób można modelować wiele rzeczywistych problemów związanych z uczeniem się i optymalizacją. W ostatnich dwóch dekadach zaproponowano kilka strategii lub algorytmów jako rozwiązanie tego problemu, ale o ile nam wiadomo, nie ma wspólnej oceny tych algorytmów.

Volodymyr Kuleshov i Doina Precup: Algorytmy dla problemu wielorękiego bandyty (2000) Ze streszczenia:

Po drugie, wydajność większości algorytmów różni się dramatycznie w zależności od parametrów problemu bandyty. Nasze badanie identyfikuje dla każdego algorytmu ustawienia, w których działa on dobrze, oraz ustawienia, w których działa on słabo.

steffen
źródło