Timezone: »

Matching in Multi-arm Bandit with Collision
YiRui Zhang · Siwei Wang · Zhixuan Fang

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #939
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