DecInfer-08-Sequential : MDPs, Bandits et POMDPs

Serie : Programmation Probabiliste avec Infer.NET (8/10)
Duree estimee : 60 minutes
Prerequis : DecInfer-01 et 03-07 (arc Decision Theory)

---

Objectifs

• Comprendre les Processus de Decision Markoviens (MDPs)
• Maitriser l’itération de valeur et l’itération de politique
• Decouvrir les alternatives : LP, Expectimax, RTDP
• Appliquer le reward shaping avec le theoreme de preservation de politique
• Introduire les bandits multi-bras et l’indice de Gittins
• Presenter les POMDPs et les belief states

---

Navigation

Précédent	Suivant
DecInfer-07-Expert-Systems	DecInfer-10-Thompson-Sampling

---

Note : Ce notebook est une introduction conceptuelle aux decisions séquentielles. Les implementations avancees avec Deep RL sont dans la serie RL/.

1. Decisions Séquentielles vs One-Shot

Différence fondamentale

Type	Caractéristique	Exemple
One-shot	Une seule decision	Accepter une offre d’emploi
Séquentielle	Serie de decisions interdependantes	Jouer aux echecs

Horizon

• Fini : Nombre fixe d’étapes (T étapes)
• Infini : Le processus continue indefiniment

Facteur d’actualisation γ (gamma)

Pour les horizons infinis, on utilise un facteur γ ∈ [0,1) pour :

• Garantir la convergence des sommes infinies
• Modeliser la préférence pour les recompenses immediates
• γ = 0.99 : vision long terme
• γ = 0.5 : vision court terme

// Installation Infer.NET
#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;

Console.WriteLine("Infer.NET charge !");

The below script needs to be able to find the current output cell; this is an easy method to get it.

Installed Packages

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

Infer.NET charge !

Chargement du FactorGraphHelper

Le FactorGraphHelper est un utilitaire qui permet de visualiser les graphes de facteurs generes par Infer.NET. Ces visualisations sont essentielles pour comprendre la structure des modèles probabilistes séquentiels comme les MDPs et POMDPs.

Le helper utilise Graphviz pour generer des diagrammes SVG des modèles.

// Charger le helper pour visualiser les factor graphs
#load "../../Infer/FactorGraphHelper.cs"

// Flag pour activer les visualisations de factor graphs
bool ShowFactorGraph = true;

Console.WriteLine("FactorGraphHelper charge.");
Console.WriteLine($"Graphviz disponible : {FactorGraphHelper.IsGraphvizAvailable()}");

FactorGraphHelper charge.
Graphviz disponible : True

Environnement pret

L’infrastructure Infer.NET est chargee. Dans ce notebook, nous utiliserons principalement Infer.NET pour la section sur les belief states dans les POMDPs, ou l’inference bayesienne automatique simplifie considerablement les calculs.

Commencons par définir un MDP simple : une grille de navigation avec recompenses et obstacles.

2. Processus de Decision Markoviens (MDP)

Définition formelle

Un MDP est un tuple (S, A, P, R, γ) :

Élément	Notation	Description
Etats	S	Ensemble des etats possibles
Actions	A	Ensemble des actions
Transitions	P(s’|s,a)	Probabilité de transition
Recompenses	R(s,a) ou R(s,a,s’)	Recompense immediate
Discount	γ	Facteur d’actualisation

Politique et Fonction de Valeur

• Politique π : S → A (ou distribution sur A)
• Fonction de valeur V^π(s) : Utilite esperee depuis s en suivant π
• Fonction action-valeur Q^π(s, a) : Utilite esperee en faisant a puis suivant π

// Définition d'un MDP simple : Navigation dans une grille

public class GridMDP
{
    public int Width { get; }
    public int Height { get; }
    public double Gamma { get; }
    public Dictionary<(int, int), double> Rewards { get; }
    public HashSet<(int, int)> TerminalStates { get; }
    public HashSet<(int, int)> Walls { get; }
    
    public string[] Actions { get; } = { "N", "S", "E", "W" };
    
    // Directions
    private Dictionary<string, (int dx, int dy)> _directions = new()
    {
        { "N", (0, 1) }, { "S", (0, -1) }, { "E", (1, 0) }, { "W", (-1, 0) }
    };
    
    public GridMDP(int width, int height, double gamma = 0.9)
    {
        Width = width;
        Height = height;
        Gamma = gamma;
        Rewards = new Dictionary<(int, int), double>();
        TerminalStates = new HashSet<(int, int)>();
        Walls = new HashSet<(int, int)>();
    }
    
    public List<(int, int)> GetStates()
    {
        var states = new List<(int, int)>();
        for (int x = 0; x < Width; x++)
            for (int y = 0; y < Height; y++)
                if (!Walls.Contains((x, y)))
                    states.Add((x, y));
        return states;
    }
    
    public double GetReward((int, int) state) => 
        Rewards.TryGetValue(state, out var r) ? r : -0.04; // Cout de mouvement par defaut
    
    public List<((int, int) nextState, double prob)> GetTransitions((int, int) state, string action)
    {
        if (TerminalStates.Contains(state))
            return new List<((int, int), double)> { (state, 1.0) };
        
        var transitions = new List<((int, int), double)>();
        var (dx, dy) = _directions[action];
        
        // 80% de chance d'aller dans la direction voulue
        transitions.Add((NextState(state, action), 0.8));
        
        // 10% de chance d'aller perpendiculairement (droite ou gauche)
        var perpActions = action == "N" || action == "S" 
            ? new[] { "E", "W" } 
            : new[] { "N", "S" };
        
        foreach (var perpAction in perpActions)
            transitions.Add((NextState(state, perpAction), 0.1));
        
        return transitions;
    }
    
    private (int, int) NextState((int, int) state, string action)
    {
        var (x, y) = state;
        var (dx, dy) = _directions[action];
        int nx = x + dx, ny = y + dy;
        
        // Collision avec mur ou bord = rester sur place
        if (nx < 0 || nx >= Width || ny < 0 || ny >= Height || Walls.Contains((nx, ny)))
            return state;
        return (nx, ny);
    }
}

// Creer le MDP classique de Russell & Norvig
var mdp = new GridMDP(4, 3, gamma: 0.9);
mdp.Rewards[(3, 2)] = 1.0;   // But positif
mdp.Rewards[(3, 1)] = -1.0;  // Piege
mdp.TerminalStates.Add((3, 2));
mdp.TerminalStates.Add((3, 1));
mdp.Walls.Add((1, 1));       // Mur

Console.WriteLine("MDP Grille 4x3 cree :");
Console.WriteLine("  But (+1) en (3,2)");
Console.WriteLine("  Piege (-1) en (3,1)");
Console.WriteLine("  Mur en (1,1)");
Console.WriteLine($"  Gamma = {mdp.Gamma}");

MDP Grille 4x3 cree :
  But (+1) en (3,2)
  Piege (-1) en (3,1)
  Mur en (1,1)
  Gamma = 0,9

Visualisation : Backup de Bellman

L’équation de Bellman effectue un “backup” des valeurs futures vers l’etat courant :

                    Etat s (valeur V(s) a calculer)
                              │
              ┌───────────────┼───────────────┐
              │               │               │
         Action a₁       Action a₂       Action a₃
              │               │               │
              ▼               ▼               ▼
         ┌────────┐      ┌────────┐      ┌────────┐
         │ Q(s,a₁)│      │ Q(s,a₂)│      │ Q(s,a₃)│
         │  = ?   │      │  = ?   │      │  = ?   │
         └────┬───┘      └────┬───┘      └────┬───┘
              │               │               │
         ┌────┴────┐     ┌────┴────┐     ┌────┴────┐
         │         │     │         │     │         │
        P=0.8    P=0.2  P=0.9    P=0.1  P=0.7    P=0.3
         │         │     │         │     │         │
         ▼         ▼     ▼         ▼     ▼         ▼
       [s'₁]     [s'₂] [s'₁]     [s'₃] [s'₂]     [s'₃]
      V=0.8     V=0.3  V=0.8     V=0.1  V=0.3     V=0.1

Calcul pour action a₁ : - Q(s, a₁) = R(s, a₁) + γ × [0.8 × V(s’₁) + 0.2 × V(s’₂)] - Q(s, a₁) = R(s, a₁) + γ × [0.8 × 0.8 + 0.2 × 0.3] - Q(s, a₁) = R(s, a₁) + γ × 0.70

Decision : V(s) = max{Q(s, a₁), Q(s, a₂), Q(s, a₃)}

Le même backup, rendu sous forme de graphe : l’état s interroge chaque action, chaque action moyenne les valeurs des états successeurs pondérées par leur probabilité de transition.

flowchart TD
    S["État s<br/>V(s) = max Q(s,a)"]
    S --> A1["Action a₁"]
    S --> A2["Action a₂"]
    S --> A3["Action a₃"]
    A1 --> Q1["Q(s,a₁)"]
    A2 --> Q2["Q(s,a₂)"]
    A3 --> Q3["Q(s,a₃)"]
    Q1 -->|"P=0.8"| N1["s'₁ · V=0.8"]
    Q1 -->|"P=0.2"| N2["s'₂ · V=0.3"]
    Q2 -->|"P=0.9"| N3["s'₁ · V=0.8"]
    Q2 -->|"P=0.1"| N4["s'₃ · V=0.1"]
    Q3 -->|"P=0.7"| N5["s'₂ · V=0.3"]
    Q3 -->|"P=0.3"| N6["s'₃ · V=0.1"]
    classDef state fill:#cfe2ff,stroke:#084298,color:#052c65
    classDef act fill:#fff3cd,stroke:#b8860b,color:#5c4400
    classDef q fill:#d1e7dd,stroke:#0f5132,color:#052e16
    class S state
    class A1,A2,A3 act
    class Q1,Q2,Q3 q

Lecture. La valeur d’un état est le maximum sur les actions (V(s) = maxₐ Q(s,a)), tandis que la valeur d’une action est l’espérance des valeurs successeurs pondérée par les probabilités de transition (Q(s,a) = R + γ·Σ P(s'|s,a)·V(s')). Le max fait un choix, l’espérance moyenne le hasard : c’est l’alternance de ces deux opérations qui distingue la programmation dynamique du simple chaînage déterministe.

Visualisation : Propagation des Valeurs dans Value Itération

Value Itération propage les valeurs depuis les etats terminaux vers les etats initiaux :

Itération 0 (initialisation)         Itération 5                        Itération finale
┌─────┬─────┬─────┬─────┐           ┌─────┬─────┬─────┬─────┐           ┌─────┬─────┬─────┬─────┐
│ 0.0 │ 0.0 │ 0.0 │ 1.0 │           │ 0.3 │ 0.5 │ 0.7 │ 1.0 │           │ 0.5 │ 0.6 │ 0.8 │ 1.0 │
├─────┼─────┼─────┼─────┤           ├─────┼─────┼─────┼─────┤           ├─────┼─────┼─────┼─────┤
│ 0.0 │#####│ 0.0 │-1.0 │   ──►    │ 0.2 │#####│ 0.3 │-1.0 │   ──►    │ 0.4 │#####│ 0.5 │-1.0 │
├─────┼─────┼─────┼─────┤           ├─────┼─────┼─────┼─────┤           ├─────┼─────┼─────┼─────┤
│ 0.0 │ 0.0 │ 0.0 │ 0.0 │           │ 0.1 │ 0.1 │ 0.2 │ 0.0 │           │ 0.3 │ 0.3 │ 0.3 │ 0.1 │
└─────┴─────┴─────┴─────┘           └─────┴─────┴─────┴─────┘           └─────┴─────┴─────┴─────┘
    Seuls les terminaux                Les valeurs "diffusent"            Convergence (delta < ε)
    ont des valeurs non nulles         vers les etats voisins

