Première partie - Découverte du sujet et premières intuitions

Question 1

Chaque tirage se modélise par une variable aléatoire indépendante suivant une loi de Bernouilli de probabilité pA pour la machine MA ou pB pour la machine MB.

Dans l’énoncé, la fonction suivante nous est donnée :

Gm(T)=∑t=1TXm(t),t
Cela correspond à la somme des gains de valeurs Xm(t),t de tentatives allant de 1 à T (avec t correspondant à une tentative sur la machine MA ou MB).

  • Si on joue seulement avec la machine MA ou la machine MB, les gains suivent une loi Binomiale de paramètre pA si on joue uniquement avec la machine MA ou pB si on joue seulement avec la machine MB
  • Si on joue avec les deux machines en ayant la probabilité 12 de jouer avec l’une ou l’autre, on peut penser que les résultats vont ressembler à une multiplication entre deux lois de Bernouilli (machine MA=0 ou machine MB=1). E[Gm(T)] correspondra donc, pour chaque cas, à une intégrale allant de 1 à T des fonctions trouvées.

Notre intuition nous mène à penser que Rm(t) indique si nous sommes en positif ou en négatif (en terme de gain) lors d’une certaine tentative t selon une probabilité p. Par exemple si on a une probabilité 12, on est censé gagner une fois sur deux. Si c’est le cas, alors Rm(t) vaudra 0. Dans le cas contraire, la valeur sera positive si on a plus perdu que gagné et négative si on a plus gagné que perdu. On peut ainsi nommer cette variable “le regret” car elle représente le fait que notre stratégie nous fait plus gagner qu’une autre. Une “bonne” stratégie est donc une stratégie qui nous permet d’avoir plus de 1 que de 0. Le but principal étant de sortir du casino avec des gains, on doit donc avoir un Rm(T) négatif (ce qui nous indique que nous avons des gains et non des pertes).

Question 2

Dans cette stratégie, on commence par alterner les machines entre chaque tentative. Puis, arrivé à un certain nombre d’essai, on regarde quelle machine nous a le plus fait gagner puis on joue ensuite uniquement sur celle qui nous a le plus fait gagner au départ.

Il nous semble que les trajectoire de RmL(t) vont dans un premier temps anormalement varier puis stagner dans un second temps apres ϵ.T. Cette stratégie ne nous parait pas meilleure qu’une stratégie où on decide de jouer seulement sur une machine.

Question 3

Dans cette stratégie, la machine est sélectionnée selon l’ensemble des tentatives précédentes et selon une probabilité de 1−ϵ ce qui fait que l’on a une plus grande chance de continuer à jouer avec la machine qui gagne le plus.

Cette stratégie semble être prometteuse car on n’a plus de chance de jouer avec la machine qui gagne le plus (Sur l’ensemble des tentatives et pas seulement sur les ϵ.T premiers lancers comme pour RmL(T)) tout en variant parfois de machine.

Question 4

Cette fois, le choix d’une machine ne suit pas une loi de parametre 1−ϵ mais une loi Beta de paramètre (n1+1,n2+1) Le fonctionnement d’une loi Beta ne nous parait pas très clair pour le moment donc il nous est difficile de juger l’efficacité de cette dernière stratégie pour le moment.

Deuxième partie - Réalisation des exercices

On commence par définir les variables qui nous seront utiles pour les prochains exercices.

set.seed(69)
# On va effectuer 1000 tirages pour chaque stratégie
Tmax = 1000
# Probabilité de succès sur les machines A et B
pA   = 0.65
pB   = 0.55
simul_strat <- function(m, p) {
  # Explications : 
  # - On simule 1000 tirages avec la stratégie m utilisant une machine
  #   avec une probabilité de gain p
  # - On compte le nombre de succès
  # - On calcul le regret pour cette stratégie
  succes = sum(rbinom(n = Tmax, size = 1, prob = p) == 1)
  print(paste("Nombre de succes =", succes))
  regret = pA - succes/Tmax 
  print(paste("Regret pour la stratégie m", m," = ", round(regret, digits = 5), sep = ""))
}

