# Q-learning

En intelligence artificielle, plus précisément en apprentissage automatique, le Q-learning est un algorithme d'apprentissage par renforcement. Il ne nécessite aucun modèle initial de l'environnement. La lettre 'Q' désigne la fonction qui mesure la qualité d'une action exécutée dans un état donné du système.

## Applications

Google DeepMind a réalisé un programme informatique qui joue à des jeux vidéos Atari 2600. Pour cela, ils ont appliqué le Q-learning avec de l'apprentissage profond. Cette technique s'appelle alors le "deep reinforcement learning" or "deep Q-learning". Cela fait l'objet d'un brevet.

## Description

Considérons un système quelconque : par exemple, un jeu vidéo, un robot qui doit s'évader d'un labyrinthe, ou encore un robot qui doit apprendre à tenir un œuf. Un agent (programme informatique, robot) doit alors apprendre à réaliser une tâche : gagner une partie de jeu vidéo avec le plus de points, s'évader d'un labyrinthe sans se faire attraper, tenir l’œuf le plus longtemps sans le casser. Le Q-learning permet d'apprendre une stratégie, qui indique quelle action effectuer dans chaque état du système. Par exemple, le robot peut apprendre d'aller à droite quand il se trouve sur la case (2, 3), mais d'aller en haut s'il se trouve sur la case (4, 6), etc. A chaque étape, l'agent reçoit une récompense immédiate qui est un nombre réel. Typiquement, l'agent peut recevoir 100 euros s'il est sorti du labyrinthe, ou s'il a gagné le jeu. L'agent reçoit -100 euros s'il est piégé, si l’œuf est cassé. C'est le concepteur de l'environnement qui choisit ces récompenses immédiates lorsqu'il modélise le système.
Plus précisément, le Q-learning apprend une fonction de valeur notée Q. Cette fonction Q estime le gain potentiel, c'est-à-dire la somme des récompenses Q(s,a) sur le long terme, apportée par le choix d'une certaine action a dans un certain état s en suivant une politique optimale. Cette fonction Q s'appelle fonction de valeur actions-états, puisqu'elle prend comme argument un état s et une action a. Par exemple, Q( être en (2, 3), aller à droite) est une estimation de la somme des récompenses si l'agent (programme informatique, robot) est dans la case (2, 3) et décide d'aller à droite. Lorsque cette fonction de valeur Q d'actions-états est connue ou apprise par l'agent, la stratégie optimale peut être construite en sélectionnant l'action à valeur maximale pour chaque état, c'est-à-dire en sélectionnant l'action a qui maximise la valeur Q(s,a) quand l'agent se trouve dans l'état s. Autrement dit, si l'agent est dans la case (2, 3), il regarde les valeurs Q( être en (2, 3), aller à droite), Q( être en (2, 3), aller à gauche), Q( être en (2, 3), aller à haut) , Q( être en (2, 3), aller à bas) et Q( être en (2, 3), rester sur place). Il choisit alors l'action qui maximise la valeur. Par exemple si
* Q( être en (2, 3), aller à droite) = 78€
* Q( être en (2, 3), aller à gauche) = 22€
* Q( être en (2, 3), aller à haut) = -5€
* Q( être en (2, 3), aller à bas) = 12€
alors l'agent décide d'aller à droite (car 78€ est le gain maximal).
Un des points forts du Q-learning est qu'il permet de comparer les récompenses probables de prendre les actions accessibles sans avoir de connaissance initiale de l’environnement. En d'autres termes, bien que le système soit modélisé par un processus de décision markovien (fini), l'agent qui apprend ne le connaît pas et l'algorithme du Q-learning ne l'utilise pas directement : en particulier, l'algorithme n'utilise jamais l'information des probabilités de passer d'un état s' à un état s en exécutant l'action a. Le Q-learning ne fait que interagir avec l'environnement.
Cette notion d’apprentissage par récompense a été introduite à l'origine dans la thèse de Watkins en 1989. C'est une variante de l'apprentissage par différence temporelle. Le Q-learning converge vers une stratégie optimale, c'est-à-dire qu'il conduit à maximiser la récompense totale des étapes successives.

