Regret Optimality in Decentralized Multi Player Bandits

152 concepts116 papers1 proposal

In standard online learning, a single agent balances exploration and exploitation to minimize cumulative regret. However, modern decentralized systems—such as cognitive radio networks, IoT channel allocation, and distributed matching markets—require multiple independent agents to optimize their choices simultaneously from a shared pool of resources.

When two agents select the same resource at the same time, a collision occurs, typically resulting in zero reward for both. If a central controller could orchestrate their choices, achieving optimal logarithmic regret ($O(\log T)$) would be straightforward. But in a fully decentralized setting where agents cannot directly communicate or observe each other's actions, coordination seems impossible.

Remarkably, a rich body of research has demonstrated that decentralized agents can achieve regret optimality—matching the asymptotic efficiency of a perfectly coordinated centralized system. The core intuition is that agents can use their own history of rewards and collisions to implicitly synchronize, partitioning the resource space so that everyone gets a fair share of the best resources without a central coordinator.

Self-Organization via Orthogonalization

How can agents avoid collisions without talking? The earliest and most intuitive approach relies on structured exploration phases that force agents into orthogonal (collision-free) choices over time.

In Multi-Player Bandits - a Musical Chairs Approach, Jonathan Rosenski et al. proposed a protocol inspired by the classic game of musical chairs. Agents initially explore the available options at random to estimate their rewards. Once an agent finds a sufficiently good option, it "sits down" and stops exploring. If a collision occurs, the colliding agents are forced to move and explore other options. Over time, this simple interaction causes the agents to self-organize into a stable, collision-free configuration, eventually reaching a state of constant regret where the performance gap relative to the optimum stops growing entirely.

Building on this concept of implicit coordination, Keqin Liu et al. introduced the Time Division Fair Sharing (TDFS) policy in Decentralized Multi-Armed Bandit with Multiple Distributed Players. Instead of permanently claiming a single resource, agents rotate through the top-performing resources in a synchronized, time-multiplexed fashion. This ensures that all agents share the best rewards fairly, achieving the same $O(\log T)$ regret growth as a centralized system. To eliminate collisions entirely without any communication overhead, Sebastien Bubeck et al. demonstrated in Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions that agents can leverage shared randomness combined with tree-based space partitioning to completely avoid collisions while maintaining optimal regret bounds.

Hacking the Environment: Communication via Collisions

While the above methods show that coordination is possible without communication, a fascinating insight emerged: agents can communicate, not through a dedicated network channel, but by treating the environment itself as a shared medium. Specifically, they can use deliberate collisions to transmit information.

Consider a highly constrained scenario where agents lack explicit collision sensing—they only know if they received a reward or not. In SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits, Etienne Boursier et al. showed that agents can "hack" the system by intentionally colliding on specific arms at pre-determined times. By observing streaks of zero rewards, agents can decode messages from one another, effectively establishing a protocol to negotiate who claims which arm.

This idea of using collisions as a signaling mechanism was extended to two-sided matching markets by Yirui Zhang in Matching in Multi-arm Bandit with Collision. By structuring exploration into multiple layers and using collisions to resolve conflicts hierarchically, the proposed Multi-Layer Explore Then Commit (ML-ETC) algorithm achieves an order-optimal $O(\log T)$ regret bound, bypassing the exponential regret penalties that plagued earlier decentralized matching market algorithms.

The Communication-Efficient Federated Frontier

In many modern applications, such as federated learning or distributed contextual bandits, agents are connected to a central server or a sparse network graph, but communication bandwidth is a strict bottleneck. The goal shifts from communication-free learning to minimizing the total bits exchanged while preserving centralized-equivalent regret.

The key intuition here is adaptive, event-triggered communication. Instead of synchronizing after every single round, agents only communicate when their local uncertainty or data distribution changes significantly.

For example, in distributed contextual linear bandits, Sanae Amani et al. established an information-theoretic lower bound of $\Omega(dN)$ bits for optimal performance in Distributed Contextual Linear Bandits with Minimax Optimal Communication Cost and introduced algorithms that match this bound while maintaining optimal regret. For more complex non-linear reward structures, Chuanhao Li et al. leveraged Nyström approximations in Communication Efficient Distributed Learning for Kernelized Contextual Bandits to achieve sub-linear communication costs. Similarly, Sudeep Salgia et al. showed in A Communication-Efficient Adaptive Algorithm for Federated Learning under Cumulative Regret that federated systems can achieve order-optimal cumulative regret with only logarithmic communication overhead ($O(d \log(MT))$ bits), proving that decentralization does not inherently impose an error penalty during the learning process.

The Fundamental Limits and the Price of Decentralization

Is decentralized learning truly "free"? Not quite. While the order of regret (e.g., logarithmic in time for stochastic settings) can match centralized systems, decentralization introduces a constant-factor penalty.

In {Multi-Player Bandits Revisited}, Lilian Besson et al. proved that the theoretical lower bound for cumulative regret in decentralized multi-agent systems is exactly $M$ times larger than in centralized systems, where $M$ is the number of agents. This multiplicative factor represents the mathematical price of decentralization—the unavoidable cost of initial collisions and localized exploration before coordination is achieved.

Furthermore, the topology of the communication network dictates the ease of coordination. As Mengfan Xu et al. demonstrated in Multi-agent Multi-armed Bandit Regret Complexity and Optimality, as long as the communication graph remains connected, decentralized multi-agent systems can achieve single-agent regret orders. This implies that network constraints primarily affect the constant performance factors rather than the fundamental rate of learning, cementing decentralized regret optimality as a robust and practical paradigm for distributed systems.

Key Foundational Work

Distributed Learning in Multi-Armed Bandit With Multiple Players (2010) — contributed 4 concept elements to this direction.
Decentralized Multi-Armed Bandit with Multiple Distributed Players (2009) — contributed 2 concept elements to this direction.
Distributed Algorithms for Learning and Cognitive Medium Access with Logarithmic Regret (2010) — contributed 5 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_decentralized_regret_optimality_e2d60e57,
  title = {decentralized regret optimality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-regret-optimality/rdr_e2d60e5719d64f9886fd07132f7e04bc},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_decentralized_regret_optimality_e2d60e57_v1,
  title = {decentralized regret optimality},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/decentralized-regret-optimality/rdr_e2d60e5719d64f9886fd07132f7e04bc/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake