Corentin Chasseguet - Alexis Lattard

Q1.

La stratégie consistant à jouer uniquement sur la machine A a une espérance de \(E(G_{m}(T)) = \sum\limits_{k=1}^T X_{A,k} P_A = P_A\times \sum\limits_{k=1}^T X_{A,k}\) Or \(X_{A,k}\) n’a que deux valeurs possibles, \(0\) et \(1\). Cela nous donne donc \(P_A\times \sum\limits_{k=1}^T 1 = T\times P_A\)
La stratégie consistant à jouer uniquement sur la machine B utilise le même principe, on a donc \(E(G_{m}(T)) = T\times P_A\)
Après un nombre de lancers \(T\) grand, on se rapprochera de ce résultat : \(\frac{T}{2}\times (P_A + P_B)\)
Le regret représente la différence entre \(P_A\) et la moyenne de notre espérance qui est en fait la probabilité de gagner dans la stratégie qu’on a utilisé. Dans le cas où \(P_A\) est toujours plus élevé, cette différence représente à quel point on s’est éloigné de la stratégie la plus efficace, d’où le nom de regret. Dans un algorithme optimisé, on s’attend à ce que ce regret tende vers 0.

Q2.

set.seed(1)

Reg_mL = function(index, E, Tmax, pA, pB) {
  sommeA = 0
  sommeB = 0
  regret = c()
  
  t = 1
  while (t <= E*Tmax/2) {
    r = runif(1)
    if (r < pA) {
      sommeA = sommeA + 1
    }
    regret[2*t - 1] = pA - (sommeA + sommeB)/(2*t - 1)
    
    r = runif(1)
    if (r < pB) {
      sommeB = sommeB + 1
    }
    regret[2*t] = pA - (sommeA + sommeB)/(2*t)
    
    t = t + 1
  }
  
  if (sommeA >= sommeB) {
    p_opt = pA
    p_nopt = pB
  } else {
    p_opt = pB
    p_nopt = pA
  }
  sommeAB = sommeA + sommeB
  
  t = E*Tmax + 1
  while (t <= Tmax) {
    r = runif(1)
    if (r < p_opt) {
      sommeAB = sommeAB + 1
    }
    regret[t] = pA - sommeAB/t
    
    t = t + 1
  }
  
  return(data.frame(Id = index, t = (1:Tmax), RmL = regret))
}

library("ggplot2")
Regret = data.frame()

Tmax = 1000
i = 1
while (i <= 100) {
  index = rep.int(i, Tmax)
  f = Reg_mL(index, 0.05, Tmax, 0.65, 0.55)
  Regret = rbind(Regret, f)
  
  i = i + 1
}
ggplot(Regret, aes(x = t, y = RmL, group = Id)) + geom_line(alpha = 0.1)

Cette stratégie n’est pas particulièrement bonne tout simplement par le fait que, peu importe le nombre d’essais qu’on fait au départ pour estimer quelle est la borne la plus prometteuse, il y a un risque qu’on se trompe et qu’on soit totalement à côté de la plaque comme toutes les courbes ci-dessus qui tendent vers \(0.1\). Néanmoins cela reste un meilleur moyen en moyenne que celui qui est de jouer au hasard sur une machine ou celui de jouer autant sur les deux, puisqu’on va souvent trouver la “bonne” machine.

Q3.

set.seed(666)

jeu_machine = function(p, somme, t) {
  r = runif(1)
  if (r < p) {
    somme = somme + 1
  }
  t = t + 1
  return(list(somme, t))
}

