Devoir Maison de Probabilité et Statistique
Damien WYKLAND, Jeremy MASSON
November 28, 2018
Sujet : Au casino
Intuitions :
Avant de commencer à programmer, nous avons essayé de répondre aux questions par simple intuition.
La première question nous permet de comprendre de suite que la meilleure stratégie possible serait de ne jouer que la machine A, car elle a la plus grande probabilité de victoire dans notre exemple. Cependant, le but de ce projet est de trouver une stratégie permettant finalement, en jouant sur les deux machines, d’approcher au maximum le gain maximal possible. L’introduction du rejet semble donc naturelle.
La première stratégie semble être, sur le papier, plutôt bonne. On effectue une phase d’observation où l’on tire sur une machine puis sur l’autre de manière alternée afin d’avoir une idée de la probabilité de gain de chaque machine avant de ne tirer que sur celle qui semble avoir la probabilité de gain la plus élevée. On peut ainsi dire que l’on sacrifie une partie de nos tirages afin d’avoir une idée globale des probabilités des deux machines. On imagine qu’il faut juste faire attention à la valeur epsilon choisie : si on estime mal la machine qui semble la meilleure, on continuera tous les autres tirages avec la machine qui n’a pas la plus grande probabilité de victoire.
La seconde stratégie semble meilleure car au lieu d’apprendre juste sur une plage donnée de parties, elle a une chance d’apprendre pendant toute la durée de la simulation. Mais ça sera surement aussi un désavantage car au lieu de se concentrer sur la machine “gagnante”, on va perdre du temps à continuer à jouer aussi la machine “perdante” de temps en temps. L’impact sur la moyenne du regret dans le temps devrait être assez important.
Enfin, la dernière stratégie est assez dure à estimer sur le papier d’après nous. En effet, au lieu de toujours prendre la valeur la plus vraisemblable de victoire pour la machine A et B et les comparer, on va utiliser une loi beta. Cela ajoute beaucoup d’inconnu pour calculer à l’avance le résultat, mais on peut imaginer que la loi beta devenant de plus en plus précise, la moyenne du regret dans le temps deviendra bonne, de plus, comparé à la deuxième stratégie, ici aucune obligation de se “forcer” de jouer la stratégie perdante.
Question 1 : Questions préliminaires
Justification :
On sait que chaque tirage est indépendant et uniquement distribué selon une loi Binomiale, c’est à dire que pour chaque machine \(M \varepsilon {A,B}\) on modélise chaque tirage par \(\forall M,\forall t, X_{M,t}∼ B(1,p_M)\). Le gain d’une stratégie m est définie par \(G_m(T) = \sum_{t=1}^{T}X_{m(t),t}\). On souhaite calculer l’espérance du gain de différentes stratégies de jeu. Pour une loi binomiale on sait que l’espérance est égale à \(np\).
- Pour la stratégie qui consiste à jouer systématiquement sur la machine \(M_A\) on a donc: \(E[G_m(T)] = \sum_{i=1}^{T}1*p_a = T*p_a\).
- Pour la stratégie qui consiste à jouer systématiquement sur la machine \(M_B\): \(E[G_m(T)] = \sum_{i=1}^{T}1*p_b=T*p_b\) .
- Pour la stratégie qui consiste à jouer sur la machine \(M_A\) avec probabilité \(\frac{1}{2}\) et sur la machine \(M_B\) avec probabilité \(\frac{1}{2}\): \[E[G_m(T)] = \sum_{i=1}^{T}\frac{1}{2}p_a+\frac{1}{2} p_b = \frac{1}{2}\sum_{i=1}^{T}(p_a+p_b) = \frac{T}{2}*(p_a+p_b)\] .
On étudie alors seulement le cas \((p_a,p_b)=(.65,.55)\) et on s’intéresse au regret de la stratégie m notée \(R_m(t) = p_a - \frac{E[G_m(t)]}{t}\) afin d’évaluer l’efficacité de nos stratégies. On s’interesse au regret afin de comparer la probabilité de gagner (on rappel que on ne connaît pas les probabilités de gain des deux machines en jouant) obtenue en suivant notre stratégie \(m\), ici obtenue grâce à la formule \(\frac{E[G_m(t)]}{t}\), comparé à la probabilité de gagner si on utilise la stratégie la plus optimale qui consiste à ne jouer que sur la machine ayant la plus grande probabilité de gain (ici la machine A). On attendrait ainsi d’une bonne stratégie qu’elle se rapproche le plus possible de 0, c’est à dire que la probabilité de gagner de notre stratégie se rapproche le plus de celle de la probabilité de la meilleure stratégie de gain.
Code :
Voici notre code qui implémente les trois stratégies proposées dans le sujet, séparées à l’aide d’un switch. La fonction simuler prend en paramètre la stratégie demandée (1, 2 ou 3), ainsi que les variables requises pour la simulation. En paramètre, nous avons choisi de monter Tmax à 5000, qui est selon nous un bon juste milieu entre le temps de rendu et la précision obtenue. Le nombre d’essais N à 100 est suffisant pour analyser les différentes stratégies.
library("ggplot2")
library("dplyr")set.seed(123499);
simuler = function(strat, N, Tmax, pA, pB, epsilon) {
dfres = data.frame()
for(i in 1:N) {
switch(strat,
'1'={
# Stratégie 1
Test=Tmax*epsilon
Trestant=Tmax-Test
pAbis=0
pBbis=0
tab = c()
# Calcul des epsilon*Tmax premières parties
for(j in 1:Test) {
if((j%%2) == 0) {
tab[j] = rbinom(1, 1, pA)
pAbis = pAbis + tab[j]
}else {
tab[j] = rbinom(1, 1, pB)
pBbis = pBbis + tab[j]
}
}
# Calcul des parties restantes avec la machine estimée qui semble la meilleure
if(pAbis > pBbis) {
tab = c(tab, rbinom(Trestant, 1, pA))
}else {
tab = c(tab, rbinom(Trestant, 1, pB))
}
},
'2'={
# Strategie 2
# Nombre de tentative par machine
nbtryA = 0
nbtryB = 0
# Nombre de succès par machine
nbwinA = 0
nbwinB = 0
tab = c()
for(j in 1:Tmax) {
# Calcul des ratios
ratioA = nbwinA/(nbtryA+1)
ratioB = nbwinB/(nbtryB+1)
if(ratioA==ratioB) { # Si les ratios sont égaux, on choisit aléatoirement entre les deux
proba = 0.5
}else if(ratioA > ratioB) { # Si ratioA > ratioB, alors on choisira à 90% de probabilité A
proba = (1-epsilon)
}else { # Si ratioB > ratioA, alors on choisira à seulement 10% de probabilité A
proba = epsilon
}
if((runif(1)) < proba) { # On test si on joue A ou B selon la probababilité calculée auparavant
tab[j] = rbinom(1, 1, pA)
nbtryA = nbtryA + 1
nbwinA = nbwinA + tab[j]
}else {
tab[j] = rbinom(1, 1, pB)
nbtryB = nbtryB + 1
nbwinB = nbwinB + tab[j]
}
}
},
'3'={
# Strategie 3
# Nombre de victoires et d'essais sur la machine A
nbwinA = 0
nbtryA = 0
# Nombre de victoires et d'essais sur la machine B
nbwinB = 0
nbtryB = 0
tab = c()
for(j in 1:Tmax) {
vpA = rbeta(1,nbwinA+1,nbtryA-nbwinA+1)
vpB = rbeta(1,nbwinB+1,nbtryB-nbwinB+1)
if(vpA >= vpB) { # Si la probabilité vraisemblable de A est plus élevée (le égal est négligeable)
tab[j] = rbinom(1, 1, pA)
nbtryA = nbtryA + 1
nbwinA = nbwinA + tab[j]
}else { # Sinon, on joue la machine B
tab[j] = rbinom(1, 1, pB)
nbtryB = nbtryB + 1
nbwinB = nbwinB + tab[j]
}
}
}) # Fin du switch
# Calculer Rm(t) pour les Tmax valeurs et les remettre dans un tableau
rmt = c()
for(j in 1:Tmax) {
rmt[j] = pA - (cumsum(tab)[j] / j)
}
# Je crée une data.frame avec une colonne id, t et rmt
dfrmt = data.frame(id=i,
t=1:Tmax,
rmt)
# Je l'ajoute à la dataframe de resultat de la fonction
dfres = rbind(dfres,dfrmt)
}
# Je renvoie la dataframe resultat
# Calcul de la moyenne des valeur de rmt pour chaque valeur de t
dfsummarised = dfres %>% group_by(t) %>% summarise(mean_rmt = mean(rmt))
print(dfsummarised$mean_rmt[5000])
# Affichage sur un graphique des N tentatives de Tmax parties, avec la moyenne du regret pour chaque valeur de t
ggplot(NULL) + geom_line(data=dfres, aes(x=t, y=rmt, group=id), alpha=0.1) + geom_line(data=dfsummarised, aes(x=t, y=mean_rmt, colour="moyenne des rmt"))
}Question 2 : On apprend (un peu) puis on exploite
La stratégie \(m_L\) consiste à consacrer les \(\epsilon*T\) première parties (avec \(\epsilon = 0.05\) par exemple) à estimer les probabilités de la machine A et de la machine B (chaque machine est essayée alternativement), puis à ne jouer ensuite que sur la machine qui semble avoir la probabilité de gain la plus élevée.
Nous avons choisi de garder \(\epsilon\) à 0.05 car s’il est trop élevé, nous allons “gaspiller” trop de tirages sur l’estimation.
# Appel de la fonction de simulation : simuler(strat,N,Tmax,pA,pB,epsilon)
simuler('1', 100, 5000, 0.65, 0.55, 0.05)## [1] 0.006754
Justification :
La stratégie \(m_L\) semble être une stratégie comportant certains risques, même si la courbe de la moyenne des différentes trajectoires est proche de zéro. En effet deux cas de figure peuvent se produire:
- au bout de la phase d’observation on choisit de ne jouer que sur la machine ayant la probabilité de gain réelle la plus élevé et on arrive ainsi à un regret proche de zéro (la stratégie a donc marché);
- au bout de la phase d’observation on choisit de ne jouer que sur la machine ayant la probabilité de gain réelle la plus basse (cela peut arriver si elle gagne beaucoup durant cette période) et on arrive à un regret proche de 0.1 (la stratégie n’est donc pas bonne). De plus on ‘’sacrifie’’ une partie des tirages lors de la phase d’observation, c’est à dire que l’on va jouer une fois sur deux sur la mauvaise machine.
Ces risques dépendent de la valeur de \(\epsilon\) choisie. Si on choisit un \(\epsilon\) trop faible (disons de 0.01 par exemple), la phase d’observation ne dure pas assez longtemps et on a donc une plus grande chance de ne jouer que sur la pire des 2 machines, ce qui n’est pas une bonne stratégie. Au contraire si on choisit un \(\epsilon\) trop élevé (disons de 0.3) on va sacrifier un trop grand nombre de tirage lors de la phase de test ce qui va augmenter notre regret et donc diminuer nos gains moyens La difficulté de cette stratégie est donc de choisir un bon \(\epsilon\). Si l’on se trompe de machine une fois la phase d’observation terminée, il sera impossible de changer ce choix par la suite car la stratégie n’est pas évolutive. Toutefois, la moyenne du regret reste très bonne avec 0.006754 dans notre cas (pour Tmax=5000 et N=100), soit une moyenne de victoire de l’ordre de 0.65-0.006754 = 0.643 environ. On peut en déduire que sur plusieurs essais, la stratégie est bonne car la moyenne des essais est très basse. Cependant, sur un nombre d’essais très faible, la probabilité de mal estimer la meilleur machine et de se tromper augmente.
Question 3 : On exploite mais on se force à toujours apprendre (un peu)
La stratégie \(m_G\) consiste à sélectionner avec une probabilité \(1 - \epsilon\) (avec \(\epsilon = 0.1\) par exemple) la machine dont le ratio du ‘nombre de succès’ par le nombre ‘nombre de tentatives plus un’ est le plus élevé, et avec une probabilité \(\epsilon\) de choisir l’autre machine. en cas d’égalité, on choisit au hasard entre ces deux machines de façon à ne pas favoriser l’une plus que l’autre.
Nous avons choisi de garder \(\epsilon\) à 0.1 car si nous le diminuons, certe on améliore légèrement le regret moyen sur les derniers tirages, mais si estime mal la machine gagnante au début, il faut beaucoup de temps pour corriger cette erreur. La valeur 0.1 nous a donc semblé optimale.
# Appel de la fonction de simulation : simuler(strat,N,Tmax,pA,pB,epsilon)
simuler('2', 100, 5000, 0.65, 0.55, 0.1)## [1] 0.010526
Justification :
La stratégie \(m_G\) semble être une stratégie viable avec avec un \(\epsilon\) bien choisi. En effet avec un \(\epsilon = 0.1\) on observe que le regret moyen est proche de zéro et les trajectoires sont toutes proches elles aussi de zéro (la stratégie est donc bonne).
Cependant il faut toujours faire attention à la valeur d’\(\epsilon\) choisie. Si celle-ci est trop faible (disons 0.01), on ne va parfois pas pouvoir corriger nos trajectoires efficacement, ce qui fait qu’on peut continuer de jouer principalement avec la machine ayant la plus faible probabilité de gain (et ainsi obtenir des regrets égale à 0.1 de temps en temps, un peu comme avec la stratégie précédente). Si la valeur \(\epsilon\) est trop grande (disons 0.3), on va encore une fois sacrifier un trop grand nombre de tirage ce qui va augmenter notre regret et diminuer ainsi notre gain moyen.
Comme l’observation se déroule en permanence, il est difficile avec cette stratégie de se tromper trop longtemps, donc tous les essais sont environ autour de la moyenne comparé à la première stratégie (\(m_L\)), où il était possible de se tromper complètement de machine et de finir avec un regret mauvais. Reste que la moyenne des regrets était meilleur pour la stratégie 1 en moyenne avec 0.0067, tandis qu’il est de 0.0105 avec la stratégie \(m_G\). On peut aussi observer que cette stratégie se rapproche plus rapidement vers zero que la première stratégie, etant donc a priori optimale plus rapidement. On peut en déduire que si le nombre d’essais est très faible, il vaut mieux se diriger sur la stratégie \(m_G\) qui va garantir un regret correct, mais si le nombre d’essais est élevé, l’utilisation de la stratégie \(m_L\) devient discutable car elle permet en théorie d’obtenir un regret en moyenne très légèrement meilleur.
Question 4 : On tire au hasard en biaisant selon nos observations
La stratégie \(m_T\) consiste à tirer un nombre aléatoire suivant la densité beta correspondant à chacune des machines A et B afin d’obtenir une valeur vraisemblable de vA et de vB et on choisit la machine ayant obtenu la plus grande valeur.
# Appel de la fonction de simulation : simuler(strat,N,Tmax,pA,pB,epsilon)
simuler('3', 100, 5000, 0.65, 0.55, NULL)## [1] 0.003446
Justification :
La stratégie \(m_T\) est la meilleure stratégie car le regret moyen et les trajectoires sont toutes très proche de zéro. Comparé aux autres stratégies, elle est aussi meilleur car elle ne dépend d’aucune variable (epsilon) qui pourrait influencer le résultat si celle-ci serait mal choisie et de toutes les stratégies, c’est celle-ci dont les trajectoires se rapprochent le plus rapidement de zéro. On peut donc en déduire que cette stratégie est bien meilleure que les deux autres dans tous les cas de figures cités précédemment, avec seulement 0.00344 de regret moyen.
Conclusion intuitions :
On peut constater que nos intuitions n’étaient pas si loin des résultats finaux. En effet, la première et la seconde stratégie ont un regret moyen étonnamment proche, même si nous avions prédit la possibilité que la première stratégie se trompe gravement de temps en temps. La dernière stratégie, malgré l’ajout de la loi Beta pour estimer quelle variable utiliser, semble être la meilleure dans tous les cas de figure.