Le Q-learning n’est pas encore scalable

• Le RL a obtenu des résultats majeurs dans Go, les échecs et le post-entraînement des LLM, mais la plupart de ces succès reposent sur du RL on-policy, qui nécessite de nouveaux rollouts, dans des conditions différentes du RL off-policy qui peut réutiliser librement des données passées
• Le RL off-policy représentatif, le Q-learning, est très efficace en échantillons, mais il ne passe toujours pas suffisamment à l’échelle sur les tâches de long terme qui exigent plus de 100 étapes de décision significatives
• Le goulot d’étranglement vient du fait que les cibles bootstrapées biaisées de l’apprentissage TD s’accumulent à mesure que l’horizon s’allonge, une contrainte différente de celle de la prédiction du prochain token, des modèles de diffusion ou de l’apprentissage contrastif
• Dans les expériences OGBench, flow BC, IQL, CRL et SAC+BC n’ont pas réussi à résoudre toutes les tâches de long terme, même avec un jeu de données de 1B, soit 1000 fois plus grand que les jeux de données offline RL classiques, et les performances ont plafonné bien en dessous du niveau optimal
• Les réductions d’horizon comme les n-step returns et le RL hiérarchique ont amélioré la scalabilité et les performances finales, mais les techniques actuelles n’atténuent le problème que d’un facteur constant et restent insuffisantes pour résoudre des tâches de long terme arbitrairement complexes

---

Où en est aujourd’hui la scalabilité du RL

• La prédiction du prochain token, la denoising diffusion et l’apprentissage contrastif ont montré qu’il existe des fonctions objectif scalables avec de grands volumes de données et des modèles de plusieurs milliards de paramètres
• Le RL a lui aussi atteint des performances surhumaines dans Go et les échecs, et, avec les LLM, il résout des tâches de raisonnement complexes comme les mathématiques et le code
• Mais la plupart des succès concrets actuels reposent sur des algorithmes de RL on-policy
  • Exemples représentatifs : REINFORCE, PPO, GRPO
  • Ils nécessitent toujours des rollouts nouvellement échantillonnés à partir de la politique courante
  • Ils ne peuvent pas réutiliser les données passées
  • Les méthodes de type PPO peuvent réutiliser les données de façon limitée, mais sont tout de même considérées comme du RL on-policy selon des classifications comme celles de la documentation d’OpenAI
• Dans des environnements comme les jeux de plateau ou les LLM, où l’on peut générer beaucoup de rollouts à faible coût, cette contrainte n’est pas forcément un gros problème
• En robotique, produire dans le monde réel un volume d’échantillons comparable à celui utilisé pour le post-entraînement de modèles de langage via RL demande plusieurs mois, et une présence humaine 24 h/24 est nécessaire pour réinitialiser les robots pendant l’entraînement

RL off-policy et Q-learning

• Le RL off-policy peut en principe utiliser des données collectées n’importe quand et n’importe comment
• Les mêmes données peuvent être réutilisées plusieurs fois, ce qui le rend en général plus efficace en échantillons
• Il existe même un cas où un chien robot a été entraîné à marcher en 20 minutes à partir de zéro dans le monde réel
  • Cas associé : walk in the park
• Le Q-learning est l’algorithme de RL off-policy le plus utilisé
• La plupart des algorithmes pratiques de RL off-policy model-free reposent sur des variantes de la perte TD
• Pour appliquer le RL à davantage de problèmes réels, la question clé devient : « le Q-learning, c’est-à-dire l’apprentissage TD, est-il scalable ? »
• Si oui, il pourrait permettre de résoudre efficacement une plus grande variété de tâches réelles complexes, comme la robotique ou les agents capables d’utiliser un ordinateur

Ce que signifie « scalable » : pas la largeur, mais la profondeur

• Ici, la scalabilité désigne la capacité à résoudre des problèmes plus difficiles et à horizon plus long lorsqu’on ajoute suffisamment de données, de calcul et de temps, avec une couverture adéquate
• Cela diffère de la capacité d’un seul modèle à résoudre un plus grand nombre de tâches
  • Augmenter le nombre de tâches ne signifie pas forcément résoudre des tâches plus difficiles
  • Plusieurs travaux de scaling ont déjà montré le potentiel de cet axe de la « largeur »
