Résumé Technique : Le Seuil de l'Horizon dans l'Exploration Sans Récompense Coopérative Multi-Agents

Énoncé du Problème

Ce travail étudie l'exploration sans récompense coopérative multi-agents dans le cadre des Processus de Décision Markoviens (MDP) tabulaires à horizon fini. Dans ce contexte, $m$ agents interagissent en parallèle avec un environnement inconnu $M = (S, s_0, A, H, P, r)$ sur $\rho$ phases d'apprentissage. Crucialement, durant la phase d'exploration, les agents n'observent pas la fonction de récompense $r$ ; leur objectif est d'apprendre la dynamique de transition $P$ avec suffisamment de précision pour calculer une politique $\epsilon$-optimale pour n'importe quelle fonction de récompense révélée après l'exploration.

La question de recherche centrale aborde le compromis entre deux ressources :

1. Temps Parallèle : Le nombre de phases d'apprentissage $\rho$.
2. Complexité des Agents : Le nombre d'agents $m$ déployés par phase.

L'article vise à caractériser comment l'horizon $H$ régit l'efficacité de l'apprentissage, en déterminant spécifiquement si un nombre polynomial d'agents suffit lorsque le nombre de phases est contraint.

Méthodologie

Majoration : L'Algorithme H-MARFE

Les auteurs proposent H-MARFE (Exploration Sans Récompense Multi-Agents en H Phases), un algorithme conçu pour fonctionner exactement en $\rho = H$ phases en utilisant un nombre polynomial d'agents.

Mécanisme Central :
Contrairement aux approches séquentielles de minimisation du regret, H-MARFE utilise une stratégie d'exploration par couches qui ajuste la précision de l'estimation en fonction de l'accessibilité des états.

1. Estimation Phasée des Dynamiques : À la phase $i$ (où $i \in \{0, \dots, H-1\}$), l'algorithme se concentre exclusivement sur l'estimation de la dynamique de transition $P_i$ au pas de temps $i$.
2. Filtrage par Accessibilité : L'algorithme définit un ensemble d'états « actifs » $\hat{S}^\beta_i$ à chaque pas de temps, composé des états ayant une probabilité d'accessibilité d'au moins $\beta$ selon la dynamique estimée actuelle. Les états à faible accessibilité sont efficacement élagués en transitionnant de manière déterministe vers un état puits $s_{sink}$.
3. Construction de la Politique : Pour chaque paire état-action active $(s, a)$, l'algorithme calcule une politique $\hat{\pi}_{i,s,a}$ qui maximise la probabilité d'atteindre $s$ au pas de temps $i$ et d'exécuter l'action $a$, basée sur les dynamiques apprises lors des phases précédentes.
4. Exécution Parallèle : À chaque phase, $m$ agents se voient attribuer des paires état-action aléatoires issues de l'ensemble actif. Ils exécutent leurs politiques assignées pour collecter des trajectoires, qui sont agrégées pour former des estimations empiriques de transition pour la couche courante.

Innovation Technique :
L'analyse introduit un modèle de dynamique intermédiaire $P^1$ qui coïncide avec la vraie dynamique $P$ sur l'ensemble actif mais transitionne vers $s_{sink}$ sinon. La preuve repose sur la borne de l'erreur pondérée par la politique entre la dynamique estimée $\hat{P}$ et $P^1$. En contrôlant l'erreur additive dans les mesures d'occupation par rapport à l'accessibilité, l'algorithme garantit que l'erreur d'estimation de la valeur reste bornée pour toute fonction de récompense, évitant ainsi l'accumulation exponentielle d'erreur typique des parallélisations naïves.

Construction de la Majoration Inférieure

Pour établir la nécessité d'un nombre de phases à l'échelle de l'horizon, les auteurs construisent un MDP « Dynamique-Clé ».

