Cette série d’articles a pour but de vous aider à comprendre comment fonctionne le reinforcement learning.

Qu’est-ce que le reinforcement learning ?

Introduction

Le reinforcement learning (RL) ou l’apprentissage par renforcement est un sous domaine du machine learning. Cela consiste pour un agent à apprendre les meilleures actions à effectuer dans un environnement de façon à maximiser une récompense quantitative au cours du temps.

L’intuition qu’il y a derrière cette définition est simple : un agent apprend en explorant son environnement, il va interagir avec et recevoir des « récompenses », positives ou négatives, découlant de ses actions.

Cela ne vous rappelle rien ? c’est un peu notre façon naturelle d’apprentissage. Prenons un exemple avec un amateur de nourriture. La personne se rend au Mexique et va tester les différents plats du pays. Le Mexique étant connu pour ses plats épicés, au début la personne va tester des plats pas/peu épicés ou modérés et va se régaler (on peut dire qu’elle reçoit une récompense de +10).

Si la personne tests d’autres types de plats très épicés, elle risque de perdre le côté « plaisir » et risque d’avoir la bouche en feu, on peut dire qu’elle reçoit une récompense de -10. C’est donc comme cela qu’on apprend en interagissant avec notre environnement.

Voici un exemple des plus excitants lorsqu’il s’agit de RL : ATARI et Deep Mind :

Comme vous pouvez le voir sur cette vidéo, l’algorithme ne connait pas les règles du jeu et ne sait pas ce que les commandes du jeu font exactement. Au bout de 120 minutes d’entrainement l’algorithme joue comme un pro mais c’est au bout de 2h d’apprentissage que l’algorithme surpasse nos attentes et creuse un tunnel au-dessus du mur pour battre le jeu.

Il existe de multiples champs d’application de l’Apprentissage par Renforcement. A titre d’exemples, cela a déjà été utilisée pour :

• Vaincre le champion du monde du jeu de GO (toujours une prouesse de DeepMind, documentaire que vous pouvez retrouver ici)
• Faire marcher un robot
• Gérer un portefeuille d’investissements
• Jouer à des jeux Atari (ou autre) avec de meilleurs performances qu’un humain. (Five de Open AI pour dota 2 par exemple)

Rapidement pour nous situer, vous pouvez voir le RL comme une sous-catégorie du ML, au même titre que l’apprentissage supervisée ou l’apprentissage non supervisé.

Différence entre le RL et autres apprentissages

• En RL, il n'y a pas de superviseur seulement un signal de récompense ou un nombre réel qui indique à l'agent à quel point son action a été bonne ou mauvaise.
• Les retours (feedbacks) de l'environnement peuvent être retardés, ils ne sont pas nécessairement instantanés. Par exemple, lorsqu’on est dans un labyrinthe, on peut passer du temps à explorer les différentes voies jusqu’à finir par atteindre la sortie. Il nous aura fallu un certain temps pour réaliser quelles étaient les bonnes et les mauvaises actions qu’on a prises.
• Le temps est très important en RL (on traite donc des données séquentielles)
• L’agent impact l’environnement dans lequel il se trouve. Cela à une conséquence donc sur les données qu’il peut recevoir.

Formalisation du problème

Dans la définition ci-dessus nous avons parlé d’environnement, d’action ou encore de récompense. Commençons par reprendre ces termes énoncés plus haut et formalisons tout cela.

Rewards (récompenses)

Une récompense ou « reward » Rₜ est un scalaire qui représente un feedback de comment s’en sort notre agent à un temps t. L’objectif de notre agent va être de maximiser nos récompenses cumulées (cumulative reward).

En effet, le reinforcement learning se base justement sur l’hypothèse de récompense :

Tout objectif peut être décrit comme la maximisation des récompenses cumulatives attendues.

