No-Regret Caching with Delayed Hits

Delayed hits occur when requests arrive while a previous miss for the same item is still being fetched. They break the equivalence between hit ratio and latency because caching decisions depend on frequency, burst structure, and fetch latency. We develop a regret framework for delayed-hit caching, with static regret against long-term placement and switching regret against piecewise-changing workloads. We show that classical deterministic policies and randomized Marker fail to achieve no-regret guarantees, both suffering linear static regret. For stochastic arrivals, we introduce delayed-hit shadow values and propose UCB-DH, which achieves $O(\log T)$ static regret on fixed instances with positive gaps, where $T$ is the horizon. A matching gap-dependent lower bound shows that the delayed-hit latency-amplification factor is statistically unavoidable, and restarted UCB-DH gives sublinear regret for piecewise-changing workloads. For oblivious adversarial arrivals, we formulate an action-independent shadow loss and propose LA-FTPL with latency-scaled perturbations and completion-time admission. LA-FTPL achieves $O(\sqrt{KT\log N(Z^2+C_{B}Z)})$ shadow static regret, where $K$ is the cache capacity, $N$ the item universe size, $Z$ the fetch latency, and $C_B$ the maximum one-window delayed-hit penalty. With periodic restarts, it achieves $O(Z{T}^{2/3}{B}^{1/3}(K\log N{)}^{1/3})$ switching regret against comparators with at most $B$ cache changes. Experiments on synthetic and real-world traces show that our algorithms achieve sublinear regret and improve latency over the state-of-the-art baselines.