## Algorithme

La situation consiste en un agent, un ensemble d'états $S$ et d'actions $A$. En réalisant une action $a\in A$, l'agent passe d'un état $s$ à un nouvel état $s'$et reçoit une récompense $r$ (c'est une valeur numérique). Le but de l'agent est de maximiser sa récompense totale. Cela est réalisé par apprentissage de l'action optimale pour chaque état. L'action optimale pour chaque état correspond à celle avec la plus grande récompense sur le long terme. Cette récompense est la somme pondérée de l'espérance mathématique des récompenses de chaque étape future à partir de l'état actuel. La pondération de chaque étape peut être $\gamma ^{\Delta t}$ où $\Delta t$ est le délai entre l'étape actuelle et future et $\gamma$ un nombre compris entre 0 et 1 (autrement dit $0\leq \gamma \leq 1$) appelé facteur d'actualisation.
L'algorithme calcule une fonction de valeur action-état :
    $Q:S\times A\to \mathbb {R}$
Avant que l'apprentissage ne débute, la fonction $Q$ est initialisée arbitrairement. Ensuite, à chaque choix d'action, l'agent observe la récompense et le nouvel état (qui dépend de l'état précédent et de l'action actuelle). Le cœur de l'algorithme est une mise à jour de la fonction de valeur. La définition de la fonction de valeur est mise à jour à chaque étape de la façon suivante :
    $Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \max _{a'}Q[s',a']\right)$
où $s'$est le nouvel état, $s$ est l'état précédent, $a$ est l'action choisie, $r$ est la récompense reçue par l’agent, $\alpha$ est un nombre entre 0 et 1, appelé facteur d'apprentissage, et $\gamma$ est le facteur d'actualisation. En d'autres termes, la valeur de $Q[s,a]$ est remplacée par une moyenne pondérée entre la précédente valeur de $Q[s,a]$ (pondérée par $1-\alpha$) et le gain attendu $r+\gamma \max _{a'}Q[s',a']$ (pondérée par $\alpha$).
Un épisode de l'algorithme finit lorsque $s_{t+1}$ est un état final. Toutefois, le $Q$-learning peut aussi être appliqué à des tâches non épisodiques. Si le facteur d'actualisation est plus petit que 1, la valeur action-état est finie même pour $\Delta t$ infini.
N.B. : Pour chaque état final $s_{f}$, la valeur de $Q(s_{f},a)$ n'est jamais mise à jour et maintient sa valeur initiale. Généralement, $Q(s_{f},a)$ est initialisé à zéro.

## Pseudo-code

Voici le pseudo-code du Q-learning.

## Influence des variables sur l'algorithme
### Facteur d'apprentissage

Le facteur d'apprentissage $\alpha$ détermine à quel point la nouvelle information calculée surpassera l'ancienne. Si $\alpha$ = 0, l'agent n'apprend rien. A contrario, si $\alpha$ = 1, l'agent ignore toujours tout ce qu'il a appris jusqu'à présent et ne considérera que la dernière information.
Dans un environnement déterministe, la vitesse d'apprentissage $\alpha _{t}(s,a)=1$ est optimale. Lorsque le problème est stochastique, l'algorithme converge sous certaines conditions dépendant de la vitesse d'apprentissage. En pratique, souvent cette vitesse correspond à $\alpha _{t}(s,a)=0.1$ pour toute la durée du processus.

### Facteur d'actualisation

Le facteur d'actualisation γ détermine l'importance des récompenses futures. Un facteur γ = 0 rendrait l'agent myope en ne considérant seulement les récompenses courantes, alors qu'un facteur γ proche de 1 ferait aussi intervenir les récompenses plus lointaines. Si le facteur d'actualisation γ est proche ou égal à 1, la valeur de $Q$ peut diverger.

## Convergence

En 1992, Watkins et Dayan ont proposé la première démonstration de convergence de l'algorithme de Q-learning. Le théorème est le suivant.
On suppose que les couples état-action $(s,a)$ apparaissent une infinité de fois (cf. p. 281 de ; attention, le vocabulaire utilisé est différent de celui du livre de Sutton et Barto ; un épisode pour Watkins et Dayan est une observation de l'état, la sélection de l'action, l'observation de la récompense et la mise à jour ; alors que dans le livre de Sutton et Barto, un épisode est une suite de mise à jour jusqu'à atteindre un état final). Notons $n^{i}(s,a)$ le numéro de l'étape où l'agent est dans l'état s et s'apprète à exécuter l'action a pour la $i$-ème fois. On suppose que les récompenses sont bornées, i.e. il existe une constante ${\mathfrak {R}}$ telle que la récompense $r_{n}$ à l'étape $n$ vérifie $|r_{n}|\leq {\mathfrak {R}}$. Concernant les facteurs d'apprentissage, en notant le facteur d'apprentissage $\alpha _{n}$ à l'étape $n$, on demande que :
* $0\leq \alpha _{n}<1$
* $\sum _{i=1}^{+\infty }\alpha _{n^{i}(s,a)}=+\infty$ pour tout couple état-action $(s,a)$
* $\sum _{i=1}^{+\infty }\alpha _{n^{i}(s,a)}^{2}<+\infty$ pour tout couple état-action $(s,a)$
Le théorème dit, alors que sous ces conditions, le tableau $Q_{n}$ à l'étape $n$, converge avec probabilité 1 vers le tableau optimal $Q^{*}$.

## Extensions et variantes
### Double Q-learning

Comme le Q-learning utilise l'estimateur max, le Q-learning surestime la valeur des actions et de fait, dans des environnements bruités, l'apprentissage est lent. Ce problème est résolu dans la variante appelée double Q-learning qui utilise deux fonctions d'évaluation $Q^{A}$et $Q^{B}$ apprises sur deux ensembles d'expériences différents. La mise à jour se fait de façon croisée :
    $Q_{t+1}^{A}(s_{t},a_{t})=Q_{t}^{A}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma ~Q_{t}^{B}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{A}(s_{t+1},a)\right)-Q_{t}^{A}(s_{t},a_{t})\right)$, et
    $Q_{t+1}^{B}(s_{t},a_{t})=Q_{t}^{B}(s_{t},a_{t})+\alpha _{t}(s_{t},a_{t})\left(r_{t}+\gamma ~Q_{t}^{A}\left(s_{t+1},\mathop {\operatorname {arg~max} } _{a}Q_{t}^{B}(s_{t+1},a)\right)-Q_{t}^{B}(s_{t},a_{t})\right).$
