DM 1
Sujet 1 : Au casino
Q1 : questions préliminaire
Intuition
Ces expériences sont des successions de jeux sur des machines où nous pouvons avoir soit un succès, soit un échec, il s’agit donc à priori d’une loi Binomiale de paramètre n = nombre de parties, et p = probabilité du succès. L’espérance sera donc égale à np.
Réponses aux questions
Dans cette question nous allons chercher à calculer l’espérance du gain en fonction des machines sur lesquelles nous jouons. Sachant que les machines rapportent 1 (probabilité p) ou 0 (probabilité q = 1-p) euros chaque fois qu’elles sont utilisées, il est possible de représenter chaque partie par une loi de Bernoulli de paramètre p. Sachant que nous répétons cette expérience \(T_{max}\) fois de manière identique et indépendante, nous utilisons alors une loi Binomiale de paramètre (\(T_{max}\),p).
- Ici la stratégie m sera de jouer seulement sur la machine \(M_{A}\). On a donc \(Y_{1}\) une variable aléatoire représentant notre problème. Comme expliqué précédemment \(Y_{1}\) suit une loi Binomiale de paramètre (\(T_{max}\),\(p_{A}\)).
D’où le calcul de l’éspérance : E[\(Y_{1}\)] = \(T_{max}\)*\(p_{A}\) car \(Y_{1}\) suit une loi binomiale. - Ici la stratégie m sera de jouer seulement sur la machine \(M_{B}\). On a donc \(Y_{2}\) une variable aléatoire représentant notre problème. Comme expliqué précédemment \(Y_{2}\) suit une loi Binomiale de paramètre (\(T_{max}\),\(p_{B}\)).
D’où le calcul de l’éspérance : E[\(Y_{2}\)] = \(T_{max}\)*\(p_{B}\) car \(Y_{2}\) suit une loi binomiale. - Ici la stratégie m sera de jouer seulement sur la machine \(M_{A}\) avec une probabilité de \(\frac{1}{2}\) (suivant la loi \(Y_{1}\)) et la machine \(M_{B}\) avec une probabilité de \(\frac{1}{2}\) (suivant la loi \(Y_{2}\)). On a donc X une variable aléatoire représentant notre problème. Comme expliqué précédemment Y suit la loi \(\frac{1}{2}\) * (\(T_{max}\),\(p_{A}\)) + \(\frac{1}{2}\) * (\(T_{max}\),\(p_{B}\))
D’où le calcul de l’éspérance : E[Y] = \(\frac{1}{2}\) * E(\(Y_{1}\)) + \(\frac{1}{2}\) * E(\(Y_{2}\)) = \(\frac{1}{2}\) * Tmax * (\(p_{A}\) + \(p_{B}\))
Nous nous intéressons à la quantité \(R_{m}\)(t) = \(p_{A}\) - \(\frac{E[G_{m}(t)]}{t}\) car celle ci nous permet d’évaluer l’efficacité de la statégie m choisie. En effet il s’agit du regret de la stratégie. Celui ci est calculé en prenant la machine permettant théoriquement le plus de gains (ici la machine A qui a une probabilité de gain de 65 pourcents contre 55 pour la machine B) et en lui soustrayant les gains effectivement réalisés. Nous cherchons donc pour un résultat optimal que ce regret soit le plus petit possible (le plus proche de 0 possible).
Q2 : On apprend puis on exploite
Intuition
Dans cette partie nous allons étudier la stratégie \(m_{l}\) consistant à jouer alternativement sur la machine A puis sur la machine B pendant (\(\epsilon\) * \(T_{max}\)) coups, choisir la machine ayant eu le plus de succès, puis ne jouer que sur cette machine.
Cette stratégie est la première de type adaptative, elle aura comme paramètre la valeur d’\(\epsilon\) qui influera sur le choix de la meilleure machine. Nous pensons que cette stratégie sera bonne même si elle aura des limites :
- Un \(\epsilon\) trop petit pourrait tromper notre estimation des probabilités pA et pB, en effet, un échantillon trop petit pourrait mener à choisir la moins prometteuse.
- Un \(\epsilon\) trop grand gâcherait un trop gros nombre de parties à estimer laquelle des deux machines est la plus prometteuse.
- Nous ne savons pas pour l’instant quel serait la meilleure valeur d’\(\epsilon\). Afin d’être quasi certain de choisir la machine prometteuse tout en limitant le nombre de parties d’estimation (dans l’idée de jouer le plus possible sur la machine prometteuse pour maximiser nos gains).
Réponses aux questions
Voici déjà quelques lignes de code necessaires pour la suite :
library("ggplot2")
library("dplyr")##
## Attaching package: 'dplyr'## The following objects are masked from 'package:stats':
##
## filter, lag## The following objects are masked from 'package:base':
##
## intersect, setdiff, setequal, uniongainA = 0
gainB = 0
perteA = 0
perteB = 0
gain = 0
Rm = c()
pA = 0.65
pB = 0.55
flag = 1
N=100
set.seed(22)Nous simulons cette stratégie grâce à la fonction Q2 suivante prenant en argument \(T_{max}\) et :
Q2 = function(Tmax, epsilon){
#On apprend
for (i in 1:(epsilon*Tmax)){
flag = 1-flag
p = runif(1)
if (!flag && (p<pA))
gainA = gainA + 1
else if (flag && (p<pB))
gainB = gainB + 1
gain = gainA + gainB
Rm[i] = pA - (gain/i)
}
#on exploite
if (gainA>gainB)
pSuite = pA
else pSuite = pB
for (i in (epsilon*Tmax):Tmax){
p = runif(1)
if (p<pSuite)
gain=gain+1
Rm[i] = pA - (gain/i)
}
t = 1:Tmax
df = data.frame(t = t, Rm = Rm)
return (df)
}Q2 renvoie une data.frame composée de deux colonnes : la première représentant le temps , la deuxième représentant le vecteur composé du regret en fonction du temps. Par la suite nous allons effectuer notre experience 100 fois, puis nous ferons la moyenne des 100 vecteurs de regret dans le but d’avoir une idée plus précise de ce qu’il se passe :
AfficheQ2 = function(Tmax, epsilon){
df = data.frame()
for (i in 1:N){
sim = Q2(Tmax, epsilon)
sim = data.frame(sim, Id = i)
df = rbind(df, sim)
}
# calcul de la moyenne
m = df %>% group_by(t) %>% summarise(moyenne = mean(Rm))
df = data.frame(df,m$moyenne)
ggplot(df, aes(x = t, y = Rm, group = Id)) + geom_line(size = 0.05) + geom_line(aes(t, m.moyenne), colour = "red",size = 0.4)
}
AfficheQ2(1000,0.05)
Nous avons donc réalisé une boucle de 100 simulations que nous ajoutons dans notre data.frame grâce à rbind, nous rajoutons aussi une colonne Id permettant par la suite de tracer la courbe des simulations en les regroupant par Id. Enfin nous rajoutons en rouge la moyenne de toutes les simulations calculées avec dplyr.
Pour la suite nous fixerons \(T_{max}\) à 2000 pour obtenir un resultats plus précis et des trajectoire plus nettes :
AfficheQ2(2000,0.05)
Nous pouvons observer deux différentes tendances dans les trajectoires : certaines sont très proche d’un regret nul tandis que d’autre de rapproche d’un regret de 0.1. Cela peut facilement s’expliquer, effectivement durant la phase de test (\(\epsilon\) * \(T_{max}\) premiers coups), il est tout à fais possible que la machine B l’emporte sur la A car il n’y a pas assez de tentatives pour avoir un résultat fiable. Auquel cas nous aurons un regret équivalent a \(p_{A} - p_{B} = 0.65 - 0.55 = 0.1\). Nous pouvons améliorer les résultats en ayant une phase d’apprentissage plus grande. Pour preuve essayons avec un \(\epsilon\) beaucoup plus élevé :
AfficheQ2(2000,0.2)
Dans ce cas la il y a beaucoup plus de chance que la machine A (dont la probabiloté de victoire est de 0.65) l’emporte sur la machine B. Il y aura ainsi beaucoup moins de trajectoire possédant un regret aux alentours de 0.1. Nous avons le cas inverse si nous fixons epsilon avec une toute petite valeure :
AfficheQ2(2000,0.01)
Q3 : On exploite mais on se force à toujours apprendre(un peu)
Intuition
Pour la sratégie \(m_{G}\) nous jouons chaque coup sur la machine ayant jusqu’à présent le meilleur ratio gain par partie joué. Cependant il reste une probabilité de 1-\(\epsilon\) de jouer sur la machine ayant le ratio le plus faible. Enfin, en cas de ratio égal (par exemple pour le choix de la première machine sur laquelle nous allons jouer) nous prenons aléatoirement une des deux machines. Cette stratégie est la seconde de type adaptative, mais contrairement à la stratégie précédente qui avait une phase fixe d’apprentissage, celle-ci ne se limite pas à quelques parties de jeu pour apprendre, de plus \(\epsilon\) rend le choix de la machine à utiliser plus aléatoire. Il est donc plutôt compliqué de savoir si cette stratégie sera meilleure ou non que celle de la question 2. Cependant, tout comme la première stratégie, le choix de l’\(\epsilon\) sera décisif, en effet un \(\epsilon\) trop petit empèchera de changer de machine si par mal chance la mauvaise machine à été jouée, tandis qu’un \(\epsilon\) trop grand pourra plus facilement faire changer de machine, même si il s’agit de la meilleure qui a été choisie.
Réponses aux questions
Nous réalisons donc une fonction permettant de choisir la machine sur laquelle nous allons jouer :
Choisir = function(gainA, gainB, nbrA, nbrB,epsilon){
#calcul des ratios
ratioA = (gainA)/(nbrA+1)
ratioB = (gainB)/(nbrB+1)
#choix de la machine
choix = runif(1)
if (ratioA > ratioB){
if (choix < (1-epsilon))
p=pA
else p=pB
}
else if (ratioB > ratioA){
if (choix < (1-epsilon))
p=pB
else p=pA
}
else {
if (choix < 0.5)
p=pB
else p=pA
}
return (p)
}Puis nous implémentons notre fonction Q3 simulant la stratégie \(m_{G}\) :
Q3 = function(Tmax,epsilon){
gainA = 0
gainB = 0
nbrA = 0
nbrB = 0
alea = 0
Rm = c()
# on exploite mais on continue d'apprendre
p = Choisir(gainA, gainB, nbrA, nbrB, epsilon)
for (i in 1:Tmax){
alea = runif(1)
if(p==pA){
nbrA = nbrA+1
if (alea < p)
gainA = gainA+1
}
else if (p==pB){
nbrB =nbrB+1
if (alea < p)
gainB = gainB+1
}
gain = gainA + gainB
Rm[i] = pA - (gain/i)
p = Choisir(gainA, gainB, nbrA, nbrB, epsilon)
}
t = 1:Tmax
df = data.frame(t, Rm)
return (df)
}
AfficheQ3 = function(Tmax, epsilon){
df = data.frame()
for (i in 1:N){
sim = Q3(Tmax,epsilon)
sim = data.frame(sim, Id = i)
df = rbind(df, sim)
}
#calcul de la moyenne
m = df %>% group_by(t) %>% summarise(moyenne = mean(Rm))
df = data.frame(df,m$moyenne)
test <- ggplot(df, aes(x = t, y = Rm, group = Id)) + geom_line(size = 0.05)
test + geom_line(aes(t, m.moyenne), colour = "red",size = 0.4)
}
AfficheQ3(2000,0.1)
Nous pouvons déja constater que le regret de cette stratégie tend plus rapidement vers une valeure plus proche de 0, il s’agit donc aussi d’une bonne stratégie.
Pour cette question nous pouvons encore une fois faire varier epsilon pour voir ce qu’il se passe.
Prenons un epsilon élevé :
AfficheQ3(2000,0.5)
Nous avons alors une chance sur deux de prendre la machine avec le moins bon ratio, d’où les mauvais resultats obtenus pour le regret.
Si nous prenons un epsilon trop petit nous n’aurons au contraire aucune, ou très peu de chance de changer de machine une fois la première machine choisie, ce qui donne les résultats suivant :
AfficheQ3(2000,0.03)
Q4 : On tire au hasard en biaisant selon nos observations
Intuition
Ici à chaque étape t la machine dont la probabilité vraisemblable (calculée grace à une loi beta) est la plus élevée sera la machine choisie. Cette stratégie ressemble fortement à la stratégie précédente si ce n’est que nous ne calculons plus le ratio de victoire mais la valeure vraisemblable de \(p_{A}\) et \(p_{B}\). Des trajectoire similaires à la stratégie \(m_{G}\) sont donc attendues.
Réponses aux questions
Voici la fonction de simulation correspondant à \(m_{T}\) :
Q4 = function(Tmax){
for (i in 1:Tmax){
vraisemblableA = rbeta(1,gainA+1,perteA+1)
vraisemblableB = rbeta(1,gainB+1,perteB+1)
if(vraisemblableA > vraisemblableB){
if (runif(1) < pA)
gainA = gainA + 1
else perteA = perteA + 1
}
else if(vraisemblableA <= vraisemblableB){
if (runif(1) < pB)
gainB = gainB + 1
else perteB = perteB + 1
}
gain = gainA + gainB
Rm[i] = pA - (gain/i)
}
t = 1:Tmax
df = data.frame(t, Rm)
return (df)
}
AfficheQ4 = function(Tmax){
df = data.frame()
for (i in 1:N){
sim = Q4(Tmax)
sim = data.frame(sim, Id = i)
df = rbind(df, sim)
}
#calcul de la moyenne
m = df %>% group_by(t) %>% summarise(moyenne = mean(Rm))
df = data.frame(df,m$moyenne)
test <- ggplot(df, aes(x = t, y = Rm, group = Id)) + geom_line(size = 0.05)
test + geom_line(aes(t, m.moyenne), colour = "red",size = 0.4)
}
AfficheQ4(2000)
On peut constater que les résultats sont bien semblables à ceux de la question 3, mais légèrement meilleurs tout de même. En effet le regret tend plus vite vers 0 et les trajectoires son plus centrées autour de 0. Cette stratégie parait donc meilleure que les autres.
Nous allons désormais, comme conseillé dans l’énoncé, faire un switch permettant de choisir quelle stratégie utiliser, et facilitant l’observation des résultats :
dm = function(question, Tmax, epsilon){
switch(question,
Q2 = AfficheQ2(Tmax, epsilon),
Q3 = AfficheQ3(Tmax, epsilon),
Q4 = AfficheQ4(Tmax))
}
dm("Q2",1000, 0.05)
dm("Q3",1000, 0.1)
dm("Q4",1000)