[RICM4-PS] DM
Hoël Jalmin Mathieu Dumax-Vorzet
set.seed(31)
library(ggplot2)
library(dplyr)Au casino
Q1) Questions préliminaires
Intuitions
On nous fait étudier des stratégies basiques et la notion de regret afin de pouvoir mettre en place des stratégies plus adaptatives. Les stratégies plus complexes que l’on mettra en place par la suite devront avoir de meilleures performances que ces stratégies simples de référence.
Réponses
- On joue uniquement avec MA.
Forme close de l’espérance:
\(E(G_m(T)) = E(\sum^T_{t=1} X_{m(t),t}) = E(\sum^T_{t=1} X_{m_A,t}) = \sum^T_{t=1} E(X_{m_A,t}) = \sum^T_{t=1} E(p_A) = \sum^T_{t=1} p_A = p_A*T\)
- On joue uniquement avec mB.
Forme close de l’espérance:
\(E(G_m(T)) = E(\sum^T_{t=1} X_{m(t),t}) = E(\sum^T_{t=1} X_{m_B,t}) = \sum^T_{t=1} E(X_{m_B,t}) = \sum^T_{t=1} p_B = p_B*T\)
- On joue alternativement et en même proportion avec mA et mB.
Forme close de l’espérance (on suppose T pair):
\(E(G_m(T)) = E(\sum^T_{t=1} X_{m(t),t}) = E(\sum^{\frac T 2}_{t=1} X_{m_A,2t} + \sum^{\frac T 2-1}_{t=0} X_{m_B,2t+1}) =\sum^{\frac T 2}_{t=1} E(X_{m_A,2t}) + \sum^{\frac T 2-1}_{t=0} E(X_{m_B,2t+1}) =\sum^{\frac T 2}_{t=1} p_A + \sum^{\frac T 2-1}_{t=0} p_B = (p_A+p_B)*\frac T 2\)
- On prend \((p_A,p_B) = (0.65,0.55)\). Donc, on sait que pour ce cas, la meilleure machine est A et que la meilleure stratégie est donc de jouer tout le temps sur cette machine.
On s’intéresse donc au regret: \(R_m(t) = p_A - \frac{E(G_m(T))}{t}\), car il représente la différence entre l’espérance moyenne de gain sur A (ici la meilleure machine) et l’espérance moyenne de gain de notre stratégie. Ce regret nous permet donc de déterminer si nos stratégies sont efficace ou pas. Le regret doit être le plus faible possible et tendre vers zéro le plus rapidement possible pour que la stratégie soit considérée comme bonne.
Q2) On apprend (un peu) puis on exploite:
Intuitions
Cette stratégie semble efficace, puisque sur beaucoup d’estimations elle tendra à toujours choisir la meilleure machine, mais elle peut être induite en erreur sur la machine la plus prometteuse si le nombre de parties d’estimations est trop faible. Cependant, faire beaucoup de parties d’estimations laisse moins de parties pour profiter de la machine prometteuse (on se rapproche alors de la 3e stratégie de la première question, où on utilise autant les deux machines).
Réponses
#Fonction faisant une série Tmax de parties avec la stratégie mL
strat_mL = function(Tmax=1000,pA=0.65,pB=0.55,ep=0.05){
gainsA = 0
nb_tA = 0
gainsB = 0
nb_tB = 0
regret=c()
#On alterne entre les 2 machines en comptant les succes sur chacune
for (i in 1:(ep*Tmax)) { #On suppose que Tmax est multiple de epsi
if(i%%2==0){
gainsA=gainsA+(runif(n = 1)<=pA)
nb_tA = nb_tA + 1
}else{
gainsB=gainsB+(runif(n = 1)<=pB)
nb_tB = nb_tB + 1
}
regret=c(regret,pA-((gainsA+gainsB)/i))
}
#On détermine la meilleure machine et on en choisit une au hasard en cas d'égalité
if ((gainsA / nb_tA) < (gainsB / nb_tB)) {
p_m_choisie = pB
} else if ((gainsA / nb_tA) > (gainsB / nb_tB)) {
p_m_choisie = pA
} else {
p_m_choisie = ifelse(runif(1) < 0.5, pA, pB)
}
#On calcule les résulats suivants avec la meilleure machine
gains = gainsA + gainsB
for(i in (ep*Tmax+1):Tmax){
gains=gains+(runif(n = 1)<=p_m_choisie)
regret=c(regret,pA-gains/i)
}
return(regret)
}
#Fonction appliquant une stratégie sur N séries de Tmax parties
application_strat = function(strat,N=100,Tmax=1000,pA=0.65,pB=0.55,ep=0.05){
global=data.frame()
for (j in 1:N) {
i = 1:Tmax
#On remplit une dataframe avec le numéro de la série, le numéro de la partie et le regret obtenu
solo_tirage = data.frame(id = j, t = i, G = strat(Tmax,pA,pB,ep))
global= rbind(global,solo_tirage)
}
return(global)
}
#Fonction d'affichage des résultats de l'application d'une stratégie
affichage_strat = function(strat,N=100,Tmax=1000,pA=0.65,pB=0.55,ep=0.05){
results = application_strat(strat,N,Tmax,pA,pB,ep)
results = results %>% group_by(t) %>% mutate(mean_G=mean(G)) #On ajoute une colonne avec la moyenne selon t
#On affiche les séries en noir, la moyenne en rouge et l'ordonnée y=0 en bleu
ggplot(results, aes(x=t, y=G, group(id)))+geom_line(size = 0.3,aes(group=id)) + geom_line(aes(y = mean_G),size = 1, color ="red") + geom_line(aes(y = 0),size = 0.5, color ="blue")
}
affichage_strat(strat = strat_mL)
Cette stratégie semble efficace mais on peut lui trouver une faiblesse.
affichage_strat(strat=strat_mL,Tmax=3000)
On constate clairement qu’une partie des trajectoires a un regret très élevée par rapport aux autres. Toutes ces trajectoires sont celles où notre stratégie n’a pas choisie la bonne machine, engendrant un regret de \(p_A -p_B\) environ sur ces trajectoires. Notre stratégie n’est donc pas très adaptative car si elle commet une erreur sur l’estimation de la machine la plus rentable, elle est incapable de la rectifier.
affichage_strat(strat=strat_mL,ep=0.5)
On constate qu’on peut grandement réduire les trajectoires divergentes en augmentant epsilon.
affichage_strat(strat=strat_mL,ep=0.5,pA=0.75,pB=0.25)
Mais cela n’est effectif que si nos 2 machines ont des probabilités proches. Si ce n’est pas le cas, on obtient un regret très important.
affichage_strat(strat=strat_mL,ep=0.05,pA=0.75,pB=0.25)
Si nos 2 machines ont des probabilités de gains très différentes, il vaut mieux alors mettre un epsilon faible. Malheureusement, on ne connait pas l’écart entre ces probabilités avant d’appliquer notre stratégie.
Cette stratégie pourrait donc être efficace mais demanderait des données et/ou des tirages supplémentaires pour cela.
Q3) On exploite mais on se force à toujours apprendre (un peu):
Intuitions
Cette stratégie a les avantages de la stratégie précédente en contournant ses inconvénients; on affine nos estimations à chaque partie (on tend vers les probabilités exactes des machines). Les premières parties ne seront pas très significatives cependant (soit alternance entre les 2 machines, soit saturation sur une machine suite à de nombreux lancers positifs), avec comme risque de prendre la machine la moins efficace sur les premières parties. De plus, il faudrait étudier à quelle vitesse cette stratégie tend vers les bonnes probabilités de gains.
Réponses
strat_mG = function(Tmax = 1000, pA=0.65, pB=0.55, ep=0.1){
nb_tentatives_A=0
nb_tentatives_B=0
regret=c()
nbsuccesA = 0
nbsuccesB = 0
for(i in 1:Tmax){
#On détermine la machine la plus prometteuse (au hasard si le ratio d'efficacité est le même sur les deux machines)
if ((nbsuccesA/(nb_tentatives_A+1)) == (nbsuccesB/(nb_tentatives_B+1))){
m_choisie = ifelse(runif(1)<0.5,pA,pB)
}else if((nbsuccesA/(nb_tentatives_A+1)) < (nbsuccesB/(nb_tentatives_B+1))){
m_choisie = pB
}else {
m_choisie=pA
}
#On fait un tirage de test: on a 1-epsilon chance de choisir la machine la plus prometteuse sinon on choisit l'autre.
if (runif(1) < ep){
m_choisie=ifelse(m_choisie==pA,pB,pA)
}
#On joue sur la machine sélectionnée
if (m_choisie == pA){
nbsuccesA = nbsuccesA + (runif(1)<pA)
nb_tentatives_A = nb_tentatives_A+1
}
else {
nbsuccesB = nbsuccesB + (runif(1)<pB)
nb_tentatives_B = nb_tentatives_B+1
}
#On calcule le regret à chaque tirage
regret = c(regret,pA - (nbsuccesA+nbsuccesB)/i)
}
return(regret)
}
affichage_strat(strat=strat_mG)
Pour le moment, on ne voit pas de nette différence avec la stratégie précédante. Mais si on augmente Tmax :
affichage_strat(strat=strat_mG, Tmax=3000)
On voit que les trajectoires déviantes se corrigent au fur et à mesures des parties. Ainsi, notre moyenne du regret tend vers 0, alors qu’elle restait assez constante à la stratégie précédante. On constate cependant qu’il reste encore beaucoup de trajectoires avec un fort regret (0.1 environs) durant les 1000 premières parties.
affichage_strat(strat=strat_mG,ep=0.05)
Epsilon représente sur cette stratégie notre confiance dans nos estimations. On pourrait être tenté de le réduire mais cela conduit à l’apparition de davantage de trajectoires déviantes.
affichage_strat(strat=strat_mG,ep=0.4)
A l’inverse, augmenter espsilon supprime ces erreurs d’estimation mais fait perdre en efficacité, on se rapproche alors d’une stratégie de choix aléatoire.
L’efficacité de cette stratégie dépend, comme la précédente, du choix du paramètre epsilon. Elle demeure plus efficace, même si son epsilon est plus complexe à régler.
Q4) On tire au hasard en biaisant selon nos observations
Intuitions
On introduit la vraisemblance pour prendre en compte des résultats sortants de la moyenne, cela complète la méthode précédente, on n’améliore pas la véracité des résultats mais on admet notre incertitude sur nos mesures, ce qui peut conduire à une meilleure convergence.
Réponses
strat_mT = function(Tmax = 1000, pA=0.65, pB=0.55, ep){
regret=c()
nbsuccesA = 0
nbsuccesB = 0
nbfailA = 0
nbfailB = 0
for(i in 1:Tmax){
#Calcul des probabilités estimées des 2 machines selon la loi beta
pA_esti = rbeta(n=1,shape1 = nbsuccesA+1, shape2 = nbfailA+1)
pB_esti = rbeta(n=1,shape1 = nbsuccesB+1, shape2 = nbfailB+1)
#On détermine la machine la plus prometteuse (au hasard si le ratio d'efficacité est le même sur les deux machines)
if (pA_esti == pB_esti){
m_choisie = ifelse(runif(1)<0.5,pA,pB)
}else if(pA_esti < pB_esti){
m_choisie = pB
}else {
m_choisie=pA
}
#On joue sur la machine sélectionnée
if (m_choisie == pA){
if(runif(1)<pA){
nbsuccesA = nbsuccesA +1
}else{
nbfailA = nbfailA +1
}
} else {
if(runif(1)<pB){
nbsuccesB = nbsuccesB +1
}else{
nbfailB = nbfailB +1
}
}
#On calcule le regret à chaque tirage
regret = c(regret,pA - (nbsuccesA+nbsuccesB)/i)
}
return(regret)
}
affichage_strat(strat = strat_mT)
On constate que cette stratégie converge rapidement vers un regret de 0 et semble meilleure que les précédentes sur ce point, et ce sans avoir de paramètre epsilon à ajuster. On remarque les trajectoires sont moins rectilignes que dans les méthodes précédentes, notre stratégie remettant davantage en doute son choix de machine.
affichage_strat(strat=strat_mT, Tmax=3000)
Cette dernière stratégie continue de réduire son regret moyen à chaque partie, en corrigeant ses biais. Malgré nos nombreuses tentatives pour mettre à défaut cette stratégie, elle ne semble pas avoir de faiblesse apparente. On peut supposer que la loi de probabilité Beta est designée pour résoudre ce genre de problème et que cette stratégie est donc la meilleure.
Comparaison finale
On observe bien que la première stratégie garde toujours un groupe de trajectoires déviantes. La dernière stratégie semble la meilleure car ses trajectoires convergent plus rapidement. On remarque aussi, qu’avec assez de parties, le regret de ces 3 stratégies est assez proche.
Ainsi, la stratégie mT semble la plus adaptée pour estimer les probabilités de ces machines, elle converge plus vite et ne nécessite pas le réglage d’un paramètre epsilon.