• L’axe plus important et plus difficile est celui de la profondeur
  • Parce qu’il exige des capacités de décision plus avancées
• Sous sa forme actuelle, le Q-learning n’est pas fortement scalable sur cet axe de la profondeur
• Pour faire passer le Q-learning et le RL off-policy à l’échelle sur des problèmes complexes de long terme, il faudra une percée algorithmique

Le Q-learning absent des grands succès du RL à grande échelle

• Beaucoup de succès concrets du RL reposent sur autre chose que le Q-learning basé sur TD
• AlphaGo, AlphaZero et MuZero utilisent du RL basé sur un modèle et la recherche arborescente Monte Carlo, et n’emploient pas l’apprentissage TD pour les jeux de plateau
  • Référence : page 15 de l’article MuZero
• OpenAI Five a atteint des performances surhumaines dans Dota 2 avec PPO
  • Référence : note de bas de page 6 de l’article OpenAI Five
• Le RL pour les LLM est aujourd’hui dominé par des familles de policy gradient on-policy comme PPO et GRPO
• Il n’existe pas d’exemple concret présenté de succès du RL off-policy, en particulier de l’apprentissage TD à 1 étape, à une échelle comparable à AlphaGo ou aux LLM
• Cette évaluation ne cherche pas à rejeter le RL off-policy ; elle souligne plutôt la nécessité de poursuivre la recherche sur les algorithmes de RL

Pourquoi le Q-learning vacille sur les tâches de long terme

• La perte TD du Q-learning apprend à faire correspondre la valeur Q actuelle à une cible constituée de la récompense plus la valeur Q maximale de l’état suivant
• Cette cible est une cible bootstrapée biaisée qui peut ne pas être égale à la vraie valeur Q optimale
• La raison principale pour laquelle le Q-learning a du mal à passer à l’échelle est que le biais de la cible de prédiction s’accumule le long de l’horizon
• Cette accumulation du biais agit comme une limite fondamentale de l’apprentissage TD
  • Les fonctions objectif comme la prédiction du prochain token, la denoising diffusion ou l’apprentissage contrastif n’ont pas ce biais dans leurs cibles de prédiction
  • BYOL et DINO peuvent avoir un biais, mais celui-ci ne s’accumule pas le long de l’horizon
• Plus le problème est complexe et plus l’horizon est long, plus le biais des cibles bootstrapées s’accumule fortement
• Il est difficile d’atténuer ce problème simplement avec plus de données et des modèles plus grands
• Cela explique aussi en partie pourquoi on utilise rarement dans la pratique des facteurs d’actualisation plus grands, comme (\gamma > 0.999)
• Les méthodes de policy gradient souffrent relativement moins de ce problème
  • Des techniques d’estimation de valeur on-policy comme le GAE gèrent relativement plus facilement les horizons longs, au prix d’une variance plus élevée
  • Elles ne sont pas enfermées dans une récursion stricte à 1 étape

Expériences de scalabilité basées sur OGBench

• Le récent article Horizon Reduction Makes RL Scalable teste cette hypothèse à travers diverses études de scaling contrôlées
• L’objectif est de vérifier si les méthodes actuelles de RL off-policy peuvent résoudre des tâches très difficiles en augmentant simplement les données et le calcul
• Les expériences utilisent des tâches complexes et auparavant non résolues de OGBench
• Les exigences des tâches sont les suivantes
  • L’agent doit apprendre des comportements complexes d’atteinte d’objectif à partir de démonstrations aléatoires non structurées de type play-style
  • Au test, il doit effectuer de la manipulation fine, de la résolution de puzzles combinatoires et de la navigation à long terme
  • Les tâches s’étendent sur 1 000 étapes d’environnement
• Les expériences ont été conçues pour réduire les facteurs de confusion
  • Une quantité de données quasi infinie a été collectée, au point que le surapprentissage est pratiquement impossible
  • Les travaux se concentrent sur le RL offline afin d’éliminer les problèmes d’exploration
  • Une couverture suffisante du jeu de données est garantie, ainsi que le fait que toutes les tâches peuvent être résolues à partir du jeu de données fourni
  • Des observations d’état ground-truth sont fournies directement pour réduire la charge liée à l’apprentissage de représentations
