Probabilités et Simulation - DM1
Leya BADAT & Victor CUAU
4 novembre 2018
Sujet 1 : Au casino
Nous présentons d’abord notre code, qui implémente les 3 statégies étudiées dans ce sujet à l’aide d’un switch. Nous détaillerons plus bas notre compréhension des stratégies, nos intuitions, et nos analyses des résultats obtenus.
library(ggplot2)
set.seed(2018)
# Valeurs réelles des probabilités de gagner sur les machines A et B
pA = .65
pB = .55
# Fonction qui exécute N trajectoires de Tmax tirages chacunes, suivant la stratégie strat
# (strat = '1', '2' ou '3')
simuler = function(strat) {
df = data.frame() # Data Frame contenant l'intégralité des trajectoires
N = 100 # Nombre de trajectoires de la simulation
Tmax = 2500 # Nombre de tirages par trajectoire
for(j in 1:N) {
# Initialisation des structures de données pour la trajectoire j
id = c() # Numéro de la trajectoire (j)
machine = c() # Machine sur laquelle est effectué le tirage ("A" ou "B")
tirage = c() # Résultat au tirage (0 ou 1)
esperance = c() # Espérance du gain
regret = c() # Regret
switch(strat,
'1'={ methode = "mL"
epsilon = 0.05 # 5% d'apprentissage
t = 0
succesA = 0.
succesB = 0.
test = Tmax*epsilon # Nombre de tirages "d'apprentissage"
# Tirages "d'apprentissage"
for (i in 1:test){
if (i%%2 == 0){ # On tire alternativement sur A et sur B
t = t + 1
tirageA = rbinom(1,1,pA)
id[t] = j
machine[t] = "A"
tirage[t] = tirageA
esperance[t] = succesA + succesB
regret[t] = pA - esperance[t]/t
succesA = succesA + tirageA
}
else{
t = t + 1
tirageB = rbinom(1,1,pB)
id[t] = j
machine[t] = "B"
tirage[t] = tirageB
esperance[t] = succesA + succesB
regret[t] = pA - esperance[t]/t
succesB = succesB + tirageB
}
}
pA_eval = succesA / (test/2) # Probabilité estimée de succès sur machine A
pB_eval = succesB / (test/2) # Probabilité estimée de succès sur machine B
succes = 0.
# On choisit la machine avec la probabilité estimée de succès la plus grande
if (pA_eval >= pB_eval) {
p_jeu = pA
machine_eval = "A"
} else {
p_jeu = pB
machine_eval = "B"
}
# Exécution des 95% de tirages restants sur la machine choisie
while (t<Tmax){
t = t + 1
tirage_temp = rbinom(1,1,p_jeu)
succes = succes + tirage_temp
id[t] = j
machine[t] = machine_eval
tirage[t] = tirage_temp
esperance[t] = succesA + succesB + succes
regret[t] = pA - esperance[t]/t
}
# Data Frame récupérant les structures de données pour la trajectoire j
resultats = data.frame(
id,
t=1:Tmax,
machine,
tirage,
esperance,
regret
)
},
'2'={ methode = "mG"
epsilon = 0.1
tentativeA = 0.
tentativeB = 0.
succesA = 0.
succesB = 0.
ratioA = 0.
ratioB = 0.
for (t in 1:Tmax){
# Choix de la machine utilisée pour le prochain tirage, en fonction des ratios
if (ratioA == ratioB){
selection = runif(1)
if (selection<0.5) { p_current = pA } else { p_current = pB }
}
else{
selection = rbinom(1,1,1-epsilon)
if (ratioA > ratioB) {
if (selection == 1) { p_current = pA } else { p_current = pB }
}
else{
if (selection == 1) { p_current = pB } else { p_current = pA }
}
}
# Exécution du tirage
tirage = rbinom(1,1,p_current)
if (p_current == pA) {
succesA = succesA + tirage
tentativeA = tentativeA + 1
machine_current = "A"
if (tentativeA == 0) ratioA = 0 else ratioA = succesA/tentativeA
}
else {
succesB = succesB + tirage
tentativeB = tentativeB + 1
machine_current = "B"
if (tentativeB == 0) ratioB = 0 else ratioB = succesB/tentativeB
}
# Remplissage des structures de données pour la trajectoire j, au tirage t
id[t] = j
machine[t] = machine_current
tirage[t] = tirage
esperance[t] = (succesA + succesB )
regret[t] = pA - esperance[t]/t
}
# Data Frame récupérant les structures de données pour la trajectoire j
resultats = data.frame(
id,
t=1:Tmax,
machine,
tirage,
esperance,
regret
)
},
'3'={ methode = "mT"
succesA = 0
echecA = 0
succesB = 0
echecB = 0
for (t in 1:Tmax){
tirageA = rbeta(1,shape1=succesA+1,shape2=echecA+1)
tirageB = rbeta(1,shape1=succesB+1,shape2=echecB+1)
# On choisit pour le tirage suivant la machine ayant la probabilité
# estimée la plus vraisemblable
if (tirageA > tirageB){
tirage = rbinom(1,1,pA)
machine_current = "A"
if (tirage == 1) succesA = succesA + tirage else echecA = echecA + 1
} else {
tirage = rbinom(1,1,pB)
machine_current = "B"
if (tirage == 1) succesB = succesB + tirage else echecB = echecB + 1
}
# Remplissage des structures de données pour la trajectoire j, au tirage t
id[t] = j
machine[t] = machine_current
tirage[t] = tirage
esperance[t] = (succesA + succesB)
regret[t] = pA - esperance[t]/t
}
# Data Frame récupérant les structures de données pour la trajectoire j
resultats = data.frame(
id,
t=1:Tmax,
machine,
tirage,
esperance,
regret
)
}
)
#print(resultats)
df = rbind(df, resultats) # Ajout des données de la trajectoire j dans le Data Frame
}
#print(df)
#ggplot(df, aes(x = t, y = regret, group = id)) + geom_line(alpha=0.1)
# Calcule de la moyenne pour chaque t
moyenne = c()
for (t in 1:Tmax){
moyenne[t] = mean(df[t,"regret"])
}
resultats = data.frame(t=1:Tmax, moyenne) # On met les données de moyenne dans un Data Frame
# On trace les trajectoires et la moyenne
ggplot(df, aes(x = t, y = regret, group = id)) + geom_line(alpha=0.1) + geom_line(data = resultats, aes(x = t, y = moyenne, color = "red")) + ggtitle(paste("Evolution du regret au fil des tirages successifs, avec la stratégie", methode)) + theme(legend.position = 'none')
}Question 1 : Questions préliminaires
On sait que \(∀m, ∀t, X _{m,t} ∼ B(1, p_m)\).
m est la stratégie qui consiste à jouer systématiquement la machine \(M_A\). Alors \(E[G_m(T)] = T \times p_A\) (espérance de la loi binomiale).
m est la stratégie qui consiste à jouer systématiquement la machine \(M_B\). Alors \(E[G_m(T)] = T \times p_B\) (espérance de la loi binomiale).
m est la stratégie qui consiste à jouer la machine \(M_A\) avec probabilité \(\frac{1}{2}\) et la machine \(M_B\) avec probabilité \(\frac{1}{2}\).
On pose \(Y_i\) la variable aléatoire représentant le gain à la \(i^{ème}\) partie.
On a donc \(\mathbb{P}(Y_i = 1) = \frac{1}{2}\times p_A + \frac{1}{2}\times p_B = \frac{1}{2}(p_A+p_B)\).
De même, \(\mathbb{P}(Y_i = 0) = 1 - \frac{1}{2}(p_A+p_B)\).
On introduit ensuite la variable aléatoire \(Y\) correspondant à \(\sum_{i=1}^{T} Y_i\). Cette variable suit ainsi une loi binomiale de paramètres \((T,\frac{1}{2}(p_A+p_B))\). On en déduit ainsi son espérance, qui correspond à l’espérance de gain \(E[G_m(T)]\). Alors \(E[G_m(T)] = T \times\frac{1}{2} (p_A+p_B)\)
On pourrait penser au regret comme étant la différence entre l’espérance de gain sur la machine A, qui semble être la meilleure machine, et l’espérance de gain suivant la stratégie m. On aurait ainsi \(R_{m_{intuitif}}(t) = E[G_m(t)]_A - E[G_m(t)] = t\times p_A - E[G_m(t)]\) d’après les questions précédente. On sait que \(t>0\), car on doit effectuer au minimum une partie. Ainsi, on peut diviser l’ensemble de notre égalité par \(t\) et on obtient alors le regret \(R_m(t) = p_A - \frac{E[G_m(t)]}{t}\).
On a \(E[G_m(t)]\) qui correspond à l’espérance de gain cumulé pour \(t\) parties, selon la stratégie \(m\). On en déduit que \(\frac{E[G_m(t)]}{t}\) correspond à la probabilité de la stratégie \(m\) : c’est comme si on modélisait une machine “virtuelle” qui aurait une probabilité de gain égale à \(\frac{E[G_m(t)]}{t}\).
On attendrait d’une bonne stratégie qu’elle fournisse un regret minimum, c’est-à-dire que l’on attend que le machine modélisée par la méthode réalisée soit le plus proche possible de la meilleure machine, soit la machine A ici.
Question 2 : On apprend (un peu) puis on exploite
On étudie la stratégie \(m_L\) qui consiste à consacrer les \(\epsilon \times T_{max}\) premières parties à estimer les probabilités \(p_A\) et \(p_B\), en essayant alternativement chaque machine. Ensuite, on jouera systématiquement la machine la plus prometeuse d’après les premiers tirages.
Intuition : Nous pensons qu’apprendre les probabilités des 2 machines uniquement sur 5% des tirages ne peut être efficace que sur un grand nombre total de tirages, afin que les 5% soient significatifs. Dans ce cas, les 5% du début peuvent suffir pour avoir une bonne idée des probabilités des machines !
On s’attend donc à ce que, pour une grand nombre de tirages, le regret tende vers 0. Cependant, on s’attend également, pour un petit nombre de tirages, à ce que le regret ne converge pas.
Modélisons cette expérience pour vérifier notre intuition :
simuler('1')
On observe que nos expériences tendent vers 2 types de résultats différents : soit l’expérience nous laisse penser que la machine A est la meilleure, soit elle nous laisse penser que c’est la machine B.
Comme la réelle probabilité de A est meilleure que la réelle probabilité de B, on constate que l’expérience s’oriente plus fréquemment vers le choix de la machine A.
Cependant, un nombre non négligeable d’expériences se terminent en considérant que la machine B est la meilleure, ce qui est faux ! En effet, on observe que le regret lors du choix de B tend vers une valeur positive, donc ce choix n’est pas optimal ! En revanche, lorsque le choix se porte finalement sur la machine A, le regret semble tendre vers 0, donc il s’agit de la meilleure méthode.
On peut donc conclure que cette stratégie est favorable au joueur dans la majorité des cas, mais qu’elle peut largement être améliorée.
Question 3 : On exploite mais on se force à toujours apprendre (un peu)
On étudie la stratégie \(m_G\). D’abord, on choisit de manière aléatoire la machine A ou la machine B, avec une probabilité \(\frac{1}{2}\). On calcule pour les deux machines leur ratio \(\frac{nombre\ de\ succès}{nombre\ de\ tentative\ +\ 1}\). Puis, au lancer suivant, on utilise avec une probabilité \(1-\widehat{\epsilon}\) la machine la plus prometteuse, c’est-à-dire celle avec le ratio le plus grand ; et donc avec une probabilité \(\epsilon\) l’autre machine.
Intuition : Selon nous, cette stratégie devrait être plus efficace que la précédente. En effet, à chaque tirage, notre choix est orienté par les résultats précédents. Ainsi, on a de bonnes chances de se diriger petit à petit vers la bonne machine. Cependant, la machine avec le meilleur ratio n’est pas toujours celle que l’on pense : on peut ne pas avoir de chance ! Par exemple, un tirage gagnant au début de l’expérience sur la machine ayant la probabilité réelle la plus faible peut fausser dès le début nos ratios, et nous empêcher de faire les bons choix par la suite.
Modélisons cette expérience pour vérifier notre intuition :
simuler('2')
Cette fois, les expériences avec cette stratégie tendent toujours vers un même résultat, très semblable à celui obtenu lors de la précédente stratégie lorsque la machine A était désignée comme plus favorable. On en déduit que cette méthode est donc plus optimale que la précédente. En effet, le regret tend vers 0.
Cela peut s’exliquer par le fait que la machine A ayant une plus grande probabilité de gain, elle a plus de chance d’avoir un ratio de réussite supérieur à celui de la machine B, ce qui augmente ses chances d’être sélectionnée à chaque tirage.
Nous ne sommes évidemment pas à l’abri de coups de “malchance” pour la machine A ou d’un succès exceptionnel de la machine B (cela se voit sur les tous premiers tirages, où le regret est ainsi très élevé), mais avec un grand nombre de tirages, cela se corrige et on tend vers la sélection de la machine A.
Question 4 : On tire au hasard en biaisant selon nos observations
Comme lors de la question 3, on comptabilise le nombre de tentative et le nombre de succès lors des tirages sur chaque machine. Mais cette fois, on utilise ces valeurs pour calculer la vraisemblance des probabilités estimées. On tire alors sur la machine dont la probabilité estimée est la plus vraisemblable.
Intuition : Cette méthode est une “correction” de la méthode précédente. En effet, dans cette stratégie, une machine avec une bonne probabilité estimée ne sera sélectionnée que si sa vraisemblance est correcte. Cela limite l’impact de la “malchance” sur la suite de l’expérience. On s’attend donc à voir notre regret converger vers 0 plus rapidement.
simuler('3')
Avec cette dernière stratégie, on observe que le regret tend à nouveau vers 0. Donc c’est une bonne stratégie.
De plus, on remarque que les valeurs du regrets tendent plus rapidement vers 0 qu’avec la stratégie précédente.
On peut donc conclure que cette stratégie est la meilleure des trois, puisque l’on arrive plus rapidement à une solution rentable en terme de gain. Notre intuition était bonne !