Learning in Matching Games with Bandit Feedback

Technische Samenvatting: Leren in Matchingsspellen met Bandit-feedback

Probleemformulering
Dit artikel introduceert een nieuw leerprobleem dat zich bevindt op het snijvlak van tweezijdige matching-markten en speltheorie. De setting betreft een gegeneraliseerde markt met twee verschillende verzamelingen agenten, $P$ en $A$, die over een tijdshorizon $T$ door een centraal platform aan elkaar worden gekoppeld. In tegenstelling tot traditionele matching-problemen waarbij agenten statische, bekende voorkeuren hebben, of standaard Multi-Armed Bandit (MAB) instellingen waarbij agenten directe stochastische beloningen ontvangen, postuleert dit kader dat gejoinde agenten, zodra ze gematcht zijn, een twee-speler nul-som spel (ZSG) aangaan met een aanvankelijk onbekende payoff-matrix.

In dit scenario moeten agenten zowel de onderliggende speldynamiek als hun voorkeuren afleiden uit de uitkomsten van deze interacties. Op elk tijdstip $t$:

1. Genereert een centraal platform een matching $m_t$ op basis van geschatte agent-voorkeuren.
2. Kiezen gematchte agenten strategieën (gemengde acties) en samplen specifieke acties.
3. Ontvangen agenten stochastische bandit-feedback (beloningen) en observeren de acties van hun gematchte partner.
4. Updaten agenten hun schattingen van de payoff-matrices en hun voorkeuren voor de volgende ronde.

De kernuitdaging is het leren van een Matching Equilibrium, een oplossingsconcept gedefinieerd door [10] waarbij de matching stabiel is (geen blokkerende paren) en de agenten een Nash-evenwicht (NE) spelen met hun toegewezen partners. De moeilijkheid ontstaat doordat agenten de spelmatrices niet vooraf kennen en moeten exploreren om voorkeuren te vormen, terwijl het matching-mechanisme (meestal Gale-Shapley) afhankelijk is van die voorkeuren om stabiliteit te waarborgen.

Methodologie en Algoritme
Om dit aan te pakken, stellen de auteurs UCB-MG voor, een algoritme gebaseerd op het principe van "optimisme in het gezicht van onzekerheid". De methodologie werkt als volgt:

• Optimistische Schattingen: Agenten houden Upper Confidence Bounds (UCB) bij voor de payoff-matrices van potentiële matches. Specifiek wordt voor een paar $(p, a)$ de optimistische payoff-matrix $\bar{A}_{p,a}$ geconstrueerd door een confidence bonus toe te voegen aan het empirische gemiddelde van de geobserveerde beloningen.
• Voorkeuren Vormen: Op basis van deze optimistische payoff-matrices berekenen agenten de optimistische spelwaarde ($\bar{V}^*$) uitgaande van optimaal spel (minimax-strategieën) tegen elke potentiële partner. Agenten rangschikken vervolgens hun voorkeuren volgens deze optimistische spelwaarden.
• Matching: Het centrale platform verzamelt deze gerapporteerde voorkeuren en voert het Gale-Shapley (GS) algoritme uit om een stabiele matching voor de huidige ronde te genereren.
• Strategie-Executie: Eenmaal gematcht, kiezen agenten acties op basis van de minimax-strategieën afgeleid van hun optimistische payoff-matrices, samplen acties en ontvangen feedback om hun schattingen bij te werken.

Regret Formulering: Matching Instabiliteit
Een cruciale bijdrage van het artikel is de definitie van een passende regret-metriek, getiteld Matching Instability (MI). Standaard regret-definities uit MAB of speltheorie zijn onvoldoien omdat het doel is om te convergeren naar een gezamenlijk evenwicht van matching en strategie.

De auteurs definiëren MI als de minimale totale subsidie die nodig is om de markt te stabiliseren, gegeven een huidige matching $m$ en strategieprofiel $X$. Wiskundig gezien is het de oplossing van een lineair programma dat subsidies $s_a$ minimaliseert onder de voorwaarden:

