DM_COSCIA_CHABRE
Sujet : Au casino
1/ Questions préliminaires
- Quand la stratégie m consiste à jouer systématiquement sur la machine A, on obtient l’espérance des gains suivante: $$
E[Gm(t)] = E[{i=1}^{T} X{m(t),t}] = E[{i=1}^{T} X{mA,t}]= {i=1}^{T} E [X_{mA,t}] = {i=1}^{T} 1pA =TpA \[ \] X_{mA,t} $$
Quand la stratégie m consiste à jouer systématiquement sur la machine B, on obtient l’espérance des gains suivante: \[ E[Gm(t)] = E[\sum_{i=1}^{T} X_{m(t),t}] = E[\sum_{i=1}^{T} X_{mB,t}]= \sum_{i=1}^{T} E [X_{mB,t}] = \sum_{i=1}^{T} 1*pB =T*pB \] \[ \text {car : } X_{mB,t} \text { suit une loi binomiale de paramètre pB. } \]
Quand la stratégie m consiste à jouer sur la machine A et sur la machine B avec une probabilité 1/2, on obtient l’espérance des gains suivante: \[ E[Gm(t)]= E[\sum_{i=1}^{T} X_{m(t),t}] \] avec \[ m(t) = \frac{1}{2}*(pA +pB) \] donc on a : \[ E[Gm(t)] = E[\sum_{i=1}^{T} X_{m(t),t}] = E[\sum_{i=1}^{T} (\frac{1}{2}*X_{mA,t} + \frac{1}{2}*X_{mB,t})] = E[\sum_{i=1}^{T} (\frac{1}{2}*X_{mA,t})] + E[\sum_{i=1}^{T} (\frac{1}{2}*X_{mB,t})] \] \[= \frac{1}{2} \sum_{i=1}^{T} E[(X_{mA,t})] + \frac{1}{2} \sum_{i=1}^{T} E[(X_{mB,t})] = \frac{1}{2}*(\sum_{i=1}^{T} pA + \sum_{i=1}^{T} pB) = \frac{T}{2}*(pA+pB) \]
La quantité Rm(t)= pA - E(Gm(t))/t représente le regret que l’on ait d’avoir à jouer la stratégie m plutôt que de jouer systématiquement sur la machine A. On s’intéresse à cette quantité au cours du temps, car si la stratégie est bonne alors la courbe tendra vers 0, ce qui est facile à remarquer sur un graphique.
2/ On apprend (un peu) puis on exploite
Intuition :
Cette stratégie consiste à observer sur les e*Tmax premières parties, quelle est la machine avec la probabilité de gagner la plus élevée. Puis on joue sur cette dernière sur les parties restantes.
Cette stratégie semble assez bonne si on a un Tmax très grand, car on a le temps d’estimer et de gagner suffisamment avec le reste de parties.
En revanche, si le Tmax est assez faible, cela revient à jouer alternativement ou c’est une mauvaise stratégie, car on estime mal les probabilités.
De même, cela dépend de l’epsilon, s’il est trop faible on n’aura pas le temps d’estimer pA et pB correctement.
De manière générale, la stratégie est bonne, mais ne sera pas fiable à 100%. De ce fait, on s’attend à ce que la courbe ait des points dispersés au début afin d’estimer les probabilités puis d’avoir des courbes convergentes vers 0. Il pourra y en avoir certaines qui convergent vers 0.1.
Code de Rmt :
Le code du regret pour la stratégie mL est la fonction Rml(), voire Annexe. La simulation des 100 trajectoires est faite par la fonction main(“L”).
Analyse de la courbe de Rmt au cours du temps :
On peut voir sur cette courbe qu’il y a deux “paquets”. En effet le paquet convergent vers 0 correspond aux trajectoires qui ont bien estimé que A était la machine avec la probabilité de gains la plus élevé. En revanche, le paquet convergent vers 0.1 correspond aux trajectoires ayant pris B comme machine avec gains le plus élevée.
La moyenne est donc entre 0 et 0.1, on peut remarquer qu’elle est légèrement plus proche de 0 que de 0.1.
On peut donc en déduire que cette stratégie est bonne dans plus de la moitié des cas, mais n’est pas optimales, car il y a quand même pas mal d’essais ou la probabilité de gains la plus élevée est mal estimée. Ce qui correspond aux trajectoires ou l’algorithme se “trompe”.
Analyse de notre intuition :
Nous avions eu la bonne intuition générale, en effet nous nous attendions à ce que cette stratégie soit bonne en général. En revanche, nous ne nous attendions pas à ce qu’il y ai autant de mauvaise estimation. De ce fait nous ne pensions également pas que la moyenne soit aussi haute.
3/ On exploite, mais on se force à toujours apprendre (un peu)
Intuition :
Cette stratégie sélectionne, avec une probabilité de 1-e, la machine ayant eu la meilleure probabilité de gain jusqu’à ce tirage et avec e l’autre. En cas d’égalité on choisira entre les deux machines de manière uniforme.
Nous pensons que cette stratégie sera meilleure que la précédente, car on à toujours une chance de mieux évaluer les probabilités des machines A et B, même si cette chance est faible.
En revanche, nous pensons aussi que cette stratégie est moins bien que la précédente, car lorsqu’on a choisi une machine on évalue sa probabilité d’apparition. On peut donc dire que cette méthode est très bonne si on prend A au début, sinon elle peut être assez mauvaise.
En ce qui concerne la moyenne, dans la plupart des cas elle convergera vers 0, mais cela pourra arriver qu’elle n’y soit pas !
Code de Rmt :
Le code du regret pour la stratégie mG est la fonction Rmg(), voir Annexe. La simulation des 100 trajectoires est faite par la fonction main(“G”).
Analyse de la courbe de Rmt au cours du temps :
Comme dans la question précédente on peut voir une convergence vers 0 assez rapidement. Cette stratégie est meilleure que la précédente, car les courbes sont toutes autant voir plus proches de 0 que lors de la stratégie précédente. En effet on observe un seul paquet, non plus deux. En revanche, pour la moyenne en fonction de la valeur de base on va avoir une convergence de la moyenne vers 0 rapide, ou plus lente. Si B est choisi au début on voit que les valeurs sont plus loin de 0 au début, et se rapproche de 0 ensuite.La moyenne au bout des Tmax parties est similaire dans les deux cas.
Analyse de notre intuition :
Nous avions eu la bonne intuition générale sur les courbes, en effet nous pensions bien que la stratégie serait meilleure que la précédente. En revanche, nous pensions que la moyenne aurait été plus base, mais cela est dû au fait que nous pensions qu’il y aurait moins “d’erreur”.
4/ On tire au hasard en biaisant selon nos observations
Intuition :
Cette stratégie consiste à approximer les probabilités pA et pB à l’aide de la fonction Beta, puis à tirer sur la machine avec la probabilité la plus élevée. On met alors à jour les variables de succès et d’échec de la machine sur laquelle on a tiré en fonction du résultat du tirage.
Nous pensons que cette stratégie sera encore meilleure que la précédente, car la fonction bêta évalue généralement bien les probabilités avec un nombre de parties (réussite ou échec) assez grand. Cette stratégie ne sera donc pas nécessairement meilleure au début, mais au plus on avancera dans le temps au plus la fonction bêta sera précise, même s’il y a toujours une petite marge d’échec.
En ce qui concerne la moyenne, nous pensons donc qu’elle sera nettement plus proche de 0.
Code de Rmt :
Le code du regret pour la stratégie mT est la fonction Rmt(), voire Annexe. La simulation des 100 trajectoires est faite par la fonction main(“T”).
Analyse de la courbe de Rmt au cours du temps :
Comme dans les questions précédentes on peut voir une convergence vers 0 assez rapide. Cette méthode est légèrement meilleure que la précédente, dans le meilleur cas. En effet, lorsque la fonction bêta tire quelque chose de réaliste pA > pB lors des premières parties alors nous pouvons voir une convergence rapide vers 0 et une moyenne très proche de 0, c’est le meilleur cas. À l’opposé, dans le pire cas, la fonction bêta tire pB > pA dans les premiers lancers, dans ce cas-là, la stratégie est autant voir moins bonne que celle de la question précédente. Si on fait plusieurs simulations de la fonction main(“T”), on peut voir des courbes très différentes, soit une courbe avec une moyenne très proche de 0 et un seul “paquet de courbe”, soit un “paquet” de courbe et quelques courbes qui sont nettement au-dessus de 0 donc une moyenne plus haute.
Analyse de notre intuition :
Notre intuition était encore une fois bonne dans l’idée générale, mais nous pensions que le résultat serait toujours dans le meilleur cas décrit ci-dessus, donc que la moyenne serait encore meilleure.
Dans toutes nos intuitions, nous avions bien compris l’esprit général, mais à chaque fois nous avons sous-estimé la probabilité d’apparition du mauvais cas.
Annexe
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, unionset.seed(0)
pA = 0.65
pB = 0.55
e = 0.05
Tmax = 1000
Rml <- function() { #fonction de la stratégie L de la question 2
gains = 0 #total des gains
gain_A = 0 #total des gains sur la machine A lors des premiers lancers
gain_B = 0 #total des gains sur la machine B lors des premiers lancers
proba_max = 0 #proba_max sur les premiers lancé = pA ou pB
R = c() #initialisation du tableau des 1000 lancers
R[0]=0
for(t in 1:(e*Tmax)){ #pour les epsilon premiers tirages
if(t%%2 == 0 ){ #si la machine précédente était B
temp = rbinom(1,1,pA) #on tire selon la proba de la machine A
gain_A = gain_A + temp #on ajoute le tirage sur A au gains de A
gains = gains + temp #on ajoute aussi le gains au gains total
}else{ #si la machine précédente était A on fait de mem avec pB
temp = rbinom(1,1,pB) #ontire selon la proba de la machine B
gain_B = gain_B + temp #on ajoute le tirage sur A au gains de B
gains = gains + temp #onajoute aussi le gains au gains total
}
R[t] = pA - gains/t #on ajoute le t-ème tirage au tableau
}
if(gain_B > gain_A) #on choisi la machine sur laquelle jouer plus tard
proba_max = pB
else
proba_max = pA
for(t in (e*Tmax):Tmax){ #pour les derniers tirages
gains = gains + rbinom(1,1,proba_max) #on tire sur la machine de proba_max sur les epsilon premiers tirages
R[t] = pA - gains/t #on ajoute le t-ème gains au tableau
}
return(R) # on retourne le tableau des gains pour les Tmax tirages
}
Rmg <- function(){ #fonction de la stratégie G de la question 3
nb_succes_A = 0
nb_tirages_A = 0
nb_succes_B = 0
nb_tirages_B = 0
e = 0.1
gains = 0
prom = 0.5
eff = 0 #cette variables sert à determiner si on effectue un tirage sur B (0) ou sur A (1)
R = c() #tableau des du regret en fonction du temps
R[0]=0
for(t in 1:Tmax){ #pour tous les tirages
if(runif(1,0,1) < (1-e)){ #on tire un nombre aléatoire entre 0 et 1, si il est en dessous de la probabilité de 1-e
if(prom == (nb_succes_A/(nb_tirages_A+1))){ #on tire sur la machine la plus prometteuse
eff = 1 #on dit que l'on tire sur A si c'est elle la plus prometteuse
}else if(prom == (nb_succes_B/(nb_tirages_B+1))){
eff = 0 #on dit que l'on tire sur B si c'est elle la plus prometteuse
}else{
if(runif(1,0,1) < 0.5){ #si elle on la meme probabilité de gain, on tire au hasard entre les deux machines
eff = 1
}else{
eff = 0
}
}
}else{ #sinon on tire sur la machine la moins prometteuse
if(prom == (nb_succes_A/(nb_tirages_A+1))){ #si la machine la plus prometteuse est A
eff = 0 #on tire sur B
}else if(prom == (nb_succes_B/(nb_tirages_B+1))){ #si la machine la plus prometteuse est B
eff = 1 #on tire sur A
}else{
if(runif(1,0,1) < 0.5){ #si elle on la meme probabilité de gain, on tire au hasard entre les deux machines
eff = 1
}else{
eff = 0
}
}
}
if(eff){ #on effectue le tirage sur A
temp = rbinom(1,1, pA) #on tire un nombre selon pA
gains = gains + temp #on ajoute l'echec (0) ou la reussite (1) du tirage au gain
nb_succes_A = nb_succes_A + temp #on ajoute l'echec (0) ou la reussite (1) du tirage au nombre de succes
nb_tirages_A = nb_tirages_A +1 #on augmente le nombre de tirages sur A de 1
}else{ #on effectue le tirage sur B de la meme manière mais avec pB
temp = rbinom(1,1, pB)
gains = gains + temp
nb_succes_B = nb_succes_B + temp
nb_tirages_B = nb_tirages_B +1
}
if((nb_succes_A/(nb_tirages_A+1)) > prom){ #on met à jour la machine la plus prometteuse avec le nouveau tirage
prom = (nb_succes_A/(nb_tirages_A+1))
}else{
prom = (nb_succes_B/(nb_tirages_B+1))
}
R[t] = pA - gains/t #on ajoute le regret pour ce tirage au tableau
}
return(R) #on retourne le tableau de regret
}
Rmt <- function(){
approx_pA = 0
approx_pB = 0
nb_succes_A = 0
nb_perte_A = 0
nb_succes_B = 0
nb_perte_B = 0
gains = 0
R =c()
R[0]=0
for(t in 1:Tmax){ #pour toutes les parties
approx_pA = rbeta(1, nb_succes_A+1, nb_perte_A+1) #on approche la probabilité de A en tirant aléatoirement selon la fonction beta
approx_pB = rbeta(1, nb_succes_B+1, nb_perte_B+1) #on approche la probabilité de B en tirant aléatoirement selon la fonction beta
if(approx_pA > approx_pB){ #si la probabilité de A est plus élevé que celle de B
if(rbinom(1,1,pA)){ #on tire un nombre selon pA, si c'est une réussite
nb_succes_A = nb_succes_A + 1 #on augmente le nombre de succés sur la machine A
gains = gains + 1 #on augmznte le gains total
}else{ #si on a perdu
nb_perte_A = nb_perte_A + 1 #on incrémente le nombre de perte
}
}else{ #si la probabilité de B est plus élevé que celle de A
if(rbinom(1,1,pB)){ #on tire un nombre avec la probabilité pB, si c'est on a gagné
nb_succes_B = nb_succes_B + 1 #on incrémente le nombre de succes de B
gains = gains + 1 #ainsi que le gain total
}else{ #si on a perdu
nb_perte_B = nb_perte_B + 1 #on incrémente le nombre de perte de B
}
}
R[t]= pA - gains/t #on ajoute la valeur du regret pour ce tirages au tableau
}
return(R) #on retourne le tableau
}
main <- function(meth){
N = 100 #on défini le nombre de trajectoires à 100
df = data.frame() #on initialise la data frame
t1 = 1:Tmax #on déclare un vector de temps
switch (meth, #on choisi quelle fonction appelé pour créer notre data frame en fonction de la stratégie donné en argument
'L' = { for(j in 1:N){ #pour les N trajectoires
df = rbind(df, data.frame(id = j, t = t1, G=Rml())) #on ajoute à la data frame la nouvelle data frame
}},
'G' = {
for(j in 1:N){ #pour les N trajectoires
df = rbind(df, data.frame(id = j, t = t1, G=Rmg())) #on ajoute à la data frame la nouvelle data frame
}},
'T' = {
for(j in 1:N){ #pour les N trajectoires
df = rbind(df, data.frame(id = j, t = t1, G=Rmt())) #on ajoute à la data frame la nouvelle data frame
}}
)
moyenne = df %>% group_by(t) %>% summarise(n = n(), G_mean = mean(G)) %>% filter(n > 1) #on calcule la moyenne des gains par parties des N trajectoires
names(moyenne) = c("t1", "n", "G_mean") #on renomme les colonne des données de la moyenne
df = cbind(df, moyenne) #on aoute les colonnes de la moyenne à la data frame
ggplot(df, aes(x=t, y=G, group(id)))+geom_point(alpha = 0.1, size = 0.1) +geom_point(data=df, aes(x=t1, y=G_mean), size = 0.2, color = "red")+ ggtitle(paste('Stratégie utilisé : ', meth))+theme(plot.title = element_text(hjust = 0.5))+xlab("Tirage t")+ylab("Regret au tirage t") #on trace les N trajectoires, ainsi que la moyenne en rouge et on ajoute un titre
}
main("L") #on trace la courbe pour la stratégie L (celle de la question 2)
main("G") #on trace la courbe pour la stratégie G (celle de la question 3)
main("T") #on trace la courbe pour la stratégie T (celle de la question 4)