Question Préléminaires

On sait que \(\forall M, \forall t, X_{M,t}\) ~ \(B(1, p_M)\).
Et \(G_M(T) = \sum_{t=1}^T X_{m(t),t}\). Donc \(G_M(T)\) ~ \(B(T, p_M)\) et \(E[G_M(T)] = Tp_M\).

Pour la suite, on étudiera spécifiquement \((p_A,p_B) = (0.65,0.55)\).
Le regret de la stratégie m est définie comme : \[R_m(t) = p_A - \frac{E[G_m(t)]}{t}\] Or \(p_A\) avec les valeurs étudiées est la probabilité nous pemettant de maximiser notre gain, et \(\frac{E[G_m(t)]}{t}\) est la probabilité de gain de la méthode m.
Le regret est donc la différence entre la probabilité maximisant le gain, et la probabilité de gain de la méthode m.
Ce calcul nous permet de comparer les méthodes et de trouver la plus efficace, celle dont le regret est le plus faible. En effet, plus la probabilité de la méthode m se rapproche de la probabilité maximale, plus la méthode est bonne et plus le regret sera faible.

Intuition

Q2. On apprend (un peu) puis on exploite

Avec cette stratégie, le regret évolue en deux phases:

  1. Le regret augmente constamment pendant la phase d’estimation des probabilités.
  2. Si l’on choisi la bonne machine, le regret reste constant. Sinon il augmente plus fortement.

Dans cette stratégie, le choix de \(\epsilon\) impacte fortement le regret.

  • Si l’on prend un \(\epsilon\) trop élevé, la phase 1 durera plus longtemps et donc le regret sera plus élevé. Par contre, on aura plus de chance de choisir la bonne machine dans la phase 2.
  • Si l’on prend un \(\epsilon\) trop faible, la phase 1 durera moins longtemps, le regret augmentera moins. Cependant on aura moins de chance de choisir la bonne machine dans la phase 2.

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

Ici aussi, le choix de \(\epsilon\) influence grandement la valeur du regret. Soit \(r_a\) le ratio de A et \(r_b\) celui de B. Prenons deux cas pour \(\epsilon\).

  • Soit \(\epsilon = 0.1\). Prenons \(p_a = 0.65\) et \(p_b = 0.55\). Au premier coup, on joue aléatoirement sur l’une des deux machines puisque leur ratio est 0. Admettons que l’on joue sur B et que l’on gagne.
    Alors \(r_a = 0\) et \(r_b = \frac{1}{2}\), donc on a 90% de chance de rejouer sur B et 10% de chance de jouer sur A. On a de faibles chances d’augmenter le ratio de la machine ayant la meilleure probabilité.
    Cette exemple nous montre une limite de cette stratégie : en prenant un epsilon très faible, on admet que les ratios représentent la réalité. Or ce n’est pas forcément le cas au début. Dans notre cas, il faudra un certain temps pour que la machine A soit choisie, mais son ratio augmentera plus rapidement. Et lorsque \(r_a\) aura dépassé \(r_b\), il deviendra fort improbable que \(r_b\) repasse devant.

Prenons un cas plus général, avec \(\epsilon = 0.25\). Lors des premiers choix de machine, le regret alternera entre des augmentations et des conservations de sa valeur. Plus on effectuera de tirage, plus les augmentations seront rare, et plus le regret se stabilisera. Du fait que les ratios s’éloignent.

Q4. On tire au hasard en biaisant selon nos observations

Plus on effectue de tirages, plus la densité beta de A (resp B) se rapproche de \(p_a\) (resp \(p_b\)), et plus on choisit la machine ayant la meilleure probabilité. Ce qui entraine une stabilisation du regret.

Code

# Calcule le regret à partir d'un vecteur de valeur
compute_regret = function(tab, pa, Tmax){
  regret = c()
  for(i in 1:Tmax){
    regret = c(regret, pa - sum(tab[1:i])/i)
  }
  return(regret)
}

Q2.

simu1 = function(pa, pb, Tmax, e){
  v = c()
  
  # epsilon*Tmax premier tirage alternativement sur A et B
  va = rbinom(e*Tmax/2, 1, pa)
  vb = rbinom(e*Tmax/2, 1, pb)
  
  # Calcul des gains sur chaque machine
  na = sum(va)
  nb = sum(vb)
  
  # On replace les tirage dans l'ordre 
  for(i in seq(2, e*Tmax, 2)){
    v[i-1] = va[i/2]
    v[i] = vb[i/2]
  }
  
  # On joue uniquement sur la machine qui a fait le plus de gain
  if(na > nb){
    v = c(v, rbinom(Tmax - length(v), 1, pa))
  } else {
    v = c(v, rbinom(Tmax - length(v), 1, pb))
  }
  
  # On calcule le regret de la simulation
  regret = compute_regret(v, max(pa, pb), Tmax)
  
  # Data frame de retour
  df = data.frame(t = (1:Tmax), r = regret)
  
  return (df)
}

