Online Dynamic Acknowledgement with Learned Predictions
Sungjin Im Benjamin Moseley Chenyang Xu Ruilong Zhang
We revisit the online dynamic acknowledgment problem. In the problem, a
sequence of requests arrive over time to be acknowledged, and all outstanding
requests can be satisfied simultaneously by one acknowledgement. The goal of
the problem is to minimize the total request delay plus acknowledgement cost.
This elegant model studies the trade-off between acknowledgement cost and
waiting experienced by requests. The problem has been well studied and the
tight competitive ratios have been determined. For this well-studied problem,
we focus on how to effectively use machine-learned predictions to have better
performance.
  We develop algorithms that perform arbitrarily close to the optimum with
accurate predictions while concurrently having the guarantees arbitrarily close
to what the best online algorithms can offer without access to predictions,
thereby achieving simultaneous optimum consistency and robustness. This new
result is enabled by our novel prediction error measure. No error measure was
defined for the problem prior to our work, and natural measures failed due to
the challenge that requests with different arrival times have different effects
on the objective. We hope our ideas can be used for other online problems with
temporal aspects that have been resisting proper error measures.