DecInfer-10-Thompson-Sampling : Bandits bayesiens par Infer.NET

Serie : Programmation Probabiliste avec Infer.NET (10/10) Duree estimee : 60 minutes Prerequis : Infer-7-Skills-IRT (posterior Beta), DecInfer-08-Sequential (bandits, epsilon-greedy, UCB1)

Objectifs

Modeliser un bandit multi-bras comme un programme probabiliste Infer.NET
Faire calculer au moteur d’inference le posterior Beta-Bernoulli de chaque bras (inference variationnelle / EP), plutot que d’appliquer la formule conjuguee a la main
Implementer le Thompson Sampling : jouer le bras dont l’echantillon posterior est le plus eleve
Mesurer le regret cumule face a epsilon-greedy et UCB1 (Prong-B : Thompson exploite l’incertitude posterior)
Etendre au best-arm identification : estimer P(bras i est le meilleur) par echantillonnage posterior

Navigation

Précédent	Suivant
DecInfer-08-Sequential	Infer-5-Causal-Inference

Pont inter-series : le traitement des bandits en DecInfer-08 section 8 implemente epsilon-greedy, UCB1 et un exercice de Thompson manuel (comptage des succes/echecs, formule conjuguee codee a la main). Ce notebook en est le versant moteur : Infer.NET calcule le posterior Beta de chaque bras par inference variationnelle, et Thompson echantillonne depuis ce posterior.

1. Exploration vs exploitation — pourquoi Thompson ?

Un bandit multi-bras (Robbins, 1952) : K bras, chacun d’une recompense Bernoulli de moyenne inconnue theta_k. A chaque pas de temps on choisit un bras, on percoit une recompense 0/1, et on cherche a maximiser la recompense cumulee. Le dilemme :

Exploiter : jouer le bras qui semble le meilleur jusqu’ici.
Explorer : tester un bras peu joue pour estimer sa moyenne.

Trois familles de politiques :

Politique	Stratégie d’exploration
epsilon-greedy	Avec proba epsilon, jouer un bras au hasard (exploration uniforme)
UCB1 (Auer et al., 2002)	Jouer le bras maximisant moyenne + bonus d’incertitude `sqrt(2 ln t / n_k)`
Thompson Sampling (Thompson, 1933)	Maintenir un posterior sur chaque theta_k ; echantillonner theta_k dans son posterior ; jouer le max

L’idee de Thompson est subtilement bayesienne : au lieu d’explorer au hasard (epsilon-greedy) ou via un bonus frequentiste (UCB1), on quantifie l’incertitude sur chaque bras par une distribution posterior, et on joue proportionnellement a la probabilite que chaque bras soit le meilleur. Les bras peu explores ont un posterior large (incertain) : l’echantillonnage les fait parfois gagner, ce qui declenche une exploration ciblee la ou l’information manque.

La valeur ajoutee Infer.NET (non-doublon avec DecInfer-08)

Pour un bras Bernoulli de prior Beta(a, b), le posterior après s succes et f echecs est conjugue : Beta(a+s, b+f). On pourrait le coder a la main (c’est l’exercice DecInfer-08 section 8). Ce notebook ne le fait pas : on declare le modèle theta ~ Beta ; reward ~ Bernoulli(theta) et on laisse Infer.NET inferer le posterior. Pour ce cas conjugue le moteur recouvre exactement la forme analytique — mais la même approche se generalise a des modèles non conjugues ou la formule fermee n’existe pas, la ou seul un moteur d’inference (EP, VMP) sait faire.

2. Configuration d’Infer.NET

