Sujet 1 : Au Casino

Pour pouvoir afficher les graphiques clairement dans la suite du DM, nous avons placé notre code en première partie, puis, vous trouverez les réponses aux différentes questions ainsi que nos intuitions en deuxième partie. Les différentes stratégies (1, 2, 3, L, G, T) sont exécutées à l’aide d’un switch à la toute fin du code.

Code

set.seed(987) # Sauvegarde de la graine

# Initialisation du contexte de simulation
N = 100 # Nombre de trajectoires
Tmax = 2000 # Nombre de tirages par trajectoire
pa = 0.65 # Probabilité de gain sur la machine A
pb = 0.55 # Probabilité de gain sur la machine B
eps = 0.05 # Pour la question 2
epsb = 0.1 # Pour la question 3

# Fonction qui met en pratique la stratégie mL
strat_L <- function(pa, pb, Tmax, eps){
  # On tire une fois sur deux en utilisant la machine A pour t allant de 1 à Tmax*eps
  debut_pa = cumsum(rbinom(1:(Tmax*eps), 1, c(pa, 0)))
  # Puis une fois sur deux en utilisant la machine B pour t allant de 1 à Tmax*eps
  debut_pb = cumsum(rbinom(1:(Tmax*eps), 1, c(0, pb)))
  # On stocke la probabilité de la machine qui a généré le plus de gains
  best_p = if(debut_pa[Tmax*eps] > debut_pb[Tmax*eps]){pa} else {pb} 
  # On combine les précédents tirages alternatifs
  debut_total = debut_pa + debut_pb
  # Puis, on finit d'effectuer nos tirages pour t allant de Tmax*eps+1 jusqu'à Tmax avec la probabilité récupérée précedemment
  res_fin =  c(debut_total, debut_total[Tmax*eps] + cumsum(rbinom((Tmax*eps+1):Tmax, 1, best_p)))
  # On retourne nos résultats sous forme d'un vecteur
  return(res_fin)
}

# Fonction qui met en pratique la stratégie mG
strat_G <- function(pa, pb, Tmax, epsb){
  temp = 0
  succesA = 0
  succesB = 0
  tentativeA = 1
  tentativeB = 1
  res = c()
  
  # On répète les actions suivantes pour chaque tirage
  for(i in 1:Tmax){
    # On détermine la machine la plus prometteuse en fonction des succès
    selectedMachine = sample(c('A','B'), 1, TRUE,
                             if(succesA/tentativeA == succesB/tentativeB){
                               c(0.5,0.5)
                             }else{
                               if(succesA/tentativeA > succesB/tentativeB){
                                 c(1-epsb,epsb)
                               }else{
                                 c(epsb,1-epsb)
                               }
                             })
 
    # On effectue le tirage suivant la machine sélectionnée et on incrémente les variables concernant la tentative et le succès pour la machine sélectionnée
    switch(selectedMachine,
      'A' = {
        temp = rbinom(1, 1, pa)
        tentativeA = tentativeA + 1
        succesA = succesA + temp
        },
      'B' = {
        temp = rbinom(1, 1, pb)
        tentativeB = tentativeB + 1
        succesB = succesB + temp
      }
    )
   
    # On concatène les résultats du tirage que l'on vient d'effectuer avec les précedents
    res = c(res, temp)
  }
  
  # On retourne la somme cumulée de nos résultats sous forme d'un vecteur
  return(cumsum(res))
}
 
