Model-Based Reinforcement Learning with Double Oracle Efficiency in Policy Optimization and Offline Estimation

1. Énoncé du Problème

L'apprentissage par renforcement (RL) dans des environnements à grande échelle ou continus fait face à des goulots d'étranglement computationnels sévères. Les algorithmes traditionnels de minimisation du regret basés sur un modèle nécessitent des appels fréquents à deux types d'"oracles" :

1. Oracle d'Estimation Statistique : Utilisé pour estimer le modèle de l'environnement (dynamiques de transition et récompenses) à partir des données.
2. Oracle d'Optimisation de Politique (Planification) : Utilisé pour calculer la politique optimale étant donné le modèle estimé.

Les approches existantes souffrent de deux limitations principales :

• Fréquence Élevée des Appels aux Oracles : La plupart des algorithmes nécessitent $O(T)$ appels à ces oracles, où $T$ est l'horizon temporel, ce qui les rend computationnellement prohibitifs pour de grands $T$.
• Dépendance à la Taille de l'Espace d'États/Actions : La complexité de la planification dépend souvent de la cardinalité de l'espace d'états ($S$) et de l'espace d'actions ($A$). Cela rend les méthodes existantes intraitables pour des environnements avec des espaces d'états/actions grands, infinis ou continus (par exemple, des MDP linéaires avec des états infinis).

Bien que des travaux récents (par exemple, Qian et al., 2024) aient atteint une "efficacité oracle hors ligne" (peu d'appels à l'oracle d'estimation) pour les MDP tabulaires, leur complexité d'oracle de planification dépendait toujours de $S$ et $A$ (spécifiquement $O(HSA \log \log T)$). L'article aborde la question ouverte : Pouvons-nous concevoir un algorithme efficace à la fois pour les oracles d'estimation et de planification, avec une complexité indépendante de $S$ et $A$, et applicable à des espaces d'états/actions infinis ?

2. Méthodologie

Les auteurs proposent DOERL (Apprentissage par Renforcement Doublement Efficace en Oracle), un cadre algorithmique novateur basé sur la régularisation par barrière logarithmique et log-déterminant. L'innovation centrale réside dans la manière dont l'algorithme gère le compromis entre exploration et exploitation tout en minimisant les appels aux oracles.

Composants Techniques Clés :

1. Apprentissage par Époques avec Mises à Jour Tronquées :

   • Le processus d'interaction est divisé en $N$ époques. Au sein de chaque époque, l'agent exécute une politique fixe pendant un segment de temps.
   • Crucialement, l'oracle d'estimation hors ligne n'est appelé qu'à la fin de chaque époque (ou segment), agrégeant les données pour mettre à jour le modèle. Cela réduit le nombre d'appels d'estimation à $O(N)$.
   • L'oracle de planification est également invoqué uniquement au début des segments, réduisant considérablement la fréquence de planification.

2. Mesures d'Occupation de Confiance :

   • Pour éviter d'explorer des transitions d'état-action rares ou peu fiables, l'algorithme définit un "ensemble de transitions de confiance" $\mathcal{T}_m^h$.
   • Les transitions ne sont considérées comme "de confiance" que si la mesure d'occupation estimée multipliée par la probabilité de transition dépasse un seuil ($1/\zeta_m$).
   • Ce concept, adapté de Qian et al. (2024), est modifié pour être calculable sans itérer sur tout l'espace des politiques, ce qui est crucial pour l'efficacité.

3. Régularisation pour l'Exploration :

   • Pour les MDP Tabulaires : L'algorithme utilise une Régularisation par Barrière Logarithmique. L'objectif d'optimisation de la politique inclut un terme $\sum \log(\text{mesure d'occupation de confiance} + \beta)$. Cela encourage l'agent à visiter des paires état-action qui sont "de confiance" mais ont une faible probabilité, assurant une exploration suffisante sans avoir à énumérer tous les états.
   • Pour les MDP Linéaires (Espaces Infinites) : L'algorithme introduit une Régularisation par Log-Déterminant. Au lieu de sommer sur des états discrets, il maximise le log-déterminant de la matrice de covariance des caractéristiques pondérée par la mesure d'occupation de confiance : $\log \det(\mathbf{K} + \beta \mathbf{I})$. Cela favorise l'exploration de l'espace des caractéristiques, assurant que l'agent collecte des données diversifiées pour estimer les coefficients linéaires avec précision.