Question 1

Stratégie m1
  • m1 est la stratégie qui vise à jouer systématiquement la machine MA de paramètre pA. E[Gm(T)] correspond ainsi à l’espérance d’une variable aléatoire suivant une loi Binomiale de parametre pA et de nombre de tentative T. On en déduit la forme close suivante :
    E[Gm(T)]=T×pA
# Simulation pour la stratégie m1
simul_strat(1,pA)
## [1] "Nombre de succes = 658"
## [1] "Regret pour la stratégie m1 = -0.008"

Au moment de calculer le nombre de tirage réussi pour cette stratégie, on s’attend a obtenir une valeur proche de E[Gm(T)]=T×pA=1000×0.65=650. En effet, on obtient bien une valeur proche de cela.

Stratégie m2
  • m2 est la stratégie consitant à jouer systématiquement la machine MB de paramètre pB. E[Gm(T)] correspond donc à l’espérance d’une variable aléatoire suivant une loi Binomiale de paramètre pB et de nombre de tentative T. On en déduit la forme close suivante :
    E[Gm(T)]=T×pB
# Simulation pour la stratégie m2
simul_strat(2,pB)
## [1] "Nombre de succes = 568"
## [1] "Regret pour la stratégie m2 = 0.082"

Au moment de calculer le nombre de tirage réussi pour cette stratégie, on s’attend a obtenir une valeur proche de E[Gm(T)]=T×pB=1000×0.55=550. En effet, on obtient une valeur proche de cela.

Stratégie m3
  • m3 est la stratégie qui consiste à jouer la machine MA avec probabilité 12 et la machine MB avec probabilité 12. Cette stratégie mélange les deux précédentes. On obtient donc cette forme close :
    E[Gm(T)]=T2pA+T2pB
# Simulation pour la stratégie m3
machineA = 0
machineB = 0
tirages  = c()
# On simule cette stratégie sur 1000 tirages
for(i in 1:Tmax){
    machine = runif(1)
    # machine A
    if(machine >= 0.5){
      tirages  = c(tirages, rbinom(n = 1, size = 1, prob = pA))
      machineA = machineA + 1
    # machine B
    }else{
      tirages  = c(tirages, rbinom(n = 1, size = 1, prob = pB))
      machineB = machineB + 1
    }
}
succes = sum(tirages == 1)
regret = pA - succes / Tmax
print(paste("Nombre de succes =", succes))
## [1] "Nombre de succes = 612"
print(paste("Nombre de tirage avec la machine A :", machineA))
## [1] "Nombre de tirage avec la machine A : 501"
print(paste("Nombre de tirage avec la machine B :", machineB))
## [1] "Nombre de tirage avec la machine B : 499"
print(paste("Regret pour la stratégie m3 = ", round(regret, digits = 5), sep = ""))
## [1] "Regret pour la stratégie m3 = 0.038"

On doit donc obtenir un nombre de succès proche de 600 correspondant au calcul de E[Gm(T)] de cette stratégie pour pA=0.65 et pB=0.55.

Le regret de la stratégie

Pour montrer l’intérêt du regret de la stratégie, on va reprendre les codes R précédents et ajouter le calcul de Rm(T) pour les 3 stratégies précédentes.
La formule de Rm(T) consiste a calculer le nombre de réussite d’une stratégie sur le nombre de tirage T et de soustraire la valeur obtenue à une probabilité (ici pA). Or on voit que dans la premiere stratégie, Rm(T) est toujours proche de 0 car si on idéalise le calcul de Rm(T) dans ce cas là, on obtient Rm(T)=pA−pA=0. Rm(T) permet donc de comparer la probabilité de gagner de deux stratégies.
De plus, si on idéalise le calcul de Rm(T) pour la deuxieme stratégie, on a Rm(T)=pA−pB=0.1 or on voit dans le code que Rm(T) est proche de 0.1 pour la stratégie utilisant que la machine MB.
On en déduit donc que Rm(T) permet de comparer deux stratégies (ici pA). On observe aussi que si Rm(T) est positif, cela veut dire que la stratégie est moins efficace que celle qui utilise que la machine MA. Au contraire si Rm(T) est négatif, la stratégie se trouve être plus efficace que d’utiliser que la machine MA.

