Résumé Technique : Un peu de liberté fait toute la différence : Algorithmes classiques et quantiques pour l'apprentissage par renforcement sous un modèle génératif

Énoncé du Problème

L'article traite du problème de l'apprentissage des processus de décision de Markov (MDP) dans un cadre en ligne, en se concentrant spécifiquement sur la minimisation du regret (la différence entre la récompense accumulée par l'agent et celle d'une politique optimale). Les auteurs considèrent trois contextes de MDP distincts :

1. MDP à horizon fini : Les interactions se produisent sur un nombre fixe d'étapes $H$.
2. MDP à horizon infini avec remise (discounting) : Les interactions se poursuivent indéfiniment avec des récompenses actualisées par un facteur $\gamma \in [0, 1)$.
3. MDP à horizon infini sans remise : Les interactions se poursuivent indéfiniment selon des critères de récompense moyenne, en se concentrant spécifiquement sur les MDP faiblement communicants.

Un défi central de l'apprentissage par renforcement (RL) est le compromis entre exploration et exploitation. Dans le cadre classique, les agents doivent apprendre les probabilités de transition $p(\cdot|s, a)$ tout en interagissant avec l'environnement. Dans le cadre quantique, un problème fondamental surgit : les oracles quantiques standards permettent la superposition et les opérations inverses, ce qui peut conduire à des mesures de regret mal définies si l'agent interagit avec l'environnement de manière quantique tout au long du processus d'apprentissage. De plus, les travaux antérieurs de RL quantique tentant d'atteindre un regret polylogarithmique en temps $T$ reposaient sur des hypothèses erronées concernant l'application cohérente de l'estimation d'amplitude quantique.

Méthodologie

Le Modèle Hybride RL en Ligne-Hors Ligne

Pour résoudre les problèmes de définition du regret dans le RL quantique et pour tirer parti des accélérations quantiques, les auteurs proposent un modèle de RL hybride en ligne-hors ligne. Ce modèle sépare le processus d'apprentissage en deux phases distinctes :

1. Phase en ligne (Exploration) : L'agent interagit avec l'environnement de manière classique. Il choisit des actions, reçoit des récompenses et observe les transitions d'état. Crucialement, le regret s'accumule durant cette phase. L'agent n'a pas accès aux oracles quantiques ici.
2. Phase hors ligne (Apprentissage Génératif) : L'agent bénéficie de la « liberté » d'interagir avec l'environnement via un modèle génératif.
   • Dans la phase hors ligne classique, l'agent accède à un oracle d'échantillonnage $C_p$ qui renvoie les états suivants $s'$ donnés $(s, a)$.
   • Dans la phase hors ligne quantique, l'agent accède à un oracle quantique $Q_p$ (et son inverse) qui prépare des superpositions des états suivants.
   • Contrainte : Le nombre d'appels d'oracle dans la phase hors ligne est limité par une fonction de la longueur de la phase en ligne précédente $\tau$, spécifiquement $O(\tau^\beta)$, où $\beta \in [0, \infty)$ est un paramètre de « budget ». Cela empêche l'agent d'obtenir une politique quasi optimale avec un regret nul en interrogeant excessivement l'oracle.

Approche Algorithmique

Les algorithmes proposés (Algorithme 1) progressent par époques. Dans chaque époque $\ell$ :

1. Calcul Hors Ligne : En utilisant les données collectées lors de la phase en ligne précédente (longueur $\tau_{\ell-1}$), l'agent calcule une politique $\epsilon_\ell$-optimale.
   • Classique : Utilise des algorithmes d'optimisation par échantillonnage connus (ex: Sidford et al.) pour calculer les politiques.
   • Quantique : Les auteurs introduisent de nouveaux algorithmes quantiques pour calculer les politiques optimales sous un modèle génératif. Ces algorithmes utilisent l'estimation de moyenne quantique (Kothari et O'Donnell) et la recherche de minimum/maximum quantique (Dürr et Høyer) pour accélérer l'itération de valeur.
2. Exécution en Ligne : La politique calculée $\pi^{(\ell)}$ est exécutée dans l'environnement pour une durée déterminée par une technique de doublement (augmentation de l'horizon par un facteur 2 ou $2H$).
3. Analyse du Regret : Le regret total est borné par la somme de la sous-optimalité des politiques utilisées dans chaque phase en ligne.

Contributions Techniques Clés

