Apprentissage par renforcement : pourquoi choisir entre SARSA et Q-learning ?

Imaginez un robot qui doit traverser un entrepôt rempli de caisses et de chariots. S’il apprend en marchant Droit sur les étagères, il risque de tout casser. S’il apprend en évitant soigneusement les obstacles, il mettra trois fois plus de temps à atteindre la sortie. En apprentissage par renforcement, ce dilemme se résume à une question : faut-il apprendre uniquement à partir de ses propres actions… ou aussi à partir des actions des autres ?

LE DILEMME INVISIBLE QUI DÉCIDE DE TOUT

Quand on parle d’apprentissage par renforcement, on cite souvent des noms d’algorithmes comme SARSA, Q-learning, PPO ou DQN. Chaque nom semble pointer vers une méthode différente, une astuce mathématique unique. Pourtant, la plupart de ces algorithmes reposent sur une question bien plus simple :

Cette question, c’est le cœur de la différence entre on-policy et off-policy. Pour la comprendre, il faut d’abord savoir ce qu’est une politique en apprentissage par renforcement : c’est la règle que l’agent utilise pour décider quelle action prendre dans chaque situation. Une fois cette idée claire, le contraste devient évident.

Une méthode on-policy apprend à partir de la même stratégie que celle que l’agent utilise actuellement. Une méthode off-policy, en revanche, sépare les deux. L’agent peut agir selon une stratégie tout en apprenant à partir d’une autre. Par exemple, un robot peut agir prudemment pour éviter les accidents tout en apprenant, à partir de données enregistrées, une stratégie plus performante mais risquée.

Cette séparation entre comment l’agent agit et ce qu’il apprend est l’idée clé derrière l’apprentissage off-policy. Ce choix n’est pas qu’une question de vocabulaire : il influence des propriétés essentielles de l’algorithme, comme la façon dont il explore l’environnement, combien de données il a besoin, s’il peut apprendre à partir d’expériences passées, et à quel point son entraînement est stable.

Dans un contexte où les données sont faciles à obtenir, ce choix peut sembler technique. Mais dans un environnement où les données sont coûteuses, lentes ou risquées à collecter, il devient une nécessité pratique. Prenons l’exemple d’un robot apprenant à se déplacer dans un entrepôt bondé. Pour des raisons de sécurité, son comportement pendant l’entraînement doit rester prudent. Une méthode on-policy améliore directement ce comportement conservateur. Une méthode off-policy permet quelque chose de plus flexible : le robot peut continuer à agir prudemment tout en apprenant, à partir de données collectées, une stratégie différente qui pourrait, à terme, être plus performante.

POURQUOI SARSA ET Q-LEARNING NE SONT PAS JUMEAUX

Pour comprendre cette différence, il faut revenir à une question plus fondamentale : que cherche vraiment à apprendre un agent en apprentissage par renforcement ? Avant de comparer des algorithmes comme SARSA et Q-learning, il est utile de comprendre l’objet qu’ils mettent à jour. Dans la plupart des méthodes tabulaires (où chaque état et action est représenté explicitement), l’agent n’apprend pas directement les actions. Il apprend des estimations de la valeur de chaque action dans chaque situation.

Prenons un exemple concret. Imaginez un agent qui se déplace dans un monde. À chaque étape, il se trouve dans un état s, choisit une action a, reçoit une récompense r, et arrive dans un nouvel état s’. Son objectif : maximiser la somme totale des récompenses qu’il collecte au fil du temps.

Pour y parvenir, l’agent a besoin d’une façon d’évaluer ses choix. Il doit répondre à des questions comme : « Si je prends cette action maintenant, combien de récompenses puis-je espérer obtenir à l’avenir ? » C’est là qu’intervient la fonction de valeur d’action, souvent notée Q(s, a). En termes simples, cette fonction mesure à quel point il est bon de prendre l’action a dans l’état s, en tenant compte non seulement de la récompense immédiate, mais aussi des récompenses futures possibles.

