#bandit-manchot — Apprentissage par renforcement

Bandit manchot : explorer ou exploiter ?

Ce que tu vas manipuler

Bienvenue dans #bandit-manchot. À l'écran, cinq machines à sous alignées. Chacune cache une probabilité de gain différente — un chiffre que personne ne te donnera. Au-dessus de chaque machine, une barre bleue : ton estimation Q(a) de sa moyenne (toutes à zéro, tu n'as encore rien tiré) ; une barre fine indigo : ton incertitude. Sous chaque machine, une pile de jetons comptera tes tirages ; à droite, deux courbes suivront ta récompense cumulée (bleu) et ton regret cumulé (rose). Le dilemme : chaque tirage sur une machine que tu connais est un tirage de moins pour découvrir si une autre paie mieux. Exploiter ce qu'on sait ou explorer ce qu'on ignore — c'est le problème du bandit manchot, celui d'un test A/B, d'un moteur de recommandation ou du choix d'un restaurant le soir.
Tire dix fois avec la stratégie par défaut, la gloutonne : /tirer 10. Elle joue toujours la machine au Q le plus élevé (au hasard en cas d'égalité). Regarde les billes tomber : verte, la machine a payé ; rouge, rien.
Vérifions. Dévoile les vraies probabilités : /reveler. Une barre grise apparaît derrière chaque barre bleue — la vraie moyenne de la machine — et le meilleur bras est marqué en vert.
Ajoutons un peu de hasard : /strategie epsilon. Avec l'ε-gloutonne, un tirage sur dix (ε = 0,10) part sur une machine tirée au sort ; les neuf autres exploitent la meilleure estimation du moment.
Lance une longue série : /jouer 500. Cinq cents tirages d'un coup ; les barres glissent vers leurs nouvelles valeurs et les courbes se tracent.
Passe à une stratégie plus fine : /strategie ucb. UCB (borne de confiance supérieure) joue la machine dont Q(a) + c·√(ln t / N(a)) est le plus grand : l'estimation plus un bonus d'incertitude, qui fond à mesure qu'on tire la machine.
Rejoue cinq cents tirages, cette fois avec UCB : /jouer 500.
Fais le bilan : /regret. La réponse donne le regret cumulé, la machine optimale et ce que chaque machine t'a coûté ; la scène l'écrit en rose sur chaque machine.
À toi de jouer : /strategie thompson puis /jouer 2000 (échantillonnage bayésien : souvent le meilleur regret de tous), /bras 10 pour dix machines (l'exploration coûte plus cher), /epsilon 0.3 ou /c 0.5 pour régler l'appétit d'exploration, /graine 42 pour d'autres machines, /reveler pour cacher à nouveau les vraies moyennes, /reinit pour repartir. Prochaine étape : #q-learning, où l'agent doit en plus tenir compte de l'état dans lequel il se trouve — le bandit devient un problème de décision séquentielle.

Commandes du canal

/bras <2..10> — Nombre de machines ; nouvelles moyennes cachées, compteurs à zéro.
/strategie <glouton|epsilon|ucb|thompson> — Façon de choisir la machine à chaque tirage ; Q et N sont conservés.
/epsilon <0..1> — Taux d'exploration ε de la stratégie ε-gloutonne.
/c <0..3> — Bonus d'exploration c d'UCB : Q(a) + c·√(ln t / N(a)).
/tirer <1..50> — Quelques tirages, rejoués un à un à l'écran (bille verte = gain, rouge = rien).
/jouer <100..2000> — Simulation longue : joue n tirages d'un coup et trace les courbes.
/reveler — Affiche ou masque les vraies moyennes (barres grises) et le meilleur bras.
/regret — Bilan : regret cumulé, machine optimale et part de chaque machine (affichée ou masquée sur la scène).
/graine <1..9999> — Change les moyennes cachées et les tirages ; compteurs à zéro.
/reinit — Revient à cinq machines, stratégie gloutonne, ε = 0,10, c = 1, moyennes cachées.

Glossaire

bandit manchot: Problème où l'on choisit, à répétition, l'une de k machines à sous (« bras ») aux gains moyens inconnus, en n'observant que le gain du bras joué. Modèle du test A/B, de la recommandation ou de l'allocation d'essais cliniques : apprendre en agissant, sans jamais voir « ce qu'aurait donné » l'autre choix.
exploration et exploitation: Le dilemme central : exploiter, c'est jouer le bras qu'on croit le meilleur pour engranger ; explorer, c'est en essayer un autre pour vérifier qu'on ne se trompe pas. Trop exploiter fige sur une erreur ; trop explorer gaspille. Toutes les stratégies de bandit sont des façons de doser ce compromis.
stratégie gloutonne: Joue toujours le bras au Q(a) estimé le plus grand. Sans exploration, elle se fige sur le premier bras qui a payé : son Q reste positif alors que les bras jamais essayés restent à zéro. Regret linéaire dans le pire cas — la « leçon négative » du bandit.
ε-glouton: Avec probabilité ε, un bras au hasard ; sinon le meilleur Q. Corrige le défaut de la gloutonne, mais ε fixe implique une part constante de tirages gaspillés : regret linéaire, de pente ≈ ε × écart moyen. On peut faire décroître ε avec le temps pour obtenir un regret sous-linéaire.
UCB (borne de confiance supérieure): Joue le bras qui maximise Q(a) + c·√(ln t / N(a)) : l'estimation plus un bonus d'incertitude, grand pour un bras peu tiré et qui fond avec N(a). Principe de l'optimisme face à l'incertitude. UCB1 (Auer, 2002) garantit un regret en O(ln t), l'ordre optimal.
échantillonnage de Thompson: Approche bayésienne : chaque bras a une loi de croyance sur sa moyenne — pour des gains 0/1, une Beta(1 + gains, 1 + échecs). À chaque tour on tire une valeur dans chaque loi et on joue le bras au tirage le plus grand : un bras est donc choisi avec la probabilité qu'il soit le meilleur. Simple, sans paramètre, souvent le plus efficace en pratique.
regret: Ce qu'on a perdu par rapport à un joueur qui connaîtrait le meilleur bras : L(t) = Σ (μ* − μ_{a_s}) sur les t tirages. Une stratégie est bonne si son regret est sous-linéaire (il croît moins vite que t) : la proportion de tirages gaspillés tend vers zéro. Il ne se calcule qu'en connaissant les vraies moyennes — en pratique on le borne, on ne le mesure pas.
valeur d'action Q(a): Estimation du gain moyen du bras a : la moyenne des gains observés, mise à jour par Q ← Q + (r − Q) / N(a) après chaque tirage (moyenne incrémentale). C'est la même quantité que le Q(s, a) du Q-learning, sans l'état s : le bandit est un problème de renforcement à un seul état.
récompense stochastique: Le gain d'un bras est aléatoire : ici 1 avec probabilité μ_a, 0 sinon (loi de Bernoulli). Un seul tirage ne dit presque rien sur μ_a ; il faut N tirages pour l'estimer à ≈ 1/√N près — c'est cette incertitude que les barres fines représentent et que l'exploration doit réduire.
bandit contextuel: Variante où l'on observe un contexte (profil de l'utilisateur, heure, page) avant de choisir le bras, et où le gain moyen dépend de ce contexte. C'est le modèle des moteurs de recommandation et des publicités en ligne ; un pas de plus, avec un état qui évolue selon les actions, et l'on arrive à l'apprentissage par renforcement complet.

Autres canaux du thème Apprentissage par renforcement

#bandit-manchot — Bandit manchot : explorer ou exploiter ?
#q-learning — Q-learning : apprendre un chemin par essais et erreurs.