Résumé Technique : Q-Learning sous Critère de Coût Moyen pour les MDP Continus

1. Formulation du Problème

Cet article traite du défi consistant à résoudre des processus de décision de Markov (MDP) avec des espaces d'états et d'actions continus sous le critère du coût moyen à l'horizon infini. Le modèle est défini par un tuple $(X, U, \mathcal{T}, c)$, où $X$ et $U$ sont des espaces de Borel standards (espaces métriques complets et séparables), $\mathcal{T}$ est le noyau de transition, et $c$ est la fonction de coût. L'objectif est de trouver une politique $\pi$ qui minimise le coût moyen à long terme :
$$J^*(x) := \inf_{\pi} \limsup_{T \to \infty} \frac{1}{T} \mathbb{E}^\pi_x \left[ \sum_{t=0}^{T-1} c(x_t, u_t) \right]$$

Les auteurs soulignent que si les problèmes à horizon fini et à coût actualisé pour les espaces continus sont bien étudiés grâce aux propriétés de contraction des opérateurs de Bellman, les problèmes de coût moyen présentent des difficultés uniques. Plus précisément, l'absence de facteur d'actualisation supprime la contraction immédiate, nécessissant des hypothèses alternatives de stabilité et d'ergodicité. De plus, la littérature existante sur l'apprentissage par renforcement (RL) à coût moyen se concentre largement sur les espaces finis ou impose des hypothèses structurelles restrictives (par exemple, la dynamique linéaire ou les politiques Lipschitziennes) qui limitent l'applicabilité aux espaces continus généraux.

2. Méthodologie

Le papier emploie une approche à deux volets : l'approximation par quantification et des algorithmes d'apprentissage par renforcement conçus pour ces approximations.

2.1 Discrétisation et Approximation

La méthodologie centrale consiste à construire un MDP approximatif à états et actions finis en quantifiant les espaces continus.

