Apprentissage par renforcement profond

Introduction

Motivation

Jusqu'ici, nous avons abordé les algorithmes suivants:

  • Programmation dynamique
    • Policy Iteration
    • Value iteration
  • Apprentissage sans-modèle
    • Monte-Carlo
    • SARSA
    • Q-Learning

Ces algorithmes se basent sur des représentations de \(Q(s, a)\) ou \(V(s)\) tabulaires (sous forme de tableau).

Limitations:

  • Des états et actions proches ayant le même effet seront représentés différemment,
  • Cette représentation explose si le nombre d'états est grand,
  • Ce n'est pas adapté aux représentations continues.

Approximation de fonction

Idée: nous allons donc essayer de représenter \(Q(s, a)\) ou \(V(s)\) par un approximateur de fonction (par exemple un réseau de neurones).

Apprentissage supervisé

Présentation

L'objectif de l'approximation de fonction est de trouver une fonction \(f(x)\) qui correspond le mieux aux données d'entrée :

C'est ce que l'on appelle l'apprentissage supervisé. Afin de trouver la fonction \(f\), on se restreint généralement à une certaine forme de fonction (par exemple un réseau de neuronnes) et on cherche les paramètres de cette fonction.

Si nous appelons ces paramètres \(w\), nous chercons donc à trouver \(w\) tel que \(f(x, w)\) soit le plus proche des \((x_i, y_i)\).

Par exemple, si \(f(x) = ax + b\), alors \(w = (a, b)\) sont les paramètres de \(f\) que l'on cherche.

Réseau de neurones

L'apprentissage supervisé peut fonctionner avec toute fonction \(f(x, w)\) que l'on peut imaginer, mais un choix est particulièrement populaire: les réseaux de neurones.

Un réseau de neurones peut être défini comme une famille de fonctions \(f(x, w)\) dont l'architecture provient à l'origine d'idées bio-inspirées (d'où le nom).

Perceptron

Les réseaux de neurones s'appuient sur des blocs de base appelés perceptrons :

  • Les entrées sont d'abord multipliées par des poids \(w_i\), puis additionnées,
  • Un biais est ajouté à la somme,
  • Le résultat est passé dans une fonction d'activation \(g\), qui est non-linéaire.

La sortie du perceptron est donc :

$$y = g(w_0 + \sum_{i=1}^n w_i x_i)$$

Perceptron multi-couches

Cette architecture de perceptron est alors répétée plusieurs fois avec une architecture en couches, on parle de perceptron multi-couches:

Fonction de perte

Comment définir ce que signifie "le plus proche" pour notre fonction? Il faut pour cela définir une métrique d'erreur, par exemple l'écart à la courbe:

Un score d'erreur peut alors être la moyenne de ces écarts pour tous les points de données:

$$\mathcal{L}(w) = \frac{1}{N} \sum_{i=1}^N \epsilon_i(w)$$

Ici, on appelle \(\mathcal{L}\) la fonction de perte que l'on cherche à minimiser.

Minimisation de la fonction de perte

On cherche donc \(w\) afin de minimiser la fonction de perte.

Pour un candidat initial des poids \(w\), on peut donc calculer \(\mathcal{L}(w)\), puis calculer les dérivées suivantes pour chaque \(w_i\) :

$$\frac{d \mathcal{L}}{d w_i}$$

L'ensemble de ces dérivées s'appelle le gradient de la fonction de perte, qui donnera une direction de descente.

Pour calculer le gradient, on pourrait utiliser toutes les données disponibles, mais cela peut être très coûteux.

C'est pour cette raison que l'on utilise en général un mini-batch, qui est en fait un échantillon de données, ce qui revient à approximer \(\mathcal{L}\) par :

$$\mathcal{L}(w) \approx \frac{1}{B} \sum_{i=1}^B \epsilon_i(w)$$

Où \(B\) est largement inférieur à \(N\), et les données sont prises dans un ordre aléatoire.

En résumé

Pour faire de l'apprentissage supervisé, nous avons donc besoin :

  • D'un jeu de données \(\mathcal{D} = ((x_1, y_1), \dots, (x_N, y_N))\),
  • D'un modèle de fonction \(f(x, w)\),
    • Par exemple: un réseau de neurones,
  • D'une fonction de perte \(\mathcal{L}(w)\),
    • Par exemple: la moyenne des carrés des erreurs ou la moyenne des valeurs absolues des erreurs,
  • D'un algorithme de minimisation de la fonction de perte,
    • Par exemple la bibliothèque PyTorch.

Actions discrète, état continu (DQN)

Présentation

Un des premiers algorithmes fructueux alliant apprentissage par renforcement et apprentissage profond est le Deep Q-Network (DQN).

Il a été proposé par DeepMind en 2013, et a été appliqué à des jeux Atari.

Playing Atari with Deep Reinforcement Learning (DQN)

papier original (DeepMind)

