Résolution de l'équation de Bellman : évaluation d'une politique

Dans ce TP, on s'intéresse à la résolution de l'équation de Bellman selon deux méthodes vues en cours, ce qui correspond au chapitre 2 du polycopié de cours. Il ne faut pas oublier ce que l'on a vu dant le 1er TP. Le TP précédent doit impérativement avoir été fait avant celui-ci.

On voit successivement :

1. résolution de l'équation de Bellman par algèbre linéaire,
2. itération sur l'équation de Bellman.

Outre l'implantation de ces méthodes, l'objectif est de les comparer. Pour les programmeurs C (python peut-être aussi), il est intéressant d'essayer d'optimiser l'algorithme. Entre une implantation naïve et une autre plus maligne, on peut accélérer les calculs grandement (facteur de plusieurs dizaines, voire 100, possible en C).

Il est très pratique que vos programmes prennent en argument de ligne de commande le nombre d'états, le nombre d'actions, le facteur de décompte γ, et le nom du fichier qui contient la fonction de transition et la fonction de retour. Bien entendu, d'autres arguments pertinents peuvent être passés sur la ligne de commande, selon l'algorithme qui est utilisé.

Calcul de la fonction valeur par algèbre linéaire

À faire :

1. écrire un programme qui calcule la valeur d'une politique par résolution du système d'équations linéaires et affiche le résultat sur stdout (l'écran du terminal). Il s'agit de mettre en œuvre ce qui a été vu en cours et qui est expliqué en section 2.9, pages 12 et 13 du poly. Faire en sorte que votre programme puisse calculer la valeur d'une politique déterministe ou stochastique. Vous spécifiez la politique comme bon vous semble (a priori, dans un fichier, selon un format que je vous laisse définir).
   
   
   C

   En C, vous utilisez les fonctions d'algèbre linéaire de la GSL qui résolvent un système d'équations linéaires.
   Pour le type de systèmes d'équations linéaires que nous devons résoudre, la méthode passant par une décomposition LU convient parfaitement. Si on note \( A x = b \) le système à résoudre, où \( A \) est une matrice \( N\times{}N \), \( b \in \mathbb{N} \) sont connus et \( x \in \mathbb{N} \) inconnu, on commence par effectuer la décomposition LU de la matrice \( A \) avec la fonction gsl_linalg_LU_decomp (). Ensuite, on résout le système d'équations linéaires avec la fonction gsl_linalg_LU_solve ().

   Python

   En python, on résout un système d'équations linéaires comme celui-ci avec la fonction numpy.linalg.solve ().

   
   
   
   
   
   
   
   
   
2. Tester le programme sur le problème du chauffeur de taxi. On prendra γ = 0,9.

Calcul de la fonction valeur par itération de l'équation de Bellman

À faire :

1. écrire un programme qui calcule la valeur d'une politique en itérant l'équation de Bellman et affiche le résultat sur stdout (l'écran du terminal). Il s'agit de mettre en œuvre ce qui a été vu en cours et est expliqué en section 3.1 du poly. Là encore, faire en sorte que votre programme puisse calculer la valeur d'une politique déterministe ou stochastique.
2. Tester le programme sur le problème du chauffeur de taxi. On prendra γ = 0,9 et on itère pour obtenir une précision de 10^-6.
3. Comparer la valeur estimée par cette méthode avec celle calculée par la précédente.
4. D'après vous, laquelle de ces deux méthodes est la plus précise ?

Mise en œuvre

Taxi

Calculer la valeur de toutes les politiques déterministes pour le problème du chauffeur de taxi (pour γ = 0,9). Reproduire la figure 3 du poly.

21 avec un dé

Évaluer une politique uniformément aléatoire pour le 21-avec-un-dé par les deux méthodes.

Vitesse de convergence de la méthode itérant sur l'équation de Bellman

Pour le problème du chauffeur de taxi et le 21-avec-un-dé, déterminer le nombre d'itérations nécessaires pour l'obtention d'une certaine précision. On le fera pour les puissances de 10 allant de -1 à -7.

Pour le chauffeur de taxi, étudier l'influence de la valeur de γ sur ce nombre d'itérations. On prendra \( \gamma \in \{ 0.1, 0.25, 0.5, 0.75 \} \).

Comparaison expérimentales des deux approches sur des PDM artificiels

On effectue une petite expérimentation pour étudier comment le temps d'exécution de ces 2 méthodes évolue en fonction de la taille du PDM.

1. Écrire une fonction qui génère des PDM aléatoires dont on a juste spécifier le nombre d'états et le nombre d'actions (N et M).
2. Passage à l'échelle : on étudie comment le temps d'exécution varie en fonction de la taille du PDM. Pour cela, vous énumerérez les valeurs N=10, N=100, N=200 et pour chacune de ces valeurs, vous énumérez pour M les valeurs 2, 5, N/10 (quand cela a un sens en fonction de N). Pour chaque couple, vous réalisez 10 expériences en générant un problème de cette taille et en le résolvant. Vous mesurez le temps d'exécution de la résolution et vous en faites un graphique.
   Vous faitez cela pour les 2 algorithmes vus précédemment.

Activité libre (vivement recommendée) : estimation de la valeur par la méthode de Monte Carlo

De manière générale, une méthode de Monte Carlo consiste à estimer une ou des quantités en simulant la dynamique d'un système. Quand la dynamique est stochastique, on effectue plusieurs simulations dont on moyenne les résultats.
On peut appliquer ce principe à l'estimation de la valeur d'une politique. Pour cela, on estime la valeur en chaque état en simulant la dynamique à partir de cet état et en calculant \( R (e_{t=0}) = \sum_k \gamma^k r_k \), les \( r_k \) étant observés le long de la trajectoire. En simulant plusieurs trajectoires issues du même état \( e_{t=0} \) et en moyennant ces \( R (e_{t=0}) \), on estime la valeur de cet état. On effectue ce même traitement à partir de chacun des états et on obtient une estimation de la valeur de la politique.

À faire :

1. écrire un programme qui calcule la valeur d'une politique par une approche de Monte Carlo et affiche le résultat sur stdout. Étudiez comment la précision de l'estimation de la valeur des états varie en fonction du nombre de trajectoires simulées (pour cela, utiliser l'estimation de la fonction valeur obtenue par l'une des deux méthodes précédentes).
2. Tester le programme sur le problème du chauffeur de taxi. Faire varier le nombre de simulations et observer l'écart entre les valeurs estimées par les deux méthodes précédentes et celle-ci (cf. TP 1).