• Quantification de l'état : L'espace d'état $X$ est partitionné en compartiments disjoints $\{B_i\}_{i=1}^M$ avec des états représentatifs $y_i$. Une application $q: X \to Y$ (où $Y$ est l'ensemble fini des représentants) est définie.
• Quantification de l'action : L'espace d'action $U$ est approximé par un ensemble fini $\Lambda$.
• Construction du modèle approximatif : Le modèle approximatif $(\hat{X}, \hat{U}, \hat{\mathcal{T}}, \hat{c})$ est défini en utilisant une mesure de poids $\mu$ (souvent la mesure invariante du processus d'état). Les noyaux de coût et de transition approximatifs sont des moyennes des fonctions originales sur les compartiments de quantification :
  $$\hat{c}(y_i, u) = \int_{B_i} c(z, u) \mu_{y_i}(dz), \quad \hat{\mathcal{T}}(A|y_i, u) = \int_{B_i} \mathcal{T}(A|z, u) \mu_{y_i}(dz)$$
• Conditions de Continuité Relâchées : Un changement méthodologique significatif est le relâchement de la condition de continuité de la Variation Totale (TV), standard dans la littérature d'approximation antérieure (ex: Saldi et al., 2018). Les auteurs établissent des résultats d'approximation sous :
  1. Continuité Faible (Feller) : Suffisante pour la convergence asymptotique des erreurs lorsque les tailles de grille tendent vers zéro.
  2. Continuité de Wasserstein : Suffisante pour établir des taux de convergence explicites (bornes d'erreur) lorsque les tailles de grille tendent vers zéro.

2.2 Algorithmes d'Apprentissage par Renforcement

Le papier propose des algorithmes de Q-Learning Quantifié pour apprendre la politique optimale du modèle approximatif directement à partir des données.

• Algorithme Synchrone (Algorithme 1) : Met à jour les valeurs Q pour tous les couples état-action dans la grille finie simultanément. Il repose sur l'échantillonnage d'états de chaque compartiment selon une mesure prédéterminée.
• Algorithme Asynchrone (Algorithme 2) : Met à jour les valeurs Q basées sur une trajectoire unique du processus continu original. Cela est plus pratique mais introduit un terme de bruit non markovien car le processus quantifié $q(X_t)$ n'est pas une chaîne de Markov (c'est un MDP partiellement observable du point de vue de l'état quantifié).
• Mécanisme de Convergence : Pour gérer le critère de coût moyen et l'absence de bornage des itérés Q (contra_irement aux cas actualisés), les auteurs utilisent :
  • Des semi-normes de Span pour les mises à jour synchrones.
  • Des hypothèses d'ergodicité : La politique d'exploration doit induire une mesure invariante unique avec un support complet sur les compartiments quantifiés.
  • Des mises à jour décalées (Shifted Updates) : L'algorithme asynchrone soustrait une valeur de référence (basée sur un compartiment spécifique) pour stabiliser l'itération, traitant le processus quantifié comme un POMDP.

3. Contributions Clés

Le papier apporte trois contributions majeures, faisant progresser l'état de l'art du contrôle à coût moyen dans les espaces continus :

1. Théorie de l'Approximation avec des Conditions plus Faibles :

   • Les auteurs fournissent des bornes d'erreur pour les approximations finies sous continuité faible et continuité de Wasserstein, relâchant la stricte continuité de Variation Totale requise par les travaux précédents (ex: Saldi et al., 2018).
   • Ils établissent que sous la continuité de Wasserstein (avec une constante de contraction $K_T < 1$), l'erreur du coût moyen optimal décroît à un taux proportionnel à l'erreur de quantification (spécifiquement $L_X^\delta$).
   • Sous la seule continuité faible, ils prouvent la convergence asymptotique du coût de la politique approximative vers le coût optimal lorsque la discrétisation devient plus fine.

2. Convergence du Q-Learning Quantifié :

   • Le papier établit la convergence presque sûre des algorithmes de Q-learning synchrone et asynchrone pour les espaces continus.
   • Crucialement, il prouve que ces algorithmes convergent vers les valeurs Q optimales du modèle fini construit, et non seulement vers le modèle continu original. Cette distinction est vitale car le processus quantifié n'est pas strictement markovien.
   • L'analyse généralise les résultats précédents (ex: Kara et Yüksel, 2023) des coûts actualisés vers le critère de coût moyen, beaucoup plus complexe, nécessitant une nouvelle analyse technique pour gérer les itérés Q non bornés.

3. Garanties de Quasi-Optimalité :

   • En combinant les bornes d'erreur d'approximation avec la convergence des algorithmes d'apprentissage, le papier démontre que les politiques apprises via le Q-learning quantifié sont quasi-optimales pour le MDP continu original.
   • La perte de performance est explicitement bornée en termes de résolution de la quantification et des constantes de Lipschitz des noyaux de coût et de transition.

4. Résultats Clés et Théorèmes

• Théorèmes 1 & 2 (Bornes d'Approximation) : Établissent des bornes supérieures sur la différence entre le coût moyen optimal du modèle original ($\rho$) et le modèle approximatif ($\hat{\rho}$).
  • Sous la continuité de Wasserstein : $|\rho - \hat{\rho}| \leq C \cdot (L_X)^\delta$, où $L_X$ est l'erreur de quantification.
  • Sous la continuité faible : $\lim_{n \to \infty} \rho(\pi_n) = \rho$.
• Théorèmes 5 & 6 (Convergence de l'Algorithme) : Prouvent que les itérations de Q-learning synchrone et asynchrone convergent vers les valeurs Q optimales du modèle fini approximatif. La convergence asynchrone repose sur l'ergodicité du processus d'état sous la politique d'exploration.
• Corollaire 1 : Combine les résultats d'approximation et d'apprentissage pour montrer que la politique apprise $\hat{\pi}$ satisfait $\rho(\hat{\pi}) - \rho \leq \epsilon$, où $\epsilon$ tend vers zéro lorsque la taille de la grille de discrétisation approche zéro.

5. Signification et Revendications

Les auteurs positionnent ce travail comme une solution aux problèmes ouverts de la littérature concernant l'apprentissage par renforcement pour les MDP à coût moyen avec des espaces continus.

• Relâchement des Hypothèses : Le papier revendique une avancée théorique significative en s'éloignant de la continuité de Variation Totale, souvent trop restrictive pour les modèles pratiques, au profit de la continuité Faible et de Wasserstein. Cela élargit la classe de systèmes (ex: ceux avec du bruit additif ou des dynamiques spécifiques) pour lesquels des garanties théoriques peuvent être fournies.
• Pont entre Théorie et Pratique : En prouvant que le Q-learning converge vers la solution d'une approximation finie bien définie, le papier fournit une justification rigoureuse à l'utilisation de la discrétisation pour le RL dans les contextes de coût moyen continus. Il clarifie que la "quasi-optimalité" est une conséquence directe de la qualité de l'approximation, et non un artefact de l'algorithme d'apprentissage.
• Gestion de la Quantification Non-Markovienne : Le papier traite explicitement la difficulté technique selon laquelle le processus d'état quantifié est un POMDP, et non un MDP, et fournit une preuve de convergence pour l'apprentissage asynchrone dans ce cadre sous le critère de coût moyen, un vide précédemment noté dans la littérature (ex: Wan et al., 2021).

Le papier conclut par une étude de cas numérique sur un problème de contrôle continu, démontrant la convergence des fonctions de valeur et la réduction du regret à mesure que le taux de quantification augmente, validant ainsi les bornes théoriques.