- Ces derniers temps, la scalabilité de l’apprentissage par renforcement (RL) attire l’attention, comme on l’a vu avec les grands modèles de langage (LLM)
- En pratique, AlphaGo, les LLM, etc. affichent de fortes performances, mais ils utilisent principalement des algorithmes de RL on-policy
- Le Q-learning, algorithme emblématique du RL off-policy, passe mal à l’échelle sur les problèmes à long horizon à cause d’un problème de biais cumulatif
- Les résultats expérimentaux montrent que, même en augmentant fortement les données et la puissance de calcul, les algorithmes standards de la famille du Q-learning atteignent des limites de performance sur des tâches complexes de long terme
- Il n’existe guère que des solutions locales, comme les méthodes hiérarchiques qui atténuent le problème du horizon ; il faut donc un nouvel objectif de RL off-policy fondamentalement scalable
Le RL est-il scalable ?
- Ces derniers temps, la prédiction du prochain token des modèles de langage, les modèles de diffusion et l’apprentissage contrastif sont des objectifs qui passent bien à l’échelle à mesure que l’on augmente les données et le calcul
- Dans les jeux, les mathématiques, le code, etc., le RL a lui aussi obtenu des résultats marquants, souvent grâce à des algorithmes de RL on-policy (par ex. PPO, REINFORCE)
- Le RL on-policy ne peut utiliser que de nouveaux roll-outs, c’est-à-dire des données générées directement par la politique la plus récente
- Cette approche n’est pas un gros problème en simulation ou pour les LLM, mais elle est très inefficace dans les environnements réels comme la robotique
- Par exemple, en robotique, obtenir suffisamment de données peut prendre plusieurs mois et nécessite une intervention humaine manuelle
L’émergence du RL off-policy
- Le RL off-policy est très efficace en sample efficiency, car il permet de réutiliser toutes les données passées
- Le Q-learning en est l’algorithme représentatif le plus utilisé, avec des résultats par exemple sur la marche en temps réel de robots quadrupèdes
- Le Q-learning s’appuie sur la minimisation de la perte de différence temporelle (TD loss), et presque tout le RL off-policy repose sur ce principe
- Pour appliquer le RL à des problèmes du monde réel, la question centrale devient donc : le Q-learning peut-il lui aussi passer à l’échelle ?
Les limites de passage à l’échelle du Q-learning
- L’auteur soutient que le Q-learning actuel ne passe pas bien à l’échelle dès que l’on rencontre des problèmes à long horizon (plus de 100 étapes de décision)
- Ici, la « scalabilité » désigne la capacité à résoudre un problème même si sa profondeur/difficulté (“depth”) augmente, simplement en ajoutant des données et des ressources de calcul
- Comme l’ont montré expérimentalement plusieurs articles, il ne s’agit pas simplement d’augmenter le nombre de problèmes traitables, c’est-à-dire la “width”
- Thèse de l’auteur : la famille du Q-learning est peu scalable sur l’axe de la profondeur (difficulty), et des innovations algorithmiques sont indispensables
- Deux principaux arguments étayent cette idée : l’absence de grands succès empiriques, et une série récente d’expériences systématiques
Éléments empiriques
- AlphaGo, AlphaZero et MuZero relèvent tous du RL on-policy à base de modèle (model-based), et non de la famille du TD-learning
- OpenAI Five repose lui aussi sur des méthodes on-policy comme PPO
- Pour le RL appliqué aux LLM, ce sont également majoritairement des variantes on-policy de type policy gradient qui dominent
- Le Q-learning et les méthodes similaires de RL off-policy n’ont presque aucun exemple concret de réussite à très grande échelle, au niveau d’AlphaGo ou des LLM
- L’auteur indique qu’après avoir examiné divers articles et cas pratiques, il ne connaît pas de grand succès reposant sur le Q-learning
D’où viennent les limites du Q-learning : horizon et biais cumulatif
- Dans le Q-learning, les cibles TD construites par bootstrap (prédictions générées à partir d’estimations) sont toujours biaisées ; ce biais s’accumule le long du time-horizon
- À l’inverse, d’autres objectifs très scalables, comme la prédiction de token, la diffusion ou l’apprentissage contrastif, n’ont pas de biais cumulatif dans leurs cibles de prédiction
- Plus le horizon (la longueur de décision) est grand, plus l’accumulation des erreurs limite la montée en puissance du Q-learning
- C’est pourquoi on règle souvent le discount factor à une valeur plus faible pour atténuer ce problème
- Les approches on-policy d’estimation de valeur, comme le policy gradient, sont relativement moins affectées par le problème de horizon grâce à des techniques comme GAE
Vérification expérimentale des limites de scalabilité
- Dans un article récent, des tâches difficiles de plusieurs milliers d’étapes ont été conçues sur OGBench et d’autres environnements pour étudier les tâches à ultra-long horizon
- Les facteurs de bruit ont été minimisés en supposant des données « presque infinies », des modèles puissants et une réduction de la charge liée aux réseaux de représentation
- Les méthodes classiques d’offline RL (BC, IQL, CRL, SAC+BC, etc.) n’ont pas réussi à apprendre des tâches complexes, même avec des jeux de données gigantesques
- Des tests d’ablation ont été menés sur toutes les variables — taille des données et des modèles, durée d’apprentissage, hyperparamètres, etc. — sans parvenir à dépasser ces limites
- En revanche, seules les techniques qui réduisent le horizon (la longueur de décision) ont montré un effet clair sur la scalabilité des performances
L’effet des techniques de réduction du horizon
- Le n-step return, le RL hiérarchique et d’autres approches de réduction du horizon sont les seules à montrer un effet décisif sur le scaling du RL
- La réduction du horizon n’accélère pas seulement l’apprentissage : elle améliore aussi radicalement la performance finale elle-même
- Mais ces méthodes ne résolvent pas le problème à la racine ; elles ne font que réduire le horizon d’un facteur constant
- Il faut donc une nouvelle approche algorithmique capable de lever la malédiction du horizon
Pourquoi il faut un nouvel objectif off-policy scalable
- Les travaux menés jusqu’ici montrent qu’augmenter simplement la taille des données ou des modèles ne permet pas de surmonter fondamentalement la malédiction du horizon
- À terme, il faudra une variante de RL off-policy capable de passer à l’échelle sur des problèmes de long terme de longueur arbitraire
- Si cet objectif est atteint, il deviendra possible de traiter un ensemble beaucoup plus large de problèmes réels impliquant des robots, des LLM et divers agents de décision
Idées et propositions pour la suite
- Au-delà des hiérarchies à deux niveaux, il serait possible de proposer une nouvelle structure hiérarchique simple et scalable capable de traiter des horizons de longueur arbitraire
- Le RL à base de modèle (model-based RL) pourrait être scalable en combinant une modélisation fondée sur l’apprentissage supervisé et du RL on-policy
- Il peut aussi être utile d’explorer de nouvelles familles comme quasimetric RL ou contrastive RL, qui écartent complètement le TD learning
- L’environnement d’évaluation et le code publiés peuvent servir de benchmark de tests de passage à l’échelle pour divers nouveaux algorithmes de RL
Remerciements
- L’auteur remercie plusieurs chercheurs pour leur collaboration et leurs retours sur l’article et le billet
- Il précise que ce contenu s’appuie notamment sur l’article [Horizon Reduction Makes RL Scalable] et reflète son opinion personnelle
1 commentaires
Commentaires sur Hacker News
Je pense que les limites de scalabilité du Q-Learning sont encore plus importantes que ce que le blog mentionne. Le nombre d’états qu’un agent doit gérer augmente généralement de façon exponentielle à mesure que l’horizon augmente. En conséquence, les besoins en données pour entraîner les Q correspondant à ces états augmentent eux aussi exponentiellement. À l’inverse, l’apprentissage on-policy n’apprend que les états importants, ce qui simplifie relativement le problème en concentrant les données d’entraînement uniquement là où elles sont nécessaires, malgré un espace d’états exponentiel
Je suis d’accord avec l’analyse du biais de sur-approximation du Q-learning évoquée dans l’article. L’opérateur Max du Q-learning a tendance à amplifier le bruit le long de l’axe temporel. Il existe aussi des cas où des méthodes d’atténuation du biais, comme dans cet article, ont effectivement amélioré les performances d’agents RL. Des travaux montrent également que ce phénomène apparaît plus facilement dans des états peu visités par le réseau. L’un des points forts du deep learning est que, même si le nombre d’états augmente exponentiellement, de bonnes performances restent possibles s’il existe une structure apprenable. L’essentiel est de définir le bon objectif d’entraînement, et l’article soutient que le Q-learning a des limites sur ce point. Je me demande si des systèmes de RL basés sur un modèle, comme MuZero, pourraient constituer une solution. MuZero améliore l’efficacité de l’entraînement en réanalysant des trajectoires précédentes, et Monte Carlo Tree Search (MCTS) est une manière principielle de réduire l’horizon en déroulant plusieurs étapes. Le problème de l’opérateur Max peut aussi apparaître dans MCTS, mais ce type d’effet peut être compensé à mesure que la recherche devient plus profonde
Je pense que ce fil peut être utile. D’un point de vue totalement non spécialiste, certaines tâches semblent conserver une certaine homogénéité malgré leur « profondeur », et dans ce cas l’apprentissage reste possible même si la qualité des échantillons est un peu moins bonne. J’aurais envie d’appeler ce type de tâches « ergodiques ». Mais je pense qu’il existe clairement aussi des tâches qui ne le sont pas nécessairement
Je me demande si cela ressemble à la différence entre l’intégration de Monte Carlo sur grille classique et l’intégration de Monte Carlo par échantillonnage d’importance
Impression sur Majorana-1
Je trouve dommage que le blog ne mentionne pas les approches hors ligne comme Decision Transformers et Trajectory Transformers. Grâce au mécanisme d’attention, elles évitent le problème de credit assignment et obtiennent de bonnes performances sur les tâches à long horizon. Beaucoup de chercheurs en RL estiment que ces approches ne sont pas du « vrai RL », car elles ne peuvent pas attribuer du crédit au-delà de la fenêtre de contexte. Elles sont donc souvent considérées comme peu adaptées aux tâches à horizon infini. Mais si la fenêtre de contexte dépasse le million, je me demande si cela ne devient pas en pratique beaucoup moins problématique. Voir l’article sur le Decision Transformer et celui sur le Trajectory Transformer
Je pense que cela résume bien l’essence de la RL. Très simplement, c’est comme être en mouvement permanent à poursuivre un objectif dont la position continue elle-même à changer en fonction de la manière dont je me déplace. Autrement dit, en RL fondée sur la valeur, il n’existe pas de vérité absolue (ground truth) ; c’est un jeu où l’on ajuste les deux côtés uniquement à partir de ses propres estimations. Mais je ne pense pas que ce soit désespéré. Au contraire, j’ai le sentiment que la RL est désormais proche d’un usage pratique, notamment parce qu’on a longtemps manqué de world models ou de fonctions de dynamique fiables. Or il y a maintenant de grands progrès aussi sur ce point
Cet article / billet de blog s’adresse à des personnes ayant déjà des connaissances en RL. Si vous voulez approfondir le sujet, je recommande le cours d’introduction de David Silver (Deep Mind)
La limite fondamentale de l’apprentissage off-policy, c’est que des données d’exploration initiale peu efficaces aident peu à apprendre une politique plus avancée. En échec, par exemple, cela correspondrait à des erreurs de débutant, des coups dénués de sens ou des comportements incapables de résoudre un puzzle. Les données deviennent off-policy à partir du moment où ces actions s’écartent de la politique actuelle, c’est-à-dire de ce que l’agent choisirait réellement. Au fond, le cœur du problème tient donc à une meilleure généralisation et à une meilleure efficacité échantillonnale
Quand les humains apprennent des tâches de long terme (à horizon long), ils procèdent souvent par entraînement répété en découpant la tâche globale en sous-tâches à horizon court, puis en combinant ensuite ces compétences partielles de manière hiérarchique
Les humains utilisent en réalité à la fois l’apprentissage on-policy et off-policy. Ils apprennent on-policy en explorant directement les conséquences de leurs actions, et apprennent aussi off-policy en observant les démonstrations d’autres experts. Mais la différence avec la RL, c’est que les humains distinguent les bonnes actions des mauvaises et ne retiennent pour apprendre que les « bonnes ». À l’inverse, dans la plupart des approches RL off-policy, les mauvaises actions sont elles aussi utilisées comme données, ce qui ralentit l’entraînement global
J’aime bien le contenu du blog, mais je trouve regrettable que l’usage d’acronymes et de termes spécialisés non expliqués en réduise l’utilité pour un lectorat plus large. Il aurait été préférable d’expliquer les termes et les acronymes pour améliorer l’accessibilité
Pour ce genre de billet de blog, dont le contenu est très riche mais qui demande beaucoup de connaissances préalables et reste donc peu accessible, les outils d’IA sont très utiles pour fournir des explications et des versions simplifiées. J’ai récemment utilisé Dia dans le navigateur et je l’ai trouvé efficace. Même un simple copier-coller dans un autre modèle d’IA permet d’obtenir à la fois une vue d’ensemble concise et des éclaircissements sur les points qui posent question
On sent que ce genre de texte a été clairement écrit pour des chercheurs en RL. La conclusion ressemble à : « Quelqu’un peut-il trouver un moyen de rendre le Q-learning scalable ? »
Je pense au contraire que c’est justement ce qui rend ce texte plus propre
La force des techniques off-policy comme le Q-Learning, c’est qu’il suffit d’obtenir des données sous-optimales (pas très bonnes) pour finir malgré tout par converger vers la solution optimale. Par exemple, même si l’on collecte uniquement des parties d’échecs sans stratégie particulière et qu’on les utilise comme entrée pour le Q-Learning, il reste possible d’apprendre au final la politique optimale (même si ce sera plus lent qu’avec de bonnes données)