Source-linked AI summary
SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits
Etienne Boursier, Vianney Perchet
TL;DR
Synchronization makes decentralized multiplayer bandits effectively communicative through collisions, though the assumption is considered impractical. The paper uses synchronized collision-based communication and also proposes an algorithm for a dynamic setting without synchronization. It reports centralized-lower-bound-level exploration regret for synchronized play and logarithmic regret for the dynamic model.
Problem
Synchronization makes decentralized multiplayer bandits effectively communicative through collisions, but is considered unreasonable for practical settings, motivating a dynamic model.
Source: §2.3 · p. 7, §4 · p. 9Method
The paper uses synchronized collision-based communication for the static model, then proposes DYN-MMAB for the dynamic No Sensing model.
Source: §3 · p. 7, §3.1 · p. 7, §4 · p. 9Results
Synchronized exploration regret reaches the centralized problem's lower bound up to a constant factor, while DYN-MMAB has logarithmic regret in the dynamic setting.
Source: §1 · p. 2, §2.3 · p. 7, §3.1 · p. 7Takeaways & Limitations
The authors argue synchronization should not be assumed unless communication is allowed, while logarithmic regret remains achievable in the dynamic model.
Source: §1 · p. 2, §4 · p. 9Communication cost scales with KM^3 and can predominate for large networks; the dynamic model is difficult to formalize when players stay briefly.
Source: §2.3 · p. 7
Abstract
from arXiv · showhide
Motivated by cognitive radio networks, we consider the stochastic multiplayer multi-armed bandit problem, where several players pull arms simultaneously and collisions occur if one of them is pulled by several players at the same stage. We present a decentralized algorithm that achieves the same performance as a centralized one, contradicting the existing lower bounds for that problem. This is possible by "hacking" the standard model by constructing a communication protocol between players that deliberately enforces collisions, allowing them to share their information at a negligible cost. This motivates the introduction of a more appropriate dynamic setting without sensing, where similar communication protocols are no longer possible. However, we show that the logarithmic growth of the regret is still achievable for this model with a new algorithm.
1 Introduction
The introduction frames multiplayer bandits as a collision-prone, decentralized learning problem and contrasts existing bounds with algorithms that use synchronization or address dynamic, no-sensing play.
1 Introduction
- In decentralized cognitive-radio bandits, simultaneous pulls of the same arm cause collisions and zero rewards, while centralized control permits costly per-step communication.Existing multiplayer lower bounds suggest decentralization adds a factor M, but are proved without accounting for collisions.Source: §1 · pp. 1–2
- SIC-MMAB uses deliberate, observed collisions to communicate, and its regret asymptotically reaches the centralized problem's lower bound up to a universal constant.This result contradicts existing lower bounds for the problem.Source: §1 · p. 2
- Without synchronization or collision observations, the proposed algorithm achieves logarithmic regret, with dependencies on reward gaps that become quadratic.Source: §1 · p. 2
1.1 Models
- The models distinguish centralized players who can share information from decentralized players limited to their own rewards and actions; synchronized starts define the static model, while unknown staggered entry defines the dynamic model.Source: §1.1 · p. 2
- In No Sensing, a zero reward cannot distinguish a collision from a zero arm reward; this is the most difficult setting because players receive no extra observation.No Sensing and Collision Sensing are equivalent when P(Xk = 0) = 0.Source: §1.1 · p. 3
2 Collision Sensing: achieving centralized performances by communicating through collisions
SIC-MMAB uses synchronization to exchange player statistics through deliberate collisions, making decentralized collision-sensing bandits nearly centralized in regret growth. Its exploration regret reaches the centralized lower bound up to a constant factor, but the approach depends on synchronization and incurs communication costs.
2 Collision Sensing: achieving centralized performances by communicating through collisions
- With synchronized players, SIC-MMAB achieves exploration regret similar to the centralized lower bound, up to a constant factor.The communication cost scales with KM^3 and may dominate log(T) in large networks.Source: §2 · p. 3, §2.3 · p. 7
2.2.1 Initialization phase
- Initialization estimates the player count and assigns ranks, first creating an orthogonal arm allocation and then inferring ranks from observed collisions.The first procedure runs for ⌈K log(T)⌉ steps; the rank-inference procedure lasts 2K steps.Source: §2.2.1 · p. 4
2.2.2 Exploration phase
- During exploration, active players hop collision-free across active arms so each arm receives 2^p pulls per active player in phase p.Players use their internal ranks to maintain an orthogonal setting.Source: §2.2.2 · p. 4
2.2.3 Communication phase
- Players send statistics through deliberate collisions: pulling a receiver’s communicating arm encodes 1, while pulling one’s own encodes 0.At the end of communication, active players share statistics and can accept or reject arms.Source: §2.2.3 · p. 5
Communication Protocol
- Each arm statistic is quantized to an integer and transmitted in p+1 bits, preserving synchronization among players.The protocol schedules communications in turn using players’ internal ranks.Source: §2.2.3 · p. 5
2.2.3 Communication phase
- Without collision sensing, a bit cannot be sent in one time step, but the paper proposes two communication-based algorithms for that setting.The passage states that a bit can then be sent in log(T) time.Source: §2.2.3 · p. 5
2.2.4 Regret bound of SIC-MMAB
- Synthetic experiments confirm SIC-MMAB scales better than MCTopM with the gaps and has smaller minmax regret.The regret bound separates exploration, initialization, and communication costs.Source: §2.2.4 · p. 6
2.3 In contradiction with existing lower bounds?
- The result contradicts prior decentralized lower bounds because those arguments disregard information that players can infer from collisions.SIC-MMAB uses synchronization to establish collision-based communication.Source: §2.3 · pp. 6–7
3 Without synchronization, the dynamic setting
The dynamic setting removes synchronization and collision observations, and DYN-MMAB achieves logarithmic regret without synchronization. Its communication-less protocol tracks occupied and preferred arms, using reward estimates to identify available arms and avoid collisions.
3 Without synchronization, the dynamic setting
- The setting removes synchronized starts; players do not know the global time, but know how long they have been playing and their remaining horizon.The section assumes players stay after joining, while noting adaptations for departures during specified intervals or a shared internal clock.Source: §3 · p. 7
3.1 A logarithmic regret algorithm
- DYN-MMAB achieves logarithmic regret in the dynamic No Sensing model, though its regret bound depends quadratically on reward gaps.The supplied theorem passage introduces an upper bound but does not provide its formula.Source: §3.1 · p. 7
3.2 A communication-less protocol
- Players track occupied arms and an ordered preference list; an arm is active until it enters either set.The algorithm detects an occupied arm after successive zero rewards, or when its average reward falls enough to be dominated by another arm.Source: §3.2 · p. 8
- For a free arm, confidence intervals estimate its mean multiplied by a shared factor; interval dominance still identifies the better arm.The factor reflects the expected effect of players exploring simultaneously and affects the analysis, not the algorithm's operation.Source: §3.2 · p. 8
- A player tries to occupy the best remaining free arm and keeps exploring if another player appears to have occupied it.With high probability, the player eventually exploits an arm after all better arms are exploited.Source: §3.2 · p. 9
4 Conclusion
The conclusion argues that synchronization effectively permits communication through deliberate collisions, making the decentralized problem nearly equivalent to the centralized one in the considered model. The appendix outlines SIC-MMAB’s initialization and phased operation.
4 Conclusion
- Synchronization enables deliberate collision-based communication at sub-logarithmic cost, making decentralized multiplayer bandits nearly equivalent to the centralized problem in the considered model.The communication cost depends strongly on the number of agents, motivating work on scaling with both time and player count and on efficient protocols.Source: §4 · p. 9
- The paper argues synchronization should not be assumed without communication, and introduces a dynamic model with a first logarithmic-regret algorithm.The supplied conclusion states this claim without specifying the algorithm's bound.Source: §4 · p. 9
MusicalChairs Protocol
- Musical Chairs runs for T0 steps to reach an orthogonal setting, where players pull different arms; each player's arm then serves as an external rank.The appendix specifies T0 = ⌈K log(T)⌉.Source: §A.1 · p. 11, MusicalChairs Protocol · p. 11
Estimate_M Protocol
- Estimate_M uses collisions during arm pulls and sequential hopping to estimate the player count and assign each player an internal rank.After initialization, SIC-MMAB alternates exploration and communication phases before players exploit assigned arms.Source: Estimate_M Protocol · pp. 11–12, MusicalChairs Protocol · p. 11
- SIC-MMAB explores by sequentially hopping among active arms, sends statistics during communication phases, and eventually pulls an assigned arm through horizon T.The algorithm maintains statistics across phases and removes accepted or rejected arms from the active set.Source: Estimate_M Protocol · p. 12
A.2 Regret analysis of SIC-MMAB
The regret analysis decomposes SIC-MMAB's regret into initialization, communication, and exploration or exploitation contributions.
A.2 Regret analysis of SIC-MMAB
- The communication contribution is associated with steps when players communicate statistics using the Send Protocol.The analysis denotes these steps by Comm.Source: §A.2 · pp. 12–13
- The exploration and exploitation contribution covers steps after initialization that are not communication steps.The analysis denotes this set of steps by Explo.Source: §A.2 · pp. 12–13
- The analysis separates regret incurred during initialization from regret incurred during communication and during exploration or exploitation.Communication steps are those in which players send statistics using the Send Protocol.Source: §A.2 · pp. 12–13
A.2.1 Initialization analysis
The initialization analysis bounds its duration and considers the probability that Musical Chairs reaches an orthogonal setting before players estimate their number and assign ranks.
A.2.1 Initialization analysis
- Initialization regret is bounded by M(T0+2K), since initialization lasts T0+2K steps.If the players reach an orthogonal setting, they determine M and unique internal ranks.Source: §A.2.1 · p. 13
- Musical Chairs aims to place all players on different arms by time T0, enabling the subsequent player-count and rank assignment.Players with external ranks k and k′ collide at round T0 + k + k′ during the assignment procedure.Source: §A.2.1 · p. 13
- The proof bounds a single player's probability of colliding at every step through T0, then applies a union bound over all M players.The supplied passage does not include the resulting probability expression.Source: §A.2.1 · p. 13
A.2.2 Exploration regret
The section bounds exploration regret by controlling how many pulls occur before arms are accepted or rejected. Under successful initialization and correct arm estimates, its lemmas establish bounds for optimal- and suboptimal-arm exploration that yield Lemma 3.
A.2.2 Exploration regret
- Lemma 4 bounds the probability that an arm’s estimate deviates from its mean beyond the confidence bound over the first n phases by 4n.The supplied statement gives the bound as printed; it does not include a denominator.Source: §A.2.2 · p. 13
- An optimal arm is accepted within the phase determined by its gap, and cannot be wrongly rejected while the confidence intervals are correct.The proof conditions on successful initialization and correct estimates.Source: §A.2.2 · p. 14
- With successful initialization and correct estimates, the number of exploration pulls before accepting or rejecting an arm is at most t_k with the probability in Proposition 1.The proof controls when optimal arms are accepted and suboptimal arms rejected.Source: §A.2.2 · pp. 14–15
- The two auxiliary lemmas yield the second point of Lemma 5, and the two points of Lemma 5 together with Equation (3) yield Lemma 3.Source: §A.2.2 · pp. 15–16
- Exploration pulls of optimal arms are accounted for by the pulls they miss when active suboptimal arms are explored instead.The proof sums this accounting over optimal arms.Source: §A.2.2 · p. 15
A.2.3 Communication cost
Communication cost is negligible compared with log(T), with a notable regret impact only for small T.
A.2.3 Communication cost
- Communication cost is negligible compared with log(T), and has a significant impact on regret only for small T.Source: §A.2.3 · p. 16
- Each communication phase has length at most KM 2(p + 1), yielding a total communication-cost bound expressed as KM 3 times a sum over phases.The supplied passage truncates the sum’s endpoint.Source: §A.2.3 · p. 16
A.2.4 Total regret
The total-regret proof combines the lemmas with a bound on bad events to obtain an O(KM log(T)) contribution and then the bound in Theorem 1.
A.2.4 Total regret
- The choice T0 = ⌈K log(T)⌉, together with Lemmas 2, 3, and 8, bounds the probability of a bad event.The supplied passage truncates the probability bound.Source: §A.2.4 · p. 16
- The average regret due to bad events is upper bounded by O(KM log(T)).Source: §A.2.4 · p. 16
A.3 Experiments
In experiments, SIC-MMAB’s regret depends less on the gap than MCTopM’s, although it needs a much longer horizon to reach constant regret in the reported setting. DYN-MMAB tracks preferred and occupied arms while players explore and attempt to claim preferred arms.
A.3 Experiments
- For K = 9, M = 6, and T = 5 × 10^5, SIC-MMAB requires a horizon near 40 times larger to converge to constant regret.The experiment used means linearly distributed between 0.9 and 0.89, with consecutive-arm gap 1.25 × 10−3.Source: §A.3 · pp. 16–17
- SIC-MMAB’s regret has smaller dependence on 1/∆ than MCTopM’s, whose gap-scaling slope is approximately twice as large.The comparison used Bernoulli rewards and averages over 200 runs; at very small gaps, regret depends only on T.Source: §A.3 · pp. 16–17, Figure 1 · p. 17
B.1 DYN-MMAB description
- DYN-MMAB adds an arm to Occupied after a full block of L_j^k pulls yields only zero rewards, with L_j^k updated from a lower bound on the arm’s mean.Source: §B.1 · p. 17
- A player adds an active arm to Preferences when its confidence interval makes it better than every other active arm.Source: §B.1 · p. 17
- Players try preferred arms in order while continuing to explore, and move to the next preference when an arm is occupied by another player.They exploit an arm after a positive reward; a player does not exploit a later preference before the current one is resolved.Source: §B.1 · p. 18
B.2.1 Auxiliary lemmas
These passages develop SIC-MMAB2’s initialization, exploration, communication, and arm-update procedures, along with auxiliary lemmas supporting reliable player-count and signal detection, occupied-arm identification, eventual exploitation, and regret analysis.
B.2.1 Auxiliary lemmas
- The occupied-arm detection proof separates early and late occupation: few pulls make its average reward drop quickly, while later occupation permits tight estimation and quick detection.The analysis conditions on correct estimates of free arms and concludes that the occupied arm is detected after a bounded time.Source: §B.2.1 · pp. 19–20
- With high probability, no free arm is falsely detected as occupied, because each block of pulls on it yields a positive reward.The proof conditions on correct estimates of the free arms and applies a union bound over blocks.Source: §B.2.1 · p. 21
- With high probability, each player eventually exploits an arm only after all better arms are exploited by other players.Lemma 10 bounds the stage by which this occurs using the player’s selected arm and its exploration time.Source: §B.2.1 · p. 21
B.2.2 Regret in dynamic setting
- The dynamic-setting regret is bounded by twice the sum of exploration times, since players exploit the top-M arms and collisions involve at most one exploiting player.Regret from low-probability estimation errors is O(KM^2), dominated by exploration regret.Source: §B.2.2 · p. 22
C No Sensing: communication through synchronization
- Without sensing, a known positive reward lower bound permits communication via repeated actions, but its log(T)/µmin cost motivates SIC-MMAB2’s limited-information protocol and logarithmic regret.SIC-MMAB2 communicates whether arms are optimal or sub-optimal rather than transmitting statistics, improving the dependency on M.Source: C No Sensing: communication through… · p. 22
- In No Sensing, SELFISH players independently following UCB may incur linear regret with some constant probability [8].The paper says Appendix D explains reasons for this failure using algebraic arguments.Source: C No Sensing: communication through… · p. 22
C.1 Adapted communication protocol
- SIC-MMAB2 initializes by estimating M, alternates exploration and communication to declare optimal or sub-optimal arms, then exploits; it assumes players know a positive lower bound µmin.Its communication phases share common sets of active arms and players.Source: §C.1 · p. 22
C.2 Algorithm description
- The SIC-MMAB2 algorithm description reuses the definitions of Mp and Kp from Section 2.Source: §C.2 · p. 23
C.2.2 Exploration phases
- Exploration begins with Musical Chairs when the previous communication phase had a declaration or fixation block, creating an orthogonal setting for collision-free sequential hopping.Statistics are not shared between players, inducing an additional M factor in regret; acceptance and rejection decisions remain based on exploration pulls as in SIC-MMAB.Source: §C.2.2 · p. 23
C.2.3 Communication phase
- Active players communicate in synchronized Td-length blocks, which may differ in type across players; declarations, fixation, and reception support sharing discoveries and occupying optimal arms.Players declare sub-optimal arms, attempt to occupy detected optimal arms, and use sequential hopping to receive declarations.Source: §C.2.3 · p. 24
- To declare an arm sub-optimal, a player randomly alternates between pulling it and sequentially hopping, enabling her to signal while detecting other players’ signals.Other players detect the signal through a significant loss in the arm’s empirical reward.Source: §C.2.3 · p. 24
Declare Protocol
- Lemma 12 gives a choice of Td that lets every player detect declarations without false positives, with high probability, regardless of the block they are in.Players detect signals from reward losses on arms sampled by the declaring player.Source: §C.2.3 · p. 24, Declare Protocol · p. 25
Occupy Protocol
- In fixation blocks, players sequentially hop until they receive a positive reward on a detected optimal arm, then exploit it; reception blocks detect other players’ signals.The last reception block with no new signal lets players distinguish exploited optimal arms, which yield zero rewards, from declared sub-optimal arms, and share a common active-arm set and player count.Source: Declare Protocol · p. 25, Occupy Protocol · p. 25, Receive Protocol · pp. 25–26
Update
- The update removes all declared arms from the active set and reduces the active-player count by the number of declared arms whose s[i] equals 0.Source: Update · pp. 26–27
C.3 Regret analysis
- SIC-MMAB2 regret analysis decomposes total regret into initialization, exploration, and communication terms.A communication step is counted when at least one player uses Declare or Occupy; a final reception block counts as exploration if its statistics are used for arm estimation.Source: §C.3 · p. 27
C.3.1 Initialization regret
- With probability 1 − O(MK exp(−µminTc)), every player correctly estimates M and the players reach an orthogonal setting by the end of initialization.Initialization lasts 3KTc steps, giving Rinit ≤ 3MKTc; Estimate_M_NoSensing counts zero-reward Tc-step blocks while sequentially hopping across 2K blocks.Source: Estimate_M_NoSensing Protocol · p. 23, §C.3.1 · p. 28
C.3.2 Communication regret
The communication-regret analysis establishes conditions for successful declarations and occupation signals, then bounds the communication cost across the algorithm’s phases.
C.3.2 Communication regret
- The communication-phase properties and regret are collected in Lemma 12, with block length chosen as specified by its Td condition.Source: §C.3.2 · p. 28
- A declaration is detected by all active players, while false signals are excluded and occupation of an arm is recognized as a declaration.Source: §C.3.2 · p. 28
- A successful communication block correctly detects every declaration, assigns detected optimal arms for exploitation, and produces no false detections, conditional on prior Musical Chairs success.Source: §C.3.2 · p. 29
- There are at most N + K communication blocks under the preceding-success condition, and only blocks containing a declaration or fixation count toward Comm’s length.Source: §C.3.2 · pp. 29–30
C.3.3 Exploration regret
The exploration analysis bounds regret by conditioning on successful initialization, communication, and Musical Chairs procedures; a separate argument explains how SELFISH can remain synchronized and incur linear regret.
C.3.3 Exploration regret
- Conditioned on successful initialization, communication, and Musical Chairs, exploration outside Musical Chairs is collision-free and sub-optimal arms are identified with high probability.Source: §C.3.3 · p. 30
- The total-regret bound combines the component regrets and the bad-event cost, whose contribution is dominated by communication regret.Source: §C.3.3 · p. 30
D On the inefficiency of SELFISH algorithm
- SELFISH can leave players with identical pull counts and observed averages, causing them to choose the same arms and collide until a tie-breaking point occurs.Source: D On the inefficiency of SELFISH… · p. 31
- For Bernoulli rewards, the analysis argues such tie-breaking points might never occur under its distinct-positive-reward-count condition, though that event remains possible with probability independent of T.Source: D On the inefficiency of SELFISH… · p. 31
- The argument is theoretical: finite-precision computers cannot distinguish rationals from irrationals, so its advanced reasoning does not apply in practice.Source: D On the inefficiency of SELFISH… · p. 31