Collaborative Bandits: Why Your Social Network Needs a Leader to Learn Better

TL;DR

In a networked world, we often assume that "more information is always better." However, in the context of Multi-Armed Bandits (MAB), this paper proves that simply sharing rewards among neighbors isn't enough. In fact, standard "rational" strategies like UCB1 can lead to unexpectedly high regret in hierarchical networks. The authors propose a Follow Your Leader (FYL) strategy that leverages the graph's structure (Dominating Sets) to achieve a massive $m$-fold improvement in learning efficiency.

The "Selfish Agent" Problem in Networks

In a typical MAB scenario, an agent tries to minimize "regret"—the difference between the rewards they got and the rewards they could have gotten by picking the best possible "arm."

When you put these agents in a network, they gain "side observations" from their neighbors. You would expect the group to learn faster. But the authors identify a fatal flaw in a class of policies they call Non-Altruistic and Individually Consistent (NAIC). In these policies:

• Selfishness: Once an agent (like a hub in a star network) determines an arm is sub-optimal, it stops pulling it.
• Information Starvation: Because the hub stops pulling the bad arm, its neighbors (the "leaf" nodes) stop receiving data about that arm. They are forced to explore the sub-optimal arm themselves to satisfy their own "confidence bounds," leading to redundant mistakes across the network.

Methodology: The Power of Hierarchy

The core insight of the paper is that to optimize the network's total regret, some nodes must act as "explorers" for the sake of the collective.

1. The UCB-Network Baseline

The authors first analyze a natural extension of UCB1 where agents incorporate neighborhood data. They provide a graph-dependent upper bound on regret, showing that in a star network, the regret scales as $O((m-1)\ln n)$.

2. Follow Your Leader (FYL)

To break the NAIC inefficiency, they propose the FYL policy based on the Dominating Set of the graph.

• Leaders: A small subset of nodes (the dominating set) that are adjacent to everyone else. They perform the "heavy lifting" of exploration using a UCB-style policy.
• Followers: These nodes simply copy the leader's action from the previous round.

Fig 1: Typical network topologies studied: Fully Connected, Circular, Star, and Fully Disconnected.

Experimental Proof: Star Networks as the Ultimate Litmus Test

The paper places a particular focus on Star Networks because they are common in real-world social hierarchies and represent the extreme case of the "information hub" bottleneck.

Key Result:

In a star network with $m$ nodes:

• NAIC Policies: Regret grows with $m$ because every leaf node eventually has to pull the bad arm to "be sure" it's bad.
• FYL Policy: Regret is independent of $m$ (asymptotically). Since the leader (the hub) does all the testing, the $m-1$ followers transition to the optimal arm the moment the leader does.

Fig 2: Comparing UCB-Network (High Regret) vs. FYL (Low Regret) in star networks. The FYL strategy clearly optimizes the group much faster.

Critical Insight: The Price of Individual Consistency

The mathematical beauty of this paper lies in the "Lower Bound" analysis. The authors prove that the Universal Lower Bound for network regret is $O(\ln n)$. However, if you restrict agents to being "individually consistent" (meaning they must optimize their own personal reward), the regret must be at least $O(m\ln n)$ in certain graphs.

By asking followers to be "inconsistent" (i.e., trust the leader even when their own local data is sparse), the FYL policy bypasses this lower bound, effectively "hacking" the statistical limits of decentralized learning.

Conclusion & Future Outlook

This work provides a bridge between Social Network Theory and Online Learning. It tells us that in distributed recommendation systems or traffic routing (like Waze), "blindly" following an influential "leader" node can actually be mathematically optimal for the community, provided that leader is strategically chosen (i.e., part of the minimum dominating set).

Future Directions:

• How do we handle dynamic networks where connections appear and disappear?
• What happens if the leader is malicious or the rewards are non-stationary?

The FYL policy proves that in the world of bandits, sometimes it pays to be a follower.