Bandit multi-bersenjata untuk distribusi hadiah umum

11

Saya sedang mengerjakan masalah bandit multi-bersenjata di mana kami tidak memiliki informasi tentang distribusi hadiah.

Saya telah menemukan banyak makalah yang menjamin batas penyesalan untuk distribusi dengan batas yang diketahui, dan untuk distribusi umum dengan dukungan pada [0,1].

Saya ingin mencari tahu apakah ada cara untuk bekerja dengan baik di lingkungan di mana distribusi hadiah tidak memiliki jaminan tentang dukungannya. Saya mencoba menghitung batas toleransi nonparametrik dan menggunakan angka itu untuk menskalakan distribusi hadiah sehingga saya dapat menggunakan algoritma 2 yang ditentukan pada makalah ini ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf ). Adakah yang mengira pendekatan ini akan berhasil?

Jika tidak, adakah yang bisa mengarahkan saya ke tempat yang tepat?

Terima kasih banyak!

references multiarmed-bandit tamu
sumber

Jawaban:

6

Penelitian tentang algoritma MAB terkait erat dengan jaminan kinerja teoritis. Memang, kebangkitan minat ke dalam algoritma ini (ingat pengambilan sampel Thompson diusulkan pada 30-an) hanya benar-benar terjadi sejak kertas Auer 2002 membuktikan menyesali batas untuk berbagai UCB dan -greedy algoritma. Dengan demikian, ada sedikit minat pada masalah di mana distribusi hadiah tidak memiliki batas yang diketahui karena hampir tidak ada yang dapat dikatakan secara teoritis.ϵO(log⁡(T))ϵ

Bahkan algoritma pengambilan sampel Thompson sederhana yang Anda sebutkan membutuhkan hadiah yang didistribusikan Bernoulli, dan bahkan itu membutuhkan waktu 80 tahun untuk membuktikan ikatan penyesalan yang logaritmik!

Namun, dalam praktiknya, dalam kasus di mana Anda tidak mengetahui distribusi hadiah secara pasti, Anda dapat mengaturnya menjadi dengan membaginya dengan angka , dan jika Anda mengamati hadiah di atas cukup gandakan nilainya, . Tidak ada jaminan penyesalan menggunakan pendekatan ini, tetapi biasanya bekerja dengan baik.S S S : = 2 S[0,1]SSS:=2S

Juga, algoritme pengambilan sampel Thompson yang Anda sebutkan memerlukan uji coba Bernoulli, sehingga Anda tidak dapat menggunakan imbalan berkelanjutan yang sewenang-wenang. Anda bisa memasukkan distribusi posterior Gaussian alih-alih Beta, tetapi ini agak sensitif terhadap pilihan Anda sebelumnya, jadi Anda mungkin ingin mengaturnya menjadi sangat datar. Jika Anda tidak ingin membuktikan apa pun tentang implementasi Anda, ini mungkin akan berfungsi dengan baik.

fairidox
sumber
1
Terima kasih banyak atas tanggapannya! Saya sangat menghargai itu! Saya punya pertanyaan. Saya pikir algoritma 2 di atas kertas (di atas halaman 39.4) yang saya sebutkan tidak memerlukan apa-apa tentang distribusi hadiah, TAPI fakta bahwa dukungannya ada di [0,1]. Mungkin Anda melihat algoritma 1?
tamu
Ya, keren, trik yang cukup menarik untuk mengonversi nilai nyata ke sampel Bernoulli, terima kasih karena menunjukkan bahwa detailnya telah lolos dari saya. Bagaimanapun, seperti yang Anda katakan, Anda masih memerlukan variabel terikat, Anda bisa melakukan ini dengan trik ganda murah yang saya sebutkan dan menggunakan versi pengambilan sampel Thompson ini. Tetapi Anda mungkin lebih baik merumuskan metode yang menggunakan posterior Gaussian.
fairidox
Saya akan melihat lebih dalam metode posterior Gaussian, tetapi apa yang Anda maksud dengan "flat" dalam hal Gaussian? Saya kira itu akan sesuai dengan sesuatu seperti Beta (1,1) (seragam) sebelumnya, benar?
tamu
benar, tetapi Anda jelas tidak dapat memiliki seragam sebelum menggunakan domain yang tidak dibatasi. Jadi, jika Anda memiliki model posterior Gaussian, Anda mungkin memiliki Gaussian prior, jadi Anda biasanya ingin memilikinya sebagai "flat" atau tidak informatif mungkin. Ini umumnya berarti membuat varians sebesar yang Anda bisa berdiri. Saya bukan ahli, tetapi ada banyak bidang studi tentang bagaimana membangun prior, mungkin berpotensi tidak tepat, dan mungkin Anda ingin melihat. Juga, jika Anda memiliki hadiah yang sangat positif, Anda mungkin ingin mempertimbangkan model yang berbeda.
fairidox