4. Stratégie d'Agrégation :

   • L'algorithme agrège les estimations couche par couche (kernels de transition et récompenses) provenant de l'oracle hors ligne en un modèle global unique pour l'époque suivante, plutôt que de mettre à jour le modèle à chaque étape individuelle.

3. Contributions Clés

1. Efficacité Double Oracle :

   • L'article présente le premier algorithme qui atteint à la fois l'efficacité de l'oracle d'estimation statistique et l'efficacité de l'oracle d'optimisation de politique.
   • Complexité des Appels aux Oracles : L'algorithme nécessite uniquement $O(H \log \log T)$ appels aux deux oracles lorsque $T$ est connu (et $O(H \log T)$ lorsqu'il est inconnu).
   • Indépendance des Dimensions : Crucialement, cette complexité est strictement indépendante de la taille de l'espace d'états ($S$) et de la taille de l'espace d'actions ($A$).

2. Extension aux Espaces Infinites :

   • Le cadre est généralisé aux MDP Linéaires avec des espaces d'états infinis et des espaces d'actions arbitraires.
   • C'est le premier algorithme efficace en oracle hors ligne à atteindre un regret sous-linéaire dans ce contexte, surmontant la "malédiction de la dimensionnalité" qui affecte les méthodes tabulaires.

3. Bornes de Regret Optimales :

   • MDP Tabulaires : Atteint la borne de regret optimale $O(\sqrt{T})$.
   • MDP Linéaires : Atteint une borne de regret sous-linéaire de $O(T^{4/5})$ (avec des facteurs logarithmiques), ce qui est significatif pour les contextes de dimension infinie sous les contraintes d'oracles données.

4. Résultats

Des garanties théoriques sont établies pour les contextes finis (tabulaires) et infinis (linéaires) :

• MDP Tabulaires :

  • Regret : $O(\sqrt{T})$ (optimal).
  • Appels aux Oracles : $O(H \log \log T)$ pour l'estimation et la planification.
  • Comparaison : Améliore considérablement Qian et al. (2024), qui nécessitait $O(HSA \log \log T)$ appels de planification.

• MDP Linéaires (États/Actions Infinites) :

  • Regret : $O(T^{4/5} \cdot \text{polylog}(T))$.
  • Appels aux Oracles : $O(H \log \log T)$ pour les deux oracles.
  • Signification : Avant ce travail, aucun algorithme n'existait capable de résoudre des MDP à états infinis avec des appels aux oracles aussi peu fréquents tout en maintenant un regret sous-linéaire.

5. Signification et Impact

• Pont entre Théorie et Pratique : En découplant la complexité computationnelle de la taille des espaces d'états/actions, ce travail rend le RL basé sur un modèle théoriquement viable pour des applications complexes et réelles comme la robotique et les systèmes autonomes, où $S$ et $A$ sont effectivement infinis.
• Efficacité dans les Systèmes à Grande Échelle : La réduction des appels aux oracles de $O(T)$ ou $O(SA)$à$O(\log \log T)$ représente une réduction massive de la surcharge computationnelle, permettant l'utilisation d'estimateurs hors ligne coûteux (comme les réseaux de neurones profonds) dans les boucles de RL où ils étaient auparavant trop coûteux.
• Nouveau Paradigme pour l'Exploration : L'intégration de la régularisation par barrière logarithmique et log-déterminant avec des mesures "de confiance" fournit un mécanisme théorique robuste pour l'exploration qui s'adapte gracieusement à la dimensionalité, offrant un modèle pour les algorithmes futurs en contrôle de haute dimension.

En résumé, cet article fait progresser fondamentalement l'état de l'art en Apprentissage par Renforcement en prouvant qu'un regret optimal peut être atteint avec une surcharge computationnelle minimale (indépendante de la taille de l'environnement) grâce à une combinaison novatrice d'apprentissage par époques, de mesures de confiance et de régularisation basée sur le déterminant.