Q-Learning sur un espace d'états discrétisé

Introduction

On aborde le cas des espaces d'états infinis, non dénombrables. En particulier, le cas où l'espace d'états est un sous-ensemble compact (dans le contexte présent, le terme mathématique « compact » signifie qu'on s'intéresse à un sus-ensemble dans lequel il n'y a pas de trou) de \( \mathbb{R}^P \), autrement dit, un hyper-parallélépipéde en dimension \( P \). Si \( P = 2 \), c'est simplement un rectangle et si \( P = 1 \), un segment de droite.
Des exemples simples sont les systèmes dynamiques contrôlés, tels des robots. Un système dynamique est un système dont l'état évolue au cours du temps. On s'intéresse particulièrement aux systèmes dont la dynamique est régie par la loi de Newton. Dans ceux-ci une action est une accélération (positive ou négative) et connaissant la masse et l'accélération, on en déduit la vitesse puis la positin par intégration. Pour ces systèmes dynamiques newtoniens, on sait (cours de physique au lycée) que l'état du système à un instant donnée est décrit pas sa position et sa vitesse. La fonction de transition du processus de décision de Markov est alors donnée par une équation différentielle reliant l'action à son effet sur le changement d'état.
Dans ce TP, on discrétise l'espace des états pour se ramener au Q-Learning.

Quelques problèmes auxquels on va s'intéresser

On décrit deux problèmes dont l'espace d'état est un sous-espace de \( \mathbb{R}^2 \), autrement dit un rectangle : le pendule inversé et la voiture dans la montagne.

Le pendule inversé

On essaie de mettre un pendule à l'équilibre, vers le haut. Cette position est très instable.

L'équation de la dynamique est la suivante :
\( a = \frac{1}{ml^2} (- \mu v + mgl \sin{(p)} + u) \)
où :

Pour une action donnée, on calcule \( a \) d'où l'on déduit la nouvelle vitesse \( v_{t+\Delta t} = v_t + a \Delta t \) et la nouvelle position \( p_{t + \Delta t} = p_t + v_t \Delta t \). On prendra \( \Delta t = 0,01 \), c'est-à-dire que les actions sont réalisées à chaque centième de seconde.
L'état courant est donc donné par le couple \( (p, v) \).
La position est un angle, donc \( p \in [-\pi, \pi] \). Par convention, l'angle nul correspond à la position instable du pendule, donc à l'équilibre supérieur. \( \pi \) correspondant donc à la psition stable du pendule, pendant vers le bas.
On limite la vitesse à 10 en valeur absolue. Au-delà, le pendule casse.
Il y a trois actions possibles : \( u \in \{ -5, 0, 5 \} \) Newtons.
Le retour peut-être défini de différente manière. L'objectif étant de placer le pendule en équilibre supérieur, on pourrait le définir comme valant 1 lorsque la position angulaire est (presque) 0 et la vitesse (presque) nulle. Cependant résoudre ainsi le problème est assez difficile. Le problème est beaucoup plus simple à résoudre si on définit le retour comment étant le cosinus de la position angulaire, soit \( \cos{(p)} \).

La voiture dans la montagne

Une « voiture » essaie d'atteindre le sommet d'une montagne. Son moteur n'est pas assez puissant pour l'atteindre. La voiture doit prendre de l'élan en remontant la montagne opposée, prendre de la vitesse, accélérer pour enfin réussir à atteindre le sommet.

L'équation de la dynmique est la suivante :
\( v_{t+1} = clip (v_t + 0,001 u - 0,0025 \cos{(3.p_t)})\)
\( p_{t+1} = clip (p_t + v_{t+1}) \)
où \( u \) est l'action : \( u \in \{ -1, 0, +1 \} \). \( p_t \) et \( v_t \) sont la position et la vitesse courantes.
La position est comprise entre -1,2 et 0,6.
La vitesse est comprise entre -0,07 et 0,07.
La fonction \( clip () \) empêche la position et la vitesse de déborder de ces intervalles.
Le système débute toujours dans l'état initial \( p_0 \in \{ -0,6; -0,4 \} \) et \( v_0 = 0 \).
Le retour est -1 à chaque interaction.
L'objectif est d'atteindre la position \( p \ge{} 0,5 \) en moins de 200 interactions.
Si l'état final n'est pas atteint en au plus 200 pas, le système est replacé dans son état initial.

Algorithme

L'algorithme est le Q-Learning que vous implantez lors du TP précédent. La différence cette fois-ci est qu'il faut discrétiser l'espace d'états.

Implantation

Vos expériences doivent être reproductibles.

À faire : implanter cet algorithme. Encore une fois, faire en sorte que l'implantation soit générique.
On pourra utiliser une grille de 40x40 pour discrétiser l'espace d'états.

Expérimentation

Vous résolvez les deux problèmes indiqués plus haut, le pendule inversé et la voiture dans la montagne. Pour chacun, vous essayez d'obtenir les meilleures performances de votre algorithme.
Lorsque votre algorithme fonctionne, réalisez une vingtaine d'épisodes de test, c'est-à-dire que vous utilisez l'estimation de la qualité \( \hat{Q} \) et que vous exécutez 20 fois la politique gloutonne. À chaque exécution, vous mesurez le retour, c'est-à-dire la somme des retours immédiats pondérés, \( R = \sum_t \gamma^t r_t \). Quelle est la médiane ? Quelle est la variabilité de \( R \) ?

Pour vous donner un ordre de grandeur, pour le pendule inversé, en réalisant 50.000 épisodes de 5000 pas maximum, j'obtiens une relativement bonne approximation de la fonction valeur. Ci-dessous une représentation 3D sous différents angles. On observe bien la forme attendue.

Et ci-dessous, la fonction valeur estimée avec des grilles de 10x10 et 20x20 après seulement 100 épisodes de 5000 pas maximum chacun.


Pour la voiture dans la montagne, en utilisant un paramètre d'apprentissage fixe \( \alpha = 0,2 \), le Q-Learning tabulaire réussit à atteindre l'état terminal en moins de 200 pas en moins de 5000 épisodes. Il l'atteint en 88 pas en faisant 30000 épisodes. Ci-dessous, des représentations 3D de l'estimation de la fonction valeur après respectivement 5000, 30000 et 100000 épisodes.

À l'issue de ce TP, votre programme doit pouvoir être appliqué à n'importe quel problème de décision de Markov à espace d'états continu.