Introduction

On fixe au préalable la graine du générateur afin de pouvoir reproduire les données avec exactitude d’un ordinateur à l’autre.

set.seed(seed = 42)

On possède deux machines à sous dont la probabilité de victoire est inconnue: Machine A et Machine B.
Les issues du jeu sont : gagner 0€ ou gagner 1€.
Notre objectif est de maximiser nos gains en appliquant une stratégie de jeu optimale.

Calcul d’espérance

Calcul de \(\mathbb{E}(G_{m}(T))\) pour différentes stratégies basiques :

  1. On joue tout le temps avec \(M_A\)

\(\mathbb{E}(G_{m}(T)) = \mathbb{E}[\sum_{t=1}^TX_{A,t}] = \sum_{t=1}^T\mathbb{E}[X_{A,t}] = \sum_{t=1}^Tp_A = T p_A\)

  1. On joue tout le temps avec \(M_B\)

\(\mathbb{E}(G_{m}(T)) = \mathbb{E}[\sum_{t=1}^TX_{B,t}] = \sum_{t=1}^T\mathbb{E}[X_{B,t}] = \sum_{t=1}^Tp_B = T p_B\)

  1. On joue alternativement avec \(M_A\) et \(M_B\)

\(\mathbb{E}(G_{m}(T)) = \mathbb{E}[\sum_{t=1}^TX_{m(t),t}] = \sum_{t=1}^T\mathbb{E}[\frac{1}{2} X_{B,t} + \frac{1}{2} X_{B,t}] =\sum_{t=1}^T\frac{1}{2} \mathbb{E}[ X_{B,t}] + \frac{1}{2} \mathbb{E}[X_{B,t}] = \sum_{t=1}^T\frac{1}{2}p_A + \frac{1}{2} p_B = \frac{T}{2} (p_A + p_B)\)

Regret

Le regret \(R_{m(t)} = p_A - \frac{\mathbb{E}[G_m(t)]}{t}\) permet de connaître, pour une stratégie donnée, l’écart entre sa probabilité de gain moyen et la probabilité de gains en ne jouant que sur la machine A. Une bonne stratégie serait d’obtenir un regret négatif, c’est-à-dire que notre stratégie est plus performante que celle consistant à ne jouer que sur A. Dans les exemples ci-dessous, on prend \(p_A > p_B\), cela signifie qu’il sera impossible de trouver une stratégie meilleure que celle consistant à ne jouer qu’avec la machine A. On cherchera donc à minimiser au mieux le regret.

Intuition sur les stratégies proposées

Il semble que ce soit une bonne stratégie pour déterminer quelle machine a la meilleure probabilité de victoire. Néanmoins, il faudra trouver un epsilon significatif, ni trop élevé ni trop faible. Par exemple avec un epsilon grand :

tMax = 10000
epsilon = 0.8
nbEssais = epsilon*tMax
print(nbEssais)
## [1] 8000

On passerait 8000 essais sur 10 000 à effectuer des tests afin de déterminer quelle machine utiliser, il ne resterait donc plus beaucoup d’occasions pour appliquer la stratégie la plus efficace.

A l’inverse, si on utilise un epsilon trop petit :

epsilon = 0.01
nbEssais = epsilon*tMax
print(nbEssais)
## [1] 100

On effectuera seulement 100 essais sur 10 000 ce qui n’est pas significatif pour savoir quelle machine est la plus performante (on risque de jouer avec la mauvaise machine jusqu’à la fin en cas de mauvais choix au départ)

Il faudrait ainsi trouver un juste milieu.

La stratégie paraît bonne dans la majorité des cas. On va toujours prendre la machine qui semble avoir la meilleur probabilité de gains à l’instant t. Cependant, une machine avec une meilleure probabilité de gain sera jouée plus souvent, ce qui affinera sa probabilité réelle (loi des grands nombres). Au final, on peut se retrouver avec une probabilité de gains très précise pour une machine et très peu précise pour l’autre (car très peu d’essais réalisés). Le fait de laisser une chance à une machine dont la probabilité estimée est plus faible corrige partiellement ce problème. Le choix du epsilon sera encore une fois très déterminant. Un gros problème de cette stratégie est le cas où les deux probabilités sont très éloignées. En effet, même si l’une des deux machines se démarque par rapport à l’autre, on va continuer à jouer sur la machine dont la probabilité est beaucoup plus faible.

Cette stratégie reprend la logique de la précédente. On va simplement modifier la manière dont on laisse une chance à la machine dont la proba estimée est la plus faible. Au lieu de tirer uniformément et de choisir en fonction d’un pourcentage, on va tirer deux probabilités “vraisemblables” à partir d’une loi bêta. Cela diminue donc le problème que l’on rencontrait précédemment lorsque les valeurs étaient très proches ou très éloignées. En effet, si les valeurs sont très éloignées, les deux courbes en cloche le seront aussi, favorisant la meilleur courbe. Si les valeurs sont très proches, on va quasiment tirer avec une proba 50/50 entre les deux machines.

