Masalah Lock-In
Seorang Bandit yang Terus Menang
Vanilla UCB1 menghitung ulang skor setiap langkah. Memilih satu lengan. Menariknya. Memperbarui n_k & mean_reward(k). Mengulangi. Dalam pelatihan panjang dengan banyak sumber, satu lengan dapat mengumpulkan serangkaian hadiah tinggi, mendorong rata-ratanya naik, & menjadi hampir tidak mungkin dikalahkan. Lengan lain stagnan pada n_k rendah dengan rata-rata usang. Lock-in.
Lock-in merugikan ANDREA dalam dua cara:
1. Kehilangan keberagaman. Model yang melatih 90% langkah pada satu sumber mempelajari ciri gaya sumber tersebut. Sampel generasi bergeser menuju pola berulang yang cocok dengan sumber dominan.
2. Eksplorasi usang. Lengan dengan rata-rata usang tidak dapat pulih. Lengan yang rata-ratanya turun lebih awal tetap terjebak pada rata-rata tersebut meskipun model sekarang memiliki kapasitas yang cukup untuk mengekstrak hadiah darinya.
Sebuah Fase Membeli Waktu
Solusi: tahan satu set lengan fokus tetap untuk satu fase (beberapa langkah) sebelum mengevaluasi ulang. Fase 14 langkah berarti 14 forward pass mengenai lengan fokus yang sama. Rata-rata hadiah stabil. Kebisingan stokastik merata. Kemudian bandit melempar ulang.
Panjang Fase Variabel
ANDREA memilih panjang fase secara acak seragam dari {7, 14, 21, 28, 42} langkah pada setiap batas fase. Lima nilai, acak seragam. Fase pendek (7) bereaksi cepat terhadap pilihan buruk; fase panjang (42) membiarkan set fokus stabil dieksploitasi sepenuhnya. Batas atas membatasi kerusakan: paling banyak 42 langkah yang dihabiskan pada konfigurasi fokus buruk sebelum dipaksa gulir ulang.
Statistik Panjang Fase
1d3 (2-mata) & 1d4 (3-mata)
Notasi Dadu
Notasi tabletop: NdM berarti lempar N dadu dengan M sisi masing-masing. 1d3 melempar satu dadu 3 sisi, menghasilkan nilai dalam {1, 2, 3}. 1d4 melempar satu dadu 4 sisi, menghasilkan {1, 2, 3, 4}. ANDREA juga mengizinkan hasil 0 dengan konvensi: lemparan 0 berarti fase sepenuhnya acak (tidak ada lengan fokus UCB).
Konfigurasi 2-Mata vs 3-Mata
Konfigurasi pelatihan ANDREA memilih salah satu dari dua mode dadu:
Konfigurasi 2-mata (1d3). Jumlah lengan fokus yang mungkin: {0, 1, 2, 3}. Hasil 0 disediakan untuk fase acak.
Konfigurasi 3-mata (1d4). Jumlah lengan fokus yang mungkin: {0, 1, 2, 3, 4}. Pool yang lebih besar memungkinkan fase yang lebih terkonsentrasi.
Acak Terlebih Dahulu, UCB Kedua
Apapun hasil lemparan dadu, ANDREA mengisi slot fokus dalam dua tahap:
1. Lengan acak terlebih dahulu. Pilih sebagian slot fokus secara seragam secara acak dari semua lengan yang tersedia. Ini memaksa variasi kombinatorial setiap fase, terlepas dari peringkat UCB.
2. UCB mengisi slot yang tersisa. Hitung skor UCB1 untuk lengan yang belum dipilih. Ambil lengan dengan peringkat teratas yang tersisa hingga jumlah slot fokus terpenuhi.
Pemilihan acak terlebih dahulu penting. Jika UCB dipilih terlebih dahulu, pemimpin streak akan selalu mengklaim slot. Dengan random-first, bahkan lengan UCB terbaik pun bisa tidak terpilih dalam satu fase. Keberagaman tetap terjamin.
Fase Pure Random
Ketika dadu menghasilkan 0, seluruh set fokus berasal dari pemilihan acak. UCB tidak berkontribusi apa pun. Sekitar 25% fase (1d4) atau 33% fase (1d3) jatuh ke sini. Fase pure random memaksa bandit untuk menyegarkan sampelnya dari lengan yang jarang ditarik, menjaga estimasi mean_reward tetap jujur di seluruh kumpulan lengan.
Probabilitas Hasil Dadu
Membatasi Kerusakan
Satu Fase Buruk Biayanya Hingga 42 Langkah
Misalkan peringkat UCB memilih lengan fokus yang rata-rata sebenarnya jauh lebih rendah daripada rata-rata teramatinya. Fase tersebut mengunci lengan itu. Hadiah tetap rendah untuk seluruh fase. Berapa lama sampai bandit bisa memperbaiki?
Panjang fase maksimum: 42 langkah. Setelah 42 langkah, fase berakhir, dadu digulir ulang, lengan fokus diacak ulang. Pilihan buruk tidak bisa bertahan lebih dari 42 operasi maju.
Mengapa 42 (Bukan 100, Bukan 1000)
Fase panjang memungkinkan estimasi mean_reward stabil. Teori statistik: varians dari rata-rata n sampel menyusut sebesar 1/n. Dari 7 sampel ke 42 sampel memberikan 6x lebih banyak sampel, sqrt(6) sekitar 2.45x standard error yang lebih ketat. Setelah 42 sampel, mean_reward berada dalam kisaran kira-kira +/-15% dari nilai sebenarnya (tergantung varians reward).
Melewati 42 sampel, keuntungannya menyusut: 100 sampel vs 42 sampel = 2.4x lebih banyak, sqrt(2.4) sekitar 1.55x standard error yang lebih ketat. Manfaat marginal menurun seiring meningkatnya biaya dari kunci buruk. 42 langkah menyeimbangkan keduanya.
Keberagaman vs Konvergensi
Fase pendek (7 langkah): estimasi reward tetap bising, tapi pilihan buruk biayanya kecil. Fase panjang (42 langkah): estimasi ketat, tapi pilihan buruk biayanya lebih besar. ANDREA mencampur panjang fase secara seragam sehingga kedua rezim muncul di setiap jalankan pelatihan.
Biaya Pembangunan Ulang Btok
Setiap batas fase memicu pembangunan ulang file btok untuk lengan fokus. Pembangunan ulang btok berjalan di thread latar belakang; CUDA hot-reload pada perubahan mtime. Pembangunan ulang memakan waktu detik; fase harus berjalan cukup lama sehingga overhead pembangunan ulang tetap kecil. 42 langkah pada kecepatan pelatihan ANDREA-120M dengan nyaman melebihi waktu pembangunan ulang.
Pemikiran Tentang Batas Atas
Selanjutnya
Apa yang Anda Miliki
Kontrol dadu berbasis fase membungkus UCB1 dalam tiga aturan pelindung: panjang fase variabel (7-42), lengan acak terlebih dahulu, fase acak yang digerakkan dadu (25-33% murni acak). Batasan 42 langkah membatasi kerusakan; fase acak mencegah kuncian; panjang variabel mencampur kecepatan reaksi dengan stabilitas estimasi.
Apa yang Tersisa
Dari mana sebenarnya sinyal reward yang memberi makan UCB berasal? Aktivitas 78 (atribusi reward) menunjukkan bagaimana CUDA melaporkan kerugian per-sumber setiap langkah, bagaimana EMA per-sumber melacak reward, & mengapa ANDREA menskalakan reward mentah 1000x sebelum memberi makan UCB1.
Lantai & penalti epoch (aktivitas 79) menambahkan lapisan aturan pelindung lebih lanjut di atas output bandit, memastikan sumber kecil tidak kelaparan & sumber besar tidak diulang untuk hafalan.
Referensi
Whitepaper ANDREA, bagian 3.2.