Graine du générateur :

set.seed(5)

Questions preliminaires

Intuitions

Un tirage d’une deux premières stratégies suit une loi de Bernouilli (succès ou pas) de probabilité \(p_A\) et \(p_b\), l’espérance du gain obtenu en jouant \(T\) fois sur :

  • la machine A est de \(T * p_A\)
  • la machine B est de \(T * p_B\)
  • la machine A et B est de \(\frac{T}{2}(p_A + p_B)\)

Résultats

Stratégie 1 et 2

Le gain de tirage d’une machine \(A\) ou \(B\) suit un loi de bernouilli \(B(1, p_i)\) où \(i \in \{A, B\}\). En répétant l’experience \(T\) fois, le gain de cette succession de partie suit donc une loi binomial \(B(T, p_i)\) où \(i \in \{A, B\}\). L’espérance de cette loi est alors \(T * p_i\).

On peut démontrer ce résultat :

\[\begin{align*} \mathbb{E}[G_m(T)] &= \mathbb{E}\Big[\sum_{t=0}^{T} X_m(t),t \Big] \\ &= \sum_{t=0}^{T}\mathbb{E}[X_m(t),t ] \text{ car l'espérance d'une somme est la somme des espérances} \\ &= \sum_{t=0}^{T}p_i \text{ car $X_m(t),t$ suit une loi de bernouilli} \\ &= T * p_i \end{align*}\]

Pour \(i \in \{A, B\}\) on en déduit que :

  • En jouant uniquement sur la machine \(A\), l’espérance est \(\mathbb{E}[G_m(T)] = T * p_A\)
  • En jouant uniquement sur la machine \(B\), l’espérance est \(\mathbb{E}[G_m(T)] = T * p_B\)

Stratégie 3

Cette fois-ci il y a \(50%\) de chance de jouer sur la machine A ou sur la machine B.

\[\begin{align*} \mathbb{E}[G_m(T)] &= \mathbb{E}\Big[\sum_{t=0}^{T} X_{m(t)} \Big] \\ &= \sum_{t=0}^{T}\mathbb{E}[X_{m(t)} ] \text{ car l'espérance d'une somme est la somme des éspérances} \\ &= \sum_{t=0}^{T} \frac{1}{2}(p_A + p_B) \\ &= \frac{T}{2} (p_A + p_B) \end{align*}\]

Justification de la quantité \(R_m(t)\)

\(R_m(t) = p_A - \frac{\mathbb{E}[G_m(t)]}{t}\)

Cette quantité est la différence entre l’espérance de gain obtenue en jouant uniquement sur la machine \(A\) et entre l’espérance d’avoir joué en utilisant la stratégie \(m\) (\(\mathbb{E}[G_m(t)]\) étant l’esperance de gain sur \(t\) parties, on divise cette quantité par \(t\) pour la ramener sur une partie pour la comparer à l’espérance d’une partie sur la machine \(A\)).

Programme de simulation

library(ggplot2)
library(shiny)

simulation = function(strategie, Tmax=1000, nb_trajectoire=100, pa=0.65, pb=0.55, epsilon=0.05, epsilon_cir=0.1) {
  result <- data.frame()
  
  for(nPartie in 1:nb_trajectoire) {
    regret <- c()
    gain <- c()
  
    switch(strategie,
      ml = {
        # On choisit le même nombre de tirage pour la machine A et B
        # utile si Tmax impaire pour ne favoriser aucune machine. 
        nbTirageEvalMachine = ceiling(0.5*Tmax*epsilon) # Arrondie vers le haut 
        
        # Phase d'évaluation de la meilleur machine
        evaluerA <- rbinom(nbTirageEvalMachine, 1 , pa)
        evaluerB <- rbinom(nbTirageEvalMachine, 1 , pb)
        gain <- as.vector(rbind(evaluerA, evaluerB)) # On "intercalle" les deux précédentes suite de tirage
        
        # Reste des parties (choix de la machine + simulation)
        if(sum(evaluerA)>sum(evaluerB)) {
          p_choisi = pa
        }else if(sum(evaluerA) < sum(evaluerB)) {
          p_choisi = pb
        }else { # Gain cumulé egaux, on choisit au hasard entre les deux machines
          p_choisi = if (runif(1) < 0.5) pa else pb;
        }
        gain <- c(gain, rbinom(Tmax - (nbTirageEvalMachine*2), 1 , p_choisi))
      },
      
      mg = {
        succesA = 0
        tentativeA = 1
        succesB = 0
        tentativeB = 1
  
        for(i in 1:Tmax) {
          # On chosis quelle machine on va utiliser
          if((succesA/tentativeA) == (succesB/tentativeB)) {
            p_choisi <- if(runif(1)<0.5) pa else pb
          }else {
            if((succesA/tentativeA) > (succesB/tentativeB)) {
              p_choisi = if (runif(1)<(1-epsilon_cir)) pa else pb 
            }else {
              p_choisi = if (runif(1)<(1-epsilon_cir)) pb else pa
            }
          } 
          
          gain[i] = rbinom(1,1,p_choisi)
          
          # On met à jour les succès / tentatives
          if(p_choisi == pa) {
            succesA = succesA + gain[i]
            tentativeA = tentativeA + 1
          }else {
            succesB = succesB + gain[i]
            tentativeB = tentativeB + 1
          }
        }
      },
      
      mt = {
        succes_a = 0
        echec_a = 0
        succes_b = 0
        echec_b = 0
        
        for(i in 1:Tmax) {
          # Probabilités vraisemblables
          estim_pa = rbeta(1, succes_a+1, echec_a+1) 
          estim_pb = rbeta(1, succes_b+1, echec_b+1)
          
          # On choisit la machine en fonction des probabilités vraisemblables
          if(estim_pa > estim_pb) {
            gain[i] <- rbinom(1,1,pa)
            succes_a <- succes_a + gain[i]
            echec_a <- echec_a + (1-gain[i])
          }else { # Pas de test pas l'egalité car rbeta est une loi continue, donc en théorie pas d'égalité
            gain[i] <- rbinom(1,1,pb)
            succes_b <- succes_b + gain[i]
            echec_b <- echec_b + (1-gain[i])
          }
        }
      }
    )#FIN DU SWITCH
    
    # Calcul du regret et stockage dans un dataframe
    regret <-pa - cumsum(gain)/(1:Tmax) 
    result <- rbind(result, data.frame(t=1:Tmax, regret, id=nPartie))
  }
  return(result)
}


