Introduction aux méthodes de solutions approximatives pour l’apprentissage par renforcement

série sur l’apprentissage par renforcement (RL), faisant suite au célèbre livre de Sutton et Barto « Apprentissage par renforcement » [1].

Dans les articles précédents, nous avons fini de disséquer la première partie dudit livre, qui présente les techniques fondamentales de résolution qui constituent la base de nombreuses méthodes RL. Ce sont : Programmation dynamique (DP), Méthodes de Monte Carlo (MC) et Apprentissage par différence temporelle (TD). Ce qui sépare la première partie de la deuxième partie du livre de Sutton, et justifie la distinction, est une contrainte sur la taille du problème : alors que dans la première partie les méthodes de résolution tabulaires étaient couvertes, nous osons maintenant approfondir ce sujet fascinant et inclure l’approximation des fonctions.

Pour être plus précis, dans la première partie, nous avons supposé que l’espace d’état des problèmes étudiés était suffisamment petit pour que nous puissions le représenter ainsi que les solutions trouvées via un simple tableau (imaginez un tableau désignant une certaine « bonté » – une valeur – pour chaque état). Dans la deuxième partie, nous abandonnons cette hypothèse et sommes ainsi en mesure d’aborder des problèmes arbitraires.

Et cette configuration modifiée est absolument nécessaire, comme nous avons pu le constater : dans un article précédent, nous avons réussi à apprendre à jouer au Tic Tac Toe, mais nous avons déjà échoué pour Connect Four – puisque le nombre d’états ici est de l’ordre de 10²⁰. Ou bien, considérons un problème RL qui apprend une tâche basée sur des images de caméra : le nombre d’images de caméra possibles est supérieur au nombre d’atomes dans l’univers connu. [1].

Ces chiffres devraient convaincre tout le monde que des méthodes de résolution approximatives sont absolument nécessaires. En plus de permettre de résoudre de tels problèmes, ils offrent également une généralisation : pour les méthodes tabulaires, deux états proches, mais néanmoins différents, ont été traités complètement séparément – ​​alors que pour les méthodes de résolution approchée, nous espérons que notre approximation de fonction puisse détecter des états aussi proches et généraliser.

Sur ce, commençons. Dans les prochains paragraphes, nous allons :

• donner une introduction à l’approximation des fonctions
• produire des méthodes de solution à de tels problèmes
• discuter de différents choix pour les fonctions d’approximation.

Introduction à l’approximation des fonctions

Contrairement aux méthodes de résolution tabulaires, pour lesquelles nous utilisions un tableau pour représenter par exemple les fonctions de valeur, nous utilisons désormais une fonction paramétrée.

avec un vecteur de poids

v peut être n’importe quoi, comme une fonction linéaire des valeurs d’entrée ou un réseau neuronal profond. Plus loin dans cet article, nous discuterons en détail des différentes possibilités.

Habituellement, le nombre de poids est bien inférieur au nombre d’états – ce qui conduit à une généralisation : lorsque nous mettons à jour notre fonction en ajustant certains poids, nous ne mettons pas seulement à jour une seule entrée dans un tableau – mais cela aura également un effet sur (éventuellement) toutes les autres estimations.

Récapitulons les règles de mise à jour de quelques-unes des méthodes que nous avons vues dans les articles précédents.

Les méthodes MC attribuent le retour observé G comme estimation de la valeur d’un état :

TD(0) amorce l’estimation de la valeur de l’état suivant :

Alors que DP utilise :

Nous allons désormais interpréter les mises à jour de la forme s -> u comme des couples d’entrées/sorties d’une fonction que nous souhaitons approximer, et utiliser pour cela des techniques issues du machine learning, notamment : l’apprentissage supervisé. Les tâches dans lesquelles des nombres (u) doivent être estimés sont connues sous le nom d’approximation de fonction ou de régression.