C’est-à-dire que dans le cas d'un robot que l’on cherche à faire marcher, nous allons lui attribuer une récompense positive pour avancer sans tomber et une récompense négative lorsqu’il tombe. Il va ainsi associer la marche à une victoire et le fait de tomber à une perte. On cherche alors à maximiser ses récompenses cumulées de façon à ce qu’il marche au cours de la période choisie sans tomber.

A noter que dans certain cas, une récompense immédiate à moins d’importance qu’une future récompenses globales, dans ces cas-là, il peut être plus intéressant de sacrifier une récompense immédiate dans le but de maximiser notre future récompense globale.

Agent et environnement

A chaque temps t, un agent va :

• Exécuter une action Aₜ
• Recevoir des observations de l’environnement Oₜ
• Recevoir une récompense Rₜ

L’environnement lui va :

• Recevoir une action Aₜ
• Émettre des observations Oₜ₊₁
• Émettre la récompense Rₜ₊₁

Prenons un exemple (très réducteur) de la voiture autonome (notre agent) sur la voie publique (notre environnement). Au tout début, lorsqu’on initialise notre environnement nous allons récupérer des observations : combien de voitures se trouvent devant nous, à quelle distance se trouve notre destination, combien de piétons nous pouvons observer etc. Par rapport à ses observations, notre agent va décider d’entreprendre une action : avancer, tourner à droite, tourner à gauche, s’arrêter ou encore reculer. A chaque action Aₜ, notre agent va recevoir des observations Oₜ émises par notre environnement et une récompense Rₜ, positive s’il se rapproche de sa destination finale, négative s’il écrase un piéton (juste un exemple, ne laissons pas certains fantasmes devenir réalités). L’environnement lui va recevoir l’action Aₜ, évoluer et émettre l’observation Oₜ₊₁ et la récompense Rₜ₊₁ jusqu’à éventuellement aboutir à un enchainement d’observations, de récompenses et d’actions au cours du temps comme suit :

Hₜ = O₁,R₁,A₁, ... , Aₜ,Rₜ,Oₜ

C’est ce qu’on va appeler l’« history » ou notre historique et cela représente toutes nos variables observables à chaque temps t.

Ce qu’il va se passer ensuite va donc dépendre de notre historique. Intuitivement, nous pouvons penser que c’est une bonne donnée à prendre en compte pour savoir quelle action prendre par la suite. En réalité, son utilisation est plus complexe. A la place, nous allons utiliser une fonction de l’history : l’état (state).

L’état ou state est l’information utilisée pour déterminer l’étape suivante. Formellement, c’est une fonction de l’history :

Sₜ = f(Hₜ)

Donc jusqu’ici on se dit, au lieu d’utiliser toute la suite d’O, R et A, nous allons utiliser une seule valeur à la place qui va nous aider à déterminer l’action suivante.

État de l’environnement et état d’un agent

Pour être plus exacte, il existe plusieurs définitions de l’état (state), nous allons en reprendre 3.

Environment State

C’est simplement toutes les informations du point de vue de l’environnement qu’on va utiliser pour déterminer ce qui va se passer par la suite. i.e. : les données pour les prochaines observations/rewards qu’on va donner à l’agent.

A noter que l’environment state Sᵉₜ n’est pas toujours visible du point de vue de l’agent ; même si celui-ci est visible, il peut contenir des informations non pertinentes : imaginez un robot qui apprend à marcher, il ne connait pas forcement la température à l’autre bout de la planète, il ne voit que ce qui se trouve devant lui, même si la température est connue, ça ne lui servira pas à grand-chose.

Agent State

Pour construire notre algorithme, l’environment state n’est pas très utile pour l’instant : on ne le voit pas forcement. A la place nous allons utiliser l’agent state ou l’état de notre agent Sᵃₜ.

L’agent state, c’est tout simplement toutes les informations stockées par notre agent : ce qu’il a vu/fait jusqu’à présent ou toutes autres informations que l’on décide de garder. C’est toutes ces informations là que nous allons utiliser pour choisir notre prochaine action.

