Beyond log^2 (T) Regret for Decentralized Bandits in Matching Markets

International Conference on Machine Learning (ICML)


We design decentralized algorithms for regret minimization in two sided matching markets with one-sided bandit feedback that significantly improves upon the prior works (Liu et al., 2020a; Sankararaman et al., 2020; Liu et al., 2020b). First, for general markets, for any ε>0, we design an algorithm that achieves a O(log1+ε(T)) regret to the agent-optimal stable matching, with unknown time horizon T, improving upon the O(log2(T)) regret achieved in (Liu et al., 2020b). Second, we provide the optimal Θ(log(T)) regret for markets satisfying uniqueness consistency – markets where leaving participants don’t alter the original stable matching. Previously, Θ(log(T)) regret was achievable (Sankararaman et al., 2020; Liu et al., 2020b) in the much restricted serial dictatorship setting, when all arms have the same preference over the agents. We propose a phase based algorithm, where in each phase, besides deleting the globally communicated dominated arms, the agents locally delete arms with which they collide often. This local deletion is pivotal in breaking deadlocks arising from rank heterogeneity of agents across arms. We further demonstrate superiority of our algorithm over existing works through simulations.

Latest Publications

Presto: A Decade of SQL Analytics at Meta

Yutian James Sun, Tim Meehan, Rebecca Schlussel, Wenlei Xie, Masha Basmanova, Orri Erling, Andrii Rosa, Shixuan Fan, Rongrong Zhong, Arun Thirupathi, Nikhil Collooru, Ke Wang, Sameer Agarwal, Arjun Gupta, Dionysios Logothetis, Kostas Xirogiannopoulos, Bin Fan, Amit Dutta, Varun Gajjala, Rohit Jain, Ajay Palakuzhy, Prithvi Pandian, Sergey Pershin, Abhisek Saikia, Pranjal Shankhdhar, Neerad Somanchi, Swapnil Tailor, Jialiang Tan, Sreeni Viswanadha, Zac Wen, Deepak Majeti, Aditi Pandit, Biswapesh Chattopadhyay

SIGMOD - 2023