Bras, Tirages, Récompenses
Une Rangée de Machines à Sous
Imaginez K machines à sous alignées. Chaque machine paie une récompense moyenne différente, mais vous ne connaissez aucune des moyennes. À chaque étape, vous choisissez une machine, tirez son levier, & observez un paiement. Votre objectif : maximiser la récompense totale sur de nombreux tirages.
Cette configuration définit un problème de bandit à plusieurs bras. K = nombre de bras. Un tirage choisit un bras. La récompense provient de la distribution cachée de ce bras. La mean_reward(k) du bras k suit la moyenne glissante sur les tirages de k.
Exploration vs Exploitation
Deux pressions s'opposent l'une à l'autre :
Exploitation tire le bras avec la récompense moyenne observée la plus élevée. Avide. Risque : un bras qui semblait excellent après 2 tirages pourrait régresser vers une vraie moyenne plus basse.
Exploration tire un bras moins testé pour réduire l'incertitude. Risque : le temps passé à explorer coûte des récompenses que vous auriez pu collecter d'un bras connu comme bon.
Une bonne politique mélange les deux. L'exploitation pure verrouille les premiers gagnants pour toujours. L'exploration pure ne collecte jamais de récompense.
Les bras d'ANDREA = Sources de données
ANDREA cadre l'entraînement comme un bandit. Chaque source de données (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) agit comme un bras. Chaque étape d'entraînement tire un bras : charge un document de cette source, exécute un passage avant, observe la réduction de perte. La récompense moyenne par source suit dans quelle mesure cette source améliore la perte en moyenne.
Pourquoi cela convient : les besoins du modèle changent pendant l'entraînement. Les premières étapes bénéficient d'une exposition large (plusieurs sources). Les étapes ultérieures bénéficient d'un polissage ciblé (quelques sources à haute récompense). Un bandit s'adapte ; un ratio d'échantillonnage fixe ne peut pas.
Nommer les pièces
Le Score UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer et ses collègues ont publié UCB1 en 2002 comme une politique de bandit à temps fini avec une borne de regret de O(log N). UCB1 choisit un bras en combinant sa récompense moyenne actuelle avec un bonus d'exploration qui diminue à mesure que le bras est tiré.
La Formule
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Terme par terme :
- mean_reward(k) : récompense moyenne observée pour le bras k sur ses n_k tirages. Terme d'exploitation.
- N : nombre total de tirages sur tous les bras jusqu'à présent. Augmente à chaque étape.
- n_k : nombre de tirages du bras k spécifiquement. Augmente seulement quand k est sélectionné.
- C : constante d'exploration. Valeur standard des manuels : 1.4 (sqrt(2)). ANDREA utilise C=0.5.
- sqrt(ln(N) / n_k) : rayon de confiance. Un bras rarement tiré a un petit n_k et reçoit un gros bonus ; un bras bien tiré a un grand n_k et reçoit un petit bonus.
Pourquoi la formule fonctionne
ln(N) croît lentement (logarithmique), donc le numérateur augmente doucement avec l'expérience totale. n_k au dénominateur réduit le terme à mesure que les preuves s'accumulent pour un bras spécifique. La racine carrée adoucit la réponse, ce qui empêche un seul bras sous-exploré de dominer indéfiniment.
Sélectionner par argmax_k UCB(k) à chaque étape équilibre automatiquement les deux pressions. Pas de paramètre epsilon, pas de calendrier, pas de température. Les maths s'en chargent.
Calculer un score UCB
Pourquoi C=0.5 au lieu de 1.4
La valeur du manuel
Auer, Cesa-Bianchi & Fischer dérivent une borne de regret en supposant que les récompenses se situent dans [0, 1]. La borne est valable pour C = sqrt(2) approx 1.414. La plupart des manuels enseignent C=1.4 comme valeur par défaut sûre.
Les magnitudes de récompenses d'ANDREA
ANDREA rapporte les améliorations de perte par étape comme récompense. Les améliorations brutes tournent autour de 0.001 (la perte passe de 4.521 à 4.520). Après le facteur d'échelle 1000x (couvert dans l'activité 78, attribution de récompense), les récompenses échelonnées atteignent une magnitude proche de 1.0. Les récompenses moyennes sur l'historique d'un bras se stabilisent dans une bande de 0.5 à 3.0.
Considérons maintenant le bonus d'exploration avec 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 se situe à l'intérieur de la bande de récompense. Tolérable. Maintenant n_k=10 (un bras rare) :
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 se situe AU-DESSUS de la plupart des mean_rewards observées. L'exploration domine : le bras rare gagne indépendamment de sa moyenne réelle. Avec de nombreuses sources & des entraînements longs, cela inonde l'horaire de bras à faible moyenne.
La Solution : C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 se situe en dessous de la plupart des moyennes de récompenses. L'exploration se produit toujours (les bras rares obtiennent encore un bonus), mais mean_reward domine. ANDREA exploite plus, explore moins, & évite la domination de l'exploration.
L'accordage comme Ingénierie, Pas Théorie
La borne du manuel suppose des récompenses dans [0, 1]. Les récompenses d'ANDREA vivent dans environ [0, 5]. Échelle la constante pour correspondre à la magnitude des récompenses. Même algorithme, environnement calibré.
Diagnostic de la Dominance de l'Exploration
À Venir Prochainement
Ce Que Vous Avez
UCB1 choisit le bras avec la borne supérieure de confiance la plus élevée. La borne combine mean_reward (exploiter) avec sqrt(ln(N) / n_k) scalé par C (explorer). ANDREA ajuste C=0.5 car les récompenses par étape se situent dans une bande de 0.5 à 3.0, & le 1.4 du manuel inonde l'horaire de bras à faible moyenne.
Ce qui reste
Vanilla UCB1 choisit un bras à la fois. ANDREA choisit plusieurs bras de focus par phase, mélange d'abord des bras aléatoires, & maintient chaque phase pendant 7 à 42 étapes. Cette structure (activité 77 : phases de dés) empêche UCB de s'engager excessivement sur les premiers gagnants tout en lui permettant encore de concentrer l'effort.
L'attribution des récompenses (activité 78) montre d'où vient réellement mean_reward(k). Les planchers & pénalités d'époque (activité 79) ajoutent des règles protectrices par-dessus la sortie d'UCB.
Référence
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Whitepaper ANDREA, sections 3.1 & 3.4.