Comment appliquer l'apprentissage par renforcement aux problèmes de planification dans la vie réelle

Récemment, j'ai publié quelques exemples dans lesquels j'ai créé des modèles d'apprentissage par renforcement pour résoudre des problèmes de la vie réelle. Par exemple, utiliser l'apprentissage par renforcement pour la planification des repas en fonction d'un budget défini et de préférences personnelles.

L'apprentissage par renforcement peut être utilisé de cette manière pour résoudre divers problèmes de planification, notamment les plans de déplacement, la planification budgétaire et la stratégie commerciale. L'utilisation de RL présente deux avantages: elle prend en compte la probabilité de résultats et nous permet de contrôler certaines parties de l'environnement. Par conséquent, j'ai décidé d'écrire un exemple simple pour que d'autres puissent réfléchir à la façon dont ils pourraient commencer à l'utiliser pour résoudre certains de leurs problèmes quotidiens ou professionnels.

Qu'est-ce que l'apprentissage par renforcement?

L'apprentissage par renforcement est le processus qui consiste à tester quelles actions sont les meilleures pour chaque état d'un environnement, essentiellement par essais et erreurs. Le modèle introduit une stratégie aléatoire pour commencer et chaque fois qu'une action est entreprise, un montant initial (appelé récompense) est injecté dans le modèle. Cela se poursuit jusqu'à ce qu'un objectif final soit atteint, par exemple vous gagnez ou perdez le jeu, où cette course (ou épisode) se termine et le jeu réinitialise.

À mesure que le modèle traverse de plus en plus d'épisodes, il commence à apprendre quelles actions sont les plus susceptibles de nous conduire à un résultat positif. Par conséquent, il trouve les meilleures actions dans n'importe quel état, appelé stratégie optimale.

Processus général d'apprentissage par renforcement

De nombreuses applications RL en ligne entraînent des modèles dans un environnement de jeu ou virtuel où le modèle est capable d'interagir avec l'environnement à plusieurs reprises. Par exemple, vous laissez le modèle jouer une simulation de tic-tac-toe encore et encore pour qu'il observe le succès et l'échec d'essayer différents mouvements.

Dans la vraie vie, il est probable que nous n’ayons pas accès à la formation de notre modèle de cette manière. Par exemple, un système de recommandation dans les achats en ligne a besoin de l’avis d’une personne pour nous dire s’il a réussi ou non, et sa disponibilité est limitée en fonction du nombre d’utilisateurs qui interagissent avec le site d’achat.

À la place, nous pouvons avoir des exemples de données montrant les tendances d’achat sur une période donnée que nous pouvons utiliser pour créer des probabilités estimées. À l'aide de ceux-ci, nous pouvons créer ce que l'on appelle un processus de décision de Markov partiellement observé (POMDP) ​​comme moyen de généraliser la distribution de probabilité sous-jacente.

Processus décisionnels de Markov partiellement observés (POMDP)

Les processus de décision de Markov (MDP) fournissent un cadre pour modéliser la prise de décision dans des situations où les résultats sont en partie aléatoires et en partie sous le contrôle d'un décideur. La principale caractéristique des MDP est qu’ils suivent la propriété de Markov; tous les états futurs sont indépendants du passé compte tenu du présent. En d'autres termes, la probabilité de passer à l'état suivant ne dépend que de l'état actuel.

Les POMDP fonctionnent de la même manière, sauf qu’il s’agit d’une généralisation des PDM. En bref, cela signifie que le modèle ne peut pas simplement interagir avec l'environnement, mais se voit attribuer une distribution de probabilité définie basée sur ce que nous avons observé. Plus d'informations peuvent être trouvées ici. Nous pourrions utiliser des méthodes d’itération de valeur sur notre POMDP, mais j’ai plutôt décidé d’utiliser Monte Carlo Learning dans cet exemple.

Exemple d'environnement

Imaginez que vous soyez de retour à l’école (ou peut-être le soyez encore) et que vous êtes dans une salle de classe. L’enseignant applique une politique stricte en matière de déchets de papier. les déchets dans la poubelle.

Cependant, certains élèves de la classe se soucient peu des règles de l’enseignant et préfèrent éviter de s’ennuyer à passer le papier autour de la classe. Au lieu de cela, ces personnes gênantes peuvent choisir de jeter le papier de rebut dans le bac à distance. Maintenant, cela met en colère le professeur et ceux qui le font sont punis.

