2022/05/31 by Avishek Ghosh, Ghosh, Avishek, Abishek Sankararaman +7 · 1 citation
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2206.00120
openalex publication_date 2022/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Understanding complex dynamics of two-sided online matching markets, where the demand-side agents compete to match with the supply-side (arms), has recently received substantial interest. To that end, in this paper, we introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We adhere to the serial dictatorship setting, where the demand-side agents have unknown and different preferences over the supply-side (arms), but the arms have fixed and known preference over the agents. We propose and analyze a decentralized and asynchronous learning algorithm, namely Decentralized Non-stationary Competing Bandits (DNCB), where the agents play (restrictive) successive elimination type learning algorithms to learn their preference over the arms. The complexity in understanding such a system stems from the fact that the competing bandits choose their actions in an asynchronous fashion, and the lower ranked agents only get to learn from a set of arms, not dominated by the higher ranked agents, which leads to forced exploration. With carefully defined complexity parameters, we characterize this forced exploration and obtain sub-linear (logarithmic) regret of DNCB. Furthermore, we validate our theoretical findings via experiments.