POND: Pessimistic-Optimistic oNline Dispatching
This work addresses online dispatching challenges for applications like ride-sharing or logistics, offering a solution with theoretical guarantees and practical performance.
The paper tackles the problem of constrained online dispatching with unknown distributions by proposing the POND algorithm, which achieves O(√T) regret and O(1) constraint violation, as validated by experiments on synthetic and real datasets.
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(\sqrt{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.