Kilitlenme Sorunu
Sürekli Kazanan Bir Haydut
Vanilya UCB1 her adımda skorları yeniden hesaplar. Bir kolu seçer. Çeker. n_k ve mean_reward(k)'yi günceller. Tekrarlar. Birçok kaynakla uzun bir eğitim çalışmasında, tek bir kol yüksek ödüller zinciri toplayabilir, ortalamasını yükseltebilir ve yenilmesi neredeyse imkansız hale gelebilir. Diğer kollar düşük n_k ile bayat ortalamalarda durgunlaşır. Kilitlenme.
Kilitlenme ANDREA'ya iki şekilde zarar verir:
1. Çeşitlilik çöküşü. Adımların %90'ını tek bir kaynaktan eğiten bir model, o kaynağın üslup tiklerini öğrenir. Üretilen örnekler, baskın kaynağa uyan tekrarlayan kalıplara doğru kayar.
2. Bayat keşif. Bayat ortalamalara sahip kollar toparlanamaz. Erken dönemde ortalaması düşen bir kol, model artık o koldan ödül çıkaracak kapasiteye sahip olsa bile o ortalamada sıkışıp kalır.
Bir Aşama Zaman Kazanır
Çözüm: bir aşama (birden fazla adım) boyunca sabit bir odak kolları kümesini tutun, ardından yeniden değerlendirin. 14 adımlık bir aşama, 14 ileri geçişin aynı odak kollarına çarpması anlamına gelir. Ortalama ödüller stabilize olur. Stokastik gürültü ortalamadan çıkar. Sonra bandit yeniden zar atar.
Değişken Aşama Uzunluğu
ANDREA her faz sınırında {7, 14, 21, 28, 42} adımlardan rastgele bir faz uzunluğu seçer. Beş değer, uniform rastgele. Kısa fazlar (7) kötü seçimlere hızlı tepki verir; uzun fazlar (42) stabil odak setlerinin tam olarak sömürülmesine izin verir. Tavan hasarı sınırlar: kötü bir odak konfigürasyonu için en fazla 42 adım harcanır, ardından zorunlu yeniden atış.
Faz Uzunluğu İstatistikleri
1d3 (2-göz) & 1d4 (3-göz)
Zar Notasyonu
Masaüstü notasyonu: NdM her biri M yüzlü N zar atmak anlamına gelir. 1d3 bir 3 yüzlü zar atar, {1, 2, 3} değerlerinden birini döndürür. 1d4 bir 4 yüzlü zar atar, {1, 2, 3, 4} döndürür. ANDREA ayrıca gelenek gereği 0 sonucuna izin verir: 0 atışı tamamen rastgele faz (UCB odak kolları yok) anlamına gelir.
2-Göz vs 3-Göz Yapılandırmaları
ANDREA'nın eğitim yapılandırması iki zar modundan birini seçer:
2-göz konfigürasyonu (1d3). Olası odak kol sayıları: {0, 1, 2, 3}. Sonuç 0 rastgele faz için ayrılmıştır.
3-göz konfigürasyonu (1d4). Olası odak kol sayıları: {0, 1, 2, 3, 4}. Daha büyük havuzlar daha yoğun fazlara izin verir.
Önce Rastgele, Sonra UCB
Zar sonuçları ne olursa olsun, ANDREA odak yuvalarını iki geçişte doldurur:
1. Önce rastgele kollar. Mevcut tüm kollar arasından odak yuvalarının bir kısmını uniform rastgele seçin. Bu, UCB sıralamalarına bakılmaksızın her fazda kombinatorial çeşitliliği zorlar.
2. UCB kalan slotları doldurur. Zaten seçilmiş kollar hariç kollar için UCB1 skorlarını hesapla. Odak slot sayısı dolana kadar en üst sıradaki kalan kolları al.
Önce rastgele seçimin önemi. Eğer UCB önce seçseydi, bir seri lideri her zaman bir slot kapardı. Rastgele-önce ile, en iyi UCB kolu bile bir fazı dışarıda kalabilir. Çeşitlilik garanti kalır.
Saf Rastgele Fazlar
Zar 0 attığında, tüm odak kümesi rastgele seçimlerden gelir. UCB hiçbir şey katkıda bulunmaz. Yaklaşık %25'lik fazlar (1d4) veya %33'lük fazlar (1d3) buraya düşer. Saf rastgele fazlar, bantitin az çekilmiş kolların örneğini yenilemesini zorlar, ortalama ödül tahminlerini tüm kol havuzunda dürüst tutar.
Zar Sonucu Olasılıkları
Hasarı Sınırlama
Kötü Bir Faz En Fazla 42 Adım Mal Olur
UCB sıralamalarının, gözlemlenen ortalamasından çok daha düşük gerçek ortalamaya sahip bir odak kolu seçtiğini varsayalım. Faz o kolu kilitleyecek. Ödül tüm faz boyunca düşük kalacak. Banditin düzeltmesi ne kadar sürer?
Maksimum faz uzunluğu: 42 adım. 42 adımdan sonra faz biter, zarlar yeniden atılır, odak kolları yeniden karıştırılır. Kötü seçim 42 ileri geçişten daha uzun süremez.
Neden 42 (Ve Değil 100, & Değil 1000)
Uzun fazlar mean_reward tahminlerinin stabilize olmasını sağlar. İstatistiksel teori: n örnek ortalamasının varyansı 1/n oranında küçülür. 7 örnekten 42 örneğe geçmek 6 kat daha fazla örnek verir, sqrt(6) yaklaşık 2.45 kat daha dar standart hata. 42 örnekten sonra mean_reward, gerçek değerinin yaklaşık +/-%15'i içinde oturur (ödül varyansına bağlı olarak).
42 örnekten sonra kazanç küçülür: 100 örnek vs 42 örnek = 2.4 kat daha fazla, sqrt(2.4) yaklaşık 1.55 kat daha dar standart hata. Kötü kilitlenmenin maliyeti arttıkça marjinal fayda düşer. 42 adım ikisini dengeler.
Çeşitlilik vs Yakınsama
Kısa fazlar (7 adım): ödül tahminleri gürültülü kalır, ancak kötü seçimler az maliyetlidir. Uzun fazlar (42 adım): tahminler sıkı, ancak kötü seçimler daha fazla maliyetlidir. ANDREA faz uzunluklarını uniform şekilde karıştırır böylece her eğitim çalıştırmasında her iki rejim de görünür.
Btok Yeniden İnşa Maliyeti
Her faz sınırı, odak kolları için bir btok dosyası yeniden inşasını tetikler. Btok yeniden inşası arka plan thread'inde çalışır; CUDA mtime değişikliğinde hot-reload yapar. Yeniden inşa saniyeler alır; fazlar yeniden inşa yükünün küçük kalması için yeterince uzun çalışmalıdır. ANDREA-120M eğitim hızında 42 adım, yeniden inşa süresini rahatça aşar.
Tavan Hakkında Akıl Yürütme
Sırada Ne Var
Sahip Olduklarınız
Faz tabanlı zar kontrolü, UCB1'i üç koruyucu kuralda sarar: değişken faz uzunluğu (7-42), önce rastgele kollar, zar odaklı rastgele fazlar (25-33% saf rastgele). 42-adımlık tavan hasarı sınırlar; rastgele fazlar kilitlenmeyi önler; değişken uzunluklar tepki hızını tahmin istikrarıyla karıştırır.
Kalanlar
UCB'ye beslenen ödül sinyali aslında nereden geliyor? Etkinlik 78 (ödül atfetme), CUDA'nın her adımda kaynak başına kayıp raporladığını, kaynak başına EMA'nın ödülü izlediğini ve ANDREA'nın ham ödülleri UCB1'e beslemeden önce 1000x ölçeklediğini gösterir.
Zeminler ve epoch cezaları (etkinlik 79), haydutun çıktısının üzerine daha fazla koruyucu kural katmanını ekler; küçük kaynakların aç kalmamasını ve büyük kaynakların ezberlenmeye tekrarlanmamasını sağlar.
Kaynak
ANDREA whitepaper, bölüm 3.2.