Questions préliminaires

Intuitions

Stratégie 1

Pour nous, la stratégie ne nous semble pas bonne. Le fait d’utiliser les \(\epsilon\)\(*Tmax\) premiers tirages pour déterminer la meilleure machine, ne nous semble pas être une bonne idée. En effet, sur les \(\epsilon\)\(*Tmax\) on alterne les tirages sur la machine A et la machine B donc des tirages avec la machine la plus prometteuse sont “perdus”. Alors que si on établit la meilleure machine avant de faire nos Tmax tirages, nos Tmax tirages sont optimisés. De plus, nous pensons que déterminer la meilleure machine sur un échantillon ne nous permet pas de savoir réellement si on a trouvé la machine la plus prometteuse.

Stratégie 2

La stratégie 2 nous semble être une bonne stratégie. Le fait de chercher la machine la plus prometteuse, avant de faire nos Tmax tirages, nous permet de ne pas “perdre” des tirages sur la recherche de la machine prometteuse. Malgré tout avec cette stratégie on n’élimine pas complétement une machine contrairement à la stratégie précédente. On ne fait que cibler la plus performante. Cela permet de varier les tirages en cas de mauvais choix lors du choix de la meilleure machine. Cependant si une machine étant déterminée comme la plus performante durant la cherche préliminaire est la mauvaise alors les gains totaux vont être influencés.

Statégie 3

La stratégie 3 nous semble également être une bonne solution car à chaque tirage on choisi la machine la plus performante en fonction des valeurs des vraisemblances de chaque machine (La vraisemblance étant calculée grâce à la fonction de densité beta). Cela permet de ne pas avoir une erreur dans la recherche préliminaire de la meilleure machine contrairement à la stratégie 2. Ici rien n’est fixé, le choix de la machine est déterminée à chaque tirage donc il y a moins d’erreur et plus de précision dans le choix de la meilleure machine.

Code

Paramètres

N = 100 #nb de trajectoires
Tmax = 1000 #nb de tirages
moyenne=0 
pA =0.65 #probabilité de A
pB=0.55 #probabilité de B
epsilon_s1 = 0.05 #epsilon pour la stratégie 1
epsilon_s2 = 0.1 #epsilon pour la stratégie 2

Implémentation de la stratégie 1

#fonction qui renvoie la dataframe d'une simulation de la stratégie 1
strat1 <- function(pA, pB, Tmax, epsilon, id){
    
    premier_essais = Tmax*epsilon #Nombre de premiers essais
    tirage_mA=0 #Epsion*Tmax premier tirages avec la machine A
    tirage_mB=0 #Epsion*Tmax premier tirages avec la machine B
    tirage_mAB=0 #Epsion*Tmax premier tirages avec la machine A puis B
    tirage=0 #Tous les tirages
    gain=0 #Somme des gains
    gainA =0 #Gain avec la machine A
    gainB =0 #Gain avec la machine B
    tirage_mP =0 #Gain avec la machine prometteuse
    gain_cum = 0 #tableau des gains cumulés à l'instant t
    regret =0 #Regret en fonction du temps
    i=0
    
    tirage_mB = rbinom(1,1,pB) #Tirage avec la machine B
    tirage_mAB[1] = tirage_mB #Ajout du gain du dernier tirage au gain total de la machine B
    gainB = gainB + tirage_mB #Ajout du gain obtenu dans le tableau des gains 
    gain_cum[1] = tirage_mB #Ajout du gain du tirage au gain total
    regret[1] = pA - gain_cum[1]/1 #Calcul du regret au tirage i 
    
    
    
#Alternance des tirages avec machine A machine B sur les epsilone*Tmax premiers tirages
    for (i in 2:premier_essais) {
        if((i%%2)==0){ 
             tirage_mA = rbinom(1,1,pA) #Tirage avec la machine A
             gainA = gainA +tirage_mA #Ajout du gain du dernier tirage au gain total de la machine A
             tirage_mAB[i] =tirage_mA #Ajout du gain obtenu dans le tableau des gains 
             gain_cum[i] = gain_cum[i-1] + tirage_mA #Ajout du gain du tirage au gain total
        }else{
             tirage_mB = rbinom(1,1,pB) #Tirage avec la machine B
             tirage_mAB[i] = tirage_mB #Ajout du gain du dernier tirage au gain total de la machine B
             gainB = gainB + tirage_mB #Ajout du gain obtenu dans le tableau des gains 
             gain_cum[i] = gain_cum[i-1] + tirage_mB #Ajout du gain du tirage au gain total
        }
        regret[i] = pA - gain_cum[i]/i #Calcul du regret au tirage i 
    }
                
    if(max(gainA,gainB) == gainA){ #Savoir qui est la machine la plus prometteuse
        machine_prom = pA
    }else{ 
        machine_prom = pB
    }
    
    #Tirages de epsilon*Tmax+1 à Tmax avec la machine prometeuse
    for( i in (premier_essais+1):Tmax){
       tirage_mP = rbinom(1,1,machine_prom) #Tirage avec la machine prometeuse
       gain_cum[i] = gain_cum[i-1] + tirage_mP #Ajout du gain obtenu au gain total 
       regret[i] =pA - gain_cum[i]/i #Calcul du regret au tirage i
    }
  
    t = seq(1,Tmax,1) #Sequence qui represente le temps 
    data.frame(id,t,regret, gain_cum) #Création d'une dataframe avec le regret en fontion des tirages
}

