Devoir Maison Probabilités & Simulation
HOUBRON Adrian (avec la coopération de Julien CORDAT-AUCLAIR)
November 9, 2018
Intuition :
Méthode 1 : On ne joue que sur la machine ayant la plus grande probabilité de gagner, de ce fait on peut penser que cette méthode est efficace. Toutefois, pour qu’elle s’avère réellement efficace il est nécessaire de savoir quelle machine à la meilleure probabilité de gagner.
Méthode 2 : On joue systématiquement sur la machine ayant la plus petite probabilité de gagner, de ce fait cette méthode est de base moins efficace.
Méthode 3 : On alterne entre machine A et machine B, de ce fait cette méthode se retrouve à cheval entre les deux méthodes précédentes.
Méthode L : On consacre les T premières parties pour tester les machines et ainsi estimer quelle machine a la plus grande probabilité de gagner et donc jouer sur cette dernière. Cette méthode se rapproche de la méthode 1, il faut juste déterminer sur quelle machine jouer : pour ce faire, il faut effectuer un nombre suffisant de parties afin d’estimer correctement les probabilités de gain de chaque machine.
Méthode G : On estime au fur et à mesure des parties le ratio de victoires de chaque machine et on adapte nos choix en fonction de la machine ayant le meilleur ratio. Cette méthode est similaire à la précédente mais avec une période de test en moins, cette méthode me semble donc plus prometteuse.
Méthode T : On tire aléatoirement un nombre selon la densité béta. On s’attend à avoir un résultat semblable à celui de la méthode précédente, mais en encore plus efficace.
Questions préliminaires :
set.seed(42) # The Ultimate Anwser of Life, the Universe and EverythingMéthode 1 : On joue systématiquement sur la machine A.
Comme \(X(a,t)\) suit une loi de Bernoulli de paramètre \((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.
Même raisonnement que pour la méthode 1 mais avec la machine B.
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 calculs précédents : comme les deux variables sont indépendantes, on peut séparer le calcul en deux sommes (une somme représentant les parties sur la machine A et l’autre représentant les parties sur la machine B).
On obtient donc : \(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\) car elle représente la quantité d’argent “perdue” au cours des tirages jusqu’à un instant \(t\) donné, par rapport à ce que la machine avec la plus grande probabilité de gagner (dans notre cas la machine A) nous aurait fait gagner. On attend donc d’une “bonne stratégie” qu’elle minimise cette valeur.
Simulation des trois méthodes :
library('dplyr')
library('ggplot2')
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 suite à une partie sur la machine A
gB = rbinom(1, 1, pB) # gain 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)
}
res = 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(res, .id = "methodes"), aes(t, r, colour = methodes)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
On remarque que l’allure des courbes varie grandement dans les 2OO premiers tirages, avant de se stabiliser aux alentours de zéro.
La courbe rouge représente la moyenne des trois trajectoires et se stabilise elle aussi vers une valeur proche de zéro.
On peut déduire de ce graphique que la méthode 1 (tracé rouge claire sur le graphique), semble être la méthode la plus efficace, en effet c’est avec cette méthode que le regret est le plus petit pendant toutes les parties.
La courbe verte représente elle la méthode 2, il est donc logique que cette méthode soit moins efficace que la précédente puisque l’on joue uniquement sur la machine ayant la plus petite probabilité de gagner, le regret est donc élevé.
La courbe bleue, représentant la méthode 3, se situe entre les deux courbes précédentes.
De plus, on remarque que plus les valeurs de \(pA\) et \(pB\) sont proches, plus les courbes le sont aussi, et inversément.
Comme nous l’avions prévu, la méthode 1 est donc la méthode la plus efficace, toutefois elle reste difficilement applicable en réalité car elle implique de connaître à l’avance quelle machine a le plus de probabilité de gagner.
On apprend (un peu) puis on exploite :
Implémentation de la Méthode L :
pA = 0.65
pB = 0.55
Tmax = 1000
Eps = 0.2
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour la méthode L
RmL = function(Tmax, Eps) {
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*Eps) {
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 uniquement 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 uniquement 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)
}
res = list(sim1 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim2 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim3 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim4 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim5 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)))## [1] "on joue uniquement sur la machine A"
## [1] "on joue uniquement sur la machine A"
## [1] "on joue uniquement sur la machine A"
## [1] "on joue uniquement sur la machine A"
## [1] "on joue uniquement sur la machine A"ggplot(bind_rows(res, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Quelle que soit la machine choisie au final, on remarque une forte période d’oscillations durant les Epsilon*Tmax premières parties. Cette période d’oscillations correspond au changement de machine pendant les premiers tirages (phase de tests). Une fois cette période terminée, la trajectoire de la courbe se stabilise étant donné qu’il n’y a plus de changement de machine, on ne joue plus que sur une seule d’entre elles.
Cette méthode semble donc efficace, en effet elle nous permet d’obtenir une valeur de regret très proche de zéro en moyenne (courbe rouge sur le graphique). Toutefois, il est possible que cette méthode s’avère moins efficace, notamment lorsque l’on fait varier la valeur de Epsilon : si on prend Epsilon trop petit, on obtiendra une phase de tests trop courte et on aura donc plus de chance de se tromper de machine est de choisir celle n’ayant pas la plus grande probabilité de gagner.
Il faut donc soigneusement choisir cette valeur, ni trop petite ni trop grande.
Cas où Epsilon est petit (\(Epsilon = 0.02\)) :
Eps = 0.02
res = list(sim1 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim2 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim3 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim4 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)),
sim5 = data.frame(t = c(1:Tmax), r = RmL(Tmax, Eps)))## [1] "on joue uniquement sur la machine B"
## [1] "on joue uniquement sur la machine A"
## [1] "on joue uniquement sur la machine B"
## [1] "on joue uniquement sur la machine B"
## [1] "on joue uniquement sur la machine B"ggplot(bind_rows(res, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
On voit donc bien que si la valeur de Epsilon est trop petite, il est possible de se tromper dans nos estimations et donc de choisir la “mauvaise” machine.
Au final, cette méthode peut s’avérer efficace si et seulement si la meilleure machine est choisie à la suite de la phase de tests. Pour celà, il faut choisir une valeur de Epsilon assez élevée, et il ne faut pas que les probabilités \(pA\) et \(pB\) soient trop proches, sinon il est difficile d’estimer quelle machine est la “meilleure”. De plus, un autre inconvénient de cette méthode est qu’elle nécessite une phase de test qui peut s’avérer longue.
On exploite mais on se force à toujours apprendre (un peu) :
Implémentation de la Méthode G :
pA = 0.65
pB = 0.55
Tmax = 1000
Eps = 0.1
# Fonction renvoyant un tableau contenant le regret calculé à chaque instant pour la méthode G
RmG = function(Tmax, Eps) {
R = c()
t = 1
gTotalA = 0
gTotalB = 0
gTotal = 0
nbA = 0 # nombre de coups joués sur la machine A
nbB = 0 # nombre de coups joués sur la machine B
while(t <= Tmax) {
ratioA = gTotalA/(nbA + 1) # ratio du nombre de succès sur la machine A
ratioB = gTotalB/(nbB + 1) # ratio du nombre de succès sur la machine B
choixMachine = rbinom(1, 1, 1 - Eps) # renvoie 0 avec une probabilité Eps, 1 avec une probabilité 1 - Eps
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
nbA = nbA + 1
} else {
gB = rbinom(1, 1, pB)
gTotalB = gTotalB + gB
gTotal = gTotal + gB
R[t] = pA - gTotal/t
nbB = nbB + 1
}
t = t + 1
}
print(paste0('ratioA : ', ratioA))
print(paste0('ratioB : ', ratioB))
return(R)
}
res = list(sim1 = data.frame(t = c(1:Tmax), r = RmG(Tmax, Eps)),
sim2 = data.frame(t = c(1:Tmax), r = RmG(Tmax, Eps)),
sim3 = data.frame(t = c(1:Tmax), r = RmG(Tmax, Eps)),
sim4 = data.frame(t = c(1:Tmax), r = RmG(Tmax, Eps)),
sim5 = data.frame(t = c(1:Tmax), r = RmG(Tmax, Eps)))## [1] "ratioA : 0.670951156812339"
## [1] "ratioB : 0.573991031390135"
## [1] "ratioA : 0.633771929824561"
## [1] "ratioB : 0.50561797752809"
## [1] "ratioA : 0.653587443946188"
## [1] "ratioB : 0.532110091743119"
## [1] "ratioA : 0.639908256880734"
## [1] "ratioB : 0.48062015503876"
## [1] "ratioA : 0.619153674832962"
## [1] "ratioB : 0.524271844660194"ggplot(bind_rows(res, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
On remarque que les trajectoires des courbes obtenues oscillent beaucoup moins, pendant moins longtemps et se stabilisent donc plus rapidement vers une valeur de regret très proche de zéro. Cette méthode semble donc être encore plus efficace que la précédente : en effet elle permet d’obtenir une valeur de regret quasiment nulle et ce au bout de très peu de tirages !
On tire au hasard en biaisant nos observations :
Implémentation de la Méthode T :
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
nbSuccA = 0 # Nombre de succès obtenus sur la machine A
nbSuccB = 0 # Nombre de succès obtenus sur la machine B
nbFailA = 0 # Nombre d'échecs obtenus sur la machine A
nbFailB = 0 # Nombre d'échecs obtenus sur la machine B
while(t <= Tmax) {
pAv = rbeta(1, nbSuccA + 1, nbFailA + 1)
pBv = rbeta(1, nbSuccB + 1, nbFailB + 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) {
nbFailA = nbFailA + 1
} else {
nbSuccA = nbSuccA + 1
}
} else {
gB = rbinom(1, 1, pB)
gTotal = gTotal + gB
R[t] = pA - gTotal/t
if (gB == 0) {
nbFailB = nbFailB + 1
} else {
nbSuccB = nbSuccB + 1
}
}
t = t + 1
}
return(R)
}
res = 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(res, .id = "simulations"), aes(t, r, colour = simulations)) + geom_line() + geom_smooth(method = 'loess', se = FALSE, colour = 'red') + theme_bw()
Il s’agit là d’une bonne stratégie, en effet on remarque que les trajectoires des courbes oscillent très peu et se stabilisent assez rapidement vers un valeur très proche de zéro. Cette méthode semble donc être au moins aussi efficace que la précédente.
Conclusions :
Comme nous l’avions pensé en debut de ce DM, la méthode 1 est une méthode efficace, cependant elle reste difficilement applicable (besoin de connaître la “meilleure” machine). La méthode 2 ainsi que la méthode 3 sont, comme prévu, des stratégies moins efficaces que la première.
La méthode L est une stratégie efficace (comme nous l’avions pensé), qui fonctionne et nous permet d’obtenir des résultats probants, toutefois elle nécessite une phase de tests.
La méthode G est quant à elle encore plus efficace que la méthode L, car elle s’affranchit de la phase de tests et nous délivre donc plus rapidement des résultats probants.
Enfin, la méthode T est elle aussi très efficace, bien que je ne vois pas de grands changements comparé à la précédente méthode.