Ferkans — Interactive Telecom Tutor

Real Demand Is Non-Stationary

The i.i.d. assumption underlying log-regret bounds (§20.2) is violated by real content demand:

Daily / weekly periodicity. Work-hour news vs evening entertainment; weekday vs weekend.
Viral spikes. A trending video's popularity rises and falls on $\sim$ 1-week timescales.
Long-tail drift. Catalog popularity distribution reshapes with new content uploads.
Seasonal shifts. Summer sports vs winter sports; movie release calendar.

Under non-stationary demand, standard log-regret bounds fail. Regret against a single static optimum becomes unbounded. The correct benchmark is dynamic regret: compare against a piecewise-constant or slowly-changing reference.

Definition:
Dynamic Regret

For a non-stationary demand process, dynamic regret is $\mathcal{R}_T^\text{dyn} \;=\; \sum_{t=1}^T C^{(t)}(\mathcal{A}^{(t)}) - \sum_{t=1}^T \min_\mathbf{Z} C^{(t)}(\mathbf{Z}).$ The reference is the best per-round placement (knows $\mathbf{d}^{(t)}$ before committing). Much stronger than static regret.

Under non-stationarity measured by total variation $V_T$ (how much the optimal placement drifts over $T$ rounds), dynamic regret is bounded by $O(T^{2/3} V_T^{1/3})$ in general.

Dynamic regret can exceed static regret because the reference adapts. The bound $T^{2/3} V_T^{1/3}$ reveals the tradeoff: slow drift ( $V_T$ small) allows tight regret; fast drift ( $V_T \to T$ ) makes learning impossible.

Theorem: Dynamic Regret for Coded Online Caching

For coded online caching under non-stationary demand with path length $V_T = \sum_t \|\pi^{(t)} - \pi^{(t-1)}\|$ , there exists an algorithm (with restart / tracking mechanism) achieving $\mathcal{R}_T^\text{dyn} \;=\; O\!\left(T^{2/3} V_T^{1/3} \sqrt{\log N}\right).$ For slow drift ( $V_T = T^\gamma$ with $\gamma < 1$ ), regret is sublinear.

The algorithm uses a sliding-window estimate of recent demands or a restart mechanism when drift is detected. Standard machinery from online learning with drifting environments. The $T^{2/3}$ scaling is inherent: tracking a changing target is harder than tracking a fixed one.

Proof

Window size selection

Use window $W = T^{2/3}$ rounds. Within a window, drift is bounded; average KL divergence from current $\pi^{(t)}$ is $\lesssim V_T / T$ .

Per-window regret

Within-window regret: $O(\sqrt{W \log N})$ . Number of windows: $T/W = T^{1/3}$ .

Total regret

Sum: $T^{1/3} \cdot \sqrt{W \log N} = T^{2/3} V_T^{1/3} \sqrt{\log N}$ (roughly). $\blacksquare$

Adaptive vs Static Placement Over Time

Delivery rate convergence of adaptive online caching vs static MAN placement. Adaptive approaches oracle-optimal as it learns. Static stays at MAN baseline forever.

Parameters

Users K10

Memory ratio μ0.2

Drift Detection Techniques

Detecting non-stationarity in real-time enables adaptive schemes to restart or re-weight:

Sliding window. Use the last $W$ observations; drop older. Simple; requires tuning $W$ .
Exponential weighting. Weight observation $t$ by $e^{-\lambda (T - t)}$ . Continuous; no window boundary.
Change-point detection. Statistical tests (CUSUM, Shiryaev-Roberts) to identify drift events. Restart the estimator at detected change points.
ML-based predictors. Neural networks predicting $\pi^{(t+1)}$ from recent history. Powerful but harder to theoretically analyze.

Practical systems use combinations: windowed estimation + ML prediction for popular-shift forecasting.

Example: Trending Video: Concept Drift in Action

A trending video's popularity rises 100× over 1 hour (spike), then decays exponentially over 3 days. Design an online caching response.

Solution

Detection

Request count exceeds 10× recent average for 5 consecutive windows — trigger rapid cache refresh.

Re-placement

Admit trending video into caches of all edge nodes serving affected population. Evict least-popular current items.

Delivery

During 1-hour surge, trending video's broadcast is coded over all requesting users — massive multicast gain. Delivery rate near-zero additional bandwidth.

Decay

After 3 days, popularity returns to baseline. Evict from edge; re-admit if another surge occurs.

Dynamic regret analysis

Over 4-day horizon with one spike: $V_T$ bounded. Sublinear dynamic regret achievable.

🔧Engineering Note

How Production CDNs Handle Drift

Real CDNs' approaches to non-stationary demand:

Fast admission, slow eviction. Admit new items quickly; evict only when cache full. LRU does this implicitly.
Popularity prediction. ML models (on publisher metadata: upload time, social signals) predict popularity. Cache forward-looking.
Geographic specialization. Edge caches specialize per region; trending local content cached locally.
Pre-positioning. For scheduled events (live sports, movie releases), preload caches.

Coded online caching could augment each with multicasting gain — but integration requires coded-delivery-aware admission logic, not yet commercialized.

Practical Constraints

•
Akamai: regional pre-positioning for scheduled events
•
Netflix: Popularity-based prediction + edge caching
•
Meta/TikTok: Heavy ML-based popularity prediction
•
Coded augmentation: research frontier

,

Common Mistake: Don't Assume Stationarity Blindly

Mistake:

Using i.i.d. log-regret bounds to claim performance in non-stationary regimes.

Correction:

Log-regret is proven under i.i.d. Under concept drift, log-regret may be infinite. Always verify the assumption matches the workload.

If drift is suspected: (i) measure drift rate $V_T$ from history; (ii) use dynamic-regret bounds; (iii) allocate algorithmic budget for tracking.

Key Takeaway

Real demand drifts — $\\mathcal{R}_T^\\text{dyn} = O(T^{2/3} V_T^{1/3})$ is the right bound. Algorithmic responses include sliding windows, exponential weighting, and change-point detection. Production CDNs handle drift with LRU + ML prediction; coded augmentation is an open research opportunity.

Non-Stationary Demand and Concept Drift