Proprietes de convergence : - Le facteur γ=0.9 garantit que les valeurs diminuent exponentiellement avec la distance - Convergence en O(log(1/ε)/(1-γ)) itérations - Pour γ=0.9 et ε=0.001 : environ 14-15 itérations

3. Équation de Bellman

Intuition

L’équation de Bellman exprime un principe fondamental de consistance temporelle :

La valeur d’un etat = recompense immediate + valeur actualisee des etats futurs

C’est une relation récursive : la valeur de chaque etat depend de la valeur des etats atteignables. Cette structure permet de resoudre le problème “a l’envers” (backward induction) ou iterativement.

Équation de Bellman pour V*

La fonction de valeur optimale satisfait :

\[V^*(s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} P(s'|s,a) V^*(s') \right]\]

Interpretation terme par terme : - \(\max_a\) : On choisit la meilleure action - \(R(s,a)\) : Recompense immediate - \(\gamma\) : Facteur d’actualisation (valeur du futur) - \(\sum_{s'} P(s'|s,a) V^*(s')\) : Esperance de la valeur future

Équation de Bellman pour Q*

\[Q^*(s, a) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q^*(s', a')\]

La fonction Q donne la valeur de faire a puis agir optimalement.

Politique optimale

\[\pi^*(s) = \arg\max_a Q^*(s, a)\]

La politique optimale est déterministe : dans chaque etat, une action domine.

Pourquoi Bellman est-il si important ?

L’équation de Bellman est la cle de voute de la programmation dynamique et du reinforcement learning car :

1. Elle decompose un problème global en sous-problemes locaux
2. Elle fournit une condition d’optimalite verifiable
3. Elle inspire les algorithmes (VI, PI, Q-learning, etc.)

4. Itération de Valeur

Algorithme

1. Initialiser V(s) = 0 pour tout s
2. Repeter jusqu’a convergence :
   • Pour chaque etat s :
     • V(s) ← max_a [R(s,a) + γ Σ_s’ P(s’|s,a) V(s’)]
3. Extraire la politique : π(s) = argmax_a Q(s,a)

Complexite

• O(|S|² |A|) par itération
• Converge en O(log(1/ε) / (1-γ)) itérations

Visualisation ASCII de la Grille MDP

La grille 4x3 ci-dessous illustre la structure du MDP : - Les fleches montrent la politique optimale calculee - Les valeurs V*(s) decroissent avec la distance au but - Le mur (1,1) bloque certains chemins

    y=2:   [0.51]→  [0.65]→  [0.80]→  [+1.0]●
                                         ↑
    y=1:   [0.40]↑  [WALL]   [0.49]↑  [-1.0]●
                                         ↑
    y=0:   [0.30]↑  [0.25]→  [0.35]↑  [0.13]←

Structure du factor graph MDP (conceptuel) :

  s_t ─────┬────→ s_{t+1} ─────┬────→ s_{t+2}
           │                   │
           ↓                   ↓
   [ P(s'|s,a) ]       [ P(s'|s,a) ]
           │                   │
           ↓                   ↓
         a_t                 a_{t+1}
           │                   │
           ↓                   ↓
        R(s,a)              R(s,a)

Chaque étape temporelle forme une “tranche” avec : - Un noeud d’etat s_t (variable aleatoire) - Un noeud d’action a_t (variable de decision) - Un facteur de transition P(s_{t+1}|s_t, a_t) - Un facteur de recompense R(s_t, a_t)

// Iteration de Valeur

public class ValueIteration
{
    public static (Dictionary<(int,int), double> V, Dictionary<(int,int), string> policy) 
        Solve(GridMDP mdp, double epsilon = 0.001, int maxIter = 100)
    {
        var states = mdp.GetStates();
        var V = states.ToDictionary(s => s, s => 0.0);
        
        for (int iter = 0; iter < maxIter; iter++)
        {
            double delta = 0;
            var newV = new Dictionary<(int, int), double>(V);
            
            foreach (var s in states)
            {
                if (mdp.TerminalStates.Contains(s))
                {
                    newV[s] = mdp.GetReward(s);
                    continue;
                }
                
                double maxQ = double.NegativeInfinity;
                foreach (var a in mdp.Actions)
                {
                    double q = mdp.GetReward(s);
                    foreach (var (nextState, prob) in mdp.GetTransitions(s, a))
                        q += mdp.Gamma * prob * V[nextState];
                    maxQ = Math.Max(maxQ, q);
                }
                
                newV[s] = maxQ;
                delta = Math.Max(delta, Math.Abs(V[s] - newV[s]));
            }
            
            V = newV;
            
            if (delta < epsilon)
            {
                Console.WriteLine($"Convergence apres {iter + 1} iterations (delta = {delta:E2})");
                break;
            }
        }
        
        // Extraire la politique
        var policy = new Dictionary<(int, int), string>();
        foreach (var s in states)
        {
            if (mdp.TerminalStates.Contains(s))
            {
                policy[s] = "T"; // Terminal
                continue;
            }
            
            string bestAction = null;
            double maxQ = double.NegativeInfinity;
            
            foreach (var a in mdp.Actions)
            {
                double q = mdp.GetReward(s);
                foreach (var (nextState, prob) in mdp.GetTransitions(s, a))
                    q += mdp.Gamma * prob * V[nextState];
                
                if (q > maxQ)
                {
                    maxQ = q;
                    bestAction = a;
                }
            }
            policy[s] = bestAction;
        }
        
        return (V, policy);
    }
}

var (V, policy) = ValueIteration.Solve(mdp);

// Afficher la grille
Console.WriteLine("\nFonction de Valeur V* :");
for (int y = mdp.Height - 1; y >= 0; y--)
{
    for (int x = 0; x < mdp.Width; x++)
    {
        if (mdp.Walls.Contains((x, y)))
            Console.Write("  ####  ");
        else
            Console.Write($" {V[(x, y)],6:F3} ");
    }
    Console.WriteLine();
}

Console.WriteLine("\nPolitique optimale π* :");
var arrows = new Dictionary<string, string> { {"N","↑"}, {"S","↓"}, {"E","→"}, {"W","←"}, {"T","●"} };
for (int y = mdp.Height - 1; y >= 0; y--)
{
    for (int x = 0; x < mdp.Width; x++)
    {
        if (mdp.Walls.Contains((x, y)))
            Console.Write(" # ");
        else
            Console.Write($" {arrows[policy[(x, y)]]} ");
    }
    Console.WriteLine();
}

Convergence apres 14 iterations (delta = 6,01E-004)

Fonction de Valeur V* :
  0,509   0,650   0,795   1,000 
  0,398   ####    0,486  -1,000 
  0,296   0,254   0,345   0,130 

Politique optimale π* :
 →  →  →  ● 
 ↑  #  ↑  ● 
 ↑  →  ↑  ← 

Interpretation de l’Itération de Valeur

Fonction de valeur V* : - Les valeurs decroissent en s’eloignant du but (+1 en (3,2)) - La case (3,1) vaut -1 car c’est un piege (terminal negatif) - Les valeurs reflètent la distance actualisee au but avec risque de deviation

Politique optimale π* : - Toutes les fleches pointent vers le but (3,2) en evitant le piege (3,1) - La case (3,0) pointe vers la gauche (←) pour eviter de tomber dans le piege ! - Cette politique non-intuitive illustre la puissance de l’optimisation

Pourquoi 14 itérations ? - Le facteur γ = 0.9 propage les valeurs lentement - Les etats eloignes du but ont besoin de plusieurs itérations pour “sentir” la recompense - Critère d’arret : delta < 0.001 (precision suffisante)

Verification pratique : - V(0,0) ≈ 0.30 : depuis (0,0), on peut atteindre le but avec un profit actualise de ~0.30 - V(2,2) ≈ 0.80 : juste a cote du but, on y arrive presque certainement

5. Itération de Politique

Algorithme

1. Initialiser π arbitrairement
2. Repeter jusqu’a stabilite :
   • Évaluation : Calculer V^π (resoudre système lineaire)
   • Amelioration : π(s) ← argmax_a Q^π(s,a)

Compromis Value Itération vs Policy Itération

Critère	Value Itération	Policy Itération
Itérations	Beaucoup (log(1/ε)/(1-γ))	Peu (souvent 5-10)
Cout/itération	O(|S|² |A|) leger	O(|S|³) évaluation exacte
Convergence	Asymptotique (ε-optimal)	Exacte en nombre fini
Memoire	V(s) seulement	V(s) + π(s)

Quand utiliser chaque méthode ?

Preferer Value Itération si : - Grand espace d’etats (|S| > 10,000) - Precision approximative suffisante - γ proche de 1 (convergence lente de PI) - Implementation simple souhaitee

Preferer Policy Itération si : - Petit/moyen espace d’etats - Solution exacte requise - Politique stable rapidement - Évaluation peut etre acceleree (ex: méthodes matricielles)

Variantes hybrides

• Modified Policy Itération : Évaluation partielle (k itérations de Bellman au lieu de resolution exacte)
• Asynchronous VI : Mise a jour d’un sous-ensemble d’etats a chaque itération
• Prioritized Sweeping : Mettre a jour les etats les plus “surprenants” en premier

// Iteration de Politique

public class PolicyIteration
{
    public static (Dictionary<(int,int), double> V, Dictionary<(int,int), string> policy) 
        Solve(GridMDP mdp, int maxIter = 20)
    {
        var states = mdp.GetStates();
        
        // Initialiser politique aleatoire
        var policy = states.ToDictionary(s => s, s => 
            mdp.TerminalStates.Contains(s) ? "T" : "N");
        
        var V = states.ToDictionary(s => s, s => 0.0);
        
        for (int iter = 0; iter < maxIter; iter++)
        {
            // 1. Évaluation de politique (iterative simplifiee)
            for (int evalIter = 0; evalIter < 50; evalIter++)
            {
                var newV = new Dictionary<(int, int), double>(V);
                foreach (var s in states)
                {
                    if (mdp.TerminalStates.Contains(s))
                    {
                        newV[s] = mdp.GetReward(s);
                        continue;
                    }
                    
                    string a = policy[s];
                    double v = mdp.GetReward(s);
                    foreach (var (nextState, prob) in mdp.GetTransitions(s, a))
                        v += mdp.Gamma * prob * V[nextState];
                    newV[s] = v;
                }
                V = newV;
            }
            
            // 2. Amelioration de politique
            bool stable = true;
            foreach (var s in states)
            {
                if (mdp.TerminalStates.Contains(s)) continue;
                
                string oldAction = policy[s];
                string bestAction = null;
                double maxQ = double.NegativeInfinity;
                
                foreach (var a in mdp.Actions)
                {
                    double q = mdp.GetReward(s);
                    foreach (var (nextState, prob) in mdp.GetTransitions(s, a))
                        q += mdp.Gamma * prob * V[nextState];
                    
                    if (q > maxQ)
                    {
                        maxQ = q;
                        bestAction = a;
                    }
                }
                
                policy[s] = bestAction;
                if (bestAction != oldAction) stable = false;
            }
            
            Console.WriteLine($"Iteration {iter + 1} : stable = {stable}");
            if (stable) break;
        }
        
        return (V, policy);
    }
}

Console.WriteLine("=== Iteration de Politique ===\n");
var (V_pi, policy_pi) = PolicyIteration.Solve(mdp);

// Verifier que les résultats sont identiques
Console.WriteLine("\nComparaison avec Value Iteration :");
bool same = true;
foreach (var s in mdp.GetStates())
{
    if (policy[s] != policy_pi[s])
    {
        same = false;
        Console.WriteLine($"  Difference en {s}: VI={policy[s]}, PI={policy_pi[s]}");
    }
}
if (same) Console.WriteLine("  Politiques identiques !");

=== Iteration de Politique ===

Iteration 1 : stable = False
Iteration 2 : stable = False
Iteration 3 : stable = True

Comparaison avec Value Iteration :
  Politiques identiques !

Interpretation de l’Itération de Politique

Convergence rapide : - Seulement 3 itérations contre 14 pour Value Itération ! - Chaque itération est plus couteuse (évaluation complete), mais beaucoup moins d’itérations

Pourquoi moins d’itérations ? - Policy Itération fait des sauts dans l’espace des politiques - Value Itération fait des petits pas dans l’espace des valeurs - La politique peut etre optimale bien avant que les valeurs convergent exactement

Verification de coherence : - Les deux méthodes donnent la même politique optimale - C’est rassurant : le problème a une solution unique

Quand utiliser chaque méthode ?

Situation	Méthode recommandee
Grand espace d’etats	Value Itération (moins de memoire)
Besoin de precision exacte	Policy Itération
Implementation simple	Value Itération
γ très proche de 1	Policy Itération (VI converge lentement)

Exercice 1 : MDP Modifie - Comparaison Value Itération et Policy Itération

Contexte : Vous disposez du MDP grille 4x3 du cours, mais avec des recompenses modifiees. Vous allez comparer la vitesse de convergence de Value Itération et Policy Itération.

Données :

Paramètre	Valeur
But (+5) en (3,2)	Recompense plus elevee
Piege (-5) en (3,1)	Penalite plus severe
Bonus (+0.5) en (2,2)	Recompense intermediaire
Mur en (1,1)	Obstacle
Gamma	0.9 (puis 0.95)

Objectif : Comparer les deux méthodes sur un MDP modifie et analyser l’impact de gamma.

Étapes : 1. Appliquer Value Itération sur le MDP modifie et noter le nombre d’itérations 2. Appliquer Policy Itération sur le même MDP et noter le nombre d’itérations 3. Verifier que les deux méthodes donnent la même politique optimale 4. Tester avec gamma = 0.95 et observer l’impact sur la convergence 5. Analyser l’effet du bonus intermediaire en (2,2) sur la politique

Indices : - Indice 1 : Les classes ValueIteration.Solve() et PolicyIteration.Solve() sont déjà définies - Indice 2 : Pour changer gamma, recreer le MDP avec new GridMDP(4, 3, gamma: 0.95) - Indice 3 : Le bonus en (2,2) attire l’agent vers cette case. La politique passe-t-elle par (2,2) ?

// Exercice : MDP Modifie - Comparaison VI et PI avec Paramètres Différents

// Creer un MDP modifie : même grille 4x3 mais recompenses différentes
var mdpMod = new GridMDP(4, 3, gamma: 0.9);
mdpMod.Rewards[(3, 2)] = 5.0;    // But plus attractif
mdpMod.Rewards[(3, 1)] = -5.0;   // Piege plus dangereux
mdpMod.Rewards[(2, 2)] = 0.5;    // Bonus intermediaire
mdpMod.TerminalStates.Add((3, 2));
mdpMod.TerminalStates.Add((3, 1));
mdpMod.Walls.Add((1, 1));         // Même mur

Console.WriteLine("=== Exercice : MDP Modifie ===\n");
Console.WriteLine("MDP Grille 4x3 modifie :");
Console.WriteLine("  But (+5) en (3,2)");
Console.WriteLine("  Piege (-5) en (3,1)");
Console.WriteLine("  Bonus (+0.5) en (2,2)");
Console.WriteLine("  Mur en (1,1)");

// TODO 1 : Appliquer Value Iteration et compter les iterations
// Indice : la classe ValueIteration.Solve affiche deja le nombre d'iterations
Console.WriteLine("\n--- Value Iteration ---");

// TODO 2 : Appliquer Policy Iteration et compter les iterations
// Indice : la classe PolicyIteration.Solve affiche aussi les iterations
Console.WriteLine("\n--- Policy Iteration ---");

// TODO 3 : Comparer les résultats (politiques et valeurs)
// Indice : afficher les deux politiques et verifier si elles sont identiques

// TODO 4 : Tester avec gamma = 0.95 et observer l'impact
// Indice : recreer le MDP avec gamma=0.95 et relancer les deux méthodes
// Étape : la convergence est-elle plus rapide ou plus lente ?

// TODO 5 : Analyser pourquoi le bonus en (2,2) change (ou pas) la politique
// Indice : comparer la politique obtenue avec celle du MDP original
Console.WriteLine("Exercice a completer");

=== Exercice : MDP Modifie ===

MDP Grille 4x3 modifie :
  But (+5) en (3,2)
  Piege (-5) en (3,1)
  Bonus (+0.5) en (2,2)
  Mur en (1,1)

--- Value Iteration ---

--- Policy Iteration ---
Exercice a completer

6. Alternatives : LP, Expectimax, RTDP

Programmation Lineaire (LP)

Le MDP peut etre formule comme un programme lineaire :

• Variables : V(s) pour chaque etat
• Objectif : min Σ_s V(s)
• Contraintes : V(s) ≥ R(s,a) + γ Σ_s’ P(s’|s,a) V(s’) pour tout a

Expectimax

Pour les MDPs a horizon fini, on peut utiliser un arbre de recherche :

       (s0)
      / | \
   a1  a2  a3     <- Noeuds max (choix agent)
   / \ 
 s1  s2           <- Noeuds chance (transition)

RTDP (Real-Time Dynamic Programming)

• Mise a jour le long de trajectoires simulees
• Focus sur les etats atteignables
• Algorithme anytime : ameliore avec plus de temps

// RTDP simplifie

public class RTDP
{
    public static Dictionary<(int,int), double> Solve(
        GridMDP mdp, (int, int) startState, int nTrials = 100)
    {
        var states = mdp.GetStates();
        var V = states.ToDictionary(s => s, s => 0.0);
        var rng = new Random(42);
        
        for (int trial = 0; trial < nTrials; trial++)
        {
            var s = startState;
            int steps = 0;
            
            while (!mdp.TerminalStates.Contains(s) && steps < 100)
            {
                // Mise a jour de Bellman
                double maxQ = double.NegativeInfinity;
                string bestAction = null;
                
                foreach (var a in mdp.Actions)
                {
                    double q = mdp.GetReward(s);
                    foreach (var (nextState, prob) in mdp.GetTransitions(s, a))
                        q += mdp.Gamma * prob * V[nextState];
                    
                    if (q > maxQ)
                    {
                        maxQ = q;
                        bestAction = a;
                    }
                }
                
                V[s] = maxQ;
                
                // Simuler transition
                var transitions = mdp.GetTransitions(s, bestAction);
                double r = rng.NextDouble();
                double cumProb = 0;
                foreach (var (nextState, prob) in transitions)
                {
                    cumProb += prob;
                    if (r <= cumProb)
                    {
                        s = nextState;
                        break;
                    }
                }
                
                steps++;
            }
            
            // Update terminal state
            if (mdp.TerminalStates.Contains(s))
                V[s] = mdp.GetReward(s);
        }
        
        return V;
    }
}

Console.WriteLine("=== RTDP (100 trials depuis (0,0)) ===\n");
var V_rtdp = RTDP.Solve(mdp, (0, 0), nTrials: 100);

// Comparer avec Value Iteration
Console.WriteLine("Comparaison V_RTDP vs V_VI :");
Console.WriteLine("  Etat   |  V_RTDP  |   V_VI   |   Diff");
Console.WriteLine("---------|----------|----------|--------");
foreach (var s in new[] { (0,0), (0,2), (2,2), (3,2) })
{
    double diff = Math.Abs(V_rtdp[s] - V[s]);
    Console.WriteLine($" ({s.Item1},{s.Item2})   | {V_rtdp[s],8:F4} | {V[s],8:F4} | {diff,6:F4}");
}

=== RTDP (100 trials depuis (0,0)) ===

Comparaison V_RTDP vs V_VI :
  Etat   |  V_RTDP  |   V_VI   |   Diff
---------|----------|----------|--------
 (0,0)   |   0,1666 |   0,2960 | 0,1294
 (0,2)   |  -0,1123 |   0,5094 | 0,6217
 (2,2)   |   0,7954 |   0,7954 | 0,0000
 (3,2)   |   1,0000 |   1,0000 | 0,0000

Interpretation de RTDP (Real-Time Dynamic Programming)

Comparaison RTDP vs Value Itération :

Etat	V_RTDP	V_VI	Ecart	Commentaire
(0,0)	0.17	0.30	0.13	Sous-estime (visite moderee)
(0,2)	-0.11	0.51	0.62	Non visite depuis (0,0)
(2,2)	0.80	0.80	0.00	Exact (sur le chemin optimal)
(3,2)	1.00	1.00	0.00	Terminal (toujours exact)

Pourquoi ces ecarts ?

RTDP est un algorithme anytime qui : 1. Ne met a jour que les etats visites par simulation 2. Converge vers V* sur les etats atteignables depuis l’etat de depart 3. Peut ignorer certains etats non pertinents pour la politique courante

Etat (0,2) très sous-estime : - Depuis (0,0), la politique optimale va vers l’est, pas vers le nord - L’etat (0,2) n’est jamais visite dans les simulations - Sa valeur reste proche de l’initialisation (ici negative a cause de mauvaises transitions simulees)

Note technique : RTDP garantit la convergence vers V* uniquement sur les etats visites infiniment souvent. Pour une convergence globale, on utilise des variantes comme LRTDP (Labeled RTDP) qui marquent les etats “resolus”.

Quand utiliser RTDP ?

Situation	Recommandation
Grands espaces d’etats	RTDP (focus sur etats pertinents)
Solution exacte requise	Value Itération classique
Temps de calcul limite	RTDP (anytime)
Tous les etats importants	Value/Policy Itération

Visualisation : Reward Shaping avec Potentiel

Le reward shaping ajoute une recompense de guidage F(s, a, s’) sans modifier la politique optimale :

                SANS Shaping                     AVEC Shaping (Φ = -distance au but)
                                  
    ┌─────────────────────────┐           ┌─────────────────────────┐
    │                    ★ +1 │           │                    ★ +1 │
    │                         │           │      F=+0.5   F=+1.0    │
    │                    ×-1  │           │         ↘       ↘       │
    │   R=-0.04  R=-0.04      │           │   R'≈0.5  R'≈0.8  ×-1  │
    │      ↓        ↓         │           │      ↓        ↓         │
    │   R=-0.04  R=-0.04      │           │   R'≈0.3  R'≈0.6       │
    │      ↓        ↓         │           │      ↓        ↓         │
    │   R=-0.04  R=-0.04      │           │   R'≈0.1  R'≈0.4       │
    │      ↑                   │           │      ↑                   │
    │   START                  │           │   START                  │
    └─────────────────────────┘           └─────────────────────────┘
    
    Recompense sparse :                    Recompense dense :
    - Longue exploration                   - Gradient vers le but
    - Signaux retardes                     - Apprentissage accelere

Theoreme de Ng et al. : Si F(s, a, s’) = γΦ(s’) - Φ(s), alors π* est preservee.

Intuition : Le shaping recompense les “progres” sans créer de raccourcis.

7. Reward Shaping

Le problème des recompenses sparses

Quand les recompenses sont rares (ex: +1 seulement au but), l’apprentissage est très lent.

Solution : Ajouter une recompense de faconnage

\[R'(s, a, s') = R(s, a, s') + F(s, a, s')\]

Theoreme de preservation de politique (Ng et al., 1999)

Si F a la forme d’une fonction de potentiel :

\[F(s, a, s') = \gamma \Phi(s') - \Phi(s)\]

Alors la politique optimale est preservee !

Intuition

• Φ(s) represente “a quel point s est proche du but”
• F recompense les transitions vers des etats meilleurs
• La forme spécifique garantit que les raccourcis ne sont pas crees

---

Synthese : Comparaison des méthodes de resolution MDP

Avant de passer aux bandits, recapitulons les méthodes vues pour resoudre les MDPs :

Méthode	Principe	Complexite/iter	Convergence	Usage typique
Value Itération	Bellman updates iteratifs	O(|S|^2 |A|)	Asymptotique	Standard, simple
Policy Itération	Évaluation + Amelioration	O(|S|^3)	Exacte, finie	Petits MDPs
LP	Programmation lineaire	Polynomial	Exacte	Structure particuliere
RTDP	Updates sur trajectoires	Variable	Sur etats visites	Grands espaces
Expectimax	Arbre de recherche	Exponentiel	Exacte (horizon fini)	Jeux, planification

Arbre de decision pour choisir une méthode :

MDP a resoudre
    |
    +-- Horizon fini ?
    |       |
    |       +-- Oui --> Expectimax ou backward induction
    |       +-- Non --> Méthodes iteratives
    |
    +-- Grand espace d'etats (\|S\| > 10,000) ?
    |       |
    |       +-- Oui --> RTDP, LRTDP, ou approximation
    |       +-- Non --> VI ou PI
    |
    +-- Besoin de precision exacte ?
            |
            +-- Oui --> Policy Itération ou LP
            +-- Non --> Value Itération (plus rapide par itération)

Note : En pratique moderne, les grands MDPs sont souvent resolus par Deep Reinforcement Learning (DQN, PPO, etc.) qui approximent V ou Q avec des reseaux de neurones. Voir la serie RL/.

Visualisation : Dilemme Exploration vs Exploitation

Le problème du bandit multi-bras illustre le dilemme fondamental :

              ┌─────────────────────────────────────────┐
              │     Agent avec connaissance partielle   │
              │                                         │
              │   Bras 1: μ̂ = 0.35 (n=20)              │
              │   Bras 2: μ̂ = 0.48 (n=15)    ◄── Best? │
              │   Bras 3: μ̂ = 0.52 (n=8)     ◄── Best? │
              │   Bras 4: μ̂ = 0.30 (n=12)              │
              └─────────────────────┬───────────────────┘
                                    │
                    ┌───────────────┴───────────────┐
                    │                               │
              ┌─────▼─────┐                   ┌─────▼─────┐
              │ EXPLOITER │                   │ EXPLORER  │
              │           │                   │           │
              │ Jouer le  │                   │ Jouer un  │
              │ meilleur  │                   │ bras peu  │
              │ connu     │                   │ essaye    │
              │ (Bras 3?) │                   │ (Bras 3?) │
              └───────────┘                   └───────────┘
                    │                               │
              Gain court                      Gain long
              terme sur                       terme si
                                              meilleur

Stratégies : - ε-greedy : Exploite (1-ε)% du temps, explore ε% aleatoirement - UCB : Ajoute un bonus d’incertitude aux bras peu explores - Thompson : Echantillonne selon la posterior de chaque bras - Gittins : Index optimal théorique (mais couteux a calculer)

Le même dilemme, rendu sous forme de graphe : depuis un état de connaissance partielle, l’agent choisit entre exploiter le meilleur bras connu ou explorer un bras encore incertain.

flowchart TD
    AG["Agent · connaissance partielle<br/>Bras 1 : μ̂=0.35 (n=20)<br/>Bras 2 : μ̂=0.48 (n=15)<br/>Bras 3 : μ̂=0.52 (n=8) — meilleur μ̂ mais peu essayé<br/>Bras 4 : μ̂=0.30 (n=12)"]
    AG --> EXPLOIT["EXPLOITER<br/>jouer le meilleur connu (Bras 3)"]
    AG --> EXPLORE["EXPLORER<br/>jouer un bras peu essayé<br/>(Bras 3 aussi : n=8 seulement)"]
    EXPLOIT --> G1["Gain court terme"]
    EXPLORE --> G2["Gain long terme si meilleur"]
    classDef agent fill:#cfe2ff,stroke:#084298,color:#052c65
    classDef exploit fill:#d1e7dd,stroke:#0f5132,color:#052e16
    classDef explore fill:#fff3cd,stroke:#b8860b,color:#5c4400
    class AG agent
    class EXPLOIT,G1 exploit
    class EXPLORE,G2 explore

Lecture. Le Bras 3 illustre la tension : il a la meilleure moyenne estimée (μ̂=0.52) et le plus faible nombre d’essais (n=8) — donc l’estimation la moins fiable. L’exploiter maximise le gain immédiat ; l’explorer réduit l’incertitude au risque d’un coup moins bon. Les stratégies (ε-greedy, UCB, Thompson, Gittins) diffèrent uniquement par la façon dont elles pondèrent ce compromis moyenne ↔︎ incertitude.

// Demonstration du Reward Shaping

public class ShapedGridMDP : GridMDP
{
    private Func<(int, int), double> _potential;
    private double _gamma;
    
    public ShapedGridMDP(int width, int height, double gamma, Func<(int, int), double> potential) 
        : base(width, height, gamma)
    {
        _potential = potential;
        _gamma = gamma;
    }
    
    public double GetShapedReward((int, int) s, (int, int) sPrime)
    {
        double R = GetReward(s);
        double F = _gamma * _potential(sPrime) - _potential(s);
        return R + F;
    }
}

// Fonction de potentiel : distance negative au but
(int, int) goal = (3, 2);
Func<(int, int), double> Phi = s => -Math.Sqrt(Math.Pow(s.Item1 - goal.Item1, 2) + Math.Pow(s.Item2 - goal.Item2, 2));

Console.WriteLine("=== Reward Shaping avec Fonction de Potentiel ===\n");
Console.WriteLine($"But en {goal}");
Console.WriteLine("Phi(s) = -distance(s, but)\n");

Console.WriteLine("Fonction de potentiel Phi(s) :");
for (int y = 2; y >= 0; y--)
{
    for (int x = 0; x < 4; x++)
    {
        if (mdp.Walls.Contains((x, y)))
            Console.Write("  ####  ");
        else
            Console.Write($" {Phi((x, y)),6:F2} ");
    }
    Console.WriteLine();
}

Console.WriteLine("\nExemples de shaping reward F(s, a, s') = gamma*Phi(s') - Phi(s) :");
Console.WriteLine($"  F((0,0) -> (1,0)) = {0.9 * Phi((1, 0)) - Phi((0, 0)):F3} (vers le but)");
Console.WriteLine($"  F((1,0) -> (0,0)) = {0.9 * Phi((0, 0)) - Phi((1, 0)):F3} (loin du but)");
Console.WriteLine($"  F((2,2) -> (3,2)) = {0.9 * Phi((3, 2)) - Phi((2, 2)):F3} (atteindre le but)");

Console.WriteLine();
Console.WriteLine("=> Le shaping recompense les mouvements vers le but,");
Console.WriteLine("   mais le theoreme garantit que la politique optimale est preservee.");

=== Reward Shaping avec Fonction de Potentiel ===

But en (3, 2)
Phi(s) = -distance(s, but)

Fonction de potentiel Phi(s) :
  -3,00   -2,00   -1,00   -0,00 
  -3,16   ####    -1,41   -1,00 
  -3,61   -2,83   -2,24   -2,00 

Exemples de shaping reward F(s, a, s') = gamma*Phi(s') - Phi(s) :
  F((0,0) -> (1,0)) = 1,060 (vers le but)
  F((1,0) -> (0,0)) = -0,417 (loin du but)
  F((2,2) -> (3,2)) = 1,000 (atteindre le but)

=> Le shaping recompense les mouvements vers le but,
   mais le theoreme garantit que la politique optimale est preservee.

8. Bandits Multi-Bras

Le problème

Vous avez K machines a sous (“bras”). Chaque bras i donne une recompense selon une distribution inconnue.

Dilemme exploration/exploitation : - Explorer : essayer de nouveaux bras pour estimer leurs distributions - Exploiter : jouer le meilleur bras connu

Approches classiques

Méthode	Description
ε-greedy	Exploiter avec proba 1-ε, explorer avec ε
UCB	Upper Confidence Bound : optimisme face a l’incertitude
Thompson	Echantillonner selon la posterior des recompenses
Gittins	Solution optimale pour bandits avec discount

Calcul pratique de l’indice de Gittins

L’indice de Gittins est difficile a calculer exactement car il necessite de resoudre un problème d’arret optimal pour chaque etat possible du bras.

Méthodes de calcul :

Méthode	Complexite	Precision
Calcul exact (DP)	Exponentielle en horizon	Exacte
Approximation restart	Polynomiale	Borne inférieure
Interpolation tabulee	O(1) lookup	Pre-calcule

Cas particulier : Beta-Bernoulli

Pour un bras avec prior Beta(α, β) et recompenses Bernoulli, l’indice peut etre pre-calcule et stocke dans une table.

En pratique : L’indice de Gittins est rarement utilise car UCB et Thompson Sampling sont plus simples a implementer et ont des garanties théoriques similaires pour de nombreux problemes.

// Bandit multi-bras avec différentes strategies

public class MultiArmedBandit
{
    private double[] _trueMeans;
    private Random _rng;
    
    public int K { get; }
    
    public MultiArmedBandit(double[] means, int seed = 42)
    {
        _trueMeans = means;
        K = means.Length;
        _rng = new Random(seed);
    }
    
    public double Pull(int arm)
    {
        // Recompense gaussienne autour de la moyenne vraie
        double u1 = _rng.NextDouble();
        double u2 = _rng.NextDouble();
        double z = Math.Sqrt(-2 * Math.Log(u1)) * Math.Cos(2 * Math.PI * u2);
        return _trueMeans[arm] + 0.5 * z;
    }
    
    public double OptimalMean => _trueMeans.Max();
}

// Strategies
public interface IBanditStrategy
{
    int SelectArm(int[] counts, double[] sumRewards);
    string Name { get; }
}

public class EpsilonGreedy : IBanditStrategy
{
    private double _epsilon;
    private Random _rng;  // seeded pour reproductibilite (fix drift-trap #8364
    public string Name => $"ε-greedy (ε={_epsilon})";
    
    public EpsilonGreedy(double epsilon, int seed = 42) { _epsilon = epsilon; _rng = new Random(seed); }
    
    public int SelectArm(int[] counts, double[] sumRewards)
    {
        if (_rng.NextDouble() < _epsilon)
            return _rng.Next(counts.Length);
        
        int best = 0;
        double bestMean = double.NegativeInfinity;
        for (int i = 0; i < counts.Length; i++)
        {
            double mean = counts[i] > 0 ? sumRewards[i] / counts[i] : 0;
            if (mean > bestMean) { bestMean = mean; best = i; }
        }
        return best;
    }
}

public class UCB : IBanditStrategy
{
    public string Name => "UCB1";
    
    public int SelectArm(int[] counts, double[] sumRewards)
    {
        int totalPulls = counts.Sum();
        if (totalPulls < counts.Length)
            return totalPulls; // Essayer chaque bras une fois
        
        int best = 0;
        double bestUCB = double.NegativeInfinity;
        for (int i = 0; i < counts.Length; i++)
        {
            double mean = sumRewards[i] / counts[i];
            double bonus = Math.Sqrt(2 * Math.Log(totalPulls) / counts[i]);
            double ucb = mean + bonus;
            if (ucb > bestUCB) { bestUCB = ucb; best = i; }
        }
        return best;
    }
}

// Simulation
var bandit = new MultiArmedBandit(new[] { 0.3, 0.5, 0.7, 0.4 });
var strategies = new IBanditStrategy[] { new EpsilonGreedy(0.1), new UCB() };

Console.WriteLine($"Bandit avec {bandit.K} bras, moyennes vraies inconnues");
Console.WriteLine($"Meilleure moyenne : {bandit.OptimalMean}\n");

int T = 1000;

foreach (var strategy in strategies)
{
    var counts = new int[bandit.K];
    var sumRewards = new double[bandit.K];
    double totalReward = 0;
    double totalRegret = 0;
    
    for (int t = 0; t < T; t++)
    {
        int arm = strategy.SelectArm(counts, sumRewards);
        double reward = bandit.Pull(arm);
        
        counts[arm]++;
        sumRewards[arm] += reward;
        totalReward += reward;
        totalRegret += bandit.OptimalMean - reward;
    }
    
    Console.WriteLine($"{strategy.Name}:");
    Console.WriteLine($"  Recompense totale : {totalReward:F1}");
    Console.WriteLine($"  Regret cumule : {totalRegret:F1}");
    Console.WriteLine($"  Tirages par bras : {string.Join(", ", counts)}\n");
}

Bandit avec 4 bras, moyennes vraies inconnues
Meilleure moyenne : 0,7

ε-greedy (ε=0,1):
  Recompense totale : 686,4
  Regret cumule : 13,6
  Tirages par bras : 32, 46, 897, 25

UCB1:
  Recompense totale : 616,1
  Regret cumule : 83,9
  Tirages par bras : 54, 166, 719, 61

Interpretation des stratégies de bandits

Moyennes vraies (inconnues de l’agent) : Bras 1=0.3, Bras 2=0.5, Bras 3=0.7, Bras 4=0.4

Comparaison des stratégies :

Stratégie	Recompense	Regret	Tirages du meilleur bras
ε-greedy (ε=0.1)	686,4	13,6	897/1000 (90%)
UCB1	616,1	83,9	719/1000 (72%)

Analyse : - ε-greedy a mieux performe ici car il exploite plus (90% du temps) - UCB explore plus systematiquement (tous les bras 54-166 fois) - Le regret cumule est plus faible pour ε-greedy dans ce cas simple

Reproductibilité : les chiffres ci-dessus sont déterministes — la stratégie ε-greedy utilise un générateur aléatoire seedé (new Random(42)), donc une nouvelle exécution du notebook produit exactement les mêmes valeurs. Sans ce seed, ces nombres dériveraient à chaque exécution (piège de reproductibilité).

Pourquoi UCB explore-t-il plus ? - UCB ajoute un bonus d’incertitude aux bras peu explores - Un bras tire 54 fois a un gros bonus, même si sa moyenne est faible - Cette exploration est garantie optimale asymptotiquement

Lecon pratique : - ε-greedy est simple et souvent suffisant pour des problemes simples - UCB brille quand les différences entre bras sont subtiles - Le choix depend du compromis exploration/exploitation souhaite

Exercice 2 : Stratégies de Bandits - Comparaison Empirique

Contexte : Vous etes responsable d’un site web et devez choisir parmi 5 versions d’une page (A/B/n testing). Chaque version a un taux de conversion inconnu. Vous devez trouver la meilleure version tout en minimisant les pertes.

Données : 5 bras avec moyennes vraies inconnues : [0.2, 0.4, 0.5, 0.6, 0.8]

Objectif : Implementer Thompson Sampling et comparer empiriquement les stratégies.

Étapes : 1. Implementer la stratégie Thompson Sampling (echantillonnage Beta) 2. Comparer epsilon-greedy (eps=0.05, 0.10, 0.20), UCB1, et Thompson 3. Executer chaque stratégie sur T=500 pas et calculer le regret cumule 4. Afficher un tableau comparatif des résultats 5. Tester avec deux bras très proches (0.5 vs 0.51) et observer la difficulte

Indices : - Indice 1 : Thompson Sampling echantillonne Beta(alpha_i, beta_i) par bras, ou alpha = succes+1, beta = echecs+1 - Indice 2 : Pour des recompenses gaussiennes, approximer en seuillant a [0,1] pour le comptage succes/echec - Indice 3 : Le regret cumule = somme(mu* - reward_t) mesure la perte totale par rapport a l’optimal

// Exercice : Strategies de Bandits - Comparaison Empirique

// TODO 1 : Implementer la strategie Thompson Sampling
// Indice : Maintenir des counts de succes/echec (alpha, beta) par bras
// A chaque pas, echantillonner Beta(alpha_i, beta_i) pour chaque bras
// Choisir le bras avec le plus grand echantillon
// Mettre a jour alpha/beta selon la recompense obtenue

public class ThompsonSampling : IBanditStrategy
{
    public string Name => "Thompson Sampling";

    public int SelectArm(int[] counts, double[] sumRewards)
    {
        // TODO etudiant : implementer Thompson Sampling
        // Indice : utiliser les statistiques par bras pour parametriser Beta(alpha, beta)
        // Pour un bras avec n tirages et somme S, on peut estimer alpha et beta
        return 0;  // TODO etudiant : retourner le bras selectionne
    }
}

// TODO 2 : Comparer toutes les strategies sur un bandit a 5 bras
double[] vraiesMoyennes = { 0.2, 0.4, 0.5, 0.6, 0.8 };
var banditEx = new MultiArmedBandit(vraiesMoyennes);
var strategiesEx = new IBanditStrategy[] {
    new EpsilonGreedy(0.05),
    new EpsilonGreedy(0.10),
    new EpsilonGreedy(0.20),
    new UCB(),
    new ThompsonSampling()
};

Console.WriteLine("=== Exercice : Comparaison de Strategies ===\n");
Console.WriteLine($"Bandit a {vraiesMoyennes.Length} bras, moyennes vraies inconnues");
Console.WriteLine($"Meilleure moyenne : {vraiesMoyennes.Max()}\n");

// TODO 3 : Executer chaque strategie sur T=500 pas et calculer le regret cumule
int T = 500;
// Indice : même structure que la simulation precedente
// Pour chaque strategie, tracker le regret cumule = somme (mu* - reward_t)

// TODO 4 : Afficher un tableau comparatif
// Colonnes : Strategie | Recompense totale | Regret cumule | Tirages du meilleur bras

// TODO 5 : Que se passe-t-il si deux bras ont des moyennes très proches ?
// Indice : tester avec moyennes = {0.5, 0.51, 0.3, 0.2, 0.1}
Console.WriteLine("Exercice a completer");

=== Exercice : Comparaison de Strategies ===

Bandit a 5 bras, moyennes vraies inconnues
Meilleure moyenne : 0,8

Exercice a completer

Visualisation : Structure du POMDP

Différence MDP vs POMDP :

MDP (etat observable):
  s_0 ──→ s_1 ──→ s_2 ──→ ...
   ↑       ↑       ↑
  a_0     a_1     a_2

POMDP (etat cache):
  s_0 ──→ s_1 ──→ s_2 ──→ ...     (etats caches)
   │       │       │
   ↓       ↓       ↓
  o_0     o_1     o_2              (observations)
   ↑       ↑       ↑
  a_0 ←── a_1 ←── a_2              (actions basees sur observations)

Problème du Tigre - Structure graphique :

                 ┌─────────────────────────────────────┐
                 │      BELIEF STATE b(s)             │
                 │  P(tigre_gauche) = 0.5 (initial)   │
                 └────────────┬────────────────────────┘
                              │
              ┌───────────────┼───────────────┐
              │               │               │
         ┌────▼────┐    ┌─────▼─────┐   ┌─────▼─────┐
         │ Ouvrir  │    │  Ouvrir   │   │  Ecouter  │
         │ Gauche  │    │  Droite   │   │           │
         └────┬────┘    └─────┬─────┘   └─────┬─────┘
              │               │               │
         EU = -45         EU = -45         EU = -1 + VoI
              │               │               │
         [terminal]      [terminal]       [continue]
                                               │
                                    ┌──────────┴──────────┐
                                    │                     │
                              ┌─────▼─────┐         ┌─────▼─────┐
                              │ Bruit_G   │         │ Bruit_D   │
                              │ (P=0.85   │         │ (P=0.15   │
                              │ si TG)    │         │ si TG)    │
                              └─────┬─────┘         └─────┬─────┘
                                    │                     │
                              b' = 0.85              b' = 0.15

La valeur d’ecouter vient de la reduction d’incertitude : après observation, on peut prendre une meilleure decision.

Les mêmes structures, rendues sous forme de graphes. MDP vs POMDP — dans un POMDP, l’état réel est caché et la politique ne dispose que d’observations bruitées :

flowchart TB
    subgraph MDP["MDP — état observable"]
        direction LR
        M0["s₀"] -->|a₀| M1["s₁"] -->|a₁| M2["s₂"] --> MX["…"]
    end
    subgraph POMDP["POMDP — état caché, observations bruitées"]
        direction TB
        P0["s₀ caché"] --> P1["s₁ caché"] --> P2["s₂ caché"]
        P0 --> O0["o₀"]
        P1 --> O1["o₁"]
        P2 --> O2["o₂"]
        O0 --> PI["politique π(a | o₀…oₜ)"]
        O1 --> PI
        O2 --> PI
    end
    classDef obs fill:#cfe2ff,stroke:#084298,color:#052c65
    classDef hidden fill:#e2e3e5,stroke:#41464b,color:#1b1e21
    classDef pol fill:#d1e7dd,stroke:#0f5132,color:#052e16
    class M0,M1,M2,O0,O1,O2 obs
    class P0,P1,P2 hidden
    class PI pol

Problème du Tigre — l’arbre de décision sur l’état de croyance b(s) :

flowchart TD
    B["BELIEF STATE b(s)<br/>P(tigre gauche) = 0.5"]
    B --> OG["Ouvrir Gauche"]
    B --> OD["Ouvrir Droite"]
    B --> EC["Écouter"]
    OG --> EUG["EU = -45 · terminal"]
    OD --> EUD["EU = -45 · terminal"]
    EC --> EUE["EU = -1 + VoI · continue"]
    EUE --> BG["Bruit_G · P=0.85 si tigre gauche"]
    EUE --> BD["Bruit_D · P=0.15 si tigre gauche"]
    BG --> BPG["b' = 0.85"]
    BD --> BPD["b' = 0.15"]
    classDef belief fill:#cfe2ff,stroke:#084298,color:#052c65
    classDef open fill:#f8d7da,stroke:#842029,color:#2c0b0e
    classDef listen fill:#d1e7dd,stroke:#0f5132,color:#052e16
    class B,BPG,BPD belief
    class OG,OD,EUG,EUD open
    class EC,EUE,BG,BD listen

Lecture. Ouvrir une porte est terminal (gain immédiat mais risqué : EU = -45) ; écouter coûte peu (EU = -1) et rapporte de l’information — c’est la value of information (VoI). L’observation bruitée met à jour la croyance (b = 0.5 → b' = 0.85 ou 0.15), et c’est sur cette croyance affinée qu’une décision d’ouverture devient bien meilleure. Un POMDP se résout ainsi dans l’espace continu des croyances, pas dans l’espace discret des états.

Trois formulations du problème de bandits

La théorie des bandits distingue trois natures de sequences de recompenses, chacune associant une famille d’algorithmes optimale :

Formulation	Nature des recompenses	Stratégie optimale	Principe
Stochastique	Distribution inconnue, i.i.d.	UCB (Upper Confidence Bound)	Optimisme face a l’incertitude : construire des bornes superieures sur les moyennes
Adversariale	Choisis arbitrairement par un adversaire	Hedge / Exp3	Maintenir et mettre a jour une distribution de probabilités sur les bras
Markovienne	Transitions d’etat connues	Indice de Gittins	Index indépendant par bras, optimal sous discount

Pourquoi cette distinction ?

• Si les recompenses sont i.i.d. (stochastique), l’incertitude se reduit avec les tirages : UCB exploite cette propriete.
• Si un adversaire contrôle les recompenses, il peut penaliser toute stratégie déterministe : Hedge maintient une probabilité de melange.
• Si les bras ont une structure Markovienne (etats internes et transitions connues), chaque bras est un petit MDP : Gittins decompose le problème en K sous-problemes independants.

Cette section se concentre sur la formulation Markovienne et l’indice de Gittins, qui est le cadre le plus structure et le plus elegant.

Cadre SFABP : Famille Simple de Processus Bandits Alternatifs

L’indice de Gittins s’inscrit dans le cadre formel des SFABP (Simple Family of Alternative Bandit Processes). Ce formalisme précis est essentiel pour comprendre pourquoi la decomposition est possible.

Définition : On dispose de K processus bandits independants. Chacun evolue dans un espace d’etats denombrable. A chaque instant, on choisit un seul processus :

• Continuer le processus choisi : on recoit une recompense et son etat transite
• Geler les autres processus : pas de recompense, l’etat reste fixe

Formellement : Soit \(B_1, B_2, \ldots, B_K\) les K bandits. A l’instant \(t\), on applique le contrôle au bandit \(a_t\) :

\[\text{Recompense : } R_{a_t}(s_{a_t})\] \[\text{Transition : } s_{a_t} \to s' \text{ avec proba } P(s' | s_{a_t})\] \[\text{Autres bandits : etats gels (inchanges)}\]

Objectif : Maximiser la somme infinie escomptee :

\[V^\pi = \mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t R_{a_t}(s_{a_t})\right]\]

