TY - GEN
T1 - Efficient Sequential UCB-based Hungarian Algorithm for Assignment Problems
AU - Shi, Yuyang
AU - Mei, Yajun
N1 - Publisher Copyright:
© 2022 IEEE.
PY - 2022
Y1 - 2022
N2 - The assignment problem has many real-world applications such as allocations of agents and tasks for optimal utility gain. While it has been well-studied in the optimization literature when the underlying utility between every pair of agent and task is known, research is limited when the utilities are unknown and need to be learned from data on the fly. In this work, motivated by the mentor-mentee matching application in U.S. universities, we develop an efficient sequential assignment algorithm, with the objective of nearly maximizing the overall utility simultaneously for each time. Our proposed algorithm is to use stochastic binary bandit feedback to estimate the unknown utilities through the logistic regression, and then to combine the Upper Confidence Bound (UCB) method in the multi-armed bandit problem with the Hungarian algorithm in the assignment problem. We derive the theoretical bounds of our algorithm for both the estimation error and the total regret, and numerical studies are conducted to illustrate the usefulness of our algorithm.
AB - The assignment problem has many real-world applications such as allocations of agents and tasks for optimal utility gain. While it has been well-studied in the optimization literature when the underlying utility between every pair of agent and task is known, research is limited when the utilities are unknown and need to be learned from data on the fly. In this work, motivated by the mentor-mentee matching application in U.S. universities, we develop an efficient sequential assignment algorithm, with the objective of nearly maximizing the overall utility simultaneously for each time. Our proposed algorithm is to use stochastic binary bandit feedback to estimate the unknown utilities through the logistic regression, and then to combine the Upper Confidence Bound (UCB) method in the multi-armed bandit problem with the Hungarian algorithm in the assignment problem. We derive the theoretical bounds of our algorithm for both the estimation error and the total regret, and numerical studies are conducted to illustrate the usefulness of our algorithm.
UR - http://www.scopus.com/inward/record.url?scp=85142665679&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85142665679&partnerID=8YFLogxK
U2 - 10.1109/Allerton49937.2022.9929380
DO - 10.1109/Allerton49937.2022.9929380
M3 - Conference contribution
AN - SCOPUS:85142665679
T3 - 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
BT - 2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
Y2 - 27 September 2022 through 30 September 2022
ER -