Regret Bounds for Fully Asynchronous Decentralized Multiplayer Bandits via Probing

Fully asynchronous decentralized multiplayer multiarmed bandits model multiple players that learn while competing for a finite set of shared resources in a dynamic environment. Players act independently and may enter or permanently leave the system at arbitrary times. We study this problem under collision sensing. For environments containing \(x\) permanent departures, we establish an expected cumulative regret lower bound \(\Omega(\sqrt{mxT})\), where \(m\) is an upper bound on the number of simultaneously active players. We then propose PULSE (Probing Based Uncertainty Aware Lightweight Stale Arm Elimination), which uses lightweight probing to adapt when a previously occupied arm becomes available. We prove that PULSE improves the time dependence of the regret term caused by departures from \(O(m^{3/2}M\sqrt{T\log T})\) to \(O(m^{3/2}M\sqrt{T})\), removing an additional \(\sqrt{\log T}\) factor. In an asynchronous dynamic benchmark, PULSE reduces total pseudo regret by approximately 42.2% and pseudo regret after departures by approximately 51.5%. These results sharpen the analysis of fully asynchronous dynamic MP-MABs and provide a lightweight mechanism for adapting to permanent departures.