Apprentissage sans modèle

Limitations

Connaissance du modèle

Dans la partie précédente, nous avons vu comment il était possible de trouver la fonction de valeur et la politique optimale d'un MDP.

Cependant, nous avons pour cela supposé que nous avions accès à \(P\) (la fonction de transition) et \(R\) (la fonction de récompense).

Dans la pratique, nous n'avons pas souvent accès à ces fonctions. Nous allons aborder dans cette partie une autre approche pour résoudre un MDP : l'apprentissage sans modèle.

Comme ils ont accès au modèle, on dit que les algorithmes présentés précédemment sont des algorithmes de planification (planning).

Nous allons maintenant supposer que nous ne connaissons pas \(P\) et \(R\) (le modèle), et utiliser des algorithmes d'apprentissage (learning).

Épisodes

Idée

Et si nous réalisions des expériences en interagissant avec l'environnement ? Dans ce cas, nous collecterions des transitions du type:

$$(s_1, a_1, r_1, s_2, a_2, r_2, \dots, s_T, r_T)$$

Et utiliserions ces données pour apprendre!

Apprentissage épisodique

Fonction de valeur état-action (Q)

Pour améliorer notre politique, nous avons précédemment utilisé une estimation de sa fonction de valeur \(V\), puis appliqué une amélioration gourmande :

$$\pi(s) = \arg\max_a \sum_{s'} {\color{red} P(s'|s,a)} \left[ {\color{red} R(a, s, s')} + \gamma V(s') \right]$$

Cette approche ne fonctionnera pas si nous ne connaissons pas le modèle de l'environnement, c'est à dire \({\color{red} P(s'|s,a)}\) et \({\color{red} R(a, s, s')}\).

Nous allons donc utiliser une légère modification de la fonction de valeur, et introduire la fonction de valeur état-action \(Q\) définie par :

$$Q(s,a) = \sum_{s'} P(s'|s,a) \left[R(a, s, s') + \gamma V(s') \right]$$

Contrairement à \(V\), l'action \(a\) est fixée comme un paramètre de \(Q\), et ne dépend pas de la politique.

Ainsi, si on connaît \(Q^*\) (la fonction de valeur état-action optimale), on peut définir une politique optimale de la manière suivante :

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

Exemple du casse-brique

Par exemple, pour un état donné d'un jeu de casse brique, la fonction de valeur état-action pourrait prendre les valeurs suivantes :

Les deux ingrédients suivants formeront la trame du fonctionnement d'un apprentissage sans modèle :

1) Estimer \(Q\) (la fonction de valeur état-action)
2) Utiliser \(Q\) pour améliorer la politique

Politique epsilon-gourmande

Comment obtenir les données qui nous permettront d'estimer \(Q\) ? On peut: 

  • Exploiter les données que l'on a déjà, en utilisant la politique courante,
  • Explorer de nouvelles actions, en utilisant une politique différente.

L'approche la plus classique (et simple) à ce problème est d'utiliser une politique \(\epsilon\)-gourmande, qui choisit l'action optimale avec une probabilité \(1-\epsilon\), et une action aléatoire avec une probabilité \(\epsilon\).

