RICM4 Probabilités et Simulation – Devoir n°1
Mandresy Rakotoarimalala
30 novembre 2018
Q1) Questions préléminaires :
Strategie jouer systematiquement A : \(\mathbb{E}[G_{m,t}]= \sum \limits_{t=0}^T X_{A,t} = T.p_{A}\) \ Strategie jouer systematiquement B : \(\mathbb{E}[G_{m,t}]= \sum \limits_{t=0}^T X_{B,t} = T.p_{B}\) \ Strategie jouer A avec probabilité 1/2 et B avec probabilité 1/2 : \(\mathbb{E}[G_{m,t}]= \sum \limits_{t=0}^T X_{B,t} = T.(p_{A}+p_{B})/2\) \
On s’interesse au regret \(R_m(t)\) car on veut evaluer de combien est ce qu’on s’est trompé en moyenne. La bonne strategie varie selon ce qu’on veut. On peut vouloir minimiser le regret pour ne pas beaucoup “regretter”. Mais, on peut aussi par exemple choisir de regretter un peu mais avoir gagner beaucoup seulement sur une partie du temps. On va choisir la première methode : minimiser le regret.
Le Code :
On fixe un seed au debut et on déclare nos différentes variables
set.seed(5)
library(ggplot2)
Tmax = 1:1000 ## Nb de tirages observés sur les 2 machines
n = 100 ## Nb de repetition de l'experience à 100 tirages (= trajectoire)
pa = 0.65
pb = 0.55Strategie1A c’est la strategie qui consiste à jouer systématiquement la machine A z fois :
strategie1A = function(z){
Xa = rbinom(z, 1, pa)
Xa
tab_r = c()
for (t in z){
Esp_gain = sum(Xa[1:t])
regret = pa - (Esp_gain/t)
tab_r = c(tab_r,regret)
}
myData = data.frame(t = z, r = tab_r)
return(myData)
}
##Affichage du regret pour la strategie qui consiste a jouer systématiquement A
rmt_data = data.frame()
for ( i in 1:n){
rmt_data = rbind(rmt_data, strategie1A(Tmax))
}
print(rmt_data$r[1000])## [1] 0.005 rmt_data_sumr = summary(rmt_data)
rmt_data_sumr## t r
## Min. : 1.0 Min. :-0.350000
## 1st Qu.: 250.8 1st Qu.:-0.019697
## Median : 500.5 Median :-0.001540
## Mean : 500.5 Mean :-0.002181
## 3rd Qu.: 750.2 3rd Qu.: 0.013149
## Max. :1000.0 Max. : 0.650000 ggplot(data = rmt_data, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie 1")+ theme_bw()
Strategie1B c’est la strategie qui consiste à jouer systématiquement la machine B z fois :
strategie1B = function(z){
Xb = rbinom(z, 1, pb)
Xb
tab_r = c()
for (t in z){
Esp_gain = sum(Xb[1:t])
regret = pa - (Esp_gain/t)
tab_r[t] = regret
}
myData = data.frame(t = z, r = tab_r)
return(myData)
}
##Affichage du regret pour la strategie qui consiste a jouer systématiquement B
rmt_data_B = data.frame()
for ( i in 1:n){
rmt_data_B = rbind(rmt_data_B, strategie1B(Tmax))
}
print(rmt_data_B$r[1000])## [1] 0.099 rmt_data_sumr = summary(rmt_data_B)
rmt_data_sumr## t r
## Min. : 1.0 Min. :-0.35000
## 1st Qu.: 250.8 1st Qu.: 0.08243
## Median : 500.5 Median : 0.09654
## Mean : 500.5 Mean : 0.09695
## 3rd Qu.: 750.2 3rd Qu.: 0.11194
## Max. :1000.0 Max. : 0.65000 ggplot(data = rmt_data_B, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie 1 syst B")+ theme_bw()
Strategie1mix c’est la stratégie qui consiste à jouer A avec une probabilité \(1/2\) et B avec une probabilité \(1/2\) En fait c’est comme si on jetait une pièce de monnaie Tmax fois, si on tombe sur pile on joue \(m_{A}\) sinon on joue \(m_{B}\)
m_jouee = sample( c("A","B"), length(Tmax), rep=T, prob=c(1/2,1/2) ) #notre tirage type pile ou face
strategie1mix = function(p_slctA, p_slctB, z,tirage){
X = c()
for(i in 1:length(tirage)){
if(tirage[i]=="A"){
X = c(X, rbinom(1, 1, p_slctA)) #on joue la machine A
#print(X)
}
else{
X = c(X, rbinom(1, 1, p_slctB)) #on joue la machine B
#print(X)
}
}
tab_r = c()
for (t in z){
Esp_gain = sum(X[1:t])
regret = pa - (Esp_gain/t)
tab_r = c(tab_r,regret)
}
myData = data.frame(t = Tmax, r = tab_r)
return(myData)
}
res = strategie1mix(pa,pb,length(Tmax), m_jouee)
#res
length(res$t)## [1] 1000rmt_mix = data.frame()
for ( i in 1:n){
rmt_mix = rbind(rmt_data, strategie1mix(pa,pb,length(Tmax),m_jouee))
}
print(rmt_mix$r[1000])## [1] 0.005summary(rmt_mix)## t r
## Min. : 1.0 Min. :-0.350000
## 1st Qu.: 250.8 1st Qu.:-0.019405
## Median : 500.5 Median :-0.001260
## Mean : 500.5 Mean :-0.001615
## 3rd Qu.: 750.2 3rd Qu.: 0.013636
## Max. :1000.0 Max. : 0.650000ggplot(data = rmt_mix, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie 1/2 A et 1/2 B")+ theme_bw()
On peut deja voir qu’avec cette strategie mixte on a une moyenne de regret de 0.001340 pour les 100 trajectoires. Ce qui est deja assez petit par rapport à une strategie qui consiste à jouer une des deux machines systématiquement.
Q2) On apprend (un peu) puis on exploite
On souhaite consacrer les \(\epsilon\).Tmax première partie à estimer \(P_{a}\) et \(P_{b}\) et jouer systématiquement la machine qui a le plus rapporté pendant cette période d’étude.
strategie_epsilon = function(){
epsilon = 0.05
p_tab_r_A = c()
p_tab_r_B = c()
##On étudie les probas pendant les epsilon.Tmax premier lancés
Xa = rbinom(epsilon*Tmax/2, 1, pa)
Xb = rbinom(epsilon*Tmax/2, 1, pb)
meanA = mean(Xa)
meanB = mean(Xb)
for (t in epsilon*length(Tmax)/2){
Esp_gainA = sum(Xa[1:t])
p_regretA = pa - (Esp_gainA/t)
p_tab_r_A[t] = p_regretA
}
for (t in (epsilon*length(Tmax)/2) ){
Esp_gainB = sum(Xb[1:t])
p_regretB = pa - (Esp_gainB/t)
p_tab_r_B[t] = p_regretB
}
p_tab_r = c(p_tab_r_A, p_tab_r_B)
p_df_r = data.frame(t = 1:epsilon*length(Tmax), r = p_tab_r )
rmt_epsilon = data.frame()
if (meanA > meanB){
#print("Esp_gainA > Esp_gainB")
#print(length(p_df_r$r))
rmt_epsilon = rbind( p_df_r, strategie1A(1:950 ))
#print(length(rmt_epsilon$r))
}
else{
#print("Esp_gainA < Esp_gainB")
rmt_epsilon = rbind( p_df_r, strategie1B(1:950) )
}
return(rmt_epsilon)
}
##Affichage du regret pour la strategie 2
rmt_strategie2 = data.frame()
for ( i in 1:n){
rmt_strategie2 = rbind(rmt_strategie2, strategie_epsilon())
}
print(rmt_strategie2$r[1000])## [1] 0.007894737summary(rmt_strategie2)## t r
## Min. : 1.0 Min. :-0.350
## 1st Qu.: 250.8 1st Qu.:-0.017
## Median : 500.5 Median :-0.002
## Mean : 501.7 Mean :-0.003
## 3rd Qu.: 750.2 3rd Qu.: 0.014
## Max. :1000.0 Max. : 0.650
## NA's :4800ggplot(data = rmt_strategie2, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie 2 avec espilon")+ theme_bw()
Malheuresement, nous n’avons pas trouvé pourquoi nous avons des valeurs absentes, notre graphe n’arrivent pas jusqu’a t=1000 et dans notre summary il est dit qu’il y a 4800 NA’s. Ce qui peut fausser nos calculs. Néanmoins si on considère la moyenne que nous obtenons (ici 0.001), on pourrait dire que cette méthode n’est pas très loin de la première en termes de regret.
Q3) On exploite mais on se force à toujours apprendre (un peu)
On considère maintenant la stratégie \(m_{G}\) : sélectionner avec probabilité \(1 − εˆ\) (avec εˆ = 0.1 par exemple) la machine la plus prometteuse (i.e., celle dont le ratio du “nombre de succès” par le “nombre de tentatives plus un”, est le plus élevé) jusqu’ici et avec probabilité εˆ l’autre machine.
strategie2mix = function(){
epsilon = 0.1
#recherche de la machine la plus prometteuse ie: max (succes/nb tentative+1)
machine = sample( c("A","B"), length(Tmax), rep=T, prob = c(pa,pa))
resA = sum(machine=="A")/(length(Tmax)+1)
resB = sum(machine=="B")/(length(Tmax)+1)
m_promet = max(resA,resB) #indiquera qui est la machine la plus prometteuse
X = c()
for(i in 1:length(machine)){
if(machine[i]=="A"){
X = c(X, rbinom(1, 1, 1-epsilon)) #on joue la machine A
#print(X)
}
else{
X = c(X, rbinom(1, 1, epsilon)) #on joue la machine B
#print(X)
}
}
tab_r = c()
for (t in Tmax){
Esp_gain = sum(X[1:t])
regret = pa - (Esp_gain/t)
tab_r = c(tab_r,regret)
}
myData = data.frame(t = Tmax, r = tab_r)
return(myData)
}
rmt_mix2 = data.frame()
for ( i in 1:n){
rmt_mix2 = rbind(rmt_mix2, strategie2mix())
}
print(rmt_mix2$r[1000])## [1] 0.174summary(rmt_mix2)## t r
## Min. : 1.0 Min. :-0.3500
## 1st Qu.: 250.8 1st Qu.: 0.1285
## Median : 500.5 Median : 0.1463
## Mean : 500.5 Mean : 0.1453
## 3rd Qu.: 750.2 3rd Qu.: 0.1641
## Max. :1000.0 Max. : 0.6500ggplot(data = rmt_mix2, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie avec epsilon chapeau")+ theme_bw()
Q4) On tire au hasard en biaisant selon nos observations
n1=20 ; n2=50 ; plot(function(x) {dbeta(x,shape1=n1+1,shape2=n2+1)})
strategieBeta = function(){
n1a = 0 #gain machine A
n2a = 0 #perte machine A
n1b = 0 #gain machine B
n2b = 0 #perte machine B
X = c()
for(t in Tmax){
real_pa = rbeta(1,n1a,n2a) #on tire sur A aleatoirement suivant la densité beta
print(real_pa)
real_pb = rbeta(1,n1b,n2b) #on tire sur B aleatoirement suivant la densité beta
print(real_pb)
m_promet = max(real_pa, real_pb)
if(m_promet == real_pa){ # cas : machine A plus grande valeur
tir = rbinom(1, 1, real_pa)
X = c(X, tir) #on joue la machine A avec la vraisemblance real_pa
if(tir==1){n1a=n1a+1}else{n2a=n2a+1} # maj du gain et de la perte
}
else{ # cas : machine B plus grande valeur
tir = rbinom(1, 1, real_pb)
X = c(X, tir) #on joue la machine A avec la vraisemblance real_pa
if(tir==1){n1b=n1b+1}else{n2b=n2b+1} # maj du gain et de la perte
}
}
print(X)
tab_r = c()
for (t in Tmax){
Esp_gain = sum(X[1:t])
regret = pa - (Esp_gain/t)
tab_r = c(tab_r,regret)
}
myData = data.frame(t = Tmax, r = tab_r)
return(myData)
}
rmt_beta = data.frame()
for ( i in 1:n){
rmt_beta = rbind(rmt_beta, strategie2mix())
}
print(rmt_beta$r[1000])## [1] 0.163summary(rmt_beta)## t r
## Min. : 1.0 Min. :-0.3500
## 1st Qu.: 250.8 1st Qu.: 0.1366
## Median : 500.5 Median : 0.1512
## Mean : 500.5 Mean : 0.1507
## 3rd Qu.: 750.2 3rd Qu.: 0.1671
## Max. :1000.0 Max. : 0.6500ggplot(data = rmt_beta, aes(x = t, y = r)) + geom_line(alpha = 0.1) + labs(title = "Regret pour la stratégie beta")+ theme_bw()
On a un plus grand regret moyen (ici 0.1492 ) par rapport aux premières stratégies quand on tire au hasard à chaque étape, on pense donc que cette stratégie est donc pas la bonne