Timezone: »
Poster
Matching in Multi-arm Bandit with Collision
YiRui Zhang · Siwei Wang · Zhixuan Fang
In this paper, we consider the matching of multi-agent multi-armed bandit problem, i.e., while agents prefer arms with higher expected reward, arms also have preferences on agents. In such case, agents pulling the same arm may encounter collisions, which leads to a reward of zero.For this problem, we design a specific communication protocol which uses deliberate collision to transmit information among agents, and propose a layer-based algorithm that helps establish optimal stable matching between agents and arms. With this subtle communication protocol, our algorithm achieves a state-of-the-art $O(\log T)$ regret in the decentralized matching market, and outperforms existing baselines in experimental results.
Author Information
YiRui Zhang (Tsinghua University)
Siwei Wang (IIIS, Tsinghua University)
Zhixuan Fang (Tsinghua University)
More from the Same Authors
-
2022 Poster: Combinatorial Bandits with Linear Constraints: Beyond Knapsacks and Fairness »
Qingsong Liu · Weihang Xu · Siwei Wang · Zhixuan Fang -
2022 Poster: Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Arms »
Xutong Liu · Jinhang Zuo · Siwei Wang · Carlee Joe-Wong · John C.S. Lui · Wei Chen -
2021 Poster: Continuous Mean-Covariance Bandits »
Yihan Du · Siwei Wang · Zhixuan Fang · Longbo Huang -
2020 Poster: Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits »
Siwei Wang · Longbo Huang · John C. S. Lui -
2018 Poster: Multi-armed Bandits with Compensation »
Siwei Wang · Longbo Huang