Q3.

simu2 = function(pa, pb, Tmax, eps){
  
  # Stockage des ratio de A et de B
  ratioA = 0
  ratioB = 0
  
  # Stockage de la probabilité pour le prochain tirage
  p = 0
  
  # Stockage des valeurs tirées
  v = c()
  
  # Stockage des valeurs pour calculer les ratios
  nbjA = 0
  nbjB = 0
  nbgA = 0
  nbgB = 0
  
  # On effectue Tmax tirages
  for(i in 1:Tmax){
    
    # Choix de la probabilité à utiliser en fonction des ratios
    if(ratioA == ratioB){
      p = sample(1, x = c(pa,pb), prob = c(0.5,0.5))
    }
    else if(ratioA > ratioB){
      p = sample(1, x = c(pa,pb), prob = c(1-eps,eps))
    }
    else{
      p = sample(1, x = c(pa,pb), prob = c(eps,1-eps))
    }
    
    # Récupeération de la valeur du tirage
    v = c(v, rbinom(1, 1, p))
    
    # Mise à jour des ratios
    if(p == pa){
      nbgA = nbgA + v[i]
      nbjA = nbjA + 1
      ratioA = nbgA/(nbjA+1)
    }
    else{
      nbgB = nbgB + v[i]
      nbjB = nbjB + 1
      ratioB = nbgB/(nbjB + 1)
    }
  }
  # Calcul du regret
  regret = compute_regret(v, pa, Tmax)
  
  # Data frame de retour
  df = data.frame(t = (1:Tmax), r = regret)
  return(df)
}

Q4

simu3 = function(pa, pb, Tmax){
  # Stockage reussite de chaque machines
  nbrA = 0 
  nbrB = 0
  
  # Stockage echec de chaque machines
  nbeA = 0
  nbeB = 0
  
  # Stockage resultat de chaque tirages
  v = c()
  for (i in 1:Tmax) {
    # Tirage de 2 nombre suivant les lois beta de chaque machines
    numA = rbeta(1, shape1 = nbrA+1, shape2 = nbeA+1)
    numB = rbeta(1, shape1 = nbrB+1, shape2 = nbeB+1)
    
    # Tirage plus mise à jour des nb de reussite et d'echec
    if(numA>numB){
      v = c(v, rbinom(1,1,pa))
      nbrA = nbrA + v[i]
      nbeA = nbeA + 1 - v[i]
    }
    else{
      v = c(v, rbinom(1,1,pb))
      nbrB = nbrB + v[i]
      nbeB = nbeB + 1 - v[i]
    }
  }
  # Calcul du regret
  regret = compute_regret(v, max(pa,pb), Tmax)
  
  # Data frame de retour
  df = data.frame(t = (1:Tmax), r = regret)
  return(df)
}
choix_simu = function(num = 1, pa = 0.65, pb = 0.55, Tmax = 1000, eps){
  
  # Set la seed pour toujours effectuer les mêmes tirages
  set.seed(1)
  library("ggplot2")
  library("dplyr")
  
  # Data frame dans laquelle on stocke tout les tirages
  df = data.frame()
  
  N = 100
  
  # On effectue N simulations
  for(i in 1:N){
    sim = switch(num,
                 simu1(pa, pb, Tmax, eps),
                 simu2(pa, pb, Tmax, eps),
                 simu3(pa, pb, Tmax))
    
    # Ajout dans la data frame globale
    df = rbind(df, data.frame(sim, Idx = rep(i, Tmax), couleur = "Simulation"))
  }
  
  # Calcul de la moyenne des simulations
  moy = df %>% group_by(t) %>% select(r) %>% summarize(r = mean(r))
  
  # Ajout dans la data frame globale
  df = rbind(df, data_frame(t = moy$t, r = moy$r, Idx = rep(N+1, Tmax), couleur = "Moyenne"))
  
  # Affichage des simulations
  ggplot(df, aes(x = t, y = r, group = Idx, color = couleur)) + geom_line() + theme_bw() + labs(x = "Temps", y = "Regret")
}

Méthode 1

