# POND: Pessimistic-Optimistic oNline Dispatching

arXiv: https://arxiv.org/abs/2010.09995 · HTML: https://mlsanity.com/paper/2010.09995/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Oct 2020.

## Built on by (most cited first, 7 of 7)

- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Job Dispatching Policies for Queueing Systems with Unknown Service Rates](https://mlsanity.com/paper/2106.04707/) (2021)
- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [GOSH: Task Scheduling Using Deep Surrogate Models in Fog Computing Environments](https://mlsanity.com/paper/2112.08916/) (2021)
- [A Lyapunov-Based Methodology for Constrained Optimization with Bandit Feedback](https://mlsanity.com/paper/2106.05165/) (2021)
- [A Survey on Distributed Online Optimization and Game](https://mlsanity.com/paper/2205.00473/) (2022)
- [Learning to Schedule Online Tasks with Bandit Feedback](https://mlsanity.com/paper/2402.16463/) (2024)

## Abstract (arXiv)

This paper considers constrained online dispatching with unknown arrival, reward and constraint distributions. We propose a novel online dispatching algorithm, named POND, standing for Pessimistic-Optimistic oNline Dispatching, which achieves O(√T) regret and O(1) constraint violation. Both bounds are sharp. Our experiments on synthetic and real datasets show that POND achieves low regret with minimal constraint violations.