Au casino

Intuitions

Avant de commencer la programmation nous allons essayer de répondre aux différentes questions simplement avec notre intuition.

La première stratégie semble être une bonne stratégie. En effet, on va d’abord passer du temps à observer chaque machine de manière alternée afin de voir laquelle produit le meilleur résultat, c’est à dire le gain le plus élevé. Une fois que nous avons trouvé la bonne machine, il suffit d’effectuer des tirages uniquement sur celle-ci. Le désavantage de cette stratégie et qu’on perd du temps au début pour voir quelle machine est la meilleure. De plus, il faut faire attention à bien estimer les probabilités de chaque machines, si on ne choisit pas le bon epsilon, on peut se retrouver avec une mauvaise estimation et donc de mauvais gains.

La deuxième stratégie semble meilleure que la première stratégie car nous apprenons tout au long de la simulation ce qui nous permet d’être plus précis dans nos estimations. Le désavantage de cette stratégie est que au lieu de tirer uniquement sur la machine la plus rentable, on va perdre des lancers à tester la machine la moins rentable de temps en temps.

La troisième stratégie est compliquée à estimer vu qu’on va utiliser une loi annexe au lieu de simplement déterminer quelle machine est la meilleure. On peut tout de même penser que plus le nombre de tirages sera élevé plus la loi beta sera précise et meilleurs seront les résultats.

Question 1

Pour la stratégie qui consiste à jouer systématiquement sur la machine A, on a :
\(E[G_m(T)] = T*pA\)

Pour la stratégie qui consiste à jouer systématiquement sur la machine B, on a :
\(E[G_m(T)] = T*pB\)

Pour la stratégie qui consiste à jouer la machine A et la machine B avec une probabilité, on a :
\(E[G_m(T)] = \frac{1}{2} *T * (pA + pB)\)

Pour calculer le regret, on soustrait l’espérance de la stratégie m à l’espérance de la stratégie qui consiste à toujours tirer A.

Si la stratégie m est meilleure que la stratégie A alors la gain moyen c’est-à-dire l’espérance est supérieure. On veut donc un regret minimum pour une stratégie plus efficace. Dans notre cas la stratégie de jouer uniquement la machine A est la plus efficace, on cherchera une stratégie dont le regret est nul.

Voici le code qu’on utilisera afin de simuler les tirages des différentes stratégies que nous allons étudier :

#On fixe la seed afin de toujours avoir les mêmes tirages
set.seed(42)
#Simule une trajectoire de la stratégie 1
Q1 = function(t,pa,pb,e){
  regret =c()
  gain = 0
  nbSA = 0
  nbSB = 0
  #Pour les Tmax*epsilon premiers tirages on alterne les machines A et B
  for(i in 1:(t*e)){
    if(i%%2 == 0){
      if(runif(1)<pa){
        gain = gain + 1
        nbSA = nbSA + 1
      }
    } else{
      if(runif(1)<pb){
        gain = gain + 1
        nbSB = nbSB + 1
      }
    }
    #On calcule le regret pour chaque t
    regret[i] = pa - (gain/i)
  }
  #On choisit la machine qui a été la plus perfomante
  if(nbSB>nbSB){
    p = pb
  } else {
    p = pa
  }
  #On effecte tous les tirages restants avec cette machine
  for(i in (t*e+1):t){
    if(runif(1)<p){
      gain = gain + 1
    }
    #On calcule le regret
    regret[i] = pa - (gain/i)
  }
  #On renvoit le vecteur contenant le regret pour chaque tirage
  return (regret)
}
#Simule une trajectoire de la stratégie 2
Q2 = function(t,pa,pb,e){
  regret = c()
  nbSA = 0
  nbSB = 0
  gain = 0
  for(i in 1:t){
  #On distingue trois cas :
    #Si La machine A a été plus performante que la B
    if((nbSA/(i+1))>(nbSB/(i+1))){
      #On choisit sur quelle machine on va tirer avec une probabilité de choisir la meilleur de 1-epsilon
      if(runif(1)<(1-e)){
        if(runif(1)<pa){
          nbSA = nbSA +1
          gain = gain +1
        }
      } else {
        if(runif(1)<pb){
          nbSB = nbSB +1
          gain = gain +1
        }
      }
    }
    #Si la machine B a été plus perfomante que la A
    else if((nbSA/(i+1))<(nbSB/(i+1))) {
      if(runif(1)<(1-e)){
        if(runif(1)<pb){
          nbSB = nbSB +1
          gain = gain +1
        }
      } else {
        if(runif(1)<pa){
          nbSA = nbSA +1
          gain = gain +1
        }
      }
    }
    #Si les deux machines ont la même performance
    else {
      if(runif(1)<0.5){
        if(runif(1)<pb){
          nbSB = nbSB +1
          gain = gain +1
        }
      } else {
        if(runif(1)<pa){
          nbSA = nbSA +1
          gain = gain +1
        }
      }
    }
    #On calcule le regret
    regret[i] = pa-(gain/i)
  }
  #On renvoit le vecteur contenant le regret pour chaque tirage
  return (regret)
}
#Simule une trajectoire de la stratégie 3
Q3 = function(t,pa,pb){
  regret = c()
  nbSA = 0
  nbSB = 0
  nbEA = 0
  nbEB = 0
  gain = 0
  for(i in 1:t){
    #On estime les probabilités des machines A et B à l'aide de la fonction beta
    pA = rbeta(1, shape1 = nbSA+1, shape = nbEA+1)
    pB = rbeta(1, shape1 = nbSB+1, shape = nbEB+1)
    #On choisit la machine la plus performante pour faire notre tirage
    if(pA > pB){
      if(runif(1)<pa){
        nbSA = nbSA + 1
        gain = gain + 1
      } else {
        nbEA = nbEA + 1
      }
    } else {
      if(runif(1)<pb){
        nbSB = nbSB + 1
        gain = gain + 1
      } else {
        nbEB = nbEB + 1
      }
    }
    #On calcule le regret
    regret[i] = pa - (gain/i)
  }
  #On renvoit le vecteur contenant le regret pour chaque tirage
  return (regret)
}