choix_simu(num = 1, eps = 0.1)
## 
## Attaching package: 'dplyr'
## The following objects are masked from 'package:stats':
## 
##     filter, lag
## The following objects are masked from 'package:base':
## 
##     intersect, setdiff, setequal, union
## Adding missing grouping variables: `t`

On se rend compte avec cette méthode qu’il y a bien les cas où on choisit la bonne méthode et les cas où on choisit pas la bonne. En effet, après avoir dépassé la moitié du temps, il y a une démarquation et on voit aucune simulation dans un certain intervalle.

En choisissant un \(\epsilon\) trop faible (inférieur de 0,05), on a remarqué que la démarquation se fait plus tôt et que celà empeche le regret de diminuer car les simulations où la bonne machine a été choisie et celles où on a pas choisie la bonne vont se cumuler et vont empêcher de faire diminuer le regret moyen.

A l’inverse, en prenant un \(\epsilon\) bien plus important (supérieur à 0,01), on voit un intervalle vraiment important au début entre le regret le plus important et le regret le moins important. Cependant, dans ce cas, ayant beaucoup moins de chance de se tromper, on voit qu’à la fin, le regret diminue et se rapproche de 0, qu’il y a que très peu de simulations qui augmente et enfin que les simulations se regroupent sur un très faible intervalle.

On a donc choisie de prendre un \(\epsilon\) plutôt important afin d’utiliser cette méthode de manière la plus efficace possible sachant que ca ne servait à rien de trop l’augmenter non plus, car celà ne modifie presque pas le regret moyen final.

Cette méthode est donc intéressante car avec un bon choix de \(\epsilon\), il est possible de rendre cette méthode plutôt efficace. Cependant, ce choix de \(\epsilon\) est borné et nous permet d’être efficace jusqu’à un certain point car comme prévu, plus notre variable est importante, moins les risques de se tromper sont faibles, mais moins le regret à le temps de diminuer une fois la machine choisie.

Méthode 2

choix_simu(num = 2, eps = 0.1)
## Adding missing grouping variables: `t`

Avec cette méthode aussi, on a pris deux choix de \(\epsilon\) pour vérifier les deux cas qui nous semblait interessant de regarder d’après nos estimations.

Prenons tout d’abord un \(\epsilon\) plutôt important (supérieur à 0.3). Dans ce cas, on peut voir que les simulations se regroupent sous un petit intervalle, qu’elles ont à peu près le même regret moyen. Par contre, on voit que la valeur du regret moyen est plutôt important et au moins aussi efficace que celui de la méthode précédente. Ce qui semble indiquer que cette méthode n’est pas plus effiace avec cette valeur de \(\epsilon\). N’ayant pas une très grande confiance dans les ratios étant donné le \(\epsilon\) choisie, le regret ne peut pas vraiment diminuer à long terme comme nous l’avions prévu.

Prenons maintent un \(\epsilon\) plus faible (inférieur à 0.1). Dans ce cas, la première chose qui frappe est que les regrets ne se regroupent pas. Il y a beaucoup de valeurs différentes pour les regrets finaux. Cependant, on voit que la valeur du regret moyen est plus faible avec ce choix. De plus, on voit que contrairement à l’autre cas, il y a une plus petite diminution du regret moyen au départ mais que la réduction est continue au court du temps comme nous l’avions prévu.

D’après nos 2 valeurs, on peut donc voir qu’il faut prendre une valeur comprise entre ces deux cas pour pouvoir cumuler les avantages des deux cas, c’est à dire une diminution plutôt rapide au départ du regret moyen mais avec une réduction constante après ce qui nous donne le regret le plus faible à la fin, ainsi que des simulations plutôt regroupées.

Dans ce cas là alors, la méthode est plus efficace que la précédente mais il y a encore trop d’écarts entre les simulations, notamment au début, comme on le craignait dans nos estimations.

Méthode 3

choix_simu(num = 3, eps = 0.1)
## Adding missing grouping variables: `t`

Pour cette dernière méthode, nous avons pris les mêmes valeurs que pour la méthode dernière et nous sous sommes rendus compte que la variation de \(\epsilon\) dans cette méthode n’avait quasiment aucune influence. En effet, avec une valeur importante ou plutôt faible, l’écart entre les simulations est similaires, il y a une réduction régulière qui commence assez rapidement, les simulations donnent globalement un regret plutôt identique et extrèmement faible, bien plus faible que les regrets moyens des dernières méthodes.

On a donc bien la méthode la plus efficace comme nous l’avions la dernière fois. En effet, elle résout les problèmes rencontrés avec les anciennes méthodes : le regret moyen plutôt important pour la première et les écarts plutôt important dans la deuxième.