Pourquoi la programmation dynamique classique echoue :

L’espace d’etat conjoint est le produit cartesien \(S_1 \times S_2 \times \cdots \times S_K\). Pour K bandits avec \(|S_i|\) etats chacun :

\[\text{Nombre de politiques stationnaires} = \prod_{i=1}^{K} |A_i|^{|S_i|}\]

Cette explosion combinatoire rend la programmation dynamique directe inapplicable. L’apport de Gittins est de reduire ce problème a K calculs independants d’un index scalaire par etat.

Preuve par les “prevailing charges” (charges prevalentes)

L’optimalite de la politique de Gittins peut etre demontree de maniere constructive via l’argument des charges prevalentes. Cette preuve, dûe a Weber (1992), est particulierement elegante car elle construit une borne supérieure et montre qu’elle est atteinte.

Idees cles :

1. Charge prevalente \(c(s)\) : un cout fixe associe a l’etat \(s\) d’un bras. C’est le “loyer” que l’on paie pour continuer a jouer ce bras.

2. Charge equitable (fair charge) : le niveau de charge pour lequel on est indifferent entre arreter immediatement ou continuer au moins un tour puis s’arreter optimalement. Formellement :

\[\lambda(s) = \sup_{\tau \geq 1} \frac{\mathbb{E}\left[\sum_{t=0}^{\tau-1} \gamma^t R_t \mid s_0 = s\right]}{\mathbb{E}\left[\sum_{t=0}^{\tau-1} \gamma^t \mid s_0 = s\right]}\]