• Si le Q-learning ne passe pas à l’échelle même dans cet environnement contrôlé, il a encore moins de chances d’y parvenir dans des environnements réels avec peu de données et des observations bruitées

Résultats des algorithmes standard de RL offline

• Les algorithmes standard et largement utilisés de RL offline n’ont pas réussi à résoudre toutes les tâches
• Les algorithmes évalués sont flow BC, IQL, CRL et SAC+BC
• Les expériences ont été menées même sur un jeu de données de taille 1B
  • Soit (1000 \times) la taille des jeux de données offline RL typiques
• Plus important encore, les performances ont souvent atteint un plateau très en dessous des performances optimales
• Diverses ablations et expériences de contrôle — modèles plus grands, entraînement plus long, autres hyperparamètres — n’ont pas aidé
• La seule approche ayant eu un effet notable a été la réduction d’horizon

Les améliorations apportées par la réduction d’horizon

• L’hypothèse de départ est que l’horizon, et donc l’accumulation de biais qui en découle, constitue le principal obstacle à la scalabilité du RL off-policy
• Pour la vérifier, plusieurs techniques de réduction d’horizon visant à diminuer le nombre de backups TD biaisés ont été testées
  • Exemples : n-step returns, RL hiérarchique
• Les résultats ont été positifs
  • Même des méthodes simples comme les n-step returns ont fortement amélioré la scalabilité et les performances finales
  • Ce n’est pas seulement une astuce pour accélérer l’entraînement : les performances asymptotiques s’améliorent aussi
  • Des méthodes hiérarchiques complètes fonctionnent encore mieux
• Sur l’ensemble des expériences, la seule technique à avoir donné des résultats cohérents est la réduction d’horizon
• Augmenter simplement les données et le calcul ne suffit pas à résoudre la malédiction de l’horizon
• Il faut de meilleurs algorithmes qui ciblent directement ce problème

Pistes de recherche vers des fonctions objectif off-policy scalables

• La réduction d’horizon ouvre une voie vers la scalabilité du Q-learning, mais les techniques actuelles ne résolvent pas le problème à la racine
• Les méthodes actuelles comme les n-step returns et le RL hiérarchique n’atténuent le problème que d’un facteur constant dans la plupart des cas
• Il manque encore des algorithmes de RL off-policy capables de passer à l’échelle jusqu’à des problèmes de long terme arbitrairement complexes
• Trois pistes de recherche possibles sont proposées
  • Trouver une structure hiérarchique récursive simple et scalable, au-delà d’une hiérarchie à deux niveaux, pour gérer des horizons de longueur arbitraire
  • Puisque l’apprentissage de modèle est un apprentissage supervisé et que le RL on-policy est scalable, adopter une approche de RL basé sur un modèle : apprendre d’abord un modèle, puis exécuter du RL on-policy à l’intérieur de ce modèle
  • Éviter complètement l’apprentissage TD
    • Par exemple, quasimetric RL repose sur la formulation LP du RL
    • Des méthodes basées sur Monte Carlo comme le contrastive RL pourraient aussi mieux passer à l’échelle que les approches basées sur TD
• Ce cadre expérimental peut servir de point de départ pour tester ce type d’idées
  • Les tâches robotiques complexes et les jeux de données sont déjà conçus
  • Il a été vérifié que les tâches peuvent être résolues à partir des données fournies
  • On peut rendre les tâches arbitrairement plus difficiles, par exemple en ajoutant davantage de cubes, afin de stress-tester la scalabilité algorithmique de manière contrôlée
  • Code disponible : horizon-reduction

[GN⁺]

Avis sur Hacker News