Plus précisément, sous une politique π, la fonction de valeur d’action est définie comme l’espérance de la récompense totale lorsque l’on part de l’état s, que l’on prend l’action a, et que l’on suit ensuite la politique π indéfiniment :

Q_π(s, a) = E[G_t | S_t = s, A_t = a, π]

où G_t représente la récompense totale actualisée à partir de l’étape t :

G_t = R_t+1 + γR_t+2 + γ²R_t+3 + …

En combinant ces éléments, on peut écrire explicitement la fonction de valeur d’action comme :

Q_π(s, a) = E[R_t+1 + γQ_π(S_t+1, A_t+1) | S_t = s, A_t = a, π]

L’intuition derrière cette formule est simple :

La valeur d’une action ne dépend pas uniquement de ce qui se passe immédiatement après l’avoir prise. Elle dépend aussi de ce que l’agent fera ensuite. La même action peut avoir des valeurs différentes selon les stratégies futures adoptées. C’est pourquoi la fonction de valeur d’action est toujours définie par rapport à une politique. Et c’est précisément là que commence la distinction entre on-policy et off-policy.

LA DIFFÉRENCE QUI CHANGE TOUT : ON-POLICY VS OFF-POLICY

Avec ces définitions, on peut formuler clairement la distinction :

Une méthode on-policy améliore la stratégie que l’agent utilise effectivement dans l’environnement. Une méthode off-policy, en revanche, permet à l’agent d’agir d’une certaine manière (peut-être prudemment ou aléatoirement pour explorer) tout en apprenant à propos d’une autre stratégie en arrière-plan. Cette séparation est ce qui permet aux méthodes off-policy de réutiliser d’anciennes données, d’apprendre à partir d’actions exploratoires, et même de bénéficier d’expériences collectées par un autre agent.

Une analogie simple aide à comprendre. Imaginez que vous apprenez à jouer aux échecs. Une approche on-policy consiste à améliorer votre jeu en analysant exactement les coups que vous avez joués pendant vos parties. Une approche off-policy, c’est jouer un style en pratique tout en étudiant les conséquences de coups plus forts à partir de parties enregistrées ou d’exemples d’experts. Dans les deux cas, vous apprenez, mais la relation entre comment vous agissez et ce que vous apprenez est différente. Cette relation est l’idée clé derrière cet article.

Pour rendre cette distinction concrète, examinons maintenant comment les estimations de valeur sont mises à jour en pratique. C’est là que le contraste entre SARSA et Q-learning devient particulièrement éclairant.

LA FONDATION INVISIBLE : L’APPRENTISSAGE PAR DIFFÉRENCE TEMPORELLE

Avant de comparer SARSA et Q-learning, il faut comprendre l’idée sur laquelle ils reposent tous les deux : l’apprentissage par différence temporelle (TD learning). Si la distinction entre on-policy et off-policy nous indique quel type de relation entre politiques un algorithme utilise, l’apprentissage TD nous explique comment l’agent met à jour ce qu’il sait à partir de l’expérience. En ce sens, l’apprentissage TD est la base commune de nombreuses méthodes d’apprentissage par renforcement parmi les plus importantes.

Historiquement, l’apprentissage TD se situe entre deux idées plus anciennes :

• Les méthodes de Monte Carlo, qui attendent la fin d’un épisode pour estimer la valeur d’un état.
• La programmation dynamique, qui nécessite un modèle complet de l’environnement.

L’apprentissage TD combine le meilleur des deux mondes. Comme les méthodes de Monte Carlo, il apprend directement à partir de l’expérience et ne nécessite pas de modèle de l’environnement. Comme la programmation dynamique, il met à jour ses estimations en utilisant d’autres estimations, plutôt que d’attendre la fin d’un épisode.

Cette combinaison est ce qui rend l’apprentissage TD si puissant. Supposons que l’agent essaie d’estimer la valeur d’un état (V(s)). Après être passé de l’état (S_t) à l’état (S_t+1) et avoir reçu la récompense (R_t+1), une mise à jour TD en une étape ressemble à ceci :

V(S_t) ← V(S_t) + α [R_t+1 + γV(S_t+1) − V(S_t)]