3. Evolution de la charge prevalente : on initialise \(c_0(s) = \lambda(s)\). Quand on continue a jouer un bras et que son etat transite, sa charge prevalente peut devenir inférieure a la charge equitable du nouvel etat. A ce moment, on reduit la charge prevalente au niveau de la nouvelle charge equitable :

\[c_t(s) = \min\{c_{t-1}(s),\, \lambda(s)\}\]

La suite \(c_t\) est donc decroissante.

Argument principal :

• Borne supérieure : Le joueur paie la charge prevalente du bras choisi. Par construction, le joueur ne peut pas faire mieux que “gagner sa vie” (zero profit espere), car chaque bras est indifferent a sa charge equitable :

\[\mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t R_{a_t}\right] \leq \mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^t c_t(s_{a_t})\right]\]

• La politique de Gittins atteint cette borne : En choisissant toujours le bras avec la plus forte charge prevalente (donc le plus fort indice de Gittins), on maximise la somme escomptee des charges prevalentes. Puisque les suites \(c_t\) sont decroissantes, l’entrelacement optimal est de toujours prendre le bras avec la plus forte charge.

Conclusion de la preuve :

La politique de Gittins est exactement optimale car elle atteint la borne supérieure. L’index est indépendant par bras (pas besoin de connaitre les etats des autres), ce qui rend la complexite lineaire en K plutot qu’exponentielle.

