Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources
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.
Related
- Regularized Coupling Maps on Matrix Polytopes: From Assignment to Graph Matching and Optimal Transport
- Online tensor learning: Computational and statistical trade-offs, adaptivity and optimal regret
- Optimal Multiclass Online Regret with Arbitrary Label Spaces
- Optimal Multi-way Decision Trees for Stratified Sampling in Online Controlled Experiments
- Design-Driven Inference for Online Experiments: Jointly Optimal Evidence Collection, Testing, and Estimation
BibTeX
@misc{gurushankar2026meanfield,
title = {{Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources}},
author = {Keerthana Gurushankar},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.19038},
eprint = {2610.19038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.19038},
}
RIS
TY - UNPB
TI - Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources
AU - Keerthana Gurushankar
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.19038
UR - https://arxiv.org/abs/2610.19038
AB - 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.
ER -