Learning Ordinal Response Policies in Rank-Based Stochastic Prize-Collecting Games

Résumé Technique : Apprentissage de Politiques de Réponse Ordinale dans des Jeux de Collecte de Prix Stochastiques Basés sur le Rang

1. Définition du Problème

Le document traite des limites du Problème d'Orientation d'Équipe (TOP - Team Orienteering Problem) dans les systèmes multi-agents. Bien que le TOP fournisse un cadre unifié pour le routage coopératif (ex. : livraison du dernier kilomètre, surveillance) où les agents maximisent une utilité collective sous des contraintes de budget de déplacement, il ne parvient pas à modéliser les scénarios impliquant des agents auto-intéressés rivalisant dans des environnements aux ressources rares. Dans ces contextes, les agents (ex. : flottes de livraison concurrentes ou chauffeurs de l'économie collaborative) privilégient leurs récompenses individuelles plutôt que le gain collectif, et leurs interactions sont régies par des transitions stochastiques et des contraintes énergétiques.

Pour combler cette lacune, les auteurs proposent le Jeu de Collecte de Prix Stochastique (SPCOG - Stochastic Prize-Collecting Orienteering Game). Dans un SPCOG :

• Les agents opèrent sur un graphe pondéré avec des distributions de prix stochastiques aux nœuds.
• Les agents disposent de budgets de déplacement individuels et visent à maximiser leurs propres récompenses cumulées.
• Résolution des Conflits : Lorsque plusieurs agents visitent le même nœud simultanément, une règle basée sur le rang s'applique : l'agent ayant le rang global le plus élevé (indice le plus bas) revendique l'intégralité du prix ; les autres reçoivent zéro.
• Objectif : Trouver des politiques convergentes pour des agents indépendants afin de maximiser les récompenses individuelles, tout en reconnaissant que la récompense totale de l'équipe peut être inférieure à l'optimum du TOP coopératif.

2. Méthodologie

Analyse Théorique des Équilibres
Les auteurs analysent d'abord l'existence d'un Équilibre de Nash Pur (PNE - Pure Nash Equilibrium) dans les SPCOGs :

• Graphes Complets : Ils prouvent que pour les graphes complets, un PNE unique existe sous une résolution de conflit basée sur le rang. Dans cet équilibre, le $i$-ème agent classé choisit le $i$-ème plus grand prix disponible. La récompense totale dans ce PNE coïncide avec la solution optimale d'un TOP coopératif équivalent.
• Graphes en Étoile : Un PNE unique similaire existe, où les agents se déplacent vers le $i$-ème plus grand prix lors d'étapes alternées.
• Graphes Arbitraires : Le document démontre, via un contre-exemple (un scénario spécifique à deux agents), qu'un PNE n'existe pas nécessairement pour des structures de graphes arbitraires lorsque les agents se déplacent simultanément, soulignant la complexité de la résolution de ces jeux par rapport aux formulations de Stackelberg (leader-suiveur).

Concept de Rang Ordinal (OR - Ordinal Rank)
Pour répondre au défi de l'observabilité partielle et de l'espace d'états exponentiel dans les graphes généraux, les auteurs introduisent le Rang Ordinal (OR) :

• Opposants Immédiats : Les agents sont regroupés en "jeux de stade localisés" basés sur un "graphe séparateur" où les arêtes connectent les agents ayant des ensembles atteignables qui se chevauchent.
• Définition : Le rang OR d'un agent est défini comme $1 +$ le nombre d'agents possédant un rang global plus élevé (indice plus bas) au sein de son voisinage immédiat (composante connexe).
• Signification : L'OR résume la compétition locale la plus influente. Les auteurs émettent l'hypothèse que le fait de conditionner les politiques sur l'OR, plutôt que sur l'état global ou le rang global, agit comme un biais inductif fort, permettant aux agents d'apprendre des réponses optimales face à leurs opposants immédiats sans nécessiter d'informations globales.

Apprentissage par Réponse Ordinale Fictive (FORL - Fictitious Ordinal Response Learning)
Les auteurs proposent le FORL, un algorithme d'apprentissage régulé par l'entropie conçu pour l'apprentissage par renforcement multi-agent indépendant (MARL) :

• Mises à jour Séquentielles : Les agents mettent à jour leurs politiques séquentiellement selon leur rang. Les agents de rang supérieur mettent à jour leurs politiques en premier, supposant que les agents de rang inférieur suivent des politiques aléatoires ou stationnaires.
• Bootstrapping : L'agent le mieux classé apprend en premier pour résoudre le problème stochastique sous-jacent à agent unique. Une fois que sa politique atteint un seuil de confiance (mesuré par l'entropie), ses paramètres sont partagés avec les autres.
• Jeu Fictif (Fictitious Play) : Les agents suivants mettent à jour leurs politiques en jouant contre les politiques "stationnaires" des agents de rang supérieur.
• Régulation de l'Entropie : L'algorithme utilise un seuil d'entropie décroissant ($H_{stop}$) pour assurer la convergence. Si un PNE existe, l'algorithme converge vers une stratégie pure (entropie $\to$ 0) ; sinon, il fournit des bornes de confiance sur la qualité de la politique de stratégie mixte.
• Architecture de Politique : Les politiques sont modélisées à l'aide d'une architecture basée sur les Transformers (TRXL-I) et sont conditionnées sur des observations locales augmentées par l'OR. Un masquage d'actions est utilisé pour imposer les contraintes du graphe.

