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 an asynchronous and decentralized learning algorithm, namely Non-Stationary Competing Bandits (NSCB), 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 NSCB. Furthermore, we validate our theoretical findings via experiments.
Short Bio:
Avishek Ghosh (Ph.D UC Berkeley, 2021) is an Assistant Professor at the department of Systems and Control Engg. and The Centre for Machine Intelligence and Data Science at IIT Bombay. Previously, he was an HDSI (Data Science) Post-doctoral fellow at the University of California, San Diego. Prior to this, he completed my PhD from the Electrical Engg. and Computer Sciences (EECS) department of UC Berkeley, advised by Prof. Kannan Ramchandran and Prof. Aditya Guntuboyina. His research interests are broadly in Theoretical Machine Learning, including Federated Learning and multi-agent Reinforcement/Bandit Learning. In particular, Avishek is interested in theoretically understanding challenges in multi-agent systems, and competition/collaboration across agents. Before coming to Berkeley, Avishek completed his masters degree from Indian Institute of Science (IISc), Bangalore (at the Electrical Communication Engg. Dept) and prior Avishek completed his bachelors degree from Jadavpur University, in the dept. of Electronics and Telecommunication Engineering.