• Il me semble que cet article passe à côté d’une raison plus importante pour laquelle le Q-learning a du mal à passer à l’échelle
  À mesure que l’horizon s’allonge, le nombre d’états possibles augmente généralement de façon exponentielle, et pour apprendre une fonction Q capable de traiter ces états, il faut aussi une quantité de données exponentielle
  En apprentissage on-policy, ce problème est moins marqué, car seuls les états proches de la politique actuelle comptent, et ce sont effectivement ces états-là qui sont échantillonnés

  • Je pense que l’analyse de l’article sur le biais de surestimation est correcte
    Le point clé est que l’opération max du Q-learning amplifie le bruit au fil des pas de temps, et des techniques d’atténuation du biais comme https://arxiv.org/abs/1509.06461 ont réussi à améliorer les performances des agents d’apprentissage par renforcement
    D’après les recherches, ce phénomène est plus marqué dans les états que le réseau a peu visités
    Le fait que le nombre d’états soit exponentiel n’est décisif que s’il n’existe aucun motif entre ces états. S’il y a une structure apprenable, cela peut bien fonctionner, et ce n’est pas une faiblesse du deep learning, mais une force
    L’enjeu est de choisir le bon objectif d’apprentissage, et l’article soutient en quelque sorte que le Q-learning n’est pas cet objectif
    Je me demande aussi si l’apprentissage par renforcement fondé sur un modèle, comme MuZero, pourrait répondre aux inquiétudes de l’auteur. MuZero peut améliorer l’efficacité de l’apprentissage en réanalysant les trajectoires précédentes, et la recherche arborescente de Monte-Carlo (MCTS) est une méthode de principe pour réduire l’horizon en déroulant le modèle sur plusieurs étapes
    L’opération max de MCTS peut créer des problèmes similaires, mais l’approfondissement de la recherche peut les compenser
  • https://news.ycombinator.com/item?id=44280505 ce fil pourrait peut-être être utile
    En tant que parfait non-spécialiste, je me dis que certaines tâches peuvent être « profondes » tout en restant suffisamment « uniformes » pour que de mauvais échantillons suffisent. J’aurais envie d’appeler ce genre de tâches des tâches ergodiques
    Bien sûr, il existe certainement aussi des tâches qui ne le sont pas
  • Cette différence revient-elle essentiellement à celle entre une intégration Monte-Carlo sur grille générale et une intégration Monte-Carlo par échantillonnage d’importance ?

• Cet article part déjà du principe qu’on connaît assez bien l’apprentissage par renforcement
  Si vous voulez vraiment vous y plonger, le cours d’introduction de David Silver (DeepMind) est excellent : https://youtu.be/2pWv7GOvuf0?si=CmFJHNnNqraL5i0s

• Je suis entièrement d’accord, et je trouve que c’est un très bon résumé
  En très court, le problème est de poursuivre une cible mouvante, qui change en fonction de la manière dont je me déplace
  Dans l’apprentissage par renforcement fondé sur la valeur, il n’existe pas de véritable réponse correcte vers laquelle converger. On minimise en quelque sorte un écart où sa propre approximation apparaît des deux côtés de l’équation
  Je ne trouve pas pour autant la situation désespérée. Je pense que l’apprentissage par renforcement est passé très près de fonctionner ; ce qui manquait jusqu’ici, c’était un modèle du monde / une fonction de dynamique directe fiable
  Avec cela, on peut planifier sans explorer, et nous disposons désormais de tels modèles

• Les avantages de l’apprentissage off-policy sont fondamentalement limités par le fait que les données inefficaces issues de l’exploration initiale ne sont pas très utiles pour améliorer une politique ultérieure plus affinée
  C’est évident si l’on pense aux erreurs aux échecs, aux mouvements saccadés, ou aux échecs dans la résolution d’un puzzle
  Cela devient encore plus clair quand on réalise que des données ne sont off-policy que lorsqu’elles décrivent des choses que la politique actuelle ne ferait pas
  La solution à ce problème me semble malheureusement liée au besoin d’une meilleure généralisation et d’une meilleure efficacité d’échantillonnage

  • Cet argument ne prouve-t-il pas trop de choses ?
    Comment expliquer le chien qui a appris à marcher en 20 minutes grâce à l’apprentissage off-policy, cité dans l’article ? Ou bien l’argument est-il plus subtil ?

