DM Probabilités & Simulation
Julien Cordat-Auclair (travail réalisé avec Adrian Houbron)
6 décembre 2018
Au casino
Question 0 : intuition
méthode 1 : on joue uniquement sur la machine ayant la meilleure probabilité de gagner. Ainsi, il serait légitime de penser que cette stratégie soit efficace. Par contre, elle n’est pas applicable dans une situation concrète car elle nécessite de connaître à l’avance cette machine.
méthode 2 : on joue uniquement sur la machine ayant la moins bonne probabilité de gagner. Logiquement, cette méthode devrait être la moins rentable.
méthode 3 : on joue alternativement sur chacune des deux machines. Cette stratégie, applicable en réalité, devrait se situer entre les deux précédentes.
méthode L : on réserve les premiers tirages pour tester les machines et en déduire laquelle jouer pour le reste du temps. Cette méthode serait celle à laquelle on penserait en premier car elle permet de résoudre le problème présenté précédemment, à savoir que l’on ne connaît pas la meilleure machine. Si on arrive à effectuer suffisamment de tests pour la connaître, alors on peut optimiser le reste des tirages on jouant uniquement sur cette machine.
méthode G : on teste au fur et à mesure que l’on joue et on adapte le choix de la machine en fonction de nos calculs. Je pense que cette méthode est une version améliorée (et donc meilleure) de la précédente car elle permettra d’éviter une phase de test relativement longue tout en obtenant un résultat similaire.
méthode T : on se base sur la densité bêta pour choisir sur quelle machine tirer. Difficile d’estimer le résultat obtenu mais je pense qu’il ne devrait pas varier grandement de la méthode précédente puisque cette nouvelle stratégie l’imite tout en évitant les problèmes de sur-estimation ou sous-estimation des probabilités de gain. Cela peut laisser penser qu’elle sera légèrement meilleure que la précédente, donc la meilleure de toutes.
set.seed(54321)Question 1 : questions préliminaires
méthode 1 : on joue systématiquement sur la machine A. Comme \(X(a,t)\) suit une loi binomiale de paramètres \((1, pA)\) et que les gains obtenus à chaque tirage sont indépendants et identiquement distribués, alors \(G_1(T)\) suit une loi binomiale de paramètres \((T, pA)\). Ainsi, \(E[G_1(T)] = T * pA\).
méthode 2 : on joue systématiquement sur la machine B. Comme \(X(b,t)\) suit une loi binomiale de paramètres \((1, pB)\) et que les gains obtenus à chaque tirage sont indépendants et identiquement distribués, alors \(G_2(T)\) suit une loi binomiale de paramètres \((T, pB)\). Ainsi, \(E[G_2(T)] = T * pB\).
méthode 3 : on joue sur la machine A avec une probabilité \(1/2\) et sur la machine B avec une probabilité \(1/2\). On utilise les deux formules calculées précédemment ; comme les variables aléatoires sont indépendantes, on peut séparer le calcul de \(G_3(T)\) en deux sommes afin de simuler le choix de telle ou telle machine avec une probabilité \(1/2\). En effet, alterner entre la machine A et la machine B au cours de T tirages revient à ne choisir que la machine A au cours des \(T/2\) premiers tirages puis de se concentrer uniquement sur la machine B lors des \(T/2\) tirages restants. Ainsi, on obtient \(G_3(T) = (T/2) * pA + (T/2) * pB = (T/2) * (pA + pB)\).
La quantité \(Rm(t)\) permet d’évaluer l’efficacité de la stratégie \(m\) puisqu’elle permet de se rendre compte de la quantité d’argent “non-empochée” au cours des tirages que l’on a effectués jusqu’à un instant \(t\) donné vis-à-vis de la machine ayant la plus forte probabilité de gagner (ici, c’est la machine A). Le but d’une bonne stratégie est donc de minimiser cette valeur.
Voici l’implémentation de ces trois méthodes :
# PACKAGES
library('dplyr')
library('ggplot2')
# Faire varier ces paramètres
pA = 0.65
pB = 0.55
Tmax = 1000
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour une des trois méthodes données
Rm = function(Tmax, m) {
for (i in 1:5) {
R = c()
t = 1
gTotalA = 0 # gain total suite aux parties jouées sur la machine A
gTotalB = 0 # gain total suite aux parties jouées sur la machine B
while(t <= Tmax) {
gA = rbinom(1, 1, pA) # gain obtenu suite à une partie sur la machine A
gB = rbinom(1, 1, pB) # gain obtenu suite à une partie sur la machine B
gTotalA = gTotalA + gA
gTotalB = gTotalB + gB
R[t] = switch(m,
pA - gTotalA/t, # m1 = on ne joue que sur la machine A
pA - gTotalB/t, # m2 = on ne joue que sur la machine B
pA - (1/2)*(gTotalA + gTotalB)/t) # m3 = on joue sur les machines A et B alternativement
t = t + 1
}
}
return(R)
}Voici à quoi ressemblent les résultats :
mdf = list(m1 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 1)),
m2 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 2)),
m3 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 3)))
ggplot(bind_rows(mdf, .id = "methodes"), aes(t, r, colour = methodes)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
La première observation que l’on puisse faire est que les trois trajectoires oscillent grandement au cours des 250 premiers tirages. On peut par ailleurs voir que la courbe rouge qui représente la moyenne de ces trois trajectoires à chaque instant semble se stabiliser autour d’une valeur légèrement supérieure à 0. La méthode 1 semble être la plus efficace parmi les trois présentées puisque c’est celle avec laquelle on obtient un regret minimal sur toute la durée du test. C’était prévisible puisque c’est la méthode qui consiste à jouer uniquement sur la machine qui a la plus grande chance de gagner (à l’inverse de la méthode 2 qui obtient logiquement le résultat le moins bon), bien qu’il soit possible de réaliser des simulations “malchanceuses” où la machine avec la probabilité de gagner la plus faible est finalement celle ayant généré un regret minimal. La trajectoire de la méthode 3 se situe logiquement entre les deux autres étant donnée la manière dont elle est définie.
On notera par également que plus \(pA\) et \(pB\) sont différents et plus les trajectoires s’écartent, et qu’à l’inverse les trajectoires se rapprochent si \(pA\) et \(pB\) sont proches :
pA = 0.75
pB = 0.25
mdf = list(m1 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 1)),
m2 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 2)),
m3 = data.frame(t = c(1:Tmax), r = Rm(Tmax, 3)))
ggplot(bind_rows(mdf, .id = "methodes"), aes(t, r, colour = methodes)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Les méthodes 2 et 3 ne sont pas bonnes car le regret calculé à chaque instant n’est pas assez petit pour être intéressant. Cependant, la méthode 1 qui consiste à jouer uniquement sur la machine avec la plus forte probabilité de gagner peut être considérée comme étant une bonne stratégie étant donnée la valeur de \(r\) à chaque tirage. Mais dans une situation concrète, le joueur ne connaît pas la machine la plus rentable (sauf s’il effectue une série de tests auparavant comme on l’étudiera après) : cette méthode n’est donc pas applicable.
Question 2 : on apprend (un peu) puis on exploite
Voici l’implémentation de la méthode L. L’idée de cette dernière consiste à effectuer une phase de test de manière à identifier quelle machine est la plus performante pour ensuite jouer uniquement sur celle-ci :
# Faire varier ces paramètres
pA = 0.65
pB = 0.55
Tmax = 1000
epsilon = 0.2
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour la méthode L
RmL = function(Tmax, epsilon) {
R = c()
t = 1
gTotalA = 0
gTotalB = 0
gEpsA = 0 # gain obtenu suite aux (epsilon*Tmax) premières parties jouées sur la machine A
gEpsB = 0 # gain obtenu suite aux (epsilon*Tmax) premières parties jouées sur la machine B
while(t <= Tmax*epsilon) {
if (t%%2 == 0) {
gA = rbinom(1, 1, pA)
gEpsA = gEpsA + gA
R[t] = pA - gEpsA/t # on joue uniquement sur A
} else {
gB = rbinom(1, 1, pB)
gEpsB = gEpsB + gB
R[t] = pA - gEpsB/t # on joue uniquement sur B
}
t = t + 1
}
gEps = gEpsA + gEpsB # gain obtenu suite aux (epsilon*Tmax) premières parties jouées
gTotal = gEps # gain obtenu suit aux Tmax parties jouées
if ((gEpsA > gEpsB) || ((gEpsA == gEpsB) && (rbinom(1, 1, 0.5) == 1))) {
print('on joue seulement sur la machine A')
while(t <= Tmax) {
gA = rbinom(1, 1, pA)
gTotal = gTotal + gA
R[t] = pA - gTotal/t
t = t + 1
}
} else {
print('on joue seulement sur la machine B')
while(t <= Tmax) {
gB = rbinom(1, 1, pB)
gTotal = gTotal + gB
R[t] = pA - gTotal/t
t = t + 1
}
}
return(R)
}On génère une trajectoire selon cette méthode :
df = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon))## [1] "on joue seulement sur la machine A"ggplot(df, aes(t, r)) + geom_line() + geom_vline(xintercept = epsilon*Tmax, linetype="dotted", color = "red") + theme_bw()
On remarque bien les fortes oscillations au cours de la phase de test qui sont dues au changement de machine lors de chaque tirage. Une fois que cette phase se termine, la trajectoire est bien plus stable puisqu’on utilise la même machine pour tous les tirages restants.
Simulons maintenant 5 trajectoires selon cette même méthode :
mdf = list(sim1 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim2 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim3 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim4 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim5 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)))## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"ggplot(bind_rows(mdf, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Grâce à cette méthode, on observe donc qu’il est possible d’obtenir de bons résultats. Ce sont les cas où la machine ayant obtenu le meilleur ratio de succès lors de la phase de test est celle qui a la plus forte probabilité de gagner sur le papier. Mais il est aussi possible que la machine ayant obtenu le meilleur ratio de succès lors de la phase de test soit celle ayant en réalité la plus faible probabilité de gagner et on se retrouve alors avec un résultat final peu convaincant.
Faire varier \(epsilon\) peut être dangereux : si on le prend trop petit, la phase de test est très courte ce qui permet d’éviter beaucoup de tirages durant lesquels le regret est important mais on risque alors de choisir la mauvaise machine pour la suite des tirages puisqu’il devient alors difficile de trouver la machine ayant la plus forte probabilité de gagner. Le choix d’un \(epsilon\) grand présente les mêmes avantages et inconvénients mais inversés. Ainsi, \(epsilon = 0.2\) semble ici être un choix pertinent (mais il ne faut pas oublier qu’il pourrait être bien plus petit si \(Tmax\) était choisit plus grand ou inversement !).
Prenons par exemple \(epsilon = 0.5\) ; on va se rendre compte que la phase de test est longue mais qu’elle permet (en général) toujours de choisir la bonne machine pour la suite des tirages :
epsilon = 0.5
mdf = list(sim1 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim2 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim3 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim4 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim5 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)))## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"ggplot(bind_rows(mdf, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Cependant, si \(epsilon = 0.01\), alors on peut voir que la machine la moins performante a un risque important d’être choisie après la phase de test :
epsilon = 0.01
mdf = list(sim1 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim2 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim3 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim4 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)),
sim5 = data.frame(t = c(1:Tmax), r = RmL(Tmax, epsilon)))## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine A"
## [1] "on joue seulement sur la machine B"
## [1] "on joue seulement sur la machine B"
## [1] "on joue seulement sur la machine A"ggplot(bind_rows(mdf, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Ces observations me permettent de déduire que cette méthode peut se révéler efficace si jamais la phase de test se déroule “correctement” (dans le sens où la meilleure machine sortante est bien celle ayant la plus forte probabilité de gagner) ou si \(pA\) et \(pB\) sont assez différents (donc facilement identifiables) mais qu’elle peut être facilement trompée par des observations malchanceuses lors des premiers essais, ce phénomène étant accentué lorsque les probabilités de gagner de chacune des deux machines sont très proches. De plus, il faut prendre en compte le fait que cette méthode nécessite une phase de test relativement longue durant laquelle le regret est élevé.
Cette méthode n’est donc pas assez fiable pour pouvoir être utilisée : elle peut être performante dans certains cas mais elle semble l’être beaucoup moins dans une situation concrète où les probabilités de gagner des deux machines ne diffèrent que de très peu (ce n’est qu’une hypothèse de ma part car si ce n’était pas le cas, alors l’utilisateur pourrait deviner rapidement sur laquelle jouer pour s’enrichir).
Question 3 : on exploite mais on se force à toujours apprendre (un peu)
Voici l’implémentation de la méthode G. Au lieu de réserver une phase de tirages spécifiques au test, on identifie à chaque tirage quelle machine est la plus performante pour ensuite jouer sur celle-ci au tirage suivant (une sorte de méthode L améliorée) :
# Faire varier ces paramètres
pA = 0.65
pB = 0.55
Tmax = 1000
epsilonbis = 0.1
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour la méthode G
RmG = function(Tmax, epsilonbis) {
R = c()
t = 1
gTotalA = 0
gTotalB = 0
gTotal = 0
nA = 0 # nombre de coups joués sur la machine A
nB = 0 # nombre de coups joués sur la machine B
while(t <= Tmax) {
ratioA = gTotalA/(nA + 1) # ratio du nombre de succès sur la machine A
ratioB = gTotalB/(nB + 1) # ratio du nombre de succès sur la machine B
choixMachine = rbinom(1, 1, 1 - epsilonbis) # renvoie 0 avec une probabilité epsilonbis, 1 avec une probabilité 1 - epsilonbis
if (((ratioA > ratioB) && (choixMachine == 1)) || ((ratioA < ratioB) && (choixMachine == 0)) || ((ratioA == ratioB) && (rbinom(1, 1, 0.5) == 1))) {
gA = rbinom(1, 1, pA)
gTotalA = gTotalA + gA
gTotal = gTotal + gA
R[t] = pA - gTotal/t
nA = nA + 1
} else {
gB = rbinom(1, 1, pB)
gTotalB = gTotalB + gB
gTotal = gTotal + gB
R[t] = pA - gTotal/t
nB = nB + 1
}
t = t + 1
}
print(paste0('ratioA : ', ratioA, ' | ratioB : ', ratioB))
return(R)
}Simulons une trajectoire selon cette nouvelle méthode :
df = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis))## [1] "ratioA : 0.652125279642058 | ratioB : 0.485981308411215"ggplot(df, aes(t, r)) + geom_line() + theme_bw()
On peut déjà observer que les oscillations sont beaucoup plus faibles que précédemment.
Simulons maintenant 5 trajectoires :
epsilonbis = 0.1
mdf = list(sim1 = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis)),
sim2 = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis)),
sim3 = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis)),
sim4 = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis)),
sim5 = data.frame(t = c(1:Tmax), r = RmG(Tmax, epsilonbis)))## [1] "ratioA : 0.641868512110727 | ratioB : 0.524822695035461"
## [1] "ratioA : 0.677094972067039 | ratioB : 0.547169811320755"
## [1] "ratioA : 0.660087719298246 | ratioB : 0.50561797752809"
## [1] "ratioA : 0.63481228668942 | ratioB : 0.590163934426229"
## [1] "ratioA : 0.665178571428571 | ratioB : 0.495238095238095"ggplot(bind_rows(mdf, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Ces trajectoires semblent bien plus intéressantes que celles rencontrées jusqu’ici : elles se stabilisent rapidement autour de \(r = 0\), limitant ainsi le problème d’un regret trop élevé durant les premiers tirages. De ce fait, cette méthode semble être la plus performante jusqu’ici puisqu’elle permet d’obtenir une valeur de regret très faible seulement au bout d’une dizaine de tirages et avec de faibles variations sur l’ensemble des tirages.
Par ailleurs, la valeur d’\(epsilonbis\) fournie dans l’énoncé semble être un bon choix. Si on l’augmente, alors les trajectoires ont tendance à s’écarter davantage et la moyenne de celles-ci est légèrement plus élevée. Il est difficile de la réduire davantage et la fixer à \(0\) serait incohérent dans le sens où l’intérêt de la méthode qui consiste à garder une part de hasard dans le choix de la machine sur laquelle jouer à l’instant \(t\) ne serait pas conservé.
Question 4 : on tire au hasard en biaisant nos observations
Voici l’implémentation de cette méthode :
# Faire varier ces paramètres
pA = 0.65
pB = 0.55
Tmax = 1000
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour la méthode G
RmT = function(Tmax) {
R = c()
t = 1
gTotal = 0
nSuccA = 0 # Nombre de succès obtenus sur la machine A
nSuccB = 0 # Nombre de succès obtenus sur la machine B
nFailA = 0 # Nombre d'échecs obtenus sur la machine A
nFailB = 0 # Nombre d'échecs obtenus sur la machine B
while(t <= Tmax) {
pAv = rbeta(1, nSuccA + 1, nFailA + 1)
pBv = rbeta(1, nSuccB + 1, nFailB + 1)
if ((pAv > pBv) || ((pAv == pBv) && (rbinom(1, 1, 0.5) == 1))) {
gA = rbinom(1, 1, pA)
gTotal = gTotal + gA
R[t] = pA - gTotal/t
if (gA == 0) {
nFailA = nFailA + 1
} else {
nSuccA = nSuccA + 1
}
} else {
gB = rbinom(1, 1, pB)
gTotal = gTotal + gB
R[t] = pA - gTotal/t
if (gB == 0) {
nFailB = nFailB + 1
} else {
nSuccB = nSuccB + 1
}
}
t = t + 1
}
return(R)
}Voici le résultat alors obtenu lors de la simulation d’une trajectoire :
df = data.frame(t = c(1:Tmax), r = RmT(Tmax))
ggplot(df, aes(t, r)) + geom_line() + theme_bw()
Simulons maintenant 5 trajectoires :
mdf = list(sim1 = data.frame(t = c(1:Tmax), r = RmT(Tmax)),
sim2 = data.frame(t = c(1:Tmax), r = RmT(Tmax)),
sim3 = data.frame(t = c(1:Tmax), r = RmT(Tmax)),
sim4 = data.frame(t = c(1:Tmax), r = RmT(Tmax)),
sim5 = data.frame(t = c(1:Tmax), r = RmT(Tmax)))
ggplot(bind_rows(mdf, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
C’est une bonne méthode car on observe que les trajectoires se stabilisent rapidement, permettant ainsi d’obtenir un regret minimal dès les premiers tirages (comme pour la méthode précédente). La valeur de \(r\) obtenue au terme des \(Tmax\) tirage est très faible.
Même si la moyenne des regrets à chaque instant semble être ici minimale, il est difficile d’affirmer avec certitude quelle méthode est meilleure que l’autre. Mais il est évident que ces deux méthodes peuvent être considérées comme étant les meilleures parmi toutes celles étudiées dans le cadre d’une situation concrète où l’on ne connait pas la machine la plus performante.
Conclusion : retour sur les intuitions énoncées au début du sujet
méthode 1 : comme prévu, c’est une méthode efficace mais pas réalisable en situation concrète.
méthode 2 : c’est la moins bonne des méthodes comme annoncé.
méthode 3 : cette stratégie est bien un mélange des deux précédentes et sa trajectoire de \(r\) en fonction de \(t\) se situe donc entre elles.
méthode L : c’est une méthode facilement applicable qui comme énoncée au début permet d’obtenir de bons résultats si la phase de tests est assez longue. Cependant, je n’avais pas pris en compte le fait que malgré cela, il est quand même possible de se tromper de machine suite à des observations “malchanceuses” (je m’en suis rendu compte en faisant beaucoup de simulations).
méthode G : c’est en effet une amélioration de la méthode précédente et les résultats obtenus grâce à celle-ci sont très bons.
méthode T : difficile de dire si cette méthode est meilleure que la précédente, mais il est certain qu’elle est également très efficace comme je l’avais pensé.