⚡ electrical engineering

Cooperative Bandit Learning in Directed Networks with Arm-Access Constraints

This paper proposes a distributed consensus-based UCB algorithm for multi-agent multi-armed bandit problems in directed networks with heterogeneous arm access, proving that a mass-preserving information mixing mechanism achieves logarithmic regret for all agents despite asymmetric communication and partial arm availability.

Original authors: Evagoras Makridis, Themistoklis Charalambous

Published 2026-03-25

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Evagoras Makridis, Themistoklis Charalambous

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to find the best restaurant in a huge city, but they have some very specific rules and limitations. This is the core story of the paper you shared, which deals with a problem called Cooperative Bandit Learning.

Here is the breakdown using simple analogies:

1. The Setting: The "Restaurant Hunt"

In the world of computer science, this is called a Multi-Armed Bandit problem.

The Arms: Think of these as different slot machines or, in our analogy, different restaurants.
The Goal: You want to find the one restaurant that serves the best food (highest reward) so you can eat there every day.
The Problem: You don't know which one is the best at the start. You have to try them out (explore) to learn, but you also want to eat at the good ones you've already found (exploit). If you keep trying bad restaurants, you get "regret" (you wasted time and money).

2. The Twist: The "Specialized Friends"

In most old studies, everyone in the group could visit any restaurant in the city. But in the real world, that's not true.

Arm-Access Constraints: Imagine your group of friends is scattered across the city.
- Alice only lives near the Italian district, so she can only visit Italian restaurants.
- Bob only has a bike, so he can only reach the cafes within 2 miles.
- Charlie has a car but is allergic to seafood, so he can't go to the fish places.
The Challenge: No single person can visit every restaurant. If Alice never visits the best sushi place, she will never know it's the best. She needs help.

3. The Complication: The "One-Way Street" Network

Now, imagine these friends communicate via a weird messaging app.

Directed Graphs: Some friends can text others, but those others can't text back.
- Alice can text Bob.
- Bob can text Charlie.
- But Charlie cannot text Alice.
The Problem: Information flows one way. If Charlie finds a great sushi place, he tells Bob, who tells Alice. But if Alice finds a great pizza place, Bob knows, but Charlie never hears about it because the message can't go backward. This creates "traffic jams" in information.

4. The Solution: The "Smart Group Chat" (A2C-UCB)

The authors of this paper invented a new way for these friends to cooperate, called A2C-UCB. Here is how it works in plain English:

A. The "Mass-Preserving" Messenger
Usually, when people share info in a one-way street, the message gets distorted. If Bob talks to 10 people, his opinion gets diluted.

The Fix: The authors created a special "messenger protocol." It's like a game of "pass the parcel" where the parcel never loses its weight. Even if the message goes through many people and only one-way streets, the math ensures that the final group average is perfectly accurate. It doesn't matter who talks to whom; the group eventually agrees on the true average quality of every restaurant, even the ones a specific person has never visited.

B. The "Confidence Score"
When deciding which restaurant to pick, the algorithm uses a "Confidence Score."

