Braccia, Tiri, Ricompense
Una Fila di Macchinette
Immagina K macchinette allineate. Ogni macchina paga una ricompensa media diversa, ma non conosci nessuna delle medie. Ogni passo scegli una macchina, tiri la sua leva, & osservi un pagamento. Il tuo obiettivo: massimizzare la ricompensa totale su molti tiri.
Quella configurazione definisce un problema di bandito a braccia multiple. K = numero di braccia. Un tiro sceglie una braccio. La ricompensa proviene dalla distribuzione nascosta di quel braccio. La mean_reward(k) del braccio k traccia la media mobile sui tiri di k.
Esplorazione vs Sfruttamento
Due pressioni si tirano l'una contro l'altra:
Sfruttamento tira la leva con la media_reward osservata più alta. Avido. Rischio: una leva che sembrava ottima dopo 2 tirate potrebbe regredire a una media vera più bassa.
Esplorazione tira una leva meno testata per ridurre l'incertezza. Rischio: il tempo speso a esplorare costa ricompense che avresti potuto raccogliere da una leva nota buona.
Una buona politica mescola entrambe. La pura exploitation blocca i vincitori iniziali per sempre. La pura exploration non raccoglie mai un payoff.
Le Braccia di ANDREA = Fonti di Dati
ANDREA inquadra l'addestramento come un bandit. Ogni fonte di dati (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, ecc.) agisce come una braccio. Ogni passo di addestramento tira un braccio: carica un documento da quella fonte, esegui un forward pass, osserva la riduzione della loss. La ricompensa media per fonte traccia quanto quella fonte migliora la loss in media.
Perché si adatta: il modello cambia bisogni durante l'addestramento. I primi passi beneficiano di un'esposizione ampia (molte fonti). I passi successivi beneficiano di un polish mirato (poche fonti ad alta ricompensa). Un bandit si adatta; un rapporto di campionamento fisso non può.
Nominare i Pezzi
Il Punteggio UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer e colleghi hanno pubblicato UCB1 nel 2002 come una politica bandit a tempo finito con un bound di regret di O(log N). UCB1 sceglie un braccio combinando la sua ricompensa media corrente con un bonus di esplorazione che si riduce man mano che il braccio viene tirato.
La Formula
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Termine per termine:
- mean_reward(k): ricompensa media osservata per il braccio k sulle sue n_k estrazioni. Termine di sfruttamento.
- N: estrazioni totali su tutti i bracci finora. Cresce a ogni passo.
- n_k: estrazioni del braccio k specificamente. Cresce solo quando k viene selezionato.
- C: costante di esplorazione. Valore standard da manuale: 1.4 (sqrt(2)). ANDREA usa C=0.5.
- sqrt(ln(N) / n_k): raggio di confidenza. Un braccio raramente estratto ha n_k piccolo e riceve un grande bonus; un braccio ben estratto ha n_k grande e riceve un piccolo bonus.
Perché la Formula Funziona
ln(N) cresce lentamente (logaritmicamente), quindi il numeratore sale dolcemente con l'esperienza totale. n_k al denominatore riduce il termine man mano che le evidenze si accumulano per un braccio specifico. La radice quadrata ammorbidisce la risposta, impedendo a un singolo braccio sotto-esplorato di dominare per sempre.
Scegliere con argmax_k UCB(k) ad ogni passo bilancia automaticamente entrambe le pressioni. Nessun parametro epsilon, nessun programma, nessuna temperatura. La matematica se ne occupa.
Calcola un punteggio UCB
Perché C=0.5 invece di 1.4
Il Valore del Testo
Auer, Cesa-Bianchi & Fischer derivano un bound di regret assumendo che le ricompense siano in [0, 1]. Il bound vale per C = sqrt(2) approx 1.414. La maggior parte dei testi insegna C=1.4 come default sicuro.
Magnitudini delle Ricompense di ANDREA
ANDREA riporta miglioramenti di loss per step come ricompensa. I miglioramenti raw sono intorno a 0.001 (loss scende da 4.521 a 4.520). Dopo il fattore di scaling 1000x (coperto nell'attività 78, attribution della ricompensa), le ricompense scalate atterrano vicino a 1.0 in magnitudine. Le ricompense medie attraverso la storia di un braccio si stabilizzano in una banda da 0.5 a 3.0.
Ora considera il bonus di esplorazione con C=1.4, 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 si trova all'interno della banda di reward. Tollerabile. Ora n_k=10 (un braccio raro):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 si trova SOPRA la maggior parte delle mean_rewards osservate. L'esplorazione domina: il braccio raro vince indipendentemente dalla sua media reale. Con molte fonti e run di training lunghe, questo inonda lo schedule con braccia a bassa media.
La Soluzione: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 si posiziona sotto la maggior parte delle medie delle ricompense. L'esplorazione avviene ancora (le braccia rare ottengono ancora un bonus), ma mean_reward guida. ANDREA sfrutta di più, esplora meno e evita la dominanza dell'esplorazione.
Il Tuning come Ingegneria, Non Teoria
Il bound del textbook assume ricompense in [0, 1]. Le ricompense di ANDREA vivono approssimativamente in [0, 5]. Scalare la costante adatta la costante alla magnitudine della ricompensa. Stesso algoritmo, ambiente calibrato.
Dominanza dell'Esplorazione da Diagnosticare
Prossimo in Arrivo
Cosa Hai
UCB1 sceglie il braccio con il più alto upper confidence bound. Il bound combina mean_reward (sfruttamento) con sqrt(ln(N) / n_k) scalato da C (esplorazione). ANDREA regola C=0.5 perché le ricompense per passo si trovano in una banda da 0.5 a 3.0, & il valore di testo 1.4 inonda la schedule con bracci a bassa media.
Cosa Resta
Vanilla UCB1 sceglie un braccio alla volta. ANDREA sceglie diversi bracci focali per fase, mescola prima bracci casuali, & mantiene ogni fase per 7 a 42 passi. Quella struttura (attività 77: fasi a dadi) impedisce a UCB di impegnarsi eccessivamente nei vincitori iniziali pur permettendogli di concentrare lo sforzo.
L'attribuzione delle ricompense (attività 78) mostra da dove proviene realmente mean_reward(k). I pavimenti & le penalità per epoca (attività 79) aggiungono regole protettive sopra l'output di UCB.
Riferimento
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Whitepaper ANDREA, sezioni 3.1 e 3.4.