Taming the Heavy Tail: Age-Optimal Preemption
2026 IEEE International Symposium on Information Theory, ISIT 2026, Guangzhou, China, 28 June - 03 July 2026, (Full Text)
- Publication Type: Conference Paper / Full Text
- Doi Number: 10.1109/isit62367.2026.11653616
- City: Guangzhou
- Country: China
- Middle East Technical University Affiliated: Yes
Abstract
This paper studies a continuous-time joint sampling-and-preemption problem, incorporating sampling and preemption penalties under general service-time distributions. We formulate the system as an impulse-controlled piecewise-deterministic Markov process (PDMP) and derive coupled integral average-cost optimality equations via the dynamic programming principle, thereby avoiding the smoothness assumptions typically required for an average-cost Hamilton-Jacobi-Bellman quasi-variational inequality (HJB-QVI) characterization. A key invariance in the busy phase collapses the dynamics onto a one-dimensional busy-start boundary, reducing preemption control to an optimal stopping problem. Building on this structure, we develop TAILOR (TAIL-aware Optimal pReemption), an efficient policy-iteration algorithm with heavy-tail acceleration, employing a hybrid (uniform/log-spaced) action grid and a far-field linear closure. Simulations under Pareto and log-normal service times demonstrate substantial improvements over AoI-optimal non-preemptive sampling and zero-wait baselines, achieving up to a 28× reduction in average cost in heavy-tailed regimes. Finally, simulations uncover a counterintuitive insight: under preemption, delay variance, despite typically being a liability, can become a strategic advantage for information freshness.