Masalah Warren Buffett

Ini adalah abstraksi dari masalah pembelajaran / bandit online yang telah saya kerjakan di musim panas. Saya belum pernah melihat masalah seperti ini sebelumnya, dan itu terlihat cukup menarik. Jika Anda tahu ada pekerjaan terkait, saya sangat menghargai referensi.

Masalah Pengaturannya adalah bandit multi-bersenjata. Anda memiliki lengan N. Setiap lengan saya memiliki distribusi probabilitas yang tidak diketahui tetapi tetap atas hadiah yang dapat diperoleh dengan memainkannya. Untuk konkret, mari kita asumsikan bahwa setiap lengan saya membayar hadiah $ 10 dengan probabilitas p [i] dan hadiah $ 0 dengan prob. 1-p [i] .

Dalam setiap putaran t Anda memilih satu set S [t] senjata untuk bermain. Untuk setiap lengan yang Anda pilih, Anda membayar biaya $ 1 di muka. Untuk setiap lengan yang dipilih, Anda mengumpulkan hadiah yang diambil dari distribusi probabilitas hadiah (tidak diketahui) dari lengan itu. Semua hadiah dikreditkan ke rekening bank Anda, dan semua biaya dikurangkan dari akun itu. Selain itu, Anda mendapatkan kredit $ 1 di awal setiap iterasi.

Masalahnya adalah untuk mengembangkan kebijakan untuk memilih subset senjata untuk dimainkan di setiap iterasi untuk memaksimalkan keuntungan (yaitu hadiah dikurangi biaya untuk bermain) selama cakrawala yang cukup lama, tunduk pada batasan bahwa ia harus mempertahankan saldo akun non-negatif di setiap saat.

Saya tidak menentukan apakah distribusi hadiah per-lengan dipilih dari distribusi sebelumnya atau dipilih oleh musuh. Kedua pilihan itu masuk akal. Formulasi musuh lebih menarik bagi saya, tetapi mungkin lebih sulit untuk membuat kemajuan. Di sini, musuh memilih vektor (D1, D2, .., DN) dari distribusi. Mengingat distribusi, kebijakan seimbang anggaran optimal adalah untuk memainkan semua senjata yang hadiah yang diharapkan lebih dari $ 1. Biarkan P menjadi laba per langkah dari kebijakan mahatahu yang optimal ini. Saya ingin kebijakan online saya untuk meminimalkan penyesalan (yaitu hilangnya laba selama jangka waktu T), menggunakan kebijakan yang maha tahu ini.

Saya membayangkan ada banyak pendekatan yang mungkin untuk masalah ini (banyak yang saya yakin Anda pertimbangkan) - berikut adalah beberapa ide / referensi.

• $N$
• $O(2^{N/2} T^{1/2})$
• Dalam makalah NIPS 2010 mendatang, Saten Kale, Rob Schapire, dan saya mempertimbangkan kasus di mana seseorang memainkan serentetan senjata sekaligus. Namun, dalam pekerjaan kami, ukuran batu tulis ditetapkan. Makalah ini juga mempertimbangkan masalah serupa. Karya lain yang serupa muncul di ALT 2010. Mungkin beberapa gagasan berpindah.
• $2^N$$O(N\sqrt{T})$$O(2^N T)$

Sunting di bawah ini:

$0$$1$$(n-1)/n$$T$$T$$(n-1)T/n$

$B$$0$$2B$$1/B$