Collision Budgets as Attribution Signals in Blind Multi-Player Bandits

Picture many radios, robots, or satellites sharing a small set of channels or work slots. None of them can talk to each other, and when two of them grab the same resource at the same moment, both get nothing. In this setting, called a multi-player multi-armed bandit, each player repeatedly picks one of $K$ "arms" (resources) and sees only its own reward. In the "blind" version, a player sees a zero but is not told whether it collided. Existing algorithms treat collisions as lost reward. Some even collide on purpose to send bits to each other. In many deployments, though, a collision is damage: a physical crash, a destroyed transmission, a regulatory violation. Collisions then have to be kept under an explicit budget while the players are still learning. The resources are also not fixed. Channel quality drifts and jumps, and players join and leave. A zero reward can therefore mean three different things: the arm is poor, a peer just collided with me, or the world changed.

This note proposes that the safety budget is the tool for separating those three explanations. Suppose every player follows a protocol that caps how often it may probe arms other players might occupy. Then a player sitting on an arm can bound how much peer interference it could possibly be receiving. Any sustained reward drop larger than that bound must come from the environment. Collisions can also only push rewards down, toward zero, never up. Together, these two facts give a one-sided change detector whose tolerance is set by the collision budget rather than tuned by hand. We build a budgeted, communication-free seating protocol around this detector, prove that its collision and regret costs scale with the budget, and test it against the strongest blind multi-player bandit algorithms under abrupt shifts, continuous drift, and player churn.

Core Claim

In blind decentralized contention where collisions count as safety violations, an anytime per-player collision budget $\epsilon$ does two jobs. It is the constraint, and it is also a known upper bound on how much any seated player's reward stream can be corrupted by peers. Concretely, if a seated player's arm has true mean $\mu$ and at most a fraction $\rho$ of its pulls in a window $W$ are collisions, its observed window mean $\hat\mu_W$ satisfies

$$\hat\mu_W \;\ge\; (1-\rho)\,\mu \;-\; \sqrt{\tfrac{\log(1/\delta)}{2|W|}}$$

with probability at least $1-\delta$. The bound follows because colliding pulls return zero and the rest are ordinary samples (Hoeffding). Here $\rho \le (\hat M - 1)\epsilon$, where $\hat M$ is the player's estimate of the number of players, so $\rho$ is computable from quantities the protocol already maintains. A drop below this floor cannot be explained by budget-compliant peers. The seated player can therefore attribute it to the environment and release its seat. Upward shifts are never peer-caused and pass through the detector without any correction. The claim is that this coupling turns the three-way confusion described in Decentralized Multi-player Multi-armed Bandits with No Collision Information into a two-way one. It does so without collision sensing, without communication, and without intentional collisions.

Relation to Prior Work

The blind multi-player bandit literature supplies the coordination mechanism we reuse and the failure modes we target. Multi-Player Bandits - a Musical Chairs Approach introduces "sit down on the first collision-free success," which we keep. Its dynamic variant handles churn with globally synchronized epoch restarts and assumes fixed arm means within epochs. We replace clock-driven restarts with change-driven releases, which need no shared clock. {Multi-Player Bandits Revisited} defines the blind sensing model (Model III) and the Selfish heuristic, which treats collisions as zero rewards inside a kl-UCB index. It also documents that Selfish can fall into absorbing states where players collide forever. That paper motivates our work, since Selfish is the obvious baseline and has no collision control. SIC-MMAB shows that deliberate collisions can carry bits and reach near-centralized regret. That result constrains our design: its signaling is exactly what a collision budget forbids, so we treat SIC-MMAB and DYN-MMAB as an unsafe reference ceiling rather than a competitor in the safe regime.

From safe exploration we borrow the per-round "permissible set" idea of Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk. That paper filters arms by an optimistic risk bound and then picks among them by an optimistic reward bound. It also shows that methods enforcing only an average constraint over the horizon play unsafe arms linearly often. That paper is single-agent with stationary, independent risk. In our setting, an arm's collision risk is caused by other learners and changes when they move. Decentralized Multi-Agent Linear Bandits with Safety Constraints is the closest safe multi-agent bandit work. Its agents cooperate over a communication graph and never block each other from arms. We study the opposite structure: mutually exclusive resources and no messages.