À première vue, cela peut ressembler à une simple équation, mais la logique est simple. L’agent commence avec son estimation actuelle V(S_t), puis ajuste cette estimation vers une cible plus précise :

Nouvelle estimation = Récompense immédiate + Récompense future actualisée

Cette cible dit : « Prends la récompense immédiate que tu viens d’observer, puis ajoute l’estimation actualisée de ce qui vient ensuite. » La quantité entre crochets,

R_t+1 + γV(S_t+1) − V(S_t)

est appelée l’erreur TD. On peut voir cette erreur comme une mesure de surprise :

La mise à jour TD est donc une idée très naturelle : prédire, observer, comparer, corriger.

C’est aussi là qu’intervient l’idée de bootstrap. Dans l’apprentissage TD, l’agent met à jour une estimation en utilisant une autre estimation. Au lieu d’attendre de voir la récompense totale future, il utilise sa supposition actuelle sur l’état suivant comme partie de la cible. Cela rend l’apprentissage plus rapide et plus incrémental, ce qui explique pourquoi les méthodes TD sont si centrales en apprentissage par renforcement.

Mais le bootstrap a une conséquence importante : quelle estimation nous utilisons pour le bootstrap compte. Et c’est précisément là que la distinction entre on-policy et off-policy commence à se manifester sous forme algorithmique.

SARSA : L’APPRENTISSAGE QUI REFLETE VOS IMPERFECTIONS

SARSA et Q-learning sont tous deux des méthodes de contrôle par différence temporelle. Ils utilisent des mises à jour de type TD pour apprendre les valeurs d’action et améliorer le comportement au fil du temps. La différence cruciale entre eux réside dans la cible à partir de laquelle ils effectuent le bootstrap :

SARSA est l’algorithme classique de contrôle TD on-policy. Son nom vient du tuple qu’il utilise : (State, Action, Reward, next State, next Action).

Sa mise à jour ressemble à ceci :

nextaction = policy(Q, nextstate)
tdtarget = reward + gamma * Q[nextstate, next_action]
tderror = tdtarget - Q[state, action]
Q[state, action] += alpha * td_error

Cette Q(nextstate, nextaction) est la valeur de l’action que l’agent a effectivement choisie pour l’étape suivante. Ce n’est pas la meilleure action, ni une moyenne, juste l’action qu’il va réellement prendre.

Cela peut sembler anodin, mais cela change tout. Si l’agent utilise une politique ε-greedy (principalement gloutonne, parfois aléatoire), SARSA apprend la valeur de cette politique ε-greedy, avec ses défauts inclus. L’agent prend en compte ses propres imperfections.

Après avoir mis à jour Q, l’agent recalcule simplement sa politique ε-greedy à partir des nouvelles valeurs Q. Si la politique visite finalement toutes les paires état-action et que ε décroît jusqu’à zéro, SARSA converge vers la politique optimale. Mais pendant l’apprentissage, il apprend à partir de son propre comportement (imparfait).

Pour voir cela en action, prenons l’exemple du Chemin de la Falaise. Imaginez une grille :

Départ en S, objectif en G. Chaque étape coûte −1. Si on marche sur la falaise, on obtient −100 et on revient à S.

Pourquoi SARSA évite-t-il la falaise ? Parce qu’il sait qu’il prend parfois des actions aléatoires. Si on marche juste à côté de la falaise, on risque occasionnellement de tomber. Les estimations de valeur de SARSA reflètent ce risque. C’est pourquoi il préfère la route intérieure.

Si notre agent fait effectivement des erreurs parfois, prendre la route sûre est la chose intelligente à faire. Dans l’expérience classique du Chemin de la Falaise, ε est maintenu constant à 0,1, donc SARSA ne devient jamais entièrement glouton ; c’est pourquoi sa politique apprise reste prudente. Avec un ε décroissant, SARSA convergerait éventuellement vers le chemin optimal, mais aurait subi beaucoup plus de chutes en chemin.

Q-LEARNING : L’ILLUSION DE LA PERFECTION

