Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Apprentissage par renforcement et par imitation

Processus de décision markoviens : agent, environnement, retour, politique et fonctions de valeur

Le langage de l'apprentissage par renforcement : la boucle agent-environnement, la propriété de Markov, retour et actualisation, politique, valeur d'état et d'action, avantage, le monde en grille avec politique aléatoire et optimale.

https://www.electronics-engineering.com/fr/processus-de-decision-markoviens-retour-politique-fonctions-de-valeur/

Pas encore de vote : soyez le premier à noter cette page.

Dans l’apprentissage supervisé, quelqu’un fournit la bonne réponse pour chaque exemple. Dans l’apprentissage par renforcement (AR), personne ne la connaît : un agent essaie des actions dans un environnement, reçoit une récompense numérique et doit apprendre tout seul quel comportement la maximise à long terme. C’est ainsi que l’on entraîne des programmes qui jouent mieux que les champions (AlphaGo), des robots qui marchent, des régulateurs de trafic et l’étape finale des grands modèles de langage (RLHF). Cette première leçon définit le langage mathématique de tout le cours : le processus de décision markovien, le retour, la politique et les fonctions de valeur.

L’agent et l’environnement

À chaque instant t = 0, 1, 2, \dots, l’agent observe l’état s_t, choisit une action a_t, et l’environnement répond par une récompense r_{t+1} et un nouvel état s_{t+1}. La boucle se répète. Pour un robot, l’état est les positions et les vitesses des articulations, l’action les couples des moteurs, la récompense un nombre qui récompense l’avancée sans tomber. Pour CartPole, l’exemple que nous utiliserons souvent, l’état est la position et la vitesse du chariot, l’angle et la vitesse angulaire du bâton, l’action est de pousser à gauche ou à droite, et la récompense est +1 à chaque pas où le bâton reste debout.

La boucle agent-environnement
L’agent, en bleu, reçoit l’état s t et la récompense r t et choisit l’action a t ; l’environnement, en vert, répond par le nouvel état et la nouvelle récompense. Le retard d’un pas est représenté par le bloc z puissance moins 1.

Le processus de décision markovien

Un MDP (Markov decision process) est le quintuplet (\mathcal S, \mathcal A, P, R, \gamma) :

  • \mathcal S l’ensemble des états, \mathcal A celui des actions ;
  • P(s' \mid s, a) la probabilité de passer à s' en prenant a dans s ;
  • R(s, a) la récompense moyenne obtenue en prenant a dans s ;
  • \gamma \in [0, 1] le facteur d’actualisation.

Le mot markovien indique l’hypothèse fondamentale : le futur ne dépend du passé que par l’état présent, P(s_{t+1} \mid s_t, a_t, s_{t-1}, \dots) = P(s_{t+1} \mid s_t, a_t). Si l’observation ne contient pas tout le nécessaire (par exemple une seule image d’une balle, qui ne dit pas sa vitesse), on le retrouve en mettant aussi les observations précédentes dans l’état ou en utilisant des réseaux à mémoire.

Le retour et l’actualisation

Le but n’est pas la récompense immédiate mais le retour, la somme des récompenses futures actualisées :

    \[ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty}\gamma^k r_{t+k+1} \]

L’actualisation a trois raisons. Mathématique : si les récompenses sont bornées par r_{max} et \gamma \lt  1, la série géométrique converge, |G_t| \le \frac{r_{max}}{1 - \gamma}. Pratique : une récompense lointaine est plus incertaine. D’interprétation : \frac{1}{1 - \gamma} est l’horizon sur lequel l’agent « regarde » : avec \gamma = 0.99, environ 100 pas. La relation récursive, base de tout le cours, vaut :

    \[ G_t = r_{t+1} + \gamma\,G_{t+1} \]

Politique et fonctions de valeur

Une politique \pi(a \mid s) est la règle par laquelle l’agent choisit : la probabilité de prendre a dans l’état s (déterministe si elle donne toujours la même action). Pour l’évaluer, on définit :

    \[ V^\pi(s) = \mathbb E_\pi[G_t \mid s_t = s],\qquad Q^\pi(s, a) = \mathbb E_\pi[G_t \mid s_t = s,\ a_t = a] \]

V^\pi(s), la valeur de l’état, est le retour moyen en partant de s et en suivant \pi ; Q^\pi(s, a), la valeur de l’action, est le retour moyen en prenant d’abord a puis en suivant \pi. Elles sont liées par V^\pi(s) = \sum_a\pi(a \mid s)\,Q^\pi(s, a). La différence A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s) s’appelle l’avantage : de combien l’action a est meilleure que la moyenne. Tous les algorithmes modernes l’utilisent.

Une politique \pi^* est optimale si V^{\pi^*}(s) \ge V^\pi(s) dans tout état, pour toute autre \pi. Dans un MDP fini, il existe toujours une politique optimale déterministe (on le démontre dans la leçon sur les équations de Bellman), et en connaissant Q^* elle est immédiate : \pi^*(s) = \arg\max_a Q^*(s, a).

Un exemple complet : le monde en grille

Une grille 4×4 ; les cases en haut à gauche et en bas à droite sont les sorties. L’agent se déplace d’une case vers le haut, le bas, la gauche ou la droite (s’il heurte le bord, il reste sur place), et chaque pas coûte -1 : maximiser le retour veut dire sortir le plus vite possible. Avec \gamma = 1 :

  • pour la politique optimale, la valeur de chaque case est moins le nombre de pas jusqu’à la sortie la plus proche : 0, −1, −2, −3 ;
  • pour la politique aléatoire (chaque direction avec une probabilité 1/4), les valeurs sont bien plus négatives : −14 près des sorties, −22 dans les coins éloignés, parce que la marche aléatoire erre longtemps avant de sortir.
Valeurs des états du monde en grille 4 par 4
À gauche la politique aléatoire, avec des valeurs de moins 14 à moins 22 ; à droite la politique optimale, avec des valeurs de 0 à moins 3 et les flèches de la meilleure direction. Les cases sombres en haut à gauche et en bas à droite sont les sorties.

Le fait que la politique aléatoire vaille −22 dans un coin, et l’optimale −3, montre le point central de l’AR : à partir des mêmes états et des mêmes actions, le comportement choisi change radicalement le résultat. La leçon suivante montre comment calculer ces valeurs, et à partir d’elles la politique optimale, avec les équations de Bellman ; les leçons d’après, comment les apprendre quand P et R sont inconnues et que l’état est trop grand pour un tableau.

Où se situe l’AR parmi les techniques de contrôle

Ceux qui ont étudié les Contrôles automatiques reconnaîtront la structure : l’état, l’entrée (l’action), la dynamique (P), un indice de coût à optimiser (-G). Le contrôle optimal (LQR, MPC) résout le même problème en connaissant le modèle ; l’AR le résout en apprenant de l’expérience, même quand il n’y a pas de modèle ou qu’il est trop compliqué. Le prix est le nombre d’essais : c’est pourquoi l’AR se fait presque toujours en simulation, et la vitesse des simulateurs (leçon sur les bibliothèques) est décisive.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x