A Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning

Résumé technique : Une théorie à itérations finies pour l'apprentissage par différence temporelle distributionnelle catégorielle asynchrone

Énoncé du problème
Les récentes avancées en apprentissage par renforcement (RL) distributionnel ont établi de solides garanties asymptotiques pour les méthodes d'évaluation de politiques catégorielles, à savoir l'apprentissage par différence temporelle catégorielle scalaire (CTD) dans la métrique de Cramér et l'apprentissage par différence temporelle catégorielle signée multivariée (MTD) dans la métrique de déviation moyenne maximale (MMD). Cependant, les analyses non asymptotiques (à itérations finies) existantes se concentrent largement sur des mises à jour d'état complet synchrones, des modèles génératifs ou des substituts idéalisés. Dans les contextes pratiques de RL en ligne, l'apprentissage TD catégoriel standard fonctionne de manière asynchrone : il effectue des mises à jour d'un seul état à chaque itération, pilotées par une trajectoire markovienne. Cela crée un fossé théorique entre la théorie asymptotique établie et le comportement à itérations finies des récurrences exactes utilisées en pratique. Cet article comble ce fossé en fournissant des garanties à itérations finies pour le CTD et le MTD asynchrones, dans des régimes à horizon fixe avec et sans facteur d'actualisation.

Méthodologie
Les auteurs comblent l'écart entre les mises à jour asynchrones pratiques et la théorie de l'approximation stochastique (SA) à itérations finies grâce à un cadre unifié fondé sur des plongements isométriques état par état et une géométrie de supremum par blocs.

1. Plongements isométriques et contraction :

   • Pour le CTD, les auteurs utilisent la métrique de Cramér et un plongement isométrique de masse cumulative ($I_C$). Cela transforme l'opérateur de Bellman projeté en une contraction dans une norme de supremum par blocs ($\|\cdot\|_{2,\infty}$) avec un module de $\sqrt{\gamma}$ (avec actualisation) ou une contraction pondérée (à horizon fixe).
   • Pour le MTD, ils emploient la métrique MMD avec un noyau caractéristique et un plongement par matrice de Gram ($I_M$). Cela convertit de même l'application de Bellman projetée en une contraction dans la géométrie MMD de supremum par blocs, avec un module de $\gamma^{c/2}$ (avec actualisation) ou une contraction pondérée (à horizon fixe).

2. Formulation de l'approximation stochastique (SA) asynchrone :

   • La règle standard de mise à jour d'un seul état est reformulée comme une récurrence SA asynchrone : $U_{k+1} = U_k + \alpha_k P_{S_k}(\hat{T}(U_k; S_k, \xi_k) - U_k(S_k))$.
   • L'analyse repose sur des cadres abstraits à itérations finies pour les récurrences contractives sous échantillonnage i.i.d. et markovien (s'appuyant sur Chen et al., Robbins-Monro et Borkar).
   • Géométrie de la perturbation : Une distinction critique est établie entre les structures de bruit des deux méthodes. Le CTD opère dans un régime de bruit borné en raison du support borné des distributions catégorielles et de la géométrie de Cramér. En revanche, le MTD opère dans un régime de perturbation affine car la projection catégorielle signée est affine et non uniformément bornée, conduisant à des bornes de perturbation qui évoluent avec la norme de l'itéré courant.

3. Régimes analysés :

   • Évaluation de politique avec actualisation : Analysée sous échantillonnage i.i.d. (mémoire de rejeu/modèle génératif) et échantillonnage de trajectoire markovienne (RL en ligne standard). Le cas markovien intègre des bornes sur le temps de mélange géométrique.
   • Évaluation à horizon fixe sans actualisation : Analysée pour des tâches épisodiques avec un horizon fixe $H$. Puisqu'il n'y a pas de facteur d'actualisation $\gamma < 1$ pour assurer la contraction, les auteurs introduisent une métrique de bloc pondérée ($\lambda^h$) à travers la pile de l'horizon. Cela permet de retrouver une propriété de contraction où l'horizon $h$ se base sur $h-1$. L'analyse est effectuée aux limites des épisodes pour gérer la dérive dépendante de la phase au sein d'un épisode.

