Résumé Technique : Un Pas de Taille Unique Suffit pour le TD(0) Linéaire Non Projeté

Énoncé du Problème

L'article traite de l'analyse de la convergence en temps fini et à haute probabilité de l'apprentissage de la différence temporelle linéaire à biais nul (TD(0)) sous échantillonnage markovien. Dans ce cadre, les données sont générées le long d'une trajectoire unique d'une chaîne de Markov plutôt que comme des échantillons indépendants et identiquement distribués (i.i.d.).

Le défi central réside dans le fait que le TD(0) n'est pas une méthode de descente de gradient stochastique standard ; ses mises à jour sont biaisées, non symétriques, et le bruit est temporellement corrélé. De plus, l'amplitude de la mise à jour dépend de l'amplitude des itérés actuels. Les analyses non asymptotiques existantes reposent généralement sur l'une des deux approches restrictives suivantes :

1. Projections : Imposer la bornitude en projetant les itérés sur une boule connue. Cela simplifie les arguments de concentration mais modifie l'algorithme et nécessite la connaissance préalable d'un rayon approprié (souvent lié à la courbure du problème).
2. Stabilité Dépendante de la Courbure : Exploiter la nature contractive de la dynamique moyenne pour argumenter la stabilité sans projections. Cependant, cela produit généralement des conditions de pas de taille ou des bornes de stabilité qui dépendent d'un paramètre de courbure inconnu ($\omega$). Lorsque $\omega$ est petit, ces bornes deviennent arbitrairement lentes, et le pas de taille ne peut être choisi indépendamment de $\omega$.

Les auteurs visent à établir un programme de pas de taille unique qui est indépendant du paramètre de courbure $\omega$ et ne nécessite aucune projection, tout en garantissant simultanément :

• Robustesse : Un taux de convergence de $\tilde{O}(1/\sqrt{T})$ qui tient quel que soit $\omega$.
• Rapidité : Un taux de convergence de $\tilde{O}(1/(\omega T))$ qui exploite une courbure favorable lorsqu'elle existe.

Méthodologie

1. Argument d'Auto-Bornitude via les Équations de Poisson

La nouveauté technique centrale est un nouvel argument inductif d'« auto-bornitude » (self-bounding) qui contrôle la bornitude par chemin des itérés $\theta_t$ sans dépendre de la courbure $\omega$ ou de projections artificielles.

• La Boucle : Une analyse de concentration naïve est circulaire : borner l'erreur nécessite des mises à jour bornées, mais des mises à jour bornées nécessitent des itérés bornés.
• La Solution : Les auteurs décomposent le bruit markovien en utilisant l'équation de Poisson associée à la chaîne de Markov à mélange géométrique. Pour un terme de forçage centré $h$, ils résolvent $u - P_Z u = \tilde{h}$.
• Décomposition : Cela permet de décomposer l'accumulation du bruit markovien en un terme de martingale ($M_t$) et un terme de reste contrôlé ($R_t$).
• Induction : Ils établissent une hypothèse inductive où la bornitude des itérés jusqu'à $t-1$ implique la bornitude à $t$. En contrôlant le terme de martingale via l'inégalité de Pinelis et le terme de reste via les propriétés Lipschitz de la solution de Poisson, ils prouvent que les itérés restent uniformément bornés avec une haute probabilité, indépendamment de $\omega$.

2. Moyennage de Polyak–Ruppert (PR)

L'article analyse l'itéré moyenné de Polyak–Ruppert $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, où $S_T = \sum \eta_{t-1}$.

