Prerequisites & Notation

Before You Begin

This chapter addresses dynamic demand: libraries change over time, new files appear, popularity shifts. Prerequisites: static MAN, some exposure to online learning.

MAN coded caching (Ch 2)(Review ch02)
Self-check: What does the static MAN scheme assume about demand?
Decentralized caching (Ch 13)(Review ch13)
Self-check: How does random placement compare to MAN?
Zipf / popularity distributions (Ch 13)(Review ch13)
Self-check: What is a Zipf- $\alpha$ distribution?
Online learning basics (regret, FTL, FTPL)
Self-check: What is regret vs. hindsight optimum in online learning?
Stochastic vs adversarial models
Self-check: Distinguish i.i.d., adversarial, and smoothed inputs.

Notation for This Chapter

Symbols for dynamic caching and online learning.

Symbol	Meaning	Introduced
$T$	Number of time rounds	s01
$\mathbf{d}^{(t)}$	Demand vector at round $t$	s01
$\mathcal{Z}^{(t)}$	Cache content at user $k$ at time $t$	s01
$\mathcal{R}_T$	Regret after $T$ rounds: total extra delivery cost vs offline optimum	s02
$\eta$	Learning rate in online algorithms	s02
$\pi$	Demand distribution (unknown, possibly non-stationary)	s01
$\mathcal{A}$	Online algorithm / policy	s02

← Ch 19 Online Model: Dynamic Demand, Dynamic Cache