Contributions clés

1. Garanties à itérations finies pour le CTD et le MTD asynchrones : L'article établit des taux de convergence non asymptotiques explicites pour les récurrences asynchrones standards du CTD et du MTD. Il s'agit de la première théorie de ce type pour ces méthodes spécifiques sous des mises à jour d'un seul état pilotées par trajectoire.
2. Cadre unifié pour les régimes avec actualisation et à horizon fixe : Les auteurs fournissent un traitement théorique cohérent couvrant à la fois les problèmes avec actualisation (avec échantillonnage i.i.d. et markovien) et les problèmes à horizon fixe sans actualisation (sous échantillonnage épisodique i.i.d.).
3. Décomposition déterministe de l'erreur de représentation : L'article présente une décomposition qui sépare l'erreur totale en un terme algorithmique (contrôlé par les bornes à itérations finies) et un terme de biais de projection déterministe (dépendant de la famille de supports catégoriels). Cela permet d'analyser indépendamment l'analyse SA et le biais de discrétisation.
4. Constantes explicites et régimes de taille de pas : L'analyse fournit des constantes explicites pour trois régimes de taille de pas :
   • Taille de pas constante : Convergence géométrique vers un voisinage $O(\alpha)$.
   • Taille de pas décroissante linéairement : Décroissance résiduelle de $O(1/k)$ (erreur quadratique), impliquant une complexité en échantillons de $O(\epsilon^{-2})$ pour une erreur moyenne $\epsilon$.
   • Taille de pas décroissante polynomialement : Décroissance de $O(1/k^z)$, échangeant le taux de convergence contre des conditions d'admissibilité plus douces.

Résultats

• Régime avec actualisation : Pour le CTD et le MTD, sous échantillonnage i.i.d., l'erreur quadratique converge à un taux de $O(1/k)$ avec des tailles de pas décroissant linéairement. Sous échantillonnage markovien, le taux est $\tilde{O}(1/k)$, entraînant une surcharge logarithmique due au temps de mélange de la chaîne de Markov sous-jacente.
• Régime à horizon fixe : Pour les tâches épisodiques sans actualisation, l'erreur aux limites des épisodes converge à des taux analogues au cas avec actualisation. Plus précisément, une convergence de $O(1/m)$ pour l'erreur quadratique après $m$ épisodes (équivalent à $O(\epsilon^{-2})$ transitions).
• Régimes de bruit : Les résultats confirment que le CTD bénéficie d'un bruit uniformément borné, tandis que le MTD nécessite de gérer des bornes de bruit affines, ce qui introduit des constantes supplémentaires liées à la norme de l'itéré dans les garanties de convergence.

Portée et affirmations
L'article prétend combler un fossé théorique significatif entre la compréhension asymptotique du RL distributionnel et les mises à jour asynchrones d'un seul état utilisées dans les implémentations pratiques. En démontrant que les récurrences catégorielles standards constituent des schémas SA asynchrones dotés de structures contractives dans des plongements appropriés, les auteurs permettent un contrôle rigoureux à itérations finies.

Les auteurs notent modestement la portée de leur travail :

• La théorie est limitée à l'évaluation de politiques tabulaire et à états finis et ne traite pas du contrôle ou de l'amélioration de la politique.
• Les garanties sont des bornes d'espérance plutôt que des bornes à haute probabilité.
• Les résultats s'appliquent aux récurrences asynchrones exactes utilisées en pratique, les distinguant des travaux antérieurs qui analysaient des substituts synchrones ou basés sur un modèle.

Ce travail établit que, une fois le CTD et le MTD formulés avec les plongements état par état appropriés, leurs règles de mise à jour possèdent les propriétés structurelles nécessaires (contraction, continuité lipschitzienne et perturbation contrôlée) pour être analysées à l'aide d'outils SA non asymptotiques modernes, fournissant ainsi la première théorie à itérations finies pour ces méthodes distributionnelles largement utilisées dans des contextes en ligne réalistes.