Implémentation de la stratégie 2

#fonction qui renvoie la dataframe d'une simulation de la stratégie 2
strat2 <- function(pA, pB, Tmax, epsilon, id){
    
    tirage_mA=0 #Epsion*Tmax premier tirages avec la machine A
    tirage_mB=0 #Epsion*Tmax premier tirages avec la machine B
    tirage=0 # Tous les tirages
    
    gainA =0 #Gain avec la machine A
    gainB =0 #Gain avec la machine B
    gain = 0 #tableau des gains cumulés à l'instant t
    gain_tot =0
    machine_prom = 0 #proba de la machine promettteuse
    machine_non_prom = 0 #proba de la machine non prometteuse
    regret =0 #Regret en fonction du temps
    
    
    for(i in 1:Tmax){ #tirages pour determiner la machine la plus prometteuse
        tirage_mA = rbinom(1,1,pA)
        gainA = gainA + tirage_mA
        tirage_mB = rbinom(1,1,pB)
        gainB= gainB + tirage_mB
      }
     
    #calcul du ratio et définition de la machine prometteuse
     if(gainA/(Tmax+1) > gainB/(Tmax+1)){ # la machine A est prometteuse
          machine_prom = pA
          machine_non_prom = pB
     }else if ( (gainA/(Tmax+1)) < (gainB/(Tmax+1)) ){ #la machine B est prometteuse
          machine_prom = pB
          machine_non_prom =pA
     }else{
        if(runif(1)<(1/2)){ #tirage aléatoire de la machine prometteuse
          machine_prom = pA
          machine_non_prom = pB
        }else{
          machine_prom = pB
          machine_non_prom = pA
        }
      }
     
      for(i in 1:Tmax){ #Tmax tirage
        if(runif(1) < 1-epsilon){ #La machine prometteuse est selectionnée avec 1-epsilon chance
          tirage[i] = rbinom(1,1,machine_prom)
        }else{
          tirage[i] = rbinom(1,1,machine_non_prom) #La machine non prometteuse est selectionnée avec epsilon chance
        }
         gain = gain + tirage[i] #Calcul des gains cumulés
         regret[i] =pA - gain/i #Calcul du regret au tirage i
      }
      
      gain_cum= cumsum(tirage) #gains cumulés
      t = seq(1,Tmax,1)#Sequence qui représente le temps 
      data.frame(id,t,regret, gain_cum) #Création d'une dataframe avec le regret en fontion des tirages
}

Implémentation de la stratégie 3

