DM Gautier Yann Fontfreyde Joachim

library(ggplot2)

set.seed(123456)

simulation <- function(strategie,pa,pb,Tmax,nCourbes){
  res = data.frame()
  
  switch(strategie,
         '1'={
            epsilon = 0.1
            
            Ba = rbinom(nCourbes, (epsilon * Tmax)/2, pa)
            Bb = rbinom(nCourbes, (epsilon * Tmax)/2, pb)     
            p  = ifelse(Ba > Bb, pa, pb)
            
            for ( i in 1:nCourbes){
            {
              Bt = cumsum(rbinom(1:Tmax, 1, p[i]))
              regret = pa - Bt/ (1:Tmax)
               
              res = rbind(res, data.frame(id = i, t=1:Tmax, regret))
            }
           }
         },
         '2'={
           epsilon = 0.1
           
           for (j in 1:nCourbes)
           {
             nSuccesA = 0
             nSuccesB = 0
             result = c()
             
             for (i in 1:Tmax)
             {
               if(nSuccesA == nSuccesB){ p = ifelse(runif(1,0,1) > 0.5, pa, pb) }
               
               else if(rbinom(1,1, 1 - epsilon)){
                 if(max(nSuccesA, nSuccesB) == nSuccesA){ p = pa }
                 else{ p = pb }
               }
               
               else{
                 if(min(nSuccesA, nSuccesB) == nSuccesA){ p = pa }
                 else{ p = pb }
               }
               
               result[i] = rbinom(1,1, p)
               if(result[i] == 1){
                 if(p == pa) {nSuccesA = nSuccesA + 1}
                 else {succesB = nSuccesB + 1}
               }
             }
             
             regret = pa - cumsum(result)/ (1:Tmax)
             res = rbind(res, data.frame(id = j, t=1:Tmax, regret))
           }
         },
         '3'={
           for(j in 1:nCourbes)
           {
             nSuccesA = 0
             nEchecA = 0
             
             nSuccesB = 0
             nEchecB = 0
             
             result = c()
             for(i in 1:Tmax)
             {
               pSuppA = rbeta(1, shape1 = nSuccesA + 1, shape2 = nEchecA + 1)
               pSuppB = rbeta(1, shape1 = nSuccesB + 1, shape2 = nEchecB + 1)
               
               if(pSuppA > pSuppB) { p = pa }
               else if(pSuppB > pSuppA) { p = pb }
               else { p = ifelse(runif(1,0,1) > 0.5, pa, pb) }
               
               result[i] = rbinom(1,1,p)
               
               if(result[i] == 1){
                 if(p == pa){ nSuccesA = nSuccesA + 1 }
                 else{ nSuccesB = nSuccesB + 1 }
               }
               else{
                 if(p == pa){ nEchecA = nEchecA + 1 }
                 else{ nEchecB = nEchecB + 1 }
               }
             }
             
             regret = pa - cumsum(result)/ (1:Tmax)
             res = rbind(res, data.frame(id = j, t=1:Tmax, regret))
           }
         })
  
  return(res)
}

Tmax = 1000
nCourbes = 10
pa = 0.65
pb = 0.55

data1 = simulation('1', pa, pb, Tmax, nCourbes)
data2 = simulation('2', pa, pb, Tmax, nCourbes)
data3 = simulation('3', pa, pb, Tmax, nCourbes)

p1 = ggplot(data=data1, aes(x=t, y=regret , group = id)) +
  geom_line(size=0.1) + 
  stat_summary(fun.y=mean, colour="red", geom="line", aes(group = 1))

p2 = ggplot(data=data2, aes(x=t, y=regret , group = id)) +
  geom_line(size=0.1) + 
  stat_summary(fun.y=mean, colour="red", geom="line", aes(group = 1))

p3 = ggplot(data=data3, aes(x=t, y=regret , group = id)) +
  geom_line(size=0.1) + 
  stat_summary(fun.y=mean, colour="red", geom="line", aes(group = 1))

Question 1

Par linéarité de l’esperance, l’esperance de la somme devient la somme d’esperance de variable de Bernoulli, ainsi \(E(G_{a}(T)) = T*p_{a}\)
De même \(E(G_{b}(T)) = T*p_{b}\)
Pour le dernier cas, le fait de choisir les machines dans l’ordre ou non n’affecte pas l’experience (suite d’experience indépendante). Ainsi, on peut calculer en supposant que les T/2 premières machines sont A et les suivantes B. On obtient deux sommes de 1 à T/2 que l’on transforme comme précèdemment d’où \(E(G_{1/2}(T)) = T/2*(p_{a} + p_{b})\)
On s’interesse à cette quantité car elle représente la différence de gain entre notre stratégie et celle que nous pourrions avoir en utilisant uniquement la meilleur machine (xa représente l’esperance d’une variable aléatoire suivant une loi de Bernoulli). Ainsi, plus le regret tant vers 0 plus notre stratégie se rapproche de l’optimalité.

Question 2

Cette stratégie semble bonne car les courbes représentant le regret sont proches de la valeur 0. Néanmoins on observe que si Pa et Pb sont proches alors il faut conssacrer un nombre d’essai important à l’identification de la machine afin d’éviter de tomber sur la mauvaise et ainsi avoir un regret trop important dans certain cas. Le regret moyen quant à lui reste très proche de 0.

Question 3

L’efficacité de cette stratégie depend des machines. En effet si l’une d’elle à une probabilité très faible (par rapport à l’autre machine) de nous faire gagnger, le fait de choisir la “mauvaise” machine dans certain cas augmente considérablement le regret. Ainsi, si le regret de cette stratégie n’est pas très bon il peut être judicieux de diminuer le paramètre epsilon.

Question 4

Cette stratégie semble bonne, le regret moyen est de 0. Pourtant dans le cas où l’une des machines à une probabilité proche de 1 de donner un gain le regret moyen diminue de manière significative. On remarque ainsi que la meilleur stratégie dans ce cas serait la stratégie 2.