Lucas Reygrobellet & Léo Jan

Q1

Lorsque l’on ne joue que sur la machine A, \[G_{A}(T) = \sum_{t=1}^{T}X_{A,t} \] \(G_{A}(T)\) suit une loi \(B(T,p_A)\) \(E(G_{A}(T)) = T*p_A\)

Lorsque l’on ne joue que sur la machine B, \[G_{B}(T) = \sum_{t=1}^{T}X_{B,t} \] \(G_{B}(T)\) suit une loi \(B(T,p_B)\) \(E(G_{B}(T)) = T*p_B\)

Lorsque l’on joue sur les 2 machines \[G_{m}(T) = \sum_{t=1}^{T/2}X_{A,t}+\sum_{t=1}^{T/2}X_{B,t} \] \((\sum_{t=1}^{T/2}X_{A,t})\) suit une loi \(B(\frac{T}{2},p_A)\) \((\sum_{t=1}^{T/2}X_{B,t})\) suit une loi \(B(\frac{T}{2},p_B)\)

\(E(G_{m}(T)) = \frac{T}{2}*p_A +\frac{T}{2}*p_B\)

Le regret, exprime la difference entre le gain a un instant donne et le gain maximal

En essayant differente strategie, on essayera de minimiser le regret, et ainsi de trouver la meilleure machine

Q2

Cette stratégie n’est pas optimale. En effet, le regret est assez élevé des le début. Au cours du temps, il diminue, mais il reste positif malgré tout (on cherche un regret = 0 pour une machine optimale)

Q3

Le regret moyen reste constamment à 0. Cette méthode est donc tres efficace!

Q4

