Résumé Technique : Apprentissage de l'Affectation de Tâches de Prédiction à des Agents avec Contraintes de Capacité

Définition du Problème

L'article aborde le problème de l'affectation séquentielle en ligne de tâches dans des environnements où les tâches arrivent de manière séquentielle et doivent être allouées à un ensemble d'agents disponibles (humains ou IA). Le défi central implique deux contraintes simultanées :

1. Expertise Hétérogène et Dépendante du Contexte : Les agents possèdent des niveaux d'expertise variables qui dépendent du contexte spécifique de la tâche (par exemple, un radiologue peut exceller dans des cas médicaux spécifiques mais pas dans d'autres ; un LLM peut mieux performer sur certains types de requêtes). Cette expertise est initialement inconnue et doit être apprise en ligne.
2. Contraintes de Capacité : Contrairement aux contraintes de budget de coûts où un agent peu coûteux pourrait théoriquement gérer toutes les tâches, ce cadre impose des limites de capacité à long terme sur les agents individuels. Chaque agent $a$ a une fraction cible $\alpha_a$ de la charge de travail totale qu'il peut gérer. Cela reflète des limites opérationnelles réelles telles que la fatigue humaine, l'épuisement professionnel ou les niveaux de dotation, empêchant la sur-allocation de tâches à un seul agent hautement performant.

L'objectif est d'apprendre une politique d'affectation qui maximise la récompense espérée globale (par exemple, la précision de la prédiction) tout en adhérant strictement à ces contraintes de capacité à long terme, malgré l'incertitude initiale concernant la performance des agents.

Méthodologie

Cadre Théorique

Les auteurs modélisent le problème comme un bandit manchot contextuel (MAB).

• Politique Optimale Sans Contrainte : Dans un cadre oracle où l'expertise de l'agent $\mu_a(x)$ est connue, la politique optimale assigne chaque contexte $x$ à l'agent ayant la récompense espérée conditionnelle la plus élevée.
• Politique Optimale Contrainte : Lorsque des contraintes de capacité $\alpha_a$ sont introduites, les auteurs dérivent la politique optimale en utilisant des multiplicateurs de Lagrange. Ils prouvent que la politique optimale contrainte prend la forme :
  $$\phi^*(x) = \arg\max_{a} \{ \mu_a(x) - \lambda_a \}$$
  où $\lambda_a$ agit comme un « prix d'ombre » pour la contrainte de capacité. Cela implique que la stratégie optimale consiste à assigner les tâches à l'agent ayant la récompense ajustée la plus élevée, pénalisant efficacement les agents qui approchent de leurs limites de capacité.
• Analyse à Deux Agents : L'article fournit des caractérisations spécifiques pour le cas à deux agents, montrant que la politique optimale assigne l'agent avec une capacité $\alpha$ au $\alpha$-masse de contextes où l'écart de récompense $\Delta(x) = \mu_1(x) - \mu_2(x)$ est le plus grand. L'analyse théorique démontre que les politiques contextuelles surpassent strictement les bases non contextuelles (aléatoires ou à agent fixe) dès que la performance de l'agent varie avec le contexte.

Algorithme d'Apprentissage en Ligne

Pour gérer le scénario pratique où $\mu_a(x)$ est inconnu, les auteurs proposent un cadre d'apprentissage en ligne basé sur des files d'attente :

