Bandit Learning for Online Scheduling with Immediate Decision

Zilong Wang, Yuhao Zhang, Zhewei Wei, Shuai Li
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:7168-7199, 2026.

Abstract

Motivated by latency-critical streaming domains such as IoT data processing and cloud resource allocation, we investigate the problem of Online Scheduling with Immediate Decision, where a scheduler must instantly decide whether to accept an incoming task without buffering. We consider a system with $M$ identical machines handling tasks with fixed processing lengths and stochastic, initially unknown rewards. A distinct feature of our model is preemption with abandonment: while a machine can interrupt a running task to accept a more valuable new arrival, the preempted task is permanently discarded, yielding no reward and no feedback, which is crucial for learning. We first analyze the setting with known rewards, deriving a worst-case competitive ratio lower bound and proposing the near-optimal Maximum Remaining Density First (MRDF) algorithm. For the challenging case of unknown rewards with censored feedback, we design an efficient bandit algorithm, Scheduling Upper Confidence Bound (S-{UCB}), which balances exploration and exploitation to achieve an $O(\log T)$ regret over time horizon $T$. Experimental results demonstrate the efficacy of the proposed algorithms against standard baselines.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-wang26g, title = {Bandit Learning for Online Scheduling with Immediate Decision}, author = {Wang, Zilong and Zhang, Yuhao and Wei, Zhewei and Li, Shuai}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {7168--7199}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/wang26g/wang26g.pdf}, url = {https://proceedings.mlr.press/v337/wang26g.html}, abstract = {Motivated by latency-critical streaming domains such as IoT data processing and cloud resource allocation, we investigate the problem of Online Scheduling with Immediate Decision, where a scheduler must instantly decide whether to accept an incoming task without buffering. We consider a system with $M$ identical machines handling tasks with fixed processing lengths and stochastic, initially unknown rewards. A distinct feature of our model is preemption with abandonment: while a machine can interrupt a running task to accept a more valuable new arrival, the preempted task is permanently discarded, yielding no reward and no feedback, which is crucial for learning. We first analyze the setting with known rewards, deriving a worst-case competitive ratio lower bound and proposing the near-optimal Maximum Remaining Density First (MRDF) algorithm. For the challenging case of unknown rewards with censored feedback, we design an efficient bandit algorithm, Scheduling Upper Confidence Bound (S-{UCB}), which balances exploration and exploitation to achieve an $O(\log T)$ regret over time horizon $T$. Experimental results demonstrate the efficacy of the proposed algorithms against standard baselines.} }
Endnote
%0 Conference Paper %T Bandit Learning for Online Scheduling with Immediate Decision %A Zilong Wang %A Yuhao Zhang %A Zhewei Wei %A Shuai Li %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-wang26g %I PMLR %P 7168--7199 %U https://proceedings.mlr.press/v337/wang26g.html %V 337 %X Motivated by latency-critical streaming domains such as IoT data processing and cloud resource allocation, we investigate the problem of Online Scheduling with Immediate Decision, where a scheduler must instantly decide whether to accept an incoming task without buffering. We consider a system with $M$ identical machines handling tasks with fixed processing lengths and stochastic, initially unknown rewards. A distinct feature of our model is preemption with abandonment: while a machine can interrupt a running task to accept a more valuable new arrival, the preempted task is permanently discarded, yielding no reward and no feedback, which is crucial for learning. We first analyze the setting with known rewards, deriving a worst-case competitive ratio lower bound and proposing the near-optimal Maximum Remaining Density First (MRDF) algorithm. For the challenging case of unknown rewards with censored feedback, we design an efficient bandit algorithm, Scheduling Upper Confidence Bound (S-{UCB}), which balances exploration and exploitation to achieve an $O(\log T)$ regret over time horizon $T$. Experimental results demonstrate the efficacy of the proposed algorithms against standard baselines.
APA
Wang, Z., Zhang, Y., Wei, Z. & Li, S.. (2026). Bandit Learning for Online Scheduling with Immediate Decision. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:7168-7199 Available from https://proceedings.mlr.press/v337/wang26g.html.

Related Material