Track trials, findings, and clinical evidence as it lands.
Search papers, labs, and topics across Lattice.
This paper introduces a randomized online algorithm for TCP acknowledgment that achieves a $(2+\varepsilon)$-competitive ratio against the offline optimal cost and an expected regret of $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$ against $k$ randomized experts. The algorithm dynamically balances learning from experts with minimizing immediate costs by controlling switching costs and using the gap between the competitive bound and current cost to guide learning. This work establishes near-optimal bounds for simultaneous competitive and regret guarantees in this setting, demonstrating the necessity of $\varepsilon>0$ for sublinear regret.
A single randomized algorithm simultaneously achieves near-optimal $(2+\varepsilon)$-competitiveness and sublinear regret for TCP acknowledgment, proving $\varepsilon>0$ is essential for the latter.
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 $\mathrm{OPT}$ and whose expected regret against the expert with the smallest realized cost is $O(\sqrt{\mathrm{OPT}\log(k+1)}+\log(1/\varepsilon))$. The algorithm requires no advance knowledge of the number of packets or $\mathrm{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\ge 2$, this regret bound is asymptotically optimal in $\mathrm{OPT}$, $k$, and $\varepsilon$, and that $\varepsilon>0$ is necessary for sublinear regret.