Chapter Summary

Chapter Summary

Key Points

• 1.

  Online coded caching addresses dynamic demand. Time is first-class; cache updates per round. Regret vs best static MAN placement is the standard metric.

• 2.

  Sublinear regret. Adversarial: $\mathcal{R}_T = O(\sqrt{T K \log N})$. Stochastic: $\mathcal{R}_T = O(\log T)$. Warmup penalty is small; asymptotically matches static MAN.

• 3.

  FTPL (Follow-the-Perturbed-Leader) is a canonical algorithm achieving these bounds. Practical implementation uses parameterized placements for scalability.

• 4.

  LRU and LFU miss the coded multicasting gain. Their regret against coded MAN is linear in $T$. Factor $1 + K\mu$ improvement available but untapped in production.

• 5.

  Non-stationary demand. Real workloads drift; standard log-regret breaks. Dynamic regret bounded by $O(T^{2/3} V_T^{1/3})$, where $V_T$ is the path length of optimal placement.

• 6.

  Concept drift handling. Sliding windows, exponential weighting, change-point detection, ML-based prediction. Production CDNs use LRU + ML popularity prediction — no coded augmentation yet.

• 7.

  Research-practice gap. Coded online caching provides provable $O(\sqrt{T})$ regret with $1 + K\mu$ multicasting gain — but production deployment is a research opportunity, requiring coded-aware admission logic.