Online Learning and Equilibrium Computation with Ranking Feedback

1. Problématique et Contexte

L'apprentissage en ligne (online learning) dans des environnements arbitraires ou adverses est un pilier de la prise de décision séquentielle. Traditionnellement, les algorithmes reposent sur des retours d'information numériques (vecteurs d'utilité ou valeurs de récompense). Cependant, dans de nombreuses applications réelles impliquant des humains (comme le Reinforcement Learning from Human Feedback - RLHF) ou soumises à des contraintes de confidentialité, l'obtention de scores numériques calibrés est impossible ou coûteuse. À la place, les agents ne reçoivent que des classements (rankings) d'actions proposées.

L'article étudie ce problème dans un cadre non-stochastique (potentiellement adversaire) et explore deux mécanismes de génération de ces classements :

1. InstUtil Rank : Le classement est basé sur l'utilité instantanée au temps $t$.
2. AvgUtil Rank : Le classement est basé sur l'utilité moyenne dans le temps (cumulée jusqu'au temps $t$).

Le défi central est de minimiser le regret externe (la différence entre la performance de l'agent et celle de la meilleure action fixe a posteriori) et de garantir la convergence vers un équilibre de Nash (ou un équilibre corrélé grossier - CCE) dans les jeux répétés, en n'ayant accès qu'à ces retours de classement.

2. Méthodologie et Modélisation

Les auteurs modélisent le processus de feedback via le modèle Plackett-Luce (PL). À chaque étape $t$, étant donné un ensemble d'actions proposées $o(t)$, le classement $\sigma(t)$ est échantillonné selon une probabilité dépendante d'un vecteur d'utilité $r(t)$ et d'un paramètre de température $\tau > 0$.

• Si $\tau \to 0$, le classement est déterministe (l'action avec la plus haute utilité est toujours première).
• Si $\tau$ est grand, le classement devient plus bruité.

L'approche méthodologique se décompose en trois axes :

A. Résultats de Hardness (Impossibilité)

Les auteurs démontrent d'abord des bornes inférieures (hardness results) montrant que l'apprentissage sans regret est impossible dans certains cas :

• Pour InstUtil Rank, le regret est linéaire $\Omega(T)$ pour tout $\tau$ constant, car l'adversaire peut faire varier les utilités trop rapidement pour que le classement fournisse assez d'information.
• Pour AvgUtil Rank, si le modèle est trop déterministe ($\tau$ très petit, de l'ordre de $O(1/T \log T)$ ou $O(1/\log T)$), le regret reste linéaire. L'agent ne peut pas distinguer les séquences d'utilités qui produisent les mêmes classements.

B. Estimation d'Utilité et Algorithmes

Pour surmonter ces limitations, les auteurs proposent de nouvelles algorithmes basés sur l'estimation des vecteurs d'utilité à partir des permutations observées.

• Estimation par Fenêtre Glissante : Ils utilisent une fenêtre des $m$ dernières permutations pour estimer l'utilité. En décomposant le classement en comparaisons binaires (paires d'actions), ils exploitent la structure logistique du modèle PL pour inverser la probabilité de classement et estimer les utilités sous-jacentes.
• Hypothèse de Variation Sublinéaire : Pour obtenir des résultats positifs, ils imposent une hypothèse (Assumption 5.2) : la variation totale des vecteurs d'utilité au cours du temps doit être sublinéaire ($\sum \|u(t) - u(t-1)\| \le O(T^q)$ avec $q < 1$). Cela signifie que l'environnement ne change pas trop brutalement.
• Cas Full-Information vs Bandit :
  • En Full-Information (toutes les actions sont proposées), l'algorithme atteint un regret sous-linéaire sous l'hypothèse de variation.
  • En Bandit (seulement $K$ actions sont proposées), l'estimation est plus difficile. Les auteurs introduisent une technique de "blocage" (block-based estimation) pour gérer la variance de l'estimateur empirique, permettant d'atteindre un regret sous-linéaire sous des conditions plus strictes sur la variation ($q < 1/3$).
• Cas Spécial AvgUtil Rank Full-Information : De manière notable, pour le feedback AvgUtil Rank en Full-Information, l'hypothèse de variation sublinéaire n'est pas nécessaire (le regret est sous-linéaire même sans cette hypothèse), car la moyenne temporelle lisse naturellement les variations.

C. Calcul d'Équilibre

En appliquant ces algorithmes d'apprentissage sans regret dans un jeu normal-form répété où tous les joueurs utilisent ces stratégies, les auteurs prouvent que la stratégie moyenne conjointe converge vers un $\epsilon$-Équilibre Corrélé Grossier (CCE). La variation des stratégies des joueurs étant contrôlée par les algorithmes, la condition de variation sublinéaire des utilités est automatiquement satisfaite dans ce contexte.

3. Contributions Clés

1. Analyse de la Difficulté Fondamentale : Établissement de bornes inférieures montrant que le regret sous-linéaire est impossible pour des modèles de classement trop déterministes ou pour des utilités instantanées changeant trop vite.
2. Nouveaux Algorithmes d'Estimation : Développement d'estimateurs d'utilité robustes basés sur la décomposition des permutations en comparaisons binaires, valables pour les régimes Full-Information et Bandit.
3. Garanties de Regret Sous-Linéaire :
   • Preuve que le regret est sous-linéaire pour InstUtil Rank sous l'hypothèse de variation sublinéaire.
   • Preuve que le regret est sous-linéaire pour AvgUtil Rank (Full-Info) sans hypothèse de variation, et avec hypothèse pour le cas Bandit.
4. Convergence vers l'Équilibre : Démonstration que l'interaction de joueurs suivant ces algorithmes conduit à un équilibre approximatif (CCE) dans les jeux répétés.
5. Validation Empirique : Application réussie à une tâche de routage de modèles de langage (LLM), où un serveur doit choisir le meilleur modèle pour un utilisateur basé uniquement sur des classements de réponses.

4. Résultats Expérimentaux

Les auteurs ont validé leurs algorithmes sur :

• Jeux générés aléatoirement : Mesure de l'exploitabilité (distance à l'équilibre) qui diminue avec le temps, confirmant la convergence vers un CCE.
• Routage de LLM (Large Language Models) : Simulation d'un système recommandant des réponses générées par différents modèles (Qwen, Phi, GPT-4o, Llama) à un utilisateur. L'algorithme (Algorithm 3 avec AvgUtil Rank) a montré une diminution du regret moyen au fil du temps, s'approchant de la performance du meilleur modèle fixe a posteriori, même avec un feedback de classement bruité.

5. Signification et Impact

Ce travail comble un vide théorique important entre l'apprentissage en ligne classique (feedback numérique) et l'apprentissage basé sur les préférences (feedback de classement).

• Théorique : Il clarifie les limites fondamentales de l'apprentissage avec feedback de classement dans des environnements adverses, distinguant clairement les cas où l'apprentissage est possible ou non selon le type de feedback (instantané vs moyen) et le niveau de bruit ($\tau$).
• Pratique : Il offre des solutions algorithmiques concrètes pour des applications critiques comme le RLHF, les plateformes de recommandation et les systèmes de matchmaking, où les retours numériques sont souvent indisponibles. La capacité à garantir un équilibre dans les jeux multi-agents avec uniquement des classements ouvre la voie à des mécanismes de coordination plus robustes et respectueux de la vie privée.

En résumé, l'article établit que bien que l'apprentissage avec feedback de classement soit intrinsèquement plus difficile que l'apprentissage numérique, des garanties fortes de performance et de convergence vers l'équilibre sont possibles en exploitant la structure temporelle des préférences et en utilisant des estimateurs statistiques adaptés.