Tmax = 5000 #Une trajectoire comporte 1000 tirages
N = 100 #Pour chaque stratégie, on calcule 100 trajectoires
#On fixe pa et pb pour le reste de l'exercice
pA = 0.65
pB = 0.55
#Nous aurons aussi besoin de deux valeur d'epsilon
epsilon1 = 0.05
epsilon2 = 0.1

#On calcule N trajectoires composées des Tmax tirages
#Tous les résultats seront enregistrés dans la dataframe a
a = data.frame()
for(j in 1:N){
  r1 = data.frame(Q1(Tmax,pA,pB,epsilon1))
  r2 = data.frame(Q2(Tmax,pA,pB,epsilon2))
  r3 = data.frame(Q3(Tmax,pA,pB))
  t = c(1:Tmax)
  id = seq(j,j,length = Tmax)
  df = cbind(id,t,r1,r2,r3)
  a = rbind(a,df)
}
#On renommne les colonnes de la dataframe
names(a)[3] = "r1"
names(a)[4] = "r2"
names(a)[5] = "r3"

#On calcule la moyenne du regret en fonction du temps
a = rbind(a,cbind(id = seq(N+1,N+1,length = Tmax),select(a,t,r1,r2,r3) %>% group_by(t) %>% summarise(r1 = mean(r1), r2 = mean(r2), r3 = mean(r3))))

#La fonction affichage nous permet de dessiner le grapghique correspondant à une stratégie avec la moyenne du regret tracée en rouge
affichage = function(nbStrat){
  switch(nbStrat,'1' = {ggplot(a) + geom_line(data = subset(a,id<N+1),aes(x = t,y = r1,group = id)) + geom_line(data = subset(a,id == N+1),aes(x = t, y = r1, color = "red"))},
                '2' = {ggplot(a) + geom_line(data = subset(a,id<N+1),aes(x = t,y = r2,group = id)) + geom_line(data = subset(a,id == N+1),aes(x = t, y = r2, color = "red"))},
                '3' = {ggplot(a) + geom_line(data = subset(a,id<N+1),aes(x = t,y = r3,group = id)) + geom_line(data = subset(a,id == N+1),aes(x = t, y = r3, color = "red"))})
}

Question 2

Voici le graphique combinant 100 trajectoires de la stratégie 1 :

affichage(1)

On voit qu’en moyenne, après avoir effectué les tirages d’évaluation, le regret tend vers 0. Une bonne stratégie a un regret nul, on peut donc dire que cette stratégie est plutôt efficace.

Question 3

Voici le graphique combinant 100 trajectoires de la stratégie 2 :

affichage(2)

On peut voir que l’évaluation de la meileure machine n’est pas très performante. En effet sur le graphique on peut voir qu’un certain nombre de trajectoire ont un regret tournant autour de 0,1. Cela indique qu’on a estimé que la machine la plus perfomante était la machine B. On peut en conclure que cette stratégie est moins fiable que la première stratégie.

Question 4

Voici le graphique combinant 100 trajectoires de la stratégie 3 :

affichage(3)

On peut voir que l’intervalle des regrets à un temps t se réduit proportionnellement au nombre de tirages. Cette loi est plus efficace lorsque le nombre de tirages est très grand. La moyenne des regrets est meilleure que celles des autres stratégies.

Conclusion

Comme nous avons pu le voir, nos intuitions étaient plutôt exactes. En effet la troisième stratégie est la meilleure sur le long terme. La première est aussi très fiable. Cependant on peut voir que la deuxième stratégie se trompe régulièrement et est la moins efficace.