提出首个异步去中心化多玩家博弈算法,解决无全局时钟下的碰撞与玩家数量探测难题。
Decentralized Asynchronous Multi-player Bandits
- 玩家自适应切换探索与利用,探索时均匀抽样减少冲突
- 以小概率试探他人正在使用的动作,实现动态检测玩家进出
- 首次在异步去中心化场景下实现近最优后悔率,适合物联网等真实系统
近年来,多玩家多臂老虎机(MP-MAB)因在认知无线电网络和物联网系统中的广泛应用而受到广泛关注。现有研究多集中于同步场景,但现实系统常为去中心化且异步,玩家可随时加入或离开,且无全局时钟。这种设定带来两大挑战:一、缺乏全局时间,玩家无法通过时间隐式协调,难以避免动作冲突;二、需检测当前玩家数量,但此过程代价高昂。本文针对完全异步的去中心化环境提出新算法,玩家自适应地在探索与利用间切换。探索阶段均匀抽样各臂,降低碰撞概率,缓解第一挑战;同时以小概率持续尝试他人正在使用的臂,从而有效感知玩家退出,应对第二挑战。理论证明该算法达到 $/mathcal{O}(\ ext{sqrt}{T \log T} + \log T / Δ^2)$ 的后悔上界,其中 $Δ$ 为任意两臂间最小期望奖励差距。据我们所知,这是首个在异步去中心化环境中高效的 MP-MAB 算法。大量实验验证了其有效性与鲁棒性,证明其适用于真实场景。
原文摘要 · Abstract (English)
In recent years, multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their wide applications in cognitive radio networks and Internet of Things systems. While most existing research on MP-MAB focuses on synchronized settings, real-world systems are often decentralized and asynchronous, where players may enter or leave the system at arbitrary times, and do not have a global clock. This decentralized asynchronous setting introduces two major challenges. First, without a global time, players cannot implicitly coordinate their actions through time, making it difficult to avoid collisions. Second, it is important to detect how many players are in the system, but doing so may cost a lot. In this paper, we address the challenges posed by such a fully asynchronous setting in a decentralized environment. We develop a novel algorithm in which players adaptively change between exploration and exploitation. During exploration, players uniformly pull their arms, reducing the probability of collisions and effectively mitigating the first challenge. Meanwhile, players continue pulling arms currently exploited by others with a small probability, enabling them to detect when a player has left, thereby addressing the second challenge. We prove that our algorithm achieves a regret of $\mathcal{O}(\sqrt{T \log T} + {\log T}/{Δ^2})$, where $Δ$ is the minimum expected reward gap between any two arms. To the best of our knowledge, this is the first efficient MP-MAB algorithm in the asynchronous and decentralized environment. Extensive experiments further validate the effectiveness and robustness of our algorithm, demonstrating its applicability to real-world scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。