DM1 Probas et simulations
Antoine Pelisson - Loïc Schanen
Sujet 1 : Au casino
On a \(\forall M, \forall t, X_{M,t}\) ~ \(B(1, p_M)\) et \(G_M(T) = \sum_{t=1}^T X_{m(t),t}\).
Questions Préliminaires
On sait que l’espérance d’une loi binomiale de paramètres n et p est \(n * p\). On a donc ici \(E[G_M(T)] = Tp_M\) car \(G_M(T)\) suit une loi binomiale de paramètres \(T, p_M\).
Or, ne jouer que sur la machine A revient à avoir une loi binomiale de paramètres Tmax et pA. Donc l’espérance est de \(Tmax * pA\).
On obtient donc sur la machine A : \(E[G_M(T)] = Tp_A\).
Pour la même raison, on a l’espérance de la méthode “ne jouer que sur la machine B” égale à \(Tmax * pB\).
On obtient donc sur la machine A : \(E[G_M(T)] = Tp_B\).
Enfin, si on joue une fois sur deux sur la machine A et l’autre fois sur la machine B, on peux assimiler cette méthode à la somme de deux lois binomiales \(B(Tmax/2,pA)\) et \(B(Tmax/2,pB)\). Or l’espérance de la somme de deux variables aléatoires est égale à la somme des espérances. Ainsi, l’espérance de cette dernière méthode est \(\frac{Tmax * (pA + pB)}{2}\).
Dans la suite du DM, on supposera (pA,pB) = (0.65, 0.55), de plus, on va réaliser des estimations basées sur un N supérieur ou égal à 100.
On définit ensuite le regret ainsi: \(R_m(t) = p_A - \frac{E[G_m(t)]}{t}\). Cette expression est interessante car elle permet de comparer les différentes méthodes, plus une méthode est efficace, plus \(p_A - \frac{E[G_m(t)]}{t}\) sera faible (pour des t assez grands). En effet, \(\frac{E[G_m(t)]}{t}\) représente le gain moyen jusqu’à l’instant t. Donc plus le gain sera grand (meilleure méthode), plus le regret sera faible. Ainsi une “bonne” statégie aura un regret faible.
Nous définissons une fonction calcul_regret afin de transformer un tableau de \(Tmax\) essais en tableau de regrets, de plus nous fixons la graine de notre générateur pour qu’il soit possible de reproduire nos données avec exactitude :
set.seed(966613);
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, union# Variables à changer pour faire varier l'expérience
pa = 0.65;
pb = 0.55;
Tmax = 1000;
N = 100;
# Fonction pour transformer un tableau de Tmax essais en tableau de regrets
calcul_regret = function(t, pa, Tmax){
regret = c()
for(i in 1:Tmax){
regret = c(regret, pa - sum(t[1:i])/i)
}
return(regret)
}Question 2
On s’interesse maintenant à la stratégie consistant à choisir un certain \(\epsilon\) compris entre 0 et 1 tel que l’on va utiliser \(Tmax * \epsilon\) essais alternés entre les deux machines pour déterminer la machine la plus rentable; puis jouer uniquement sur celle-là par la suite.
Cette stratégie peut être interessante si l’écart entre pA et pB est important car la détermination de la meilleure machine sera rapide et plutôt fiable même pour un petit \(\epsilon\). Par contre, si pA et pB sont proches, il faut un \(\epsilon\) trop grand pour déterminer la bonne machine et on gâche alors beaucoup d’essais avec un risque d’erreur en plus. Cette méthode dépend donc beaucoup de l’écart existant entre pA et pB et de la valeur de \(\epsilon\).
Nous avons réalisé une fonction test_1 afin d’obtenir une estimation du regret de la stratégie \(m_L\) sous forme de tableau avant de pouvoir la représenter au cours du temps. Pour cela nous décomposons cette stratégie en deux étapes : la première consiste à estimer les probabilités \(p_A\) et \(p_B\) en regardant les gains obtenus sur chaque machine après avoir joué \(\epsilon * T\) parties de manière alternée sur la machine A et sur la machine B. Il faut ensuite remettre dans l’ordre les valeurs obtenues lors des premières parties dans un tableau qui contiendra toutes les valeurs de l’ensemble des parties réalisées. Une fois cela fait nous pourrons calculer le regret de ce tableau.
res = c();
test_1 = function(e = 0.05) {
# On joue A et B une fois sur deux pendant e*Tmax essais
resA = rbinom(e*Tmax/2, 1, pa);
resB = rbinom(e*Tmax/2, 1, pa);
# On calcule les gains de chaque machine
gainA = sum(resA);
gainB = sum(resB);
# On alterne les résultats précédents en remettant dans l'ordre des parties jouées les résultats obtenues précédemment
for(i in seq(2, e*Tmax, 2)){
res[i-1] = resA[i/2];
res[i] = resB[i/2];
}
# On ne joue que sur la machine la plus rentable
if(gainA >= gainB){
res = c(res, rbinom(Tmax - e * (Tmax - 1), 1, pa));
} else {
res = c(res, rbinom(Tmax - e * (Tmax - 1), 1, pb));
}
df_regret = data.frame(t = (1:Tmax),reg = calcul_regret(res, pa, Tmax));
return (df_regret);
}Question 3
On s’interesse maintenant à la stratégie consistant à choisir un certain \(\epsilon'\) compris entre 0 et 1 tel que \(1 - \epsilon'\) est la probabilité de jouer sur la machine la plus rentable (le meilleur rapport gain / nombre de parties jouées) jusqu’à maintenant et \(\epsilon'\) la probabilité de jouer sur l’autre.
Nous pouvons déjà voir que la valeur de \(\epsilon\) aura un certain impact sur l’efficacité de cette stratégie, en effet, nous avons une probabilité de \(1-\epsilon\) de sélectionner la machine la plus prometteuse. Nous supposons que cette stratégie aura un regret correct, plus faible que la première stratégie car moins d’erreures possibles. Néanmoins le fait que la probabilité de sélectionner la mauvaise machine dépendent de \(\epsilon\) nous semble encore trop décisif dans notre gain potentiel pour que cela en fasse une très bonne stratégie. En effet, en fonction de la valeur de \(\epsilon\) nous pouvons nous faire avoir et obtenir des résultats insatisfaisants, même si le fait que cette stratégie évolue avec le temps est un bon point, la dépendance vis à vis de \(\epsilon\) et des ratios initiaux est trop importante.
test_2 = function(e = 0.1) {
res = c();
# On stocke les gains moyens, le nombre de parties jouées et le nombre de parties gagnées de chaque machine
g_moyA = 0;
g_moyB = 0;
nb_pjA = 0;
nb_pjB = 0;
nb_pgA = 0;
nb_pgB = 0;
# On joue Tmax fois
for(i in (1:Tmax)){
# On détermine sur quelle machine jouer
if (g_moyA == g_moyB) {
rand = trunc(runif(1)*2) +1
prob = switch(rand, pa, pb);
m = switch(rand, "a", "b");
} else if (g_moyA > g_moyB) {
if (runif(1) < (1-e)) {
prob = pa;
m = "a";
} else { prob = pb; m = "b"; }
} else {
if (runif(1) < e) {
prob = pa;
m = "a";
} else { prob = pb; m = "b" }
}
res = c(res, rbinom(1,1,prob));
# On met à jour les valeurs stockées
if (m == "a") {
nb_pjA = nb_pjA + 1;
nb_pgA = nb_pgA + res[i];
g_moyA = nb_pgA/(nb_pjA+1);
} else {
nb_pjB = nb_pjB + 1;
nb_pgB = nb_pgB + res[i];
g_moyB = nb_pgB/(nb_pjB+1);
}
}
df_regret = data.frame(t = (1:Tmax),reg = calcul_regret(res, pa, Tmax));
return (df_regret);
}Question 4
On s’interesse en dernier à la stratégie qui consiste à tirer à chaque partie un nombre aléatoire suivant la densité beta pour la machine A et celle pour la machine B afin d’obtenir une estimation de \(p_A\) et de \(p_B\) pour ensuite choisir la machine qui aura la probabilité la plus élevée.
Pour nous, cette stratégie sera la plus efficace car elle évolue elle aussi en fonction du temps afin de s’approcher le plus possible de la solution optimale.
test_3 = function() {
res = c();
# On stocke le nombre de parties perdues et le nombre de parties gagnées de chaque machine
nb_ppA = 0;
nb_ppB = 0;
nb_pgA = 0;
nb_pgB = 0;
# On joue Tmax fois
for(i in (1:Tmax)) {
# On tire deux nombres suivant les lois beta de A et de B
betaA = rbeta(1, shape1 = nb_pgA+1, shape2 = nb_ppA+1);
betaB = rbeta(1, shape1 = nb_pgB+1, shape2 = nb_ppB+1);
# On joue sur la meilleure machine et on met à jour les valeurs stockées
if (betaA > betaB) {
res = c(res, rbinom(1,1,pa));
nb_pgA = nb_pgA + res[i];
nb_ppA = nb_ppA + 1 - res[i];
} else {
res = c(res, rbinom(1,1,pb));
nb_pgB = nb_pgB + res[i];
nb_ppB = nb_ppB + 1;
}
}
df_regret = data.frame(t = (1:Tmax),reg = calcul_regret(res, pa, Tmax));
return (df_regret);
}Pour tracer une estimation de \(R_m(t)\) au cours du temps t pour une stratégie \(m\), nous utiliserons le programme suivant :
# Fonction pour afficher le graphe des N trajectoires de la méthode met (1 -> mL / 2 -> mG / 3 -> mT)
affichage = function(methode = 1, e = 0.05) {
courbes = data.frame();
# On met les N dataframe de la méthode considérée dans la totale
for (i in (1:N)) {
tmp = switch(methode, test_1(e), test_2(e), test_3());
courbes = rbind(courbes, data.frame(tmp, Idx = rep(i, Tmax), Legende = "Simulations"))
}
moy_simu = courbes %>% group_by(t) %>% select(reg) %>% summarise(reg = mean(reg))
courbes = rbind(courbes, data_frame(t = moy_simu$t, reg = moy_simu$reg, Idx = rep(N+1, Tmax), Legende = "Moyenne des simulations"))
# Affichage des simulations
plot <- ggplot(courbes, aes(x = t, y = reg, group = Idx, color = Legende)) + geom_line(size=0.4) + theme_bw() + labs(x = "Temps (nombre de partie realisees)", y = "Rm(t) (Regret)") + ggtitle("Evolution du regret en fonction du temps")
plot
}Résultats et Analyses :
Stratégie \(m_L\) :
Nous pouvons, ci-dessous, observer la représentation du regret de \(m_L\) au cours du temps pour \(\epsilon = 0.05\) :
affichage()## Adding missing grouping variables: `t`
Puis une représentation du regret de \(m_L\) au cours du temps pour \(\epsilon = 0.5\) :
affichage(methode=1, e=0.5)## Adding missing grouping variables: `t`
Enfin une représentation du regret de \(m_L\) au cours du temps pour \(\epsilon = 0.8\) :
affichage(methode=1, e=0.8)## Adding missing grouping variables: `t`
A la vue de ces 3 estimations de la valeur du regret de \(m_l\) en fonction du temps, nous pouvons en déduire que \(m_L\) n’est pas une bonne stratégie car nous pouvons en effet voir ce que nous avions décrit dans nos estimations : nous avons \(p_A\) et \(p_B\) très proche et donc comme \(\epsilon\) est trop faible, l’estimation des probabilités est erronée et donc on a plus de chance de choisir la mauvaise machine et donc d’augmenter le regret. Tandis que lorsque l’on prend \(\epsilon\) assez élevé nous avons plus de chance d’obtenir la bonne machine, néanmoins nous pouvons observé que dans ce cas la courbe est en 2 parties distinctes, une première partie qui correspond au choix de la meilleure machine, et la seconde les parties effectuées sur la machine choisie avec une légère augmentation du regret car la phase de choix a été longue.
Dans le premier cas avec un \(\epsilon\) faible nous voyons qu’il y a beaucoup d’erreurs sur le choix de la machine avec une forte augmentation du regret quand cela arrive et donc la courbe est séparée en deux parties car lorsque l’on choisi la mauvaise machine nous continuons le reste des parties dessus.
Nous pouvons néamoins observer qu’avec un écart très important entre \(p_A\) et \(p_B\) et un \(\epsilon\) peu élevé il y toujours beaucoup d’erreurs (voir ci-dessous), notre estimation là dessus était donc fausse.
pa = 0.75
pb = 0.25
affichage(methode=1, e=0.1)## Adding missing grouping variables: `t`
Stratégie \(m_G\) :
Nous pouvons, ci-dessous, observer la représentation du regret de \(m_G\) au cours du temps pour \(\epsilon = 0.1\) :
pa = 0.65;
pb = 0.55;
affichage(methode=2, e=0.1)## Adding missing grouping variables: `t`
Puis une représentation du regret de \(m_G\) au cours du temps pour \(\epsilon = 0.5\) :
affichage(methode=2, e=0.5)## Adding missing grouping variables: `t`
Avec ces 2 représentations nous pouvons en conclure que nos estimations étaient bonnes : la stratégie \(m_G\) est une stratégie relativement bonne, et son efficacité augmente avec \(\epsilon\) comme nous pouvons le voir. En effet dans la première représentation, le choix de la machine la plus prometteuse est parfois erroné ce qui fait que le courbe est assez épaisse car ces mauvais choix restent non négligeables et fond augmenter le regret. Néanmoins, contrairement à la première stratégie, celle-ci évolue avec le temps et donc les erreurs se remarquent moins que dans la première.
Avec un \(\epsilon\) faible, comme les ratios sont nuls au début, nous avons une chance sur deux de choisir la mauvaise machine et donc de faire augmenter son ratio et non celui de la bonne machine, et donc beaucoup plus de chance de rejouer sur la mauvaise machine à cause de la faible valeur de \(\epsilon\). Cela explique les erreurs assez importantes sur la première représentation.
Tandis qu’avec la représenation avec un \(\epsilon\) plus élevé nous pouvons voir que le regret se stabilise plus vite et est moins élevé, car il y aura moins de chances de choisir la mauvaise machine au fur et à mesure du temps et donc le rejet se stabilisera de plus en plus vite en augmentant de moins en moins.
Stratégie \(m_T\) :
Nous pouvons, ci-dessous, observer la représentation du regret de \(m_T\) au cours du temps avec \(N = 100\) :
affichage(methode=3)## Adding missing grouping variables: `t`
Puis une représentation du regret de \(m_T\) au cours du temps pour \(N = 200\) :
affichage(methode=3)## Adding missing grouping variables: `t`
Avec ces 2 représentations nous pouvons bien observer que cette stratégie est la meilleure, en effet, on observe qu’il y a déjà assez peu d’erreurs et une stabilisation du regret assez rapide. Cette stratégie évolue au cours du temps et se “débrouille” toute seule, plus il y aura de parties réalisées plus la méthode sera efficace.
Nous pouvons conclure que la première stratégie \(m_L\) n’est pas bonne sauf pour des très grandes valeurs de \(\epsilon\), la seconde \(m_G\) est bonne pour des valeurs assez élevées de \(\epsilon\) et la troisième stratégie \(m_T\) est la meilleure car elle dépend de presque rien.
Pour réaliser ce DM nous avons beaucoup discuté avec d’autres groupes sur les méthodes à utiliser pour la réalisation des programmes car nous avions beaucoup de mal à voir comment partir, mais avec les explications de nos camarades qui nous ont expliqué comment décomposer les problèmes en plusieurs parties nous avons pu assez facilement réaliser toutes les fonctions.