A Linear Matching Bandit Approach to Online Multi-Human Multi-Robot Teaming

Formulation du Problème
L'article traite du défi de la collaboration en ligne entre plusieurs humains et plusieurs robots, un scénario où un apprenant doit assigner un ensemble fixe de $K$ robots aux capacités inconnues à des ensembles variables de $M$ agents humains sur $T$ tours. L'objectif est de maximiser la récompense cumulative générée par ces équipes humain-robot. Le problème est formulé dans le cadre d'un bandit de correspondance linéaire (linear matching bandit). La difficulté principale réside dans deux aspects : l'« espace de bras intraçable », où traiter chaque correspondance unique comme un bras de bandit distinct entraîne une croissance exponentielle, et la « complexité combinatoire », où les contraintes de correspondance interconnectent les récompenses et compliquent l'optimisation.

Les auteurs supposent une structure de récompense linéaire où la récompense attendue d'une équipe formée par un agent humain $m$ (avec un vecteur de caractéristiques connu $X_{m,t} \in \mathbb{R}^d$) et un robot $k$ (avec un vecteur de caractéristiques inconnu $\theta_k \in \mathbb{R}^d$) est donnée par le produit scalaire $X_{m,t}^\top \theta_k$. Bien que les caractéristiques humaines soient observables (dérivées de profils ou du contexte de la tâche), les caractéristiques des robots sont inconnues en raison de la complexité et du manque de transparence des systèmes d'IA avancés. L'apprenant observe les caractures des humains arrivants, sélectionne une correspondance (une fonction d'injection des humains vers les robots) et reçoit des récompenses bruitées.

Méthodologie : Algorithme LinMatch
Pour résoudre cela, les auteurs proposent LinMatch, un algorithme d'apprentissage en ligne basé sur le principe de l'« Optimisme face à l'Incertitude » (OFU - Optimism in the Face of Uncertainty). L'algorithme opère par tours et consiste en les étapes suivantes :

1. Construction de l'Intervalle de Confiance : En utilisant la régression ridge, LinMatch estime les vecteurs de caractéristiques inconnus $\theta_k$ pour chaque robot. Il maintient une matrice de covariance $V_{k,t}$ et une somme pondérée des récompenses $H_{k,t}$ pour chaque robot basée sur les affectations historiques. Cela permet la construction d'un intervalle de confiance ellipsoïdal $\hat{\Theta}_{k,t}$ pour chaque $\theta_k$, garantissant que le paramètre réel se situe dans l'intervalle avec une haute probabilité.
2. Correspondance Optimiste : À chaque tour, l'algorithme calcule une correspondance « optimiste ». Au lieu d'utiliser les estimations ponctuelles de $\theta_k$, il sélectionne les vecteurs de paramètres au sein des intervalles de confiance qui maximisent la récompense totale attendue.
3. Résolution Efficace via la Programmation Linéaire : Une contribution technique clé est la reformulation du problème de correspondance optimiste. Les auteurs démontrent que le programme entier-mixte requis pour trouver la correspondance qui maximise la somme des produits scalaires sur les ensembles de confiance peut être décomposé. En définissant des estimations de récompense optimistes $\tilde{y}_{mk,t}$ pour chaque paire humain-robot, le problème se réduit à un problème standard de correspondance de poids maximal dans un graphe biparti. Cela peut être résolu efficacement en un temps de $O(K^3)$ en utilisant l'algorithme hongrois.

Contributions Clés et Résultats Théoriques
L'article présente deux contributions principales :

1. Reformulation Algorithmique : Il recaste le problème de correspondance optimiste de chaque tour comme un programme linéaire de correspondance de poids maximal, ce qui le rend calculablement traitable via l'algorithme hongrois.
2. Bornes de Regret Serrées : Les auteurs fournissent des garanties théoriques rigoureuses pour LinMatch.
   • Borne Supérieure : Ils établissent une borne supérieure indépendante de l'instance du regret cumulé de $\tilde{O}(d\sqrt{MKT})$, où $d$ est la dimension des caractéristiques, $M$ est le nombre d'humains, $K$ est le nombre de robots, et $T$ est l'horizon temporel.
   • Borne Inférieure : Ils prouvent une borne inférieure minimax de $\Omega(d\sqrt{MKT})$ pour toute politique de correspondance dans ce contexte.
   • Optimalité : L'appariement des bornes supérieure et inférieure établit un taux de regret optimal serré de $\tilde{\Theta}(d\sqrt{MKT})$. Cela démontre que LinMatch atteint le taux de regret optimal strictement réalisable par rapport à tous les paramètres du problème ($T, d, M, K$).

Résultats Expérimentaux
Les auteurs valident LinMatch par des simulations numériques avec $K=20$ robots et $M=10$ humains.

• Comparaison avec ETC : LinMatch est comparé à un algorithme Explore-Then-Commit (ETC). Bien que l'ETC puisse atteindre un regret sous-linéaire avec une phase d'exploration de longueur optimale, il souffre d'un regret linéaire si l'exploration est insuffisante. LinMatch démontre une performance plus constante avec un intervalle de confiance plus étroit par rapport à l'ETC.
• Sensibilité à la Régularisation : Les expériences variant le paramètre de régularisation $\lambda$ montrent que, bien que la borne supérieure théorique nécessite $\lambda \ge L^2$, en pratique, des valeurs plus petites (par exemple, $\lambda=1$) produisent souvent des regrets plus faibles, suggérant que la condition théorique est conservatrice.

Signification et Portée
L'article affirme que LinMatch est le premier travail montrant que le taux de regret optimal réalisable et indépendant de l'instance pour les problèmes de correspondance avec une structure de bandit linéaire est précisément $\tilde{\Theta}(d\sqrt{MKT})$. L'approche proposée est conçue pour être applicable au-delà de la collaboration humain-robot, à tout problème de correspondance centralisée avec des caractéristiques linéaires, tels que l'allocation de logements et les systèmes de recommandation. Ce travail souligne qu'en exploitant la structure linéaire et l'optimisation combinatoire efficace, on peut surmonter la complexité exponentielle typiquement associée à la correspondance multi-agents dans les contextes d'apprentissage en ligne.