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

Dans ce TP, on s'intéresse à la résolution de l'équation d'optimalité de Bellman selon différentes méthodes vues en cours, ce qui correspond au chapitre 3 du polycopié de cours.

Itération sur les politiques

Implantation de l'algorithme

Implanter l'algorithme d'itération sur les politiques vu en cours.

Expérimentation avec l'algorithme

Tester votre implantation sur le problème du chauffeur de taxi.
Résoudre le problème du 21-avec-un-dé.

Influence de γ

Déterminer la politique optimale pour « toutes » les valeurs de γ. Déterminer les valeurs de γ auxquelles la politique optimale change.

(Bien sûr, on ne peut pas calculer la politique optimale pour toutes les valeurs de γ entre 0 et 1. On les énumère par exemple avec un pas d'1/100è.)

Itération sur la valeur

Implantation de l'algorithme

Implanter l'algorithme d'itération sur la valeur vu en cours.

Expérimentation avec l'algorithme

Tester votre implantation sur le problème du chauffeur de taxi.
Résoudre le problème du 21-avec-un-dé.

Résolution par programmation linéaire

Implanter la résolution d'un problème de décision de Markov par programmation linéaire.

La tester sur le problème du chauffeur de taxi et sur le problème du 21-avec-un-dé. Retrouvez-vous les mêmes politiques optimales que par la méthode d'itération sur les politiques ?

C

On utilise la bibliothèque glpk pour résoudre un programme linéaire. Elle est installée sur les ordinateurs en salle TP. Sur votre ordinateur personnel, il faut peut-être l'installer. Sous Ubuntu, la documentation est dans le fichier /usr/share/doc/glpk-doc/glpk.pdf.

Python

On utilise la bibliothèque PuLP. Si import pulp ne fonctionne pas, faites un pip3 install pulp et ça fonctionnera.

Une courte introduction à l'utilisation de PuLP pour résoudre un programme linéaire.
On considère le petit problème vu en cours et qui est décrit dans l'annexe D du polycopié. On le résout à l'aide du code ci-dessous : 

import numpy as np
import pulp

N = 2 # nombre de variables
x = pulp.LpVariable.dicts ("x", (range (N))) # les variables
prob = pulp.LpProblem ("exemple", pulp.LpMaximize)

# on définit la fonction objectif
prob += sum ([x [i] for i in range (N)])

# on définit les contraintes
prob += x [0] + 2 * x [1] <= 4
prob += 4 * x [0] + 2 * x [1] <= 12
prob += - x [0] + x [1] <= 1

#on résout le PL
prob. solve ()
solution = np. zeros (N)

# on affiche la solution
print ("Solution du primal :")
for i in range (N):
    solution [i] = x [i]. varValue
    print (solution [i])

solution_dual = np.zeros ((N, 3))
s = 0
a = 0
M = 3 # nombre de contraintes
print ("solution du dual")
for name, c in list(prob.constraints.items()):
    print (c. pi)