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:
- 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.
- 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.
- 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.
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.
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