Référence : Gittins, Glazebrook & Weber (2011), Multi-armed Bandit Allocation Indices, Wiley. Adapted from Zhiyu He (2024).

9. Indice de Gittins

Le Theoreme Fondamental (Gittins, 1979)

L’indice de Gittins est l’un des résultats les plus elegants de la théorie de la decision. Il resout le problème du bandit multi-bras de maniere optimale et decomposable.

Theoreme : Pour un bandit multi-bras avec facteur de discount γ, la stratégie optimale est de toujours jouer le bras avec l’indice de Gittins le plus eleve.

Pourquoi est-ce remarquable ?

1. Reduction de complexite : Un problème a K bras interdependants devient K problemes independants
2. Optimalite garantie : Pas une heuristique, c’est la solution exacte
3. Index-ability : Chaque bras a un “prix” intrinseque

Définition intuitive

L’indice de Gittins d’un bras represente :

“Le prix equivalent certain” de ce bras - la recompense garantie pour laquelle on serait indifferent entre jouer ce bras et recevoir cette recompense fixe.

Plus formellement : c’est le taux d’intérêt critique au-dessus duquel on prefererait “encaisser” plutot que jouer le bras.

Calcul formel

L’indice est la solution d’un problème d’arret optimal :

\[G(s) = \sup_{\tau \geq 1} \frac{E\left[\sum_{t=0}^{\tau-1} \gamma^t R_t \mid s_0 = s\right]}{E\left[\sum_{t=0}^{\tau-1} \gamma^t \mid s_0 = s\right]}\]

