Résumé Technique : Une Théorie des Systèmes à Commutation pour le Q-Learning avec Approximation Linéaire de Fonctions

1. Énoncé du Problème

Le Q-learning est un algorithme fondamental de l'apprentissage par renforcement dans les processus de décision de Markov (MDP) à rabais. Bien que le Q-learning tabulaire soit bien compris, il devient calculatoirement prohibitif pour les espaces état-action de grande dimension. Le remède standard est l'Approximation Linéaire de Fonctions (LFA), où la fonction Q est représentée comme une combinaison linéaire de caractéristiques ($Q_\theta = \Phi\theta$).

Malgré des études approfondies, la convergence et la stabilité du Q-learning Linéaire (Q-learning avec LFA) restent complexes. Les analyses existantes s'appuient sur l'approximation stochastique, les méthodes d'équations différentielles ordinaires (ODE), ou des arguments de contraction de Bellman. Un fossé critique existe dans la compréhension du comportement de l'erreur en temps fini et des conditions de stabilité précises, particulièrement parce que la récursion déterministe du Q-learning linéaire est non linéaire en raison de l'opérateur $\max$ dans la mise à jour de Bellman. De plus, il existe une distinction connue entre la convergence de l'équation de Bellman projetée (souvent résolue via l'Itération de Valeur Q Projetée) et la mise à jour réelle du Q-learning linéaire ; la première ne garantit pas la convergence de la seconde.

Cet article traite de ces questions en développant un nouveau cadre basé sur la théorie des Systèmes Linéaires à Commutation (SLS). Le problème central est de caractériser la stabilité de la dynamique d'erreur du Q-learning linéaire, qui bascule entre différents modes linéaires selon les estimations de paramètres actuelles et la politique gourmande (greedy) qui en découle.

2. Méthodologie

Les auteurs proposent un cadre qui modélise la dynamique d'erreur du Q-learning linéaire comme un Système Linéaire à Commutation (SLS).

2.1 Représentation par Système à Commutation

L'idée clé est que la différence non linéaire entre deux estimations de valeurs Q, $V_\theta - V_{\bar{\theta}}$, peut être exprimée comme un opérateur linéaire indexé par une politique stochastique. Spécifiquement, pour tout $\theta, \bar{\theta}$, il existe une politique stochastique $\mu_{\theta, \bar{\theta}}$ telle que :
$$V_\theta - V_{\bar{\theta}} = \Pi_{\mu_{\theta, \bar{\theta}}} \Phi (\theta - \bar{\theta})$$
où $\Pi_\mu$ est la matrice de transition état-action induite par la politique $\mu$.

Par conséquent, la carte de mise à jour déterministe du Q-learning linéaire $T_\alpha(\theta) = \theta + \alpha g(\theta)$ (où $g$ est le résidu de Bellman projeté) satisfait :
$$T_\alpha(\theta) - T_\alpha(\bar{\theta}) = A_{\mu_{\theta, \bar{\theta}}} (\theta - \bar{\theta})$$
où $A_\mu = I - \alpha \Phi^\top D \Phi + \alpha \gamma \Phi^\top D P \Pi_\mu \Phi$.

Cela transforme la récursion non linéaire en une récursion d'erreur linéaire à commutation :
$$x_{k+1} = A_{\mu_k} x_k$$
où $x_k = \theta_k - \theta^*$ est l'erreur par rapport à un point fixe de Bellman projeté, et le signal de commutation $\mu_k$ est déterminé par la trajectoire.

2.2 Rayon Spectral Conjoint (JSR) comme Certificat de Stabilité

La stabilité de ce système à commutation est analysée en utilisant le Rayon Spectral Conjoint (JSR) de la famille de matrices associée.

• Soit $\mathcal{A}_\alpha$ la famille finie de matrices correspondant à toutes les politiques déterministes.
• Le JSR, noté $\rho(\mathcal{A}_\alpha)$, est défini comme le taux de croissance exponentielle exact du pire cas des produits de matrices issues de cette famille.
• Les auteurs prouvent que le JSR de l'enveloppe convexe des matrices de politiques stochastiques est égal au JSR de la famille déterministe finie ($\rho(\text{co}(\mathcal{A}_\alpha)) = \rho(\mathcal{A}_\alpha)$).

La condition $\rho(\mathcal{A}_\alpha) < 1$ sert de certificat de stabilité robuste suffisant. Contra à des bornes de norme sur une seule étape, le JSR capture le comportement du pire cas sur des séquences de commutation arbitraires, fournissant une caractérisation plus étroite et plus intrinsèque de la stabilité du système.

2.3 Construction de Lyapunov

Lorsque $\rho(\mathcal{A}_\alpha) < 1$, l'article construit une fonction de Lyapunov quadratique par morceaux (une norme $p_\epsilon$) directement à partir des produits des matrices de commutation. Cette fonction certifie que la carte $T_\alpha$ est une contraction globale dans la norme $p_\epsilon$, assurant l'existence d'un point fixe unique et la convergence exponentielle de la récursion déterministe.

2.4 Extensions Stochastiques et Régularisées

• Cas Stochastique : Le cadre est étendu au modèle d'échantillonnage i.i.d. La récursion stochastique est décomposée en la dynamique à commutation déterministe plus un terme de bruit de différence de martingales. Des bornes d'erreur en temps fini sont dérivées, montrant que l'erreur converge vers un voisinage du point fixe, la taille de ce voisinage dépendant du pas et des caractéristiques du bruit.
• Cas Régularisé : L'analyse est appliquée au Q-learning avec régularisation $\ell_2$. La régularisation décale les matrices de commutation par $-\alpha \eta I$. La stabilité est déterminée par le JSR de cette famille décalée, $\rho(\mathcal{A}_{\alpha, \eta})$. L'article dérive des bornes montrant comment la régularisation interagit avec le pas et les données intrinsèques du problème.

3. Contributions Clés et Résultats

3.1 Analyse de l'Erreur en Temps Fini

L'article dérive des bornes d'erreur explicites en temps fini pour le Q-learning linéaire. Le taux de convergence est lié au JSR de la famille de commutation. Plus précisément, si $\rho(\mathcal{A}_\alpha) < 1$, l'erreur décroît exponentiellement à un taux déterminé par $\rho(\mathcal{A}_\alpha) + \epsilon$. Les bornes incluent des termes pour l'erreur initiale, le pas et le plancher de bruit.

3.2 Distinction Entre les Itérations

L'article démontre rigoureusement que la convergence de l'Itération de Valeur Q Projetée (PQVI) n'implique pas la convergence du Q-learning Linéaire Déterministe, et vice versa.

• Exemple 1 & 2 : Les auteurs fournissent des contre-exemples où la PQVI diverge alors que le Q-learning linéaire converge (et vice versa). Cela souligne que les deux algorithmes, bien qu'ils partagent le même point fixe, ont des comportements dynamiques fondamentalement différents.
• Exemple 4 : Un cas est présenté où le JSR de la famille de commutation est supérieur à 1 (impliquant une instabilité sous commutation arbitraire), pourtant la récursion non linéaire réelle générée par Bellman converge globalement. Cela illustre que la condition du JSR est une condition suffisante conservatrice pour la trajectoire réelle, car la trajectoire réelle n'explore pas toutes les séquences de commutation possibles autorisées par la définition du JSR.

3.3 Analyse de la Régularisation

L'article propose une vue unifiée du Q-learning régularisé. Il montre que la régularisation décale les modes de commutation, menant à une nouvelle condition de JSR.

• Proposition 4 : Établit une identité exacte reliant le JSR régularisé au JSR non régularisé rescalé : $\rho(\mathcal{A}_{\alpha, \eta}) = |1 - \alpha \eta| \rho(\mathcal{B}_{\alpha/(1-\alpha \eta)})$.
• Insight : Cela révèle qu'augmenter le paramètre de régularisation $\eta$ n'améliore pas de manière monotone la stabilité dans un cadre à pas fixe. Bien qu'il augmente l'« accrétivité » (marge de stabilité), il modifie également l'échelle effective du pas, ce qui peut durcir les contraintes de stabilité.

3.4 Certificats de Lyapunov

L'article construit une fonction de Lyapunov quadratique commune par morceaux (une norme) qui certifie la contraction pour la carte non linéaire. Ce certificat est moins conservateur que les bornes de norme standard sur une seule étape car il tient compte de la structure de produit des dynamiques de commutation.

4. Signification et Revendications

L'article prétend offrir un cadre unifié pour analyser le Q-learning linéaire à travers le prisme des systèmes à commutation. Sa principale importance réside dans :

1. Caractérisation Exacte du Pire Cas : En utilisant le JSR, l'analyse capture le taux de croissance exponentiel exact du pire cas du système, allant au-delà des bornes conservatrices sur une seule étape.
2. Vue Unifiée de la Régularisation : Il connecte le Q-learning régularisé à la même théorie des systèmes à commutation, montrant comment la régularisation modifie la famille de commutation et fournit des conditions explicites pour la stabilité.
3. Clarification des Mécanismes de Convergence : Il sépare explicitement les dynamiques du Q-learning linéaire des itérations de Bellman projetées, expliquant pourquoi ils peuvent présenter des comportements de convergence différents malgré le partage de points fixes.
4. Robustesse : La condition basée sur le JSR est un certificat robuste pour la commutation réelle de la politique stochastique, car elle garantit la stabilité même sous une commutation arbitraire, qui est un surensemble du comportement de la trajectoire réelle.

Les auteurs notent que leur analyse se concentre sur les observations i.i.d. pour plus de clarté, bien que la décomposition de commutation puisse être étendue au bruit markovien. Le travail ne propose pas de nouveaux algorithmes mais fournit une compréhension théorique plus profonde des dynamiques de Q-learning linéaire existantes et de leurs propriétés de stabilité.