Pour résoudre ce problème, nous pouvons en théorie recourir à n’importe quelle méthode possible pour une telle tâche. Nous en discuterons dans un instant, mais nous devons mentionner qu’il y a certaines exigences sur de telles méthodes : d’une part, elles doivent être capables de gérer des changements et des ensembles de données incrémentiels – puisque dans RL, nous acquérons généralement de l’expérience au fil du temps, ce qui diffère, par exemple, des tâches d’apprentissage supervisé classiques. De plus, la méthode choisie devrait être capable de gérer des cibles non stationnaires – ce dont nous discuterons dans la sous-section suivante.

L’objectif de prédiction

Tout au long de la première partie du livre de Sutton, nous n’avons jamais eu besoin d’un objectif de prédiction ou similaire – après tout, nous pouvions toujours converger vers la fonction optimale qui décrivait parfaitement la valeur de chaque état. Pour les raisons évoquées ci-dessus, cela n’est plus possible – ce qui nécessite de définir un objectif, une fonction de coût, que l’on souhaite optimiser.

Nous utilisons les éléments suivants :

Essayons de comprendre cela. Il s’agit d’une attente concernant la différence entre les valeurs prédites et réelles, qui, intuitivement, a du sens et est courante dans l’apprentissage supervisé. Notez que cela nous oblige à définir une distribution µ, qui précise à quel point nous nous soucions de certains états.

Il s’agit souvent simplement d’une mesure proportionnelle à la fréquence à laquelle les États sont visités – la répartition selon les politiques, sur laquelle nous nous concentrerons dans cette section.

Cependant, notez qu’il n’est pas clair si c’est le bon objectif : chez RL, nous nous soucions de trouver de bonnes politiques. Certaines de nos méthodes pourraient extrêmement bien optimiser au-dessus de l’objectif, mais ne parviendraient toujours pas à résoudre le problème en question – par exemple lorsque la politique passe trop de temps dans des états indésirables. Pourtant, comme nous l’avons vu, nous avons besoin d’un tel objectif – et faute d’autres possibilités, nous l’optimisons simplement.

Introduisons ensuite une méthode pour minimiser cet objectif.

Minimiser l’objectif de prédiction

L’outil que nous choisissons pour cette tâche est la descente de gradient stochastique (SGD). Contrairement à Sutton, je ne souhaite pas entrer ici dans trop de détails, et me concentrer uniquement sur la partie RL – j’aimerais donc renvoyer le lecteur intéressé à [1] ou tout autre tutoriel sur SGD/deep learning.

Mais, en principe, SGD utilise des lots (ou mini-lots) pour calculer le gradient de l’objectif et mettre à jour les poids d’un petit pas dans le sens de minimiser cet objectif.

Car ainsi, ce gradient vaut :

Maintenant la partie intéressante : supposons que v_π n’est pas la vraie cible, mais une approximation (bruyante) de celle-ci, disons U_t :

Nous pouvons montrer que si U_t est un non biaisé de v_π, alors la solution obtenue via SGD converge vers un optimum local – pratique. Nous pouvons maintenant simplement utiliser par exemple le retour MC comme U_t, et obtenir notre toute première méthode gradient RL :

Il est également possible d’utiliser d’autres mesures pour U_t, notamment d’utiliser également le bootstrapping, c’est-à-dire d’utiliser des estimations précédentes. Ce faisant, nous perdons ces garanties de convergence – mais, comme souvent, de manière empirique, cela fonctionne toujours. De telles méthodes sont appelées méthodes semi-gradientes, car elles prennent uniquement en compte l’effet de la modification des poids sur la valeur à mettre à jour, mais pas sur la cible.

Sur cette base, nous pouvons introduire TD(0) avec une approximation de fonction :

Une extension naturelle de ceci, et également une extension de la méthode tabulaire en n étapes correspondante, est le TD semi-gradient en n étapes :

Méthodes d’approximation des fonctions