#fonction qui renvoie la dataframe d'une simulation de la stratégie 3
strat3 <- function(pA, pB, Tmax, id){
    tirage_mA=0 #Epsion*Tmax premier tirages avec la machine A
    tirage_mB=0 #Epsion*Tmax premier tirages avec la machine B
    tirage=0 # Tous les tirages
    gainA =0 #Gain avec la machine A
    gainB =0 #Gain avec la machine B
    gain_cum = 0 #tableau des gains cumulés à l'instant t
    regret =0 #Regret en fonction du temps
    gain =0
    
#Determination des parties gagnées grâce la machine A et la machine B
    for(i in 1:Tmax){
      tirage_mA = rbinom(1,1,pA)
      gainA = gainA + tirage_mA
      tirage_mB = rbinom(1,1,pB)
      gainB= gainB + tirage_mB
    }
    
    for( i in 1:Tmax){
     VraisemblableA= rbeta(1,shape1 = (gainA+1) ,shape2 = (Tmax-gainA+1)) #Calcul du vraisemblable de A grâce à la densité de beta
     VraisemblableB = rbeta(1,shape1 = (gainB+1), shape2 = (Tmax-gainB+1)) #Calcul du vraisemblable de A grâce à la densité de beta
      if(VraisemblableA >= VraisemblableB){ #On utilise la machine A pour le tirage i
        tirage[i] = rbinom(1,1,pA)
      }else{ #On utilise la machine B pour le tirage i
        tirage[i] = rbinom(1,1,pB)
      }
       gain = gain + tirage[i] #Calcul des gains cumulés
       regret[i] =pA - gain/i #Calcul du regret au tirage i
    }

    gain_cum= cumsum(tirage) #gains cumulés
    t = seq(1,Tmax,1)
    data.frame(id,t,regret, gain_cum)
}

Calcul de la moyenne

moyenne <- function(df, Tmax, N){
  moy_r=0
  moy_g =0
  #Mise à zero du vecteur moy_r (moyenne regret) et moy_g (moyenne gain)
  for(i in 1:Tmax){
    moy_r[i] = 0
    moy_g[i] = 0
  }
  #Calcul de la moyenne du regret en fonction de t sur les N tirages
  for(i in 1:Tmax){
    for(j in 0:(N-1)){
      moy_r[i] =  moy_r[i] + df$regret[i+j*Tmax]
      moy_g[i] =  moy_g[i] + df$gain_cum[i+j*Tmax]
    }
  }
  moy_r= moy_r/N
  moy_g = moy_g/N
  
  data.frame(moy_r,moy_g)
}

Simulation

#fonction simulation qui en fonction de son argument renvoie le dataframe de la stratégie
simulation <- function(strategie){
  switch (strategie,
    '1' = {
       df = strat1(pA, pB, Tmax, epsilon_s1, 1) #on récupère les premiers resultats qu'on met dans une dataframe
       for(i in 2:N){ #On crée l'unique data frame avec tous les resultats de la simultaion
           df = rbind(df, strat1(pA, pB, Tmax, epsilon_s1, i))
       }
    },
    '2' = {
      df = strat2(pA, pB, Tmax, epsilon_s2, 1) #idem pour la stratégie 2
      for(i in 2:N){
          df = rbind(df, strat2(pA, pB, Tmax, epsilon_s2, i))
      }
    },
    '3' = {
      df = strat3(pA,pB,Tmax,1) #idem pour la stratégie 3
       for(i in 2:N){
          df = rbind(df, strat3(pA, pB, Tmax, i))
      }
    }
  )
  moy = moyenne(df, Tmax, N) #appel à la fonction moyenne pour récupérer le data frame correspondant à la moyenne en fonction du temps t pour chaque trajectoire
  df = cbind(df, moy) #rajout de la colonne moyenne à la data frame
  df #on renvoie la data frame
}

Affichage

