Optimal task assignment policy improves resource reuse rewards
Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources
Machine LearningPerformance
Summary
Assigning tasks to busy but reusable resources such as call center agents or peer reviewers is a common but tricky problem where tasks arrive randomly and must be immediately matched to available servers. The authors study this by modeling it as a type of 'multi-armed bandit' problem with changing contexts. They develop a mathematical policy, called Lag, that helps decide task assignments to maximize long-term rewards. Tested on real and synthetic data, their policy consistently outperforms simpler methods and nearly matches the best possible theoretical reward.
What this means in practice
- •For call center managers: Assign incoming calls efficiently to agents with varying skills to improve long-run customer service rewards.
- •For peer review coordinators: Match submitted papers to reviewers with relevant expertise under time constraints, increasing overall review quality.
Authors
Keerthana Gurushankar
Abstract
We study online task assignment with reusable resources. This problem arises in peer reviewer assignment, skill-based call routing, rideshare matching, emergency dispatch, and crowdsourcing: Tasks arrive according to a geometric process and must be immediately assigned to servers that become temporarily busy, yielding rewards that depend on the task-server pair. The goal is to maximize long-run average reward. We cast the problem as a contextual restless multi-armed bandit (CRMAB). We derive an occupancy-measure LP (OCC-LP) that upper-bounds the reward of any work-conserving policy. From its dual we obtain Lag, a closed-form index policy. We introduce a scaling regime in which the number of copies of each server and the number of arrivals per step grow together. This regime yields the first deterministic fluid limit for a contextual bandit. In it, Lag is asymptotically optimal. Finally, we evaluate our algorithms on peer review datasets and call center routing. The Lagrangian index achieves 83-99% of the LP upper bound across all load levels. Moreover, the Lagrangian index policy significantly outperforms the natural greedy assignment scheme, improving reward by up to 12.3% on journal data and 36% on structured synthetic instances.