• Le numerateur est la recompense totale actualisee jusqu’au temps d’arret τ
• Le denominateur est le “temps effectif” actualise
• On maximise sur tous les temps d’arret possibles

Implications pratiques

Aspect	Consequence
Exploration	Un bras incertain a un indice eleve (optimisme)
Exploitation	Un bras connu avec haute moyenne a un indice eleve
Compromis	L’indice equilibre automatiquement exploration/exploitation

Limitation

Le theoreme de Gittins s’applique sous des hypotheses spécifiques : - Discount γ < 1 (pas pour horizon fini sans discount) - Les bras sont independants (pas d’interactions) - Une seule action par étape (pas de contraintes de ressources)

La formalisation complète de l’indice de Gittins en Lean (companion natif) : DecInfer-08b-Lean-Gittins.

10. POMDPs : MDPs Partiellement Observables

Motivation

Dans un MDP standard, l’agent connait l’etat exact du monde a chaque instant. En pratique, c’est souvent irrealiste :

• Un robot ne voit pas a travers les murs
• Un medecin ne connait pas la vraie maladie, seulement les symptomes
• Un joueur de poker ne voit pas les cartes adverses

Extension du MDP

Dans un POMDP, l’agent ne connait pas l’etat exact. Il recoit des observations qui sont des indicateurs bruitees de l’etat réel.

Définition formelle

Un POMDP est un tuple (S, A, P, R, O, Ω, γ) :

Élément	Description
S, A, P, R, γ	Comme MDP (etats, actions, transitions, recompenses, discount)
O	Ensemble des observations possibles
Ω(o|s’, a)	Modèle de capteur : P(observation | nouvel etat, action)

Belief State : La Cle des POMDPs

Puisque l’agent ne connait pas l’etat, il doit maintenir une distribution de croyance (belief) b(s) sur tous les etats possibles.

b(s) = P(etat = s | historique des observations et actions)

Le belief state est une statistique suffisante : il resume toute l’information pertinente de l’historique.

Mise a jour du Belief State

Après avoir fait action a et observe o, le nouveau belief b’ est :

\[b'(s') = \eta \cdot \Omega(o|s', a) \sum_s P(s'|s, a) b(s)\]

ou η est une constante de normalisation.

C’est exactement une mise a jour bayesienne ! Le POMDP est donc naturellement lie a l’inference probabiliste.

Plans conditionnels

La politique d’un POMDP n’est pas s → a comme dans un MDP, mais b → a ou equivalemment un arbre de decision :

        a1           <- Action initiale
       /  \
     o1    o2        <- Observations possibles
     |      |
    a2     a3        <- Actions conditionnelles
   / \    / \
  o1 o2  o1 o2
  ...

Complexite

Les POMDPs sont PSPACE-complete a resoudre exactement. En pratique, on utilise : - Point-Based Value Itération (PBVI) - SARSOP - Monte Carlo Tree Search (MCTS) - Ou on approxime par des MDP avec belief states discrets

// POMDP simple : Tigre derriere une porte

Console.WriteLine("=== POMDP : Probleme du Tigre ===\n");
Console.WriteLine("Deux portes : gauche (G) et droite (D)");
Console.WriteLine("Un tigre est cache derriere l'une des portes.");
Console.WriteLine("Actions : Ouvrir G, Ouvrir D, Ecouter\n");

// Etats : tigre gauche (TG), tigre droite (TD)
// Actions : ouvrir_gauche, ouvrir_droite, ecouter
// Observations (si ecouter) : bruit_gauche, bruit_droite

double pCorrectHearing = 0.85; // P(bruit_gauche | tigre_gauche)
double rewardTresor = 10;
double rewardTigre = -100;
double costEcoute = -1;

// Belief state : b = P(tigre_gauche)
double b = 0.5; // Prior uniforme

Console.WriteLine($"Belief initial : P(tigre gauche) = {b:P0}\n");

// Fonction de valeur pour chaque action
double EU_ouvrirGauche(double belief) => 
    belief * rewardTigre + (1 - belief) * rewardTresor;

double EU_ouvrirDroite(double belief) => 
    belief * rewardTresor + (1 - belief) * rewardTigre;

// Pour ecouter, on doit calculer la valeur esperee apres observation
// (simplifie ici)

Console.WriteLine("Utilites esperees :");
Console.WriteLine($"  E[U(ouvrir gauche) | b={b:P0}] = {EU_ouvrirGauche(b):F1}");
Console.WriteLine($"  E[U(ouvrir droite) | b={b:P0}] = {EU_ouvrirDroite(b):F1}");
Console.WriteLine($"  Ecouter : cout immediat = {costEcoute}, mais reduit l'incertitude\n");

// Simuler une sequence d'observations
Console.WriteLine("Simulation : 3 ecoutes donnent 'bruit gauche'\n");

for (int i = 0; i < 3; i++)
{
    // Mise a jour bayesienne apres observation "bruit gauche"
    // P(TG|bruit_g) = P(bruit_g|TG) * P(TG) / P(bruit_g)
    double pBruitGauche = b * pCorrectHearing + (1 - b) * (1 - pCorrectHearing);
    b = (pCorrectHearing * b) / pBruitGauche;
    
    Console.WriteLine($"Apres observation {i+1} : P(tigre gauche) = {b:P1}");
}

Console.WriteLine();
Console.WriteLine($"E[U(ouvrir gauche)] = {EU_ouvrirGauche(b):F1}");
Console.WriteLine($"E[U(ouvrir droite)] = {EU_ouvrirDroite(b):F1}");
Console.WriteLine();
Console.WriteLine($"=> Decision : OUVRIR DROITE (tigre probablement a gauche)");