From non-stationary adaptation, Provably Efficient Model-Free Algorithms for Non-stationary CMDPs handles drift under constraints with restarts and an Exp3 master, but only for a single agent. STAR triggers relearning from accumulated prediction error with hand-set thresholds. We take its "detect, then rebuild" structure and remove the hand-set threshold, deriving the tolerance from the budget. Balancing Plasticity and Stability with Fast and Slow Successor Features shows that under continuous drift, aggressive resetting hurts and stability is the bottleneck. This supports releasing a seat only on evidence rather than periodically, and it supplies our continuous-drift generator (Ornstein-Uhlenbeck processes).

Research Program

The protocol, which we call Budgeted Musical Chairs with Attribution (BMC-A), gives each player two modes. A searching player maintains, for each arm, an estimate of its "available value": the reward it would get there, accounting for collisions. It also maintains an upper confidence bound on that arm's collision probability. It pulls only arms whose collision bound keeps its anytime collision count below $\epsilon t$, and among those it picks by an optimistic index on available value. This adapts the doubly optimistic rule to peer-induced risk. When no arm is permissible, it pulls the arm with the lowest collision bound. These "forced" pulls are counted and analyzed separately, because they are the price of entering a crowded system. A searching player sits down after a run of collision-free successes long enough to exclude occupancy at the chosen confidence level. A seated player runs a CUSUM-style one-sided test against the contamination-adjusted floor above, plus a symmetric test for upward shifts on neighboring free arms, which it samples rarely within its budget. When the downward test fires, the player releases its seat and searches again.

The analysis targets three results. The first is a collision bound: total collisions are at most $\epsilon M T$ plus a term logarithmic in $T$ from forced pulls. The second is a detection guarantee: a mean drop of size $\Delta > \rho\mu$ is detected within $O(\log(1/\delta)/(\Delta-\rho\mu)^2)$ pulls, by inverting the deviation bound above. The third is a dynamic-regret bound that adds the cost of undetectable drifts, of order $\rho\mu T$, to a per-change re-seating cost. The trade-off this exposes is the central scientific object of the project. A tighter collision budget makes peer interference smaller and more identifiable, but it also slows re-seating after each change. We will characterize the budget that minimizes regret as a function of the change rate and $M$. We will also state honestly that slow drift below the contamination floor is invisible by construction.

Two open issues are part of the program rather than footnotes. The first is that the floor needs an estimate $\hat M$. Errors in $\hat M$ during churn can cause false releases, so we will test a conservative, inflated estimate against a collision-frequency estimate of the kind Musical Chairs uses. The second is that a newly arriving player is budget-compliant only after it starts running the protocol. A burst of arrivals temporarily exceeds the floor, and we must measure whether this causes cascades of false releases.

Baselines

The naive reference is Selfish kl-UCB from {Multi-Player Bandits Revisited}, with collisions folded in as zero reward and no budget. It is the strongest communication-free heuristic in the blind model and the method a practitioner would deploy first. We run it with the authors' index, the same horizons and arm sets as ours, and a tuning budget equal to ours.

The strongest non-stationary competitor is Selfish with a sliding-window or discounted kl-UCB index. Window length or discount is tuned on held-out drift schedules using the same number of tuning runs we spend on BMC-A's confidence parameter. Beating it means lower dynamic regret at equal or fewer total collisions, or the same regret with collisions inside the budget where it exceeds it.

The structured blind baselines are MCTopM and Dynamic Musical Chairs. The latter gets the true shared clock it requires, which is an advantage over us. MCTopM's collision count grows as $O(M^3\log T)$ ({Multi-Player Bandits Revisited}). Dynamic Musical Chairs is proven sublinear under churn (Multi-Player Bandits - a Musical Chairs Approach). We found no reported numerical regret or collision count on Lacuna for either method under drifting arm means, so we will produce those numbers ourselves.

