RICM4 PS

Quelques remarques générales:

  • Beaucoup d'entre vous donnent des explications vraiment pas claires pour ce qui est du calcul de l'espérance du gain de la stratégie mixte. Je le réécris donc proprement: Dans cette stratégie, on tire la machine $M_t$ à pile ou face. Autrement dit, $P[M_t==A]=0.5$ et $P[M_t==B]=0.5$. Du coup, $P[X_{M_t,t}=1] = P[M_t=A].P[X_{A,t}=1] + P[M_t=B].P[X_{B,t}=1] = 0.5 p_A + 0.5 p_B$. De même, on obtient $P[X_{M_t,t}=0] = 1-0.5(p_A+p_B)$. C'est ce qu'on appelle la loi (la probabilité de chaque valeur) de $X_{M_t,t}$ et on en déduit que l'espérance de $X_{M_t,t}$ est $E[X_{M_t,t}=0] = 0.5(p_A+p_B)$.

Le gain cumulé est $G(T) = \sum_{t=1}^T X_{M_t,t}$ et on en déduit son espérance: $E[G(T)] = E[\sum_{t=1}^T X_{M_t,t}] = \sum_{t=1}^T E[X_{M_t,t}] = T/2.(p_A+p_B)$.

  • Autre petite remarque pour ceux qui auraient calculé le regret avec une boucle for. Il y a plus "élégant". Si X est le tableau du gain de la machine jouée aux étapes 1 à T, il suffit d'écrire: R=cumsum(X)/(1:T). Je vous renvoie à mes explications rapides sur le DM pour une mise en œuvre concise.

  • Lorsque l'on joue une machine fixe $M$, notre gain moyen (le gain cumulé divisé par T) est une variable aléatoire dont la loi est concentrée autour de $p_M$. En fait, il est facile de montrer que l'espérance du gain moyen est alors exactement $p_M$.

  • Si $A$ est la meilleur machine, jouer systématiquement est la meilleur stratégie et l'espérance de son gain moyen est donc $p_A$. Toute autre stratégie aura une espérance de gain moyen d'une stratégie plus basse et le regret mesure donc la différence avec celui de la stratégie optimale. Le regret est donc forcément positif (à moins de déjà connaître la meilleur stratégie bien sûr) et une bonne stratégie est une stratégie dont le regret à l'étape $T$ tend vers 0 quand $T$ tend vers l'infini.

  • Ainsi, si on considère la stratégie qui joue systématiquement la machine $B$, on a un regret de $p_B-p_A>0$. Si on joue aléatoirement avec même probabilité (ou si on alterne systématiquement) entre la machine $A$ et la machine $B$, on aura un regret de $(p_B-p_A)/2$. Et si on joue une fois sur 10 sur la machine $B$, on on aura un regret de $(p_B-p_A)/10>0$. Toute stratégie qui joue "trop" sur la machine B aura un regret qui tendra vers une valeur strictement positive.

  • Comme la plupart d'entre vous l'ont remarqué, la stratégie $m_L$ qui apprend pendant $\epsilon.T$ étapes puis joue systématiquement sur la machine qui semble la meilleur, conduit à deux types de trajectoires: celles (nombreuses) qui sélectionnent $A$ et tirent le regret vers 0, et celles (peu nombreuses mais significatives, surtout si la phase d'exploration est courte) qui sélectionnent $B$ et tirent le regret vers une valeur non nulle. Cette stratégie ne peut donc être optimale. En fait, toute stratégie qui ne jouerait $B$ qu'un nombre fini de fois ne peut être certaine d'avoir identifié la meilleur machine. Il faut donc jouer chaque machine une infinité de fois mais pas trop souvent la mauvaise machine car elle augmente le regret.

  • La stratégie $m_G$ qui joue gloutonnement mais continue à essayer de temps en temps l'autre machine a la bonne propriété que l'estimation de la probabilité de gain des deux machine s'améliore bien au cours du temps (puisque les deux machines vont être jouées une infinité de fois). Seulement en continuant à jouer avec proba $\epsilon$ l'autre machine, le regret ne pourra jamais dépasser $\epsilon(p_A-p_B)>0$. Cette stratégie ne peut être optimale.

  • La dernière stratégie (échantillonnage dit «de Thompson», qui utilise la loi beta) permet de jouer une infinité de fois chaque machine (et ainsi d'affiner les estimations des probabilité de gain de chaque machine) mais joue bien plus fréquemment la machine la plus prometteuse d'où un regret qui va tendre vers 0 quand $T$ tend vers l'infini. Comme certains l'ont remarqué, l'ensemble des trajectoire est également bien plus stable que pour les stratégies précédentes.