Source-linked AI summary
Simultaneous Competitive and Regret Guarantees for TCP Acknowledgment
Tsubasa Harada, Yasushi Kawase, Hanna Sumita
TL;DR
For TCP acknowledgment, the challenge is to learn from online experts without giving up a worst-case competitive guarantee. The paper combines expert learning with a budget tied to its permitted cost, guaranteeing per-realization (2 + ε)-competitiveness alongside sublinear regret, with lower bounds matching the dependence on OPT, k, and ε.
Problem
A competitive guarantee alone does not ensure near-best performance for a particular arrival pattern; the question is whether an algorithm can preserve near-2 competitiveness while achieving sublinear regret against the best expert.
Source: §1 · p. 1Method
The algorithm controls the cost of switching between experts and uses the gap between its permitted competitive cost and its current cost to manage learning.
Source: §1.2 · p. 2, §3.2 · p. 6Results
The algorithm guarantees realized cost at most (2 + ε)OPT and sublinear expected regret for fixed k and ε, with lower bounds matching the dependence on OPT, k, and ε.
Source: §1.1 · p. 2Takeaways & Limitations
Allowing ε > 0 is necessary for sublinear regret: exact 2-competitiveness forces Ω(OPT) expected regret on some inputs with arbitrarily large OPT.
Source: §1.1 · p. 2The guarantees are analyzed for an oblivious adversary: the input is fixed independently of all random choices.
Source: §2 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
TCP acknowledgment policies must balance acknowledgment and packet-waiting costs, and competitive guarantees alone do not ensure performance close to the best policy for a particular input. The paper combines expert learning with a worst-case cost guarantee, using switching control and a budget tied to the permitted competitive bound.
1.1 Our results
- The algorithm guarantees realized cost at most (2 + ε)OPT on every input while achieving sublinear expected regret for fixed k and ε.Its regret bound depends on ε through an additive O(log(1/ε)) term.Source: §1.1 · p. 2
- For k ≥2, lower bounds match the upper bound’s dependence on OPT, k, and ε; exact 2-competitiveness forces Ω(OPT) expected regret on some inputs.The latter obstruction holds for inputs with arbitrarily large OPT.Source: §1.1 · p. 2
1.2 Overview of techniques
- At expert switches, the learner acknowledges pending packets when needed, keeping its pending set within the selected expert’s and adding at most one acknowledgment per switch.This bounds the learning problem’s switching cost by one; the method uses correlated multiplicative-weights choices to control switching frequency.Source: §1.2 · p. 2
- The algorithm tracks Φ(t) = (2 + ε)OPT(t) − CALG(t) as the remaining cost budget, then uses budget-sized learning blocks and a separate procedure when the budget is too small.The small-budget procedure raises the budget by at least one before returning and contributes O(log(1/ε)) expected regret overall.Source: §1.2 · pp. 2–3
1.3 Related work
- The paper distinguishes its additive comparison with the best online expert from prior guarantees based on predictions of the arrival sequence [Im et al. 2023].It requires no assumption on prediction accuracy.Source: §1.3 · p. 3
2 Model
The model specifies online packet arrivals, acknowledgment decisions, and the combined acknowledgment and waiting-cost objective. It also defines the expert benchmark and the input and randomness assumptions for the guarantees.
2 Model
- Packets arrive online, and the algorithm does not know when the input ends or the number of packets in advance.At each time it observes all arrivals before deciding whether to acknowledge pending packets.Source: §2 · p. 4
- Each acknowledgment costs one and serves all pending packets; each packet’s waiting cost is the time from its arrival until acknowledgment.The objective sums acknowledgment costs and packet waiting costs.Source: §2 · p. 4
- OPT is the minimum total cost with the input known in advance, while expected regret compares the algorithm with the expert having the lowest realized cost on the same input.The regret expectation is over the algorithm’s randomness.Source: §2 · p. 4
- The input is fixed independently of random choices, and the learner can simulate each expert online and observe its decisions and realized costs.Expert randomness is independent of the learner’s; expectations are taken over both unless stated otherwise.Source: §2 · p. 4
3 Simultaneous competitive and regret guarantees
The section combines expert learning with a competitive-cost guarantee for TCP acknowledgment. It bounds realized cost by (2 + ε) OPT while achieving sublinear expected regret for fixed k and ε.
3 Simultaneous competitive and regret guarantees
- The algorithm’s realized cost is at most (2 + ε) OPT on every input, with sublinear expected regret for fixed k and ε.The theorem states the competitive guarantee for every realization of the algorithm’s random choices.Source: §3 · p. 4
3.1 Competitive algorithms
- The greedy algorithm is 2-competitive, while AR(z) acknowledges when j pending packets have each waited at least z/j.AR(0) acknowledges each packet immediately upon arrival.Source: §3.1 · p. 5
3.2 Learning with switching costs
- AL simulates the experts in rounds ending at an expert acknowledgment or one unit of waiting cost; switching experts adds at most one synchronization cost.Each expert’s loss per round is at most 2, and synchronization is the acknowledgment sent at an expert switch.Source: §3.2 · pp. 5–6
3.3 Increasing the budget
- The available budget is the extra cost allowed by the competitive bound; threshold algorithms increase it at expected cost O(log(1/ε), versus O(1/ε) for fresh greedy intervals.The threshold procedure uses independent fair-coin choices and monitors the budget stopping condition continuously.Source: §3.3 · pp. 6–7
3.4 The full algorithm
The algorithm runs in blocks sized by its available competitive budget, combining a learner with a randomized threshold algorithm. Block costs preserve the realized competitive guarantee, while the proof sums expert-regret bounds and budget-recovery costs.
3.4 The full algorithm
- Fresh learner and threshold simulations run within each block, while the experts continue their executions across blocks.The learner switches between simulations using cost-difference thresholds; switching may require acknowledging pending packets.Source: §3.4 · pp. 8–9
- Each block costs at most half its starting budget in every realization, preserving a nonnegative budget and the competitive guarantee.For a block starting at t0, its cost is at most 16b = 16Φ(t0)/θ ≤ Φ(t0)/2.Source: §3.4 · pp. 8, 11
- The first block requires budget recovery, whose total expected cost is O(log(1/ε)); subsequent recovery runs have expected total cost O(1 + log(1/ε)).The proof bounds the expected number of recovery runs by O(1), then sums their conditional expected costs.Source: §3.4 · pp. 11–12
- The regret proof sums blockwise costs against the cheapest realized expert and adds the budget-recovery costs.For each block, the comparison includes expert cost accrued during that block, including waiting by packets already pending at its start.Source: §3.4 · pp. 8, 13
4 Lower bounds
The lower bounds isolate the regret costs of requiring a competitive ratio near two and of learning among many experts. Together they match the upper bound's dependence on OPT, k, and ε; at ratio two, sublinear regret is impossible.
4.1 Dependence on ε
- With a (2 + ε) guarantee for 0 < ε ≤ 1/16, the separated-packet construction forces regret Ω(min{n, log(1/ε)}).The argument bounds the delay of each initial packet under the realized competitive guarantee.Source: §4.1 · pp. 13, 15
- At competitive ratio 2, every realization incurs regret Ω(OPT) on the separated-packet inputs σ_n, ruling out sublinear regret.For 0 < ε ≤ 1/16, the construction instead gives Ω(min{n, log(1/ε)}) regret.Source: §4.1 · pp. 13, 15
4.2 Dependence on the number of experts
- For every ε∈(0, 1), some fixed input with h ≤ OPT ≤ 3h/2 has regret Ω(min{h, √h log k + log(1/ε)}), matching Theorem 3.1’s upper bound up to constant factors.Source: §4.2 · pp. 16–17
- A distribution over packet intervals gives expected regret at least OPT/6 against the offline optimum for some input, even without a competitive requirement.The input can be chosen with h ≤ OPT ≤ 3h/2.Source: §4.2 · p. 17
A.1 Proof of Lemma 3.2
The proof compares a threshold algorithm with arbitrary offline schedules by charging waiting costs and identifying intervals where the schedule delays packets.
A.1 Proof of Lemma 3.2
- Each completed AR(1) interval contains an acknowledgment of AR(z), giving N1(t) ≤ Nz(t).The triggering packets in each completed AR(z) interval contribute at least z waiting cost.Source: §A.1 · pp. 18–19
- After an offline schedule acknowledges a packet, waiting accumulated by AR(z) on packets still pending can be charged to that acknowledgment at cost at most z.If q packets remain pending, AR(z) serves them within z/q further time.Source: §A.1 · p. 19
- Intervals of AR(1) without a schedule acknowledgment leave the schedule with at least 1 − z more waiting cost than AR(z), yielding a lower bound on schedule cost.The triggering packet sets are disjoint, so these savings do not overlap with the post-acknowledgment charges.Source: §A.1 · p. 19
A.2 Proof of Lemma 3.3
The proof uses threshold-algorithm acknowledgment counts to relate offline cost to algorithm cost, then averages cost bounds for different thresholds.
A.2 Proof of Lemma 3.3
- For threshold u, OPT(t) is at least uNu(t) + (1 − u)N1(t), and the threshold algorithm's cost is bounded using those counts.The proof also uses Nu(t) ≤ OPT(t)/u.Source: §A.2 · p. 19
- The deterministic cost bounds follow by combining the threshold-count inequalities with the offline-cost lower bound.The proof first derives bounds for each threshold, then averages for the expectation.Source: §A.2 · p. 19
- Averaging the cost bounds for u = 1 and u = x gives an expected-cost bound for the randomized threshold choice.The derivation uses that Nx(t) ≥ N1(t) and x(Nx(t) − N1(t)) + N1(t) ≤ OPT(t).Source: §A.2 · p. 19
A.3 Proof of Lemma 3.4
The proof bounds synchronized redraws and shows that expert selection follows the normalized weights. It then bounds the expected excess in terms of the learning rate and expert loss.
A.3 Proof of Lemma 3.4
- The synchronization rule gives Y ≤ L + ν_L, where ν_L counts redraws during the first h rounds, including redraws that select the same expert.Source: §A.3 · p. 19
- By induction using the retention and redraw rules, the probability of selecting expert i at round s equals p_i,s = w_i,s/W_s.Source: §A.3 · p. 19
- E[Y] − L_i ≤ (1+η)L̄ − L_i ≤ (2η+η²)L_i + 2(1+η)ln k when η ≤ 1/2.Source: §A.3 · p. 20