Efficient Sequential UCB-based Hungarian Algorithm for Assignment Problems

Yuyang Shi, Yajun Mei

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publication2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9798350399981
DOIs
StatePublished - 2022
Event58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022 - Monticello, United States
Duration: Sep 27 2022Sep 30 2022

Publication series

Name2022 58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022

Conference

Conference58th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2022
Country/TerritoryUnited States
CityMonticello
Period9/27/229/30/22

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Computer Vision and Pattern Recognition
  • Signal Processing
  • Control and Optimization

Fingerprint

Dive into the research topics of 'Efficient Sequential UCB-based Hungarian Algorithm for Assignment Problems'. Together they form a unique fingerprint.

Cite this