Saya menemukan formula untuk mendapatkan batas kepercayaan atas pada masalah bandit bersenjata k:
di mana adalah jumlah sampel yang kami miliki untuk bandit khusus ini dan adalah jumlah total sampel yang kami miliki dari semua bandit. Algoritma yang sama digunakan dalam Pencarian Pohon Monte Carlo juga untuk mendapatkan batas kepercayaan atas.
Saya mengerti dengan sangat jelas apa yang dimaksud dengan batas kepercayaan tinggi, tetapi apa yang tidak saya mengerti adalah dari mana formula ini berasal. Saya telah mencoba mencari online di beberapa tempat tetapi tidak dapat menemukan penjelasan yang jelas tentang bagaimana formula ini diturunkan. Adakah yang bisa menjelaskan dari mana formula ini berasal? Harap asumsikan saya tidak memiliki latar belakang statistik yang bagus.
sumber
Jawaban:
Apa yang Anda miliki di sana biasa disebut istilah eksplorasi. Batas kepercayaan atas adalah mean empiris ditambah istilah eksplorasi ini.
Mari kita pertimbangkan setiap istilah secara terpisah:
Untuk deskripsi yang lebih teknis, makalah oleh Auer et al. adalah titik awal yang baik.
sumber
Ini berasal dari ketidaksetaraan Hoeffding, yang memberikan batas atas pada probabilitas bahwa jumlah variabel acak terikat independen menyimpang dari nilai yang diharapkan dengan lebih dari jumlah tertentu. Lihat https://en.wikipedia.org/wiki/Hoeffding%27s_inequality untuk informasi lebih lanjut tentang ketidaksetaraan Hoeffding. Lihat teks di sekitar persamaan (3) dalam makalah UCT asli untuk diskusi terperinci terkait dengan UCB1 di pengaturan bandit http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.1296
sumber