1. Nouveaux Algorithmes Quantiques pour les Modèles Génératifs :

   • Horizon Fini : Les auteurs conçoivent des algorithmes quantiques qui améliorent la complexité de requête classique. Ils combinent l'itération de valeur quantifiée avec des techniques de réduction de variance. La complexité de requête est $\tilde{O}(\min\{H^{2.5}SA/\epsilon, H^3S\sqrt{A}/\epsilon\})$, améliorant la dépendance envers $H$ et $A$ par rapport aux bornes classiques.
   • Horizon Infini avec Remise : Des améliorations similaires sont obtenues, avec une complexité de requête de $\tilde{O}(\min\{\Gamma^{1.5}SA/\epsilon, \Gamma^3S\sqrt{A}/\epsilon\})$.
   • Horizon Infini Sans Remise : Il s'agit d'une nouvelle contribution. Les auteurs proposent un algorithme quantique pour les MDP faiblement communicants sous l'hypothèse que l'opérateur de Bellman optimal est une contraction de span-$\nu$ à $J$ étapes. La complexité est $\tilde{O}(\Lambda S \sqrt{A} / \epsilon)$.

2. Correction des Travaux Antérieurs de RL Quantique :
   L'article critique les travaux précédents (ex: Ganguly et al., Zhong et al.) qui prétendaient un regret polylogarithmique. Les auteurs soutiennent que ces travaux ont supposé à tort que l'estimation d'amplitude quantique pouvait être effectuée sur une collection d'états stockés plutôt que nécessitant des applications séquentielles et cohérentes de l'oracle et de son inverse. Le modèle hybride proposé corrige cela en imposant une phase hors ligne distincte où de telles opérations cohérentes peuvent être effectuées sans engendrer de regret.

3. Bornes de Regret sous le Modèle Hybride :
   Les auteurs dérivent des bornes de regret pour les contextes classiques et quantiques en fonction du paramètre de budget $\beta$ :

   • Horizon Fini :
     • Classique : $\tilde{O}(\sqrt{HSAT})$ (correspondant à l'état de l'art) quand $\beta \ge 2$.
     • Quantique : $\tilde{O}(\min\{H^{1.5}SA, H^2S\sqrt{A}\} T^{1-\beta})$ pour $\beta < 1$, et polylogarithmique en $T$ pour $\beta \ge 1$.
   • Horizon Infini avec Remise :
     • Quantique : Atteint un regret $\tilde{O}(\text{polylog}(T))$ quand $\beta \ge 1$, brisant la barrière classique de $\Omega(\sqrt{T})$.
   • Horizon Infini Sans Remise :
     • Quantique : Atteint un regret $\tilde{O}(\Lambda S \sqrt{A} \cdot \text{polylog}(T))$ pour $\beta \ge 1$, améliorant significativement la borne $\tilde{O}(\Lambda S^5 A^4)$ des travaux quantiques antérieurs.

Résultats et Signification

L'article affirme que le « peu de liberté » fourni par la phase générative hors ligne permet une amélioration substantielle de l'efficacité de l'apprentissage.

• Avantage Quantique : Le résultat le plus significatif est la démonstration que les ordinateurs quantiques peuvent atteindre un regret polylogarithmique dans l'horizon temporel $T$ (spécifiquement lorsque $\beta \in [1, 2)$), alors que les algorithmes classiques sont fondamentalement limités à un regret de $\Omega(\sqrt{T})$ dans ces contextes. Cela représente une amélioration exponentielle de la dépendance envers $T$.
• Dépendance des Paramètres : Les algorithmes quantiques améliorent la dépendance envers la taille de l'espace d'états $S$, l'espace d'actions $A$, et l'horizon $H$ (ou l'horizon effectif $\Gamma$) par rapport aux algorithmes classiques et aux tentatives quantiques précédentes.
• Validité du Modèle : L'article établit que le modèle hybride en ligne-hors ligne est un cadre nécessaire et significatif pour le RL quantique. Il résout l'ambiguïté de la définition du regret dans les interactions quantiques et corrige les failles théoriques de la littérature antérieure qui supposait une exploration quantique sans regret.

Les auteurs concluent que bien que l'avantage quantique exponentiel en $T$ disparaisse lorsque le budget $\beta$ est très élevé ($\beta \ge 2$, où les algorithmes classiques atteignent également un regret polylogarithmique), il existe une plage critique ($\beta \in [1, 2)$) où les ordinateurs quantiques offrent un avantage substantiel. Ils identifient cette plage comme la zone principale où les accélérations quantiques dans le RL sont les plus impactantes sous le modèle proposé.