Reinforcement Learning - Reinforcement Learning

Projet : Résolution d’un problème de gestion de stock par programmation dynamique et apprentissage par renforcement

Master M2 MIASHS | Enseignant: Stéphane Chrétien

Objectif général¶

Ce projet a pour objectif de mettre en œuvre l’apprentissage par renforcement sur un problème classique de gestion de stock stochastique déjà programmé ici. La mission consistera à implémenter, analyser et comparer :

Les itérations de Bellman sur un modèle connu (avec dynamique de transition exacte),
La méthode REINFORCE appliquée au même problème, sans connaissance du modèle (mais en supposant que la réalité est le modèle inconnu qui est déjà programmé).

Contexte¶

On considère un système de gestion de stock discret dans lequel :

Le stock maximal est noté $M$ ,
La demande $D_t$ à chaque période est une variable aléatoire suivant une loi donnée,
L’action $a_t$ correspond à la quantité commandée,
Les coûts comprennent un coût de stockage, un coût de commande et éventuellement un coût de rupture.

L’objectif est de déterminer une politique optimale stationnaire $\pi^*$ minimisant le coût total espéré à horizon infini avec un facteur d’actualisation $\gamma \in [0, 1)$ .

Partie 1 — Programmation dynamique¶

1. Implémentation de l’équation d’optimalité de Bellman¶

Pour une politique donnée $\pi$ , l’équation de Bellman est

V^\pi(x) = \mathbb{E} [R(x, U \sim \pi(x), D)] + \gamma \mathbb{E} [p(x' | x, U \sim \pi(x))] V^\pi(x').

(1)

où :

$x$ est le stock avant commande,
$u$ est la quantité commandée,
$R(x, u, D)$ est la récompense aléatoire pour l’action $u$ , en fonction de la demande $D$
$\gamma \in [0, 1)$ est le facteur d’actualisation,
la transition $X_{t+1} = x'$ dépend des événements $X_t = x$ , $U = u$ et de la demande aléatoire $D_t$ . Notez que $p(x' | x, u)$ encode l’impact aléatoire de la demande, donc pas besoin d’écrire $p(x' | x, u, D)$

La version stationnaire de l’équation d’optimalité de Bellman à horizon infini est :

V^*(x) = \max_\pi \mathbb{E} [R(x, U \sim \pi(x), D)] + \gamma \mathbb{E} [p(x' | x, U \sim \pi(x))] V^*(x').

(2)

où :

$x$ est le stock avant commande,
$u$ est la quantité commandée,
$R(x, u, D)$ est la récompense aléatoire pour l’action $u$ , en fonction de la demande $D$ .
$\gamma \in [0, 1)$ est le facteur d’actualisation,
la transition $X_{t+1} = x'$ dépend des événements $X_t = x$ , $U = u$ et de la demande aléatoire $D_t$ .

2. Itérations de Bellman¶

Implémentez l’algorithme d’itérations de Bellman pour un horizon infini :

Initialisez $V_0(x)$ pour tout $x$ en choisissant une politique de votre choix puis en résolvant l’équation de Bellman associée à cette politique.
Répétez la mise à jour :

V_{k+1}(x) = \max_\pi \mathbb{E} [R(x, U \sim \pi(x))] + \gamma \mathbb{E}[p(x' | x, U \sim \pi(x))] V_k(x'),

(3)

jusqu’à convergence de $V_k$ ,

En déduire la politique optimale $\pi^*$ .

3. Visualisation des politiques¶

Reproduisez la figure finale du notebook de base et ajoutez la politique optimale $\pi^*$ trouvée par itérations de Bellman sur la même figure, afin de comparer visuellement les différentes stratégies.

Partie 2 — Méthode REINFORCE¶

Dans cette partie, on suppose que la dynamique du système est inconnue. L’objectif est d’apprendre une politique paramétrique $\pi_\theta(u | x)$ à partir de trajectoires simulées, sans utiliser les probabilités de transition suivies en réalité par le vrai modèle.

1. Implémentation de REINFORCE¶

L’algorithme REINFORCE (Williams, 1992) repose sur une mise à jour du gradient de politique à partir du retour total observé à chaque instant $t$ .

Pour chaque trajectoire générée par la politique courante :

$(x_0, u_0, r_0, x_1, u_1, r_1, \dots),$

on définit pour tout $t$ le retour (return) à partir de $t$ :

G_t = \sum_{k=t}^\infty \gamma^{k-t} r_k

(4)

où :

$r_k$ est la récompense (ou le coût négatif) observée à l’étape $k$ ,
$\gamma \in [0, 1)$ est le facteur d’actualisation,
$G_t$ représente la somme des récompenses futures actualisées à partir de $t$ .

La mise à jour des paramètres de la politique s’écrit alors :

\theta \leftarrow \theta + \alpha G_t \nabla_\theta \log \pi_\theta(u_t | x_t)

(5)

où $\alpha$ est le taux d’apprentissage. L’espérance de cette mise à jour est proportionnelle au gradient du rendement moyen, ce qui garantit (sous certaines hypothèses) une amélioration progressive de la politique.

2. Expérimentation¶

Faire un test avec 1000 pas de gradients et un $\alpha$ qui marche bien à découvrir en essayant plusieurs valeurs. N’oubliez pas de re-générer $G_t$ à chaque itération de la méthode du gradient avec la nouvelle politique $\pi_\theta$ obtenue.
Si vous générez plusieurs trajectoires, comment les combiner pour avoir un meilleur estimateur de $G_t$ ? Entraînez la politique pour différents nombres de trajectoires simulées (par exemple : 100, 1000, 5000),
Comparez la politique apprise avec :
- Les politiques naives du notebook fourni.
- La politique optimale obtenue par les itérations de Bellman.

3. Analyse comparative¶

Présentez vos résultats sous forme de graphiques (valeurs d’état, coûts moyens, politiques apprises) et commentez :

la convergence de la méthode REINFORCE,
l’effet du nombre de trajectoires sur la stabilité et la qualité de la politique,
les différences entre approche « modèle connu » (Bellman) et approche « sans modèle » (REINFORCE).