En apprentissage par renforcement, un agent interagit avec un environnement. Le temps est classiquement
découpé en étapes.
À chaque étape, l'agent choisit une action \(a_t\), qui est envoyée à l'environnement. L'environnement
renvoie une récompense \(r_{t+1}\) et une observation de l'état \(s_{t+1}\).
Exemples
Jeu de Morpion
État: configuration du plateau de jeu
Action: coup joué
Récompense: \(0\) tant que la partie n'est pas terminée, \(1\) si le joueur gagne, \(-1\) s'il perd.
La récompense est latente, il faut jouer une partie pour l'obtenir. C'est une des difficultés de
l'apprentissage par renforcement!
Jeu ATARI
État: les pixels de l'écran
Action: boutons appuyés sur la manette
Récompense: la variation de score du jeu (par exemple, \(1\) lorsque le score augmente, \(-1\) lorsqu'il diminue)
Conduire un Kart
État: position et orientation du kart sur la piste, vitesse du kart
Action: orientation du volant, accélération
Récompense: \(0\) en permanence, et \(1\) lorsqu'on franchit la ligne d'arrivée
Un exemple introductif
Cet exemple est une intruduction d'illustration permettant de comprendre intuitivement le fonctionnement
d'un processus de décision markovien.
Présentation
Supposons que l'on joue à un jeu. Nous sommes dans une salle \(s_0\), et on vous propose les choix suivants:
Lancer une pièce (action \(a_1\))
Si c'est face, vous gagnez 2 € et allez dans la salle \(s_1\)
Si c'est pile, vous perdez 1 € et allez dans la salle \(s_2\)
Lancer un dé (action \(a_2\))
Si c'est un 6, vous gagnez 20 € et le jeu s'arrête
Sinon, vous allez dans la salle \(s_3\)
De votre connaissance du jeu (et de votre capacité à y jouer), vous pensez pouvoir gagner 2 € à partir de
la salle \(s_1\), 3 € à partir de la salle \(s_2\), et perdre 1 € à partir de la salle \(s_3\).
Quelle action choisir ?
Représentation graphique
Une solution intuitive
La solution à ce problème est assez intuitive: il suffit de choisir l'action qui maximise le gain moyen:
Pour faire ce calcul, on a utilisé trois ingrédients:
En \({\color{blue} bleu}\), les probabilités de transition, qui sont définies par le jeu et indépendantes de notre stratégie
En \({\color{orange} orange}\), les récompenses
En \({\color{purple} violet}\), les estimations de gain futurs
Ces dernières (les estimations en \({\color{purple}violet}\)) jouent un rôle cruciales dans notre stratégie. On peut remarquer que:
Il n'est pas facile de les calculer, car elles dépendent de la stratégie, qui elle-même dépend des
estimations.
Par exemple, à l'issu du calcul, \(3\) serait une estimation des gains futurs obtenus à partir de \(s_0\).
Cette estimation pourrait à son tour bénéficier à un autre état qui aurait une transition vers \(s_0\).
Si on les connaît, on peut prendre une décision optimale.
Nous verrons dans le cours qu'on les retrouve sous le nom de fonction de valeur \(V\)
ou de fonction de valeur état-action \(Q\).
Principe d'optimalité de Bellman
On peut remarquer le principe suivant:
Si on connaît les estimations de gain futurs, c'est à dire si on sait se comporter de manière optimale
à partir des salles suivantes, on peut alors prendre une décision optimale à partir de la salle \(s_0\).
De manière générale, on appelle ce principe le principe d'optimalité de Bellman.
Processus de décision de Markov
Définition
Pour formaliser l'environnement, on utilisera ce qu'on appelle un
processus de décision markovien (MDP)
\((S, A, P, R)\), où:
\(S\) est un ensemble d'états,
\(A\) est un ensemble d'actions,
\(P\) est une fonction de transition
\(P(s' | s, a)\) est la probabilité de transition de l'état \(s\) à l'état \(s'\) en
effectuant l'action \(a\),
\(R\) est une fonction de récompense qui dépend de la transition effectuée \(R(s,a,s')\).
Exemple: un casse-brique
Prenons comme exemple le jeu du casse brique
On pourrait avoir:
\(S\) (états): la position et la vitesse de la balle, la position de la raquette, la position des briques,
\(A\) (actions): déplacer la raquette vers la gauche, déplacer la raquette vers la droite,
\(P\) (transition): la balle se déplace vers la gauche, la balle se déplace vers la droite,
\(R\) (récompense): \(0\) tant que la partie n'est pas terminée, \(1\) lorsqu'on casse une brique.
Politique
Définition
On appelle \(\pi\) la politique (policy en anglais), qui décrit pour chaque état l'action qui
sera réalisée.
La politique peut être :
Déterministe: \(a = \pi(s)\)
Aléatoire: \(\pi(a | s)\) est la probabilité de choisir l'action \(a\) dans l'état \(s\).
Dans ce cours, nous nous intéresserons principalement aux politiques déterministes.
Exemple: un casse-brique
Sur l'exemple du casse brique, la politique associerait alors à un état une action correspondante :
Retour
En suivant une politique, on obtient alors une série de récompenses \(r_1, r_2, \dots, r_T\). On peut donc
calculer le score suivant, que l'on appelera le "retour" (returns) :
$$G = \sum_{k=0}^{T} r_{k}$$
Ici, \(T\) est le nombre d'étapes d'un épisode se terminant à un état terminal \(s_T\).
Exemple: un casse-brique
Sur l'exemple du casse brique, on peut imaginer une récompense qui serait de \(0\) tant que la partie n'est pas
terminée, et de \(1\) lorsqu'on casse une brique.
Par exemple la première transition de l'état \(s_1\) à l'état \(s_2\) ne casserait aucune brique, provoquant une
récompense \(r_1 = 0\) :
Plus tard pendant le jeu, la transition de \(s_6\) à \(s_7\) casserait une brique, provoquant une récompense
\(r_6 = 1\) :
Le retour \(G\) étant la somme des récompenses \(r_i\) obtenues pendant la partie, il sera à la fin du jeu
égal au nombre de briques cassées (c'est le score).
Score de politique
En suivant une politique \(\pi\) donnée, il est possible d'obtenir un score. Cependant, ce score dépend
de facteurs aléatoires (par exemple, si l'environnement comporte une partie aléatoire comme un tirage de cartes).
C'est pour cela que, pour évaluer une politique, nous nous intéresserons à \(J(\pi) = \mathbb{E} [ G ]\),
qui est l'espérance de \(G\), que l'ont peut voir comme le retour moyen obtenu en suivant la politique \(\pi\).
La politique qui maximise \(J(\pi)\) est appelée la politique optimale.
Fonction de valeur
Définition
La fonction de valeur \(V^{\pi}\) est la fonction qui associe à un état \(s\) l'espérance
du score obtenu en suivant la politique \(\pi\) à partir de cet état :
$$V^{\pi}(s) = \mathbb{E} \left[ G | s_1 = s \right]$$
Exemple: un casse-brique
Par exemple, pour une politique bien entraînée, la fonction de valeur d'un jeu de casse brique qui débuterait
pourrait être le nombre de briques restantes :
Plus tard dans le jeu, la fonction de valeur serait plus faible, car il resterait moins de briques :
Dans une situation où la balle serait impossible à rattraper, la fonction de valeur pourrait
alors valoir \(0\) :
Récurisivité
Il est possible de réécrire l'équation de \(V\), en remarquant sa récursivité :
$$V^{\pi}(s) = \sum_{s'} P(s' | s, a) [R(s,a,s') + V^{\pi}(s')]$$
Avec \(a = \pi(s)\) l'action choisie par la politique.
Exemple: un casse-brique
Supposons que le casse-brique soit déterministe; dans ce cas un seul état futur est possible pour une action donnée,
(et donc \(P(s' | s, a) = 1\) pour cet état et \(0\) pour les autres).
En fonction de l'action choisie, la fonction de valeur dépendra alors de la récompense obtenue
(si une brique est cassée) et de la fonction de valeur de l'état d'arrivée :
Un autre exemple
Supposons qu'un étudiant ait le choix entre réviser et aller boire un verre, selon le modèle suivant :
Ici, \(S= \{ I, B, R, BR, BB, RR, F \}\) est l'ensemble des états. Les actions sont
\(A=\{ \text{reviser}, \text{boire}, \text{examen} \}\).
En suivant une politique qui consiste à boire, voici la fonction de valeur obtenue :
Avec une autre politique qui consiste à réviser, la fonction de valeur est différente :
Taux d'escompte
Dans un environnement qui ne termine jamais (ex: faire des tours de piste en kart), la somme des récompenses
peut être infinie.
De plus, on aimerait parfois donner plus d'importance aux récompenses proches dans le temps.
Pour faire cela, on utilise un facteur d'escompte, que l'on appellera \(\gamma\), et qui est un nombre entre \(0\) et \(1\).
Il est important que dans un MDP, l'état \(s_{t+1}\) ne dépende que de l'état \(s_t\), et pas des états précédents.
Autrement dit, le passé doit être "capturé" par l'état \(s_t\).