If a restaurant is popular and many people have tried it, the score is high (we are sure it's good).
If a restaurant is only accessible to one person (like the sushi place only Charlie can reach), the algorithm gives it a bonus. It says, "Hey, we haven't tried this enough yet because it's hard to reach. Let's explore it more!"
This prevents the group from ignoring the "hard-to-reach" best restaurants just because they are difficult to access.

5. The Result: Why It Matters

The paper proves two main things:

It Works: Even with one-way communication and restricted access, the group learns the best options much faster than if they were working alone.
It's Fair: The "regret" (the time wasted eating bad food) grows very slowly (logarithmically). This means that as time goes on, the group gets incredibly efficient at finding the best spots, almost as if they had a central brain, even though they are all separate individuals.

The Big Picture Metaphor

Imagine a team of detectives solving a mystery.

Old Way: Each detective works alone. If Detective A can only look at the kitchen and Detective B can only look at the bedroom, they might miss the clue in the hallway that solves the case.
New Way (This Paper): They share their notes. But because Detective A can't talk to Detective C directly, they have to pass notes through Detective B. The new algorithm ensures that even with these messy, one-way note-passing rules, the final "case file" held by every detective is 100% accurate. They solve the mystery faster, together, than they ever could alone.

In summary: This paper teaches computers how to work together efficiently even when they have limited tools and can only talk to each other in a messy, one-way direction. It ensures that no matter who can see what, the whole group learns the truth.

1. Problem Statement

The paper addresses the Multi-Agent Multi-Armed Bandit (MAMAB) problem under two specific, realistic constraints that are often ignored in classical literature:

Directed Communication Networks: Agents communicate over a directed graph (digraph) which may be unbalanced. This creates asymmetric information flow, meaning standard averaging consensus mechanisms fail to preserve global statistics or converge to the true mean without bias.
Heterogeneous Arm-Access Constraints: Agents do not have access to all available arms. Each agent $i$ can only pull a specific subset of arms $K_i \subseteq K$ . Consequently, no single agent may have access to the globally optimal arm, and the rate of learning for a specific arm depends on the "generation mass" (the number of agents capable of sampling that arm).

Objective: The goal is to minimize the cumulative pseudo-regret for each agent. Crucially, the regret is defined relative to the agent's best accessible arm ( $\mu_i^*$ ), not the global optimum, because the global optimum may be physically inaccessible to certain agents. The paper distinguishes between "constraint-induced loss" (unavoidable linear regret due to inaccessibility) and "learnable regret" (sublinear regret due to learning dynamics).

2. Methodology: A2C-UCB Algorithm

The authors propose A2C-UCB (Arm Access Constrained Cooperative Upper Confidence Bound), a distributed algorithm that combines Ratio Consensus with UCB exploration.

Key Mechanisms:

Mass-Preserving Information Mixing:
To handle directed and unbalanced graphs, the algorithm uses a running ratio consensus approach. Instead of simple averaging (which biases estimates in directed graphs), agents maintain two running sums for each arm $k$ :
1. $\hat{s}_i^k(t)$ : Cumulative reward estimate.
2. $\hat{n}_i^k(t)$ : Cumulative pull count estimate.
  These are updated using column-stochastic weights based on out-degrees. Agents compute the ratio $\hat{\mu}_i^k(t) = \hat{s}_i^k(t) / \hat{n}_i^k(t)$ to obtain an unbiased estimate of the network-wide empirical mean, even if they cannot pull that arm themselves.
Distributed Estimation of Structural Parameters:
Since agents do not know the global topology or which agents can access which arms, they must estimate two critical quantities locally:
1. Global Pull Count ( $\hat{\nu}_i^k(t)$ ): The total number of times arm $k$ has been pulled across the network.
2. Generation Mass ( $\hat{g}_i^k(t)$ ): The number of agents capable of accessing arm $k$ .
  The algorithm employs auxiliary variables ( $\hat{y}_i(t)$ and $\hat{u}_i^k(t)$ ) updated via consensus. By taking ratios (e.g., $\hat{n}_i^k(t) / \hat{y}_i(t)$ ), agents cancel out the stationary distribution bias caused by the directed graph, allowing them to asymptotically track the true global averages.
Network-Aware UCB Index:
The decision policy uses a modified UCB index:
$Q_i^k(t) = \hat{\mu}_i^k(t) + \sqrt{\frac{\alpha \log(t \hat{g}_i^k(t))}{\hat{\nu}_i^k(t)}}$
- The denominator $\hat{\nu}_i^k(t)$ reflects the effective global sample size.
- The term $\hat{g}_i^k(t)$ in the logarithm acts as a correction factor: if an arm is accessible to few agents (low generation mass), the exploration bonus is increased to compensate for slower information propagation.

3. Key Contributions

Formal Characterization of Structural Limits: The paper introduces the concept of "generation mass" and formally separates the regret into unavoidable structural loss (due to inaccessibility) and learnable regret. It proves that learning speed is fundamentally tied to the intersection of network topology and arm-accessibility constraints.
Unbiased Distributed Estimation: Unlike previous works that use row-stochastic mixing (which introduces bias in directed graphs) or assume full arm access, this work utilizes a sum-preserving ratio consensus. This ensures that reward estimates remain unbiased across the network despite asymmetric communication and heterogeneous access.
Logarithmic Regret Guarantee: The authors prove that under standard stochastic assumptions, the proposed algorithm achieves logarithmic regret ( $O(\log T)$ $O (lo g T)$ ) for every agent. The regret bound explicitly depends on:
- The suboptimality gap of accessible arms.
- The network mixing properties (spectral gap of the consensus matrix).
- The arm accessibility structure (generation mass).

4. Results

Theoretical Analysis:
- Lemma 1 & 2: Establish that the running ratio consensus tracks the true network-wide statistics with bounded error, even in directed graphs.
- Theorem 1: Proves that the expected regret for each agent is bounded by a term scaling with $\log T$ , plus a constant term dependent on network topology and accessibility constraints.
Simulation:
- Scenario: A network of 6 edge devices with limited access to 7 servers (arms).
- Comparison 1 (vs. Non-Cooperative): A2C-UCB significantly outperforms independent UCB1 agents. Cooperation allows agents to learn about arms they cannot pull directly, drastically reducing cumulative regret.
- Comparison 2 (vs. State-of-the-Art): Compared to a cooperative algorithm by Zhu et al. [17] (which assumes full arm access), A2C-UCB performs better even in full-access scenarios and is the only method capable of operating under partial access constraints.

5. Significance

This work bridges a critical gap in cooperative learning theory by addressing the coupling between network topology and action space constraints.

Realism: It moves beyond the idealized assumption that all agents can observe all arms and communicate symmetrically, which is rarely true in sensor networks, IoT, and distributed robotics.
Robustness: The mass-preserving mechanism ensures that the system remains stable and unbiased even when information flow is highly asymmetric.
Scalability: The algorithm is fully distributed, requiring only local communication and knowledge of local out-degrees, making it suitable for large-scale networks where global coordination is impossible.

In summary, the paper provides a rigorous framework for cooperative learning in constrained, directed environments, proving that agents can achieve optimal learning rates despite having incomplete local views of both the network and the available actions.