=== POMDP : Probleme du Tigre ===

Deux portes : gauche (G) et droite (D)
Un tigre est cache derriere l'une des portes.
Actions : Ouvrir G, Ouvrir D, Ecouter

Belief initial : P(tigre gauche) = 50 %

Utilites esperees :
  E[U(ouvrir gauche) | b=50 %] = -45,0
  E[U(ouvrir droite) | b=50 %] = -45,0
  Ecouter : cout immediat = -1, mais reduit l'incertitude

Simulation : 3 ecoutes donnent 'bruit gauche'

Apres observation 1 : P(tigre gauche) = 85,0 %
Apres observation 2 : P(tigre gauche) = 97,0 %
Apres observation 3 : P(tigre gauche) = 99,5 %

E[U(ouvrir gauche)] = -99,4
E[U(ouvrir droite)] = 9,4

=> Decision : OUVRIR DROITE (tigre probablement a gauche)

Interpretation du problème du tigre (POMDP)

Evolution du belief state :

Étape	P(tigre gauche)	Decision optimale
Initial	50%	Indecis (EU = -45 pour les deux portes)
Après ecoute 1	85%	Encore incertain
Après ecoute 2	97%	Très confiant
Après ecoute 3	99.5%	Quasi-certain

Pourquoi ecouter plusieurs fois ? - Chaque ecoute coute -1 mais reduit l’incertitude - Après 3 ecoutes, EU(ouvrir droite) = +9.4 >> EU(ouvrir gauche) = -99.4 - Le cout total d’ecoute (3 x -1 = -3) est très inférieur au gain de certitude

Mise a jour bayesienne : - P(tigre gauche | bruit gauche) = P(bruit gauche | tigre gauche) x P(tigre gauche) / P(bruit gauche) - Avec P(bruit correct | position) = 85%, chaque observation “pousse” le belief

Point cle POMDP : - L’agent ne connait pas l’etat exact (position du tigre) - Il maintient une distribution de croyance (belief) - La decision optimale depend du belief, pas de l’etat réel

// Visualisation du factor graph pour le modèle de maintenance predictive
// En activant ShowFactorGraph, Infer.NET genere un fichier .gv

Console.WriteLine("=== Factor Graph du Modèle de Maintenance ===\n");

// Creer un modèle simple pour visualiser la structure
var engineViz = new InferenceEngine();
engineViz.Compiler.CompilerChoice = Microsoft.ML.Probabilistic.Compiler.CompilerChoice.Roslyn;

if (ShowFactorGraph)
{
    engineViz.ShowFactorGraph = true;
    engineViz.ModelName = "Model_MaintenancePOMDP";
}

// Modèle : Etat -> Observation
Range vizEtatRange = new Range(3).Named("vizEtatRange");
var vizPrior = Variable.Discrete(new double[] { 0.7, 0.2, 0.1 }).Named("etatPrior");
vizPrior.SetValueRange(vizEtatRange);

var vizObs = Variable.New<int>().Named("capteur");
vizObs.SetValueRange(new Range(2));

// Structure conditionnelle pour le modèle d'observation
using (Variable.Case(vizPrior, 0))
    vizObs.SetTo(Variable.Discrete(0.95, 0.05));
using (Variable.Case(vizPrior, 1))
    vizObs.SetTo(Variable.Discrete(0.30, 0.70));
using (Variable.Case(vizPrior, 2))
    vizObs.SetTo(Variable.Discrete(0.05, 0.95));

vizObs.ObservedValue = 1; // Observer "anormal"

var vizPosterior = engineViz.Infer<Discrete>(vizPrior);
Console.WriteLine($"Posterior apres observation 'anormal': {vizPosterior}");

// Afficher le factor graph si disponible
if (ShowFactorGraph && FactorGraphHelper.IsGraphvizAvailable())
{
    FactorGraphHelper.GetLatestFactorGraphHtml().DisplayAs("text/html");
}
else if (ShowFactorGraph)
{
    Console.WriteLine("\nNote: Installez Graphviz pour visualiser le factor graph.");
    Console.WriteLine("Fichier .gv genere dans le repertoire courant.");
}

=== Factor Graph du Modèle de Maintenance ===

Compiling model...done.
Posterior apres observation 'anormal': Discrete(0,1296 0,5185 0,3519)

Model_MaintenancePOMDP_09_23_26_09_16_38_75.svg

10bis. Belief State Updates avec Infer.NET

L’exemple précédent calculait les mises a jour du belief “a la main”. Avec Infer.NET, on peut automatiser cette inference bayesienne, ce qui devient precieux pour des modèles plus complexes.

Avantages d’Infer.NET pour les POMDPs

Aspect	Calcul manuel	Infer.NET
Formule	Ecrire Bayes explicitement	Automatique
Etats multiples	Combinatoire	Gere par le moteur
Observations multiples	Produits manuels	Modelisation naturelle
Incertitude sur paramètres	Très complexe	Hyper-priors possibles

Scénario : Maintenance predictive

Un système peut etre dans 3 etats : {Bon, Degrade, Defaillant}. A chaque pas de temps : - L’etat peut se degrader (Markov) - On observe un signal de capteur (bruite) - On decide : continuer, maintenance preventive, ou remplacement

---

Vision d’ensemble : De la decision one-shot aux systèmes adaptatifs

Ce notebook conclut la serie Decision Theory en faisant le pont vers le Reinforcement Learning :

Decisions One-Shot (DecInfer-01 a 07)
    |
    +-- Utilite et aversion au risque (DecInfer-01, 03)
    +-- Attributs multiples (DecInfer-04)
    +-- Diagrammes d'influence (DecInfer-05)
    +-- Valeur de l'information (DecInfer-06)
    +-- Robustesse et experts (DecInfer-07)
    |
    v
Decisions Séquentielles (DecInfer-08)
    |
    +-- MDPs : Etats connus, actions multiples
    +-- Bellman : Decomposition récursive
    +-- Bandits : Exploration/exploitation
    +-- POMDPs : Etats partiellement observables
    |
    v
Reinforcement Learning (Serie RL/)
    |
    +-- Q-Learning : Apprendre sans modèle
    +-- Deep RL : Approximation neuronale
    +-- Policy Gradient : Optimisation directe

Message cle : > La théorie de la decision fournit les fondements mathematiques (utilite, rationalite, Bellman) sur lesquels reposent les algorithmes modernes de RL. Comprendre ces concepts permet de mieux concevoir, debugger et ameliorer les systèmes d’apprentissage.

#load "../../Infer/SvgChartHelper.cs"

// Belief State Updates avec Infer.NET : Maintenance Predictive

using Microsoft.ML.Probabilistic.Math;

// Historique des croyances pour la visualisation (Prior + chaque pas de temps)
var beliefHist = new List<(string Label, double[] Probs)>();

Console.WriteLine("=== Belief State Updates avec Infer.NET ===\n");
Console.WriteLine("Scénario : Maintenance predictive d'un système\n");

// Définition des etats et observations
int nEtats = 3;
Range etatRange = new Range(nEtats).Named("etatRange");
string[] etatsNom = { "Bon", "Degrade", "Defaillant" };

// Matrice de transition (degradation naturelle)
double[,] transMatrix = {
    // vers:    Bon    Degrade  Defaillant
    /* Bon */    { 0.90,  0.08,    0.02 },
    /* Deg */    { 0.00,  0.85,    0.15 },
    /* Def */    { 0.00,  0.00,    1.00 }  // Absorbant
};

// Modèle d'observation : capteur de vibration (0=normal, 1=anormal)
double[,] obsMatrix = {
    // P(obs | etat)  Normal  Anormal
    /* Bon */       { 0.95,   0.05 },
    /* Deg */       { 0.30,   0.70 },
    /* Def */       { 0.05,   0.95 }
};

// Utilites des decisions
double[,] utilities = {
    //                  Bon     Degrade  Defaillant
    /* Continuer */   { 100,    50,      -500 },  // Risque si defaillant
    /* Maintenance */ { -20,    80,       -50 },  // Preventif, moins de gain si bon
    /* Remplacer */   { -100,  -100,       50 }   // Couteux mais resout defaillance
};
string[] actionsNom = { "Continuer", "Maintenance", "Remplacer" };

// === Simulation avec Infer.NET ===
// Observations sequentielles : Normal, Anormal, Anormal
int[] observations = { 0, 1, 1 };

// Belief initial (le système vient d'etre installe => Bon)
double[] belief = { 0.95, 0.04, 0.01 };

Console.WriteLine("Belief initial :");
for (int e = 0; e < nEtats; e++)
    Console.WriteLine($"  P({etatsNom[e]}) = {belief[e]:P1}");
beliefHist.Add(("Prior", belief.ToArray()));
Console.WriteLine();

// Boucle de mise a jour
for (int t = 0; t < observations.Length; t++)
{
    Console.WriteLine($"=== Pas de temps {t + 1} ===");
    
    // 1. Prediction (transition)
    double[] predicted = new double[nEtats];
    for (int sPrime = 0; sPrime < nEtats; sPrime++)
    {
        for (int s = 0; s < nEtats; s++)
            predicted[sPrime] += transMatrix[s, sPrime] * belief[s];
    }
    
    Console.WriteLine("Apres prediction (transition) :");
    for (int e = 0; e < nEtats; e++)
        Console.WriteLine($"  P({etatsNom[e]}) = {predicted[e]:P1}");
    
    // 2. Correction (observation) avec Infer.NET
    Variable<int> etatVar = Variable.Discrete(predicted).Named("etat");
    etatVar.SetValueRange(etatRange);
    
    Variable<int> obsVar = Variable.New<int>().Named("observation");
    obsVar.SetValueRange(new Range(2));
    
    // Modèle d'observation
    using (Variable.Case(etatVar, 0))
        obsVar.SetTo(Variable.Discrete(obsMatrix[0, 0], obsMatrix[0, 1]));
    using (Variable.Case(etatVar, 1))
        obsVar.SetTo(Variable.Discrete(obsMatrix[1, 0], obsMatrix[1, 1]));
    using (Variable.Case(etatVar, 2))
        obsVar.SetTo(Variable.Discrete(obsMatrix[2, 0], obsMatrix[2, 1]));
    
    // Observation
    int obs = observations[t];
    obsVar.ObservedValue = obs;
    
    // Inference
    InferenceEngine engineBelief = new InferenceEngine();
    engineBelief.Compiler.CompilerChoice = Microsoft.ML.Probabilistic.Compiler.CompilerChoice.Roslyn;
    
    var posteriorEtat = engineBelief.Infer<Discrete>(etatVar);
    Vector probs = posteriorEtat.GetProbs();
    
    Console.WriteLine($"Observation : {(obs == 0 ? "Normal" : "Anormal")}");
    Console.WriteLine("Apres correction (Bayes via Infer.NET) :");
    double[] probsArr = new double[nEtats];
    for (int e = 0; e < nEtats; e++)
    {
        probsArr[e] = probs[e];
        Console.WriteLine($"  P({etatsNom[e],-10}) = {probs[e]:P1}");
    }
    beliefHist.Add(($"t={t + 1} ({(obs == 0 ? "Normal" : "Anormal")})", probsArr));
    
    // 3. Decision basee sur le belief
    double[] EU = new double[3];
    for (int a = 0; a < 3; a++)
    {
        for (int e = 0; e < nEtats; e++)
            EU[a] += probs[e] * utilities[a, e];
    }
    
    int bestAction = EU.Select((v, i) => (v, i)).OrderByDescending(x => x.v).First().i;
    
    Console.WriteLine("Utilites esperees :");
    for (int a = 0; a < 3; a++)
        Console.WriteLine($"  E[U({actionsNom[a],-12})] = {EU[a],7:F1}");
    Console.WriteLine($"=> Decision : {actionsNom[bestAction]}");
    Console.WriteLine();
    
    // Mettre a jour le belief pour le prochain pas
    // Note: GetProbs() retourne un Vector, on copie manuellement
    for (int e = 0; e < nEtats; e++)
        belief[e] = probs[e];
}

