Questions prélimaires

Jouer systématiquement sur la machine MA

Dans ce cas, on joue uniquement sur la machine MA. La probabilité de gagner sur cette machine est pA pour une partie. Si on effectue T parties, on a donc l’espérance suivante :

E[Gm(T)]=∑t=1T(pA)=pA∗T

Jouer systématiquement sur la machine MB

Même raisonnement que précédement sauf que l’on joue sur la machine MB, sur laquelle on a une probabilité pB de gagner.

E[Gm(T)]=∑t=1T(pB)=pB∗T

Jouer sur la machine MA avec une probabilité 1/2 et sur la machine MB avec une probabilité 1/2

Dans ce cas, on joue sur la machine MA avec une probabilité 1/2 et sur la machine MB avec une probabilité 1/2. On rappelle que la probabilité de ces machines sont respectivement pA et pB.

E[Gm(T)]=∑t=1T(12∗(pB+pA))=12∗(pB+pA)∗T

Intérêt du regret

pA correspond à l’espérance en jouant la machine MA. On calcule l’espérance de Gm(t), c’est à dire le gain total moyen pour une stratégie m sur t tirages. On divise par t, on se ramène donc au gain moyen lors d’un essai. On effectue une différence entre ces 2 termes, ce qui nous permet de savoir si notre stratégie m est meilleure (si différence négative) ou moins efficace (si différrence positive) que si l’on avait joué uniquement sur la machine MA.

 Code Général

set.seed(4)
library(ggplot2)

regret = function(pA,E,t){
  pA - (E / t)
}


simulation = function(id,strat,pA,pB,Tmax,e,eq3){
  Gain_A = 0 #Gain cumulé sur la machine A
  Gain_B = 0 #Gain cumulté sur la machine B
  nb_A = 0 #Nombre de coups sur la machine A
  nb_B = 0 #Nombre de coups sur la machine B
  t = 1
  tab_regret = c() #Tableau contenant les valeurs du regret
  tab_time = c(1:Tmax) #Tableau contenant les valeurs du temps

  
switch (strat,
Q2 = {
  #Declaration d'un epsilon Tmax coups paire
  new_e = (e * Tmax) - (e * Tmax %% 2)
  
  # Coups joués sur la machine A
  coups_A = rbinom(new_e/2,1,pA)
  # Coups joués sur la machine B
  coups_B = rbinom(new_e/2,1,pB)
  
  # Gains de A et B
  Gain_A = sum(coups_A)
  Gain_B = sum(coups_B)
  
  # On détermine quelle machine est la plus rentable
  if(Gain_A > Gain_B){
    pmL = pA
  } else {
    pmL = pB
  }
  
  # On effectue les coups restants
  coups_restant = rbinom(Tmax - new_e,1,pmL)
  
  # On regroupe nos différent coups dans un unique tableau
  tab_coups = c(coups_A,coups_B,coups_restant)
  
  # On parcourt notre tableau de coups pour compléter le tableau de regret
  Cum_gain = 0
  for(t in 1:Tmax){
    Cum_gain = Cum_gain + tab_coups[t]
    tab_regret[t] = regret(pA,Cum_gain,t)
  }
},
Q3 = {
  while(t <= Tmax){
    #Cas de l'égalité entre les deux ratios
    if(Gain_A/(nb_A+1) == Gain_B/(nb_B+1)){
      #On choisit aléatoirement quelle machine utilisée
      if(runif(1) < 0.5){
          pmG = pA
          #On compte le nombre de coups joués sur la machine A
          nb_A = nb_A + 1
      } else {
        pmG = pB
          #On compte le nombre de coups joués sur la machine B
          nb_B = nb_B + 1
      }
    } else {
      choix = rbinom(1,1,1-eq3)
      
      #Condition pour choisir quelle machine utiliser
      if(((Gain_A/(nb_A+1) > Gain_B/(nb_B+1)) && choix) || ((Gain_B/(nb_B+1) > Gain_A/(nb_A+1)) && !choix)){
        pmG = pA
        nb_A = nb_A + 1
      } else {
        pmG = pB
        nb_B = nb_B + 1
      }
    }
  
    Gain = rbinom(1,1,pmG)
    if(pmG == pA){
      Gain_A = Gain_A + Gain
    }else{
      Gain_B = Gain_B + Gain
    }
    
    #Ajout du regret
    E = Gain_A + Gain_B
    tab_regret[t] = regret(pA,E,t)
    t = t + 1
  }
},
Q4 = {
  while(t <= Tmax){
    #On tire un nombre aléatoire selon la densité beta pour chaque machine
    rbA = rbeta(1, Gain_A+1, (nb_A-Gain_A)+1)
    rbB = rbeta(1, Gain_B+1, (nb_B-Gain_B)+1)
    #On choisit la machine avec la meilleure estimation
    if(rbA > rbB){ 
      #On compte le nombre de coups au total sur la machine
      nb_A = nb_A + 1
      # On augmente le Gain sur la machine A de 0 ou 1 en fonction du résultat de rbinom
      Gain_A = Gain_A + rbinom(1,1,pA)
    }else{
      #On compte le nombre de coups au total sur la machine
      nb_B = nb_B + 1
      # On augmente le Gain sur la machine B de 0 ou 1 en fonction du résultat de rbinom
      Gain_B = Gain_B + rbinom(1,1,pB)
    }
    E = Gain_A + Gain_B
    tab_regret[t] = regret(pA,E,t)
    t = t + 1
    }
  }

)
  
  return(data.frame(Id = id,Strategie = strat, time = tab_time, regret = tab_regret))
}

