L'article doit être débarrassé d'une partie de sonjargon(janvier 2023).

Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible.

Discutez des points à améliorer enpage de discussion.

Enintelligence artificielle, plus précisément enapprentissage automatique, leQ-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^[1].

Google DeepMind a réalisé unprogramme informatique qui joue à desjeux vidéosAtari 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^[2].

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 unnombre 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éeQ. Cette fonction Q estime legain potentiel, c'est-à-dire la somme des récompensesQ(s,a) sur le long terme, apportée par le choix d'une certaine actiona dans un certain états 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'actiona qui maximise la valeurQ(s,a) quand l'agent se trouve dans l'états. 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 duQ-learning est qu'il permet de comparer les récompenses probables de prendre les actions accessibles^[pas clair] sans avoir de connaissance initiale de l’environnement. En d'autres termes, bien que le système soit modélisé par unprocessus de décision markovien (fini), l'agent qui apprend ne le connaît pas et l'algorithme duQ-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^[3]. C'est une variante de l'apprentissage par différence temporelle^[4]. LeQ-learning converge vers une stratégie optimale, c'est-à-dire qu'il conduit à maximiser la récompense totale des étapes successives^[5].

La situation consiste en un agent, un ensemble d'états${\displaystyle S}$ et d'actions${\displaystyle A}$. En réalisant une action${\displaystyle a\in A}$, l'agent passe d'un état${\displaystyle s}$ à un nouvel état${\displaystyle s^{\prime }}$et reçoit une récompense${\displaystyle 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${\displaystyle {\gamma }^{\mathrm{\Delta }t}}$ où${\displaystyle \mathrm{\Delta }t}$ est le délai entre l'étape actuelle et future et${\displaystyle \gamma }$ un nombre compris entre 0 et 1 (autrement dit${\displaystyle 0\le \gamma \le 1}$) appeléfacteur d'actualisation.

L'algorithme calcule une fonction de valeur action-état :

${\displaystyle Q:S\times A\to \mathbb{R}}$

Avant que l'apprentissage ne débute, la fonction${\displaystyle 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 unemise à jour de la fonction de valeur. La définition de la fonction de valeur est mise à jour à chaque étape de la façon suivante^[6] :

${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \underset{a^{\prime }}{max}Q[s^{\prime },a^{\prime }]\right)}$

où${\displaystyle s^{\prime }}$est le nouvel état,${\displaystyle s}$ est l'état précédent,${\displaystyle a}$ est l'action choisie,${\displaystyle r}$ est larécompense reçue par l’agent,${\displaystyle \alpha }$ est un nombre entre 0 et 1, appeléfacteur d'apprentissage, et${\displaystyle \gamma }$ est lefacteur d'actualisation. En d'autres termes, la valeur de${\displaystyle Q[s,a]}$ est remplacée par unemoyenne pondérée entre la précédente valeur de${\displaystyle Q[s,a]}$ (pondérée par${\displaystyle 1-\alpha }$) et le gain attendu${\displaystyle r+\gamma \underset{a^{\prime }}{max}Q[s^{\prime },a^{\prime }]}$ (pondérée par${\displaystyle \alpha }$).

Un épisode de l'algorithme finit lorsque${\displaystyle s_{t+1}}$ est un état final. Toutefois, le${\displaystyle 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${\displaystyle \mathrm{\Delta }t}$ infini.

N.B. : Pour chaque état final${\displaystyle s_f}$, la valeur de${\displaystyle Q(s_f,a)}$ n'est jamais mise à jour et maintient sa valeur initiale. Généralement,${\displaystyle Q(s_f,a)}$ est initialisé à zéro.

Voici lepseudo-code du Q-learning.

entrée : taux d'apprentissage α > 0 et un petit ε > 0, taux γ > 0sortie : tableau Q[., .]initialiser Q[s, a] pour tout état s non final, toute action a de façon arbitraire,          et Q(état terminal, a) = 0 pour toute action arépéter      //début d'un épisode       s := état initialrépéter               //étape d'un épisodechoisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy)exécuter l'action aobserver la récompense r et le nouvel état s'               Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)]               s := s'jusqu'à ce que s soit l'état terminal

Le facteur d'apprentissage${\displaystyle \alpha }$ détermine à quel point la nouvelle information calculée surpassera l'ancienne. Si${\displaystyle \alpha }$ = 0, l'agent n'apprend rien. A contrario, si${\displaystyle \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${\displaystyle {\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 à${\displaystyle {\alpha }_t(s,a)=0.1}$ pour toute la durée du processus^[7].

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${\displaystyle Q}$ peut diverger^[8].

En 1992, Watkins et Dayan ont proposé la première démonstration de convergence de l'algorithme de Q-learning^[9]. Le théorème est le suivant.

On suppose que les couples état-action${\displaystyle (s,a)}$ apparaissent une infinité de fois (cf. p. 281 de^[9] ; attention, le vocabulaire utilisé est différent de celui du livre de Sutton et Barto^[7] ; 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${\displaystyle 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${\displaystyle i}$-ème fois. On suppose que les récompenses sont bornées, i.e. il existe une constante${\displaystyle \mathfrak{R}}$ telle que la récompense${\displaystyle r_n}$ à l'étape${\displaystyle n}$ vérifie${\displaystyle |r_n|\le \mathfrak{R}}$. Concernant les facteurs d'apprentissage, en notant le facteur d'apprentissage${\displaystyle {\alpha }_n}$ à l'étape${\displaystyle n}$, on demande que :

• 
• ${\displaystyle \sum _{i=1}^{+\mathrm{\infty }}{\alpha }_{n^i(s,a)}=+\mathrm{\infty }}$ pour tout couple état-action${\displaystyle (s,a)}$
• pour tout couple état-action${\displaystyle (s,a)}$

Le théorème dit, alors que sous ces conditions, le tableau${\displaystyle Q_n}$ à l'étape${\displaystyle n}$, converge avec probabilité 1 vers le tableau optimal${\displaystyle Q^{\ast }}$.

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^[10] qui utilise deux fonctions d'évaluation${\displaystyle Q^A}$et${\displaystyle Q^B}$ apprises sur deux ensembles d'expériences différents. La mise à jour se fait de façon croisée :

${\displaystyle 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},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{Q}_t^A(s_{t+1},a)\right)-Q_t^A(s_t,a_t)\right)}$, et

${\displaystyle 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},\underset{a}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}}{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^[11].

Q-learning estoff-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${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma \underset{a^{\prime }}{max}Q[s^{\prime },a^{\prime }]\right)}$. On y note le terme${\displaystyle \underset{a^{\prime }}{max}Q[s^{\prime },a^{\prime }]}$, 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'algorithmeSARSA mais la mise à jour, elle, utilise la politique en train d'être apprise. Dans SARSA, l'équation de mise à jour est${\displaystyle Q[s,a]:=(1-\alpha )Q[s,a]+\alpha \left(r+\gamma Q[s^{\prime },a^{\prime }]\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^[12].

• SARSA, un autre algorithme d'apprentissage par renforcement mais on-policy

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé« Q-Learning »(voir la liste des auteurs).

• Portail de l’éducation

• Apprentissage

• Article à déjargoniser
• Portail:Éducation/Articles liés
• Portail:Société/Articles liés