Nous avons maintenant la trame d'un algorithme capable d'apprendre la politique optimale sans connaissance du modèle :

  1. Initialiser \(Q(s,a)\) arbitrairement
  2. Répéter jusqu'à convergence :
    1. Choisir \(a\) selon la politique \(\epsilon\)-gourmande définie par \(Q\)
    2. Observer \(r\) et \(s'\)
    3. Mettre à jour \(Q(s,a)\)

Cette dernière étape de mise à jour de \(Q\) peut se faire de différentes manières, nous allons en voir deux.

Approches tabulaires

Dans cette partie, nous allons supposer que l'espace des états et l'espace des actions sont finis, et que nous pouvons donc stocker \(Q\) dans un tableau (c'est ce que l'on appelle une approche tabulaire).

\(Q(s,a)\)\(a_1\)\(a_2\)\(a_3\)
\(s_1\)
\(s_2\)
\(s_3\)

En Python, une manière de représenter \(Q\) est d'utiliser un dictionnaire dont les clés sont des tuples état/action:

q: dict = {}
s: int = 12
a: int = 3
q[(s, a)] = 0.0

Monte-Carlo

Présentation

Si on réalise des expériences en interagissant avec l'environnement, on peut collecter des transitions du type :

$$(s_1, a_1, r_1, s_2, a_2, r_2, \dots, s_T, r_T)$$

Si on arrive dans un état terminal, on peut calculer le retour obtenu pour chacun des états \(s_t\) visités. Ce retour est un vrai échantillon de retour possible que l'on peut obtenir en suivant la politique à partir de \(s_t, a_t\), et donc un échantillon de \(Q(s_t, a_t)\) :

$$G_t = \sum_{k=t}^T \gamma^{k-t} r_k$$

Voici un diagramme qui résume la manière dont ces estimations sont obtenues :

\(i\) désigne ici le numéro de l'épisode

L'idée de l'algorithme de Monte-Carlo est de mettre à jour \(Q\) en utilisant ces retours :

$$Q(s_t, a_t) \leftarrow \frac{1}{N(s_t, a_t)} \sum_{i=1}^{N(s_t, a_t)} G^i_t$$

Où \(N(s_t, a_t)\) est le nombre de fois où l'on a visité l'état \(s_t\) en choisissant l'action \(a_t\).

Algorithme de Monte-Carlo

Reinforcement learning: an introduction, second edition, page 123

Implémentation incrémentale

La moyenne \(\bar{x}_n\) de \(n\) valeurs \(x_1, \dots, x_n\), est :

$$\bar{x}_n = \frac{1}{n} \sum_{i=1}^n x_i$$

Et la moyenne \(\bar{x}_{n+1}\) de \(n+1\) valeurs \(x_1, \dots, x_n, x_{n+1}\), est :

$$\bar{x}_{n+1} = \frac{1}{n+1} \sum_{i=1}^{n+1} x_i$$

En sortant le terme \(x_{n+1}\), on peut réécrire cette moyenne :

$$\begin{split} \bar{x}_{n+1} & = \frac{1}{n+1} \sum_{i=1}^{n} x_i + \frac{1}{n+1} x_{n+1} \\ & = \frac{n}{n+1} \frac{1}{n} \sum_{i=1}^{n} x_i + \frac{1}{n+1} x_{n+1} \\ & = \frac{n}{n+1} \bar{x}_n + \frac{1}{n+1} x_{n+1} \end{split}$$

Ou encore:

$$\begin{split} \bar{x}_{n+1} & = \frac{n+1-1}{n+1} \bar{x}_n + \frac{1}{n+1} x_{n+1} \\ & = \bar{x}_n - \frac{1}{n+1} \bar{x}_n + \frac{1}{n+1} x_{n+1} \\ & = \bar{x}_n + \frac{1}{n+1} (x_{n+1} - \bar{x}_n) \end{split}$$

Il n'est donc pas nécessaire de stocker toutes les valeurs \(x_i\) pour calculer la moyenne, il suffit de stocker la moyenne précédente \(\bar{x}_{n}\), et le nombre de valeurs \(n\) puis d'appliquer cette mise à jour.

Différence temporelle: SARSA et Q-Learning

Présentation

Dans Monte-Carlo, nous avons vu comment mettre à jour \(Q\) en utilisant des retours obtenus en fin d'épisode.

Cette approche nécessite d'atteindre un épisode terminal (si l'environnement en dispose) pour mettre à jour \(Q\).

Idée des différences temporelles: Et si on utilisait une estimation de \(Q\) basé sur l'équation de Bellman ?

Par exemple, après avoir réalisé une transition \((s, a, r, s', a')\), on pourrait produire une nouvelle estimation de \(Q\), deux possibles candidats seraient :

Méthode SARSA: On utilise \(a'\), l'action qu'on a vraiment réalisée à l'étape suivante :

$$G = r + \gamma Q(s', a')$$

Méthode Q-Learning: On utilise \(a^*\), l'action optimale à l'étape suivante :

$$G = r + \max_{a^*} Q(s', a^*)$$

Erreur de différence temporelle

On peut alors mettre à jour notre estimation dans la direction du nouvel échantillon, en utilisant un taux d'apprentissage \(\alpha\) :

$$Q(s, a) \leftarrow Q(s, a) + \alpha {\color{blue} [G - Q(s, a)]}$$

Cette formule met à jour \(Q\) dans la direction \(G\), en utilisant un taux d'apprentissage \(\alpha\) (compris entre \(0\) et \(1\)), qui permet de contrôler l'importance de cette mise à jour.

Le terme écrit en bleu dans l'équation ci-dessus est appellé l'erreur de différence temporelle (ou TD error), elle représente un "correctif" à apporter à notre estimation de \(Q\) :

$$\delta = G - Q(s, a)$$

On peut remarquer que la forme:

$$Q(s, a) \leftarrow Q(s, a) + \alpha [G - Q(s, a)]$$

Est similaire à la mise à jour incrémentale vue précédemment, si on avait \(\alpha = \frac{1}{n+1}\).

SARSA

SARSA est un algorithme de différence temporelle qui utilise l'estimation de \(Q\) suivante :

Reinforcement learning: an introduction, second edition, page 152

Q-Learning

Q-Learning est un algorithme de différence temporelle qui utilise l'estimation de \(Q\) suivante :

Reinforcement learning: an introduction, second edition, page 153

Q-Learning utilise la supposition que la politique utilisée pour générer les transitions est gourmande par rapport à \(Q\). Or, en réalité, on utilise souvent une politique \(\epsilon\)-gourmande pour garder de l'exploration.

C'est la différence avec SARSA, qui utilise la politique courante pour générer les estimations.

Pour cette raison, on dit que SARSA est un algorithme on-policy et que Q-Learning est un algorithme off-policy.

TD 2