Decentralized Competing Bandits in Non-Stationary Matching Markets
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.