Nous n’avons pas réussi à tracer le graphique correspondant, a cause d’une erreur dans notre code production de NAsError in if (gainA > gaintmp) { : valeur manquante là où TRUE / FALSE est requis
Nous sommes censé comparer deux nombres, cette erreur est donc étrange.

library(ggplot2)
set.seed(243254353)
pa=0.65
pb = 0.55
pdf=data.frame()
tmax=1000
N=100


strat0 <- function(){
  pdf1=data.frame()
  df = data.frame()
  for (j in 1:N){
    x=rbinom(1:tmax,1,pa)
    regret=(pa - cumsum(x)/(1:tmax))
    df=data.frame(id=j,t=(1:tmax),regret)
    pdf1=rbind(pdf1,df)
  }
  return (pdf1)
}


strat1 <- function(){
  e = 0.05 # epsilon
  pdf1=data.frame()
  df = data.frame()
  for (j in 1:N) { # On simule l'experience N fois
    x=c()
    gainA = 0
    gainB = 0
    regret=c()
    
    i=1
    while (i<=e*tmax) { # les e*tmax premier lancer, on joue alternativement sur Ma ou Mb
      if(i %% 2 == 0){ #permet d'alterner entre les 2 machines
        gainA = gainA + rbinom(1,1,pa) # on somme les gains
        regret = c(regret, (pa - gainA/i)) # on calcule le regret a chaque coup
        
      }
      else{
        gainB = gainB + rbinom(1,1,pb)
        regret = c(regret,(pb - gainB/i))
      }
      i = i+1
    }
    
    if (gainB < gainA){ # si la machine A etait plus rentable, on joue le reste des coups sur celle ci
      x=rbinom((e*tmax+1):tmax,1,pa)
      regret=c(regret,(pa - cumsum(x)/((e*tmax+1):tmax)))
      
    }
    else{
      x=rbinom((e*tmax+1):tmax,1,pb)
      regret=c(regret,(pb - cumsum(x)/((e*tmax+1):tmax)))
    }
    
    # on cree une data frame avec les donnees d'une simulation
    df=data.frame(id=j,t=(1:tmax),regret)
    # et on la rajoute dans la data frame des N simulations
    pdf1=rbind(pdf1,df)
  }
  return (pdf1)
}

strat2 <- function(){
  e=0.1
  pdf1=data.frame()
  df = data.frame()
  for (j in 1:N) {
    regret=c()
    gainA=0
    gainB=0
    ratio1=0
    ratio2=0
   
    pa=1-e 
    pb = e
     i=1
    while (i<=tmax) {
      if(pa == 1-e){# machine A a la meilleure proba, donc on joue dessus
        gainA = gainA + rbinom(1,1,pa)
        ratio1 = gainA/(i+1) # gainA : gain sur la machine A ; i+1 : nombre de coup+1 joue dessus
        regret = c(regret, (pa - gainA/i))
        
      }
      else{
        gainB = gainB + rbinom(1,1,pb)
        ratio2 = gainB/(i+1)
        regret = c(regret, (pb - gainB/i))
      }
      # a chaque coup, si la machine a a un meilleur ratio, on lui donne la meilleur proba
      if(ratio1>ratio2){
        pa = 1-e
        pb=e
      }
      else if(ratio2>ratio1){
       pb=1-e
       pa=e
      }
      else{ # si leur ratio est le meme, on tire au hasard entre les 2
        p = runif(1)
        if(p<=0.5){
          pa = 1-e
          pb=e
        }
        else{
          pb=1-e
          pa=e
        }

    }
      
      i = i+1
    }
   
    df=data.frame(id=j,t=(1:tmax),regret)
    pdf1=rbind(pdf1,df)
  }
  return (pdf1)
}

  

strat3 <- function(){
  pdf1=data.frame()
  df = data.frame()
  for (j in 1:N) {
    gaintmp = 0
    gainA=0
    gainB=0
    
    regret = c()
    ma1 = 0
    ma2 = 0
    mb1 = 0
    mb2 = 0
    i=1
    while(i<=tmax){
      x1 = runif(1)
      x2 = runif(1)
     
      
      p1 = dbeta(x1,shape1=ma1+1,shape2=ma2+1)
      p2 = dbeta(x2,shape1=mb1+1,shape2=mb2+1)
      if(p1 > p2){
        gaintmp = gainA
        gainA = gainA + rbinom(1,1,p1)
        # Il y a un probleme de boolean avec la condition suivante. Nous n'avons pas trouvé d'ou venait le bug
        if(gainA > gaintmp){
          ma1 = ma1+1
        }else{
           ma2 = ma2 + 1
        }
       
        regret = c(regret,(p1-gainA/i))
      }
      else{
        gaintmp=gainB
        x = rbinom(1,1,p2)
        gainB = gainB + x
        if (x>0){
           mb1 = mb1+1
        }
        else{
           mb2 = mb2 + 1
        }
       
        regret = c(regret,(p2-gainB/i))
      }
    
      i=i+1
    }
    df=data.frame(id=j,t=(1:tmax),regret)
    pdf1=rbind(pdf1,df)
  }
  return (pdf1)
}
x = data.frame()
#On fait un switch permettant de choisir les différentes stratégies
#Mais je ne comprend pas l'interet, sachant que il faut implémenter toutes les stratégies

# Strategie 0 : exemple
pdf = switch(1,strat0(),strat1(),strat2(),strat3())
ggplot(data=pdf,aes(t,regret, group=id)) + geom_line(alpha=.1)  + stat_summary(fun.y=mean,colour="red", geom="line", aes(group=1))

# Strategie 1
pdf = switch(2,strat0(),strat1(),strat2(),strat3())
ggplot(data=pdf,aes(t,regret, group=id)) + geom_line(alpha=.1)  + stat_summary(fun.y=mean,colour="red", geom="line", aes(group=1))

# Strategie 2
pdf = switch(3,strat0(),strat1(),strat2(),strat3())
ggplot(data=pdf,aes(t,regret, group=id)) + geom_line(alpha=.1)  + stat_summary(fun.y=mean,colour="red", geom="line", aes(group=1))

# Strategie 3
#pdf = switch(4,strat1(),strat2(),strat3())
#ggplot(data=pdf,aes(t,regret, group=id)) + geom_line(alpha=.1)  + stat_summary(fun.y=mean,colour="red", geom="line", aes(group=1))