# Fonction qui met en pratique la stratégie mT
strat_T <- function(pa, pb, Tmax){
  temp = 0
  succesA = 0
  echecA = 0
  succesB = 0
  echecB = 0
  res = c()
 
  # On répète les actions suivantes pour chaque tirage
  for(i in 1:Tmax){
    # Calcul des vraisemblances de pa et pb
    vraisA = rbeta(1, shape1 = succesA + 1, shape2 = echecA + 1)
    vraisB = rbeta(1, shape1 = succesB + 1, shape2 = echecB + 1)
   
    # On effectue notre tirage sur la machine ayant la meilleure vraisemblance et on incrémente les variables concernant le succès ou l'échec pour la machine sélectionnée de ce tirage
    if(vraisA > vraisB){
      temp = rbinom(1, 1, pa)
      if(temp == 1){succesA = succesA + 1}else{echecA = echecA + 1}
    }else{
      temp = rbinom(1, 1, pb)
      if(temp == 1){succesB = succesB + 1}else{echecB = echecB + 1}
    }
   
    # On concatène les résultats du tirage que l'on vient d'effectuer avec les précedents
    res = c(res, temp)
  }
  
  # On retourne la somme cumulée de nos résultats sous forme d'un vecteur
  return(cumsum(res))
}
 
# Fonction qui simule les résultats pour la stratégie start  (= '1','2','3','L','G','T') sur N trajectoires de Tmax tirages avec pa la probabilité de gain de la machine A, pb la probabilité de gain de la machine B et eps, epsb des valeurs renseignées pour les questions 2 et 3
simuRegret <- function(strat,pa,pb,Tmax,N,eps,epsb){
  res = data.frame() # On initialise le dataFrame qui contiendra nos résultats
  
  # Pour chaque stratégie, on créé un dataFrame contenant les résultats pour la trajectoire en cours, et on les ajoute au dataFrame res qui contiendra les trajectoires allant de 1 à N pour l'affichage
  for(i in 1:N){
    switch(strat,
      '1'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), regret=(pa-(cumsum(rbinom(1:Tmax, 1, pa))/(1:Tmax)))))
      },
      '2'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), regret=(pa-(cumsum(rbinom(1:Tmax, 1, pb))/(1:Tmax)))))
      },
      '3'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), 
                                    regret=(pa-cumsum(rbinom(1:Tmax, 1, 
                                                             sample(c(pa, pb), Tmax, TRUE, c(0.5, 0.5))))/(1:Tmax))))
      },
      'L'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), regret=pa-strat_L(pa, pb, Tmax, eps)/(1:Tmax)))
      },
      'G'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), regret=pa-strat_G(pa, pb, Tmax, epsb)/(1:Tmax)))
      },  
      'T'={
        res = rbind(res, data.frame(id=i, t=(1:Tmax), regret=pa-strat_T(pa, pb, Tmax)/(1:Tmax)))
      }
    )
  }

  # Affichage du graphique contenant les trajectoires suivant la stratégie choisie en noir et la trajectoire moyenne en vert
  ggplot(data=res, aes( x=t, y=regret , group =id)) + geom_line(size=0.10) + ggtitle(paste("Estimation du regret en fonction des tirages t sur N trajectoires en utilisant la", "\nstratégie m",strat)) + stat_summary(fun.y=mean, colour="green", geom="line", aes(group = 1))
}

Question 1 : Questions préliminaires

\(\color{red}{\text{Les formes closes :}}\)

Forme close (en fonction de \(T\), \(p_{A}\) et \(p_{B}\)) pour \(E[G_{m}(T)]\) quand :

  • Pour \(m_{1}\), la stratégie qui consiste à jouer systématiquement la machine \(M_{A}\) : On a \(\sum^T_{t=1} X_{A,t}\) ~ \(\beta(T,p_{A})\) donc \[E[G_{m_{1}}(T)] = T*p_{A}\]

  • Pour \(m_{2}\), la stratégie qui consiste à jouer systématiquement la machine \(M_{B}\) : On a \(\sum^T_{t=1} X_{B,t}\) ~ \(\beta(T,p_{B})\) donc \[E[G_{m_{2}}(T)] = T*p_{B}\]

  • Pour \(m_{3}\), la stratégie qui consiste à jouer la machine \(M_{A}\) avec probabilité 1/2 et la machine \(M_{B}\) avec probabilité 1/2 :

      On a \(Y_t\) une variable aléatoire pour le gain qui suit une loi de Bernouilli 1/2.
      En découle, \(P(Y_t=1) = 1/2*p_A + 1/2*p_B\) et \(P(Y_t=0) = 1-P(Y_t=1)\).
      La variable aléatoire \(Y\) qui vaut \(\sum^T_{t=1}Y_t\) ~ \(\beta(T,1/2*p_A + 1/2*p_B)\) donc \[E[G_{m_{3}}(T)] = T/2*p_{A} + T/2*p_{B}\]