• Une fois la bornitude uniforme de $\theta_t$ établie, les auteurs peuvent contrôler la variation quadratique des termes de la martingale et les termes de biais dans l'analyse de convergence.
• Ils dérivent deux bornes supérieures distinctes pour l'erreur de la fonction de potentiel $f(\bar{\theta}_T) - f(\theta^*)$ :
  • Une borne robuste dérivée d'une analyse classique de descente de gradient stochastique moyennée, produisant un $\tilde{O}(1/\sqrt{T})$.
  • Une borne rapide dérivée de l'analyse de l'évolution de l'erreur $e_t = \theta_t - \theta^*$ et en exploitant la positivité de la partie symétrique de la matrice TD (courbure $\omega$), produisant un $\tilde{O}(1/(\omega T))$.

3. Programme de Pas de Taille

Le pas de taille proposé est :
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
où $c$ est une constante numérique, $\tau_{\text{mix}}$ est le temps de mélange, et $\phi_\infty$ borne les normes des caractéristiques. Crucialement, ce programme dépend du temps de mélange mais pas de la courbure $\omega$.

Résultats Clés

1. Bornitude à Haute Probabilité (Théorème 4.1)

Sous des hypothèses standards (MRP ergodique, caractéristiques de rang plein), les itérés du TD(0) non projetés sont uniformément bornés avec une haute probabilité ($1-\delta$) :
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
où $R_{\text{base}}$ dépend de l'erreur initiale, de la norme de la solution optimale et des constantes du problème, mais est indépendant de $\omega$. C'est le premier résultat montrant une telle bornitude pour le TD(0) non projeté sous échantillonnage markovien sans utiliser $\omega$ dans le pas de taille ou l'argument de stabilité.

2. Taux de Convergence Simultanés (Théorème 4.2)

En utilisant le même pas de taille et le moyennage PR, l'algorithme atteint un taux de convergence à haute probabilité pour l'erreur de la fonction de potentiel :
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
En substituant le programme de pas de taille, cela se traduit par :

• Taux Robuste : $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Taux Rapide : $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

La borne s'adapte automatiquement au minimum de ces deux taux sans connaissance préalable de $\omega$.

3. Variante Sans Mélange (Annexe E)

Les auteurs proposent également un pas de taille modifié $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ qui ne nécessite pas la connaissance de $\tau_{\text{mix}}$. Cependant, cela se fait au prix d'une dépendance doublement exponentielle de $\tau_{\text{mix}}$ dans les constantes de la borne de convergence, spécifiquement à travers la borne de préfixe initiale $B_{m^*}$.

Signification et Revendications

L'article affirme être le premier à établir que le TD(0) linéaire avec échantillonnage markovien peut atteindre à la fois des taux de convergence robustes et rapides à haute probabilité en utilisant un seul pas de taille qui est :

1. Indépendant du paramètre de courbure $\omega$.
2. Sans projection.

Les auteurs soulignent que les travaux précédents nécessitaient soit des projections (changeant l'algorithme), soit des pas de taille dépendant de la courbure (échouant lorsque $\omega$ est petit), soit ne fournissaient que des bornes d'espérance (par exemple, Lee et Orabona [2025]) plutôt que des garanties à haute probabilité.

La signification réside dans l'argument d'auto-bornitude via les équations de Poisson, qui brise la dépendance circulaire entre la bornitude des itérés et l'amplitude des mises à jour sans faire appel aux propriétés de contraction de la dynamique moyenne. Cela permet à l'algorithme de rester stable et de converger rapidement même lorsque la courbure est arbitrairement petite, un scénario où les analyses précédentes sans projection ou avec abandon de données échouaient typiquement.

L'article reste modeste concernant la dépendance au temps de mélange $\tau_{\text{mix}}$. Bien que le taux rapide présente une dépendance en $\tau_{\text{mix}}^2$ (pire que la dépendance linéaire en $\tau_{\text{mix}}$ de certains travaux précédents basés sur la projection ou l'abandon de données), les auteurs notent que la dépendance optimale de $\tau_{\text{mix}}$ en l'absence de projections et d'abandon de données reste une question ouverte. Ils reconnaissent également que leur terme d'erreur initial décroît à un taux de $1/T$ plutôt qu'exponentiel, une conséquence de l'évitement des arguments de contraction.