• Structure : Le MDP possède un espace d'états de taille 2 ($s^\star$ et $s_{sink}$). Il existe une séquence « clé » cachée d'actions $a^\star_0, \dots, a^\star_{H-1}$. Prendre l'action correcte $a^\star_h$ à l'état $s^\star$ maintient l'agent dans $s^\star$ ; toute autre action transitionne vers l'état puits absorbant $s_{sink}$.
• Récompense : Une fonction de récompense spécifique $r_{key}$ attribue une récompense de 1 uniquement si l'agent atteint le dernier pas de temps dans l'état $s^\star$ après avoir exécuté la dernière action correcte.
• Implication : Pour apprendre la dynamique (et donc la politique optimale), un algorithme doit découvrir l'ensemble de la séquence clé. Dans une seule phase, $m$ agents peuvent révéler au maximum $\log_A(m)$ bits de la clé. Si le nombre de phases $\rho$ est significativement inférieur à $H$, la probabilité de découvrir la clé complète chute de manière exponentielle à moins que le nombre d'agents $m$ ne croisse exponentiellement avec $H/\rho$.

Résultats Clés

1. Majoration (Théorème 3.1)

L'algorithme H-MARFE atteint une politique $\epsilon$-optimale pour toute fonction de récompense avec une forte probabilité en utilisant :

• Phases : $\rho = H$.
• Agents : $m = \tilde{O}\left(\frac{S^6 H^6 A}{\epsilon^2}\right)$.

Cela démontre qu'un apprentissage efficace (polynomial en $S, A, H, \epsilon^{-1}$) est réalisable lorsque le nombre de phases d'apprentissage évolue linéairement avec l'horizon.

2. Majoration Inférieure (Théorème 4.1)

Pour tout algorithme multi-agents coopératif restreint à $\rho < H$ phases d'apprentissage, atteindre une précision constante (par exemple, $\epsilon = 0.1$) nécessite :

• Agents : $m = \Omega\left(\frac{A^{(H-1)/\rho}}{\rho}\right)$.

Cette majoration inférieure prouve que réduire le nombre de phases en dessous de l'horizon nécessite une augmentation exponentielle du nombre d'agents.

3. Le Seuil de l'Horizon

Les résultats combinés identifient un changement de régime net régi par l'horizon $H$ :

• Régime Polynomial : Lorsque $\rho \approx H$, la complexité des agents est polynomiale.
• Régime Exponentiel : Lorsque $\rho \ll H$, la complexité des agents devient exponentielle en $H/\rho$.

Signification et Revendications

L'article revendique l'établissement d'une limite fondamentale sur l'efficacité parallèle de l'exploration sans récompense dans les MDP tabulaires. La contribution principale est l'identification de l'horizon $H$ comme un seuil critique pour le temps parallèle.

• Nécessité de Phases à l'Échelle de l'Horizon : Le travail démontre que pour éviter une complexité exponentielle des agents, on ne peut pas simplement compresser l'exploration en un nombre constant ou sous-linéaire de phases. Le nombre de phases doit évoluer avec l'horizon.
• Efficacité Algorithmique : H-MARFE fournit une méthode computationnellement efficace pour atteindre ce compromis optimal, contrastant avec la littérature antérieure sur l'exploration sans récompense qui est intrinsèquement séquentielle ou nécessite des coûts de commutation évoluant linéairement avec les épisodes.
• Écart Théorique : Les auteurs notent que, bien que leur majoration atteigne une complexité polynomiale, la dépendance en $S$ et $H$ ($S^6 H^6$) est plus élevée que les bornes état-de-l'art pour un seul agent ($S^2 H^3$). Ils déclarent explicitement qu'il reste une question ouverte de savoir si cet écart est un coût inhérent à la parallélisation ou un artefact de leur analyse.

L'article conclut que l'exploration sans récompense coopérative multi-agents n'est réalisable avec des ressources polynomiales que si le temps parallèle (phases) est autorisé à évoluer avec l'horizon du problème, distinguant fondamentalement ce contexte des scénarios où le parallélisme peut réduire arbitrairement la complexité temporelle sans coûts exponentiels en ressources.