Timezone: »
Spotlight
Beyond $log^2(T)$ regret for decentralized bandits in matching markets
Soumya Basu · Karthik Abinav Sankararaman · Abishek Sankararaman
We design decentralized algorithms for regret minimization in the two sided matching market 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 $\varepsilon > 0$, we design an algorithm that achieves a $O(\log^{1+\varepsilon}(T))$ regret to the agent-optimal stable matching, with unknown time horizon $T$, improving upon the $O(\log^{2}(T))$ regret achieved in (Liu et al.\,2020b). Second, we provide the optimal $\Theta(\log(T))$ agent-optimal regret for markets satisfying {\em uniqueness consistency} -- markets where leaving participants don't alter the original stable matching. Previously, $\Theta(\log(T))$ regret was achievable (Sankararaman et al.\,2020, Liu et al.\,2020b) in the much restricted {\em 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 \emph{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.
Author Information
Soumya Basu (Google)
Karthik Abinav Sankararaman (Facebook)
Abishek Sankararaman (Amazon Web Services)
Related Events (a corresponding poster, oral, or spotlight)
-
2021 Poster: Beyond $log^2(T)$ regret for decentralized bandits in matching markets »
Thu. Jul 22nd 04:00 -- 06:00 AM Room
More from the Same Authors
-
2021 : Under-exploring in Bandits with Confounded Data »
Nihal Sharma · Soumya Basu · Karthikeyan Shanmugam · Sanjay Shakkottai -
2023 : Rethinking Incentives in Recommender Systems: Are Monotone Rewards Always Beneficial? »
Fan Yao · Chuanhao Li · Karthik Abinav Sankararaman · Yiming Liao · Yan Zhu · Qifan Wang · Hongning Wang · Haifeng Xu -
2023 : Competing Bandits in Non-Stationary Matching Markets »
Avishek Ghosh · Abishek Sankararaman · Kannan Ramchandran · Tara Javidi · Arya Mazumdar -
2023 Poster: A Statistical Perspective on Retrieval-Based Models »
Soumya Basu · Ankit Singh Rawat · Manzil Zaheer -
2022 Poster: Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits »
Avishek Ghosh · Abishek Sankararaman -
2022 Spotlight: Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret in Stochastic Contextual Linear Bandits »
Avishek Ghosh · Abishek Sankararaman -
2022 Poster: FITNESS: (Fine Tune on New and Similar Samples) to detect anomalies in streams with drift and outliers »
Abishek Sankararaman · Balakrishnan Narayanaswamy · Vikramank Singh · Zhao Song -
2022 Spotlight: FITNESS: (Fine Tune on New and Similar Samples) to detect anomalies in streams with drift and outliers »
Abishek Sankararaman · Balakrishnan Narayanaswamy · Vikramank Singh · Zhao Song -
2021 Poster: Combinatorial Blocking Bandits with Stochastic Delays »
Alexia Atsidakou · Orestis Papadigenopoulos · Soumya Basu · Constantine Caramanis · Sanjay Shakkottai -
2021 Spotlight: Combinatorial Blocking Bandits with Stochastic Delays »
Alexia Atsidakou · Orestis Papadigenopoulos · Soumya Basu · Constantine Caramanis · Sanjay Shakkottai -
2020 Poster: Learning Mixtures of Graphs from Epidemic Cascades »
Jessica Hoffmann · Soumya Basu · Surbhi Goel · Constantine Caramanis -
2020 Poster: The Impact of Neural Network Overparameterization on Gradient Confusion and Stochastic Gradient Descent »
Karthik Abinav Sankararaman · Soham De · Zheng Xu · W. Ronny Huang · Tom Goldstein -
2019 Poster: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai -
2019 Oral: Pareto Optimal Streaming Unsupervised Classification »
Soumya Basu · Steven Gutstein · Brent Lance · Sanjay Shakkottai