On pourra aussi remplacer pA dans le calcul de Rm(T) par la probabilité d’une autre stratégie afin de pouvoir comparer plusieurs autres stratégies entres elles.

Code questions suivantes

library("ggplot2")
library(reshape2)

# Fonction utilitaire pour factoriser le code utilisé dans
# les cas A et B du switch ci dessous
get_df_strat <- function(data, N, p) {
  for (i in 1:N) {
    # Chaine de caractère pour nommer la colonne
    # dans la data frame retournée par casino
    colname = paste("Tirage", i, sep = "_")
    tirages = rbinom(n = Tmax, size = 1, prob = p)
    Rmt     = pA - cumsum(tirages) / c(1:Tmax)
    d <- data.frame(colname = Rmt)
    data[,colname] <- d
  }
  return(data)
}
# Rappel : 
# - pA = 0.65
# - pB = 0.55
# - Tmax = 1000
casino <- function(x) {
  N = 100  # Nombre de trajectoires 
  # Data frame qui va etre renvoyé par la fonction casino
  res <- data.frame("t" = 1:Tmax)
  switch(x,
         # Stratégie m1 - pour obtenir la data frame 
         # liée à l'utiliation de la machine A
         "A" = {
           return(get_df_strat(res, N, pA))
         },
         # Stratégie m2 - pour obtenir la data frame
         # liée à l'utilisation de la machine B
         "B" = {
           return(get_df_strat(res, N, pB))
         },
         # Stratégie de la question 2 
         "1" = {
           epsilon = 0.05         # On fixe la valeur de epsilon
           etude = Tmax * epsilon # Nombre de tirage selon epsilon
           
           # Boucle pour chaque trajectoire
           for (j in 1:N) {
             tirages   = c() # Liste contenant l'ensemble des tirages
             alt       = 0   # Pour alterner le choix de la machine
             compteurA = 0   # Nombre de fois où A est utilisée
             compteurB = 0   # Nombre de fois où B est utilisée 
             proba     = 0   # Probabilité de la machine prometteuse
             colname   = paste("Tirage", j, sep = "_")
             
             # On réalise les premiers tirages selon epsilon 
             for (i in 1:etude) {
               # On alterne les machines à chaque tirage
               if (alt %% 2 == 0) {
                 tirage    = rbinom(n = 1, size = 1, prob = pA)
                 compteurA = compteurA + tirage
               } else {
                 tirage    = rbinom(n = 1, size = 1, prob = pB)
                 compteurB = compteurB + tirage
               }
               tirages = c(tirages, tirage)
               alt = alt + 1
             }
             # On détermine ensuite quelle machine est la plus prometteuse
             if (compteurA >= compteurB) proba = pA else proba = pB
             # On joue avec la machine de probabilité proba jusqu'à Tmax
             tirages = c(tirages, rbinom(n = Tmax-etude, size = 1, prob = proba))
             Rmt     = pA - cumsum(tirages) / c(1:Tmax) 
             d <- data.frame(colname = Rmt)
             res[,colname] <- d
           }
           return(res)
         },
         "2" = { 
           # Valeur de epsilon chapeau
           epsilon_chap = 0.1
           # On réalise les N trajectoires
           for (j in 1:N) {
             # Compteurs pour choisir la machine utiliser lors d'un tirage
             compteurA = 0
             compteurB = 0
             pMA = 0
             pMB = 0
             # Liste contenant les resultats
             tirages = c()
             # Chaine de caractere contenant le nom de la colonne dans la data frame
             colname = paste("Tirage", j, sep = "_")
             # On réalise les TMax tirages
             for(i in 1:Tmax){
               # On modifier la probabilité de choisir la machine A ou la machine B selon les tirages précédents
               if(compteurA > compteurB){
                 pMA = 1 - epsilon_chap 
                 pMB = epsilon_chap
               }else if(compteurB > compteurA){
                 pMB = 1 - epsilon_chap 
                 pMA = epsilon_chap
               }else{
                 pMA = 1/2  
                 pMB = 1/2
               }
               # On tire une valeur afin de determiner la machine qui va etre utilisée
               val = runif(1,min=0,max=1)
               # Tirage d'une valeur selon la machine utilisée
               if(val <= pMA){
                 tirages = c(tirages, rbinom(n = 1,size=1,prob=pA))
               }else{
                 tirages = c(tirages, rbinom(n = 1,size=1,prob=pB))
               }
               
             }
             # On sauvegarde la valeur de Rm(t) des  tirages obtenus dans la data frame
             Rmt = pA-cumsum(tirages)/c(1:Tmax)
             d <- data.frame(colname = Rmt)
             res[,colname] <- d
           }
           # On retourne la data frame
           res
         },
         "3"={
           # On réalise les N trajectoires
           for( j in 1:N){
             # Liste des valeurs des tirages
             tirages = c()
             # Nombre de succès de chaque machine au cours des tirages
             success_A = 0
             success_B = 0
             # Valeur de t au cours des tirages
             t = 1
             # Chaine de caractere pour nommer la colonne de la data frame
             colname   = paste("Tirage", j, sep = "_")
             # Réalisation des tirages
             for( i in 1:Tmax){
               # On determine la machine utilisé selon une loi beta 
               if(rbeta(1, shape1 = success_A, shape2 = t-success_A) >= rbeta(1, shape1 = success_B, shape2 = t-success_B)){
                 tirages = c(tirages, rbinom(n = 1, size = 1, prob = pA))
                 success_A = success_A + tirages[t]
               }else{
                 tirages = c(tirages, rbinom(n = 1, size = 1, prob = pB))
                 success_B = success_B + tirages[t]
               }
               t = t + 1
             }
             # On sauvegarde la valeur de Rm(t) des  tirages obtenus dans la data frame
             RmT = pA-cumsum(tirages)/c(1:Tmax)
             d <- data.frame(colname = RmT)
             res[,colname] <- d
           }
           # On retourne la data frame
           res
         },
         stop("valeur de x non valide"))
}

