Imitation Upper Confidence Bound for Bandits on a Graph

Andrei Lupu, Doina PrecupAAAI 2018 · OpenReview

Abstract

We consider a graph of interconnected agents implementing a common policy and each playing a bandit problem with identical reward distributions. We restrict the information propagated in the graph such that agents can uniquely observe each other's actions. We propose an extension of the Upper Confidence Bound (UCB) algorithm to this setting and empirically demonstrate that our solution improves the performance over UCB according to multiple metrics and within various graph configurations.

Introduction

The classic Multi-Armed Bandit (MAB) problem requires an agent to maximize rewards by balancing exploration and exploitation. While traditional models focus on isolated agents, real-world scenarios—such as social media influence or financial trading—are inherently social. In these contexts, agents often observe the actions of their peers without having access to their specific reward outcomes. This paper investigates the "multi-agent bandit problem on a graph," where agents are blind to their neighbors' payouts but can observe their choices. We introduce the Imitation Upper Confidence Bound (IUCB) algorithm to leverage this limited social information for improved collective learning.

The IUCB Algorithm

IUCB extends the standard UCB algorithm by incorporating a social component into the decision-making process. The algorithm operates on two primary pillars:

  1. Individual Component: Each agent maintains a personal UCB score for every arm based on their own reward history.
  2. Social Component: Agents track a "popularity" score ($P_i^k$) for each arm, representing the frequency with which neighbors selected that arm over the preceding 10 time steps.

At each time step, an agent chooses between individual exploration and social imitation based on an "imitation frequency" parameter, $\alpha$. With probability $1-\alpha$, the agent follows the standard UCB rule. With probability $\alpha$, the agent imitates the most popular action currently observed in its neighborhood. This hybrid strategy allows agents to "crowdsource" exploration, effectively filtering promising arms through the collective experience of the group.

Experimental Results

The performance of IUCB was evaluated using a 10-armed Gaussian bandit task across several graph topologies, including Chain, Loop, Clique, Erdős-Rényi (random), and Barabási-Albert (small-world) networks.

Comparison of cumulated regret between IUCB across various graph topologies and the single-agent UCB baseline.

Empirical results demonstrate that IUCB significantly outperforms the single-agent UCB baseline. As shown in Figure 1, the IUCB algorithm accumulates approximately half the total regret of the vanilla UCB algorithm across all tested graph sizes. The benefit of imitation scales non-linearly with graph size, particularly in random and small-world networks. Interestingly, the study revealed a "density paradox": agents in highly connected cliques sometimes converged too quickly on sub-optimal actions due to information redundancy. In contrast, sparser structures like the Barabási-Albert model allowed for more diverse exploration, leading to higher efficiency in spreading the optimal strategy.

Analysis of Social Dynamics

A key finding of this research is the temporal nature of the imitation benefit. The advantage gained from observing neighbors is not constant; rather, it is most pronounced during the early stages of the learning process.

Imitation benefit over time for different graph configurations.

As illustrated in Figure 3, the "imitation benefit" peaks early as agents borrow the exploration efforts of their peers to quickly identify high-performing arms. However, as time progresses and agents accumulate sufficient personal data to identify the optimal arm independently, the relative benefit of social imitation drops toward zero. This suggests that imitation acts as an informed exploration filter that accelerates the initial discovery phase.

Conclusion

IUCB provides a robust framework for multi-agent learning on graphs, demonstrating that even limited social information (actions without rewards) can drastically reduce regret. While the empirical evidence is strong, providing formal theoretical regret bounds for IUCB remains an open challenge. Future research may explore adaptive imitation frequencies—where agents rely less on neighbors as their own experience grows—and the performance of IUCB in non-stationary reward environments.

Summary updated

Abstract

We consider a graph of interconnected agents implementing a common policy and each playing a bandit problem with identical reward distributions. We restrict the information propagated in the graph such that agents can uniquely observe each other's actions. We propose an extension of the Upper Confidence Bound (UCB) algorithm to this setting and empirically demonstrate that our solution improves the performance over UCB according to multiple metrics and within various graph configurations.
BibTeX
@inproceedings{lupu2018imitation,
  author = {Andrei Lupu and Doina Precup},
  title = {{Imitation Upper Confidence Bound for Bandits on a Graph}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=S1Wh8Te_Wr},
}
Figure