Jonathan Suru

Introduction Au Reinforcement Learning

Après avoir suivi la formation Hors-Série sur le Deep Reinforcement Learning proposée par FIDLE, j'ai décidé de compiler et de structurer ici les concepts fondamentaux de l'apprentissage par renforcement. L'objectif de cet article est de présenter de manière claire et ordonnée les bases théoriques et les premiers algorithmes qui constituent le socle de cette discipline.

Qu'est-ce que l'Apprentissage par Renforcement ?

L'Apprentissage par Renforcement (Reinforcement Learning, RL) est un paradigme d'apprentissage automatique où un agent apprend à prendre des décisions en interagissant avec un environnement. L'objectif est de maximiser une récompense cumulée au fil du temps. Ce processus est souvent résumé par la maxime : "You Win or You Learn!" (Soit vous gagnez, soit vous apprenez).

Imaginez un écureuil qui se déplace sur une grille. À chaque pas, elle doit choisir une action : aller à gauche, à droite, en haut ou en bas. Si elle atteint une case contenant de la nourriture, elle reçoit une récompense. Si elle tombe sur la case du loup, elle subit une pénalité. Sans carte ni instructions, l’écureuil apprend progressivement, par essais et erreurs, à éviter le danger et à maximiser ses chances de trouver de la nourriture. C’est exactement ce que fait un agent en apprentissage par renforcement : il affine sa politique en fonction des récompenses et des punitions reçues lors de ses interactions avec l’environnement.

Vocabulaire Fondamental du RL

Pour comprendre le RL, il est crucial de maîtriser son vocabulaire. Ces termes ne sont pas indépendants ; ils décrivent les différentes facettes d'une boucle d'apprentissage continue. L'agent observe son état actuel dans l'environnement, choisit une action à effectuer, et reçoit en retour une récompense et un nouvel état. Sa stratégie pour choisir les actions est sa politique. L'objectif ultime est de trouver la politique qui maximise le retour total sur le long terme.

Voici les briques de base de tout problème de RL :

Le Cadre Théorique : Le Contrôle Optimal et les Équations de Bellman

Le Contrôle Optimal est une branche des mathématiques qui s'intéresse au problème de trouver une commande ou une politique qui optimise un certain critère de performance. Dans le cadre de l'apprentissage par renforcement, cela se traduit par une situation idéale où l'agent a une connaissance parfaite de son environnement.

