DM
Antoine THOMAS et Maxence VINCENT
Partie Intuition
Q1
Soit m la stratégie qui consiste à jouer systématiquement la machine \(M_A\). \(E[G_{MB}(T)] = 1/T * \sum_{i=1}^T(1*P_A) = 1/T * P_A * T = P_A\)
Soit m la stratégie qui consiste à jouer systématiquement la machine \(M_B\). \(E[G_{MA}(T)] = 1/T \sum_{i=1}^T(1*P_B) = 1/T * P_B * T = P_B\)
Soit m la stratégie qui consiste à jouer une fois sur 2 la machine \(M_A\) et une fois sur deux la machine \(M_B\). \(E[G_m(T)] = E[\frac{G_{MA}+G_{MB}}{2}(T)] = \frac{E[(G_{MA}+G_{MB})(T)]}{2} = \frac{E[G_{MA}(T)]+E[G_{MB}(T)]}{2}] = \frac {P_a + P_b}{2}\)
On s’intéresse à la quantité \(R_m\) car elle correspond à la perte de la machine que l’on a choisi par rapport à la meilleur machine. On cherche donc à minimiser cette perte. Une bonne “stratégie” doit avoir un regret le plus petit possible afin de choisir la meilleur machine dans la plupart des cas.
Q2
Cette stratégie consiste à faire des essais sur chacune des deux machines pour trouver estimer laquelle est la meilleur puis ensuite de ne jouer que sur la meilleur machine. Le problème étant que si l’on fait peu d’essai lors de la phase de recherche de la meilleur machine alors on peut se tromper auquel cas la perte sera énorme, cependant si l’on fait trop d’essais alors la perte sera grande lors de la phase de test. Avec comme nombre d’essais lors de la phase de test 0.05T, si T = 100 alors on aura trop peu d’information mais pour un T = 100 000 on aura peu de chance de se tromper sur la méthode à utiliser.
Q3
Cette stratégie utilise le ratio de victoire de chaque machine pour savoir où jouer avec 1 - \(\epsilon\) chance, le problème de cette méthode c’est que le ratio de victoire peut être biaisé en début de jeu avec un \(\epsilon\) trop faible, en effet si on a de bons résultats sur la machine A au début et un ou deux mauvais résultat sur la machine B alors on va jouer souvent sur la machine A et presque pas sur la machine B ce qui ne permettra pas ou prendra très longtemps au ratio de la machine B d’augmenter et de dépasser le ratio de la machine A. Par contre si \(\epsilon\) est haut alors on prendra dans beaucoup trop de cas la machine la moins bonne.
Q4
Cette sratégie suit la même idée que la précédente sauf qu’au lieu d’utiliser un \(\epsilon\) fixé on utlise une loi de probabilité utilisant le nombre de victoire et de défaite de la machine et qui a long terme sera une gaussienne centrée sur la probabilité de la machine. Cette stratégie semble meilleur que la précédente puisqu’on aura moins les problèmes sités ci dessus.
Partie rélisation
On choisit t = 2000 car on a une bonne vision des résultats sans que ce soit trop coûteux.
Q2
methode1 = function(epsilon){
Rm = c()
sommeA =0
sommeB =0
Pchoisi = 0
if(epsilon*Tmax %% 2 == 1) {
test = epsilon * Tmax+1
}else {
test = epsilon * Tmax
}
i=1
while (i < test) {
Ares = rbinom(1,1,Pa)
sommeA = sommeA + Ares
Rm[i] = Pa - (sommeA+sommeB)/i
Bres = rbinom(1,1,Pb)
sommeB = sommeB + Bres
Rm[i+1] = Pa - (sommeA+sommeB)/(i+1)
i = i +2
}
Ea = 2*sommeA/test
Eb = 2*sommeB/test
somme = sommeA + sommeB
if(Ea > Eb){
Pchoisi = Pa
}else if(Ea < Eb) {
Pchoisi = Pb
}else {
if(runif(1)>0.5){
Pchoisi = Pa
}else {
Pchoisi = Pb
}
}
somme = sommeA+sommeB
for(k in i : Tmax){
res = rbinom(1,1,Pchoisi)
somme = somme + res
Rm[k] = Pa - (somme/k)
}
d = data.frame(t = 1:Tmax, Rm_t = Rm, couleur = "simulation")
return(d)
}On voit que pour \(\epsilon\) = 0.05 La moyenne du regret approche 0.0158 pour t = 2000. Lorsqu’on regarde à un temps t grand, on voit deux types de trajectoires, une trajectoire où le regret est proche de 0 et une autre ou le regret est plus proche de 0,1. Ces deux cas sont en fait décidés par la phase de recherche ou pendant les 100 premiers essais on estime quel machine est la meilleur, dans le cas ou le regret est de 0.1 cela signifie que l’on choisit la machine B qui a moins de chance de gagner. Pour réduire les chances de se tromper de machine il faudrait augmenter soit notre T soit notre \(\epsilon\) même si cela signifie faire plus d’essais sur la “mauvaise” machine. En effet on voit que si l’on augmente \(\epsilon\) à 0.3, on aura plus qu’une seule tendance approchant zéro pour t = 2000 par contre on a joué 15% de nos parties sur la moins bonne machine. Je pense que ce n’est pas une bonne stratégie, soit on prend un faible \(\epsilon\) et il y a une chance non négligeable de se tromper et jouer presque toute nos parties sur la “mauvais” machine soit on prend un \(\epsilon\) élevé et on jouera focément un nombre assez grand de partie sur la machine ayant une faible chance de gain.
Q3
methode2 = function(epsilon2){
tentativeA = 0
sommeA = 0
sommeB = 0
tentativeB = 0
somme = 0
Pchoisi = 0
Rm = c()
for(k in 1 : Tmax){
bool = (runif(1)>=epsilon2)
if((sommeA/(tentativeA+1)) == (sommeB/(tentativeB+1))){
if(runif(1)>0.5){
Ares = rbinom(1,1,Pa)
sommeA = sommeA+Ares
tentativeA = tentativeA+1
somme = somme + Ares
}else {
Bres = rbinom(1,1,Pb)
sommeB = sommeB+Bres
tentativeB = tentativeB+1
somme = somme + Bres
}
} else if(((sommeA/(tentativeA+1) > sommeB/(tentativeB+1)) && bool) || ((sommeA/(tentativeA+1)<sommeB/(tentativeB+1)) && !bool )){
Ares = rbinom(1,1,Pa)
sommeA = sommeA+Ares
tentativeA = tentativeA+1
somme = somme + Ares
} else {
Bres = rbinom(1,1,Pb)
sommeB = sommeB+Bres
tentativeB = tentativeB+1
somme = somme + Bres
}
Rm[k] = Pa - (somme)/k
}
d = data.frame(t = 1:Tmax, Rm_t = Rm, couleur = "simulation")
return(d)
}On voit que cette méthode pour \(\epsilon\) = 0.1 a de meilleurs résultats que la précédente, la moyenne du regret approche 0.0144 pour t = 2000 on voit cependant qu’il ya des trajectoires qui n’approche pas un regret de 0 mais un regret de 0.1, c’est du à nôtre faible \(\epsilon\) qui fait croire à notre programme sur un petit nombre de cas que la machine B est meilleur que la machine A, en effet si on est “malchanceux” sur la machine A et “chanceux” sur la machine B c’est à dire on gagne souvent sur la machine B en début de partie et on perd souvent sur la machine A alors on va surestimer la probabilité de victoire de la machine B et sous estimer celle de la machine A. On va donc regarder les résultats de la machine A que dans un très petit nombre de cas ce qui ne permettra pas à la machine A d’avoir une moyenne qui dépassera la machine B donc on continuera à choisir la machine B. Augmenter notre \(\epsilon\) nous permettrait de gérer ce problème cependant cela signifierait aussi que l’on jouera plus souvent sur la moins bonne machine. En effet si l’on choisit \(\epsilon\) = 0.2 alors toutes les trajectoires approcherons 0 pour t = 2000 cependant nous aurons joué en moyenne 20% de partie sur la “mauvaise” machine ce qui aura augmenté notre regret moyen(0.022 au lieu de 0.015 à t = 2000). Je pense que cette stratégie est moyenne,le regret est encore trop élévé, il reste des chances de jouer beaucoup de parties sur la machine ayant la plus faible chance de gagner. Il faudrait trouver un moyen de réduire cette surestimation des probabilités sans augmenter la probabilité de jouer sur la moins bonne machine et sans augmenter le nombre de partie.
Q4
methode3 = function(){
sommeA = 0
sommeB = 0
somme = 0
Pchoisi = 0
echecA = 0
echecB = 0
Rm = c()
for(k in 1 : Tmax){
deltaA = rbeta(1,sommeA+1,echecA+1)
deltaB = rbeta(1,sommeB+1,echecB+1)
if(deltaA>deltaB){
Ares = rbinom(1,1,Pa)
if(Ares) {
sommeA = sommeA +1
somme = somme + 1
} else {
echecA = echecA +1
}
} else if (deltaA<deltaB){
Bres = rbinom(1,1,Pb)
if(Bres) {
sommeB = sommeB +1
somme = somme + 1
} else {
echecB = echecB +1
}
} else {
if(runif(1)>=0.5){
Ares = rbinom(1,1,Pa)
if(Ares) {
sommeA = sommeA +1
somme = somme + Ares
} else {
echecA = echecA +1
}
}else {
Bres = rbinom(1,1,Pb)
if(Bres) {
sommeB = sommeB +1
somme = somme + 1
} else {
echecB =echecB +1
}
}
}
Rm[k] = Pa - (somme)/k
}
d = data.frame(t = 1:Tmax, Rm_t = Rm, couleur = "simulation")
return(d)
}Cette méthode n’utilise pas de paramètre, c’est une amélioration de la méthode 2, le \(\epsilon\) choisit est remplacé par deux lois delta qui ont l’avantage de varier au cours du temps contrairement à \(\epsilon\). Cette méthode ne sur-estime et ne sous-estime pas les probabilités des machines A et B sur les premiers tirages. L’utilisation des lois delta de A et delta de B permettent malgré un départ “chanceux” pour la machine B et un départ “malchanceux” pour la machine A sur un nombre de tirage assez grand à la machine ayant la meilleur probabilité d’être choisi dans la plus part des cas. En effet on voit qu’un grand nombre de trajectoires convergent rapidement vers 0 (pour t = 1000) cependant le reste des trajectoires(cas ou la méthode 2 surestime la mauvaise machine) vont aussi converger vers 0 cela leur prendra un petit plus de temps (t=2000). On voit que pour t = 2000 le regret moyen est de 0.007 ce qui est bien inférieur aux deux autres méthodes.
Je pense que cette stratégie est bonne, le regret est faible et je finirai par ne jouer presque que sur la meilleur machine sur un grand nombre de partie, la plus part du temps je ne jouerai pas sur la “mauvaise” machine donc j’aurais plus de chance de gagner.
graphique = function(methode,epsilon){
G=data.frame()
for (k in 1 : N){
switch(methode,
M1 ={ sim = methode1(epsilon1)
},
M2 ={ sim = methode2(epsilon2)
},
M3 ={ sim = methode3()
},
)
sim = data.frame(sim, id = rep(k, Tmax))
G = rbind(G,sim)
}
A = G %>%
group_by(t) %>%
select(Rm_t) %>%
summarize(
moy = mean(Rm_t),
couleur = "moyenne"
)
G = rbind(G,data.frame(t=A$t,Rm_t=A$moy,couleur=A$couleur,id=rep(N+1,Tmax)))
return(G)
}insta
Affichage graphique
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(2)
N=100
Tmax = 2000
Pa = 0.65
Pb = 0.55
id = 1:Tmax
epsilon1 = 0.05
epsilon2 = 0.1
graph1 = graphique("M1",epsilon1)## Adding missing grouping variables: `t`graph2 = graphique("M2",epsilon2)## Adding missing grouping variables: `t`graph3 = graphique("M3")## Adding missing grouping variables: `t`graph=data.frame(graph1,Rm_t2 = graph2$Rm_t, Rm_t3 = graph3$Rm_t)
g1 <- ggplot(graph,aes(x=t,y=Rm_t,group = id,color = couleur)) + geom_line() + ggtitle("Méthode1") +
xlab("t") + ylab("Rm(t)")
g2 <- ggplot(graph,aes(x=t,y=Rm_t2,group = id,color = couleur)) + geom_line() + ggtitle("Méthode2") +
xlab("t") + ylab("Rm(t)")
g3 <- ggplot(graph,aes(x=t,y=Rm_t3,group = id,color = couleur)) + geom_line() + ggtitle("Méthode3") +
xlab("t") + ylab("Rm(t)")
g1
g2
g3
Conclusion
Pour conclure, grâce à la courbe des regrets ainsi que le regret moyen de chaque stratégie, je classerai la méthode 1 en dernière, on joue trop de partie sur la moins bonne machine. Puis je mettrais la méthode 2 en seconde position, la sratégie est meilleur mais elle peut se faire avoir par un tirage malchanceux et pour finir la méthode 3 qui est une méthode 2 dont on a réglé les problèmes de sur/sous-estimations.
Si je devais jouer je choisirai bien évidemment la stratégie numéro 3.