Pure tail constraints clarify risks in adaptive online decision problems
Pure Tail Constraints for Online Problems
Data Structures and Algorithms
Summary
Sometimes computers must make decisions step-by-step without knowing the future, and they want to avoid really bad outcomes. This paper studies how to balance doing well on average with avoiding worst-case results in such situations. The authors analyze fundamental problems where decisions adapt based on incoming information, like managing data packet acknowledgments in networks. They find the best possible tradeoffs between expected and worst-case performance and show new limits on how well algorithms can do in these adaptive scenarios.
What this means in practice
- •For network schedulers: Improve TCP acknowledgment strategies under variable traffic by understanding limits of adaptive online decision making.
- •For online auction designers: Design bidding algorithms that optimally balance average success with worst-case performance using derived tradeoff frontiers.
A theory result. No direct application yet.
Authors
Mateusz Basiak, Marcin Bienkowski, Yongho Shin, Agnieszka Tatarczuk
Abstract
Controlling tail risk is an important objective in online optimization, and recently it has been studied in the context of competitive analysis. Continuing this line of research, we investigate pure tail constraints, which capture the tradeoff between expected and worst-case competitiveness. For two fundamental search problems, online bidding and line search, we derive the Pareto-optimal frontiers of this tradeoff. We then investigate another classic problem, TCP acknowledgment, which has structure similar to the iterated ski rental problem. There, we construct an algorithm whose tradeoff coincides with the known Pareto-optimal tradeoff for ski rental. The lower bounds for this problem are substantially more involved as the problem exhibits adaptive structure: an online algorithm observes requests of the adversary (packet arrivals) and may adaptively adjust its actions (acknowledgments) on this basis. We emphasize that all previous work on tail risk in the context of competitive analysis was restricted to non-adaptive problems, where the feedback given to an algorithm was essentially limited to a binary indicator of whether the algorithm has succeeded or not. Nonetheless, we identify a set of constraints implied by tail bounds in this adaptive setting, and show that they imply a nontrivial lower bound on the TCP acknowledgment problem.