DM PS
BONASPETTI Giulia & DECAMPS Marceau
6 décembre 2018
Q1 : Questions préliminaires
Forme close pour les différentes stratégies :
-Statégie 1 : E(Gm(T)) = E(Ma).Tmax = Tmax.Pa
-Statégie 2 : E(Gm(T)) = E(Mb).Tmax = Tmax.Pb
-Statégie 3 : E(Gm(T)) = E(Ma).Tmax/2 + E(Mb).Tmax/2 = Tmax/2.Pa + Tmax/2.Pb
On s’interesse à Rm(t) = Pa - (E(Gm(t)))/t, car ce regret nous indique si notre espérence est supérieure à la probabilité de gain sur la machine la plus prometteuse, autrement dit, si notre système est bon ou pas.
Le regret tend vers 0 en l’infinie si le système est bon, nous cherchons donc a le minimiser.
Q2 : 1ère méthode
Stratégie
Nous avons un nombre de tirages T. Nous passons les epsilon premiers tirages à faire atérner entre la machine A et la machine B. La machine qui nous a fait gagné le plus est alors utilisée jusqu’à la fin de nos tirages.
Intuition
Dans les epsilon premiers tirage, le R tend vers 0,05 car il alterne entre A (qui tend à 0) et B (qui tend à 0,10) et après cela, nous choisirons probablement A et tendrons à 0.
Code
q2 = function(Tmax = 1000, Pa = 0.65, Pb = 0.55){
Epsilon = 0.05
GainsA = 0
GainsB = 0
GainsTot = 0
Pchoisie = 0
Regret = c()
for (i in 1:(Epsilon*Tmax)) {
tirage = runif(1)
if(i%%2==1 && tirage<=Pa){
GainsA = GainsA + 1 # add 1 following Pa
}else if(i%%2==0 && tirage<=Pb) {
GainsB = GainsB + 1 # add 1 following Pb
}
GainsTot = GainsA + GainsB
Regret[i]=Pa - GainsTot/i
}
if (GainsA>GainsB){
Pchoisie=Pa
}else if(GainsB>GainsA){
Pchoisie=Pb
}else{
Pchoisie = runif(1)
if(Pchoisie>.5)
Pchoisie = Pa #50% chance take Pa or Pb
else
Pchoisie = Pb
}
for(i in (Epsilon*Tmax):Tmax){
tirage = runif(1)
if(tirage<=Pchoisie)
GainsTot = GainsTot + 1 # 1 following Pchoisie
Regret[i]=Pa - GainsTot/i
}
return(Regret)
}Q3 : 2ème méthode
Stratégie
Pour chaque tirage, on choisit la machine la plus prometteuse (taux de réussite le plus élevé jusqu’à présent) avec une probabilité de 90 %. Si les taux sont identiques, on choisit une machine au hasard
Intuition
10% du temps, nous choisirons la mauvaise machine. Cette méthode n’aura jamais tendance à tendre vers 0, mais plutôt 10 % * .10 = .01
Code
q3 = function(Tmax = 1000, Pa = 0.65, Pb = 0.55){
isA = 0
isB = 0
Pchoisie = 0
Epsilon = 0.9
GainsA = 0
GainsB = 0
GainsTot = 0
Regret = c()
#on fait les Tmax tirages
for(i in 1:Tmax){
#Choisir la nouvelle probabilité
ratioA = GainsA / (i+1)
ratioB = GainsB / (i+1)
Pselec = runif(1)
if((ratioA>ratioB && Pselec>Epsilon) || (ratioA<ratioB && Pselec<=Epsilon)){
Pchoisie = Pa
isA = 1
isB = 0
}else if((ratioA<ratioB && Pselec>Epsilon) || (ratioA>ratioB && Pselec<=Epsilon)){
Pchoisie = Pb
isA = 0
isB = 1
}else{
if(Pselec>0.5){
Pchoisie = Pa
isA = 1
isB = 0
}else {
Pchoisie = Pb
isB = 1
isA = 0
}
}
tirage = runif(1)
if(tirage<=Pchoisie){
GainsTot = GainsTot + 1 # 1 following Pchoisie
if(isA == 1){
GainsA = GainsA + 1
}else{
GainsB = GainsB + 1
}
}
Regret[i]=Pa - GainsTot/i
}
return(Regret)
}Q4 : 3ème méthode
Stratégie
Prendre un nombre aléatoire en bêta pour les deux probabilités (vraisemblanceA et vraisemblanceB), les comparer. On choisit de jouer avec la machine qui a la plus grande vraisemblance.
Intuition
Cette méthode correspond à un pourcentage de fois que la loi beta choisit la machine B*0.1. L’intuition sur le résutat est compliqué à percevoir, mais on peut comprendre qu’elle est proche de la méthode 2, avec une correction d’erreur en plus.
Code
q4 = function(Tmax = 1000, Pa = 0.65, Pb = 0.55){
isA = 0
isB = 0
Pchoisie = 0
GainsA = 0
GainsB = 0
PerteA = 0
PerteB = 0
varA = 0
varB = 0
GainsTot = 0
Regret = c()
for(i in 1:Tmax){
varA = dbeta(1,shape1=GainsA+1,shape2=PerteA+1)
varB = dbeta(1,shape1=GainsB+1,shape2=PerteB+1)
if(varA>varB){
Pchoisie = Pa
isA = 1
isB = 0
}else if(varA<varB){
Pchoisie = Pb
isA = 0
isB = 1
}else{
Pchoisie = runif(1)
if(Pchoisie>0.5){
Pchoisie = Pa
isA = 1
isB = 0
}else {
Pchoisie = Pb
isB = 1
isA = 0
}
}
tirage = runif(1)
if(tirage<=Pchoisie){
GainsTot = GainsTot + 1 # 1 following Pchoisie
if(isA == 1){
GainsA = GainsA + 1
}else{
GainsB = GainsB + 1
}
}else{
if(isA == 1)
PerteA = PerteA + 1
else
PerteB = PerteB + 1
}
Regret[i]=Pa - GainsTot/i
}
return(Regret)
}Dessin et analyse des méthodes
# Fontion main qui execute la méthode N fois et dessine le regret sur un graphe.
main=function(methode, Tmax = 1000, Pa = .65, Pb = .55, N=100){
df=data.frame()
for (i in 1:N) {
t = 1:Tmax
Rm_t = data.frame(id = i, t1 = t, G = switch(methode, "1"=q2(), "2"=q3(), "3"=q4()))
df= rbind(df,Rm_t)
}
moyenne = df %>% group_by(t1) %>% summarise(m = mean(G))
df = data.frame(df, moyenne$m)
ggplot(df, aes(x =t1, y= G, group(id)))+geom_point(alpha=0.5, size =0.03)+geom_line(aes(t1, moyenne.m), colour="red")
}
# Méthode 1
main("1")
Analyse
Nous penson que cette stratégie est moyenne. En effet, si l’algorithme choisit la mauvaise machine sur les premiers tirages, il n’a aucun moyen de se rattraper, mais s’il choisit la bonne machine, alors il tend au meilleur regret (optimal).
Ce résultat est flagrant lorsque nous regardons le graphe, car nous voyons très bien la démarcation entre les deux machines.
Les chances pour que la bonne machine soit choisit sont supérieures, mais il reste tout de même une grande probabilité pour que la mauvaise machine soit choisit.
# Méthode 2
main("2")
Analyse
Nous pouvons voir sur le graphe que les tirages sont beaucup plus regroupés qu’avec la première méthode. Avec un nombre de tirage assez grand, la première méthode est meilleure parce que le temps passé à regarder quelle machine est la plus prometteuse est grand, ce qui augmente les chances de choisir la bonne machine, mais avec un T moins grand, la deuxième méthode est meilleure car elle arriverait sûrement en .01, qui est proche de 0. Cependant cette méthode n’est pas très “stable”, car si nous partons sur la mauvaise machine, nous n’avons que 10% de chance de choisir la bonne, et à l’inverse, si nous partons sur la bonne machine, nous avons 10% de chance de continuer avec la mauvaise.
# Méthode 3
main("3")
Analyse
Voyant le résultat, nous concluons que c’est une stratégie avec des résultats très similaires à la méthode 2. On peut tout de même s’apercevoir que le regroupement, et la moyenne, sont plus proche inférieurs à ceux de la méthode 2. Cela nous montre que cette méthode est plus efficace. De plus, il n’y a rien qui empeche que la solution soit optimale, contrairement aux autres méthodes qui ne fonctionnent bien que dans des conditions particulières.
Il semble donc que cette méthode soit la meilleure solution.