#fonction affichage qui en fonction de son argument donne l'affichage correspondant
afficher <- function(strategie){
  df = simulation(strategie) #On récupère la dataframe de la stratégie passée en argument

  #affichage trajectoire et moyenne
  g<- ggplot(df,aes(x=t,y=regret, group=id)) + 
  geom_point(size=0.01, alpha=0.05)+ 
  geom_point(data=df,aes(t, moy_r), color="red", size =0.001, alpha=0.05) + 
  ggtitle(paste('Stratégie', strategie))+ theme(plot.title = element_text(size=20, face="bold",hjust = 0.5)) 
  
  #afichage point moyenne à Tmax*epsion_s1 pour analyse de la stratégie 1
  if(strategie == '1'){
    g <- g +
      geom_point(data=df,aes(x = t[Tmax*epsilon_s1], y=moy_r[Tmax*epsilon_s1]), color = "green", size =0.6) + 
      annotate("text", x = Tmax*epsilon_s1, y = 0.4, label = df$moy_r[Tmax*epsilon_s1], color = "dark green")
  }
  #afichage point moyenne à Tmax et moyenne des gains cumulés à Tmax
  g + geom_point(data=df,aes(x = t[Tmax], y=moy_r[Tmax]), color = "green", size =0.6) + 
  annotate("text", x = Tmax-30, y = 0.16, label = round(df$moy_r[Tmax], 4), color = "dark green") +
  annotate("text", x = Tmax/2-30, y = 0.65, label = (paste('Moyenne des gains à Tmax = ', df$moy_g[Tmax-1])), color = "orange")
 }

Stratégie 1

En vert, la moyenne du regret

afficher("1")

Analyse Stratégie 1

A t= 50, le regret moyen est de 0.053 contre 0.014 après avoir fait un choix de machine prometteuse. Cela montre bien que de choisir une machine a permis de faire diminuer le regret. En revanche, comme on peut le voir sur le graphe ci-dessus, plusieurs trajectoires ne convergent pas vers 0. Les trajectoires qui ne tendent pas vers 0 sont les trajectoires où la machine la moins performante a été choisi comme étant la machine la plus prometteuse. On explique ce grand nombre de trajectoires qui ne tendent pas vers 0 par une recherche de la machine la plus prometteuse faîtes sur un échantillon de tirages trop petit (ici 50). Cependant, il n’est pas avantageux d’augmenter \(\epsilon\), car l’augmenter réduirait les chances de jouer les tirages restants avec la machine la plus prometteuse et donc d’obtenir un grand gain. Donc nous pouvons dire en vu des résultats que la stratégie 1 n’est pas une bonne stratégie.

Stratégie 2

afficher("2")

Analyse Stratégie 2

On remarque que l’aspect global du graphe est plus harmonieux que celui du graphe de la stratégie 1. En effet, on n’a pas de trajectoires qui sortent du groupe des autres trajectoires. On note aussi que la moyenne du regret à Tmax est plus petite et plus proche de 0 (ici 0.0103). Cette stratégie est donc bien plus performante que la stratégie précédente. Les trajectoires tendent entre -0.05 et 0.05 à partir de t = 500. On note cependant que la différence de gain moyen entre la stratégie 1 et la stratégie 2 n’est pas très grande. Cette stratégie à l’air d’être une meilleure stratégie comparée à la stratégie précédente.

Stratégie 3

afficher("3")

Analyse Stratégie 3

La moyenne du regret à Tmax est infine \(1*10^{-4}\). Cela montre que cette stratégie est encore plus performante que les stratégies précédentes. Un grand nombre de trajectoires tendent vers -0.01 et 0.01 car à cette endroit il y a une plus grande superposition de trajectoires (noir plus foncé). Donc on peut dire grâce au graphique que la stratégie 3 est une bonne stratégie car on a quasiment pas de regret de ne pas avoir joué avec la machine choisie à chaque tirage. De plus, le gain moyen après les Tmax tirages est supérieur pour cette stratégie comparé aux stratégies précédentes. Cette stratégie est donc la meilleure par rapport au deux autres.

Analyse Intuition

Au vu des résultats obtenus, nous pouvons dire que nos intuitions étaient bonnes. La stratégie 1 n’est pas une bonne stratégie. La stratégie 2 est une bonne stratégie comparé à la première mais elle n’est pas aussi performante que la stratégie 3.