# calcul de la moyenne selon une data frame passée en parametre
moyenne_essai <- function(res){
  # Liste contenant la moyenne des Rmt selon t
  moy = c()
  # On parcourt 
  for(i in 1:Tmax){
    sum = 0
    for(j in 2:101){
      # On somme chaque valeur 
      sum = sum + res[i,j]
    }
    # On calcul la moyenne 
    moy = c(moy,sum/100)
  }
  # On retourne une data frame contenant la moyenne pour chaque t
  mean <- data.frame("t"= 1:Tmax, "moyenne"= moy)
  mean
}

Execution de la stratégie m1

# Simulation 
resA = casino("A")
moyenne = moyenne_essai(resA) 
resA <- melt(resA, id.vars = 't', variable.name = 'essais')
# Plot de la simulation

ggplot(resA, aes(t,value)) + geom_line(alpha=0.1) + geom_line(moyenne,mapping = aes(x=t,y=moyenne,colour="red")) + ggtitle("RmA(t) au cours du temps t") + theme(legend.position="none") + labs(y="p_opt-Gt/t", x = "t")

Execution de la stratégie m2

# Simulation
resB = casino("B")
moyenne = moyenne_essai(resB)
resB <- melt(resB, id.vars = 't', variable.nam = 'essai')
# Plot de la simulation
ggplot(resB, aes(t,value)) + geom_line(alpha=0.1) + geom_line(moyenne,mapping = aes(x=t,y=moyenne,colour="red")) + ggtitle("RmB(t) au cours du temps t") + theme(legend.position="none") + 
labs(y="p_opt-Gt/t", x = "t")

Question 2

