Le problème du verrouillage
Un bandit qui continue de gagner
UCB1 vanilla recalcule les scores à chaque étape. Il choisit un bras. Il le tire. Il met à jour n_k & mean_reward(k). Il répète. Dans une longue exécution d'entraînement avec de nombreuses sources, un seul bras peut accumuler une série de récompenses élevées, faire monter sa moyenne, & devenir quasi impossible à battre. Les autres bras stagnent avec un n_k faible et des moyennes obsolètes. Verrouillage.
Le verrouillage nuit à ANDREA de deux manières :
1. Effondrement de la diversité. Un modèle qui entraîne 90 % de ses étapes sur une seule source apprend les tics stylistiques de cette source. Les échantillons générés dérivent vers des motifs répétitifs correspondant à la source dominante.
2. Exploration obsolète. Les bras dont les moyennes sont obsolètes ne peuvent pas se rétablir. Un bras dont la moyenne a chuté tôt reste bloqué à cette moyenne, même si le modèle a désormais suffisamment de capacité pour en extraire une récompense.
Une phase achète du temps
Solution : maintenir un ensemble fixe de bras de focus pendant une phase (plusieurs étapes) avant de réévaluer. Une phase de 14 étapes signifie que 14 passes en avant touchent les mêmes bras de focus. Les récompenses moyennes se stabilisent. Le bruit stochastique est moyenné. Ensuite, le bandit relance.
Longueur de phase variable
ANDREA choisit aléatoirement la durée de la phase parmi {7, 14, 21, 28, 42} étapes à chaque frontière de phase. Cinq valeurs, tirage uniforme. Les phases courtes (7) réagissent rapidement aux mauvais choix ; les phases longues (42) permettent aux ensembles de focus stables de s'exploiter pleinement. Le plafond limite les dégâts : au maximum 42 étapes sont passées sur une configuration de focus défavorable avant un nouveau tirage forcé.
Statistiques de la durée des phases
1d3 (2 yeux) & 1d4 (3 yeux)
Notation des dés
Notation de plateau : NdM signifie lancer N dés à M faces chacun. 1d3 lance un dé à 3 faces, renvoyant une valeur dans {1, 2, 3}. 1d4 lance un dé à 4 faces, renvoyant {1, 2, 3, 4}. ANDREA autorise également le résultat 0 par convention : un lancer de 0 signifie phase entièrement aléatoire (aucun bras de concentration UCB).
Configurations 2 yeux vs 3 yeux
La configuration d'entraînement d'ANDREA choisit l'un des deux modes de dés :
Configuration 2 yeux (1d3). Nombre de bras de focus possibles : {0, 1, 2, 3}. Le résultat 0 est réservé pour la phase aléatoire.
Configuration 3 yeux (1d4). Nombre de bras de focus possibles : {0, 1, 2, 3, 4}. Des réservoirs plus grands permettent des phases plus concentrées.
Aléatoire d'abord, UCB ensuite
Quels que soient les résultats des dés, ANDREA remplit les emplacements de focus en deux passes :
1. D'abord les bras aléatoires. Choisir une fraction des emplacements de focus de manière uniforme et aléatoire parmi tous les bras disponibles. Cela force une variété combinatoire à chaque phase, indépendamment des classements UCB.
2. UCB remplit les emplacements restants. Calculez les scores UCB1 pour les bras non encore sélectionnés. Prenez les bras restants classés en tête jusqu'à ce que le nombre d'emplacements de focus soit atteint.
Le tirage aléatoire initial est essentiel. Si UCB était choisi en premier, un bras en tête de série réclamerait toujours un emplacement. Avec le tirage aléatoire initial, même le meilleur bras UCB peut être écarté d'une phase. La diversité reste garantie.
Phases purement aléatoires
Lorsque les dés affichent 0, l'ensemble de focus provient entièrement de tirages aléatoires. UCB n'apporte rien. Environ 25 % des phases (1d4) ou 33 % des phases (1d3) tombent dans cette catégorie. Les phases purement aléatoires obligent le bandit à rafraîchir son échantillon de bras à faible tirage, maintenant ainsi les estimations de mean_reward honnêtes sur l'ensemble du pool de bras.
Probabilités des résultats des dés
Mettre un plafond aux dégâts
Une mauvaise phase coûte jusqu'à 42 étapes
Supposons que les classements UCB choisissent un bras dont la moyenne réelle est beaucoup plus basse que sa moyenne observée. La phase verrouille ce bras. La récompense reste faible pendant toute la phase. Combien de temps avant que le bandit puisse corriger ?
Longueur maximale de phase : 42 étapes. Après 42 étapes, la phase se termine, les dés sont relancés et les bras de focus sont mélangés. Le mauvais choix ne peut pas durer plus de 42 passes en avant.
Pourquoi 42 (& pas 100, & pas 1000)
Les phases longues permettent aux estimations de mean_reward de se stabiliser. Théorie statistique : la variance d'une moyenne de n échantillons diminue en 1/n. Passer de 7 échantillons à 42 échantillons donne 6 fois plus d'échantillons, ce qui entraîne un écart-type environ 2,45 fois plus serré (sqrt(6) ≈ 2,45). Après 42 échantillons, mean_reward se situe à environ +/-15 % de sa valeur réelle (selon la variance de la récompense).
Au-delà de 42 échantillons, le gain diminue : 100 échantillons par rapport à 42 échantillons = 2,4 fois plus, ce qui donne un écart-type environ 1,55 fois plus serré (sqrt(2,4) ≈ 1,55). Le bénéfice marginal diminue à mesure que le coût d'un mauvais verrouillage augmente. 42 étapes équilibrent les deux.
Diversité vs Convergence
Les phases courtes (7 étapes) : les estimations de récompense restent bruitées, mais les mauvais choix coûtent peu. Les phases longues (42 étapes) : les estimations sont précises, mais les mauvais choix coûtent plus cher. ANDREA mélange uniformément les longueurs de phase afin que les deux régimes apparaissent dans chaque exécution d'entraînement.
Coût de reconstruction Btok
Chaque frontière de phase déclenche une reconstruction du fichier btok pour les bras de focalisation. La reconstruction btok s'exécute dans un thread en arrière-plan ; CUDA recharge à chaud lors d'un changement de mtime. La reconstruction prend quelques secondes ; les phases doivent durer assez longtemps pour que le surcoût de reconstruction reste faible. 42 étapes à la vitesse d'entraînement d'ANDREA-120M dépassent confortablement le temps de reconstruction.
Raisonnement sur le plafond
À venir
Ce que vous avez
Le contrôle des dés par phases enveloppe UCB1 dans trois règles protectrices : longueur de phase variable (7-42), bras aléatoires en premier, phases aléatoires pilotées par les dés (25-33 % purement aléatoires). Le plafond de 42 étapes limite les dégâts ; les phases aléatoires empêchent le verrouillage ; les longueurs variables mélangent la vitesse de réaction et la stabilité des estimations.
Ce qui reste
D'où provient le signal de récompense qui alimente UCB ? L'Activité 78 (attribution de la récompense) montre comment CUDA rapporte la perte par source à chaque étape, comment une EMA par source suit la récompense, et pourquoi ANDREA multiplie les récompenses brutes par 1000 avant de les transmettre à UCB1.
Les planchers et les pénalités d'époque (activité 79) ajoutent des règles de protection supplémentaires à la sortie du bandit, garantissant que les sources minuscules ne soient pas affamées et que les sources importantes ne soient pas répétées jusqu'à la mémorisation.
Référence
Whitepaper ANDREA, section 3.2.