Cela signifie qu'il connaît deux choses fondamentales : les probabilités de transition d'un état à un autre pour chaque action (\(P(s' \mid s, a)\)) et la fonction de récompense (\(R(s, a)\)). Contrairement à l'apprentissage par renforcement où l'agent doit découvrir ces règles par essais et erreurs, le contrôle optimal permet de calculer directement la meilleure stratégie possible. C'est donc un problème de planification et non d'apprentissage. Ce modèle théorique est crucial car il définit la solution parfaite, l'objectif vers lequel les algorithmes d'apprentissage vont tendre à s'approcher.

Pour modéliser un problème de RL, on utilise le Processus de Décision Markovien (MDP). Un MDP est un cadre mathématique qui décrit un environnement où les conséquences des actions sont partiellement aléatoires et où l'état futur ne dépend que de l'état présent et de l'action choisie (propriété de Markov).

Les Fonctions de Valeur

Pour évaluer la qualité d'un état ou d'une action, on utilise des fonctions de valeur. Ce sont des outils de prédiction qui nous disent à quoi s'attendre dans le futur.

Les Équations de Bellman

La révolution théorique vient avec les Équations de Bellman. Elles expriment une idée intuitive mais puissante : la valeur d'une situation est égale à la récompense immédiate que l'on obtient, plus la valeur de la situation future dans laquelle on se retrouve. C'est une relation de récurrence qui permet de calculer la valeur de n'importe quel état ou action.

Équation de Bellman pour V(s) :

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

Dans cette équation, le terme γ (gamma) est le taux d'escompte. C'est un nombre compris entre 0 et 1 qui détermine l'importance que l'accorde aux récompenses futures par rapport aux récompenses immédiates. Un γ proche de 1 rend l'agent très patient, car il valorise fortement les récompenses lointaines. À l'inverse, un γ proche de 0 rend l'agent "avide", car il se concentre presque exclusivement sur les récompenses immédiates. Le choix de γ est donc crucial pour définir le comportement de l'agent.

Équation de Bellman pour \(Q(S, A)\) :

$$ Q(S, A) = R(s,a) + \gamma \sum_{s'} P(s'|s,a) \max_{a'} Q(s',a') $$

Pour une politique optimale \( \pi^{*} \), la relation entre V et Q est simple : \( V^{*}(s) = \max_{a} Q^{*}(s,a) \).

L'Apprentissage dans un Environnement Inconnu

Le monde du contrôle optimal est un idéal. Dans la réalité, l'agent ne connaît pas les règles du jeu. Il ne sait pas quelle récompense il obtiendra ni où il atterrira après une action. Il doit tout apprendre par lui-même, en interagissant. C'est là que le véritable Reinforcement Learning commence.

Le Dilemme Exploration vs. Exploitation

Cette situation crée un dilemme fondamental pour l'agent. Doit-il exploiter ses connaissances actuelles en choisissant l'action qui lui a rapporté le plus de récompenses jusqu'à présent ? Ou doit-il explorer en essayant de nouvelles actions qui pourraient s'avérer encore meilleures, mais qui pourraient aussi être désastreuses ?

C'est comme choisir un restaurant. L'exploitation, c'est aller à votre restaurant préféré, vous êtes sûr d'y passer un bon moment. L'exploration, c'est essayer ce nouveau restaurant qui vient d'ouvrir. Il pourrait être génial, ou décevant. Pour maximiser votre satisfaction sur le long terme, vous devez trouver le bon équilibre.

Une stratégie courante est la politique ε-greedy : avec une probabilité ε, l'agent explore (action aléatoire), et avec une probabilité 1-ε, il exploite (meilleure action connue).

Méthodes d'Apprentissage

Pour estimer les fonctions de valeur sans connaître l'environnement, l'agent doit apprendre de son expérience. Mais comment ? Faut-il attendre la fin d'une tâche pour juger, ou peut-on apprendre à chaque instant ? Plusieurs approches existent, chacune avec sa propre "personnalité".

1. Méthode Monte Carlo

La méthode Monte Carlo est celle de l'historien patient. Elle attend la fin d'un épisode (un "game over") pour juger de la valeur des actions. Elle regarde la séquence complète des récompenses (le retour Gₜ réel) et attribue cette valeur à chaque état-action qui a été visité.

Étapes :

  1. Initialiser la table \(Q(S, A)\).
  2. Pour chaque épisode :
    1. Générer un épisode complet en suivant une politique (ex: ε-greedy), en stockant chaque transition \( (S_t, A_t, R_{t+1}) \).
    2. Lorsque l'épisode se termine à l'étape T, calculer le retour \( G_t \) pour chaque étape t.
    3. Pour chaque paire état-action \( (S_t, A_t) \) visitée, mettre à jour \( Q(S_t, A_t) \) en fonction du retour \( G_t \).

Elle est sans biais (car basée sur des retours réels) mais à forte variance (un seul épisode chanceux ou malchanceux peut fausser l'estimation).

2. Apprentissage par Différence Temporelle (TD)

La méthode TD est celle du réaliste impatient. Elle n'attend pas la fin de l'épisode. Elle met à jour ses estimations à chaque étape, en utilisant une estimation pour la récompense future. C'est ce qu'on appelle le bootstrap : on met à jour une estimation avec une autre estimation.

Étapes :

  1. Initialiser la table \(Q(S, A)\).
  2. Pour chaque étape :
    1. Observer l'état \(S\), choisir une action \(A\) (ε-greedy).
    2. Exécuter \(A\), observer \(R\) et \(S'\).
    3. Mettre à jour : \(Q(S, A) \leftarrow Q(S, A) + \alpha \cdot [R + \gamma \cdot Q(S', A') - Q(S, A)]\).
    4. Mettre à jour l'état : \(S \leftarrow S'\).

Elle est biaisée (car l'estimation \(Q(S', A')\) peut être fausse) mais à faible variance, ce qui la rend beaucoup plus stable et rapide à apprendre.

3. Apprentissage N-step Temporal Difference : Le Juste Milieu

Si Monte Carlo est trop patient et TD est trop impatient, l'apprentissage N-step TD offre un compromis intelligent. Au lieu de regarder seulement 1 pas dans le futur ou d'attendre la fin de l'épisode, il regarde n pas en avant.

Pensez à un analyste financier. L'approche 1-step TD ne regarde que le prix d'une action demain pour prédire sa valeur aujourd'hui. L'approche Monte Carlo attend la fin du mois pour voir le profit total. L'approche N-step TD (avec n=5, par exemple) regarde l'évolution des prix sur les 5 prochains jours avant de faire une prédiction. C'est plus informatif qu'un seul jour, mais plus rapide que d'attendre la fin du mois.

La cible N-step TD est calculée en additionnant les n-1 premières récompenses réelles, puis en ajoutant une estimation de la valeur à l'étape n.

$$ Cible\_TD = R_{t+1} + \gamma R_{t+2} + ... + \gamma^{n-1}R_{t+n} + \gamma^n Q(s_{t+n}, a_{t+n}) $$

Étapes :

  1. Initialiser la table \(Q(S, A)\).
  2. Pour chaque étape :
    1. Observer l'état \(S\), choisir une action \(A\) (ε-greedy).
    2. Exécuter \(A\), observer \(R\) et \(S'\).
    3. Stocker la transition \((S, A, R, S')\) dans un buffer temporaire.
    4. Si \(n\) étapes se sont écoulées depuis la transition \((S_t, A_t)\) stockée :
      1. Calculer la cible N-step TD en utilisant les \(n\) récompenses et l'état \(S_{t+n}\).
      2. Mettre à jour \(Q(S_t, A_t)\) avec cette cible.

La beauté de N-step TD est qu'il permet de contrôler le compromis biais-variance. Plus \(n\) est grand, plus on se rapproche de Monte Carlo (moins de biais, plus de variance). Plus \(n\) est petit, plus on se rapproche de TD (plus de biais, moins de variance). En choisissant \(n\) on peut trouver l'équilibre parfait pour un problème donné.

Les Algorithmes d'Apprentissage : SARSA et Q-Learning

Les méthodes TD nous donnent un principe de mise à jour. SARSA et Q-Learning sont deux algorithmes concrets qui appliquent ce principe. Ils sont tous deux extrêmement populaires, mais ils diffèrent fondamentalement dans leur manière d'apprendre, une distinction cruciale entre on-policy et off-policy.

SARSA (On-Policy) : L'Apprenti Prudent

SARSA est un algorithme on-policy : il apprend la valeur de la politique qu'il est en train d'exécuter, avec toutes ses imperfections et ses phases d'exploration. Sa cible TD utilise l'action \(a'\) que l'agent a réellement choisie dans l'état suivant \(s'\).

$$ Q(S, A) \leftarrow Q(S, A) + \alpha \times [R + \gamma Q(s', a') - Q(S, A)] $$

Étapes :

  1. Initialiser \(Q\).
  2. Pour chaque épisode :
    1. Initialiser \(S\), choisir \(A\) (ε-greedy).
    2. Répéter :
      1. Exécuter \(A\), observer \(R\) et \(S'\).
      2. Choisir \(A'\) depuis \(S'\) (ε-greedy).
      3. Mettre à jour \(Q(S, A)\) avec la formule ci-dessus.
      4. \(S \leftarrow S'\), \(A \leftarrow A'\).

SARSA est prudent. Il apprend à naviguer en tenant compte du fait qu'il peut faire des erreurs d'exploration.

Q-Learning (Off-Policy) : Le Visionnaire Audacieux

Q-Learning est un algorithme off-policy : il apprend la valeur de la politique optimale tout en suivant une politique exploratoire. Sa cible TD utilise la meilleure action possible depuis l'état s', quelle que soit l'action qu'il a réellement choisie.

$$ Q(S, A) \leftarrow Q(S, A) + \alpha \times [R + \gamma \times \max_{a'} Q(s', a') - Q(S, A)] $$

Algorithme (étapes) :

  1. Initialiser \(Q\).
  2. Pour chaque épisode :
    1. Initialiser \(S\).
    2. Répéter :
      1. Choisir \(A\) depuis \(S\) (ε-greedy).
      2. Exécuter \(A\), observer \(R\) et \(S'\).
      3. Mettre à jour \(Q(S, A)\) avec la formule ci-dessus.
      4. \(S \leftarrow S'\).

Q-Learning est plus audacieux. Il apprend le chemin optimal en supposant qu'il finira par toujours choisir les meilleures actions. Sa nature off-policy le rend aussi très efficace, car il peut apprendre de n'importe quelle expérience passée.

Limites de l'Approche Tabulaire et Perspective

Les méthodes que nous avons vues sont incroyablement puissantes, mais elles ont un talon d'Achille : leur mémoire. Elles sont dites tabulaires, car elles stockent les valeurs Q dans une table. Cette approche fonctionne parfaitement pour des mondes simples comme un labyrinthe, mais elle se heurte à un mur infranchissable dès que l'on s'attaque à des problèmes réels.

Le Deep Reinforcement Learning

Pour surmonter ces limites, le Deep Reinforcement Learning a marqué un tournant majeur. L'idée est géniale dans sa simplicité : remplacer la table Q rigide par un réseau de neurones profond, une fonction souple capable d'approximer la valeur Q pour n'importe quel état. Le réseau de neurones apprend à généraliser à partir des exemples qu'il voit, lui permettant d'évaluer des situations nouvelles mais similaires.

Conclusion

Dans cet article, nous avons établi les fondations de l'apprentissage par renforcement. Nous sommes partis du cadre théorique idéal du contrôle optimal et des équations de Bellman, qui décrivent comment raisonner sur la valeur à long terme si l'environnement est parfaitement connu.

Nous avons ensuite brisé cette hypothèse pour entrer dans le véritable apprentissage, où un agent doit découvrir la politique optimale par lui-même. Nous avons vu comment il doit gérer le dilemme exploration/exploitation et comment des méthodes comme Monte Carlo et les différences temporelles lui permettent d'apprendre de son expérience.

Enfin, nous avons détaillé les deux algorithmes pionniers, SARSA et Q-Learning, en soulignant la distinction cruciale entre les approches on-policy (prudente) et off-policy (audacieuse et efficace).

Cependant, nous avons également mis en lumière les limites de ces méthodes tabulaires, qui sont inadaptées aux problèmes complexes du monde réel à cause de la malédiction de la dimensionnalité et de leur incapacité à généraliser.

C'est précisément pour surmonter ces obstacles que le Deep Reinforcement Learning a été conçu. En remplaçant la table rigide par un réseau de neurones souple, il a ouvert la voie à des applications autrefois inimaginables. Dans un prochain article, nous explorerons cette révolution et des algorithmes comme le Deep Q-Network (DQN).

🎁 AI Prototype Pack Vol.1 — Gratuit, sans carte bancaire. Télécharger

Liens Utiles

Pour approfondir vos connaissances et explorer des outils avancés, voici quelques ressources :

Ma recommandation musicale du jour : à écouter sans modération !

Écouter sur YouTube