1. Geen Blokkerende Paren: Ervoor zorgen dat geen enkel paar $(p, a)$ hun nut kan verbeteren door af te wijken, gegeven de huidige strategieën.
2. Individuele Rationaliteit: Ervoor zorgen dat agenten hun match verkiezen boven niet gematcht zijn.
3. Waarborging van Waarde: Ervoor zorgen dat agenten een nut ontvangen dat ten minste gelijk is aan de minimax-waarde van hun spel (een relaxatie van de strikte Nash-conditie om een tractabele analyse te faciliteren).

De cumulatieve regret $R_T$ wordt gedefinieerd als de som van de Matching Instability over de horizon $T$.

Belangrijkste Bijdragen

1. Definitie van het Leerprobleem: Het artikel formaliseert de eerste leeromgeving waar agenten in een tweezijdige markt onbekende nul-som spelen moeten leren om voorkeuren voor matching te vormen.
2. Regret-Metriek: Het introduceert Matching Instability, waarmee het concept van Subset Instability [8, 17] wordt uitgebreid naar settings waar gematchte agenten spelen. Deze metriek kwantificeert de afstand tot een Matching Equilibrium.
3. Algoritme Ontwerp: De auteurs stellen een UCB-gebaseerd algoritme (UCB-MG) voor dat optimistische spelwaarde-schatting integreert met het Gale-Shapley mechanisme.
4. Theoretische Garanties: Het artikel bewijst dat het voorgestelde algoritme een sublineaire, instantie-onafhankelijke regret-bound bereikt van $\tilde{O}(\sqrt{Tmkpa})$, waarbij $T$ de horizon is, en $m$ en $k$ het aantal acties per agent zijn, en $p$ en $a$ het aantal agenten aan elke zijde zijn.
5. Generalisatie: De theoretische bound verenigt bestaande resultaten. Wanneer $m=k=1$, herstelt het de bound voor klassieke tweezijdige matching ($\tilde{O}(\sqrt{Tpa})$). Wanneer $p=a=1$, herstelt het de bound voor self-play in nul-som spelen ($\tilde{O}(\sqrt{Tmk})$).

Resultaten en Empirisch Bewijs
De auteurs bieden empirische validatie via synthetische instanties waarbij payoff-matrices worden gesampled uit een normale verdeling. Ze vergelijken drie scenario's:

• Self-Play: Beide zijden volgen het UCB-MG algoritme.
• Nash-Response: Eén zijde kent de ware spelmatrices en speelt de Nash-evenwichtstrategie, terwijl de andere zijde leert.
• Best-Response: Eén zijde kent de ware matrices en de strategieën van de tegenstander, en speelt de best response.

Resultaten geven aan dat het systeem een stabiele uitkomst leert in alle scenario's, waarbij een sublineaire groei van de regret wordt vertoond. Zoals verwacht, levert het Nash-Response scenario de laagste regret op. Interessant genoeg presteert het Best-Response scenario aanvankelijk beter dan Self-Play, maar de prestaties verslechteren naarmate de marktomvang (aantal agenten en acties) toeneemt, waarschijnlijk door de complexiteit die ontstaat wanneer één zijde de andere exploiteert.

Betekenis en Toekomstige Richtingen
Het artikel claimt significant te zijn als een eerste stap naar het begrijpen van leren in omgevingen waar agenten pas beloningen ontvangen na interactie via acties in een spel, in plaats van directe voorkeurssignalen te ontvangen. Het demonstreert dat stabiele uitkomsten efficiënt geleerd kunnen worden in dergelijke complexe, gekoppelde settings.

De auteurs kaderen dit werk bescheiden als een fundament voor toekomstig onderzoek. Zij identificeren verschillende openstaande richtingen:

• Het uitbreiden van het model van nul-som naar algemene som spelen.
• Het integreren van no-regret leeralgoritmen (zoals Exp3) in het matching-kader om niet-nul-som dynamiek aan te pakken.
• Het versoepelen van de aanname dat agenten de acties van hun partner observeren.
• Het verkennen van alternatieve spelmodellen (Markov-spelen, Stackelberg-spelen) en matching-structuren (many-to-one markten).
• Het onderzoeken van gedecentraliseerde settings waar agenten zowel matches als strategieën selecteren zonder een centrale coördinator.