Exploration for Free: How Does Reward Heterogeneity Improve Regret in Cooperative Multi-agent Bandits?

Xuchuang Wang, Lin Yang, Yu-Zhen Janice Chen, Xutong Liu, Mohammad Hajiesmaili, Don Towsley, John C. S. LuiUAI 2023 · OpenReview

Abstract

This paper studies a cooperative multi-agent bandit scenario in which the rewards observed by agents are heterogeneous—one agent’s meat can be another agent’s poison. Specifically, the total reward observed by each agent is the sum of two values: an arm-specific reward, capturing the intrinsic value of the arm, and a privately-known agent-specific reward, which captures the personal preference/limitations of the agent. This heterogeneity in total reward leads to different local optimal arms for agents but creates an opportunity for free exploration in a cooperative setting—an agent can freely explore its local optimal arm with no regret and share this free observation with some other agents who would suffer regrets if they pull this arm since the arm is not optimal for them. We first characterize a regret lower bound that captures free exploration, i.e., arms that can be freely explored have no contribution to the regret lower bound. Then, we present a cooperative bandit algorithm that takes advantage of free exploration and achieves a near-optimal regret upper bound which tightly matches the regret lower bound up to a constant factor. Lastly, we run numerical simulations to compare our algorithm with various baselines without free exploration.

Introduction

In traditional multi-agent multi-armed bandit (MAB) problems, the standard assumption is homogeneity: all agents receive the same reward from the same arm. However, real-world scenarios—from personalized ad recommendations to distributed computing—are defined by heterogeneity. One user's preferred content might be irrelevant to another. This paper introduces the Multi-agent Multi-armed Bandits with Heterogeneous Rewards (MA2B-HR) framework to address these disparities.

Problem Formulation

The core challenge in MA2B-HR is that an arm optimal for Agent A might be suboptimal for Agent B. In a cooperative setting, if Agent B pulls an arm simply to learn about its intrinsic value, they suffer "regret" (the opportunity cost relative to their own optimal arm).

An example of reward heterogeneity across agents and arms, illustrating how preferences and constraints differ.

The authors model rewards as a decomposition of an arm-specific intrinsic value and a private agent-specific preference. This structure allows for the concept of "free exploration": if an agent pulls their own optimal arm, they generate data about that arm's intrinsic value without incurring any regret.

Methodology: The FreeExp Algorithm

The authors propose FreeExp, an algorithm designed to exploit these "free" observations. FreeExp relies on three main pillars:

  1. Pivot Arms: Each agent identifies a "pivot"—their current estimate of their local optimal arm.
  2. Filtered Exploration: Agents use a KL-UCB (Kullback–Leibler Upper Confidence Bound) index to decide which arms to explore but explicitly skip any arm that is currently being exploited as a "pivot" by another agent.
  3. Cooperative Information Sharing: Agents broadcast their observations of intrinsic arm values. Because pivots are pulled frequently during exploitation, the group receives a steady stream of "free" data.

Theoretical Insights and Results

The most striking finding is the "Breaking of the Logarithmic Barrier." In standard bandit theory, regret typically grows logarithmically ($O(\log T)$) over time. In the MA2B-HR setting, if every arm in the system is the favorite of at least one agent, the total group regret becomes a constant $O(1)$. This means that after an initial learning phase, the group incurs no further cumulative regret.

Comparison of regret bounds for various algorithms, highlighting FreeExp's achievement of O(1) regret.

The authors derived a regret lower bound specifically for this heterogeneous setting and proved that FreeExp matches this bound up to a constant factor.

Experimental Evaluation

To validate these theoretical claims, the researchers used both synthetic data and real-world click-through rates from Kaggle’s 2015 Avito Ad-Click Dataset:

  • Performance: FreeExp significantly outperformed baselines like CO-UCB, which do not account for free exploration.
  • Diversity Impact: Experiments confirmed that regret drops as the number of "free arms" (arms that are someone's favorite) increases. When all arms were covered by at least one agent's preference, the regret curve flattened to a constant, confirming the $O(1)$ theory.

Conclusion and Future Work

This research demonstrates that reward heterogeneity, often viewed as a complication, can actually be a powerful asset for cooperative learning. By leveraging the diverse preferences of agents, groups can achieve "exploration for free."

Future work includes addressing the communication overhead of broadcasting every observation, handling dynamic preferences that shift over time, and ensuring the privacy of agent-specific preferences against potential adversaries.

Summary updated

Abstract

This paper studies a cooperative multi-agent bandit scenario in which the rewards observed by agents are heterogeneous—one agent’s meat can be another agent’s poison. Specifically, the total reward observed by each agent is the sum of two values: an arm-specific reward, capturing the intrinsic value of the arm, and a privately-known agent-specific reward, which captures the personal preference/limitations of the agent. This heterogeneity in total reward leads to different local optimal arms for agents but creates an opportunity for \textit{free exploration} in a cooperative setting—an agent can freely explore its local optimal arm with no regret and share this free observation with some other agents who would suffer regrets if they pull this arm since the arm is not optimal for them. We first characterize a regret lower bound that captures free exploration, i.e., arms that can be freely explored have no contribution to the regret lower bound. Then, we present a cooperative bandit algorithm that takes advantage of free exploration and achieves a near-optimal regret upper bound which tightly matches the regret lower bound up to a constant factor. Lastly, we run numerical simulations to compare our algorithm with various baselines without free exploration.
BibTeX
@inproceedings{wang2023exploration,
  author = {Xuchuang Wang and Lin Yang and Yu-Zhen Janice Chen and Xutong Liu and Mohammad Hajiesmaili and Don Towsley and John C. S. Lui},
  title = {{Exploration for Free: How Does Reward Heterogeneity Improve Regret in Cooperative Multi-agent Bandits?}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2023},
  url = {https://openreview.net/forum?id=H5WrxxMyPU},
}
Figure