Cooperative Bandit Learning in Directed Networks with Arm-Access Constraints

Titel: Cooperatief Bandit-Leren in Gerichte Netwerken met Beperkte Toegang tot Acties (Arms)

Auteurs: Evagoras Makridis en Themistoklis Charalambous (Universiteit van Cyprus)
Datum: Preprint, maart 2026

---

1. Probleemstelling

Het paper adresseert het probleem van cooperatief multi-agent multi-armed bandit (MAMAB) leren in omgevingen met twee specifieke beperkingen die vaak voorkomen in realistische systemen (zoals sensornetwerken of robotzwermen):

1. Gerichte en onbalans communicatie: Agents communiceren via een gerichte graaf (digraph) die niet per se symmetrisch is. Dit betekent dat informatie niet gelijkmatig wordt gedeeld; sommige agents hebben meer invloed dan anderen, en standaard consensusmechanismen (die gemiddelden behouden) falen hier vaak.
2. Beperkte toegang tot "arms" (acties): Niet elke agent heeft toegang tot alle mogelijke acties (arms). Elke agent kan slechts een subset van de totale set arms selecteren, afhankelijk van hun lokale capaciteiten, locatie of middelen.

De kernuitdaging:
In eerdere werken werd vaak aangenomen dat elke agent alle arms kan observeren. In dit scenario kan een agent de global optimale arm misschien niet eens direct bereiken. Agents moeten dus samenwerken om informatie over arms die ze zelf niet kunnen "trekken" (pullen) te verzamelen via hun buren. De combinatie van asymmetrische communicatie en heterogene toegang creëert structurele knelpunten voor het leren en vereist nieuwe algoritmen om vertekende schattingen te voorkomen.

---

2. Methodologie: Het A2C-UCB Algoritme

De auteurs stellen A2C-UCB (Arm Access Constrained Cooperative Upper Confidence Bound) voor. Dit is een gedistribueerd algoritme dat de volgende componenten combineert:

A. Massabehoudende Informatiemixing (Ratio Consensus)

Om de bias te compenseren die ontstaat door de gerichte graaf (waarbij agents ongelijk bijdragen aan het globale gemiddelde), gebruiken de auteurs een ratio-consensus mechanisme.

• Elke agent $i$ houdt twee schattingen bij voor elke arm $k$:
  1. $\hat{s}^k_i(t)$: De cumulatieve beloning (som van rewards).
  2. $\hat{n}^k_i(t)$: Het totale aantal keer dat arm $k$ is getrokken door het hele netwerk.
• Agents wisselen deze waarden uit met hun buren, gewogen door hun uitgaande graad ($d_{out}$).
• Door de verhouding $\hat{s}^k_i(t) / \hat{n}^k_i(t)$ te nemen, kunnen agents de ware empirische gemiddelde beloning van het hele netwerk schatten, zelfs als ze de arm zelf nooit hebben getrokken. Dit mechanisme behoudt de totale "massa" van de informatie en zorgt voor een onbevooroordeelde schatting.

B. Gedistribueerde Schatting van Toegankelijkheid

Omdat agents niet weten hoeveel andere agents toegang hebben tot een specifieke arm (de "generatie-massa" $g_k$), moeten ze dit ook schatten.

• Agents gebruiken een extra consensus-loop om de som van de toegankelijkheidsindicatoren ($C_{ik}$) over het netwerk te berekenen.
• Dit stelt elke agent in staat om asymptotisch de exacte waarde van $g_k$ (het aantal agents dat arm $k$ kan bereiken) te schatten.

C. De UCB Index met Netwerkawareness

De beslissing welke arm te kiezen wordt genomen op basis van een aangepaste UCB-index:
$$Q^k_i(t) = \hat{\mu}^k_i(t) + \sqrt{\frac{\alpha \log(t \hat{g}^k_i(t))}{\hat{\nu}^k_i(t)}}$$
Waarbij:

• $\hat{\mu}^k_i(t)$: De geschatte gemiddelde beloning (via ratio consensus).
• $\hat{\nu}^k_i(t)$: De geschatte totale aantallen pulls over het netwerk (correctie voor onbalans).
• $\hat{g}^k_i(t)$: De geschatte "generatie-massa" (aantal agents met toegang).
• Belangrijk: De term $\hat{g}^k_i(t)$ in de teller zorgt ervoor dat arms die door minder agents toegankelijk zijn, meer exploratie krijgen om de langzamere informatieverspreiding te compenseren.

---

3. Belangrijkste Bijdragen

1. Formalisatie van Structurele Beperkingen: Het paper introduceert een model dat zowel de gerichte communicatietopologie als de heterogene arm-toegang combineert. Het onderscheidt tussen "inherent structurele verliezen" (als een agent geen toegang heeft tot de globale optimum) en "leer-regret" (verlies door onzekerheid).
2. Onbevooroordeelde Schatting in Gerichte Netwerken: In tegenstelling tot bestaande methoden die vaak bias introduceren in gerichte netwerken, garandeert het voorgestelde ratio-consensus mechanisme dat de geschatte gemiddelde beloningen onbevooroordeeld zijn en convergeren naar het ware globale gemiddelde.
3. Logaritmische Regret Garantie: De auteurs bewijzen wiskundig dat elk agent een logaritmische regret ($O(\log T)$) bereikt. De regret-grens hangt expliciet af van:
   • De netwerk-mixing eigenschappen (hoe snel informatie verspreidt).
   • De structuur van de arm-toegang (hoeveel agents toegang hebben tot een arm).
4. Robuustheid: Het algoritme werkt zonder centrale coördinatie en vereist alleen lokale communicatie, zelfs als agents niet weten wie hun buren precies zijn of hoeveel toegang ze hebben.

---

4. Resultaten en Simulaties

De auteurs evalueren het algoritme via simulaties in een scenario van edge computing (taakoffloading naar servers):

• Setup: 6 agents met toegang tot een subset van 7 servers (arms). De communicatie is een gerichte graaf.
• Vergelijking 1 (A2C-UCB vs. UCB1 zonder communicatie):
  • Het cooperatieve algoritme (A2C-UCB) toont een significante reductie in cumulatieve regret vergeleken met agents die alleen lokaal leren.
  • Delen van informatie versnelt het identificeren van de beste arm en reduceert redundante exploratie.
• Vergelijking 2 (A2C-UCB vs. Bestaande methoden [17]):
  • Bestaande methoden (zoals die van Zhu et al.) falen of presteren slecht onder arm-toegang beperkingen.
  • A2C-UCB presteert zelfs beter dan bestaande methoden in scenario's waar alle arms toegankelijk zijn, wat aantoont dat het algoritme robuust is voor zowel beperkte als volledige toegang.

---

5. Significatie en Toekomstperspectief

Significatie:
Dit werk is een belangrijke stap in het veld van gedistribueerd leren omdat het de realistische beperkingen van heterogene capaciteiten en asymmetrische netwerken adresseert. Het lost het fundamentele probleem op dat in veel bestaande werken wordt genegeerd: hoe leer je effectief als je niet alle opties kunt zien en de communicatie niet perfect is? De oplossing biedt een theoretisch onderbouwde manier om samenwerking te optimaliseren zonder centrale controle.

Toekomstig Werk:
De auteurs noemen als volgende stappen het uitbreiden van het framework naar:

• Onbetrouwbare of asynchrone communicatie.
• Dynamische netwerken (waarbij connectiviteit verandert).
• Tijdvariërende beschikbaarheid van arms.

Kortom, dit paper biedt een solide theoretisch en praktisch kader voor cooperatief leren in complexe, beperkende omgevingen.