Trace de RmL(t)
# Simulation Question 2
res = casino("1")
moyenne = moyenne_essai(res)
res <- melt(res, id.vars = 't', variable.nam = 'essai')
# Plot de la simulation de la question 2
ggplot(res, aes(t,value)) + geom_line(alpha=0.1) + geom_line(moyenne,mapping = aes(x=t,y=moyenne,colour="red")) + ggtitle("RmL(t) au cours du temps t") + theme(legend.position="none") + 
  labs(y="p_opt-Gt/t", x = "t")

Analyse du résultat

On voit que la moyenne des trajectoires (en rouge sur la graphe) est proche de 0 et qu’elle est même légérement au dessus de 0. La valeur de RmL(t) est ainsi positive. Donc la stratégie mL est moins efficace que la stratégie visant à n’utiliser que la machine MA. Cependant, on voit qu’il y a de grand écart entre certaine trajectoires, un écart d’environ 0.2. On en déduit que ces écarts sont surement du au choix de la machine. Les trajectoires utilisant la machine B sont surement ceux aboutissant à un RmL(t) positif à presque 0.1. Alors que les valeurs de RmL(t) des trajectoires utilsant la machine A sont proches de 0 et parfois négatif. On en deduit donc que la stratégie mL est parfois plus efficace que de jouer seulement avec la machine MA.

Question 3

Trace de RmG(t)
# Simulation Qestion 3
res2 = casino("2")
moyenne = moyenne_essai(res2)
res2 <- melt(res2, id.vars = 't', variable.nam = 'essai')
# Plot de la simulation de la question 3
ggplot(res2, aes(t,value)) + geom_line(alpha=0.1) + geom_line(moyenne,mapping = aes(x=t,y=moyenne,colour="red")) +
  ggtitle("RmT(t) au cours du temps t") + theme(legend.position="none") + 
  labs(y="p_opt-Gt/t", x = "t")

Analyse du résultat

On regarde d’abord la moyenne (en rouge), cette dernière est toujours au dessus de 0. on en deduit que la stratégie mG est bien moins efficace que de jouer que avec la machine MA. De plus, quasi aucune trajectoire n’est inferieure à 0 (quand on tend vers t=1000, il n’y a plus du tout de trajectoire inférieure à 0). Cela renforce l’idée que cette stratégie est bien moins efficace.

Question 4

# Simulation Question 4
res3 = casino("3")
moyenne = moyenne_essai(res3)
res3 <- melt(res3, id.vars = 't', variable.name = 'essai')
# Plot de la simulation de la question 4
ggplot(res3, aes(t,value)) + geom_line(alpha=0.1) + geom_line(moyenne,mapping = aes(x=t,y=moyenne,colour="red")) + ggtitle("RmT(t) au cours du temps t") + theme(legend.position="none") + labs(y="p_opt-Gt/t", x = "t")

Analyse du résultat

On observe que la moyenne(en rouge sur le graphe) est superieur à 0 donc on en déduis que cette stratégie est aussi moins efficace que MA. Certaines trajectoires sont moins efficaces que MA mais d’autres terminent avec un Rm(T) négatif ce qui signifie que parfois, cette stratégie peut amener à gagner plus qu’avec MA. L’écart entre l’ensemble des trajectoires est très faible. On en déduit donc que cette stratégie est trés proche de MA.

Troisième Partie - Analyse et conclusion par rapport à nos intuitions

Après une première lecture du sujet, nous pensions qu’au moins une de ces trois stratégies serait plus efficace que MA. Au final, nous constatons que ces stratégies peuvent avoir une valeur de Rm(T) négative pour certaines trajectoires signifiant que la probabilité de gagner était supérieur à 0.65 (probabilité pA de MA). Cependant ces stratégies sont dans la plupart des cas moins fiables que celle consistant à jouer seulement avec la machine MA. On en conclu qu’au casino, il n’existe pas de réelle stratégie pour augmenter ses gains. Il serait peut être préférable de laisser tomber les machine à sous pour tester le poker.