Cela introduit un concept de base action-récompense, et nous avons un exemple d'environnement de classe, comme illustré dans le diagramme suivant.

Notre objectif est de trouver les meilleures instructions pour chaque personne afin que le papier parvienne à l’enseignant et soit placé à la poubelle, évitant ainsi d’être jeté à la poubelle.

États et actions

Dans notre environnement, chaque personne peut être considérée comme un État et peut prendre diverses mesures avec le papier brouillon. Ils peuvent choisir de le transmettre à un camarade de classe adjacent, de le conserver ou de le jeter à la poubelle. Nous pouvons donc mapper notre environnement sur une grille plus standard, comme indiqué ci-dessous.

C’est délibérément conçu pour que chaque personne, ou chaque État, ait quatre actions: haut, bas, gauche ou droite et que chacune ait un résultat "réel" varié, en fonction de la personne qui a pris l’action. Une action qui met la personne dans un mur (y compris le bloc noir au milieu) indique que la personne tient sur le papier. Dans certains cas, cette action est dupliquée, mais n’est pas un problème dans notre exemple.

Par exemple, les actions de la personne A se traduisent par:

  • Up = jeter dans la corbeille
  • Bas = Tenir sur le papier
  • Gauche = Passer à la personne B
  • Droite = Tenir sur le papier

Environnement probabiliste

Pour le moment, le décideur qui contrôle en partie l'environnement, c'est nous. Nous dirons à chaque personne quelle action elle devrait entreprendre. Ceci est connu comme la politique.

Mon premier défi dans mon apprentissage est de comprendre que l'environnement est probablement probabiliste et ce que cela signifie. Un environnement probabiliste est lorsque nous donnons pour instruction à un État de prendre une mesure conformément à notre politique, il existe une probabilité associée de savoir si cela est suivi avec succès. En d’autres termes, si nous demandons à la personne A de passer le papier à la personne B, elle peut décider de ne pas suivre l’action décrite dans notre politique et de jeter à la place le papier brouillon.

Un autre exemple est que si nous recommandons des produits de magasinage en ligne, rien ne garantit que la personne les verra.

Probabilités de transition observées

Pour trouver les probabilités de transition observées, nous devons collecter des exemples de données sur le comportement de l'environnement. Avant de collecter des informations, nous introduisons d’abord une politique initiale. Pour commencer le processus, j’en ai choisi au hasard un qui donnerait des résultats positifs.

Nous observons maintenant les actions que chaque personne prend compte tenu de cette politique. En d'autres termes, supposons que nous nous sommes assis au fond de la classe et avons simplement observé la classe et observé les résultats suivants pour la personne A:

Actions observées par la personne A

Nous voyons qu'un papier a traversé cette personne 20 fois; 6 fois ils l'ont gardé, 8 fois ils l'ont passé à la personne B et 6 autres fois ils l'ont jeté à la poubelle. Cela signifie qu'en vertu de notre politique initiale, la probabilité de la garder ou de la jeter à la poubelle pour cette personne est de 6/20 = 0,3 et de même 8/20 = 0,4 à passer à la personne B. Nous pouvons observer le reste de la classe collecter les exemples de données suivants:

Résultats réels observés

De même, nous calculons ensuite les probabilités comme étant la matrice suivante et nous pourrions nous en servir pour simuler l'expérience. La précision de ce modèle dépendra largement de la pertinence des probabilités pour représenter l'ensemble de l'environnement. En d’autres termes, nous devons nous assurer de disposer d’un échantillon suffisamment volumineux et suffisamment riche en données.

Fonction de probabilité de transition observée

Bandits à plusieurs armes, épisodes, récompenses, rendement et taux de remise

Nous avons donc nos probabilités de transition estimées à partir des données de l'échantillon sous POMDP. La prochaine étape, avant que nous introduisions des modèles, consiste à introduire des récompenses. Jusqu'à présent, nous n'avons discuté que du résultat de la dernière étape. le papier est placé dans la corbeille par l'enseignant et génère une récompense positive ou est jeté par A ou M et génère une récompense négative. Cette récompense finale qui termine l'épisode est connue sous le nom de Récompense terminale.