3. Contributions Clés

1. Formulation SPCOG : Introduction d'une variante de théorie des jeux du TOP pour des agents auto-intéressés dans des environnements stochastiques avec contraintes énergétiques.
2. Garanties Théoriques : Preuve d'un PNE unique sur les graphes complets et en étoile qui s'aligne avec la solution optimale du TOP, et un contre-exemple montrant la non-existence de PNE sur des graphes arbitraires.
3. Rang Ordinal (OR) : Proposition de l'OR comme une représentation locale concise du statut compétitif d'un agent, servant de biais inductif fort pour l'apprentissage.
4. Algorithme FORL : Développement d'un algorithme inspiré du jeu fictif et régulé par l'entropie, qui produit des politiques convergentes dans des contextes d'apprentissage indépendant.
5. Validation Empirique : Démonstration que les politiques conditionnées par l'OR surpassent les politiques conditionnées par le rang global en termes de généralisabilité, de scalabilité et d'efficacité d'entraînement.

4. Résultats Expérimentaux

Des expériences ont été menées sur des réseaux routiers réels (Stockholm et Manhattan) avec des distributions de prix statiques et dynamiques.

• Performance vs TOP : Dans les graphes complets, les politiques conditionnées par l'OR ont atteint 95 % de la récompense optimale du TOP. Dans les graphes incomplets, l'équilibre le plus défavorable a atteint 87 % de la solution optimale.
• Généralisabilité : Les politiques entraînées avec FORL et le conditionnement par l'OR ont démontré de meilleures capacités de transfert "zero-shot" vers des distributions de prix déséquilibrées et dictées par la demande, comparées à l'apprentissage de politique indépendant (IPL) et aux méthodes de partage de paramètres conditionnées sur l'état global.
• Scalabilité : Lors du passage à des équipes allant jusqu'à 25 agents, les politiques conditionnées par l'OR (PS-OR) ont montré une croissance linéaire de la récompense totale avec une faible variance. En revanche, les politiques conditionnées par le rang global (PS-GR) ont présenté des gains sous-linéaires et une variance nettement plus élevée.
• Efficacité : La méthode FORL a nécessité entre 1,56x et 2,2x moins de temps d'entraînement pour atteindre des profils de récompense comparables par rapport aux bases de référence d'apprentissage indépendant et de partage de paramètres.

5. Signification et Revendications

L'article affirme que le concept de Rang Ordinal permet de découpler efficacement le besoin d'informations sur l'état global dans les jeux de routage multi-agents. En se concentrant sur les "opposants immédiats" locaux et leurs rangs relatifs, les agents peuvent apprendre des stratégies robustes qui se généralisent bien à des tailles d'équipe plus grandes et à des environnements inconnus.

Les auteurs soutiennent que le FORL fournit un mécanisme pratique pour obtenir des politiques convergentes dans des jeux de routage compétitifs et stochastiques où les hypothèses coopératives traditionnelles échouent. Ce travail suggère que, dans les scénarios de conflit basés sur le rang, l'information locale conditionnée par la position ordinale est un signal d'apprentissage plus efficace que l'état global ou le rang global, offrant une solution scalable pour des flottes robotiques hétérogènes et auto-intéressées.