Processing math: 100%
  • <- 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é r(3)r(1)+r(3).




    Soit r:N(0,+) une fonction telle que r(x)x pour tout x, r est appelée la fonction de renforcement.
    On considère la suite de variables aléatoires (Xk)k1 à valeurs dans {A,B} définie de la façon suivante. Pour k1, SAk désigne le nombre de passages en A :

    SA0=0,SAk=ki=11Xi=A{0,1,,k}.

    L'évolution est alors définie par :

    P(Xk+1=A|X1,,Xk)=r(Sk)r(Sk)+r(kSk).

    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 SAkk.

    1. Renforcement linéaire

    On trace K trajectoires de SAnn pour r de la forme r(x)=a+x.

    On démontre dans la PC 7 que, pour ce choix de renforcement r, SAnn 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 SAnn pour r de la forme r(x)=ρx, avec ρ>1.

    On peut démontrer que pour r(x)=ρx, SAnn 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