Multi-player Multi-armed Bandits with Delayed Feedback

Jingqi Fan, Zilong Wang, Shuai Li, Linghe Kong

Introduction

In decentralized Multi-player Multi-armed Bandit (MP-MAB) systems, multiple autonomous agents (players) compete for a set of resources (arms) to maximize their collective rewards. A critical constraint in these systems, common in cognitive radio networks, is that simultaneous access to the same arm results in a collision, yielding zero reward for all involved.

Effective coordination usually requires immediate feedback to signal arm availability. However, real-world systems suffer from sensing latency and signal processing delays. When feedback is delayed, players may act on stale information, leading to catastrophic collision rates and exploration inefficiency. This paper introduces Delayed Decentralized Successive Elimination (DDSE), a novel algorithm designed to maintain player synchronization and near-optimal performance despite stochastic feedback delays.

The DDSE Algorithm

DDSE addresses the latency problem by prioritizing consistency over recency. The algorithm structures player behavior into three distinct phases:

  1. Exploration Phase: Players are assigned unique IDs. The player with the highest ID acts as a leader, performing round-robin exploration of all arms to maintain confidence bounds and eliminate sub-optimal choices.
  2. Communication Phase: The leader communicates changes in the "top-M" optimal arms to followers via intentional collisions. To mitigate delay, DDSE uses a delay-aware coordination mechanism. Players estimate the delay distribution (assuming it is sub-Gaussian) and synchronize based on a delay quantile. This ensures that all players transition to new arm sets only when there is a high probability that everyone has received the necessary updates.
  3. Exploitation Phase: Once synchronized, players pull the identified optimal arms exclusively, minimizing further interference.

By fixing the start times of communication phases rather than allowing them to trigger dynamically, DDSE avoids the timing errors that typically break implicit communication in delayed environments.

Experimental Setup

The researchers validated DDSE using both synthetic and empirical data:

  • Synthetic Datasets: Bernoulli and Gaussian rewards were tested under various stochastic delay parameters to establish theoretical performance limits.
  • Real-World Spectrum Data: The team utilized power measurements from the 5G-Xcast project in Finland. This dataset represents actual paging frequency bands, providing a realistic environment for testing secondary user spectrum access without primary user interference.

Performance Analysis

Throughput Efficiency

DDSE demonstrates superior cumulative throughput compared to standard decentralized baselines. By ensuring that players do not prematurely switch arms based on incomplete or misaligned data, the algorithm maintains a steady reward growth rate that approaches centralized (ideal) performance.

Cumulative throughput over time for various algorithms. DDSE and DSE show the highest growth.

Collision Avoidance

The primary advantage of DDSE is its ability to suppress collisions. While naive decentralized approaches like SIC-MMAB or "Selfish" strategies experience spikes in collisions as they struggle to synchronize under latency, DDSE's delay-aware buffer keeps players from interfering with one another. Even compared to its predecessor, DSE, DDSE shows improved stability in the long term.

Cumulative collisions over time. DDSE maintains significantly lower collision rates than baseline decentralized methods.

Key Insights and Theoretical Bounds

  • The Exponential Trap: The authors prove that simpler algorithms (like DSE) can suffer from regret that grows exponentially with expected delay. DDSE avoids this by using estimated delay quantiles to create a safety buffer for coordination.
  • Near-Optimality: The regret upper bound for DDSE is shown to be $O(\frac{1}{1-M/K}\sqrt{\log K})$. This indicates that the performance gap between decentralized systems with delay and centralized systems without delay is manageable and scales well with the number of arms ($K$) and players ($M$).

Limitations and Future Work

While DDSE is robust, it currently relies on the assumption that delays follow a sub-Gaussian distribution. Future research could explore distribution-free quantile approaches to handle "heavy-tailed" delays. Additionally, the current model assumes homogeneous players (all players see the same rewards) and a fixed number of players. Extending DDSE to heterogeneous rewards and dynamic environments where players join or leave remains an open challenge.

Summary updated

Abstract

Multi-player multi-armed bandits have been researched for a long time due to their application in cognitive radio networks. In this setting, multiple players select arms at each time and instantly receive the feedback. Most research on this problem focuses on the content of the immediate feedback, whether it includes both the reward and collision information or the reward alone. However, delay is common in cognitive networks when users perform spectrum sensing. In this paper, we design an algorithm DDSE (Decentralized Delayed Successive Elimination) in multi-player multi-armed bandits with stochastic delay feedback and establish a regret bound. Compared with existing algorithms that fail to address this problem, our algorithm enables players to adapt to delayed feedback and avoid collision. We also derive a lower bound in centralized setting to prove the algorithm achieves near-optimal. Numerical experiments on both synthetic and real-world datasets validate the effectiveness of our algorithm.
BibTeX
@inproceedings{fan2025multi,
  author = {Jingqi Fan and Zilong Wang and Shuai Li and Linghe Kong},
  title = {{Multi-player Multi-armed Bandits with Delayed Feedback}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/564},
}
Figure