Distributed Multi-Player Bandits - a Game of Thrones Approach

Ilai Bistritz, Amir Leshem

In the world of online learning, the Multi-Armed Bandit (MAB) problem is the classic framework for the exploration-exploitation tradeoff. But what happens when you have multiple players competing for the same resources (arms), each with different preferences, and—crucially—they aren't allowed to talk to each other or even see what the others are doing?

In their paper, "Game of Thrones: Fully Distributed Learning for Multi-Player Bandits," Ilai Bistritz and Amir Leshem introduce a novel algorithm that allows a decentralized system to converge to a globally optimal assignment with near-optimal efficiency.

TL;DR

The authors present the first "fully distributed" algorithm for multi-player bandits where players have heterogeneous rewards and cannot communicate or observe each other's actions. By using a "Game of Thrones" (GoT) dynamic based on perturbed Markov chains, they achieve a near-optimal expected total regret of $O(\log^{1+\delta} T)$.

What Problem Does This Paper Address?

Most multi-player bandit research assumes one of two things: either all players see the same rewards for the same arms (homogeneous), or players can communicate (or at least observe each other's moves) to coordinate.

In real-world scenarios like wireless networking, these assumptions fail. Different users (players) experience different channel qualities (arms) based on their physical location. Furthermore, coordination is expensive; a "fully distributed" system where players only know their own history of actions and rewards is much more robust but significantly harder to optimize.

The core challenge is the Assignment Problem: how do we match $N$ players to $M$ arms such that the total reward is maximized, given that if two players pick the same arm, they both get zero reward (a collision)?

Methods

The authors propose the Game of Thrones (GoT) Algorithm, which operates in increasing time blocks called epochs.

Epoch structure of the GoT algorithm showing Exploration, GoT, and Exploitation phases.

As illustrated above, each epoch $k$ consists of three distinct phases whose lengths scale differently over time:

  1. Exploration Phase ($c_1 k^\delta$): Players pick arms uniformly at random to build an estimate of the expected rewards ($\mu_{n,i}$) for each arm.
  2. GoT Phase ($c_2 k^\delta$): This is the heart of the paper. Players treat their reward estimates as fixed utilities and play a decentralized game. They use payoff-based dynamics where each player is either "Content" or "Discontent":
  3. Content players mostly stick to their "baseline" action.
  4. Discontent players explore arms randomly.
  5. Transitions between these states are governed by the rewards received. The authors modified standard dynamics to work even when the game is "non-interdependent" (i.e., when players on different arms don't directly affect each other's payoffs).
  6. Exploitation Phase ($c_3 2^k$): Players play the arm that was most successful during the recent GoT phases. Notice that this phase grows exponentially, allowing the system to heavily exploit the learned optimal assignment over time.

The "Game of Thrones" name stems from the idea that players are competing for the "throne"—the unique optimal assignment that maximizes the sum of rewards.

Evaluation and Datasets

As a theoretical paper in reinforcement learning and information theory, it does not use standard vision or NLP datasets. Instead, the authors evaluate the algorithm using numerical simulations:

  • Synthetic Reward Matrices: $N \times M$ matrices (e.g., $3 \times 3$ or $5 \times 5$) where mean rewards are randomly generated.
  • Stochastic Noise: Instantaneous rewards are generated using Gaussian distributions or Markovian processes to test the algorithm's robustness against noise and temporal correlation.

Key Insights and Ideas

  • The Power of Discontent: The algorithm uses a "social" dynamic where the only stable state for the entire system is the global optimum. If the system is in a sub-optimal state, at least one player will eventually become "discontent" and trigger a search for a better configuration.
  • Overcoming the Interdependence Gap: Previous payoff-based dynamics required that any group of players could be influenced by someone outside that group. In a collision-based bandit model, this isn't true (if you are on a clear arm, a collision elsewhere doesn't affect you). The authors' modified transition rules solve this by ensuring that only the optimal matching is stochastically stable.
  • Near-Optimal Regret: They prove that the total regret (the reward lost compared to a perfect centralized controller) grows at a rate of $O(\log^{1+\delta} T)$. This is very close to the theoretical lower bound of $\Omega(\log T)$ for single-player bandits, meaning the lack of communication doesn't fundamentally ruin efficiency in the long run.

Key Results

  • Theoretical Guarantee: The paper provides a formal proof that the GoT algorithm achieves near-optimal regret in a fully distributed, heterogeneous setting—a first for the field.
  • Simulation Performance: In tests with 3 and 5 players, the algorithm converged to the optimal assignment quickly. The regret curves followed the predicted logarithmic growth, significantly outperforming random selection.
  • Robustness to $\epsilon$: The algorithm is not overly sensitive to the exploration parameter ($\epsilon$). It performs well across several orders of magnitude, making it practical for real-world tuning.

Limitations and Future Work

  • Convergence Speed vs. Scale: While the regret is logarithmic in time ($T$), the "mixing time" (how long it takes to find the optimum) can grow significantly as the number of players ($N$) and arms ($M$) increases. The state space of the game grows exponentially.
  • Bounded Regret: The authors suggest that if players had more information about the environment's parameters, it might be possible to achieve "bounded regret" (regret that stops growing entirely), which remains an open question for the multi-player case.
  • Exploiting Structure: Future work could involve refining the dynamics to specifically exploit the mathematical structure of the assignment problem to speed up convergence in large-scale networks.

Summary updated

Abstract

We consider a multi-armed bandit game where N players compete for K arms for T turns. Each player has different expected rewards for the arms, and the instantaneous rewards are independent and identically distributed. Performance is measured using the expected sum of regrets, compared to the optimal assignment of arms to players. We assume that each player only knows her actions and the reward she received each turn. Players cannot observe the actions of other players, and no communication between players is possible. We present a distributed algorithm and prove that it achieves an expected sum of regrets of near-O\left(\log^{2}T\right). This is the first algorithm to achieve a poly-logarithmic regret in this fully distributed scenario. All other works have assumed that either all players have the same vector of expected rewards or that communication between players is possible.
BibTeX
@inproceedings{bistritz2018distributed,
  author = {Ilai Bistritz and Amir Leshem},
  title = {{Distributed Multi-Player Bandits - a Game of Thrones Approach}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
}
Figure