Quantum-Inspired Episode Selection for Monte Carlo Reinforcement Learning via QUBO Optimization

Résumé Technique : Sélection d'Épisodes Inspirée du Quantique pour l'Apprentissage par Renforcement de Monte Carlo via l'Optimisation QUBO

Énoncé du Problème
L'apprentissage par renforcement de Monte Carlo (MC) fait face à des défis importants concernant l'efficacité de l'échantillonnage, particulièrement dans les environnements caractérisés par des récompenses éparses, des espaces d'états étendus et des trajectoires temporellement corrélées. Les méthodes MC standards reposent sur l'hypothèse que les échantillons de données sont indépendants et identiquement distribués (i.i.d.), une hypothèse violée par la nature markovienne des trajectoires de l'apprentissage par renforcement (RL). Par conséquent, les estimateurs MC souffrent de :

1. Propagation de la Variance : Les retours présentent une variance composée, nécessitant un nombre d'épisodes ($N_s$) qui croît selon $O(\epsilon^{-2})$ pour réduire l'erreur d'estimation.
2. Dilution Suboptimale des Trajectoires : Dans les domaines à récompenses éparses, l'estimateur est dilué par des trajectoires à faible récompense, nécessitant une croissance exponentielle de la taille de l'échantillon pour garantir une couverture suffisante des chemins optimaux.
3. Explosion Combinatoire : Théoriquement, sélectionner un sous-ensemble optimal de $m$ épisodes parmi $N$ candidats pour maximiser la précision de l'estimation de la valeur est un problème NP-difficile isomorphe à la sélection de caractéristiques et à la couverture d'ensembles, avec un espace de solutions de $\binom{N}{m}$.

Méthodologie
Les auteurs proposent MC+QUBO, un cadre qui reformule le processus de sélection d'épisodes comme un problème d'Optimisation Quadratique Non Contrainte Binaire (QUBO). Au lieu d'utiliser tous les épisodes échantillonnés pour les mises à jour de politique, la méthode filtre un lot de trajectoires pour sélectionner un sous-ensemble qui maximise la récompense cumulée tout en favorisant la couverture de l'espace d'états (diversité).

• Formulation QUBO : Le problème de sélection est codé comme :
  $$\min_{x \in \{0,1\}^n} \left( -\alpha \sum_{i=1}^n R_i x_i + \gamma \sum_{i<j} w_{ij} x_i x_j \right)$$
  Où :

  • $x_i = 1$ indique la sélection de l'épisode $\tau_i$.
  • $R_i$ est la récompense cumulée de l'épisode $i$.
  • $w_{ij}$ représente la similitude par paire entre les épisodes (par exemple, la similitude de Jaccard des ensembles d'états visités).
  • $\alpha$ est un multiplicateur d'échelle de la récompense, et $\gamma$ pondère la pénalité de similitude.
  • Le terme linéaire ($-\alpha R_i$) favorise les épisodes à haute récompense, tandis que le terme quadratique ($\gamma w_{ij}$) pénalise la redondance, encourageant la sélection de trajectoires diverses.

• Solveurs Inspirés du Quantique : Le problème QUBO est résolu à l'aide de samplers (échantillonneurs) inspirés du quantique en boîte noire, spécifiquement le Recuit Quantique Simulé (SQA) et la Bifurcation Simulée (SB).

  • SQA imite le recuit quantique en utilisant des mises à jour stochastiques classiques et le Monte Carlo par intégrale de chemin pour simuler l'effet tunnel quantique entre les minima d'énergie.
  • SB utilise une approche de système dynamique classique où les variables continues évoluent vers des états binaires via des phénomènes de bifurcation.
  • Les auteurs traitent ces solveurs comme des oracles fournissant des solutions approximatives de haute qualité dans des budgets computationnels pratiques.

• Intégration : Le flux de travail consiste à générer un lot d'épisodes, calculer les récompenses et les similitudes, formuler le QUBO, le transmettre au solveur, puis utiliser la meilleure solution observée (le vecteur binaire $x^*$) pour déterminer quels épisodes sont utilisés pour mettre à jour la table de valeurs d'action $Q(s, a)$ via le MC de première visite.

Principales Contributions

1. Reformulation de la Sélection d'Épisodes : L'article établit un lien formel entre la sélection d'épisodes MC et l'optimisation combinatoire, démontrant que le problème de sélection peut être mappé vers une formulation QUBO.
2. Intégration Algorithmique : Il introduit un pipeline concret (Algorithme 2) qui insère une étape de filtrage basée sur QUBO entre l'échantillonnage de trajectoires et l'évaluation de la politique dans l'apprentissage MC standard.
3. Validation Empirique : L'étude évalue la méthode sur des environnements GridWorld à horizon fini de tailles variées ($3\times3$ à $20\times20$), comparant MC+QUBO à une base de référence MC vanilla.

Résultats
Les expériences menées dans des environnements GridWorld démontrent que MC+QUBO surpasse systématiquement le MC vanilla en termes de vitesse de convergence et de qualité de la politique finale.

• Scalabilité : L'écart de performance s'élargit dans les environnements plus grands ($\ge 10\times10$), où les récompenses éparses et la croissance exponentielle de l'espace d'états entravent généralement l'évaluation MC standard.
• Convergence : MC+QUBO converge en moins de lots en se concentrant sur des trajectoires informatives et diverses, filtrant efficacement les épisodes redondants.
• Insight de Conception : Les auteurs notent que prioriser la couverture de l'espace d'états (en réglant l'influence du poids de la récompense proche de zéro) a produit un apprentissage plus équilibré et une meilleure généralisation que la sélection pilotée par la récompense, laquelle tendait à provoquer une convergence plus rapide mais moins stable.
• Performance des Solveurs : Les solveurs inspirés du quantique (SQA et SB) ont surpassé les heuristiques classiques (telles que la recherche Tabu et le Recuit Simulé) dans ce contexte. La latence de calcul était dominée par la communication cloud plutôt que par le temps de résolution lui-même (qui était négligeable pour $n \le 200$).

Signification et Revendications
L'article affirme que l'intégration de l'optimisation inspirée du quantique en tant que sous-routine de prise de décision dans l'apprentissage par renforcement offre une amélioration pratique pour les méthodes MC, particulièrement pour les problèmes avec des récompenses éparses et des trajectoires corrélées. En jetant un pont entre le RL et l'optimisation combinatoire, l'étude suggère une voie pour des algorithmes où les méthodes quantiques et inspirées du quantique guident activement le processus d'apprentissage pour surmonter l'inefficacité de l'échantillonnage.

Les auteurs restent modestes quant à la portée de leurs travaux, notant que bien que le cadre soit prometteur dans GridWorld, des travaux futurs sont nécessaires pour explorer les extensions au contrôle continu, l'apprentissage hiérarchique et les systèmes multi-agents, ainsi que le déploiement sur du matériel quantique réel. Le présent travail sert de preuve de concept pour l'utilisation de solveurs inspirés de la physique pour optimiser la phase de sélection de données de l'apprentissage par renforcement.