{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T21:52:25Z","timestamp":1767909145425,"version":"3.49.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,3,9]],"date-time":"2022-03-09T00:00:00Z","timestamp":1646784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2018YFB1004700"],"award-info":[{"award-number":["2018YFB1004700"]}]},{"name":"China NSF","award":["62172206, 61802172, 61832005, 61972254"],"award-info":[{"award-number":["62172206, 61802172, 61832005, 61972254"]}]},{"name":"China NSF of Jiangsu Province","award":["BK20201248"],"award-info":[{"award-number":["BK20201248"]}]},{"name":"Open Fund of PDL","award":["WDZC20205500109"],"award-info":[{"award-number":["WDZC20205500109"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            Online bipartite matching has attracted wide interest since it can successfully model the popular online car-hailing problem and sharing economy. Existing works consider this problem under either\n            <jats:italic>adversary<\/jats:italic>\n            setting or\n            <jats:italic>i.i.d.<\/jats:italic>\n            setting. The former is too pessimistic to improve the performance in the general case; the latter is too optimistic to deal with the varying distribution of vertices. In this article, we initiate the study of the non-stationary online bipartite matching problem, which allows the distribution of vertices to vary with time and is more practical. We divide the non-stationary online bipartite matching problem into two subproblems, the matching problem and the selecting problem, and solve them individually. Combining Batch algorithms and deep Q-learning networks, we first construct a candidate algorithm set to solve the matching problem. For the selecting problem, we use a classical online learning algorithm, Exp3, as a selector algorithm and derive a theoretical bound. We further propose CDUCB as a selector algorithm by integrating distribution change detection into UCB. Rigorous theoretical analysis demonstrates that the performance of our proposed algorithms is no worse than that of any candidate algorithms in terms of competitive ratio. Finally, extensive experiments show that our proposed algorithms have much higher performance for the non-stationary online bipartite matching problem comparing to the state-of-the-art.\n          <\/jats:p>","DOI":"10.1145\/3502734","type":"journal-article","created":{"date-parts":[[2022,3,10]],"date-time":"2022-03-10T14:03:20Z","timestamp":1646921000000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Online Learning Bipartite Matching with Non-stationary Distributions"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8283-5180","authenticated-orcid":false,"given":"Weirong","family":"Chen","sequence":"first","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiaqi","family":"Zheng","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haoyu","family":"Yu","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guihai","family":"Chen","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yixin","family":"Chen","sequence":"additional","affiliation":[{"name":"National Lab for Parallel and Distributed Processing, National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dongsheng","family":"Li","sequence":"additional","affiliation":[{"name":"National Lab for Parallel and Distributed Processing, National University of Defense Technology, Changsha, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329573"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1013689704352"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701398375"},{"key":"e_1_3_2_5_2","first-page":"138","article-title":"Adaptively tracking the best bandit arm with an unknown number of distribution changes","author":"Ortner R.","year":"2019","unstructured":"R. Ortner, P. Auer, and P. Gajane. 2019. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of the 32nd Conference on Learning Theory (2019), 138\u2013158.","journal-title":"Proceedings of the 32nd Conference on Learning Theory"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3215594.3215610"},{"key":"e_1_3_2_7_2","article-title":"What doubling tricks can and can\u2019t do for multi-armed bandits","author":"Besson Lilian","year":"2018","unstructured":"Lilian Besson and Emilie Kaufmann. 2018. What doubling tricks can and can\u2019t do for multi-armed bandits. arXiv:1803.06971. Retrieved from https:\/\/arxiv.org\/abs\/1803.06971.","journal-title":"arXiv:1803.06971. Retrieved from https:\/\/arxiv.org\/abs\/1803.06971."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2019.1843"},{"key":"e_1_3_2_9_2","doi-asserted-by":"crossref","unstructured":"Joshua Comden Sijie Yao Niangjun Chen Haipeng Xing and Zhenhua Liu. 2019. Online optimization in cloud resource provisioning: Predictions regrets and algorithms. In Proceedings of the ACM on Measurement and Analysis of Computing Systems . 1\u201330.","DOI":"10.1145\/3322205.3311087"},{"key":"e_1_3_2_10_2","volume-title":"Probability and Statistics","year":"1986","unstructured":"DeGroot and H. Morris. 1986. Probability and Statistics. Addison-Wesley Publishing Company."},{"key":"e_1_3_2_11_2","unstructured":"John P. Dickerson Karthik Abinav Sankararaman Aravind Srinivasan and Pan Xu. 2018. Assigning tasks to workers based on historical data: Online task assignment with two-sided arrivals. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems . 318\u2013326."},{"key":"e_1_3_2_12_2","unstructured":"DiDi chuxing. ([n. d.]). Retrieved on December 2019 from https:\/\/www.didiglobal.com\/."},{"key":"e_1_3_2_13_2","article-title":"Research on trip distance distribution model and parameter","author":"Bo L. Zhen","year":"2008","unstructured":"L. Zhen Bo and S. Fei. 2008. Research on trip distance distribution model and parameter. Journal of Traffic and Transportation Engineering 8, 2 (2008) 110\u2013115.","journal-title":"Journal of Traffic and Transportation Engineering"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAES.2010.5461658"},{"key":"e_1_3_2_15_2","unstructured":"Gaia. ([n. d.]). Retreived on December 2019 from https:\/\/outreach.didichuxing.com\/research\/opendata\/."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24412-4_16"},{"key":"e_1_3_2_17_2","volume-title":"On Computing the Distribution Function for the Sum of Independent and Non-identical Random Indicators","author":"Hong Yili","year":"2011","unstructured":"Yili Hong. 2011. On Computing the Distribution Function for the Sum of Independent and Non-identical Random Indicators. Technical Report."},{"key":"e_1_3_2_18_2","doi-asserted-by":"crossref","unstructured":"Zhiyi Huang Zhihao Gavin Tang Xiaowei Wu and Yuhao Zhang. 2018. Online vertex-weighted bipartite matching: Beating 1\u20131\/e with random arrivals. ACM Transactions on Algorithms 15 3 (2019) 1\u201315.","DOI":"10.1145\/3326169"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2016.0807"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00359-w"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature14236"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799379"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2019.2904350"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","unstructured":"Kunkun Pang Mingzhi Dong Yang Wu and Timothy M. Hospedales. 2018. Dynamic ensemble active learning: A non-stationary bandit with expert advice. In 24th International Conference on Pattern Recognition . 2269\u20132276.","DOI":"10.1109\/ICPR.2018.8545422"},{"key":"e_1_3_2_26_2","unstructured":"Siersdorfer Stefan Rokicki Markus and Zerr Sergej. 2015. Groupsourcing: Team competition designs for crowdsourcing. In Proceedings of the 24th International Conference on World Wide Web . 906\u2013915."},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_2_28_2","volume-title":"Proceedings of the 31st International Conference on Artificial Intelligence and Statistics","author":"Shen Yanning","year":"2018","unstructured":"Yanning Shen, Tianyi Chen, and Georgios B. Giannakis. 2018. Online ensemble multi-kernel learning adaptive to non-stationary and adversarial environments. In Proceedings of the 31st International Conference on Artificial Intelligence and Statistics."},{"key":"e_1_3_2_29_2","first-page":"301","volume-title":"Proceedings of the International Conference on Database Systems for Advanced Applications","year":"2018","unstructured":"Qian Tao, Yuxiang Zeng, Zimu Zhou, Yongxin Tong, Lei Chen, and Ke Xu. 2018. Multi-worker-aware task planning in real-time spatial crowdsourcing. In Proceedings of the International Conference on Database Systems for Advanced Applications. 301\u2013317."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994523"},{"key":"e_1_3_2_31_2","doi-asserted-by":"crossref","unstructured":"Yongxin Tong Jieying She Bolin Ding Libin Wang and Lei Chen. 2016. Online mobile micro-task allocation in spatial crowdsourcing. In Proceedings of the IEEE 32nd International Conference on Data Engineering . 49\u201360.","DOI":"10.1109\/ICDE.2016.7498228"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137643"},{"key":"e_1_3_2_33_2","article-title":"Two-sided online micro-task assignment in spatial crowdsourcing","author":"Tong Yongxin","year":"2019","unstructured":"Yongxin Tong, Yuxiang Zeng, Boling Ding, Libin Wang, and Lei Chen. 2019. Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Transactions on Knowledge and Data Engineering 33, 5 (2019), 2295\u20132309.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00133"},{"key":"e_1_3_2_35_2","first-page":"295","article-title":"On the number of successes in independent trials","volume":"3","author":"Wang Yuan H.","year":"1993","unstructured":"Yuan H. Wang. 1993. On the number of successes in independent trials. Statistica Sinica 3 (1993), 295\u2013312.","journal-title":"Statistica Sinica"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00992698"},{"key":"e_1_3_2_37_2","unstructured":"Chen-Yu Wei Yi-Te Hong and Chi-Jen Lu. 2016. Tracking the best expert in non-stationary stochastic environments. In Proceedings of the 30th International Conference on Neural Information Processing Systems . 3979\u20133987."},{"key":"e_1_3_2_38_2","unstructured":"T. Wo H. Wei Y. Wang et\u00a0al. 2016. Zest: A hybrid model on predicting passenger demand for chauffeured car. In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management . 2203\u20132208."},{"key":"e_1_3_2_39_2","unstructured":"Lijun Zhang Shiyin Lu and Zhi-Hua Zhou. 2018. Adaptive online learning in dynamic environments. In Proceedings of the 32nd International Conference on Neural Information Processing Systems . 1330\u20131340."},{"key":"e_1_3_2_40_2","unstructured":"Lijun Zhang Tianbao Yang Rong Jin and Zhi-Hua Zhou. 2018. Dynamic regret of strongly adaptive methods. In Proceedings of the 35th International Conference on Machine Learning . 5882\u20135891."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3502734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:09:47Z","timestamp":1750183787000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3502734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,9]]},"references-count":39,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3502734"],"URL":"https:\/\/doi.org\/10.1145\/3502734","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,9]]},"assertion":[{"value":"2021-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}