Représentation de Q

L'approche de DQN est similaire au Q-Learning, en remplaçant la représentation tabulaire de \(Q(s, a)\) par un réseau de la forme suivante :

On retrouve En entrée, l'état \(s\), qui peut être multi-dimensionnel dans la pratique, et en sortie l'ensemble des \(Q(s, a_i)\) pour chaque action possible \(a_i\).

Par exemple, si l'état est celui du casse-brique, et que les actions sont gauche ou droite, le réseau produira alors deux valeurs \(Q(s, \text{gauche})\) et \(Q(s, \text{droite})\) :

Politique

La politique à suivre est alors celle qui maximise le \(Q(s, a)\) pour l'état courant \(s\), et toutes les actions possibles \(a\) :

$$\pi(s) = \arg\max_a Q(s, a)$$

Cette approche fonctionne uniquement grâce au fait que l'action est discrète et que le nombre d'action est limité.

Replay Buffer

Le remplacement de la représentation tabulaire par un réseau de neurones à partir d'un algorithme type Q-Learning pose plusieurs problèmes:

Les données sont chères

Dans Q-Learning, elles ne sont utilisées qu'une fois!

Les données sont corrélées dans le temps

Les données sont prises dans un ordre séquentiel, si on considérait par exemple les \(N\) derniers états, ils auraient beaucoup de similarité.

C'est pour cette raison que l'on utilise un Replay Buffer, qui est une mémoire qui va permettre de stocker les données d'entrainement.

Le Replay Buffer contiendra des transitions de la forme \((s, a, r, s')\), où \(s\) est l'état courant, \(a\) l'action choisie, \(r\) la récompense obtenue, et \(s'\) l'état suivant.

Ce Replay Buffer constituera alors un jeu de données \(\mathcal{D}\) pour l'apprentissage supervisé.

Le Replay Buffer a une capacité limitée, les données les plus anciennes sont donc écrasées par les nouvelles.

Fonction de perte

Pour entraîner le réseau \(Q\), nous allons utiliser les données provenant du Replay Buffer. Pour un échantillon \((s_i, a_i, r_i, s'_i)\), on peut produire une valeur cible très similaire à celle du Q-Learning:

$$y_i = \biggl\{ \begin{array}{ll} r_i & \text{si s terminal} \\ r_i + \gamma \max_a Q(s'_i, a) & \text{sinon} \end{array}$$

Comme expliqué précédemment, il est alors possible d'utiliser une fonction de perte de ce type:

$$\mathcal{L} = \frac{1}{N} \sum_i | Q(s_i, a_i) - y_i |$$

L'estimation \(y_i\) s'appuie elle-même sur \(Q\). Notez bien que \(y_i\) est ici uniquement une valeur temporairement "figée" lors de l'entraînement (notamment, l'algorithme du gradient ne prend pas en compte le fait que \(y_i\) dépende des poids du réseau).

Algorithme DQN

Actions continues, état continu (DDPG)

Problème: que se passe-t-il si l'action est également continue? Il devient alors impossible de représenter \(Q\) à l'aide du réseau présenté précédemment.

C'est le problème auquel s'est attaqué DeepMind en 2015 avec l'algorithme Deep Deterministic Policy Gradient

Continuous control with deep reinforcement learning (DDPG)

papier original (DeepMind)

Archirecture acteur-critique

Idée: utiliser deux approximateurs de fonctions différents. Un pour la politique \(\pi\) et l'autre pour \(Q\).

On appelle cette représentation acteur-critique.

Entraînement de l'acteur

Comment entraîner les poids du réseau \(Q\) ?

On peut pour cela utiliser une méthode similaire à celle de DQN, en utilisant un Replay Buffer et les estimations suivantes:

$$y_i = \biggl\{ \begin{array}{ll} r_i & \text{si s terminal} \\ r_i + \gamma Q(s'_i, \pi(s'_i)) & \text{sinon} \end{array}$$

Ici, la maximisation \(\max_a Q(s, a)\) est remplacée par \(Q(s, \pi(s))\), qui est l'estimation de la valeur de l'action choisie par la politique actuelle.

L'estimation est faite différemment, mais on pourra utiliser la même fonction de perte que DQN:

$$\mathcal{L}_Q = \frac{1}{N} \sum_i | Q(s_i, a_i) - y_i |$$

Entraînement de la politique

L'objectif de l'amélioration de la politique est de maximiser la valeur, soit \(Q(s, \pi(s))\) :

Pour un état \(s_i\) donné, on peut donc utiliser la perte suivante :

$$\mathcal{L}_{\pi} = -Q(s_i, \pi(s_i))$$

On remarque que \(Q\) et \(\pi\) sont en synergie, ils ont besoin l'un de l'autre pour s'entraîner. Dans la pratique, cela pose des problèmes que nous n'aborderons pas ici.

Algorithme DDPG

TD 3