Mais, il y a aussi un troisième résultat qui n'est pas idéal non plus; le papier est continuellement distribué et jamais (ou prend beaucoup plus longtemps que nous le voudrions) n'atteint la corbeille. Par conséquent, en résumé, nous avons trois résultats finaux

  • Le papier est placé dans la corbeille par l’enseignant et donne une récompense finale positive
  • Un élève jette du papier dans la corbeille et donne une récompense finale négative
  • Le papier circule continuellement dans la pièce ou reste collé aux élèves pendant une période plus longue que celle souhaitée

Pour éviter que le papier ne soit jeté à la poubelle, nous fournissons à celui-ci une grande récompense négative, par exemple -1, et parce que l'enseignant se réjouit qu'il soit placé à la poubelle, une grande récompense positive est +1. Pour éviter le résultat où il est continuellement passé autour de la salle, nous définissons la récompense pour toutes les autres actions comme étant une petite valeur négative, disons -0.04.

Si nous définissons ce nombre comme un nombre positif ou nul, le modèle peut alors laisser le papier tourner sans fin, car il serait préférable de gagner de petits positifs plutôt que de risquer de se rapprocher du résultat négatif. Ce nombre est également très faible car il ne collectera qu'une seule récompense finale, mais plusieurs étapes sont nécessaires pour mettre fin à l'épisode. Nous devons veiller à ce que, si le papier est placé à la poubelle, l'issue positive ne soit pas annulée.

Remarque: les récompenses sont toujours relatives les unes aux autres et j'ai choisi des chiffres arbitraires, mais ils peuvent être modifiés si les résultats ne sont pas ceux souhaités.

Bien que nous ayons discuté par inadvertance des épisodes dans l'exemple, nous n'avons pas encore défini formellement. Un épisode est simplement les actions que chaque papier entreprend dans la classe pour atteindre le bac, qui est l'état terminal et met fin à l'épisode. Dans d'autres exemples, tels que jouer au tic-tac-toe, ce serait la fin d'un jeu où vous gagnerez ou perdrez.

Le document pourrait théoriquement commencer à n’importe quel état, ce qui explique pourquoi nous avons besoin d’épisodes suffisants pour garantir que chaque état et chaque action sont suffisamment testés pour que nos résultats ne soient pas motivés par des résultats invalides. D'un autre côté, plus nous introduisons d'épisodes, plus le temps de calcul est long et, en fonction de la taille de l'environnement, nous ne disposerons peut-être pas d'un nombre illimité de ressources pour le faire.

C'est ce qu'on appelle le problème des bandits à plusieurs bras. avec un temps fini (ou d'autres ressources), nous devons nous assurer de tester suffisamment chaque paire action-état pour que les actions sélectionnées dans notre politique soient, en réalité, les actions optimales. En d'autres termes, nous devons valider que les actions qui nous ont conduit à de bons résultats dans le passé ne sont pas une simple chance, mais sont en fait le bon choix, de même que les actions qui semblent pauvres. Dans notre exemple, cela peut sembler simple avec le nombre limité d’États que nous avons, mais imaginons que nous augmentions l’échelle et que cela devienne de plus en plus problématique.

L’objectif général de notre modèle RL est de sélectionner les actions qui maximisent les avantages cumulatifs attendus, appelées retour. En d'autres termes, le retour est simplement la récompense totale obtenue pour l'épisode. Un moyen simple de calculer cela serait d’additionner toutes les récompenses, y compris la récompense finale, dans chaque épisode.

Une approche plus rigoureuse consiste à considérer les premières étapes comme plus importantes que les étapes ultérieures de l'épisode en appliquant un facteur de réduction, gamma, dans la formule suivante:

En d'autres termes, nous additionnons toutes les récompenses, mais nous pesons les étapes ultérieures d'un facteur gamma à la puissance du nombre d'étapes nécessaires pour les atteindre.

Si nous pensons à notre exemple, utiliser un retour actualisé devient encore plus facile à imaginer, car l’enseignant récompensera (ou punira en conséquence) quiconque a été impliqué dans l’épisode, mais l’échelonnera en fonction de son éloignement du résultat final.

Par exemple, si le papier est passé de A à B à M qui l'a jeté à la poubelle, M devrait être puni le plus, puis B pour le lui avoir transmis et enfin la personne A qui participe toujours au résultat final mais moins que M ou B. Cela souligne également que plus il faut longtemps (en fonction du nombre d'étapes) pour commencer dans un état et atteindre la poubelle, moins on sera récompensé ou puni, mais accumulera des récompenses négatives pour avoir pris plus d'étapes.