// Visualisation SVG inline : evolution des croyances (Belief State Updates).
// La version Plotly-CDN precedente rendait BLANC en static (GitHub sandbox les <script src=cdn.plot.ly>).
// Technique C548-L2 : SVG inline via SvgChartHelper.cs (#6942 MERGED), zero-dependance NuGet.
// L'API Bar() ne suporte pas les barres groupees (un seul array de valeurs), donc on deploie
// 3 Bar() distincts (un par etat) montrant l'evolution temporelle de chaque probabilité.
// La legende textuelle ci-dessous preserve le role pedagogique de la viz d'origine
// (anomalies successives font chuter P(Bon) et basculer la decision Continuer -> Maintenance -> Remplacer).

// Labels X partages (Prior + chaque pas de temps)
var xLabels49 = beliefHist.Select(b => b.Label).ToArray();
{
    // Serie 1 : Bon (devrait chuter avec anomalies)
    var yBon = beliefHist.Select(b => Math.Round(b.Probs[0], 3)).ToArray();
    display(SvgChartHelper.Bar("Evolution de P(Bon) - chute avec anomalies successives", xLabels49, yBon));
    Console.WriteLine("  [Bon] les observations 'Anormal' font chuter P(Bon) sous 0.05 au 3e pas.");

    // Serie 2 : Degrade (devrait monter puis transferer vers Defaillant)
    var yDeg = beliefHist.Select(b => Math.Round(b.Probs[1], 3)).ToArray();
    display(SvgChartHelper.Bar("Evolution de P(Degrade) - pic intermediaire avant Defaillant", xLabels49, yDeg));
    Console.WriteLine("  [Degrade] bond au 2e pas (0.53) puis legere hausse (0.56) avant transfert vers Defaillant.");

    // Serie 3 : Defaillant (devrait monter lineairement)
    var yDef = beliefHist.Select(b => Math.Round(b.Probs[2], 3)).ToArray();
    display(SvgChartHelper.Bar("Evolution de P(Defaillant) - hausse avec les 'Anormal'", xLabels49, yDef));
    Console.WriteLine("  [Defaillant] 0.01 (prior) -> 0.002 (apres 'Normal') -> 0.42 (apres 2 'Anormal') : non monotone.");
}

Console.WriteLine("=== Resume ===");
Console.WriteLine("Les observations 'Anormal' successives ont fait augmenter P(Degrade),");
Console.WriteLine("declenchant le passage de 'Continuer' a 'Maintenance'.");
Console.WriteLine("\nC'est le principe de la maintenance predictive bayesienne !");

=== Belief State Updates avec Infer.NET ===

Scénario : Maintenance predictive d'un système

Belief initial :
  P(Bon) = 95,0 %
  P(Degrade) = 4,0 %
  P(Defaillant) = 1,0 %

=== Pas de temps 1 ===
Apres prediction (transition) :
  P(Bon) = 85,5 %
  P(Degrade) = 11,0 %
  P(Defaillant) = 3,5 %
Compiling model...done.
Observation : Normal
Apres correction (Bayes via Infer.NET) :
  P(Bon       ) = 95,9 %
  P(Degrade   ) = 3,9 %
  P(Defaillant) = 0,2 %
Utilites esperees :
  E[U(Continuer   )] =    96,8
  E[U(Maintenance )] =   -16,2
  E[U(Remplacer   )] =   -99,7
=> Decision : Continuer

=== Pas de temps 2 ===
Apres prediction (transition) :
  P(Bon) = 86,3 %
  P(Degrade) = 11,0 %
  P(Defaillant) = 2,7 %
Compiling model...done.
Observation : Anormal
Apres correction (Bayes via Infer.NET) :
  P(Bon       ) = 29,6 %
  P(Degrade   ) = 52,7 %
  P(Defaillant) = 17,7 %
Utilites esperees :
  E[U(Continuer   )] =   -32,3
  E[U(Maintenance )] =    27,4
  E[U(Remplacer   )] =   -73,5
=> Decision : Maintenance

=== Pas de temps 3 ===
Apres prediction (transition) :
  P(Bon) = 26,6 %
  P(Degrade) = 47,2 %
  P(Defaillant) = 26,2 %
Compiling model...done.
Observation : Anormal
Apres correction (Bayes via Infer.NET) :
  P(Bon       ) = 2,2 %
  P(Degrade   ) = 55,8 %
  P(Defaillant) = 42,0 %
Utilites esperees :
  E[U(Continuer   )] =  -179,7
  E[U(Maintenance )] =    23,2
  E[U(Remplacer   )] =   -37,1
=> Decision : Maintenance

  [Bon] les observations 'Anormal' font chuter P(Bon) sous 0.05 au 3e pas.

  [Degrade] bond au 2e pas (0.53) puis legere hausse (0.56) avant transfert vers Defaillant.

  [Defaillant] 0.01 (prior) -> 0.002 (apres 'Normal') -> 0.42 (apres 2 'Anormal') : non monotone.
=== Resume ===
Les observations 'Anormal' successives ont fait augmenter P(Degrade),
declenchant le passage de 'Continuer' a 'Maintenance'.

C'est le principe de la maintenance predictive bayesienne !

Interpretation de la maintenance predictive bayesienne

Scénario simule : Observations = [Normal, Anormal, Anormal]

Evolution du belief et des decisions :

Pas	Observation	P(Bon)	P(Degrade)	P(Defaillant)	Decision
1	Normal	96%	4%	0.2%	Continuer (EU=97)
2	Anormal	30%	53%	18%	Maintenance (EU=27)
3	Anormal	2%	56%	42%	Maintenance (EU=23)

Ce que montre Infer.NET : - Le moteur calcule automatiquement les posterieurs bayesiens - La boucle prediction-correction est le coeur des filtres bayesiens (Kalman, particule)

Declenchement de la maintenance : - L’observation “Normal” au pas 1 renforce le belief que le système est bon - Les observations “Anormal” aux pas 2-3 degradent progressivement le belief - La decision passe de “Continuer” a “Maintenance” quand P(Degrade) + P(Defaillant) devient significatif

Application industrielle : - Ce pattern est utilise en maintenance predictive (Industry 4.0) - Les capteurs IoT fournissent des observations en continu - Le système decide automatiquement quand intervenir, avant la panne

Visualisation : Evolution du Belief State dans le Scénario de Maintenance

Le graphique ci-dessous montre comment les observations “anormales” successives modifient la distribution de croyance :

                          Evolution du Belief State
    
    P(Bon)         ███████████████████████████████████░░░░░  95%
    t=0 (initial)  Degrade ██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  4%
                   Defaill █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  1%
                          
    P(Bon)         ███████████████████████████████████████░░  96% (obs: Normal)
    t=1            Degrade ██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  4%
                   Defaill ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  0%
                          
    P(Bon)         ████████████░░░░░░░░░░░░░░░░░░░░░░░░░░░░░  30% (obs: Anormal)
    t=2            Degrade █████████████████████░░░░░░░░░░░░░░  53%
                   Defaill ███████░░░░░░░░░░░░░░░░░░░░░░░░░░░  18%
                          
    P(Bon)         █░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░   2% (obs: Anormal)
    t=3            Degrade ██████████████████████░░░░░░░░░░░░░  56%
                   Defaill █████████████████░░░░░░░░░░░░░░░░░░  42%
    
                   ─────────────────────────────────────────►
                   Meilleure action :
                   t=0-1: Continuer (EU≈96)
                   t=2-3: Maintenance (EU≈23-27)

Observations cles : 1. Une observation “Normal” renforce P(Bon) (capteur fiable si système ok) 2. Deux observations “Anormal” font basculer vers P(Degrade) majoritaire 3. La decision optimale passe de “Continuer” a “Maintenance” quand l’incertitude sur l’etat est resolue

11. Lien avec la Serie RL

Ce notebook : Concepts fondamentaux

• MDPs et équations de Bellman
• Méthodes tabulaires (Value Itération, Policy Itération)
• Concepts théoriques (Gittins, POMDPs)

Serie RL (MyIA.AI.Notebooks/RL/) : Implementations avancees

Notebook	Contenu
RL-1-Introduction	Q-Learning tabulaire
RL-2-DeepRL	DQN avec reseaux de neurones
RL-3-PolicyGradient	REINFORCE, Actor-Critic
RL-4-AdvancedMethods	PPO, A2C, SAC
RL-5-Applications	Gym, Stable-Baselines3

---

Exercice 3 : MDP et Itération de Valeur

Objectifs : 1. Implementer un MDP simple (grille 3x3) 2. Appliquer l’itération de valeur pour trouver la politique optimale 3. Analyser la convergence et l’impact de gamma

Contexte : Un robot doit naviguer dans une grille 3x3 pour atteindre un objectif. Chaque case est un etat, le robot peut se deplacer (haut, bas, gauche, droite).

Questions de reflexion : 1. Combien d’itérations sont necessaires pour converger avec gamma=0.9 ? 2. Que se passe-t-il si gamma est trop proche de 1 ? 3. Comment gerer les etats terminaux ?

---

Navigation : << Retour au README

// Exercice : MDP et Iteration de Valeur

// TODO: Définir les etats de la grille 3x3

// TODO: Définir les actions possibles

// TODO: Définir la matrice de transition P[s'|s,a]

// TODO: Définir les recompenses R[s,a]

// TODO: Implementer l'iteration de valeur

// TODO: Extraire la politique optimale

// TODO: Afficher les résultats
Console.WriteLine("Exercice a completer");

Exercice a completer

12. Resume

Concept	Description
MDP	(S, A, P, R, γ) - cadre formel pour decisions séquentielles
Bellman	V*(s) = max_a [R + γ Σ P V*]
Value Itération	Mise a jour iterative de V jusqu’a convergence
Policy Itération	Évaluation + Amelioration alternees
Reward Shaping	F = γΦ(s’) - Φ(s) preserve la politique optimale
Bandits	Exploration vs Exploitation
Gittins	Indice optimal pour bandits avec discount
POMDP	MDP avec observations bruitees, belief states

---

Pour aller plus loin

Si vous voulez…	Consultez…
Deep Reinforcement Learning	Serie MyIA.AI.Notebooks/RL/
Implementations PyTorch/TF	Stable-Baselines3
Théorie avancee	Sutton & Barto “Reinforcement Learning”

---

Fin de la Serie Decision Theory

Felicitations ! Vous avez termine les notebooks sur la Decision Theory.

Recapitulatif de la serie 14-20

#	Titre	Concepts cles
14	Utility Foundations	Axiomes VNM, loteries, agent rationnel
15	Utility Money	CARA/CRRA, aversion au risque, dominance
16	Multi-Attribute	MAUT, indépendance, SMART
17	Decision Networks	Influence diagrams, arcs informationnels
18	Value of Information	EVPI, EVSI, droits de forage
19	Expert Systems	Minimax, regret, robustesse
20	Sequential	MDPs, bandits, POMDPs

---

Références

• Bellman (1957) : Dynamic Programming
• Gittins (1979) : Bandit Processes and Dynamic Allocation Indices
• Ng, Harada, Russell (1999) : Policy Invariance Under Reward Transformations
• Kaelbling, Littman, Cassandra (1998) : Planning and Acting in Partially Observable Stochastic Domains
• Sutton & Barto (2018) : Reinforcement Learning: An Introduction