Non seulement c’est à nous de choisir ce que l’on va mettre dans l’agent state Sᵃₜ mais c’est aussi ce que l’on va utiliser dans nos algorithmes de reinforcement learning.

Information State

La dernière définition que nous allons donner pour l’état est plus mathématique.

Un « état de Markov », Markov state ou information state, est un état qui contient toutes les informations utiles à partir de l’history. Un état Sₜ est Markovien si et seulement si :

ℙ[Sₜ₊₁| Sₜ] = ℙ[Sₜ₊₁ | S₁,…,Sₜ]

Ce qu’on veut dire par là est que le futur est indépendant du passé si on connait le présent.

En d’autres mots, la prédiction du futur à partir du présent n'est pas plus précise parce qu'on utilise des éléments d'informations supplémentaires qui concerne le passé. En effet, nous sommes dans un cas où toute l'information utile pour la prédiction du futur est contenue dans l'état présent. On peut donc « jeter » toute l’history (ce qui vient avant notre état) et seulement utiliser l’état actuel pour prédire le futur.
Nous appelons cela l'hypothèse de Markov.

Par définition l’environment state est bien un Markov state. En ce qui concerne l’agent state, c’est à nous de choisir comment nous voulons le construire et donc à nous de faire en sorte qu’il soit Markovien.

Cela nous mène vers quelques cas dans la formalisation de notre problématique de RL :

Fully observable environnent

Autrement dit les cas où les environnements sont entièrement observables. Dans ce type d’environnement, l’agent connait directement toutes les variables issues de l’environment state Sᵉₜ. Dans ce cas nous avons :

Oₜ = Sᵃₜ = Sᵉₜ

Puisque l’agent state est égale à l’environment state, et que l’environment state est Markovien, alors l’agent state est aussi un état de Markov.

Cette situation où l’on peut tout observer est assez idéaliste. C’est ce qu’on appelle un processus de décision Markovien (Markov decision process) ou MDP.

Partially observable environnent

Ce sont les cas où l’agent observe indirectement l’environnement. Nous pouvons prendre le cas d’un agent qui joue au poker qui connait uniquement ses cartes ainsi que les cartes au milieu de la table mais pas les cartes de ses adversaires.

Cette situation est bien plus réaliste que la première, c’est ce qu’on appelle un processus de décision markovien partiellement observable (ou POMDP pour partially observable Markov decision process)

Dans ce cas-là, évidemment l’agent state n’est plus égale à l’environment state et nous devons construire la représentation de notre agent state.

Comment construire Sᵃₜ ? le plus simple serait de reprendre tout l’history et de nous rappeler de tout ce qui s’est passé pour se baser dessus et en sortir notre prochaine action.

D’autres approches un peu plus recherchées existent. Une serait de construire des probabilités sur l’état de l’environnement et l’utiliser pour prévoir notre future action. Une autre serait d’utiliser une combinaison linéaire entre les observations passées et les dernières actions effectuées, cela nous donne un nouvel état.

Dans nos prochains cours, nous allons beaucoup parler des MDP, cela nous servira même pour le cas des POMDP.

Les composants d’un agent de RL

Pour l’instant nous avons seulement formaliser le problème de RL. Avant de s’attaquer à sa solution, regardons de plus près ce qui compose un agent de reinforcement learning.

Un agent peut être composer d’un ou plusieurs de ces composants :

• Policy (une politique ou une stratégie)
• Value function (combien nous rapporte chaque state ou chaque action)
• Model (une prédiction de la représentation de l’environnement qui est faite par l’agent)

A noter que l’agent peut être composé d’autres choses mais ceux cité au-dessus sont les principaux.

Avant de définir chaque composant cité ci-dessus, prenons un exemple concret. Voici un jeu : le but est qu’un taxi dépose son passager à une certaine localisation.

• Notre agent, le taxi peut avoir les actions suivantes: prendre à droite, à gauche, monter ou descendre.
• A chaque étape, la reward est de -1
• Nous définissons notre state comme la position de l’agent.