A per-agent safe-bandit baseline runs the doubly optimistic algorithm of Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk independently on each player, treating a zero as a risk event. It tests whether coordination structure matters beyond a safety filter.

SIC-MMAB and DYN-MMAB serve as an unsafe ceiling. The file reports that SIC-MMAB matches the centralized asymptotic bound up to a constant (SIC-MMAB), and we report how far over budget it runs. A centralized Hungarian-assignment oracle, in the spirit of REDA, gives the conflict-free upper reference. REDA reports 0% conflicting assignments with central matching (Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems).

Two ablations isolate the key ingredient. The first replaces the budget-derived floor with a standard two-sided detector at a tuned threshold. The second removes budget gating while keeping the detector, which shows whether the coupling, rather than either piece alone, is responsible for any gain.

Why not just…?

Why not just run Selfish with a sliding window? This is the real threat. Under rare, large, abrupt shifts, a well-tuned window may match BMC-A, because forgetting old data handles both the change and the confusion. Two things argue against it in general. Its window must be tuned to an unknown variation budget, a trade-off flagged for non-stationary methods in Provably Efficient Model-Free Algorithms for Non-stationary CMDPs. And every window expiry re-opens exploration for all players at once, which should produce collision bursts and the tied-index deadlocks documented for Selfish. Our abrupt-switch sweep settles the question directly. If windowed Selfish matches BMC-A on both regret and collisions across change rates, the attribution idea is not worth its complexity, and we will report that.

Why not just subtract a large collision penalty? A fixed penalty has no anytime guarantee. Its two failure modes are documented for safe RL: too small and agents accept damage, too large and they freeze (Quanyi Li et al.). Lagrangian versions oscillate unless stabilized (Safety Gymnasium). A penalty also gives a seated player no bound on peer interference, so it cannot support attribution. We include a penalty sweep and plot its regret against collisions next to BMC-A's curve over budgets.

Why not just restart everyone periodically, as Dynamic Musical Chairs does? Restarts need a shared clock. Each restart also spends collisions re-seating players whose arms did not change. Under continuous drift, the successor-features study found that plasticity-driven resets collapse where stability-preserving methods hold (Balancing Plasticity and Stability with Fast and Slow Successor Features). Our continuous-drift experiments measure collisions spent per restart against collisions spent per detected change.

Why not just centralize the assignment, as REDA does? Where a coordinator exists, it should be used. REDA's 0% conflict rate is the reference we aim to approach. The target here is settings with no coordinator and no messages, and we report the gap to the oracle rather than claim to close it.

Proposed Experiments

The primary testbed is the synthetic Bernoulli and Gaussian multi-player radio simulation used across Multi-Player Bandits - a Musical Chairs Approach, {Multi-Player Bandits Revisited} and SIC-MMAB, run in the blind model. We extend it along three axes: piecewise-constant switching of arm means at controlled rates, Ornstein-Uhlenbeck drift following the successor-features study, and Poisson player arrivals and departures. We vary $M$ from 2 to 20 and $K$ from $M$ to $4M$. Metrics are dynamic regret against the oracle best $M$ arms at each time, cumulative collisions and the maximum anytime collision rate relative to $\epsilon$, false-release rate, and detection delay. Results are reported over many seeds with confidence intervals.

As a semi-realistic stress test, we adapt the Constellation environment from Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems to decentralized region selection. A conflicting assignment counts as a collision, and region value drifts with orbital geometry. The centralized REDA solver provides the oracle reference.

Three checks are decisive. First, the attribution test. At a fixed budget, we inject environmental drops just above and just below $\rho\mu$ while peers probe at the maximum allowed rate. BMC-A should release on the first kind and hold on the second, while the two-sided-detector ablation should release on both. If it does not, the core claim fails. Second, the budget-regret frontier. Sweeping $\epsilon$ should trace a U-shaped dynamic-regret curve whose minimum moves with the change rate as the analysis predicts. Every baseline's operating point should lie on or above BMC-A's frontier at matched collision counts. Third, the churn test. Arrival bursts should cause only bounded cascades of false releases. If cascades grow with $M$, the $\hat M$-based floor is the weak link, and we will test the conservative estimate as the fix.