Contrairement à SARSA, Q-learning utilise une mise à jour différente :

tdtarget = reward + gamma * np.max(Q[nextstate, :])
tderror = tdtarget - Q[state, action]
Q[state, action] += alpha * td_error

Au lieu d’utiliser la valeur de l’action suivante réelle, il utilise le maximum sur toutes les actions possibles suivantes. C’est le mouvement off-policy. L’agent peut trébucher autour avec une politique ε-greedy, mais ses mises à jour agissent comme s’il allait agir de manière optimale à partir de l’étape suivante.

Revenons à la falaise. Q-learning apprend le chemin qui longe la falaise. Il imagine un futur où il agit parfaitement : sans trébuchements aléatoires. Dans ce monde parfait, marcher à côté de la falaise est sans danger, car un agent parfait ne tombe jamais. L’opérateur max suppose un comportement optimal à chaque étape future, donc le risque de l’exploration disparaît simplement de ses estimations.

Que cela signifie-t-il en pratique ? Pendant l’entraînement, Q-learning fait souvent pire en ligne que SARSA. Il marche dangereusement près de la falaise et tombe occasionnellement, accumulant de grosses pénalités. SARSA, en jouant la prudence, obtient une récompense cumulative plus élevée pendant l’apprentissage.

Mais après l’entraînement, quand on désactive l’exploration, Q-learning emprunte le chemin optimal le plus court. SARSA, lui, reste sur la route sûre plus longue.

C’est l’échange classique : meilleure performance finale vs. meilleure performance pendant l’apprentissage.

EXPECTED SARSA : LE MILIEU DU GUIDE

Il existe un troisième algorithme qui se situe entre SARSA et Q-learning : Expected SARSA. Il utilise une espérance sur toutes les actions suivantes au lieu d’un seul échantillon ou d’un max :

td_target = reward + gamma * Σ_a π(a|nextstate) * Q(nextstate, a)

Cette somme est une moyenne pondérée de toutes les actions possibles suivantes, où les poids sont les probabilités issues de la politique actuelle.

Dans les expériences du Chemin de la Falaise, Expected SARSA bat généralement à la fois SARSA et Q-learning sur une gamme de tailles de pas. L’inconvénient ? Calculer cette somme nécessite d’itérer sur toutes les actions : pas de problème pour de petites grilles, mais coûteux quand on a de grands espaces d’action ou continus. C’est pourquoi Q-learning (et sa version profonde DQN) reste plus populaire en pratique.

LE BIAIS DE MAXIMISATION : L’ARME À DOUBLE TRANCHANT DE Q-LEARNING

Q-learning a un défaut sournois : le biais de maximisation. Parce qu’il utilise max_aQ(S_t+1, a), et que ces valeurs Q ne sont que des estimations bruitées, le maximum a tendance à être une surestimation.

Imaginez que toutes les vraies valeurs d’action sont 0, mais que nos estimations ont un peu de bruit aléatoire. Le maximum de ces estimations bruitées sera généralement positif. Q-learning bootstrap ensuite à partir de cette surestimation positive, ce qui la rend encore plus grande. Avec le temps, l’agent devient surconfiant.

La solution, tirée des manuels, est le Double Q-learning. On utilise deux fonctions Q indépendantes, Q₁ et Q₂. L’une choisit la meilleure action, l’autre l’évalue :

td_target = reward + gamma * Q₂(next_state, argmax_a Q₁(next_state, a))

Pour garder les choses symétriques, la mise à jour pour Q₂ serait :

td_target = reward + gamma * Q₁(next_state, argmax_a Q₂(next_state, a))

Découpler la sélection de l’évaluation annule le biais positif. Cette idée a ensuite donné naissance à Double DQN, une amélioration majeure sur le réseau Q profond original.

N-STEPS ET L’HORIZON TEMPOREL : QUAND LE PASSÉ DEVIENT FUTUR

L’une des idées les plus surprenantes des manuels est que les mises à jour TD en une étape et Monte Carlo ne sont que deux extrémités d’un spectre, reliées par les retours à n étapes.