Voici à quoi ressemble notre jeu :

Policy

C’est globalement une stratégie que va suivre l’agent. Elle va simplement mapper les states dans lesquelles nous sommes vers des actions que l’agent va réaliser. C’est-à-dire que pour chaque state, elle va associer une action.

Donc d’après la policy de notre exemple ci-dessus, si nous sommes dans le state (0,0), l’action à prendre est « descendre». Ce sont donc les flèches qui représentent la policy.

Autre exemple avec la voiture autonome, si je suis dans l’état ou le feu est rouge, je m’arrête. Si je suis dans l’état ou le feu est vert, j’avance. On associe donc à chaque état -> une action.

On pourrait choisir d’avoir une policy déterministe, où notre action est une fonction d’un state donné :

a = π(s)

Tout comme nous pouvons partir sur une policy stochastique où :

π(a|s) = ℙ[Aₜ=A| Sₜ=s]

Value function

C’est simplement une prédiction de notre future récompense (reward). C’est principalement utilisé pour savoir si un état s et meilleur qu’un autre s’ et cela pour sélectionner l’action qui nous donnera donc le meilleur state.

Cette value function suit une certaine policy car celle-ci dépend de la stratégie que notre agent suit.

Formellement, la value fonction est définie comme suit :

Vπ(s) = 𝔼π[Rₜ₊₁ + γ Rₜ₊₂ + γ² Rₜ₊₃ + … | Sₜ=s]

Première question que vous vous poser si vous n’avez jamais vu cette expression est : que représente γ ?

Ici γ va représenter notre discount.

L’idée dernière un facteur de discount est de donner moins (ou plus) de poids au reward du futur.

Principalement car les actions lointaines dans le temps sont moins probables d’arriver qu’une action qui est moins lointaine. En effet, il y a plus d’incertitude dans le futur, nous attribuerons donc aux futures actions moins (ou plus dans d'autres cas) de poids en fonction de la valeur de γ.

Nous allons détailler cette notion et notamment ce que j'ai mis entre parenthèse dans la suite du cours (Partie 2 - Processus de décision Markoviens).

Dans notre exemple plus haut, la value function pour la policy donnée :

Model

Dans certain cas, pour savoir quelle action serait le mieux, l’agent peut avoir besoin de ce que l’environnement va faire par la suite. C’est le rôle du modèle.

Il existe deux types de modèle :

P : qui va prédire le prochain state

R : qui va prédire la prochaine reward (on parle bien de récompense imminente et non cumulée)

Voila a quoi ressemblerai notre model pour le jeu :

Pour l’instant nous n’allons pas nous étaler sur ce sujet car chaque environnement nécessite une modélisation propre à lui seul.

Problématiques en RL

Exploration et Exploitation

Avec ce qu’on a vu jusqu’à présent, on sait qu’un agent va mener des actions dans son environnement, lequel va nous soumettre de nouvelles observations et une récompense. Une problématique va voir le jour ici, nous allons avoir le choix entre soit explorer notre environnement, ce qui va nous donner plus d’informations en général et nous faciliter par la suite la prise de décision pour une action, soit directement exploiter les informations que nous avons pour maximiser notre reward.

Vous l’avez surement compris, les deux sont important et le but et de trouver un équilibre entre l’exploration et l’exploitation.

Prédiction et contrôle

Autre problématique que nous allons avoir, le choix entre la prédiction et le contrôle.

La prediction consiste à évaluer le futur en utilisant une policy donnée.

Le control consiste à optimiser le futur en trouvant la meilleure policy.

--

Nous devons évaluer toutes nos policy pour trouver la meilleure.

Et voici notre introduction au Reinforcement Learning qui prend fin. J'espère que vous avez apprécié cette première partie.

N’hésitez pas à me contacter pour toute question/remarque ou simplement pour discuter!

Photo by Alex Knight on Unsplash
Illustrations by Kamélia Laghzaouni