Lengan, Tarikan, Hadiah
Barisan Mesin Slot
Bayangkan K mesin slot yang berbaris. Setiap mesin membayar hadiah rata-rata yang berbeda, tapi Anda tidak tahu rata-rata mana pun. Setiap langkah Anda memilih satu mesin, menarik tuasnya, & mengamati pembayaran. Tujuan Anda: memaksimalkan total hadiah di seluruh banyak tarikan.
Pengaturan itu mendefinisikan masalah multi-armed bandit. K = jumlah lengan. Sebuah tarikan memilih satu lengan. Hadiah berasal dari distribusi tersembunyi lengan tersebut. mean_reward(k) dari lengan k melacak rata-rata berjalan di seluruh tarikan k.
Eksplorasi vs Eksploitasi
Dua tekanan saling menarik satu sama lain:
Eksploitasi menarik tuas dengan rata-rata_reward teramati tertinggi. Rakus. Risiko: tuas yang terlihat bagus setelah 2 tarikan mungkin regresi ke rata-rata sebenarnya yang lebih rendah.
Eksplorasi menarik tuas yang kurang diuji untuk mengurangi ketidakpastian. Risiko: waktu yang dihabiskan untuk mengeksplorasi merugikan reward yang bisa dikumpulkan dari tuas baik yang sudah diketahui.
Kebijakan yang baik menggabungkan keduanya. Eksploitasi murni mengunci pemenang awal selamanya. Eksplorasi murni tidak pernah mengumpulkan imbalan.
Lengan ANDREA = Sumber Data
ANDREA membingkai pelatihan sebagai bandit. Setiap sumber data (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, dll.) bertindak sebagai lengan. Setiap langkah pelatihan menarik satu lengan: muat dokumen dari sumber tersebut, jalankan forward pass, amati pengurangan loss. Rata-rata imbalan per sumber melacak seberapa banyak sumber tersebut meningkatkan loss secara rata-rata.
Mengapa ini cocok: model membutuhkan perubahan selama pelatihan. Langkah awal mendapat manfaat dari paparan luas (banyak sumber). Langkah akhir mendapat manfaat dari polesan tertarget (beberapa sumber imbalan tinggi). Bandit beradaptasi; rasio sampling tetap tidak bisa.
Menamai Bagian-bagiannya
Skor UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer & rekan-rekannya menerbitkan UCB1 pada tahun 2002 sebagai kebijakan bandit waktu-finit dengan batas penyesalan O(log N). UCB1 memilih lengan dengan menggabungkan rata-rata reward saat ini dengan bonus eksplorasi yang mengecil seiring lengan ditarik.
Rumus
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Istilah demi istilah:
- mean_reward(k): rata-rata reward yang diamati untuk lengan k di seluruh n_k tarikan. Istilah eksploitasi.
- N: total tarikan di seluruh lengan sejauh ini. Bertambah setiap langkah.
- n_k: tarikan lengan k secara khusus. Bertambah hanya ketika k dipilih.
- C: konstanta eksplorasi. Nilai standar buku teks: 1.4 (sqrt(2)). ANDREA menggunakan C=0.5.
- sqrt(ln(N) / n_k): radius kepercayaan. Lengan yang jarang ditarik memiliki n_k kecil & mendapat bonus besar; lengan yang sering ditarik memiliki n_k besar & mendapat bonus kecil.
Mengapa Rumus Ini Bekerja
ln(N) tumbuh perlahan (logaritmik), sehingga pembilang naik secara lembut seiring pengalaman total. n_k di penyebut mengecilkan istilah tersebut seiring bukti terkumpul untuk lengan tertentu. Akar kuadrat melembutkan respons, yang mencegah satu lengan kurang tereksplorasi mendominasi selamanya.
Memilih dengan argmax_k UCB(k) setiap langkah menyeimbangkan kedua tekanan secara otomatis. Tidak ada parameter epsilon, tidak ada jadwal, tidak ada suhu. Matematika yang mengaturnya.
Hitung Skor UCB
Mengapa C=0.5 Bukan 1.4
Nilai dalam Buku Teks
Auer, Cesa-Bianchi & Fischer menyimpulkan batas penyesalan dengan asumsi reward berada di [0, 1]. Batas tersebut berlaku untuk C = sqrt(2) kira-kira 1.414. Sebagian besar buku teks mengajarkan C=1.4 sebagai default yang aman.
Magnitudo Reward ANDREA
ANDREA melaporkan perbaikan loss per langkah sebagai reward. Perbaikan mentah berkisar sekitar 0.001 (loss turun dari 4.521 ke 4.520). Setelah faktor skala 1000x (dibahas di aktivitas 78, reward attribution), reward yang diskalakan berada di sekitar 1.0 dalam magnitudo. Rata-rata reward sepanjang riwayat sebuah arm menetap di rentang 0.5 hingga 3.0.
Sekarang pertimbangkan bonus eksplorasi pada C=1.4 dengan N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 berada di dalam rentang reward. Dapat diterima. Sekarang n_k=10 (lengan langka):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 berada DI ATAS sebagian besar mean_rewards yang diamati. Eksplorasi mendominasi: lengan langka menang terlepas dari mean sebenarnya. Dengan banyak sumber & pelatihan panjang, ini membanjiri jadwal dengan lengan ber-mean rendah.
Perbaikan: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 berada di bawah sebagian besar rata-rata reward. Eksplorasi masih terjadi (lengan langka masih mendapat bonus), tetapi mean_reward yang memimpin. ANDREA lebih banyak mengeksploitasi, lebih sedikit mengeksplorasi, & menghindari dominasi eksplorasi.
Penalaan sebagai Teknik, Bukan Teori
Batas teksbook mengasumsikan reward dalam [0, 1]. Reward ANDREA hidup di sekitar [0, 5]. Menskalakan konstanta menyesuaikan konstanta dengan magnitudo reward. Algoritma yang sama, lingkungan yang dikalibrasi.
Diagnosis Dominasi Eksplorasi
Selanjutnya yang Akan Datang
Apa yang Anda Miliki
UCB1 memilih lengan dengan upper confidence bound tertinggi. Batas tersebut menggabungkan mean_reward (eksploitasi) dengan sqrt(ln(N) / n_k) yang diskalakan oleh C (eksplorasi). ANDREA menyetel C=0.5 karena hadiah per langkah berada dalam rentang 0.5 hingga 3.0, & nilai 1.4 dari buku teks membanjiri jadwal dengan lengan ber-mean rendah.
Apa yang Tersisa
Vanilla UCB1 memilih satu lengan pada satu waktu. ANDREA memilih beberapa lengan fokus per fase, mencampur lengan acak terlebih dahulu, & mempertahankan setiap fase selama 7 hingga 42 langkah. Struktur tersebut (aktivitas 77: fase dadu) mencegah UCB terlalu berkomitmen pada pemenang awal sambil tetap memungkinkan konsentrasi usaha.
Atribusi reward (aktivitas 78) menunjukkan dari mana mean_reward(k) sebenarnya berasal. Lantai & penalti epoch (aktivitas 79) menambahkan aturan pelindung di atas output UCB.
Referensi
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA whitepaper, bagian 3.1 & 3.4.