Finding the Time to Think: Learning Planning Budgets in Real-Time RL

Résumé Technique : Trouver le temps de réfléchir : Budgets de planification de l'apprentissage en renforcement en temps réel

Définition du problème : RL en temps réel à délai variable

L'apprentissage par renforcement (RL) standard et les processus de décision markoviens (MDP) opèrent sous l'hypothèse que l'environnement attend indéfiniment que l'agent calcule une action ; ainsi, la délibération n'entraîne aucun coût. Dans les contextes en temps réel, cette hypothèse échoue : l'environnement progresse de manière continue, indépendamment du temps de calcul de l'agent. Une action parfaite exécutée trop tard est souvent inférieure à une action sous-optimale mais opportune.

Alors que des travaux antérieurs (Ramstedt & Pal, 2019) ont formalisé le RL en temps réel avec un délai fixe (par exemple, exactement un pas de temps pour calculer), cet article introduit le RL en temps réel à délai variable. Dans ce cadre, l'agent n'est pas une fonction statique mais une procédure s'exécutant dans le temps. L'agent doit décider combien de temps délibérer à chaque point de décision. Le coût de la délibération est « payé » sous forme de progression environnementale (ou d'épuisement du chronomètre dans les jeux de plateau) pendant que l'agent calcule. Cela crée un défi de méta-raisonnement : l'agent doit équilibrer la qualité de l'action planifiée et la dégradation de l'état causée par le temps passé à planifier. Planifier naïvement la durée de la planification risque d'engendrer un paradoxe où la méta-décision elle-même incorpore les mêmes coûts temporels que la planification qu'elle cherche à optimiser.

Méthodologie

Les auteurs proposent une solution basée sur un Processus de Décision Semi-Markovien (SMDP) sur des options budgétisées, découplant l'algorithme de planification de la décision de combien planifier.

1. Composants de l'architecture :

   • Politique réflexe ($\pi_{reflex}$) : Une politique rapide et légère (par exemple, la tête de politique d'un modèle AlphaZero sans MCTS) qui s'exécute en bien moins d'une image (frame). Elle fournit des actions immédiates pour l'environnement pendant que le planificateur tourne en arrière-plan.
   • Calculs d'affinement d'action de type « anytime » ($\{c_k\}$) : Un ensemble fini de calculs indexés par une durée discrète $k$. Dans ce travail, ils sont instanciés comme des exécutions de recherche arborescente Monte Carlo (MCTS) pour $k$ images. Des exécutions plus longues ($c_k$) produisent des actions de meilleure qualité mais prennent plus de temps.
   • Options budgétisées ($o_k$) : Chaque option $o_k$ enveloppe un calcul $c_k$. Lorsqu'elle est initiée, l'agent s'engage à exécuter $k-1$ actions tirées de $\pi_{reflex}$ pendant que $c_k$ s'exécute. À la $k$-ième image, l'action affinée de $c_k$ est exécutée.
   • Politique de déclenchement ($\pi_{gate}$) : Un réseau de neurones léger entraîné via l'Optimisation de Politique Proximale (PPO) qui agit comme une méta-politique. Il observe l'état actuel (observation du jeu, caractéristiques du planificateur et estimations de valeur) et sélectionne le budget $k$ (la durée de l'option) pour la prochaine méta-étape.

2. Protocole d'entraînement :

   • Entraînement en deux phases : D'abord, des planificateurs de type AlphaZero sont entraînés pour des environnements spécifiques. Ces planificateurs sont ensuite gelés. Ensuite, la politique de déclenchement est entraînée sur le planificateur gelé.
   • Formulation de Méta-MDP : La politique de déclenchement résout un problème de contrôle discret où les actions sont la sélection d'options budgétisées. La récompense est le rendement cumulé sur les $k$ images de l'option, actualisé par $\gamma^k$.
   • GAE adapté : Parce que les méta-étapes ont des durées variables ($k$), les auteurs adaptent l'Estimation de l'Avantage Généralisée (GAE) pour propager l'actualisation par étape de méta $\gamma^k$ à travers le calcul de l'avantage.

3. Instanciations d'environnements :

   • Environnements à actions engagées (Pac-Man, Tetris en temps réel, Snake) : L'environnement progresse de manière continue. L'agent exécute $k-1$ actions réflexes pendant la planification. Le coût de la planification est le changement de l'état du monde pendant le calcul.
   • Environnements à chronomètre (Speed Hex, Speed Go) : Le plateau est statique, mais un chronomètre partagé s'épuise avec le temps de réflexion. La politique réflexe émet des « no-ops » (opérations nulles) pendant la fenêtre de planification. Le coût est la réduction du budget de temps restant.

Contributions clés

1. Cadre de RL en temps réel à délai variable : Une généralisation des cadres à délai fixe où l'agent choisit sa propre durée de délibération, traitant la sélection du délai comme un problème apprenable plutôt que comme une contrainte imposée par le système.
2. Caractérisation empirique des compromis de planification : Les auteurs établissent que la qualité de la planification et la latence d'inférence évoluent conjointement avec le nombre de simulations MCTS. Cette mise à l'échelle conjointe motive la nécessité d'une allocation adaptative plutôt que de budgets fixes.
3. Déclenchement adaptatif sur des planificateurs gelés : Une méthode pour apprendre des budgets de planification dépendant de l'état en utilisant une politique de déclenchement légère entraînée sur un planificateur AlphaZero gelé. Cela évite le paradoxe de la « planification de la planification », car un passage direct (forward pass) de la porte est des ordres de grandeur moins coûteux qu'un déroulement MCTS.
4. Validation matérielle en conditions réelles : La méthode est validée dans un déploiement asynchrone sur deux GPU (un GPU pour l'environnement/réflexe, un pour le MCTS) sans changements architecturaux ni réentraînement, démontant que la politique entraînée en simulation se transfère efficacement vers une exécution séparée sur matériel.

Résultats

La politique de déclenchement a été évaluée dans cinq environnements : Pac-Man, Tetris en temps réel, Snake, Speed Hex et Speed Go.

• Performance par rapport aux bases de référence : La politique de déclenchement adaptative a systématiquement surpassé :
  • Les politiques à budget fixe : Agents contraints à un seul $k$ (par exemple, toujours planifier pour 1, 2, 3 ou 4 images).
  • Les bases de référence heuristiques : Incluant « Greedy » (toujours le maximum de simulations) et « Midpeak » (allocation en cloche courante dans les moteurs de jeu).
  • Les bases de référence aléatoires : La sélection aléatoire de budgets a été nettement moins performante, confirmant que le moment de l'allocation de calcul est aussi critique que la quantité.
• Gains spécifiques :
  • Pac-Man : +10,3 % d'amélioration par rapport au meilleur budget fixe.
  • Tetris en temps réel : +65 % d'amélioration par rapport au meilleur budget fixe.
  • Snake : +10,9 % d'amélioration.
  • Speed Hex/Go : La politique de déclenchement a obtenu des scores attendus plus élevés que les budgets fixes et les heuristiques à travers diverses contraintes de chronomètre.
• Analyse comportementale : La politique de déclenchement a appris à allouer une planification plus profonde ( $k$ élevé) dans des états à enjeux élevés ou contraints (ex: fantômes proches dans Pac-Man, plateaux denses dans Tetris, faible accessibilité dans Snake) et a réagi rapidement ( $k$ faible) dans des états sûrs ou ouverts. Elle a également démontré une généralisation à différents budgets de chronomètre dans Speed Hex/Go sans réentraînement.
• Transfert matériel : Dans une configuration asynchrone à deux GPU (H100, A100, A40), les politiques se sont transférées proprement de la simulation au matériel réel. La latence est restée dans les limites sur H100 et A100, et les rendements étaient très proches de ceux de la simulation.

Signification et affirmations

L'article affirme traiter un décalage fondamental entre le RL standard et l'interaction en temps réel en formalisant le temps de délibération comme une ressource qui doit être gérée dynamiquement. La portée réside dans :

• Échapper au paradoxe de la méta-raisonnement : En utilisant une porte légère sur un planificateur gelé, le système évite la surcharge de calcul liée à la planification de la planification, rendant l'approche pratique pour le déploiement en temps réel.
• Allocation de ressources dépendante de l'état : Les résultats démontrent qu'un budget de planification fixe est sous-optimal ; la valeur du calcul est hautement dépendante de l'état.
• Passage à l'échelle vers le matériel asynchrone : Le protocole d'entraînement à « actions engagées » modélise avec succès la dynamique de l'exécution asynchrone, permettant aux politiques entraînées en simulation de se déployer sur des matériels séparés (environnement vs planificateur) sans modification.

Limites reconnues :

• Le cadre suppose un simulateur d'environnement parfait pour les étapes engagées (le MCTS doit prédire avec précision les $k-1$ actions réflexes).
• La politique de déclenchement est entraînée sur un planificateur gelé ; l'optimisation conjointe du planificateur et de la porte est laissée comme travail futur.
• L'ensemble des budgets $\mathcal{K}$ est calibré manuellement et discret ; des vocabulaires de calcul continus ou plus riches sont suggérés comme extensions futures.