Appliquer un modèle à notre exemple

Comme notre exemple d'environnement est petit, nous pouvons appliquer chacun d'eux et montrer certains des calculs effectués manuellement et illustrer l'impact de la modification des paramètres.

Pour tout algorithme, nous devons d’abord initialiser la fonction de valeur d’état, V (s), et avons décidé de régler chacun d’eux sur 0, comme indiqué ci-dessous.

Ensuite, nous laissons le modèle simuler une expérience sur l'environnement en fonction de notre distribution de probabilité observée. Le modèle commence une feuille de papier dans des états aléatoires et les résultats de chaque action en vertu de notre politique sont basés sur nos probabilités observées. Ainsi, par exemple, supposons que les trois premiers épisodes simulés soient les suivants:

Avec ces épisodes, nous pouvons calculer nos premières mises à jour de notre fonction de valeur d'état en utilisant chacun des trois modèles donnés. Pour le moment, nous choisissons des valeurs alpha et gamma arbitraires égales à 0,5 afin de simplifier nos calculs manuels. Nous montrerons plus loin l'impact de cette variable sur les résultats.

Tout d'abord, nous appliquons la différence temporelle 0, le plus simple de nos modèles, et les trois premières mises à jour des valeurs sont les suivantes:

Alors, comment ont-ils été calculés? Comme notre exemple est petit, nous pouvons montrer les calculs à la main.

Alors, que pouvons-nous observer à ce stade précoce? Premièrement, l’utilisation de TD (0) semble injuste pour certains États, par exemple la personne D, qui, à ce stade, n’a rien gagné à ce que le document parvienne à la corbeille deux fois sur trois. Leur mise à jour n'a été affectée que par la valeur de la prochaine étape, mais cela souligne la manière dont les récompenses positives et négatives se propagent du coin vers les États.

Au fur et à mesure que nous prenons de nouveaux épisodes, les récompenses finales positives et négatives s’étendront de plus en plus loin dans tous les États. Ceci est indiqué grossièrement dans le diagramme ci-dessous où nous pouvons voir que les deux épisodes qui ont abouti à un résultat positif ont un impact sur la valeur des états Enseignant et G alors que le seul épisode négatif a puni la personne M.

Pour montrer cela, nous pouvons essayer plus d'épisodes. Si nous répétons les trois mêmes chemins déjà donnés, nous produisons la fonction de valeur d'état suivante:

(Veuillez noter que, dans cet exemple, nous avons répété ces trois épisodes pour des raisons de simplicité, mais le modèle réel comporterait des épisodes dont les résultats sont basés sur la fonction de probabilité de transition observée.)

Le diagramme ci-dessus montre les récompenses du terminal se propageant du coin supérieur droit vers les états. À partir de là, nous pouvons décider de mettre à jour notre politique car il est clair que la récompense finale négative passe par la personne M et que, par conséquent, B et C subissent un impact négatif. Par conséquent, sur la base de V27, pour chaque état, nous pouvons décider de mettre à jour notre stratégie en sélectionnant la valeur optimale suivante pour chaque état, comme indiqué dans la figure ci-dessous.

Cet exemple a deux causes d’inquiétude: la première est que la meilleure action de la personne A est de la jeter à la poubelle et d’obtenir une récompense négative. C'est parce qu'aucun des épisodes n'a visité cette personne et souligne le problème de bandit multi armé. Dans ce petit exemple, il y a très peu d'États, il faudrait donc de nombreux épisodes pour les visiter tous, mais nous devons nous en assurer.

La raison pour laquelle cette action est meilleure pour cette personne est qu’aucun des États terminaux n’a de valeur, mais plutôt que les résultats positifs et négatifs se trouvent dans les récompenses finales. Nous pourrions ensuite, si notre situation l'exigeait, initialiser la V0 avec des chiffres pour les états terminaux basés sur les résultats.

Deuxièmement, la valeur d'état de la personne M bascule entre -0,03 et -0,51 (environ) après les épisodes et nous devons déterminer pourquoi cela se produit. Ceci est causé par notre taux d'apprentissage, alpha. Pour l'instant, nous n'avons introduit que nos paramètres (le taux d'apprentissage alpha et le taux d'actualisation gamma), mais nous n'avons pas expliqué en détail leur impact sur les résultats.

