Improved Analysis of Adaptive Task Allocation and Non-Stationary Processing Times
Abstract
We study the task allocation problem, where our goal is to develop an online algorithm that efficiently distributes tasks among workers based on their computational performance. This task is challenging since computation times are random and non-stationary in practice. Recent works have introduced different online algorithms to address this problem. One of them is Adaptive Task Allocation (ATA), a bandit-style algorithm. However, previous theoretical guarantees leave substantial room for improvement, and existing methods are designed only for stationary computation times. Using new proof techniques, our work establishes an improved analysis of ATA with better gap-dependent and gap-independent regret guarantees, improving upon all previous approaches. We also introduce a new method, Sliding Window Adaptive Task Allocation (SW-ATA), designed for more practical non-stationary environments. Finally, we prove new lower bounds in both the stationary and non-stationary settings.
Related
- Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking
- Two improved Liouville-type theorems for the 3D stationary tropical climate model without temperature assumptions
- Strong NP-Hardness and Approximation Algorithm for Weighted Tardiness with Release Dates and Identical Processing Times
- Control Allocation with Adaptive Augmentation for Aerodynamic Optimization of Trailing Edge Morphing Aircraft
- Mission Efficiency Optimization in Low-Altitude Economy: Adaptive Power Allocation for Coordinating Heterogeneous Aircraft Swarms
BibTeX
@misc{begunov2026improved,
title = {{Improved Analysis of Adaptive Task Allocation and Non-Stationary Processing Times}},
author = {Grigory Begunov and Ilgam Latypov and Yuriy Dorn and Alexander Tyurin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18265},
eprint = {2610.18265},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18265},
}
RIS
TY - UNPB
TI - Improved Analysis of Adaptive Task Allocation and Non-Stationary Processing Times
AU - Grigory Begunov
AU - Ilgam Latypov
AU - Yuriy Dorn
AU - Alexander Tyurin
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18265
UR - https://arxiv.org/abs/2610.18265
AB - We study the task allocation problem, where our goal is to develop an online algorithm that efficiently distributes tasks among workers based on their computational performance. This task is challenging since computation times are random and non-stationary in practice. Recent works have introduced different online algorithms to address this problem. One of them is Adaptive Task Allocation (ATA), a bandit-style algorithm. However, previous theoretical guarantees leave substantial room for improvement, and existing methods are designed only for stationary computation times. Using new proof techniques, our work establishes an improved analysis of ATA with better gap-dependent and gap-independent regret guarantees, improving upon all previous approaches. We also introduce a new method, Sliding Window Adaptive Task Allocation (SW-ATA), designed for more practical non-stationary environments. Finally, we prove new lower bounds in both the stationary and non-stationary settings.
ER -