Un n plus grand signifie plus de dépendance aux récompenses réelles (moins de biais) mais aussi plus de variance. Un n plus petit signifie plus de dépendance aux estimations actuelles (plus de biais) mais moins de variance et une propagation plus rapide.

La distinction entre on-policy et off-policy devient encore plus riche ici. Pour SARSA à n étapes, les actions dans la trajectoire doivent provenir de la politique que nous apprenons. Pour les méthodes off-policy à n étapes, nous avons besoin de échantillonnage d’importance pour corriger les distributions non correspondantes. C’est un sujet profond, mais cela montre que le choix entre on-policy et off-policy n’est pas un simple interrupteur : il s’applique à tous les horizons temporels.

QUEL ALGORITHME CHOISIR POUR VOTRE PROJET ?

Quand on construit un système réel, comment faire son choix ?

Le superpouvoir de l’off-policy est la réutilisation des anciennes données. Parce que ses mises à jour n’assument pas que les données proviennent de la politique actuelle, on peut stocker chaque transition dans un buffer de replay et l’échantillonner des milliers de fois. C’est pourquoi DQN fonctionne si bien : il apprend à partir de millions d’expériences passées. Les méthodes on-policy comme PPO doivent collecter de nouvelles données après chaque mise à jour, ce qui est bien moins efficace en termes d’échantillonnage.

Si on déploie un agent qui doit bien performer dès le premier jour, on veut probablement une méthode on-policy. SARSA (ou PPO) sera plus prudent et stable pendant l’apprentissage. Les méthodes off-policy peuvent explorer de manière trop agressive et nous coûter des pénalités dans le monde réel.

Autre point important : SARSA construit naturellement une conscience des risques parce qu’il apprend à partir de son exécution imparfaite. Si on sait que notre agent fera occasionnellement des erreurs, SARSA évitera les états où une erreur est catastrophique. Q-learning suppose une exécution parfaite dans le futur, donc il peut être dangereusement surconfiant.

LA TRIADE MORTELLE : POURQUOI L’APPRENTISSAGE PROFOND PAR RENFORCEMENT ÉCHOUERAIT PARFOIS

Quand on combine approximation de fonction (comme un réseau de neurones) + bootstrap + apprentissage off-policy, on obtient ce qu’on appelle la triade mortelle. Cette combinaison peut mener à la divergence ou à l’instabilité si elle n’est pas soigneusement gérée.

Tous ces concepts ne sont pas que théoriques. Chaque algorithme moderne d’apprentissage profond par renforcement hérite de l’âme de ces méthodes tabulaires :

• DQN : Q-learning avec un réseau de neurones et un buffer de replay.
• DDQN : Double Q-learning appliqué au deep RL.
• PPO : Une méthode on-policy qui équilibre exploration et stabilité.
• SAC : Une méthode off-policy qui maximise à la fois la récompense et l’entropie pour une exploration plus sûre.

Chacun de ces algorithmes n’est qu’une réponse particulière à la même question fondamentale.

Il n’y a pas de bonne réponse universelle. Tout dépend de ce qu’on construit.

En pratique, de nombreux systèmes modernes mélangent les deux : un critique off-policy pour un apprentissage efficace, un acteur on-policy pour une amélioration stable. Mais comprendre les compromis au niveau tabulaire vous donne le pouvoir de faire ces choix de manière réfléchie.

LES MONDES DE GRILLE NE SONT PAS DES ROUES D’APPRENTISSAGE

Les exemples de grilles ne sont pas des roues d’entraînement : ce sont la fondation. Une fois que vous les avez intériorisés, vous pouvez regarder n’importe quel algorithme d’apprentissage par renforcement et immédiatement voir où il se situe sur le spectre on-policy/off-policy, et pourquoi il fonctionne comme il le fait.

Si cet article vous a éclairé, vous pourriez apprécier les prochains volets de cette série, sur les méthodes à n étapes et les traces d’éligibilité, où la distinction on-policy/off-policy devient encore plus riche, et où les liens avec les algorithmes modernes vont encore plus loin.