Constant or logarithmic regret in asynchronous multiplayer bandits

Hugo Richard, Etienne Boursier, Vianney Perchet

Abstract

Recent advancements in Multi-Armed Bandit (MAB) theory have addressed the complexities of asynchronous multiplayer environments, a setting common in Internet of Things (IoT) networks. This paper presents a significant improvement over previous $O(T^{2/3})$ regret benchmarks, introducing algorithms that achieve logarithmic—and in specific cases, constant—regret. By utilizing a centralized "Cautious Greedy" approach, we demonstrate that when an optimal strategy utilizes all available arms, the regret remains bounded regardless of the time horizon.

1. Introduction

In the standard multiplayer Multi-Armed Bandit (MAB) framework, multiple agents pull arms to maximize collective rewards while avoiding collisions. A collision occurs when two or more players select the same arm, resulting in zero reward for all involved. While most literature assumes perfect synchronization between players, real-world systems like IoT networks are inherently asynchronous. In these settings, devices activate independently with a certain probability $p$, leading to the Asynchronous Multiplayer Multi-Armed Bandit (AMMAB) problem.

Previous approaches to AMMAB relied on Explore-Then-Commit (ETC) strategies, which are limited by a sub-optimal regret of $O(T^{2/3})$. This research aims to bridge the gap between asynchronous systems and the theoretical gold standard of bandit performance: logarithmic ($O(\log T)$) or constant ($O(1)$) regret.

2. Problem Formulation

The AMMAB model considers $M$ players and $K$ arms. In each round $t$, each player $m$ is active with probability $p$. A central controller assigns active players to arms. If an arm is chosen by exactly one active player, a reward is generated; otherwise (zero players or multiple players), the reward is zero. The goal is to minimize the expected regret, which is the difference between the reward of the optimal static assignment and the reward collected by the algorithm.

3. Proposed Algorithms

3.1 Centralized UCB

The authors first extend the classic Upper Confidence Bound (UCB) algorithm to the centralized asynchronous setting. Centralized UCB maintains confidence intervals for the mean reward of each arm and selects the assignment that maximizes the total expected reward based on these upper bounds. While effective, it serves primarily as a baseline for more specialized strategies.

3.2 Cautious Greedy

The core innovation of this work is the "Cautious Greedy" algorithm. Standard greedy approaches often suffer from premature exploitation, failing to explore arms sufficiently. Cautious Greedy mitigates this by being "cautious" about reducing the number of players assigned to any given arm.

Key features include:

  • Lower Bound Estimation: The algorithm maintains a lower bound on $\nu^*$, the number of arms that should be left empty in an optimal configuration.
  • Round-Robin Rotation: To ensure all active arms are sampled regularly, the algorithm employs a rotation mechanism.
  • Statistical Confidence: Players are only removed from an arm's assignment when the algorithm is statistically confident that the arm is sub-optimal for that player count.

4. Theoretical Results and Key Insights

4.1 The Constant Regret Phenomenon

The most significant theoretical contribution is the identification of the "Constant Regret" regime. If the optimal policy involves assigning at least one player to every available arm ($\nu^* = 0$), Cautious Greedy achieves $O(1)$ regret. This occurs because the algorithm receives information about every arm in every round where players are active, effectively transforming the bandit problem into a supervised learning task where the learner eventually stops making mistakes.

4.2 Logarithmic Regret and Sparsity

When the optimal policy requires leaving some arms empty ($\nu^* > 0$), the regret becomes logarithmic ($O(\log T)$). The challenge in this scenario is the "cost of sparsity": the algorithm must spend time identifying which arms to abandon, and the lack of samples from abandoned arms necessitates a logarithmic exploration rate to ensure they are not actually optimal.

4.3 Scaling with Activation Probability

Interestingly, the regret bounds are robust to the activation probability $p$. While a smaller $p$ means fewer active players, the rewards are also scaled by $p$. The authors prove that the $1/p$ term effectively cancels out, preventing the regret from exploding in low-activity IoT environments.

5. Experimental Validation

The algorithms were evaluated using synthetic data across two primary scenarios:

  1. Scenario 1 ($\nu^* = 0$): All arms are part of the optimal strategy. Cautious Greedy demonstrated clear constant regret, outperforming both UCB and the previous ETC state-of-the-art.
  2. Scenario 2 ($\nu^* = 1$): One arm is sub-optimal and should be left empty. In this case, both Cautious Greedy and UCB achieved logarithmic regret, significantly outperforming the $O(T^{2/3})$ growth of ETC methods.

6. Conclusion and Future Work

This work establishes new performance upper bounds for asynchronous multiplayer bandits, proving that constant regret is achievable under certain conditions. However, several avenues for future research remain:

  • Decentralization: Transitioning from a central controller to a fully decentralized setting where players make independent decisions without communication.
  • Heterogeneity: Addressing cases where players have different activation probabilities ($p_i$).
  • Parameter Estimation: Handling scenarios where the activation probability $p$ is unknown and must be estimated alongside arm means.

Summary updated

BibTeX
@inproceedings{richard2023constant,
  author = {Hugo Richard and Etienne Boursier and Vianney Perchet},
  title = {{Constant or logarithmic regret in asynchronous multiplayer bandits}},
  booktitle = {EWRL16},
  year = {2023},
  url = {https://openreview.net/forum?id=L1mqXwF9vi},
}
Figure