• Je suis surpris que Decision Transformer ou Trajectory Transformer ne soient pas mentionnés
  Ce sont tous deux des approches offline et, grâce au mécanisme d’attention, elles contournent le problème d’attribution du crédit et fonctionnent plutôt bien sur des tâches à long horizon
  La plupart des chercheurs en apprentissage par renforcement ne considèrent pas ce type d’approche comme du « vrai apprentissage par renforcement », car elles ne peuvent pas attribuer le crédit au-delà de la fenêtre de contexte et ne peuvent donc pas apprendre des tâches à horizon infini
  Mais avec des fenêtres de contexte de plus d’un million de tokens, est-ce que ce ne serait pas moins problématique en pratique ? Je serais curieux d’avoir d’autres avis
  DT : https://arxiv.org/abs/2106.01345
  TT : https://arxiv.org/abs/2106.02039

  • TFP cite Decision Transformer
    Le simple fait d’utiliser un Transformer ne permet pas de contourner le problème d’attribution du crédit
    Un Transformer est une architecture destinée à résoudre des problèmes de modélisation séquentielle, et le problème d’attribution du crédit en apprentissage par renforcement en est un exemple. Il existait déjà beaucoup d’architectures de ce type auparavant
    Dire que le problème d’attribution du crédit est difficile, c’est parler de rareté des données. On ne peut pas le « contourner » par le seul choix d’une architecture

• Les humains font en réalité les deux
  Ils apprennent on-policy en explorant les conséquences de leurs propres actions, et aussi off-policy, par exemple à partir de démonstrations d’experts
  La différence, c’est que les humains savent distinguer les bonnes et les mauvaises actions, et peuvent filtrer pour n’apprendre que les actions qu’ils jugent bonnes
  Dans la plupart des apprentissages par renforcement off-policy, beaucoup de mauvaises actions sont incluses, et leur présence dans l’ensemble d’apprentissage ralentit l’apprentissage

  • « Savoir distinguer les bonnes et les mauvaises actions » n’est pas toujours vrai
    C’est pour cela que certaines démonstrations d’experts sont intéressantes. On peut voir des approches totalement erronées du point de vue des « bonnes pratiques » de niveau débutant produire pourtant de meilleurs résultats
    Bien sûr, parfois cela signifie seulement qu’à ce niveau de compétence, on peut se permettre ces techniques ou ces erreurs

• Il vaut la peine de noter que les tâches à long horizon que les humains apprennent par entraînement répété sont découpées en tâches à horizon plus court, puis apprises ensuite par composition hiérarchique

  • C’est peut-être naïf, mais cela ressemble davantage à un problème d’approche qu’à un problème d’algorithme
    Un modèle ne peut peut-être pas traiter une tâche à long horizon dès le départ, mais il peut d’abord apprendre des compétences à horizon court, puis utiliser ces petits blocs de compétences pour apprendre des horizons plus longs
    C’est le même principe que le chunking que nous pratiquons tous
    Personne n’apprend à piloter un avion de ligne sur un vol transcontinental comme une séquence de micro-mouvements des mains et des bras
    Enfant, on apprend bien à saisir une balle de cette manière, mais le pilotage ou le sport reposent sur une hiérarchie de compétences et de plans appris

• J’aime l’article, mais je pense que l’usage de sigles non expliqués réduit son utilité pour un public plus large
  C’est une petite remarque, mais il serait utile d’expliquer les sigles et le jargon

  • Pour les articles au contenu très bon mais peu accessibles parce qu’ils supposent énormément de connaissances préalables, il est assez utile de demander à des outils d’IA de les expliquer et de les simplifier
    Je viens de le faire avec le nouveau navigateur Dia, et cela a bien fonctionné. On peut aussi copier-coller le texte dans le fournisseur de modèle de son choix
    Cela permet de garder l’article concis, tout en pouvant poser des questions à l’outil d’IA et clarifier les points obscurs
  • Vu que la conclusion est « que quelqu’un crée donc une méthode de Q-learning qui passe à l’échelle », l’article s’adresse clairement à d’autres chercheurs en apprentissage par renforcement

• Ce qu’il y a de magique dans les méthodes off-policy comme le Q-Learning, c’est qu’elles convergent vers le résultat optimal même en ne voyant que des données d’entraînement non optimales
  Par exemple, même si l’on donne à Q-Learning en entrée un jeu de données de parties d’échecs jouées par des agents qui se déplacent totalement au hasard, sans aucune stratégie, il convergera quand même vers la politique optimale ; ce sera simplement plus lent qu’avec des entrées de haute qualité

  • Si c’est vrai, cela me semble proche de la définition d’une tâche ergodique
    J’emploie peut-être le terme de façon un peu détournée, mais je pense qu’il existe aussi des tâches non ergodiques