1. Modélisation du Contexte : L'expertise de l'agent est modélisée en utilisant soit une régression logistique (avec approximation de Laplace pour l'estimation a posteriori), soit des modèles basés sur des arbres (forêts aléatoires). Le cadre prend en charge à la fois l'échantillonnage de Thompson (pour l'exploration via l'échantillonnage a posteriori) et la sélection Gourmande (en utilisant des estimations ponctuelles).
2. Application des Contraintes par File d'Attente : Pour appliquer les contraintes de capacité à long terme sans connaître l'avenir, l'algorithme maintient une file d'attente virtuelle $Q_{t,a}$ pour chaque agent. La file d'attente suit l'écart cumulatif entre les affectations réalisées et la capacité cible $\alpha_a$ :
   $$Q_{t+1,a} = [Q_{t,a} + \mathbb{I}(a_t = a) - \alpha_a]_+$$
3. Règle de Décision : À chaque étape $t$, l'agent est sélectionné en maximisant un score ajusté qui équilibre la récompense estimée et la pression de la file d'attente :
   $$a_t = \arg\max_{a} \{ \mu_{a,t}(x_t) - \eta Q_{t,a} \}$$
   Ici, $\eta$ est un paramètre de pénalité contrôlant le compromis entre la maximisation de la récompense et la satisfaction des contraintes. La longueur de la file d'attente $Q_{t,a}$ sert d'estimation dynamique et variant dans le temps du prix d'ombre $\lambda_a$.

Les auteurs prouvent que cet algorithme hérite des bornes de regret sous-linéaires standard de la littérature sur l'échantillonnage de Thompson contextuel, même avec la complexité ajoutée des files d'attente virtuelles.

Résultats Expérimentaux

Le cadre a été évalué dans divers scénarios impliquant des tâches de prédiction sur des tableaux, des images et du texte, en utilisant des classificateurs d'apprentissage automatique, des Modèles de Langage de Grande Taille (LLM) et des annotateurs humains (réels et simulés).

• Ensembles de Données : Les expériences ont inclus Camelyon17 (imagerie médicale), MMLU (routage LLM), ImageNet16H (humain vs IA), et quatre ensembles de données tabulaires (Banque, Crédit, Coupon, Cardio).
• Performance : Les politiques d'affectation contextuelles (à la fois logistiques et basées sur des arbres, utilisant des stratégies d'échantillonnage de Thompson ou Gourmandes) ont systématiquement surpassé les bases non contextuelles à tous les niveaux de capacité.
  • Les politiques combinées ont souvent atteint des taux d'erreur inférieurs au taux d'erreur marginal du meilleur agent individuel, validant l'affirmation théorique selon laquelle l'exploitation d'expertises complémentaires améliore la performance globale du système.
  • Les modèles basés sur des arbres ont généralement surpassé les modèles logistiques, suggérant l'importance de capturer des motifs non linéaires dans l'expertise des agents.
  • Les approches Gourmande et d'échantillonnage de Thompson ont donné des résultats similaires, les contraintes elles-mêmes fournissant une exploration implicite suffisante.
• Configuration par Mini-Lots : Les auteurs ont exploré une configuration par mini-lots où les affectations sont faites pour un lot de tâches avant d'observer les résultats. Ils ont trouvé une courbe d'erreur en forme de U par rapport à la taille du lot : les petits lots permettent des mises à jour fréquentes mais une application des capacités bruyante, tandis que les grands lots retardent l'apprentissage. Les tailles de lots intermédiaires offraient le meilleur compromis, bien qu'au prix d'une latence accrue.
• Sensibilité : L'analyse de sensibilité sur le paramètre de pénalité de file d'attente $\eta$ a montré que des valeurs plus petites privilégient la maximisation de la récompense (s'approchant de la performance sans contrainte), tandis que des valeurs plus grandes appliquent la capacité de manière plus agressive (s'approchant d'une affectation aléatoire non contextuelle).

Contributions Clés

1. Caractérisation Théorique : L'article fournit un cadre théorique général pour l'affectation de tâches avec des agents contraints par la capacité, caractérisant les politiques optimales en termes de prix d'ombre et de différences d'expertise dépendantes du contexte.
2. Cadre Algorithmique : Il introduit un algorithme pratique d'apprentissage en ligne qui apprend conjointement l'expertise des agents et applique des contraintes de capacité à long terme en utilisant un mécanisme basé sur des files d'attente, applicable à la fois aux agents humains et aux agents IA.
3. Validation Empirique : Grâce à des expériences extensives sur plusieurs modalités (texte, image, tableau) et types d'agents (LLM, humains, classificateurs), l'article démontre que les politiques contextuelles contraintes par la capacité produisent des gains systématiques par rapport aux bases non contextuelles.

Importance et Revendications

L'article revendique que la collaboration efficace humain-IA et l'allocation de tâches organisationnelle à grande échelle dépendent non seulement de l'amélioration de la performance individuelle des agents, mais aussi de la conception de politiques d'allocation qui apprennent une expertise hétérogène tout en respectant les limites de capacité du monde réel.

Les auteurs soulignent que leur approche comble une lacune critique dans les travaux antérieurs (tels que l'apprentissage de la déférence ou le routage LLM), qui supposent souvent un apprentissage hors ligne ou ignorent les limites de charge de travail spécifiques aux agents. En modélisant le problème conjoint de l'apprentissage de l'expertise et de la gestion de la capacité en ligne, le cadre permet aux systèmes de s'adapter dynamiquement aux changements de distribution et aux contraintes opérationnelles. Les résultats suggèrent que l'ignorance du contexte ou des contraintes de capacité conduit à des performances sous-optimales, tandis que leur modélisation conjointe permet l'exploitation de la complémentarité des agents, surpassant potentiellement même le meilleur agent unique du système.

L'article reste modeste concernant sa portée, notant que les évaluations ont été menées en utilisant des agents proxy dans des environnements contrôlés avec des contextes de dimension relativement faible. Il reconnaît que les applications réelles peuvent impliquer des contextes de haute dimension et multimodaux, des retours différés et des comportements d'agents évolutifs, identifiant ces aspects comme des directions pour un travail futur.