Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

Sacha Arroues-Paykin, Etienne Boursier, Vianney PerchetarXiv 2026 · arXiv

TL;DR

This paper investigates the challenge of allocating heterogeneous, intermittently active players to communication channels in a multi-player bandit setting. The authors prove that finding the optimal allocation is NP-hard, but demonstrate that a simple greedy algorithm provides a robust $1/e$ approximation, which improves to $1/\sqrt{e}$ when players are sorted by their activity levels.

What Problem Does This Paper Address?

The paper focuses on Asynchronous Multi-player Multi-armed Bandits (AMMAB). Imagine a network of IoT devices (players) trying to transmit data over several radio frequencies (arms). In a realistic setting:

  1. Asynchronicity: Devices aren't always "on." Each device $i$ has a probability $p_i$ of being active at any given time.
  2. Heterogeneity: Different devices have different activity levels (different $p_i$ values).
  3. Collisions: If two or more active devices pick the same frequency, they collide, and no data is transmitted (zero reward).

The goal is to find a centralized allocation—assigning players to arms—that maximizes the total expected reward. While this is easy when all players have the same activity level (homogeneous), it becomes a significant optimization challenge when they differ. The authors aim to determine the computational complexity of this problem and find efficient ways to approximate the best possible outcome.

Methods

The authors employ a mix of computational complexity theory and approximation analysis:

  • Complexity Analysis: They prove the allocation problem is NP-hard by using a reduction from the 3-partition problem. This shows that as the number of devices and channels grows, finding the perfect allocation becomes computationally intractable.
  • Greedy Algorithms: They analyze two versions of a greedy approach:
  • Standard Greedy: Processes players in any arbitrary order and assigns each to the arm that offers the highest marginal increase in expected reward.
  • DORG (Descending-Order Reward Greedy): A specific variant that processes players in decreasing order of their activation probabilities ($p_i$).
  • Matroid Theory: The authors frame the problem as maximizing a set function over a partition matroid (a mathematical structure that models constraints like "each player can only be assigned to one arm").
  • Game Theory: They analyze the Price of Anarchy (PoA) to understand how much total reward is lost when players act selfishly (decentralized) rather than following a central controller.

Datasets

This is a purely theoretical paper; no empirical datasets or benchmarks were used. The results are established through mathematical proofs, including a reduction from a known NP-complete problem and the derivation of approximation bounds.

Key Insights and Ideas

  • Non-Submodularity: Most resource allocation problems are "submodular" (showing diminishing returns). However, the authors point out that this problem is non-monotone and non-submodular. Adding a player to an arm can actually decrease the total reward because it increases the chance of a collision. This makes standard optimization tools fail and necessitates custom proofs.
  • The $1/e$ Barrier: The authors prove that the greedy algorithm achieves at least a $1/e$ ($\approx 36.8\%$) approximation of the optimal payout, regardless of the player order. They also show this bound is "tight"—meaning there are cases where greedy performs exactly this poorly.
  • Sorting Matters: By simply sorting players from most active to least active (DORG), the guarantee jumps to $1/\sqrt{e}$ ($\approx 60.6\%$). This suggests that prioritizing high-activity devices is a powerful heuristic.
  • Price of Anarchy Risks: In a decentralized setting where players choose arms selfishly to maximize their own reward, the total system performance can be "arbitrarily bad" (unbounded PoA) if one arm is significantly better than others, leading to massive congestion and collisions.

Key Results

  • NP-Hardness: Formally established that the heterogeneous AMMAB allocation problem cannot be solved optimally in polynomial time (unless P=NP).
  • Approximation Bounds:
    • Greedy Algorithm: $1/e$-approximation (Theorem 2).
  • DORG Algorithm: $1/\sqrt{e}$-approximation (Theorem 3).
  • Decentralized Bounds: While the Price of Anarchy is unbounded in general, the authors provide a specific bound (Theorem 4) for cases where arm rewards are relatively similar and the network is not overly saturated.

Limitations and Future Work

  • Tightness of DORG: The authors suspect that their $1/\sqrt{e}$ bound for the DORG algorithm might be conservative and that a more refined analysis could prove it performs even better in practice.
  • Online Decentralized Learning: This paper primarily looks at the "offline" case where device probabilities and arm rewards are known. The "online" version—where players must learn these values while competing—remains a major open challenge, especially without a central controller to coordinate them.
  • Communication Protocols: In asynchronous settings, devices can't easily use collisions to "talk" to each other (a common trick in standard bandit problems). Developing efficient communication protocols for heterogeneous, asynchronous devices is a key next step.

Summary updated

Abstract

Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a $\frac{1}{e}$-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to $\frac{1}{\sqrt{e}}$. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.
BibTeX
@misc{arrouespaykin2026approximating,
  author = {Sacha Arroues-Paykin and Etienne Boursier and Vianney Perchet},
  title = {{Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits}},
  year = {2026},
  eprint = {2610.18514},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.18514},
}
Figure