Comme la valeur estimée est évaluée en utilisant une autre politique, le problème de la surestimation est résolu. L'apprentissage de l'algorithme à ensemble peut être effectué en utilisant des techniques d'apprentissage profond, ce qui donne les réseaux DQN (deep Q-networks, réseaux profonds Q). On peut alors avoir le Double DQN, pour obtenir de meilleures performances qu'avec l'algorithme DQN original.

## Comparaison avec d'autres algorithmes

Q-learning est off-policy, c'est-à-dire que l'on distingue :
* la politique utilisée au cours de l'apprentissage, qui est généralement une politique ε-greedy ;
* la politique utilisée dans l'équation de mise à jour $Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \max _{a'}Q[s',a']\right)$. On y note le terme $\max _{a'}Q[s',a']$, i.e. on apprend en fonction de la meilleure action a' possible en s'. Ainsi, a' n'est pas sélectionnée via la politique d'apprentissage (typiquement, la politique ε-greedy).
Un algorithme similaire à Q-learning est l'algorithme SARSA mais la mise à jour, elle, utilise la politique en train d'être apprise. Dans SARSA, l'équation de mise à jour est $Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma Q[s',a']\right)$ où a' est l'action choisie depuis l'état s' par la politique en cours d'apprentissage. Q-learning apprend une politique optimale, alors que SARSA apprend une politique proche de l'optimale. L'exemple classique (du livre de Sutton et Barto) est celui d'un robot qui apprend à aller d'un point A à un point B près d'une falaise. Q-learning apprend une politique optimale qui longe la falaise, alors que SARSA apprend une politique plus sûre, où le robot est un peu plus loin du précipice. En résumé, Q-learning est plus efficace et SARSA plus sûr.