Technische Samenvatting: Leren Toewijzen van Voorspellingstaken aan Agenten met Capaciteitsbeperkingen

Probleemdefinitie

Het artikel behandelt het probleem van online sequentiële taaktoewijzing in omgevingen waar taken sequentieel binnenkomen en moeten worden toegewezen aan een set beschikbare agenten (menselijk of AI). De kernuitdaging omvat twee gelijktijdige beperkingen:

1. Heterogene, contextafhankelijke expertise: Agenten bezitten verschillende niveaus van expertise die afhankelijk zijn van de specifieke context van de taak (bijvoorbeeld: een radioloog kan uitblinken in specifieke medische gevallen maar niet in andere; een LLM kan beter presteren bij bepaalde querytypes). Deze expertise is aanvankelijk onbekend en moet online worden aangeleerd.
2. Capaciteitsbeperkingen: In tegenstelling tot kostenbegrotingsbeperkingen, waarbij een enkele goedkope agent theoretisch alle taken zou kunnen afhandelen, legt deze setting langetermijncapaciteitslimieten op aan individuele agenten. Elke agent $a$ heeft een doelpercentage $\alpha_a$ van de totale werklast die zij kunnen afhandelen. Dit weerspiegelt realistische operationele limieten zoals menselijke vermoeidheid, burn-out of personeelsniveaus, waardoor overtoewijzing van taken aan een enkele hoogpresterende agent wordt voorkomen.

Het doel is om een toewijzingsbeleid te leren dat de totale verwachte beloning (bijvoorbeeld voorspellingnauwkeurigheid) maximaliseert, terwijl strikt wordt voldaan aan deze langetermijncapaciteitsbeperkingen, ondanks de aanvankelijke onzekerheid over de prestaties van de agenten.

Methodologie

Theoretisch Kader

De auteurs modelleren het probleem als een contextuele multi-armed bandit (MAB).

• Optimaal Ongedwongen Beleid: In een orakelsetting waar de expertise van de agent $\mu_a(x)$ bekend is, wijst het optimale beleid elke context $x$ toe aan de agent met de hoogste conditionele verwachte beloning.
• Optimaal Gedwongen Beleid: Wanneer capaciteitsbeperkingen $\alpha_a$ worden geïntroduceerd, leiden de auteurs het optimale beleid af met behulp van Lagrange-multiplicatoren. Zij bewijzen dat het optimale gedwongen beleid de volgende vorm aanneemt:
  $$\phi^*(x) = \arg\max_{a} \{ \mu_a(x) - \lambda_a \}$$
  waarbij $\lambda_a$ fungeert als een "schaduwprijs" voor de capaciteitsbeperking. Dit impliceert dat de optimale strategie is om taken toe te wijzen aan de agent met de hoogste gecorrigeerde beloning, waardoor agenten die hun capaciteitslimieten naderen effectief worden bestraft.
• Analyse van Twee Agenten: Het artikel biedt specifieke karakteriseringen voor het geval van twee agenten, waarbij wordt aangetoond dat het optimale beleid de agent met capaciteit $\alpha$ toewijst aan de $\alpha$-massa van contexten waar de beloningskloof $\Delta(x) = \mu_1(x) - \mu_2(x)$ het grootst is. Theoretische analyse toont aan dat contextuele beleidslijnen non-contextuele (willekeurige of vaste-agent) baselines strikt overtreffen zolang de prestaties van de agenten variëren met de context.

Online Leringsalgoritme

Om het praktische scenario te hanteren waarin $\mu_a(x)$ onbekend is, stellen de auteurs een op wachtrijen gebaseerd online leringskader voor:

1. Contextmodelleren: De expertise van agenten wordt gemodelleerd met behulp van logistische regressie (met Laplace-approximatie voor posterior-schatting) of op bomen gebaseerde modellen (Random Forests). Het kader ondersteunt zowel Thompson Sampling (voor exploratie via posterior-sampling) als Gierige selectie (met behulp van punt-schattingen).
2. Op Wachtrijen Gebaseerde Handhaving van Beperkingen: Om langetermijncapaciteitsbeperkingen af te dwingen zonder de toekomst te kennen, onderhoudt het algoritme een virtuele wachtrij $Q_{t,a}$ voor elke agent. De wachtrij houdt de cumulatieve afwijking bij tussen gerealiseerde toewijzingen en de doelcapaciteit $\alpha_a$:
   $$Q_{t+1,a} = [Q_{t,a} + \mathbb{I}(a_t = a) - \alpha_a]_+$$
3. Beslissingsregel: Bij elke stap $t$ wordt de agent geselecteerd door het maximaliseren van een gecorrigeerde score die de geschatte beloning en de druk van de wachtrij in evenwicht brengt:
   $$a_t = \arg\max_{a} \{ \mu_{a,t}(x_t) - \eta Q_{t,a} \}$$
   Hierbij is $\eta$ een straffingsparameter die de afweging controleert tussen beloningsmaximalisatie en het naleven van beperkingen. De wachtrijlengte $Q_{t,a}$ dient als een dynamische, tijdsvariërende schatting van de schaduwprijs $\lambda_a$.