Implémentation des différentes stratégies

Simulation \(m_A\) : on joue tout le temps avec A

# Will be useful to see how many simulations are needed
# to get a good regret estimation, in this case, it should always be 0
strat_a <- function(pA,tMax){
  regret <- c()
  gains <- 0
  for (i in 1:tMax){
    if (runif(1) < pA){
      gains = gains + 1
    }
    
    regret[i] = pA - gains/i
  }
  
  return(regret)
}

Simulation \(m_L\)

strat_ml <- function(pA, pB, tMax, epsi) {
  
  regret <- c()
  
  # Time to learn
  learnT <- floor(epsi*tMax)
  
  # Playing on each machine alternatively
  gainsA <- 0 # Number of success with A
  gainsB <- 0 # Number of success with B
  for (i in 1:learnT){
    if (i %% 2){
      if (runif(1) < pA) { # Playing with A
        gainsA <- gainsA + 1
      }
    } else {
      if (runif(1) < pB) { # Playing with B
        gainsB <- gainsB + 1
      }
    }
    regret[i] <- (pA - (gainsA + gainsB) / i) # Regret is calculated on the go
  }
  
  
  #Which Machine seems to have the best success ?
  if (gainsA > gainsB) {
    pC <- pA # Playing with A for the remaining rounds
  } else {
    pC <- pB # Playing with B for the remaining rounds
  }
  
  #Playing on the best machine for the remaining rounds
  gainsC <- 0
  for (i in (learnT + 1):(tMax)) {
    if (runif(1) < pC) {
      gainsC <- gainsC + 1
    }
    regret[i] <- (pA - (gainsA + gainsB + gainsC) / i)  # Regret is calculated on the go
  }
  
  return(regret)
}

Simulation \(m_G\)

strat_mg <- function(pA,pB,tMax,epsi){
  
  regret <- c()
  
  n1A <- 0 # Number of success of machine A
  n1B <- 0 # Number of loss by machine A
  
  n2A <- 0 # Number of success of machine A
  n2B <- 0 # Number of loss by machine B
  
  # Choosing the first machine which will play (50%/50%)
  if (runif(1) < 0.5){
    m <- 'A' # A will play first
  } else {
    m <- 'B' # B will play first
  }
  
  gains <- 0 # Total number of success
  for (t in 1:tMax){
    
    p = runif(1) # 
    
    # Playing with machine A
    if (m == 'A'){
      
      if (p < pA){
        n1A <- n1A + 1;  # Success on A
      } else {
        n2A <- n2A + 1;    # Loss on A
      }
      
    # Playing with machine B
    } else {
      if (p < pB){
        n1B <- n1B + 1;  # Success on B
      } else {
        n2B <- n2B + 1;   # Loss on B
      }
    }
    
    regret[t] <- pA - (n1A + n1B)/t # Calculating regret on the go
    
    #Choosing the machine for the next round
    if ((n1A/(n1A+n2A+1)) == (n1B/(n1B + n2B+1))){ # Equality
      
      if(runif(1) < 0.5){ # We choose randomly and impartially on of the machine
        m <- 'A'
      } else {
        m <- 'B'
      }
      
    } else if((n1A/(n1A+n2A+1)) > (n1B/(n1B + n2B+1))){ #  A has better estimated probability than B
      m <- 'A'
    } else { # B has better estimated probability than A
      m <- 'B'
    }
    
    
    # We toggle the machine for the next round
    # if the epsi is triggered
    if (runif(1) < epsi){
      if (m == 'A'){
        m = 'B'
      } else {
        m = 'A'
      }
    }
  }
  
  return(regret)
}

Simulation \(m_T\)

strat_mt <- function(pA,pB,tMax){
  regret <- c()
  
  n1A <- 0 # Number of success of machine A
  n1B <- 0 # Number of loss by machine A
  
  n2A <- 0 # Number of success of machine A
  n2B <- 0 # Number of loss by machine B
  
  # Choosing the first machine which will play (50%/50%)
  if (runif(1) < 0.5){
    m <- 'A' # A will play first
  } else {
    m <- 'B' # B will play first
  }
  
  for (t in 1:tMax){
    
    p = runif(1)
    # Playing with A
    if (m == 'A'){
      
      if (p < pA){
        n1A <- n1A + 1; # Success on A
      } else {
        n2A <- n2A + 1; # Loss on A
      } 
      
    # Playing with B
    } else { # (m == 'B')
      if (p < pB){
        n1B <- n1B + 1; # Success on B
      } else {
        n2B <- n2B + 1; # Loss on B
      }
    }
    
    regret[t] <- pA - (n1A + n1B)/t # Calculating regret on the go
    
    #Choosing the machine for the next round
    vpA = rbeta(1,n1A+1,n2A+1); # Get randomly generated probability from machine A beta law
    vpB = rbeta(1,n1B+1,n2B+1); # Get randomly generated probability from machine B beta law
    
    # We play the machine who got the best estimated probability
    if (vpA > vpB){
      m = 'A'
    } else {
      m = 'B'
    }
  }
  
  
  return(regret)
}