Dans le reste du chapitre 9, Sutton décrit différentes manières de représenter la fonction approchée : une grande partie du chapitre couvre l’approximation de fonctions linéaires et la conception des fonctionnalités pour cela, et pour l’approximation de fonctions non linéaires, des réseaux de neurones artificiels sont introduits. Nous n’aborderons que brièvement ces sujets, car sur ce blog, nous travaillons principalement avec des réseaux de neurones (profonds) et non avec de simples approximations linéaires, et nous soupçonnons également que le lecteur avisé est déjà familier avec les bases de l’apprentissage profond et des réseaux de neurones.

Approximation de la fonction linéaire

Discutons néanmoins brièvement de l’approximation linéaire. En cela, la fonction état-valeur est approximée par le produit scalaire :

Ici, l’état est décrit par le vecteur

– et, comme nous pouvons le voir, il s’agit d’un linéaire combinaison des poids.

En raison de la simplicité de la représentation, il existe des formules élégantes (et des représentations en boucle fermée) pour la solution, ainsi que des garanties de convergence.

Construction de fonctionnalités pour les méthodes linéaires

Une limitation de l’approximation naïve de fonctions linéaires introduite ci-dessus est que chaque caractéristique est utilisée séparément et qu’aucune combinaison de caractéristiques n’est possible. Sutton donne comme exemple le problème du poteau de chariot : ici, une vitesse angulaire élevée peut être bonne ou mauvaise, selon le contexte. Lorsque la perche est bien centrée, il faut probablement éviter les mouvements rapides et saccadés. Cependant, plus le pôle est proche de tomber, plus des vitesses plus rapides peuvent être nécessaires.

Il existe donc une branche distincte de la recherche sur la conception de représentations efficaces de caractéristiques (même si l’on pourrait affirmer qu’en raison de l’essor de l’apprentissage profond, cela devient moins important).

Une de ces représentations est polynômes. À titre d’exemple d’introduction, imaginez que le vecteur d’état soit composé de deux parties, s_1 et s_2. On pourrait ainsi définir l’espace des fonctionnalités :

Ensuite, en utilisant cette représentation, nous pourrions toujours faire une approximation de fonction linéaire – c’est-à-dire utiliser quatre poids pour les quatre caractéristiques nouvellement construites, et globalement toujours avoir une fonction linéaire par rapport aux poids.

Plus généralement, le caractéristiques polynomiales d’ordre n+1 peut être représenté par

où les c sont des entiers dans {0 … n}.

D’autres bases couramment utilisées sont la base de Fourier, le codage grossier et en tuiles, ainsi que les fonctions de base radiale – mais comme mentionné, nous n’approfondirons pas ce point à ce stade.

Conclusion

Dans cet article, nous avons franchi une étape importante au-delà des articles précédents vers le déploiement d’algorithmes RL « à l’état sauvage ». Dans les articles précédents, nous nous sommes concentrés sur l’introduction des méthodes RL essentielles, bien que sous forme de méthodes tabulaires. Nous avons constaté qu’ils atteignent rapidement leurs limites lorsqu’ils sont déployés sur des problèmes plus vastes et avons ainsi réalisé que des méthodes de résolution approximatives sont nécessaires.

Dans cet article, nous avons présenté les principes fondamentaux pour cela. En plus de permettre de résoudre des problèmes réels à grande échelle, ces méthodes introduisent également la généralisation – une nécessité essentielle pour tout algorithme RL réussi.

Nous avons commencé par introduire un objectif de prédiction approprié et des moyens de l’optimiser.

Ensuite, nous avons introduit nos premiers algorithmes RL à gradient et semi-gradient pour l’objectif de prédiction, c’est-à-dire l’apprentissage d’une fonction de valeur pour une politique donnée.

Enfin, nous avons discuté de différentes manières de construire la fonction d’approximation.

Comme toujours, merci d’avoir lu ! Et si vous êtes intéressé, restez à l’écoute du prochain article dans lequel nous aborderons le problème de contrôle correspondant.

Autres articles de cette série

Références

[1] http://incompleteideas.net/book/RLbook2020.pdf

[2] https://pettingzoo.farama.org/