affichage = function(strategie,pA=0.65,pB=0.55,Tmax=1000,e=0.05,eq3=0.1){
  df = data.frame()
  mean_regret = data.frame()
  tours = 100
  index = seq(1,Tmax)
  for(i in 1:tours){
    df = rbind(df,simulation(id = i,strat = strategie,pA = pA,pB = pB, Tmax = Tmax, e = e, eq3 = eq3))
  }
  mean_regret = rbind(mean_regret,aggregate(df$regret, list(df$time), mean))
  ggplot() +
    geom_line(data = df, aes(x = time, y = regret, group = Id), alpha = 0.1) +
    geom_line(data = mean_regret, aes(x = index, y = mean_regret$x), color = "red")
}

On apprend (un peu) puis on exploite

Intuitions

On suppose que l’on va obtenir 2 types de trajectoires selon quelle machine a été choisi après les epsilon T coups.

affichage("Q2")

Est-ce une bonne stratégie ?

En choisissant cette stratégie, on obtient le schéma çi dessus. Lors de cette méthode, on a joué 1000 coups avec un epsilon de 0.05, soit 50 coups, et l’on remarque que la moyenne du regret au bout de 1000 coups sur 100 trajectoires de 0,031. Cette stratégie dépend du epsilon choisi. Si ce dernier est élevé, on aura un grand nombre de coups pour déterminer quelle est la machine avec la probabilité la plus élevée. C’est pour cela que sur le schéma précédent, le epsilon étant assez faible, nous avons des trajectoires qui privilégient le fait de jouer sur la machine ayant une probabilité plus faible. En effet, sur les epsilons premiers coups cette machine semblait meilleure, ce qui était faux. D’où l’observation de 2 trajectoires distinctes, celles qui ont choisi la machine ayant la probabilité plus faible et celles qui ont choisi l’autre machine dont le regret tend vers 0. Globalement, cette stratégie est assez pertinente si l’on fixe un epsilon élevé.

On exploite mais on se force à toujours apprendre (un peu)

Intuitions

On suppose que l’on va obtenir une trajectoire qui va tendre vers 0, avec des sauts lorsque l’on joue sur la machine qui n’a pas été choisie. Lors de ces sauts, le regret sera plus élevé étant donné que cette machine à une probabilité plus faible de gagner, c’est bien pour cela que l’on ne l’a pas choisie.

affichage("Q3")

Est-ce une bonne stratégie ?

En choisissant cette stratégie, on obtient le schéma çi-dessus. On observe que la plupart des trajectoires ont un regret qui tend vers 0, ce qui est plus satisfaisant que la stratégie précédente. Cette stratégie dépend de epsilon chapeau, si ce dernier est élevé, on va régulièrement jouer sur la machine que l’on a determiné comme moins efficace. Dans notre exemple, notre epsilon chapeau étant fixé à 10%, ce qui est plutôt faible, cela se traduit par une moyenne du regret au bout de 1000 coups sur 100 trajectoires qui est de 0,017. Dans ce cas, on a une stratégie pertinente.

On tire au hasard en biaisant selon nos observations

Intuitions

Dur d’avoir une intution étant donnée que l’on ne sait pas comment fonctionne la fonction bêta.

affichage("Q4")

Est-ce une bonne stratégie ?

En choisissant cette stratégie, on obtient le schéma çi-dessus. On observe qu’avec cette stratégie, les trajectoires tendent plus vite vers 0 que la stratégie précédente. Dans cette stratégie, on utilise une fonction bêta qui nous permet d’évaluer l’estimation de notre probabilité. De plus, cette stratégie ne dépend pas d’un paramètre externe comme epsilon ou epsilon chapeau. Cette stragie semble donc être la plus satisfaisante.