# Fonction d'affichage
graphique = function(df) {
  m = aggregate(df$regret, by=list(df$t), mean)
  moyennedf <- data.frame(t=m$Group.1, moy=m$x)
  ggplot() + geom_line(data=df, aes(x=t, y=regret, group=id), alpha=0.1) + geom_line(data=moyennedf, aes(x=t, y=moy), color="red")
}

Intuitions sur les différentes stratégies

Stratégie \(m_l\)

La stratégie me semble plutôt bonne (surtout si on a un grand nombre de tirage “disponible”) mais clairement pas optimale pour plusieurs raisons. En effet il faut que \(\epsilon T\) soit assez grand pour determiner la meilleure machine (par exemple si on fait 100 tirages avec \(\epsilon = 0.1\), seulement 5 tirages sur chaque machine permet de choisir la meilleur machine, ce qui ne me parait pas suffisant pour choisir la bonne machine). En revanche sur un grand nombre de tirage ça me parait être une bonne méthode pour choisir la bonne machine (si après les \(\epsilon T\) tirages, la bonne machine est choisi, on aura joué “seulement” \(\epsilon T / 2\) tirages sur la mauvaise machine. Sur des probabilités assez différentes, par exemple \(0.01\) et \(0.7\) on joue \(\epsilon T\) tirages avec pratiquement aucun gain mais on est pratiquement sûr de choisir la bonne machine ensuite. Sur des probabilités assez assez proches, on est assuré de ne pas joué sur une machine “pour rien”“, mais on risque beaucoup plus ensuite de chosir la machine la moins performante pour tous le reste des tirages).

Stratégie \(m_g\)

Cette stratégie me semble mieux que la précédente. Cependant, mon avis est surrement biaisé par le fait que j’ai tendance à penser que vous proposez des stratégies de plus en plus efficaces. Malgré tout, il me semble plus judicieux de réavaluer les performances des deux machines tout au long de la partie. On choisit toujours la meilleure machine, mais avec une probabilité \(\hat{\epsilon}\) de basculer sur l’autre machine pour réévaluer sa performance. \(\hat{\epsilon} = 0.1\) me semble un peu faible surtout pour le début de la partie, on pourrait en effet favoriser pendant beaucoup de tirages une machine moins performante, j’aurais tendance à legerement augmenter \(\hat{\epsilon}\) (par exemple entre \([0.15;0.20]\)) pour determiner avec plus de sûreté la meilleure machine, cependant au bout d’un certain nombre de tirage on peut penser que basculer d’une machine à l’autre pour réevaluer les performances est inutiles (le nombre de tentative devenant assez elevé les tirages n’auront plus beaucoup d’impact sur l’évluation des probabilités), il faudrait alors peut être un \(\epsilon\) qui varie avec le temps ou le nombre de tentative réalisé sur chaque machine.

Stratégie \(m_t\)

Cette stratégie reprend le même principe que précédement. Je suppose qu’on est invité à expliquer en quoi elle peut être mieux / moins bien que cette dernière. Je pense que cette stratégie est encore meilleure que la seconde car elle evalue la vraisemblance des probabilités, donc au début avec peu de tirage, on va laisser plus de chance aux machines pour evaluer leurs probabilités, ça rejoint un peu mon idée avec un \(\epsilon\) qui varie avec le temps pour être plus “laxiste” au début pour mieux determiner la meilleure machine.

Stratégie \(m_l\) : On apprend (un peu) puis on exploite

Quelques simulations de la stratégie avec différents paramètres

graphique(df = simulation("ml", epsilon=0.05))

graphique(df = simulation("ml", epsilon=0.15))