De auteurs bewijzen dat dit algoritme standaard sublineaire regretgrenzen erft uit de literatuur over contextuele Thompson Sampling, zelfs met de toegevoegde complexiteit van virtuele wachtrijen.

Experimentele Resultaten

Het kader werd geëvalueerd in diverse settings die tabulaire, beeld- en tekstvoorspellingstaken omvatten, met gebruik van machine learning-classificators, Large Language Models (LLMs) en menselijke annotatoren (zowel echt als gesimuleerd).

• Datasets: Experimenten omvatten Camelyon17 (medische beeldvorming), MMLU (LLM-routing), ImageNet16H (mens versus AI) en vier tabulaire datasets (Bank, Credit, Coupon, Cardio).
• Prestaties: Contextuele toewijzingsbeleid (zowel logistisch als op bomen gebaseerd, met gebruik van Thompson Sampling of Gierige strategieën) overtroffen systematisch non-contextuele baselines op alle capaciteitsniveaus.
  • De gecombineerde beleidslijnen bereikten vaak lagere foutpercentages dan het marginale foutpercentage van de beste individuele agent, wat de theoretische claim bevestigt dat het benutten van complementaire expertise de algehele systeemprestatie verbetert.
  • Op bomen gebaseerde modellen presteerden over het algemeen beter dan logistische modellen, wat wijst op het belang van het vastleggen van niet-lineaire patronen in de expertise van agenten.
  • Gierige selectie en Thompson Sampling presteerden vergelijkbaar, waarbij de beperkingen zelf voldoende impliciete exploratie boden.
• Mini-batch Setting: De auteurs onderzochten een mini-batch-setting waarbij toewijzingen worden gedaan voor een batch taken voordat uitkomsten worden waargenomen. Zij vonden een U-vormige foutcurve met betrekking tot de batchgrootte: kleine batches staan frequente updates toe maar leiden tot ruis in de capaciteitshandhaving, terwijl grote batches leren vertragen. Intermediaire batchgroottes boden de beste afweging, zij het ten koste van verhoogde latentie.
• Gevoeligheid: Gevoeligheidsanalyse van de straffingsparameter voor de wachtrij $\eta$ toonde aan dat kleinere waarden prioriteit geven aan beloningsmaximalisatie (naderend bij ongedwongen prestaties), terwijl grotere waarden capaciteit agressiever afdwingen (naderend bij non-contextuele willekeurige toewijzing).

Belangrijkste Bijdragen

1. Theoretische Karakterisatie: Het artikel biedt een algemeen theoretisch kader voor taaktoewijzing met capaciteitsbeperkte agenten, waarbij optimale beleidslijnen worden gekarakteriseerd in termen van schaduwprijzen en contextafhankelijke expertiseverschillen.
2. Algoritmisch Kader: Het introduceert een praktisch online leringsalgoritme dat gezamenlijk de expertise van agenten leert en langetermijncapaciteitsbeperkingen afdwingt met behulp van een op wachtrijen gebaseerd mechanisme, toepasbaar op zowel menselijke als AI-agenten.
3. Empirische Validatie: Door uitgebreide experimenten over meerdere modaliteiten (tekst, beeld, tabulair) en agenttypes (LLMs, mensen, classificators) toont het artikel aan dat contextuele capaciteitsbeperkte beleidslijnen systematische winsten opleveren ten opzichte van non-contextuele baselines.

Betekenis en Claims

Het artikel claimt dat effectieve mens-AI-samenwerking en grootschalige organisatorische taaktoewijzing niet alleen afhankelijk zijn van het verbeteren van de prestaties van individuele agenten, maar ook van het ontwerpen van toewijzingsbeleid dat heterogene expertise leert terwijl het rekening houdt met realistische capaciteitslimieten.

De auteurs benadrukken dat hun aanpak een kritieke kloof in eerdere werken (zoals leren uitstellen of LLM-routing) aanpakt, die vaak uitgaan van offline leren of agent-specifieke werklastlimieten negeren. Door het gezamenlijke probleem van het leren van expertise en het beheren van capaciteit online te modelleren, stelt het kader systemen in staat zich dynamisch aan te passen aan distributieveranderingen en operationele beperkingen. De resultaten suggereren dat het negeren van context of capaciteitsbeperkingen leidt tot suboptimale prestaties, terwijl het gezamenlijk modelleren ervan toelaat om van de complementariteit van agenten gebruik te maken, wat potentieel zelfs de beste enkele agent in het systeem kan overtreffen.

Het artikel blijft bescheiden wat betreft de reikwijdte, met de opmerking dat evaluaties werden uitgevoerd met proxy-agenten in gecontroleerde settings met relatief laag-dimensionale contexten. Zij erkennen dat real-world toepassingen hoog-dimensionale, multimodale contexten, vertraagde feedback en evoluerend gedrag van agenten kunnen omvatten, en identificeren deze als richtingen voor toekomstig werk.