• <- Retour aux 1/4h python
    L'objectif des 1/4h python est d'illustrer par la simulation certains aspects du cours. Toutes les fenêtres de code peuvent (et doivent!) être exécutées en cliquant sur Evaluate. N'hésitez pas à éditer le code pour modifier les paramètres.

    Marche aléatoire renforcée

    Nous allons étudier un modèle aléatoire non-markovien le plus simple possible : la marche aléatoire renforcée à 2 états. Ce modèle est à la base d'un algorithme d'apprentissage par renforcement appelé algorithme du bandit1. Il a été également été proposé pour modéliser l'exploration d'un milieu par des insectes sociaux2.



    La fourmi va emprunter le chemin $A$ avec probabilité $\frac{r(3)}{r(1)+r(3)}$.




    Soit $r:\mathbb{N}\to (0,+\infty)$ une fonction telle que $r(x)\geq x$ pour tout $x$, $r$ est appelée la fonction de renforcement.
    On considère la suite de variables aléatoires $(X_k)_{k\geq 1}$ à valeurs dans $\{A,B\}$ définie de la façon suivante. Pour $k\geq 1$, $S^A_k$ désigne le nombre de passages en $A$ :

    $$ S^A_0=0,\qquad S^A_k=\sum_{i=1}^k \mathbf{1}_{X_i=A} \in\{0,1,\dots,k\}. $$

    L'évolution est alors définie par :

    $$ \mathbb{P}(X_{k+1}=A|X_1,\dots,X_k)= \frac{r(S_k)}{r(S_k)+r(k-S_k)}. $$

    Plus la fonction $r$ a de grandes variations, plus la marche est renforcée : la fourmi a une grande tendance à emprunter le chemin majoritaire jusque-là. On cherche à évaluer l'influence de la fonction $r$ sur le renforcement. Nous allons tracer l'évolution de la proportion $\frac{S^A_k}{k}$.

    1. Renforcement linéaire

    On trace $K$ trajectoires de $\frac{S^A_n}{n}$ pour $r$ de la forme $r(x)=a+x$.

    On démontre dans la PC 7 que, pour ce choix de renforcement $r$, $\frac{S^A_n}{n}$ converge presque-sûrement vers une variable aléatoire à densité (si $r(x)=1+x$ cette variable est uniforme sur $[0,1]$).

    2. Renforcement géométrique

    On trace $K$ trajectoires de $\frac{S^A_n}{n}$ pour $r$ de la forme $r(x)=\rho^x$, avec $\rho >1$.

    On peut démontrer que pour $r(x)=\rho^x$, $\frac{S^A_n}{n}$ converge presque-sûrement vers une variable aléatoire qui prend les valeurs $0$ ou $1$ avec probabilité $0.5/0.5$.

    Références

    Liens