Multi-Agent Lipschitz Bandits

Technische Samenvatting: Multi-Agent Lipschitz Bandits

Probleemstelling
Dit artikel behandelt het gedecentraliseerde, coöperatieve multi-player stochastische banditprobleem over een continue, Lipschitz-gestructureerde actieruimte. De setting betreft $N$ agenten die opereren in een gedeelde omgeving $X = [0, 1]^d$ zonder directe communicatie. De gemiddelde beloningsfunctie $\mu: X \to [0, 1]$ is onbekend, maar wordt verondersteld $L$-Lipschitz continu te zijn.

Een cruciale beperking is het "harde botsingsmodel": als twee of meer agenten gelijktijdig acties binnen dezelfde regio (cel) selecteren, ontvangen alle botsende agenten een beloning van nul en geen observatie. Het doel is om de collectieve cumulatieve beloning over een tijdshorizon $T$ te maximaliseren. De uitdaging ligt in de samenloop van drie factoren: de continue actieruimte (die naïeve discretisering onwerkbaar maakt), de harde botsingsbeperking (die coördinatie vereist) en het gebrek aan communicatiekanalen.

Methodologie
De auteurs stellen een modulair, communicatievrij, vierfasenprotocol voor dat ontworpen is om het coördinatieprobleem te ontkoppelen van het leerprobleem. De strategie steunt op een op partities gebaseerd botsingsmodel waarbij de actieruimte wordt gediscretiseerd in $K$ hyperkubische cellen met een zijde van lengte $h$.

1. Fase I: Grove Identificatie:
   Alle agenten voeren gedurende een vaste duur $T_0$ uniforme willekeurige bemonstering van celcentra uit. Ondanks de hoge waarschijnlijkheid van botsingen, zorgt deze fase ervoor dat, met een hoge waarschijnlijkheid, elke agent voldoende niet-botsende observaties verkrijgt om grove betrouwbaarheidsgrenzen te construeren voor de maximale waarde van elke cel. Deze fase dient om de zoekruimte te verkleinen door suboptimale cellen te elimineren.

2. Fase II: Maxima-gestuurde Verfijning ("Local Peek"):
   Om de "center-vs-maximum" pathologie aan te pakken—waarbij de waarde van het centrum van een cel een slechte benadering is van de werkelijke supremum van die cel vanwege scherpe pieken nabij de grenzen—voeren agenten een gelokaliseerde exploratie uit binnen kandidaat-cellen. Ze bemonsteren een fijn raster ($\eta$-net) binnen de resterende kandidaat-cellen om hoog-resolutie betrouwbaarheidsintervallen op te bouwen voor de werkelijke celmaxima $\mu^*(C)$. Dit stelt agenten in staat om de top-$N$ cellen te identificeren op basis van hun werkelijke suprema in plaats van hun centra.

3. Fase II 1/2: Gedecentraliseerd Platsen ("Musical Chairs"):
   Zodra agenten het eens zijn over een set van $N$ doelcellen (ofwel via een $\epsilon$-uniekheidsvoorwaarde of publieke planning), moeten zij zichzelf aan deze cellen toewijzen zonder conflict. De auteurs analyseren een praktische versie van het "Musical Chairs"-protocol waarbij agenten niet weten welke cellen bezet zijn. Niet-geplaatste agenten bemonsteren de doelset herhaaldelijk totdat ze op een onbezette cel landen. De analyse toont aan dat dit proces in verwachte $O(N)$ tijd voltooid is.

4. Fase III: Optimalisatie binnen de Cel:
   Eenmaal geplaatst, fragmenteert het probleem in $N$ onafhankelijke single-player Lipschitz banditproblemen. Elke agent voert een standaard bijna-optimaal algoritme uit (bijv. Zooming) die beperkt is tot de toegewezen cel voor de rest van de horizon.

Belangrijkste Bijdragen

• Eerste End-to-End Oplossing: Dit werk biedt de eerste principiële oplossing voor gedecentraliseerde multi-player bandits in continue domeinen met harde botsingen.
• Maxima-gestuurde Identificatie: De auteurs introduceren een nieuwe identificatiefase die een "local peek" uitvoert om werkelijke cel-suprema te inkaderen, waardoor de inherente biases van centrum-gebaseerde rangschikkingsstrategieën effectief worden vermeden.
• Ontkoppeling van Coördinatie en Leren: Het protocol scheidt de coördinatiekosten van de leerkosten. De coördinatiefases (I, II en het plaatsen) brengen een kosten met zich mee die onafhankelijk zijn van de tijdshorizon $T$ (voor een vaste betrouwbaarheid) of slechts polylogarithmisch zijn in $T$ (in verwachte regret).
• Gap-vrije Garanties: Onder een aanname van publieke dekking/planning en een nabij-optimaliteit-dimensievoorwaarde, leiden de auteurs een gap-vrije regret-grens af, wat robuustheid garandeert zelfs wanneer de beloningsverschillen tussen cellen nul zijn.
• Uitbreiding naar Afstandsdrempelmodellen: Het raamwerk wordt uitgebreid naar algemene afstandsdrempel-botsingsmodellen door het probleem te mappen naar een set "veilige bollen" afgeleid van een $r$-packing, wat inter-agent scheiding waarborgt.

Resultaten en Regret-grenzen
Het artikel stelt de volgende regret-garanties vast, waarbij $d$ de dimensie van de actieruimte is:

• Consensus-regime: Onder een $\epsilon$-uniekheidsvoorwaarde (een voldoende groot verschil tussen de $N$-de en $(N+1)$-de beste cellen), is de verwachte cumulatieve regret begrensd door:
  $$\mathbb{E}[R(T)] \leq \underbrace{O(N(T_0 + T_1) + N^2)}_{\text{Coördinatiekosten}} + \underbrace{\tilde{O}\left(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}}\right)}_{\text{Leerproceskosten}}$$
  De dominante leerterm komt overeen met de optimale single-player Lipschitz-snelheid van $\tilde{O}(T^{(d+1)/(d+2)})$. De coördinatiekosten zijn horizon-onafhankelijk voor een vaste betrouwbaarheid.

• Gap-vrij Regime: Zonder een beloningsverschil aan te nemen, bereikt het algoritme een verwachte regret van $\tilde{O}(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$ door het protocol in epochen uit te voeren met dynamisch aangepaste precisie.

• Lower Bound: De auteurs bewijzen een bijbehorende minimax lower bound van $\Omega(N (Lh)^{\frac{d}{d+2}} T^{\frac{d+1}{d+2}})$, wat aantoont dat de $T^{(d+1)/(d+2)}$-afhankelijkheid niet verbeterd kan worden in deze regimes. Dit bevestigt dat decentralisatie en botsingen de kern van de statistische moeilijkheid vergeleken met de single-player situatie niet verslechteren.

Significantie
Het artikel beweert de eerste end-to-end garanties te bieden voor multi-player bandits in continue domeinen. De primaire significantie ligt in het aantonen dat de coördinatie-overhead in een gedecentraliseerde setting geïsoleerd en onafhankelijk gemaakt kan worden van de tijdshorizon, waardoor het collectieve systeem dezelfde asymptotische leersnelheid kan bereiken als een enkele optimale agent. Het werk benadrukt dat met een maxima-gestuurde zoekstrategie de subtiele uitdagingen van continue actieruimtes (specifiek de center-vs-maximum bias) zonder communicatie kunnen worden opgelost, wat efficiënte coöperatieve exploratie mogelijk maakt in omgevingen met strijd om middelen.