arXiv：cs.LG· Keerthana Gurushankar·· 2 小时前
Lag：可复用资源在线分配的平均场最优策略
Lag: A Mean-Field Optimal Policy for Online Assignment with Reusable Resources
AI 导读
研究针对可复用资源的在线任务分配问题，将其建模为上下文 restless 多臂老虎机（CRMAB），并通过占用度量 LP（OCC-LP）的对偶推出闭式索引策略 Lag。在服务器副本数与到达量同步增长的缩放机制下，Lag 具有渐近最优性。在同行评审数据集与呼叫中心路由上，Lag 达到 LP 上界的 83-99%，奖励比贪心分配最多提升 12.3%（期刊数据）和 36%（结构化合成实例）。
正文
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.
| Subjects: | Machine Learning (cs.LG); Performance (cs.PF); Optimization and Control (math.OC) |
| Cite as: | arXiv:2610.19038 [cs.LG] |
| (or arXiv:2610.19038v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2610.19038 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Keerthana Gurushankar [view email]
[v1]
Tue, 13 Oct 2026 18:28:08 UTC (1,264 KB)
来源：arXiv：cs.LG · arxiv.org