1  Amélioration des coûts d'une chaîne de Markov

Ecrire un programme (en C, C++ ou java) qui lit les informations sur deux chaînes de Markov sur les mêmes états, décide laquelle parmi les deux a les moindres coûts asymptotiquement, et détermine si une politique mixte serait meilleur encore.

2  Date d'échéance

3  Coefficient

4   Il faut

1. Lire les matrices de probabilités de transition et de coûts pour les deux chaînes (exemple du format en proj.dat mais le vrai fichier n'aura pas de commentaires)
2. calculer les coûts asymptotiques (les v_i du cours) en utilisant actualisation avec un taux ρ de 0.95
3. afficher ces coûts
4. décider si les coûts de la meilleure des deux chaînes (c'est-à-dire la meilleure selon le v de l'état de départ qui est le premier état) pourraient être améliorés en changeant la stratégie d'un ou plusieurs états à celle de l'autre chaîne.

5  Facultativement

1. Trouver la politique mixte optimale (une politique mixte veut dire une politique qui utilise, pour chaque état, la stratégie de l'une des deux chaînes.
   (vous utiliserez, bien sûr, l'algorithme d'améliorations successives de la politique plutôt qu'un algorithme de recherche brute.)

6  Vous pouvez

1. supposer que toute politique a une chaîne avec une seule classe finale et que cette classe ne sera jamais périodique;
2. utiliser des programmes d'analyse des états d'une chaîne ou de résolution d'un système d'équations linéaires vus en TD.

7  A rendre par mail