Reg_mG = function(index, Ec, Tmax, pA, pB) {
  sommeA = 0
  tA = 0
  sommeB = 0
  tB = 0
  regret = c()
  
  t = 1
  while (t <= Tmax) {
    ratioA = sommeA/(tA + 1)
    ratioB = sommeB/(tB + 1)
    
    r = runif(1)
    if (ratioA > ratioB) {
      if (r < Ec) {
        l = jeu_machine(pB, sommeB, tB)
        sommeB = as.numeric(l[1])
        tB = as.numeric(l[2])
      } else { # r > Ec
        l = jeu_machine(pA, sommeA, tA)
        sommeA = as.numeric(l[1])
        tA = as.numeric(l[2])
      }
    } else if (ratioA == ratioB) {
      if (r < 0.5) {
        l = jeu_machine(pA, sommeA, tA)
        sommeA = as.numeric(l[1])
        tA = as.numeric(l[2])
      } else { # r > 0.5
        l = jeu_machine(pB, sommeB, tB)
        sommeB = as.numeric(l[1])
        tB = as.numeric(l[2])
      }
    } else { # ratioA < ratioB
      if (r < Ec) {
        l = jeu_machine(pA, sommeA, tA)
        sommeA = as.numeric(l[1])
        tA = as.numeric(l[2])
      } else { # r > Ec
        l = jeu_machine(pB, sommeB, tB)
        sommeB = as.numeric(l[1])
        tB = as.numeric(l[2])
      }
    }
    
    regret[tA+tB] = pA - (sommeA + sommeB)/(t)
    t = t + 1
  }
  
  return(data.frame(Id = index, tps = (1:Tmax), RmG = regret))
}

library("ggplot2")
Regret = data.frame()

Tmax = 1000
i = 1
while (i <= 100) {
  index = rep.int(i, Tmax)
  f = Reg_mG(index, 0.1, Tmax, 0.65, 0.55)
  Regret = rbind(Regret, f)
  
  i = i + 1
}

ggplot(Regret, aes(x = tps, y = RmG, group = Id)) + geom_line(alpha = 0.1)

Cette stratégie commence à être plus optimisée : on affine tout du long des mesures nos estimations de ce qui est la meilleure machine, cela permet d’être plus proche de 0 sur le regret. Cependant même si on est presque sûr qu’une machine est la meilleure (dans le cas où l’on aurait \(P_A = 0.75\) et \(P_B = 0.1\) par exemple), on a toujours une probabilité \(\epsilon\) élevée de choisir la mauvaise machine, ce qui donne lieu à quelques courbes qui sont légèrements au-dessus de \(0\).

Q4.

set.seed(42)

Reg_mT = function(index, Tmax, pA, pB) {
  essaisA = 0
  victoiresA = 0
  essaisB = 0
  victoiresB = 0
  regret = c()

  t = 1
  while (t <= Tmax) {
    rA = rbeta(1, victoiresA + 1, (essaisA - victoiresA) + 1)
    rB = rbeta(1, victoiresB + 1, (essaisB - victoiresB) + 1)
    r = runif(1)
    if (rA > rB) {
      essaisA = essaisA + 1
      if (r < pA) {
        victoiresA = victoiresA + 1
      }
    } else {
      essaisB = essaisB + 1
      if (r < pB) {
        victoiresB = victoiresB + 1
      }
    }
    
    regret[t] = pA - (victoiresA + victoiresB)/t
    t = t + 1
  }
  return(data.frame(Id = index, tps = (1:Tmax), RmT = regret))
}

library("ggplot2")
Regret = data.frame()

Tmax = 1000
i = 1
while (i <= 100) {
  index = rep.int(i, Tmax)
  f = Reg_mT(index, Tmax, 0.65, 0.55)
  Regret = rbind(Regret, f)
  
  i = i + 1
}

ggplot(Regret, aes(x = tps, y = RmT, group = Id)) + geom_line(alpha = 0.1)

La stratégie devient encore meilleure, puisque la différence par rapport à la précédente est qu’on n’utilise plus une probabilité fixe de changer de machine, celle-ci dépend des chances qu’on a de gagner sur cette machine en fonction du nombre d’essais qu’on y a fait. Cela évite de jouer trop sur une machine très mauvaise, mais permet de ne pas trop vite rejeter une machine sur laquelle on a peu joué juste parce qu’on aurait gagné plusieurs fois de suite sur l’autre. On remarque effectivement que la grande majorité des courbes semblent tendre vers \(0\).