Résumé technique : Un taux robuste de $O(1/\sqrt{T})$ pour l'apprentissage TD non projeté avec approximation de fonction linéaire

Énoncé du problème

L'apprentissage par différence temporelle (TD) avec approximation de fonction linéaire est un algorithme fondamental pour l'évaluation de politiques en apprentissage par renforcement. Si la convergence asymptotique est bien comprise, établir des taux de convergence en temps fini sous des conditions réalistes — spécifiquement lorsque les données sont générées par une chaîne de Markov (bruit markovien) plutôt que par des échantillons indépendants — reste un défi.

Un écart théorique critique existe concernant le taux de convergence « robuste » de $O(1/\sqrt{T})$. Les travaux antérieurs établissant ce taux (par exemple, Bhandari et al., 2018) reposaient sur une étape de projection artificielle, où les itérés sont forcés sur un ensemble borné pour éviter la divergence. Cette projection est rarement utilisée en pratique et nécessite la connaissance d'une borne sur la solution optimale $\theta^*$, ce qui est souvent indisponible. Inversement, des taux de convergence « rapides » de $O(1/T)$ existent pour l'apprentissage TD non projeté, mais ils dépendent de l'inverse du carré de la courbure minimale ($\omega$) de la fonction de potentiel. Comme $\omega$ peut être arbitrairement petit (problèmes mal conditionnés), le taux rapide peut se dégrader considérablement dans les régimes non asymptotiques.

Le problème ouvert, posé par Bhandari et al. (2018), est de savoir si le TD(0) non projeté peut atteindre le taux de convergence robuste de $O(1/\sqrt{T})$ sans conditions de régularité supplémentaires ou projections artificielles.

Méthodologie

Les auteurs analysent l'algorithme standard TD(0) non projeté avec approximation de fonction linéaire sous échantillonnage markovien. Leur approche diverge fondamentalement des analyses antérieures qui reposent sur des propriétés de contraction ou des projections artificielles.

1. Sélection de la fonction de potentiel

Au lieu d'utiliser la distance $D$-norm standard $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$, les auteurs utilisent la fonction de potentiel proposée par Liu et Olshevsky (2021) :
$$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$$
Cette fonction de potentiel est avantageuse car :

• Elle reste bien comportementée même lorsque le facteur de remise $\gamma \to 1$.
• Le champ de mise à jour stationnaire $\bar{g}(\theta)$ satisfait l'égalité $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$, ce qui simplifie l'analyse par rapport aux inégalités utilisées dans d'autres travaux.

2. Propriété d'auto-limitation via l'induction

La contribution technique centrale est une nouvelle propriété d'auto-limitation (self-bounding property) des mises à jour TD. Les auteurs prouvent que, sans projeter les itérés, la séquence $\{\theta_t\}$ reste bornée en espérance autour de la solution optimale $\theta^*$, à condition que le pas soit choisi avec soin.

• Conception du pas (stepsize) : Le pas est défini par $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$, où $c$ est une constante satisfaisant $c > 15 + 18\sqrt{2}$.
• Argument inductif : La preuve procède par induction. En supposant que les itérés sont bornés jusqu'au temps $t-1$, les auteurs montrent que la mise à jour au temps $t$ reste bornée. Cela repose sur la décomposition de la mise à jour en une suite de différences de martingales (bruit) et un terme de biais.
• Gestion du bruit markovien : Pour traiter le biais introduit par les corrélations markoviennes (où $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$), les auteurs exploitent le mélange géométrique de la chaîne de Markov sous-jacente (Théorème 3.2). Ils bornent le biais en reliant la distribution de l'état actuel à la distribution stationnaire sur un retard $k'$, en utilisant le taux de décroissance $\alpha^k$.

3. Analyse du bornage

Les auteurs démontrent que les itérés satisfont :
$$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$$
où $\rho_c$ est une constante dépendant du paramètre de pas $c$. Ce bornage est obtenu sans projeter les itérés, fermant ainsi la boucle d'induction.

Résultats clés

Garanties théoriques

Théorème 4.2 : Pour l'itéré de moyenne pondérée $\bar{\theta}_T$ généré par le TD(0) non projeté avec le pas spécifié, l'espérance de la norme au carré des itérés est bornée par une constante indépendante du temps de mélange et de la courbure $\omega$.

Corollaire 4.3 : L'algorithme atteint un taux de convergence de :
$$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$$
Crucialement, les constantes cachées dans la notation $\tilde{O}$ dépendent de $\|\theta^*\|$ et des bornes des caractéristiques (features), mais ne dépendent pas de la courbure minimale $\omega$ ni du temps de mélange $\alpha$ (hormis une légère correction polylogarithmique dans la condition du pas).

Comparaison avec les travaux antérieurs

• Vs Taux robustes projetés : Contrairement à Bhandari et al. (2018), ce résultat élimine l'étape de projection et l'exigence de connaître a priori les bornes sur $\theta^*$. Le taux est comparable ($\tilde{O}(1/\sqrt{T})$) mais obtenu sans contraintes artificielles.
• Vs Taux rapides non projetés : Contrairement à Srikant et Ying (2019) et aux travaux ultérieurs atteignant $O(1/T)$, ce résultat ne dépend pas du paramètre de courbure inconnu $\omega$. Les auteurs montrent via un contre-exemple que $\omega$ peut être arbitrairement petit, rendant les taux rapides potentiellement arbitrairement lents en pratique, tandis que le taux robuste reste stable.

Signification et affirmations

L'article prétend résoudre un problème ouvert spécifique identifié par Bhandari et al. (2018) : fournir une analyse en temps fini du TD(0) non projeté avec approximation de fonction linéaire qui atteint un taux de convergence robuste.

• Suppression des hypothèses artificielles : Ce travail démontre que l'étape de projection, précédemment jugée nécessaire pour une analyse robuste, n'est pas requise. Le bornage des itérés émerge naturellement de la dynamique de l'algorithme lorsque le pas est correctement mis à l'échelle avec des facteurs logarithmiques.
• Aucune régularité supplémentaire : Le résultat tient sans supposer de conditions de régularité additionnelles sur la structure du problème au-delà des hypothèses standards (irréductibilité, aperiodicité, rang de colonne complet des caractéristiques).
• Pertinence pratique : Les auteurs soulignent que si les projections sont utilisées en théorie pour simplifier les preuves, elles ne sont pas utilisées en pratique. Cette analyse comble le fossé entre les garanties théoriques et la conception d'algorithmes pratiques.
• Seuil de stabilité : Le papier identifie un seuil pour la constante du pas (spécifiquement $c > 15 + 18\sqrt{2}$) comme une condition suffisante pour la stabilité. Les résultats expérimentaux sur des données synthétiques suggèrent que ce seuil capture un effet de stabilité en temps fini réel ; si $c$ est trop petit, les itérés peuvent diverger.

Les auteurs notent que le seuil sur $c$ est une condition suffisante conservatrice dérivée des constantes de preuve (inégalité triangulaire, Cauchy-Schwarz, tests d'intégrale) et n'est pas nécessairement une règle de réglage pratique serrée. De plus, l'exigence que $T$ soit suffisamment grand par rapport au temps de mélange $\alpha$ est reconnue comme une limitation partagée par la littérature plus large sur les bornes robustes, bien que les auteurs préfèrent une présentation exécutable des hypothèses plutôt qu'une formulation « anytime » qui nécessiterait la connaissance de paramètres de mélange inconnus.