\(\color{red}{\text{Le regret :}}\)

On s’intéresse à la quantité \(R_m(t) = p_A − \frac{E[G_m(t)]}{t}\), aussi appelée regret, car elle peut nous aider à savoir si notre stratégie est optimale ou pas.

En effet, le regret est la différence entre la probabilité d’obtenir le meilleur gain possible, toutes stratégies confondues, et la probabilité de gain à l’instant t en utilisant une stratégie particulière. On s’intéresse au regret \(R_m(t)\) en sachant que n’utiliser que A est la meilleure stratégie possible \((p_A = 0.65>p_B=0.55)\), d’où la différence avec \(p_A\).

Une bonne stratégie est une stratégie dont le regret est minimum, le plus proche de 0 possible, autrement une stratégie qui se rapproche de la meilleure stratégie possible.

On donne ci-après les modélisations pour les trois premières stratégies présentées dans la question 1 :

Modélisation pour la stratégie \(m_1\)

simuRegret('1',pa,pb,Tmax,N,eps,epsb)

Modélisation pour la stratégie \(m_2\)

simuRegret('2',pa,pb,Tmax,N,eps,epsb)

Modélisation pour la stratégie \(m_3\)

simuRegret('3',pa,pb,Tmax,N,eps,epsb)

On se rend bien compte la stratégie \(m_1\) où l’on n’utilise que la machine \(M_A\) est la plus performante, le regret est assez constant et s’approche rapidement de zéro. Pour la stratégie \(m_2\) qui n’utilise que la machine \(M_B\), le regret est aussi constant mais bien moins proche de zéro comme en témoigne la courbe de moyenne. Enfin, pour \(m_3\) où l’on utilise autant \(M_A\) que \(M_B\), le regret est meilleur que pour la stratégie \(m_3\) mais moins bon que celui de la stratégie \(m_1\).

\(m_1\) est la meilleure stratégie, comme prévu, car \(M_A\) a plus de chance de gain que \(M_B\).

Question 2 : On apprend (un peu) puis on exploite

La stratégie \(m_L\)

En utilisant cette stratégie on teste les deux machines \(M_A\) et \(M_B\) alternativement pendant un certain laps de temps \(t\) allant de \(1\) à \(eps*Tmax\). A l’issue de ces tests, la machine ayant généré le plus de gains est conservée et on termine la simulation pour \(t\) allant de \(eps*Tmax\) à \(Tmax\) en utilisant uniquement cette dernière.

Intuition

Nous pensons que, lors de cette simulation, un grand nombre de trajectoires aura un regret qui tendra vers 0 rapidement et quelques trajectoires auront un regret différent, similaire à celui que l’on retrouve en utilisant la machine \(M_B\). En effet, durant la phase de tests, si l’on a eu plus de chance en utilisant la machine \(M_B\) que la machine \(M_A\) (ce qui est peu probable au vu des probabilités propres \(p_A\) et \(p_B\)), on continuera de jouer la machine \(M_B\) pour la suite de l’expérience, le regret sera donc plus grand dans quelques cas.

Modélisation

simuRegret('L',pa,pb,Tmax,N,eps,epsb)

Observations

On retrouve un graphique qui prouve notre intuition. Durant la phase de tests des deux machines de manière alternative, on aura pu avoir soit :

  • La machine \(M_A\) est meilleure

  • La machine \(M_B\) est meilleure

Ce qui explique pourquoi certains regrets approchent les résultats de la simulation en n’utilisant que \(M_A\) et d’autres en n’utilisant que \(M_B\).

