Robust Multi-Agent Bandits with Heavy-Tailed Rewards and Information Asymmetry

Technische Samenvatting: Robuuste Multi-Agent Bandieten met Heavy-Tailed Beloningen en Informatie-asymmetrie

Probleemformulering
Dit werk behandelt het Multi-Armed Bandit (MAB) probleem in een gedecentraliseerde, multi-agent setting waarbij de beloningsverdelingen "heavy-tailed" zijn. In tegen punten van de standaard literatuur, die uitgaat van sub-Gaussische beloningen, beschouwt dit artikel verdelingen waarbij het $(1+\epsilon)$-de moment eindig is ($E[|X - \mu|^{1+\epsilon}] \le v$), maar de variantie oneindig kan zijn. De studie richt zich op $M$ spelers die moeten coördineren om gezamenlijke beloningen te maximaliseren zonder online communicatie. De auteurs definiëren drie verschillende regimes van informatie-asymmetrie:

1. Probleem A (Gedeelde beloningen, niet-geobserveerde acties): Alle spelers observeren dezelfde beloningsrealisatie voor een gezamenlijke actie, maar kunnen de individuele acties die anderen kiezen niet zien.
2. Probleem B (Onafhankelijke beloningen, geobserveerde acties): Spelers observeren de gezamenlijke actie die door de groep is genomen, maar ontvangen onafhankelijke, i.i.d. beloningsmonsters.
3. Probleem C (Onafhankelijke beloningen, niet-geobserveerde acties): Spelers observeren noch een gezamenlijke beloning, noch de acties van anderen; elke speler ontvangt alleen zijn eigen onafhankelijke monster.

Methodologie en Algoritmen
De auteurs stellen robuuste gedecentraliseerde algoritmen voor elk regime voor, waarbij robuuste gemiddelde schatters (specifiek getrunceerde gemiddelden) worden aangepast aan de multi-agent context.

• Probleem A (mRUCB-A): Omdat beloningen gedeeld worden, behouden alle spelers identieke statistische schattingen als zij een deterministische regel volgen. Het algoritme maakt gebruik van een Robust Upper Confidence Bound (RUCB) index. Spelers spreken een lexicografische ordening af om gelijke gevallen consistent te doorbreken. Omdat de schattingen gesynchroniseerd blijven, reduceert het probleem zich effectief tot een single-agent heavy-tailed bandit over de gezamenlijke actieruimte, waarbij geen extra kosten worden gemaakt door actie-asymmetrie.
• Probleem B (mRUCB-Intervals): Met geobserveerde acties maar onafhankelijke beloningen, divergeren de schattingen van spelers. Om miscoördinatie te voorkomen, vervangen de auteurs index-maximalisatie door een round-robin eliminatiestrategie. Spelers onderhouden betrouwbaarheidsintervallen voor elke arm. Als het interval van een speler voor een arm strikt onder dat van een ander ligt, signaleren zij dit door af te wijken van de geplande gezamenlijke actie (door een andere individuele arm te trekken). Omdat acties observeerbaar zijn, fungeert deze afwijking als een 1-bit impliciet communicatiekanaal, waardoor alle spelers de suboptimale arm gelijktijdig elimineren. Signaleringsrondes verwerpen beloningen om statistische uitlijning te behouden.
• Probleem C (mHT-DSEE): In de volledig asymmetrische setting staat noch gedeelde beloningen, noch geobserveerde acties toe voor impliciete signalering of gesynchroniseerde schattingen. De auteurs maken gebruik van een Deterministic Schedule for Exploration and Exploitation (DSEE). Spelers volgen een vooraf overeengekomen cyclisch exploratieschema voor een duur die wordt bepaald door een functie $w(t)$ (bijv. $\lceil \log t \rceil$). Zodra het exploratiebudget is bereikt, schakelen spelers over naar exploitatie op basis van hun eigen RUCB-indices, berekend uitsluitend uit exploratiesamples. Synchronisatie wordt behouden omdat het schema enkel afhangt van de ronde-index $t$.

Belangrijkste Bijdragen en Theoretische Resultaten
De auteurs leiden regret-bounds af die bijna overeenkomen met gecentraliseerde heavy-tailed rates voor elke setting:

• Probleem A: De verwachte regret is $O(\log T \sum \Delta_a^{-1/\epsilon})$. De gedecentraliseerde agenten brengen geen extra kosten met zich mee vergeleken met een gecentraliseerde leerling, aangezien de gedeelde beloning zorgt voor perfecte synchronisatie.
• Probleem B: De regret bound is $O(\log T \sum \Delta_a^{-1/\epsilon})$ plus constante termen onafhankelijk van de horizon $T$. Het mechanisme gebruikt actie-afwijkingen als een impliciet signaleringskanaal; de kosten van signalering zijn begrensd door $(K^M - 1)\Delta_{\max}$, onafhankelijk van $T$ en het aantal spelers $M$.
• Probleem C: De regret bound is $O(K^M \log^2 T)$. Deze setting vereist een vooraf vastgesteld anytime-schema, wat een extra $\log T$ factor introduceert vergeleken met de andere regimes. De auteurs merken op dat deze factor voortkomt uit het gebrek aan gedeelde informatie om de overgang van exploratie naar exploitatie te coördineren.

Experimentele Validatie
Experimenten werden uitgevoerd met $M=2$ spelers, $K=2$ armen per speler en Pareto-verdeelde beloningen (vormparameter 2, wat een eindig gemiddelde maar een oneindige variantie garandeert).

• Resultaten: Alle drie de algoritmen vertoonden sublineaire regret-groei, wat bevestigt dat zij in staat zijn de optimale arm te identificeren onder heavy-tailed ruis.
• Trade-offs: Hoewel mRUCB-A en mHT-DSEE een lagere initiële regret vertoonden, bereikte mRUCB-Intervals (Probleem B) uiteindelijk een regret-groei van nul nadat de actieve set was ingestort, terwijl de anderen bleven exploreren. De experimenten benadrukken dat hoewel de asymptotische rates verschillen, de constanten geassocieerd met de coördinatiemechanismen (bijv. de factor 4 versus 2 in intervalscheiding) de prestaties bij gemiddelde horizonten aanzienlijk beïnvloeden.

Betekenis en Claims
De auteurs claimen dat effectief gedecentraliseerd leren haalbaar is, zelfs onder significante informatie-asymmetrie en niet-sub-Gaussische ruis.

• Gedeelde beloningen maken kostenloze synchronisatie mogelijk.
• Geobserveerde acties bieden een voldoende impliciet signaleringskanaal om het verlies van gedeelde beloningen te compenseren, waarbij de signaleringskosten niet schalen met de horizon of het aantal agenten.
• Volledige asymmetrie vereist een vooraf vastgesteld schema, wat een extra $\log T$ kost, wat de waarde van zelfs minimale observeerbaarheid onderstreept.

Het artikel concludeert dat hoewel de voorgestelde algoritmen robuust zijn, zij de kennis van de tail-parameters $(\epsilon, v)$ veronderstellen. Er wordt gesuggereerd dat toekomstig werk zich moet richten op het adapteren aan onbekende tail-zwaarte en het afleiden van strakkere lower bounds voor het volledig asymmetrische geval.