graphique(df = simulation("ml", epsilon=0.25))

graphique(df = simulation("ml", epsilon=0))

Epsilons testés : \(\{0.05, 0.15, 0.25, 0\}\)

Tout d’abord on remarque qu’il y a deux groupes de trajectoires différents, ce n’est pas étonnant, puisqu’on choisit après \(\epsilon T\) une machine pour tout le reste de la partie. En faisant varier \(\epsilon\) on peut observer différent scénarios assez evidents, plus epsilon est grand, plus la machine A est choisi (car plus de tirage pour estimer la meilleure machine) mais le gain total à tendance à diminuer (la moyenne converge moins vite vers 0). Enfin une dernière simulation a été faite avec \(\epsilon = 0\), sans surprise on a deux groupes de trajectoires de même nombre, en effet on choisit aléatoirement dès le début la machine A ou B pour tous le reste de la partie et ce 100 fois.

Stratégie \(m_g\) : On exploite mais on se force à toujours apprendre (un peu)

graphique(df = simulation("mg", epsilon_cir=0.1))

graphique(df = simulation("mg", epsilon_cir=0.15))

graphique(df = simulation("mg", epsilon_cir=0.3))

Epsilons circnflexes testés : \(\{0.1, 0.15, 0.3, 0\}\)

Pour \(\epsilon = 0.1\) :
Cette stratégie est meilleure que la précédente. Du fait qu’on ajuste tout au long de la partie le gain des deux machines il y a moins d’erreurs de choix de machine, la machine A est donc plus souvent choisi. On remaque tout de même les inquiétudes soulevées lors de mes intuitions il y a des trajectoires où la machine B a été favorisé tout le long de la partie. Cependant, en augmentant \(\hat{\epsilon}\) au délà de \(0.1\), il y a certes moins d’erreur de choix de machine, mais le gain total est de moins en moins bon (on le voit avec la moyenne ainsi qu’avec le bloc de trajectoire qui est plus haut selon l’ordonné)

Stratégie \(m_t\) : On tire au hasard en biaisant selon nos observations

graphique(df = simulation("mt"))

Pas de variations possibles (c’est la loi bêta qui s’en charge). C’est déjà un bon point pour cette stratégie (reste à voir si elle donne des résultats convainquants).

Cette stratégie est encore meilleure que la précédente. Il y a encore moins de trajectoires qui favorisent la machine B, la machine A est vraiment favorisée avec cette loi bêta. Cependant les trajectoires qui favorisent B, le favorise beaucoup plus que la précédente stratégie (puisque plus on avance dans la partie, plus on estime que B est meilleur que A avec certitude si on a pas de chance avec les tirages de A effectués, ça laisse alors de moins en moins de chance à A de s’imposer !).

Ce n’est pas surprenant que cette stratégie soit meileure d’après mes réflexions en amont, cette stratégie permet d’évaluer les probabilités de A et B avec plus de surêté au cours de la partie donc au bout d’un moment la machine la moins performante n’est plus choisit, ou beaucoup moins que pour la stratégie précédente.

Annexe : Quelques autres simulations et commentaires

Variation des probabilités

Avec des probabilité \(p_b\) eloignées de \(p_a\) :

p= 0.1
# par defaut, e = 0.05, ê = 0.1
graphique(df = simulation("ml", pb=p))

graphique(df = simulation("mg", pb=p))

graphique(df = simulation("mt", pb=p))

On remarque qu’on a toujours \(m_t > m_g > m_l\) (en terme de performance), et cette différence est d’ailleurs bien plus prononcée.

On remarque evidemment que la stratégie \(m_l\) comparée à précedemment évalue bien mieux la meilleure machine après la phase d’évaluation, cependant on remarque bien que la phase d’évalution est catastrophique pour le gain totale obtenue !

Avec ces différence de probabilité on remarque maintenant qu’avec des probabilités différentes la stratégie \(m_t\) est bien meilleure que la stratégie \(m_g\) ! En effet, avec la stratégie \(m_g\), même si on a estimé que la machine A était meilleure que la machine B, on a 1 chance sur 10 tout au long de la partie pour choisir la machine B qui est bien moins avantageuse que la machine A. La moyenne avec la stratégie \(m_g\) converge tout de même plus vite vers 0 mais en restant bien au dessus contrairement à la stratégie \(m_g\) où la moyenne se confond pratiquement avec l’axe des abscisses. On en conclut qu’il est vraiment préférable de choisir un paramètre prenant en compte le temps / nombre de tirages effectué (ici la loi bêta).

Variation du nombre de tirage

nbTirages= 100
graphique(df = simulation("ml", Tmax=nbTirages))

graphique(df = simulation("mg", Tmax=nbTirages))

graphique(df = simulation("mt", Tmax=nbTirages))

Première analyse très mathématique : les graphiques sont beaux.

D’après ces graphiques, la perfomance des stratégies n’est pas remise en cause avec un nombre de tirage peu elevé, la stratégie semble légérement meilleure. Pas grand chose d’autre à dire selon moi.