Un taux d’apprentissage élevé peut entraîner une oscillation des résultats, mais à l’inverse, il ne devrait pas être trop faible pour que la convergence prenne une éternelle. Ceci est montré plus loin dans la figure ci-dessous qui montre le (s) V total (s) pour chaque épisode et nous pouvons clairement voir comment, bien qu’il existe une tendance générale à la hausse, elle varie entre les épisodes. Une autre bonne explication du taux d’apprentissage est la suivante:

«Dans le jeu de golf, lorsque la balle est loin du trou, le joueur frappe très fort pour se rapprocher le plus possible du trou. Plus tard, lorsqu'il atteint la zone signalée, il choisit un autre bâton pour obtenir une frappe courte précise.

Donc, ce n’est pas qu’il ne pourra pas mettre la balle dans le trou sans choisir le bâton de tir court, il peut envoyer la balle devant la cible deux ou trois fois. Mais ce serait mieux s'il joue de manière optimale et utilise la bonne quantité de puissance pour atteindre le trou. "

Épisode

Il existe des méthodes complexes pour déterminer le taux d’apprentissage optimal pour un problème, mais, comme pour tout algorithme d’apprentissage automatique, si l’environnement est suffisamment simple, vous parcourez différentes valeurs jusqu’à ce que la convergence soit atteinte. Ceci est également connu sous le nom de gradient stochastique. Dans un récent projet RL, j'ai démontré l'impact de la réduction de l'alpha à l'aide d'un visuel animé, comme illustré ci-dessous. Cela démontre l’oscillation lorsque alpha est grande et comment elle est lissée à mesure que l’alpha est réduit.

De même, notre taux d'actualisation doit être compris entre 0 et 1, souvent considéré comme proche de 0,9. Le facteur de réduction nous indique l’importance des avantages futurs; un grand nombre indique qu'elles seront considérées comme importantes, alors que si l'on se rapproche de 0, le modèle considérera de moins en moins les étapes futures.

Avec ces deux éléments à l'esprit, nous pouvons modifier à la fois l'alpha de 0,5 à 0,2 et le gamma de 0,5 à 0,9 et nous obtenons les résultats suivants:

Parce que notre taux d'apprentissage est maintenant beaucoup plus petit, le modèle prend plus de temps à apprendre et les valeurs sont généralement plus petites. Le plus visiblement est pour l'enseignant qui est clairement le meilleur état. Cependant, ce compromis pour un temps de calcul accru signifie que notre valeur pour M n'oscille plus autant que précédemment. Nous pouvons maintenant voir ceci dans le diagramme ci-dessous pour la somme de V (s) suivant nos paramètres mis à jour. Bien que ce ne soit pas parfaitement lisse, le total des V augmente lentement à un taux beaucoup plus lent qu'auparavant et semble converger comme nous le voudrions, mais nécessite environ 75 épisodes pour le faire.

Changer le résultat de l'objectif

Un autre avantage crucial de RL, que nous n’avons pas mentionné en détail, c’est que nous contrôlons un peu l’environnement. Actuellement, les récompenses sont basées sur ce que nous avons décidé de faire pour que le modèle obtienne un résultat positif en un minimum d'étapes.

Cependant, supposons que l’enseignant ait changé et que le nouveau n’a pas dérangé les élèves de jeter le papier à la poubelle aussi longtemps qu’il l’atteint. Nous pourrons alors changer notre récompense négative autour de cela et la politique optimale changera.

Ceci est particulièrement utile pour les solutions d’entreprise. Par exemple, supposons que vous planifiez une stratégie et que vous sachiez que certaines transitions sont moins souhaitées que d’autres, cela peut alors être pris en compte et modifié à volonté.

Conclusion

Nous avons maintenant créé un modèle simple d'apprentissage par renforcement à partir des données observées. Beaucoup de choses pourraient être améliorées ou approfondies, y compris l'utilisation d'un modèle plus complexe, mais ceci devrait constituer une bonne introduction pour ceux qui souhaitent essayer de les appliquer à leurs propres problèmes de la vie réelle.

J'espère que vous avez apprécié la lecture de cet article. Si vous avez des questions, n'hésitez pas à commenter ci-dessous.

Merci

Sterling