TP 1 : Du planning au reinforcement learning
[Link]@[Link]
10 octobre 2011
L’objectif de ce TP est de vous familiariser avec la résolution d’un problème de
plannification (ou planning) dans un MDP : c’est à dire la résolution d’un MDP
(pour un certain critère) dont on connait les paramètres via les algorithmes IP et
IV vus en cours. On verra également des premiers algorithmes d’apprentissage
par renforcement qui visent à maximiser sa récompense dans un MDP où les
paramètres sont inconnus.
1 Algorithmes IP et IV pour le problème du plan-
ning
1. Une notion utile est celle de Q-valeur d’une politique pour un couple
état,action (x,a) :
X
Qπ (x, a) = r(x, a) + p(y|x, a)V π (y)
y∈X
Ecrire une formulation de l’algorithme d’itération sur les politiques avec
la notion de Q-valeur
2. On définit une politique “greedy” ou gloutonne par rapport à une fonction
valeur comme π = greedy(V ) ssi T π V = T V . Montrez que l’on peut
réécrire ainsi les algorithmes IV et IP :
VI : πk+1 = greedy(Vk ) Vk+1 = T πk+1 Vk .
πk ∞
PI : Vk = (T ) Vk−1 πk+1 = greedy(Vk ).
2 Un problème de gestion de stock
Le but de cette partie est de résoudre un problème de contrôle le stock en le
modélisant par un MDP. Un vendeur de machines à laver cherche à optimiser
son profit. Le cadre est le suivant :
– on note Xt le nombre de machines à laver qu’il détient dans son magasin à la
fin de la semaine numéro numéro t ;
– au maximum, il peut stocker M machines ; mais chaque semaine, le coût
d’entretien et de lavage de chaque machine est de h ;
1
– il peut acheter At machines au prix unitaire c : il les reçoit alors au début de
la semaine suivante ; les frais de livraison sont de K quel que soit le nombre
de machines livrées, sauf bien sûr si At = 0 ;
– il vend ses machines au prix p ; le nombre de clients au cours de la semaine t
est une variable aléatoire Dt , et on suppose que la suite (Dt )t≥1 est i.i.d.
– on note Rt son chiffre d’affaire sur la semaine t ;
– on suppose qu’au temps initial t = 1, son stock est plein : X1 = M ;
– soit γ ∈]0, 1[ tel que le taux d’inflation par semaine soit égal à γ −1 − 1 :
on suppose donc que le vendeur cherche à maximiser en espérance son profit
actualisé
hX∞ i
E γ t Rt+1
t=0
On pourra prendre pour les simulations, par exemple : M = 15, K = 0.8,
c = 0.5, h = 0.3, p = 1, et pour la distribution de Dt une loi géométrique de
paramètre 0.1.
Le dossier ’Gestion de stock’ contient une partie des fonctions utiles. Le fichier
Matlab ’Fil rouge.m’ contient le modèle ci-dessus et les différentes étapes du
TP.
Simulations de trajectoires et estimation de leur fonction
valeur
1. Montrer que
Xt+1 = (Xt + At ) ∧ M − Dt+1
+
Rt+1 = −KI(At >0) − c (Xt + At ) ∧ M − Xt − hXt + p Dt+1 ∧ (Xt + At ) ∧ M
+
2. Une politique π est représenté par un vecteur ligne de taille M + 1, où
π(1 + k) donne le nombre de machines acheté par le vendeur si le stock
est k. Écrire une fonction
[X,R] = trajectoire(n,x0,pi,D,M,K,h,c,pr)
qui simule l’évolution du stock et du profit sur n semaines selon une poli-
tique pi en partant d’un nombre initial x0 de machines.
3. Estimer l’espérance du profit discounté à l’aide d’un grand nombre de
simulations (estimation de Monte-Carlo de la fonction valeur de cette po-
litique) Comment évalue le profit par exemple quand le vendeur achète 2
machines chaque semaine ?
On pourra se servir des fonctions 0 simu.m0 qui simule une loi à support fini sur
[0, M ] et 0 N ewstate.m0 , 0 Reward.m0 .
2
Paramètres du MDP
Pour chaque (x, y, a) ∈ {0, . . . , M }3 , calculer P (Xt+1 = y|Xt = x, At = a) ainsi
que E[Rt+1 |Xt = x, At = a] et écrire une fonction
[P,R] = MDP(D,M,K,h,c,pr)
qui aux paramètres du problème associe la matrice de transition P (x, y, a) =
p(y|x, a) et la matrice de récompense immédiate R(x, a) = E[R|x, a].
Evaluation d’une politique
Quelle sont les différentes manières de calculer la fonction valeur V π d’une
politique donnée π ? Pour plusieurs de ces méthodes, écrire une fonction
[V] = pol_eval(pol,P,R,M,gamma)
qui évalue la politique pol. Quel est l’avantage de l’estimation par une méthode
de Monte-Carlo ?
Que peut espérer gagner le vendeur qui achète chaque semaine deux machines ?
Itération sur les valeurs, Itération sur les politiques
1. Programmer l’algorithme d’itération sur les valeurs pour trouver la stra-
tégie optimale pour le vendeur.
[V, pol] = IV(P,R,gamma,V0,nb_it)
2. Programmer l’algorithme d’itération sur les politiques, avec différentes
manières d’évaluer la politique πk
[V, pol] = IP(P,R,gamma,pi0,nb_it)
3. Interpréter la politique optimale obtenue.
4. Comparer le temps de calcul sur un nombre donné d’itération. Illustrer la
vitesse de la convergence en traçant ||V ∗ − Vk ||∞ en fonction de l’itération
k pour les différents algorithmes.
3 Q-Learning : un algorithme de RL
On suppose maintenant que le vendeur ne connaît pas la loi de Dt . L’algo-
rithme Q-Learning est un algorithme stochastique qui basé sur des simulations
de transitions, converge vers la table action-valeur optimale Q∗ (x, a).
Entrées
– politique πt pour le choix d’une
P action à l’instant
P 2 t
– suite αt de réels positifs tq αt = ∞ et αt < ∞
Pour t ≥ 0
3
– choisir At ∼ πt (Xt , .)
– observation d’une transition : récompense Rt , nouvel état Xt+1
– Updater (Xt , At ) dans la table action-valeur via :
Qt+1 (Xt , At ) = (1 − αt )Qt (Xt , At ) + αt (Rt + γ max Qt (Xt+1 , a))
a∈A
Implémenter la méthode de Q-learning, et vérifier sa convergence quand t tend
vers l’infini.
4 Toy example : un robot dans un labyrinthe
Soit le labyrinthe ci-dessus, où les boules vertes représentes les sorties. On consi-
dère que l’on contrôle un robot bruité se déplaçant dans ce labyrinthe, et le but
est de le faire sortir aussi vite que possible. Le robot est bruité au sens où lors-
qu’on lui demande de se déplacer, il a une probabilité 1 − p de rester sur place.
1. Modéliser ce problème par un MDP permettant de résoudre ce problème :
espace d’états, espace d’actions, probabilités de transition, modèle de ré-
compense, fonction valeur optimale (ie pour quel critère veut-on résoudre
ce MDP ?)
2. Dans le répertoire ’Toy Example’, la fonction
[P,R] = model_exact(para)
construit à partir du labyrinthe préalablement choisi la matrice P (x, y, a) =
p(y|x, a) des transitions et R(x, a) = r(x, a). Quel est le modèle de récom-
pense implémenté par défaut ? Vous pouvez le modifier selon votre modèle
de récompense.
3. Exécuter cellule par cellule le fichier Matlab ’ToyExample.m’ : on peut
visualiser la politique πk résultat de différentes itération de IP et ainsi
observer la convergence vers la politique optimale qui parait naturelle.
