Résolution de l'équation de Bellman : préliminaires

Nous allons manipuler des problèmes de décision de Markov et implanter plusieurs algorithmes. Il est utile de définir une structure de données en C, une classe en python, qui permettent de les représenter.

Dans cette UE, un PDM est défini par un quituplet : \( ({\cal S}, {\cal A}, {\cal P}, {\cal R}, \gamma) \), où :

• \( {\cal S} \) est l'ensemble des états que l'on considère discret. Dans l'implantation, les états sont numérotés à l'aide d'entiers naturels, à partir de 0. Il y a N états, donc ils sont numérotés de 0 à N-1.
• \( {\cal A} \) est l'ensemble des actions que l'on considère discret. Dans l'implantation, les actions sont numérotées à l'aide d'entiers naturels, à partir de 0. Il y a M actions, donc elles sont nuémrotées de 0 à M-1.
• \( {\cal P} \) est la fonction de transitions, donc un tableau à \( N\times{}M\times{}N \) entrées.
• \( {\cal R} \) est la fonction de retour, donc un tableau à \( N\times{}M\times{}N \) entrées.
• \( \gamma \) est un réel compris dans \( [0, 1[ \).

Il est pratique de pouvoir lire la fonction de transition et la fonction de retour depuis un fichier. S'il y a N états et M actions, ce fichier aura cette structure :

• NxM lignes contenant chacune N nombres : la ligne 1 contient \( {\cal P} (e_0, a_0, e_0) {\cal P} (e_0, a_0, e_1) ... {\cal P} (e_0, a_0, e_{N-1}) \),
  la ligne 2 contient \( {\cal P} (e_0, a_1, e_0) {\cal P} (e_0, a_1, e_1) ... {\cal P} (e_0, a_1, e_{N-1})) \),
  ...
  la ligne N contient \( {\cal P} (e_0, a_{M-1}, e_0) {\cal P} (e_0, a_{M-1}, e_1) ... {\cal P} (e_0, a_{M-1}, e_{N-1}) \), etc. jusque la NxM^è ligne qui contient
  \( {\cal P} (e_{N-1}, a_{M-1}, e_0) {\cal P} (e_{N-1}, a_{M-1}, e_1) ... {\cal P} (e_{N-1}, a_{M-1}, e_{N-1}) \).
  Si une action est impossible dans un état, alors la ligne contient N 0.
  Une ligne est une distribution de probabilités. Aussi, une ligne ne contient que des nombres positifs et la somme vaut 1 (sauf si l'action est impossible auquel cas toutes les valeurs sur la ligne sont 0). Il faut vérifier que c'est bien le cas car des erreurs dues à des approximations numériques peuvent se glisser. Ainsi, s'il y 3 états suivants et que la probabilité d'atteindre chacun est 1/3, ce 1/3 va se transformer en 0.333333. Or, 3x0.333333 ne fait pas 1. Une bonne manière de résoudre ce problème est de forcer \( {\cal P} (e_k, a_l, e_{N-1}) \) à prendre la valeur \( 1 - \sum_{j=0}^{j=N-2} {\cal P} (e_k, a_l, e_j) \).
• suivies de NxM lignes contenant chacune N nombres selon l'exacte même structure. Là encore, si une action est impossible dans un état, alors la ligne contient N 0.

Pour le problème du chauffeur de taxi, le fichier contiendra ce qui suit :

0.5    0.25   0.25
0.0625 0.75   0.1875
0.25   0.125  0.625
0.5    0      0.5
0      0      0
0.0625 0.875  0.0625
0.25   0.25   0.5
0.125  0.75   0.125
0.75   0.0625 0.1875

10  4  8 
 8  2  4 
 4  6  4 
14  0 18 
 0  0  0 
 8 16  8 
10  2  8 
 6  4  2 
 4  0  8

On voit que l'action \( a_1 \) est impossible dans l'état \( e_1 \).

À faire :

1. Définir les structures de données en C, classe en python, qui permettent de représenter un problème de décision de Markov, ansi qu'une politique déterministe ou stochastique.
   Une politique déterministe est un tableau de N entiers naturels (l'action associée à chaque état).
   Une politique stochastique est un tableau de NxM réels (compris entre 0 et 1) : \( \pi (e, a) \) est la probabilité d'émettre l'action \( a \) dans l'état \( e \), donc comprise entre 0 et 1. \( \pi (e, .) \) est une distribution de probabilités, donc \( \sum_{a=0}^{a=M-1} \pi (e, a) = 1 \forall e \).
   En C, c'est l'occasion d'utiliser une union (dans une struct).
2. Définir les fonctions nécessaires à la lecture de la fonction de transition et la fonction de retour depuis un fichier structuré comme indiqué ci-dessus. Le nombre d'états, le nombre d'actions et le facteur de décompte sont fournis par ailleurs.
3. Définir une fonction qui simule une trajectoire dans un problème de décision de Markov et renvoie \( \sum_k \gamma^k r_{t+k} \). La trajectoire est interrompue après un nombre de transitions fourni en paramètre à la fonction ou quand \( \gamma^k \) est inférieur à un seuil fourni en paramètre.