# Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 19 references that are in the map.
- First posted on arXiv 9 Oct 2026.

## Builds on (most cited first, 9 of 9)

- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Online metric algorithms with untrusted predictions](https://mlsanity.com/paper/2003.02144/) (2020)
- [A Tale of Two Metrics: Simultaneous Bounds on Competitiveness and Regret](https://mlsanity.com/paper/1508.03769/) (2015)
- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Best of Both Worlds in Online Control: Competitive Ratio and Policy Regret](https://mlsanity.com/paper/2211.11219/) (2022)
- [Online Dynamic Acknowledgement with Learned Predictions](https://mlsanity.com/paper/2305.18227/) (2023)
- [Online Matching with Delays and Size-based Costs](https://mlsanity.com/paper/2408.08658/) (2024)
- [Online TCP Acknowledgment under General Delays](https://mlsanity.com/paper/2604.13428/) (2026)
- [Online Algorithms for Repeated Optimal Stopping: Balancing Baseline Guarantees and Regret](https://mlsanity.com/paper/2511.04484/) (2025)

## Abstract (arXiv)

We study simultaneous competitive and regret guarantees for TCP acknowledgment. Each acknowledgment serves all pending packets, and the objective is to minimize the total acknowledgment and waiting costs. It is well known that no deterministic online algorithm achieves a competitive ratio better than 2. Given k randomized online experts and 0<varepsilon<1, we construct a randomized online algorithm whose realized total cost is always at most (2+varepsilon) times the offline optimal cost OPT and whose expected regret against the expert with the smallest realized cost is O(√OPTlog(k+1)+log(1/varepsilon)). The algorithm requires no advance knowledge of the number of packets or OPT. Our algorithm controls switching costs between experts and uses the gap between the permitted competitive bound and its current cost to determine when to learn. We also prove lower bounds showing that, for k≥ 2, this regret bound is asymptotically optimal in OPT, k, and varepsilon, and that varepsilon>0 is necessary for sublinear regret.