Related papers: Decentralized Competing Bandits in Non-Stationary Matching Markets

Decentralized Competing Bandits in Non-Stationary Matching Markets

URL: http://arxiv.org/abs/2206.00120v1
Date: Tue, 31 May 2022 21:05:30 GMT
Title: Decentralized Competing Bandits in Non-Stationary Matching Markets
Authors: Avishek Ghosh, Abishek Sankararaman, Kannan Ramchandran, Tara Javidi and Arya Mazumdar
Abstract summary: We introduce the framework of decentralized two-sided matching market under non stationary (dynamic) environments. We propose and analyze a decentralized and asynchronous learning algorithm, namely Decentralized Non-stationary Competing Bandits (textttDNCB) We characterize this emphforced exploration and obtain sub-linear (logarithmic) regret of textttDNCB.
Score: 46.13741000158631
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: 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 (\texttt{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 \emph{dominated} by the higher ranked agents, which leads to \emph{forced exploration}. With carefully defined complexity parameters, we characterize this \emph{forced exploration} and obtain sub-linear (logarithmic) regret of \texttt{DNCB}. Furthermore, we validate our theoretical findings via experiments.