Algoritma optimal untuk menyelesaikan masalah bandit n-bersenjata?

13

Saya telah membaca tentang sejumlah algoritma untuk memecahkan masalah bandit n-bersenjata seperti -greedy, softmax, dan UCB1, tapi saya mengalami beberapa masalah memilah pendekatan apa yang terbaik untuk meminimalkan penyesalan.ϵ

Apakah ada algoritma optimal yang diketahui untuk memecahkan masalah bandit n-bersenjata? Apakah ada pilihan algoritma yang tampaknya berkinerja terbaik dalam praktik?

machine-learning reinforcement-learning multiarmed-bandit JS01
sumber
Agaknya tidak ada solusi optimal yang diakui, karena kalau tidak, halaman Wikipedia akan mengatakannya dan tidak akan ada halaman Sourceforge
Henry
Bukankah ini seharusnya di Theoretical Computer Science SE?
1
@ MBQ karena pembelajaran penguatan adalah cabang pembelajaran mesin, saya tidak berpikir begitu;)
steffen
@steffen Tentu, nama itu tampak "tcsy".
@ MBB Saya tidak mengerti. Apa artinya "tscy"?
steffen

Jawaban:

9

Berikut adalah dua makalah survei yang saya temukan baru-baru ini. Saya belum membacanya, tetapi abstraknya terdengar menjanjikan.

Joann`s Vermorel dan Mehryar Mohri: Algoritma Bandit Multi-Armed dan Evaluasi Empiris (2005)

Dari abstrak:

Masalah bandit multi-bersenjata bagi seorang penjudi adalah memutuskan lengan mana dari mesin K-slot yang akan ditarik untuk memaksimalkan total hadiahnya dalam serangkaian uji coba. Banyak masalah pembelajaran dan pengoptimalan di dunia nyata dapat dimodelkan dengan cara ini. Beberapa strategi atau algoritma telah diusulkan sebagai solusi untuk masalah ini dalam dua dekade terakhir, tetapi, setahu kami, belum ada evaluasi umum untuk algoritma ini.

Volodymyr Kuleshov dan Doina Precup: Algoritma untuk masalah bandit multi-bersenjata (2000) Dari abstrak:

Kedua, kinerja sebagian besar algoritma bervariasi secara dramatis dengan parameter masalah bandit. Studi kami mengidentifikasi untuk setiap algoritma pengaturan di mana kinerjanya baik, dan pengaturan di mana kinerjanya buruk.

steffen
sumber