Résultat des simulations

La simulation est réalisée pour \(T\) allant de 0 à 1000.
On estime l’espérance à partir de \(N = 100\) trajectoires.

# Constant Values definition
N = 100  # Number of simulation
tMax = 1000  # Simulation time
epsi_l = 0.2 # Value of epsilon for strategy mL
epsi_g = 0.1 # Value of espilon for strategy mG

pA = 0.65 # Success probability of machine A
pB = 0.55 # Success probability of machine B

df <- data.frame() # Data frame for storing simulation results

for (i in 1:N){

  
  col1 <- data.frame(time = c(1:tMax)) # Simulation Time
  col2 <- data.frame(nosim = seq.int(i,i,length.out = tMax)) # Simulation number
  
  col3 <- data.frame(regretL = strat_ml(pA,pB,tMax,epsi_l)) # Strategy mL
  col4 <- data.frame(regretG = strat_mg(pA,pB,tMax,epsi_g)) # Strategy mG
  col5 <- data.frame(regretT = strat_mt(pA,pB,tMax)) # Strategy mT
  
  col6 <- data.frame(regretA = strat_a(pA,tMax)) # Strategy mA (For reference)
  
  df <- rbind(df, cbind(col1,col2,col3,col4,col5,col6)) # Adding the simulation to the dataframe
  

}


  #Calculating the mean of each strategy
  df <- rbind(df,(df %>% group_by(time) %>% select(time,regretL,regretG,regretT,regretA) %>% summarise(nosim = N+1,regretL = mean(regretL),regretG = mean(regretG), regretT = mean(regretT),regretA = mean(regretA))))
Stratégie \(m_A\)
#
ggplot(data = subset(df, nosim != N+1), aes(x = time, y = regretA, group = nosim, color = nosim)) + scale_colour_continuous(guide = FALSE) + geom_line(size = 0.5) + geom_line(data = subset(df,nosim == N+1), color = "red",size = 1.0) + xlab("t") + ylab("Regret Stratégie mA")

Le tracé de la stratégie \(m_A\) permet de vérifier si les N simulations permettent d’obtenir une estimation statisfaisant du regret.
Ici on cherche à obtenir un regret nul, puisqu’on ne joue qu’avec la machine A dont la probabilité de gain est également notre référence pour calculer le regret.
On peut voir que la moyenne du regret converge assez vite vers 0. Après le 100ème tour, la courbe reste très proche de la valeur nulle.
On va donc conclure que les N=100 simulations donnent une estimation suffisamment précise pour être utilisées dans cette simulation.

Pour la stratégie \(m_L\), on fixe \(epsilon=0.2\)
Pour la stratégie \(m_G\), on fixe \(epsilon=0.1\)

Stratégie \(m_L\)
#
ggplot(data = subset(df, nosim != N+1), aes(x = time, y = regretL, group = nosim, color = nosim)) + scale_colour_continuous(guide = FALSE) + geom_line(size = 0.5) + geom_line(data = subset(df,nosim == N+1), color = "red",size = 1.0) + xlab("t") + ylab("Regret Stratégie mL")

Stratégie \(m_G\)
#
ggplot(data = subset(df, nosim != N+1), aes(x = time, y = regretG, group = nosim, color = nosim)) + scale_colour_continuous(guide = FALSE) + geom_line(size = 0.5) + geom_line(data = subset(df,nosim == N+1), color = "red",size = 1.0) + xlab("t") + ylab("Regret Stratégie mG")

Stratégie \(m_T\)
#
ggplot(data = subset(df, nosim != N+1), aes(x = time, y = regretT, group = nosim, color = nosim)) + scale_colour_continuous(guide = FALSE) + geom_line(size = 0.5) + geom_line(data = subset(df,nosim == N+1), color = "red",size = 1.0) + xlab("t") + ylab("Regret Stratégie mT")

Conclusion sur les différentes stratégies

À première vue, les graphiques de regret des stratégies \(m_L\), \(m_G\) et \(m_T\) sont assez similaires. Néanmoins, si on regarde attentivement on peut distinguer certaines différences.