Etant donné que \(p_A > p_B\), il est, en théorie, plus probable que la machine \(M_A\) soit meilleure que la machine \(M_B\), ce qui explique pourquoi on retrouve plus de regrets s’approchant de \(0\) que de regrets s’approchant de \(0.1\).

Le fait que quelques expériences se terminent en considérant que la machine \(M_B\) est la meilleure est problématique car l’on sait que c’est faux et cela peut être optimisé.

On peut donc dire que cette méthode est appromative et qu’elle pourrait être améliorée, dans certains cas (quand le regret est proche de \(0\)) les chances de gains sont plus élevées mais dans d’autres on se retrouve avec un regret bien plus fort qui pourrait être évité en utilisant les stratégies suivantes.

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

La stratégie \(m_G\)

Pour chaque tirage et pour chaque machine \(M_A\) ou \(M_B\), on calcule \(\frac{nb succès}{nb tentatives + 1}\) et on s’en sert pour déterminer qu’elle est la machine qui semble rapporter le plus. La machine la plus prometteuse est ensuite utilisée avec une probabilité \(1-epsb\) tandis que l’autre machine est utilisée avec une probabilité \(epsb\). Si les ratios des deux machines sont égaux alors on choisit au hasard l’une des deux.

Intuition

Cette stratégie semble être meilleure que la précédente et le regret devrait assez rapidement se rapprocher de 0 puisque que l’on se dirigera progressivement vers la meilleure machine à l’aide du ratio calculé.

Cependant, il est toujours possible que le ratio “mente” et que la moins bonne machine (\(M_B\)) gagne plus que l’autre (\(M_A\)) dans les cas où le joueur n’a pas de chance. A ce moment là, le ratio pourrait s’avérer faussé et ainsi nous aurions du mal à trouver la meilleure machine.

Modélisation

simuRegret('G',pa,pb,Tmax,N,eps,epsb)

Observations

Cette stratégie est bien meilleure que la précédente, on ne retrouve plus deux groupes distincts de regrets et le regret tend vers \(0\).

En effet, la machine \(M_A\) ayant une probabilité de gains supérieure à celle de \(M_B\), il est plus probable que son ratio soit plus élevé et qu’elle soit préférée au cours de la simulation.

Mais, comme prévu, on observe toujours des regrets un peu moins condensés autour du \(0\) qui témoignent que dans certains cas, la machine \(M_B\) a mieux fonctionné que \(M_A\), que son ratio était donc supérieur et qu’elle a été favorisée.

Question 4 : On tire au hasard en biaisant selon nos observations

La stratégie \(m_T\)

En utilisant cette stratégie on améliore la stratégie précédente (\(m_G\)).

En effet, on se sert toujours du nombre de succès et du nombre de tentatives sur chaque machine mais on calcule aussi la vraisemblance des probabilités qui en résultent. La probabilité \(p_{Acalculée}\) ou \(p_{Bcalculée}\) la plus vraisembable sert ainsi à déterminer quelle machine il faut utiliser pour le tirage en cours. On répète l’expérience à chaque tirage.

Intuition

Cette stratégie semble meilleure que les deux précédentes car l’on calcule la vraisemblance des probabilités. On pourra ainsi déterminer si une probabilité semble correcte ou non et orienter plus sûrement notre choix vers la meilleure machine.

Modélisation

simuRegret('T',pa,pb,Tmax,N,eps,epsb)

Observations

On observe que cette dernière stratégie est la meilleure entre les stratégies \(m_L\), \(m_G\) et \(m_T\).

En effet, le regret tend vers 0 et plus rapidement qu’avec les autres stratégies car notre choix de machine est guidé par la vraisemblance des probabilités générées. Il devient donc bien plus probable de jouer avec la machine \(M_A\) qui a la meilleure probabilité réelle (\(0.65\)) qu’avec \(M_B\).

En conclusion, la technique \(m_T\) est la stratégie à favoriser si l’on souhaite jouer sur les deux machines \(M_A\) et \(M_B\) car elle raportera plus de gains.