Chargement du moteur d’inference probabiliste (même #r "nuget" que toute la serie).

#r "nuget: Microsoft.ML.Probabilistic"
#r "nuget: Microsoft.ML.Probabilistic.Compiler"
using Microsoft.ML.Probabilistic;
using Microsoft.ML.Probabilistic.Distributions;
using Microsoft.ML.Probabilistic.Models;
using Microsoft.ML.Probabilistic.Algorithms;
using Microsoft.ML.Probabilistic.Compiler;
Console.WriteLine("Infer.NET charge.");

Installed Packages

Microsoft.ML.Probabilistic, 0.4.2504.701
Microsoft.ML.Probabilistic.Compiler, 0.4.2504.701

Infer.NET charge.

Chargement du helper de visualisation des graphes de facteurs (Graphviz).

#load "../../Infer/FactorGraphHelper.cs"
Console.WriteLine("FactorGraphHelper charge.");
Console.WriteLine($"Graphviz disponible : {FactorGraphHelper.IsGraphvizAvailable()}");

FactorGraphHelper charge.
Graphviz disponible : True

3. Le modèle Beta-Bernoulli d’un bras

Soit un bras de probabilite de succes inconnue theta. Modèle :

Prior : theta ~ Beta(1, 1) (uniforme sur [0,1] — ignorance totale).
Vraisemblance : reward_i ~ Bernoulli(theta) pour chaque tirage observe.

Après avoir observe s succes et f echecs, on demande au moteur d’inference le posterior sur theta. Verifions qu’Infer.NET recouvre la forme conjuguee Beta(1+s, 1+f) (le moteur fait le calcul, nous declarons seulement le modèle).

// Modele Beta-Bernoulli d un bras : theta ~ Beta(1,1), rewards ~ Bernoulli(theta)
// On observe s succes + f echecs, le moteur infere le posterior.
int succ = 7, fail = 3;
var theta1 = Variable.Beta(1.0, 1.0).Named("theta1");
Range r1 = new Range(succ + fail).Named("r1");
var trial1 = Variable.Array<bool>(r1).Named("trial1");
using (Variable.ForEach(r1)) { trial1[r1] = Variable.Bernoulli(theta1); }
bool[] obs1 = Enumerable.Range(0, succ).Select(_ => true)
    .Concat(Enumerable.Range(0, fail).Select(_ => false)).ToArray();
trial1.ObservedValue = obs1;
var eng1 = new InferenceEngine();
eng1.Compiler.CompilerChoice = CompilerChoice.Roslyn;
eng1.ShowProgress = false;
Beta post1 = eng1.Infer<Beta>(theta1);
double theoMean = (double)(1 + succ) / (2 + succ + fail);
Console.WriteLine($"Apres {succ} succes / {fail} echecs :");
Console.WriteLine($"  Posterior Infer.NET = Beta({post1.TrueCount:F1}, {post1.FalseCount:F1}) ; mean = {post1.GetMean():F3}");
Console.WriteLine($"  Formule conjuguee   = Beta({1+succ}, {1+fail}) ; mean = {theoMean:F3}");
Console.WriteLine($"  => Le moteur recouvre la forme analytique (cas conjugue favorable).");

Apres 7 succes / 3 echecs :
  Posterior Infer.NET = Beta(8,0, 4,0) ; mean = 0,667
  Formule conjuguee   = Beta(8, 4) ; mean = 0,667
  => Le moteur recouvre la forme analytique (cas conjugue favorable).

3.1 Graphe de facteurs du bras (Prong-A)

Le même modèle, rendu en graphe de facteurs par Graphviz via le FactorGraphHelper (pattern de la serie, cf DecInfer-03, DecInfer-04). Le noeud theta (Beta) alimente les facteurs Bernoulli des observations.

// Rendu SVG reel du graphe de facteurs du Beta-Bernoulli (Graphviz)
var thetaFG = Variable.Beta(1.0, 1.0).Named("theta");
Range rFG = new Range(6).Named("tirages");
var trialFG = Variable.Array<bool>(rFG).Named("recompenses");
using (Variable.ForEach(rFG)) { trialFG[rFG] = Variable.Bernoulli(thetaFG); }
var engFG = new InferenceEngine();
engFG.Compiler.CompilerChoice = CompilerChoice.Roslyn;
engFG.ShowProgress = false;
engFG.ShowFactorGraph = true;
var _fg = engFG.Infer<Beta>(thetaFG);
Console.WriteLine("Modele Beta-Bernoulli : theta (Beta) -> 6 facteurs Bernoulli (un par tirage observe).");
FactorGraphHelper.GetLatestFactorGraphHtml().DisplayAs("text/html");

Modele Beta-Bernoulli : theta (Beta) -> 6 facteurs Bernoulli (un par tirage observe).

Model_09_23_26_09_20_24_20.svg

3.2 Convergence du posterior

A mesure que les observations s’accumulent, le posterior se concentre autour de la vraie moyenne. Le moteur recalcule le posterior a chaque lot d’observations.

// Convergence : on observe des lots croissants, le moteur recalcule le posterior a chaque fois.
double vraiTheta = 0.7;  // vraie moyenne inconnue du bras
var rngConv = new System.Random(42);
Console.WriteLine($"Vraie moyenne du bras = {vraiTheta:F2} (inconnue de l algorithme)");
Console.WriteLine("  N tirages | posterior mean | ic 95% (approx)");
Console.WriteLine("  ------------------------------------------");
foreach (int N in new[] { 5, 20, 50, 200 }) {
    bool[] data = new bool[N];
    int s = 0;
    for (int j = 0; j < N; j++) { data[j] = rngConv.NextDouble() < vraiTheta; if (data[j]) s++; }
    var thC = Variable.Beta(1.0, 1.0);
    Range rC = new Range(N);
    var trC = Variable.Array<bool>(rC);
    using (Variable.ForEach(rC)) { trC[rC] = Variable.Bernoulli(thC); }
    trC.ObservedValue = data;
    var eC = new InferenceEngine(); eC.Compiler.CompilerChoice = CompilerChoice.Roslyn; eC.ShowProgress = false;
    Beta pC = eC.Infer<Beta>(thC);
    double mean = pC.GetMean();
    double aV = 1 + s, bV = 1 + (N - s);  // posterior Beta(1+s, 1+f)
    double sd = System.Math.Sqrt((aV*bV) / ((aV+bV)*(aV+bV)*(aV+bV+1.0)));
    double lo = System.Math.Max(0, mean - 1.96*sd);
    double hi = System.Math.Min(1, mean + 1.96*sd);
    Console.WriteLine($"  {N,9} | {mean:F3}          | [{lo:F3}, {hi:F3}]");
}
Console.WriteLine("  => Le posterior se resserre autour de la vraie moyenne quand N croit.");

Vraie moyenne du bras = 0,70 (inconnue de l algorithme)
  N tirages | posterior mean | ic 95% (approx)
  ------------------------------------------
          5 | 0,857          | [0,615, 1,000]
         20 | 0,727          | [0,545, 0,909]
         50 | 0,769          | [0,656, 0,883]
        200 | 0,663          | [0,598, 0,728]
  => Le posterior se resserre autour de la vraie moyenne quand N croit.

Lecture du résultat : le posterior se resserre au rythme des données

À N=5 tirages, le posterior est encore optimiste — moyenne 0,857 pour une vraie moyenne de 0,70 — et son intervalle à 95 % monte jusqu’à 1,000 : cinq observations favorables n’ont encore rien exclu. À N=200, la moyenne descend à 0,663 et l’intervalle [0,598, 0,728] contient la vraie valeur 0,70 : le moteur a digéré les données contradictoires.

Deux points à retenir pour la suite :

la largeur de l’intervalle passe de 0,385 (N=5) à 0,130 (N=200) : multiplier les données par 40 ne divise l’incertitude que par ~3 — les premières observations achètent beaucoup plus d’information que les suivantes, et le coût d’apprentissage marginal décroît vite ;
l’incertitude reste quantifiée à chaque instant. Thompson Sampling (section 5) ne tirera pas parti du seul point estimé 0,663 mais de la distribution entière : c’est parce que l’intervalle est explicite que l’algorithme saura où il manque d’information.

4. Reutiliser le moteur compile (problematique runtime)

Un bandit reel rejoue des centaines de fois, et le posterior de chaque bras evolue a chaque recompense. Si l’on reconstruisait le modèle a chaque pas, Infer.NET recompilerait a chaque fois (plusieurs centaines de ms par compilation, cf. mesure §4.1 cellule suivante). La solution : un modèle a taille fixe MAX ou un masque mask[i] dit quelles cases de obs[i] sont de vraies observations. On compile une fois, puis on met seulement a jour ObservedValue des tableaux : Infer.NET reutilise le code compile (sub-milliseconde par re-inference sur modele pre-compile, cf. mesure §4.1 – soit plusieurs ordres de grandeur de moins qu’une compilation).

On encapsule ce pattern dans une classe BayesArm : un bras dont Infer.NET calcule le posterior.

// Helper BayesArm : un bras de bandit dont Infer.NET calcule le posterior Beta.
// Modele a taille MAX fixe + masque (reutilise la compilation du moteur).
public class BayesArm {
    private Variable<double> theta;
    private VariableArray<bool> obs, mask;
    private InferenceEngine engine;
    private int maxN;
    public int Succ { get; private set; }
    public int Fail { get; private set; }
    public BayesArm(int maxN, double priorA = 1.0, double priorB = 1.0) {
        this.maxN = maxN;
        theta = Variable.Beta(priorA, priorB).Named("theta");
        Range n = new Range(maxN).Named("n");
        obs  = Variable.Array<bool>(n).Named("obs");
        mask = Variable.Array<bool>(n).Named("mask");
        using (Variable.ForEach(n)) {
            using (Variable.If(mask[n])) { obs[n] = Variable.Bernoulli(theta); }
        }
        engine = new InferenceEngine();
        engine.Compiler.CompilerChoice = CompilerChoice.Roslyn;
        engine.ShowProgress = false;  // supprime le bruit Compiling model...
        // warmup : compile le modele une fois (mask vide -> prior)
        obs.ObservedValue  = new bool[maxN];
        mask.ObservedValue = new bool[maxN];
        var _ = engine.Infer<Beta>(theta);
        Succ = 0; Fail = 0;
    }
    public void Reset() {
        Succ = 0; Fail = 0;
        obs.ObservedValue  = new bool[maxN];
        mask.ObservedValue = new bool[maxN];
    }
    public void Observe(bool success) {
        if (success) Succ++; else Fail++;
        var d = new bool[maxN];
        var m = new bool[maxN];
        for (int j = 0; j < Succ; j++)        { d[j] = true;  m[j] = true; }
        for (int j = Succ; j < Succ + Fail; j++){ d[j] = false; m[j] = true; }
        obs.ObservedValue  = d;
        mask.ObservedValue = m;
    }
    public Beta Posterior() => engine.Infer<Beta>(theta);
    public double Sample()  => engine.Infer<Beta>(theta).Sample();
    public double Mean()    => engine.Infer<Beta>(theta).GetMean();
}
Console.WriteLine("Classe BayesArm definie (modele masque, moteur reutilise).");

Classe BayesArm definie (modele masque, moteur reutilise).

4.1 Mesure du gain de runtime : compilation vs re-inference

La classe BayesArm est concue pour compiler le moteur une fois (warmup dans le constructeur), puis reutiliser ce code compile a chaque Observe/Posterior. Mesurons concretement les deux regimes pour confirmer l’ordre de grandeur annonce : la compilation est l’operation couteuse (~centaines de ms), la re-inference sur un modele pre-compile est sub-milliseconde.

// Mesure runtime : compilation (1 fois) vs re-inference (compile reutilise).
var swMes = System.Diagnostics.Stopwatch.StartNew();
var armMes = new BayesArm(maxN: 220);   // constructeur = warmup compilation du moteur
swMes.Stop();
double tCompile = swMes.Elapsed.TotalMilliseconds;

var rngMes = new System.Random(42);
swMes.Restart();
int NMes = 200;
for (int i = 0; i < NMes; i++) {
    armMes.Observe(rngMes.NextDouble() < 0.5);   // ajoute une observation (masque + ObservedValue)
    var _post = armMes.Posterior();               // re-inference : compile reutilise
}
swMes.Stop();
double tReinfer = swMes.Elapsed.TotalMilliseconds / NMes;

Console.WriteLine($"Compilation (1 fois, warmup BayesArm)        : {tCompile:F1} ms");
Console.WriteLine($"Re-inference (ObservedValue, compile reutilise) : {tReinfer:F3} ms en moyenne sur {NMes} appels");
Console.WriteLine($"Ratio compilation / re-inference              : {tCompile/tReinfer:F0}x");

Compilation (1 fois, warmup BayesArm)        : 350,5 ms
Re-inference (ObservedValue, compile reutilise) : 0,044 ms en moyenne sur 200 appels
Ratio compilation / re-inference              : 7953x

Lecture du résultat : pourquoi le moteur compilé change tout

Note méthodologique — séparation structurel / machine-dep : le rapport entre le coût d’une compilation et celui d’une re-inférence sur modèle déjà compilé est un invariant structurel d’Infer.NET (plusieurs ordres de grandeur : de l’ordre de 10⁴× dans la mesure du §4.1 ci-dessus). En revanche, les durées absolues (compilation en centaines de ms, re-inférence en centièmes de ms) sont machine-dépendantes par construction (CPU, JIT, GC, version Infer.NET) et ne survivent pas à une ré-exécution sur une autre machine — c’est précisément la pathologie que l’umbrella #9434/#8052/#9377 demande de drainer plutôt que de re-épingler. La cellule de calcul §4.1 (juste au-dessus) reste intacte et exécutable localement : l’étudiant peut y observer ses propres timings sur sa machine et vérifier que le rapport (structurel) garde son ordre de grandeur même quand les valeurs absolues changent. Le rapport lui-même fluctue d’une exécution à l’autre, puisque ses deux termes sont des durées : un seuil exact comme « >10000× » ne se lirait donc pas de façon stable, seul l’ordre de grandeur le fait.

Infer.NET suit le modèle « compiler une fois, inférer souvent » : la première inférence génère du code spécialisé pour le graphe de facteurs, les suivantes se contentent d’observer de nouvelles données et de relancer l’inférence sur ce code déjà compilé. C’est la différence structurelle entre un moteur probabiliste compilé et un échantillonneur générique qui repartirait de zéro à chaque question.

5. Thompson Sampling multi-bras

Trois bras de vraies moyennes theta* = [0,2 ; 0,5 ; 0,8] (inconnues de l’algorithme). A chaque pas de temps :

Pour chaque bras, Infer.NET infere le posterior Beta.
On echantillonne theta_k ~ posterior_k (Thompson : “jouer selon la probabilite que chaque bras soit le meilleur”).
On joue le bras d’echantillon maximum.
On observe la recompense (Bernoulli(theta*)) et on met a jour le posterior du bras joue.

// Thompson Sampling multi-bras : K=3 bras, T=200 pas.
// theta* inconnu ; Infer.NET calcule chaque posterior ; on echantillonne puis on joue argmax.
int K = 3;
int T = 200;
int MAXN = 220;
double[] vraiTheta = { 0.2, 0.5, 0.8 };
var banditRng = new System.Random(7);
Microsoft.ML.Probabilistic.Math.Rand.Restart(7); // Beta.Sample() tire dans Rand, le générateur global d'Infer.NET, pas dans System.Random
var arms = new BayesArm[K];
for (int k = 0; k < K; k++) arms[k] = new BayesArm(MAXN);
int[] tiragesParBras = new int[K];
int totalRecompense = 0;
Console.WriteLine($"Bandit : K={K} bras, T={T} pas. (theta* inconnu de l algorithme)");
Console.WriteLine("  pas | bras joue | recompense | posterior means [b1 b2 b3]");
Console.WriteLine("  ---------------------------------------------------------------");
for (int t = 0; t < T; t++) {
    // 1+2. Infer posterior + sample pour chaque bras (le moteur calcule le posterior)
    double[] echant = new double[K];
    for (int k = 0; k < K; k++) echant[k] = arms[k].Sample();
    // 3. jouer argmax des echantillons
    int choisi = 0;
    for (int k = 1; k < K; k++) if (echant[k] > echant[choisi]) choisi = k;
    // 4. observer la recompense (Bernoulli(theta*)) et mettre a jour le posterior
    bool recompense = banditRng.NextDouble() < vraiTheta[choisi];
    arms[choisi].Observe(recompense);
    tiragesParBras[choisi]++;
    if (recompense) totalRecompense++;
    if (t < 5 || t == 50 || t == 100 || t == T - 1) {
        double m0 = arms[0].Mean(), m1 = arms[1].Mean(), m2 = arms[2].Mean();
        Console.WriteLine($"  {t+1,3} |    bras {choisi+1}    |     {(recompense?1:0)}      | [{m0:F2} {m1:F2} {m2:F2}]");
    }
}
Console.WriteLine("  ---------------------------------------------------------------");
Console.WriteLine($"Tirages par bras : [{tiragesParBras[0]}, {tiragesParBras[1]}, {tiragesParBras[2]}]");
Console.WriteLine($"Recompense totale = {totalRecompense}/{T} (optimal ~ {T*0.8:F0})");
Console.WriteLine($"=> Thompson converge vers le bras 3 (le meilleur, theta*=0.8).");

Bandit : K=3 bras, T=200 pas. (theta* inconnu de l algorithme)
  pas | bras joue | recompense | posterior means [b1 b2 b3]
  ---------------------------------------------------------------
    1 |    bras 3    |     1      | [0,50 0,50 0,67]
    2 |    bras 2    |     0      | [0,50 0,33 0,67]
    3 |    bras 3    |     1      | [0,50 0,33 0,75]
    4 |    bras 3    |     1      | [0,50 0,33 0,80]
    5 |    bras 3    |     1      | [0,50 0,33 0,83]
   51 |    bras 1    |     0      | [0,33 0,43 0,70]
  101 |    bras 3    |     1      | [0,33 0,33 0,75]
  200 |    bras 3    |     0      | [0,33 0,33 0,77]
  ---------------------------------------------------------------
Tirages par bras : [4, 7, 189]
Recompense totale = 150/200 (optimal ~ 160)
=> Thompson converge vers le bras 3 (le meilleur, theta*=0.8).

Lecture du résultat : la trace d’un run de Thompson

La sortie raconte l’algorithme pas à pas (les moyennes affichées sont celles des posteriors après la mise à jour du pas) :

Pas 1 : les trois bras partent du même prior uniforme Beta(1,1). L’échantillon du bras 3 sort le plus haut, par pur hasard, et le bras 3 paie : sa moyenne posterior passe de 0,50 à 0,67.
Pas 2 : le bras 2 est sondé à son tour et échoue (moyenne 0,33). C’est l’exploration par échantillonnage : un posterior encore large peut produire un échantillon élevé, et l’algorithme va vérifier.
Pas 3 à 5 : le bras 3 est rejoué trois fois et paie trois fois (0,75, 0,80 puis 0,83). L’exploitation s’installe après cinq récompenses seulement.
Pas 51 et 101 : l’exploration n’est jamais coupée. Au pas 51, le bras 1 est encore essayé (échec, moyenne 0,33). Un posterior reste une distribution : un échantillon élevé peut toujours faire revenir un bras délaissé.
Pas 200 : le bras 3 a capté 189 tirages sur 200, contre 4 pour le bras 1 et 7 pour le bras 2. Sa moyenne posterior (0,77) approche la vraie valeur 0,80. Celles des deux perdants restent toutes deux à 0,33, loin de leurs vraies moyennes (0,20 et 0,50) : Thompson ne cherche pas à bien les estimer, seulement à établir qu’ils ne sont pas les meilleurs.

Bilan du run : 150 récompenses sur 200, contre ~160 pour l’oracle qui connaîtrait les vraies moyennes — un regret de run d’environ 10. Toute la compétition exploration/exploitation tient dans cet écart.

6. Comparaison du regret cumule (Prong-B)

Le regret mesure ce qu’on perd par rapport a jouer le bras optimal des le debut : regret(t) = theta*_max - theta*(bras joue). On cumule sur T pas. On compare trois politiques, moyennées sur N_runs repetitions (graines différentes) :

epsilon-greedy (epsilon=0.1) : exploration uniforme aleatoire.
UCB1 (Auer et al., 2002) : bonus d’incertitude frequentiste.
Thompson (via Infer.NET) : exploration bayesienne par echantillonnage posterior.

Hypothese (Prong-B) : Thompson exploite l’incertitude posterior — il explore la ou l’information manque, pas au hasard — d’ou un regret cumule inferieur a epsilon-greedy.

// Comparaison regret cumule : epsilon-greedy vs UCB1 vs Thompson (Infer.NET), moyennes sur N_runs.
// eps-greedy et UCB1 sont des calculs purs (pas de moteur) ; Thompson appelle Infer.NET.
// Compteurs SEPARES par politique (chaque politique apprend de ses propres tirages).
int N_runs = 15;
int T2 = 200;
double eps = 0.1;
double[] vrai2 = { 0.2, 0.5, 0.8 };
int K2 = vrai2.Length;
int MAXN2 = T2 + 10;
double thetaMax = vrai2.Max();
// politique : 0=eps-greedy, 1=UCB1, 2=Thompson
// moyennes du regret a T2 (valeur finale moyennee sur les runs)
double[] regretFinal = new double[3];
for (int run = 0; run < N_runs; run++) {
    var rng = new System.Random(100 + run);
    Microsoft.ML.Probabilistic.Math.Rand.Restart(100 + run);
    int[] compteEG = new int[K2]; double[] recEG = new double[K2];
    int[] compteUCB = new int[K2]; double[] recUCB = new double[K2];
    // Thompson : 3 BayesArm partages entre runs (reset entre runs, compilation reutilisee)
    var thArms = new BayesArm[K2];
    for (int k = 0; k < K2; k++) { thArms[k] = new BayesArm(MAXN2); }
    double[] regret = new double[3];
    for (int t = 0; t < T2; t++) {
        // --- epsilon-greedy ---
        int aEG;
        if (t < K2 || rng.NextDouble() < eps) { aEG = rng.Next(K2); }
        else { aEG = 0; for (int k=1;k<K2;k++) { double mk = recEG[k]/System.Math.Max(1,compteEG[k]); double mb = recEG[aEG]/System.Math.Max(1,compteEG[aEG]); if (mk > mb) aEG = k; } }
        bool rEG = rng.NextDouble() < vrai2[aEG];
        compteEG[aEG]++; if (rEG) recEG[aEG]++;
        regret[0] += thetaMax - vrai2[aEG];
        // --- UCB1 ---
        int aUCB = -1;
        for (int k=0;k<K2;k++) if (compteUCB[k]==0) { aUCB = k; break; }  // init : chaque bras une fois
        if (aUCB < 0) {
            aUCB = 0; double bestUCB = double.MinValue;
            for (int k=0;k<K2;k++) {
                double mean = recUCB[k]/System.Math.Max(1,compteUCB[k]);
                double bonus = System.Math.Sqrt(2.0*System.Math.Log(t+1)/System.Math.Max(1,compteUCB[k]));
                if (mean+bonus > bestUCB) { bestUCB = mean+bonus; aUCB = k; }
            }
        }
        bool rUCB = rng.NextDouble() < vrai2[aUCB];
        compteUCB[aUCB]++; if (rUCB) recUCB[aUCB]++;
        regret[1] += thetaMax - vrai2[aUCB];
        // --- Thompson (Infer.NET) ---
        double[] ech = new double[K2];
        for (int k=0;k<K2;k++) ech[k] = thArms[k].Sample();
        int aTH = 0; for (int k=1;k<K2;k++) if (ech[k] > ech[aTH]) aTH = k;
        bool recTH = rng.NextDouble() < vrai2[aTH];
        thArms[aTH].Observe(recTH);
        regret[2] += thetaMax - vrai2[aTH];
    }
    for (int p=0;p<3;p++) regretFinal[p] += regret[p] / N_runs;
}
Console.WriteLine($"Regret cumule moyen sur {N_runs} runs (T={T2}) :");
Console.WriteLine($"  epsilon-greedy (eps={eps}) : {regretFinal[0]:F1}");
Console.WriteLine($"  UCB1                       : {regretFinal[1]:F1}");
Console.WriteLine($"  Thompson (Infer.NET)       : {regretFinal[2]:F1}");
Console.WriteLine();
Console.WriteLine($"=> Thompson ({regretFinal[2]:F1}) <= epsilon-greedy ({regretFinal[0]:F1}) : l exploration bayesienne");
Console.WriteLine($"   ciblee par le posterior exploite l incertitude la ou l information manque (Prong-B).");

Regret cumule moyen sur 15 runs (T=200) :
  epsilon-greedy (eps=0,1) : 17,5
  UCB1                       : 19,3
  Thompson (Infer.NET)       : 6,1

=> Thompson (6,1) <= epsilon-greedy (17,5) : l exploration bayesienne
   ciblee par le posterior exploite l incertitude la ou l information manque (Prong-B).

Lecture du résultat : Thompson domine les deux baselines

Sur 15 runs de T=200 pas, le regret cumulé moyen s’établit à 6,1 pour Thompson, contre 17,5 pour epsilon-greedy et 19,3 pour UCB1 — Thompson fait environ trois fois mieux que les deux baselines sur ce terrain.

Le pourquoi se lit dans la mécanique de chaque politique :

epsilon-greedy explore au hasard : ses 10 % de tirages aléatoires continuent de sonder le bras le plus mauvais même quand plus rien ne justifie de le tester — du regret payé pour aucune information nouvelle ;
UCB1 explore par bonus d’optimisme déterministe : efficace, mais son bonus est indexé sur un compteur de visites, pas sur une incertitude calibrée par les données observées ;
Thompson alloue l’exploration exactement là où le posterior est encore large — les bras sûrs d’eux-mêmes sont quasi toujours joués, les autres sondés juste ce qu’il faut.

Réserve honnête : 15 runs, c’est une moyenne courte (l’écart-type n’est pas affiché) — cette cellule est une illustration pédagogique du mécanisme, pas un benchmark statistique ; la section théorique ci-dessous donne le cadre du regret logarithmique.

6.1 Cadre theorique - pourquoi le regret de Thompson est-il logarithmique ?

La cellule precedente montre empiriquement que Thompson cumule moins de regret qu’epsilon-greedy, et se compare a UCB1. Ce n’est pas un effet du hasard : la theorie garantit que Thompson Sampling atteint le meilleur regret asymptotique possible pour un bandit stochastique.

Borne problem-dependent (logarithmique). Comme UCB1, Thompson atteint un regret qui ne croit que logarithmiquement avec l’horizon :

R(T) = O( sum_{k : Delta_k > 0} (ln T) / Delta_k )

ou Delta_k = mu* - mu_k est le gap du bras k par rapport a l’optimal mu* (Agrawal & Goyal, 2012 ; Kaufmann, Korda & Munos, 2012). Consequence concrete pour notre instance (mu = 0.2, 0.5, 0.8, donc Delta = 0.6, 0.3, 0) : le regret grandit comme ln T et non comme T - d’ou la courbe qui s’aplatit au lieu de monter lineairement.

Optimalite asymptotique (borne inferieure de Lai-Robbins). Plus fort encore : Thompson atteint asymptotiquement la borne inferieure de Lai & Robbins (1985), qui s’applique a toute politique coherent :

lim_{T -> inf} R(T) / ln T = sum_{k != k*} Delta_k / KL(mu_k || mu*)

ou KL est la divergence de Kullback-Leibler entre les lois des bras (Kaufmann, Korda & Munos, 2012). Aucune politique ne peut faire asymptotiquement mieux que cette constante : Thompson est donc optimal au sens de l’information - il tire de chaque sous-bras exactement le nombre de fois minimal pour lever l’incertitude, ni plus ni moins. C’est la formalisation mathematique de l’intuition Prong-B : l’echantillonnage posterior n’est pas une simple heuristique d’exploration, c’est la politique qui realise cette borne.

Borne problem-independent (gap-free). Quand les gaps sont inconnus ou petits, on dispose d’une garantie distribution-free R(T) = O( sqrt(K T ln T) ) (Agrawal & Goyal, 2013), du meme ordre que la borne minimax de UCB1.

Resultat	Regret	Source
Problem-dependent (log)	`O( sum_k (ln T)/Delta_k )`	Agrawal & Goyal 2012 ; Kaufmann et al. 2012
Asymptotiquement optimal	atteint la borne Lai-Robbins	Kaufmann et al. 2012 ; Lai & Robbins 1985
Gap-free (minimax-style)	`O( sqrt(K T ln T) )`	Agrawal & Goyal 2013

Hypothese de support du prior. Ces bornes supposent que le prior donne une masse positive a la vraie valeur mu* - verifie ici : le prior Beta(1,1) est uniforme sur [0,1], son support couvre tout mu* dans l’intervalle. Avec un prior trop peaked ailleurs (exercice 3, Beta(50,50) face a un mu* ~ 0.8), la convergence se degrade. Pour les modeles non conjugues que vise Infer.NET (bras Gaussiennes de variance inconnue, effets contextuels - section 8), l’optimalite asymptotique est preservee mais l’inference approchee EP/VMP ajoute une variance d’estimation : le moteur ne change pas la theorie, il rend calculable un posterior qu’on ne saurait pas ecrire en forme fermee.

References - Lai, T. L. & Robbins, H. (1985). Asymptotically efficient allocation rules. Advances in Applied Mathematics 6(1). - Agrawal, S. & Goyal, N. (2012). Analysis of Thompson Sampling for the multi-armed bandit problem. COLT 2012. - Kaufmann, E., Korda, N. & Munos, R. (2012). Thompson Sampling: an asymptotically optimal finite-time analysis. ALT 2012. - Agrawal, S. & Goyal, N. (2013). Further optimal regret bounds for Thompson Sampling. AISTATS 2013.

7. Extension — best-arm identification

Le regret mesure la performance (cumul de recompenses). Une autre question : identifier le meilleur bras avec une garantie probabiliste. Thompson fournit naturellement P(bras i est le meilleur) : on echantillonne plusieurs fois les posteriors simultanement et on compte la frequence a laquelle chaque bras gagne. Quand cette probabilite depasse un seuil (ex. 0,95), on peut declarer le gagnant.

// Best-arm identification : estimer P(bras i est le meilleur) par echantillonnage posterior.
// On reutilise les posteriors des 3 bras apres un echantillonnage Thompson court.
int KB = 3; int TB = 60; int MAXNB = 70;
double[] vraiB = { 0.2, 0.5, 0.8 };
var rngB = new System.Random(11);
Microsoft.ML.Probabilistic.Math.Rand.Restart(11);
var armB = new BayesArm[KB];
for (int k=0;k<KB;k++) armB[k] = new BayesArm(MAXNB);
// phase d apprentissage courte : Thompson TB pas
for (int t=0;t<TB;t++) {
    double[] e = new double[KB];
    for (int k=0;k<KB;k++) e[k] = armB[k].Sample();
    int a = 0; for (int k=1;k<KB;k++) if (e[k] > e[a]) a = k;
    armB[a].Observe(rngB.NextDouble() < vraiB[a]);
}
// estimation P(bras i est le meilleur) : N_samples tirages posterior simultanes
int N_samples = 2000;
int[] gagnants = new int[KB];
for (int s=0;s<N_samples;s++) {
    double mx = -1; int g = 0;
    for (int k=0;k<KB;k++) { double v = armB[k].Sample(); if (v > mx) { mx = v; g = k; } }
    gagnants[g]++;
}
Console.WriteLine($"Apres {TB} tirages Thompson, estimation P(bras i est le meilleur) sur {N_samples} echantillons :");
for (int k=0;k<KB;k++) {
    Beta p = armB[k].Posterior();
    Console.WriteLine($"  bras {k+1} : P(meilleur) = {gagnants[k]/(double)N_samples:F3}  | posterior Beta({p.TrueCount:F1},{p.FalseCount:F1}) mean={p.GetMean():F3} (vraie {vraiB[k]})");
}
int best = Array.IndexOf(gagnants, gagnants.Max());
Console.WriteLine($"=> Bras declare meilleur : bras {best+1} (theta*={vraiB[best]}).");
Console.WriteLine($"   Si P > 0.95, on peut arreter : identification du meilleur bras avec confiance.");

Apres 60 tirages Thompson, estimation P(bras i est le meilleur) sur 2000 echantillons :
  bras 1 : P(meilleur) = 0,011  | posterior Beta(1,0,3,0) mean=0,250 (vraie 0,2)
  bras 2 : P(meilleur) = 0,003  | posterior Beta(4,0,6,0) mean=0,400 (vraie 0,5)
  bras 3 : P(meilleur) = 0,986  | posterior Beta(42,0,10,0) mean=0,808 (vraie 0,8)
=> Bras declare meilleur : bras 3 (theta*=0,8).
   Si P > 0.95, on peut arreter : identification du meilleur bras avec confiance.

Lecture du résultat : une autre question, le même moteur

Après seulement 60 tirages Thompson, l’échantillonnage des posteriors donne P(bras 3 meilleur) = 0,986, contre 0,011 pour le bras 1 et 0,003 pour le bras 2 — la règle d’arrêt « P > 0,95 » est déjà franchie. Les posteriors racontent la même histoire en creux : Beta(42,0, 10,0) pour le bras 3 — 50 tirages, un posterior concentré, riche en données — contre Beta(1,0, 3,0) pour le bras 1, visité deux fois seulement, où le prior uniforme Beta(1,1) se devine encore dans les petits compteurs.

Un détail mérite l’attention : le bras 1, de moyenne posterior 0,25, reçoit une probabilité d’être le meilleur supérieure à celle du bras 2 (moyenne 0,40). Ce n’est pas une anomalie. Visité deux fois, le bras 1 garde un posterior large (écart-type 0,19), dont la queue atteint encore la zone du bras 3 ; observé huit fois, le bras 2 est plus resserré (0,15). Être le meilleur dépend de toute la distribution, pas seulement de sa moyenne. Ces deux petites probabilités restent des estimations bruitées sur 2000 échantillons ; la réponse sur le bras 3, elle, est nette.

La nuance conceptuelle mérite d’être soulignée : minimiser le regret (jouer bien maintenant) et identifier le meilleur bras (savoir avec confiance) sont deux objectifs distincts. Le premier tolère de continuer à jouer un bras presque optimal ; le second exige d’accumuler assez de preuves pour pouvoir arrêter. Thompson Sampling sert les deux avec la même machinerie bayésienne — seule change la question posée aux échantillons : « quel bras jouer ce pas ? » ou « quel bras est le meilleur, et à quel niveau de confiance ? ».

8. Limites honnetes

Cas conjugue favorable : pour un bandit Bernoulli, le posterior Beta est analytique. L’apport d’Infer.NET n’est pas la (le moteur recouvre la formule fermee) mais dans la generalisation a des modèles non conjugues (ex. bras Gaussiennes de variance inconnue, effets contextuels) ou seule l’inference approchee (EP/VMP) sait calculer le posterior.
Cout d’inference : chaque pas de Thompson requiert K inferences posteriors. Grace au modèle masque reutilise (sub-milliseconde/call, cf. mesure §4.1), cela reste negligeable pour K petit et T modere. Pour un grand K (centaines de bras) ou un modèle lourd, l’overhead devient un facteur — c’est la ou un posterior conjugue code a la main (cf DecInfer-08 section 8) garde sa place.
Non-stationnarite : si les vraies theta* changent au cours du temps, le posterior Beta s’accumule indefiniment et devient trop confident. Il faut alors introduire un facteur d’oubli (sliding window, discount) — voir exercice 2.

9. Exercices

Trois exercices pour aller plus loin. Chaque stub s’execute sans erreur ; completez le code entre les // TODO.

#	Exercice	Concept
1	Ajouter un 4e bras et observer la convergence	Thompson sur K=4
2	Bandit non-stationnaire (facteur d’oubli)	Adaptation au changement
3	Prior informatif Beta(50, 50)	Impact du prior sur l’exploration

Exercice 1 — Ajouter un 4e bras et observer la convergence

Thompson Sampling se generalise de 3 a K bras. Ajoutez un 4e bras de vraie moyenne 0,65 et relancez la boucle de sélection. Observez comment le choix bascule de bras en bras puis se stabilise sur le meilleur des 4.

Objectif. Etendre le modèle a 4 bras et verifier que Thompson identifie le meilleur.

Indices. - Etendez vraiTheta a 4 valeurs (par ex. [0.3, 0.5, 0.7, 0.65]). - Mettez K = 4 et construisez 4 BayesArm, comme en section 5. - Reportez les tirages par bras et la recompense totale cumulee.

// Exercice 1 : Ajouter un 4e bras de vraie moyenne 0.65 et relancer Thompson.
// Observez comment la selection bascule puis se stabilise sur le meilleur des 4.
// Indice : etendez vraiTheta a 4 valeurs, K=4, bouclez comme en section 5.
// Etape 1 : definir les 4 vraies moyennes
// Etape 2 : construire 4 BayesArm et boucler T pas
// Etape 3 : reporter les tirages par bras et la recompense totale
Console.WriteLine("Exercice 1 a completer : Thompson sur 4 bras (K=4).");

Exercice 1 a completer : Thompson sur 4 bras (K=4).

Exercice 2 — Bandit non-stationnaire (facteur d’oubli)

Jusqu’ici les vraies moyennes sont fixes. En pratique elles peuvent changer : ici la meilleure bascule a t = 100. Implantez un facteur d’oubli : a chaque pas, ne gardez qu’une fraction des observations passees afin que le posterior s’adapte au changement de regime.

Objectif. Ajouter l’oubli au posterior et comparer le regret avec et sans oubli.

Indices. - Modifiez BayesArm.Observe pour decaler/oublier les observations, ou ajoutez une méthode Forget(double gamma). - Definissez theta*(t) qui change a mi-parcours (ex. le bras 1 devient meilleur après t=100). - Comparez le regret avec et sans oubli sur la sequence non-stationnaire.

// Exercice 2 : Bandit non-stationnaire — la meilleure bascule a t=100.
// Implantez un facteur d oubli : a chaque pas, ne gardez qu une fraction des observations passees.
// Indice : modifiez BayesArm.Observe pour decaler/oublier, ou ajoutez une methode Forget(double gamma).
// Etape 1 : definir theta*(t) qui change a mi-parcours (ex. bras 1 devient meilleur apres t=100)
// Etape 2 : ajouter l oubli au posterior (reset partiel ou discount)
// Etape 3 : comparer le regret avec et sans oubli sur la sequence non-stationnaire
Console.WriteLine("Exercice 2 a completer : bandit non-stationnaire avec facteur d oubli.");

Exercice 2 a completer : bandit non-stationnaire avec facteur d oubli.

Exercice 3 — Prior informatif Beta(50, 50) vs uniforme

Un prior Beta(50, 50) exprime une forte conviction que theta vaut environ 0,5 ; un prior Beta(1, 1) est uniforme (sans information a priori). Comparez le regret des deux : un prior informatif reduit-il l’exploration prematuree ?

Objectif. Mesurer l’impact du prior sur la vitesse de convergence de Thompson.

Indices. - BayesArm accepte des paramètres priorA / priorB. - Créez deux jeux de bras — l’un avec Beta(1,1), l’autre avec Beta(50,50) — et mesurez le regret de chacun. - Interpretez : dans quels cas un prior informatif aide-t-il, et quand nuit-il ?

// Exercice 3 : Prior informatif Beta(50, 50) (confiant que theta~0.5) vs Beta(1,1) (uniforme).
// Comparez le regret : un prior informatif reduit-il l exploration prematuree ?
// Indice : BayesArm accepte priorA/priorB ; creez deux jeux de bras et mesurez le regret de chacun.
// Etape 1 : lancer Thompson avec prior Beta(1,1) (uniforme)
// Etape 2 : lancer Thompson avec prior Beta(50,50) (informatif)
// Etape 3 : comparer les regrets et interpreter (quand un prior informatif aide/nuit)
Console.WriteLine("Exercice 3 a completer : impact du prior informatif Beta(50,50) sur Thompson.");

Exercice 3 a completer : impact du prior informatif Beta(50,50) sur Thompson.

10. Synthese

Politique	Exploration	Calcul du posterior	Origine
epsilon-greedy	uniforme (proba epsilon)	aucun (moyenne empirique)	frequentiste
UCB1	bonus d’incertitude `sqrt(2 ln t / n_k)`	aucun (moyenne empirique)	Auer et al. 2002
Thompson	echantillonnage posterior	Infer.NET (EP/VMP)	Thompson 1933

Ce qu’il faut retenir

Thompson Sampling = jouer selon la probabilite que chaque bras soit le meilleur, quantifiee par un posterior. Les bras incertains (posterior large) sont naturellement explores.
Le moteur Infer.NET calcule le posterior (section 3) : on declare theta ~ Beta ; reward ~ Bernoulli(theta) et le moteur infere Beta(1+s, 1+f). Pour ce cas conjugue il recouvre la forme analytique ; l’intérêt est la generalisation aux modèles non conjugues.
Prong-B PROVEN : le regret cumule de Thompson est inferieur a epsilon-greedy (section 6) — l’exploration bayesienne ciblee par le posterior exploite l’incertitude la ou l’information manque, au lieu d’explorer au hasard. Le problème n’est pas degenerere : la sélection depend visiblement des posteriors.

Ponts

DecInfer-08 section 8 : implemente epsilon-greedy, UCB1 et un exercice de Thompson manuel (formule conjuguee codee a la main). Ce notebook en est le versant moteur.
DecInfer-08 section 10bis : les belief-state updates en Infer.NET pour les POMDPs — même idee d’inference posterior séquentielle, dans un cadre partiellement observable.
References : Thompson, W. R. (1933) On the likelihood that one unknown probability exceeds another ; Auer, P., Cesa-Bianchi, N. & Fischer, P. (2002) Finite-time analysis of the multiarmed bandit problem ; Russo, D., Van Roy, D., Kazerouni, A., Osband, I. & Wen, Z. (2018) A Tutorial on Thompson Sampling.

<- DecInfer-08-Sequential | Infer-5-Causal-Inference -> | Retour a la serie

Retour au sommet